第七章 查找

一、查找的基本概念

（1）关键字

关键字是数据元素中某个数据项的值，用它可以标识一个数据元素（记录）。

（2）查找

查找是根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素。若表中存在这样的一个记录，则称查找成功，此时查找的结果可以给出整个记录的信息或指示该记录在查找表中的位置。

（3）动态查找表和静态查找表

若在查找的同时对表做修改操作（如插入和删除），则对应的表称之为动态查找表，否则称之为静态查找表。

（4）平均查找长度

为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，成为查找算法在查找成功时的平均查找长度。

对于含有n个记录的表，查找成功时的平均查找长度为 ASL=P₁C₁+P₂C₂+…+P_nC_n

P_i 为查找表中第i个记录的概率（P_i =1/n），C_i为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行比较的关键字个数。

 

二、

（1）线性表的查找

顺序查找：从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败。

数据元素类型定义：

顺序表的定义

设置哨兵的顺序查找

设置哨兵的顺序查找和普通的顺序查找相比，可以减少比较次数。

顺序查找的 ASL=(n+1)/2，时间复杂度为O(n)

优点：算法简单，对表结构无要求；缺点：平均查找长度大，查找效率低。

折半查找：折半查找必须采用顺序存储结构，而且表中元素按关键字有序排列

折半查找的非递归算法

 折半查找的递归算法

对于长度为n的有序表，折半查找法在查找成功时和给值进行比较的关键字个数至多为log₂n+1，取不大于log₂n的最大整数

折半查找的时间复杂度为O(log₂n)

优点：比较次数少，查找效率高；缺点：对表结构要求高，不适用于数据元素经常变动的线性表

（2）二叉排序树

性质：中序遍历一颗二叉树得到一个结点值递增的有序序列

二叉链表存储表示

递归查找算法

含有n个结点的二叉排序树的平均查找长度和树的形态有关，当构成的二叉排序树为单支树，平均查找长度为(n+1)/2；最好情况下平均查找长度与log₂n成正比；综合所有情况，二叉排序树查找的时间复杂度为O(log₂n)

二叉排序树的插入、创建、删除都是基于查找进行的

（3）平衡二叉树

具有如下特征的二叉排序树：左子树和右子树的深度之差的绝对值不超过1，左子树和右子树也是平衡二叉树

平衡调节方法：找到离插入结点最近且平衡因子绝对值超过1的祖先结点，以该结点为根的子树称为最小平衡子树，可将重新平衡的范围局限于这颗子树

4种情况：LL型、RR型、LR型、RL型

（4）B-树（平衡多叉树）

B-树具有平衡、有序、多路的特点，一种在外存文件系统中常用的动态索引系统；所有叶子结点均在同一层次，树中每个结点中的关键字都是有序的；

在B-树上进行查找的过程是一个顺指针查找结点，和在结点的关键字中查找交叉进行的过程。

（5）B+树

一颗m阶的B+树和B-树的差异在于：

1、有n颗子树的结点中有含有n个关键字

2、所有的叶子结点中包含了全部关键字的信息，以及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接

3、所有的非终端结点可以看成是索引部分，结点中仅含有其子树中的最大关键字

（6）散列表

散列函数和散列地址：p=H(key)，这个对应关系H为散列函数，p为散列地址

散列表：一个有限连续的地址空间，通常散列表的存储空间是一个1一维数组，散列地址是数组下标

冲突和同义词：对不同的关键字可能得到同一散列地址的现象称为冲突，即key1≠key2，H(key1)=H(key2)，key1和key2称为同义词

散列函数的构造函数：数字分析法、平方取中法、折叠法、除留余数法

处理冲突的方法：开放地址法Hi=(H(key)+di)%m（线性探测法d_i=1,2,3…m-1、二次探测法d_i=1²,-1²,2²,-2²,3²,…k²,-k²、伪随机探测法）

                               链地址法(把具有相同链地址的记录放在同一个单链表)

散列表的查找

查找过程中需和给定值进行比较的关键字的个数取决于三个因素：散列函数、处理冲突的方法和散列表的装填因子

散列表的装填因子α=表中填入的记录数/散列表的长度，α标志散列表的装满程度，α越小，发生冲突的可能性越小

作业题就运用到散列表的查找

 

思路：

1、判断表格大小是否为素数，若不是素数，则找到最大素数，并将表格大小置为最大素数

2、将数据元素加入哈希表中，增加vi数组，用于判断该散列位置是否已有元素

3、处理冲突的方法，二次探测法

4、输出元素所在位置，如果无法插入号码，输出“ - ”，注意行末不能有空格

代码如下

1 #include
      
        2 #include
       
         3 using namespace std; 4  5 bool isprime(int a) 6 {
    //判断是否为素数  7     if(a==1) return false; //1不是素数，当表大小为1时需要找出最大素数  8     int k; 9     k=(int)sqrt(a);10     for(int i=2;i<=k;i++)11      if(a%i==0) return false;12     return true;13 }14 15 int findprime(int size)16 {
    //若表大小不为素数，找出最大素数 17     for(int i=size; ;i++)18     {19         if(isprime(i)==true) return i;20     }21 } 22 23 int main()24 {25     int MSize,N,num,h;26     cin>>MSize>>N;27     int TMSize=findprime(MSize); //确定表大小为最大素数 28     bool vi[TMSize]={
    false}; //初始化vi数组为false，vi数组中元素为false表示散列表中该下标元素值为空 29     for(int i=0;i
        
         >num;32         h=num%TMSize; //求出每个元素的散列地址 33         if(vi[h]==false)  34         {
    //散列表中该下标对应元素为空，可插入元素，置vi数组中该下标元素值为true 35             cout<
         
          =TMSize) cout<<'-';//找不到空位，即无法插入 52         }53         if(i!=N-1) cout<<' ';54     }55     return 0;56 }
         
        
       
      

 

上次的目标是自己打出普里姆算法和克鲁斯卡尔算法的代码，实现起来还是有困难的，尽量自己独立完成，但一定程度上还是需要书本的帮助，对算法理解得不够透彻。这次的目标是静下心来好好复习，准备期末考试。