首页 > 其他 > 详细

第七章学习小结

时间:2019-06-01 20:28:36      阅读:57      评论:0      收藏:0      [点我收藏+]

第七章学习小结

一、课本笔记

  1、线性表的查找

  1.1、顺序查找

    (1)从表的一端开始,依次将记录的关键字和给定值进行比较,若某个记录的关键字和给定值相等,则查找成功;反之,若扫描整个表后,仍未找到关键字和给定值相等的记录,则查找失败

    (2)时间复杂度O(n)

    (3)优点:算法简单,对表结构无要求,无论记录是否按关键字有序均可应用

    (4)缺点:平均查找长度较大,查找效率较低

  1.2、折半查找

    (1)满足有序、顺序存储可用

    (2)T(n)=O(log2(n)),S(n)=O(1)  

    (3)无序顺序存储:T(n)=O(nlog(n))+O(log2(n))=O(nlog2(n))

    (4)关于链式存储:可以应用二分查找,但不能在log2(n)时间复杂度内,因为无法随机存取

    (5)二分查找应用场景局限性(适用于静态查找):

      ①顺序存储

      ②针对有序数据

      ③数据量小且比较操作不耗时,不需要二分

      ④数据量不可太大(超出内存可用连续空间)

  2、树表的查找

  2.1、二叉排序树

    (1)条件:

      ①左子树小于根节点,右子树大于根节点

      ②左子树是二叉排序树

      ③右子树是二叉排序树

    (2)过程:

      ①查找

      ②插入

      ③创建

      ④删除

  2.2、不同插入次序生成结果不同

    (1)最好:O(log2n)

    (2)最坏:O(n)

  3、散列表的查找

  3.1、主要研究问题

    (1)如何构造散列函数

    (2)如何处理冲突

  3.2、好的散列函数的规则

    (1)函数计算要简单,每一关键字只能由一个散列地址与之对应

    (2)函数的值域须在表长的范围内,计算出的散列地址的分布应均匀,尽可能减少冲突

二、查找列表的编程题

7-1散列
这个问题的任务很简单:将一组不同的正整数插入哈希表,并输出输入数的位置。哈希函数定义为h(键)=键的%大小,而大小是哈希表的最大大小。二次探测(只有正增量)用于解决碰撞。
注意,表的大小最好是最好的。如果用户给出的最大大小不是质数,则必须重新定义表大小为大于用户给出的大小的最小质数。
输入规范:
每个输入文件都包含一个测试用例。对于每个情况,第一行包含两个正数:mize(≤10)
4
)和n(≤mize)分别是用户定义的表大小和输入数。然后在下一行给出了n个不同的正整数。一行中的所有数字都由一个空格分隔。
输出规范:
对于每个测试用例,在一行中打印输入数字的相应位置(索引从0开始)。一行中的所有数字都由一个空格分隔,并且在行的末尾必须没有多余的空格。如果无法插入数字,则打印“-”。
样本输入:
4 4
10 6 4 15
样本输出:
0 1 4 -

  • 问题主要分为找到最小的质数和找出存储的位置
#include <iostream>
using namespace std;

bool isPrime( int s )
{//一个数若可以进行因数分解,那么分解时得到的两个数一定是一个小于等于sqrt(n),一个大于等于sqrt(n) 
    if (s==1)
        return false;
    for (int i=2; i*i<=s; ++i){
        if (s%i==0)
            return false;
    }
    return true;
}

int main()
{
    int mize, n, num, ide;
    int j, t;
    cin >> mize >> n;
    while(!isPrime( mize )) //如果不为质数,则加一 
        mize++;
    int* last = new int [mize];
    for (int i=0; i<mize; ++i)//将数组全部置为-1 
        last[i] = -1;
    for (int i=0; i<n; ++i){//每个输入数进行判断,存入数组 
        cin >> num;
        ide = num%mize;//判断存储的位置 
        if (i!=0)//对空格的输出 
            cout <<  ;
        if (last[ide]!=-1){//如果此处存储了内容,则寻找下一个可以存储的地址 
            for ( j=1; j<=mize; ++j ){
                t = ( ide+j*j ) % mize;
                if (last[t]==-1){
                    last[t] = 1;
                    break;
                }
            }
            if ( j > mize)
                cout << -;
            else
                cout << t;
        }
        else{
            last[ide] = 1;
            cout << ide;
        }
    }
    delete [] last;    
    return 0;
}
7-1 QQ帐户的申请与登陆 (30 分)
 

实现QQ新帐户申请和老帐户登陆的简化版功能。最大挑战是:据说现在的QQ号码已经有10位数了。

输入格式:

输入首先给出一个正整数N(≤),随后给出N行指令。每行指令的格式为:“命令符(空格)QQ号码(空格)密码”。其中命令符为“N”(代表New)时表示要新申请一个QQ号,后面是新帐户的号码和密码;命令符为“L”(代表Login)时表示是老帐户登陆,后面是登陆信息。QQ号码为一个不超过10位、但大于1000(据说QQ老总的号码是1001)的整数。密码为不小于6位、不超过16位、且不包含空格的字符串。

输出格式:

针对每条指令,给出相应的信息:

1)若新申请帐户成功,则输出“New: OK”;
2)若新申请的号码已经存在,则输出“ERROR: Exist”;
3)若老帐户登陆成功,则输出“Login: OK”;
4)若老帐户QQ号码不存在,则输出“ERROR: Not Exist”;
5)若老帐户密码错误,则输出“ERROR: Wrong PW”。

输入样例:

5
L 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
L 1234567890 myQQ@qq
L 1234567890 myQQ@qq.com

输出样例:

ERROR: Not Exist
New: OK
ERROR: Exist
ERROR: Wrong PW
Login: OK
  • 第二题感觉比第一题的思路要简单,但是真正去打的时候发现查找的时候很麻烦,然后我去看了一下网上的代码,发现大部分用的都是map函数解决的,我就去看了一下map函数的用法
    #include <iostream>
    #include <map>
    using namespace std;
    map<string,string> Map;
    map<string,string>::iterator it;
    
    int main()
    {
        int N;
        string select, number, password;
        cin >> N;
        while( N-- ){
            cin >> select;
            if( select == "N" ){//注册 
                cin >> number >> password;
                if( Map.find(number) == Map.end() ){//如果不存在,就存入注册 
                    Map[number]=password;
                    cout << "New: OK" << endl;
                }
                else//存在则报错已存在 
                    cout << "ERROR: Exist" << endl;
            }
            else{//登陆 
                cin >> number >> password;
                if( Map.find(number) != Map.end() ){//已注册 
                    if( Map[number] == password )//密码正确 
                        cout << "Login: OK" << endl;
                    else//密码错误 
                        cout << "ERROR: Wrong PW" << endl;
                }
                else //未注册 
                    cout << "ERROR: Not Exist" << endl;
            }
        }
        return 0; 
    }

     

三、一些别的

   https://blog.csdn.net/yibcs/article/details/12576729这个是在百度看到的关于map函数的用法

在题目里面我主要用到的是:

  1、end()   返回指向map末尾的迭代器

  2、 find()  查找一个元素

  3、修改Map["sunquan"]=11111;

四、心得

  这周的作业好像没有之前的难理解,但是还是需要灵活的思维,还是需要多看多打才能训练到自己的思考能力。

第七章学习小结

原文:https://www.cnblogs.com/zhongjieying/p/10960818.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!