第8章查找数据结构（C语言描述）
第8章 查找 数据结构（C语言描述）
目录8.1查找的基本概念8.2静态查找表8.3动态查找表哈希表8.4退出
目 录 8.4 哈 希 表 8.3 动 态 查 找 表 8.1 查找的基本概念 8.2 静 态 查 找 表 退 出
8.1查找的基本概念查找，也称为检索。在我们日常生活中，随处可见查找的实例。如查找某人的地址、电话号码：查某单位45岁以上职工等，都属于查找范畴。本书中，我们规定查找是按关键字进行的，所谓关键字（key)是数据元素（或记录)中某个数据项的值，用它可以标识(或识别)一个数据元素。例如，描述一个考生的信息，可以包含：考号、姓名、性别、年龄、家庭住址、电话号码、成绩等关键字。但有些关键字不能唯一标识一个数据元素，而有的关键字可以唯一标识一个数据元素。如刚才的考生信息中，姓名不能唯一标识一个数据元素（因有同名同姓的人），而考号可以唯一标识一个数据元素（每个考生考号是唯一的，不能相同)。我们将能唯一标识一个数据元素的关键字称为主关键字，而其它关键字称为辅助关键字或从关键字
8.1 查找的基本概念 查找，也称为检索。在我们日常生活中，随处可见查找 的实例。如查找某人的地址、电话号码；查某单位45岁 以上职工等，都属于查找范畴。本书中，我们规定查找 是按关键字进行的，所谓关键字(key)是数据元素(或记 录)中某个数据项的值，用它可以标识(或识别)一个数据 元素。例如，描述一个考生的信息，可以包含：考号、 姓名、性别、年龄、家庭住址、电话号码、成绩等关键 字。但有些关键字不能唯一标识一个数据元素，而有的 关键字可以唯一标识一个数据元素。如刚才的考生信息 中，姓名不能唯一标识一个数据元素(因有同名同姓的 人)，而考号可以唯一标识一个数据元素(每个考生考号 是唯一的，不能相同)。我们将能唯一标识一个数据元素 的关键字称为主关键字，而其它关键字称为辅助关键字 或从关键字
有了主关键字及关键字后，我们可以给香找下一个完整的定义。所谓查找，就是根据给定的值，在一个表中查找出其关键字等于给定值的数据元素，若表中有这样的元素，则称查找是成功的，此时查找的信息为给定整个数据元素的输出或指出该元素在表中的位置：若表中不存在这样的记录，则称查找是不成功的，或称查找失败并可给出相应的提示。因为查找是对已存入计算机中的数据所进行的操作，所以采用何种查找方法，首先取决于使用哪种数据结构来表示“表”，即表中结点是按何种方式组织的。为了提高查找速度，我们经常使用某些特殊的数据结构来组织表。因此在研究各种查找算法时，我们首先必须弄清这些算法所要求的数据结构，特别是存储结构。查找有内查找和外查找之分。若整个查找过程全部在内存进行，则称这样的查找为内查找：反之，若在查找过程中还需要访问外存，则称之为外查找。我们仅介绍内查找
有了主关键字及关键字后，我们可以给查找下一个完整 的定义。所谓查找，就是根据给定的值，在一个表中查 找出其关键字等于给定值的数据元素，若表中有这样的 元素，则称查找是成功的，此时查找的信息为给定整个 数据元素的输出或指出该元素在表中的位置；若表中不 存在这样的记录，则称查找是不成功的，或称查找失败， 并可给出相应的提示。 因为查找是对已存入计算机中的数据所进行的操作，所 以采用何种查找方法，首先取决于使用哪种数据结构来 表示“表” ，即表中结点是按何种方式组织的。为了提 高查找速度，我们经常使用某些特殊的数据结构来组织 表。因此在研究各种查找算法时，我们首先必须弄清这 些算法所要求的数据结构，特别是存储结构。 查找有内查找和外查找之分。若整个查找过程全部在内 存进行，则称这样的查找为内查找；反之，若在查找过 程中还需要访问外存，则称之为外查找。我们仅介绍内 查找
要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，但我们将找到给定值与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准，对于一个含有n个元素的表，查找成功时的平均查找长度可表示为ASL=≥pc，，其中 Pi为查找第i个元素的概率，且之p,=1，一般情形下我们认为查找每个元素的概率相等，C为查找第i个元素所用到的比较次数
要衡量一种查找算法的优劣，主要是看要找的值与关键字 的比较次数，但我们将找到给定值与关键字的比较次数的 平均值来作为衡量一个查找算法好坏的标准，对于一个含 有n个元素的表，查找成功时的平均查找长度可表示为 ASL= ，其中Ｐi为查找第i个元素的概率，且 =1 。一般情形下我们认为查找每个元素的概率相等，Ｃi为查 找第i个元素所用到的比较次数。 n i i i p c 1 n i pi 1
8. 2静态查找表8.2.1顺序查找1.顺序查找的基本思想顺序查找是一种最简单的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值K相比较，若相等，则查找成功，若整个表扫描完毕，仍未找到关键字等于K的元素，则查找失败。顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。下面以顺序表的形式来描述算法
8．2 静态查找表 8.2.1 顺序查找 1．顺序查找的基本思想 顺序查找是一种最简单的查找方法，它的基本思想是： 从表的一端开始，顺序扫描线性表，依次将扫描到的 结点关键字和待找的值Ｋ相比较，若相等，则查找成 功，若整个表扫描完毕，仍未找到关键字等于Ｋ的元 素，则查找失败。 顺序查找既适用于顺序表，也适用于链表。若用顺序 表，查找可从前往后扫描，也可从后往前扫描，但若 采用单链表，则只能从前往后扫描。另外，顺序查找 的表中元素可以是无序的。 下面以顺序表的形式来描述算法
2.顺序查找算法实现#define n 10//n为表的最大长度tnodetypedef structelemtypekey；/key为关键字，类型设定为elemtype;//在表R中查int seqsearch (node R[n+1l,elemtype k)找关键字值为K的元素(inti=n;R[o].key=k;//从表尾开始向前扫描While (R[i].key!=k)i--;return i;}
2．顺序查找算法实现 #define n 10 //n为表的最大长度 typedef struct node {. elemtype key; //key为关键字，类型设定为elemtype }; int seqsearch (node R[n+1],elemtype k) //在表Ｒ中查 找关键字值为Ｋ的元素 {int i=n; R[0].key=k; //从表尾开始向前扫描 While (R[i].key!=k) i-; return i;}
在函数seqsearch中，若返回的值为0表示查找不成功，否则查找成功。函数中查找的范围从Rn到R11，Rro为监视哨，起两个作用，其一，是为了省去判定while循环中下标越界的条件1，从而节省比较时间，其二，保存要找值的副本，若查找时，遇到它，表示查找不成功。若算法中不设立监视哨R[O]，程序花费的时间将会增加，这时的算法可写为下面形式。int seqsearch(node R[n+1], elemtype k)(int i=n;while(R[i].key!=k)&&(i>=1) i--;return i,当然上面算法也可以改成从表头向后扫描，将监视哨设在右边，这种方法请读者自已完成
在函数seqsearch中，若返回的值为０表示查找不成功，否 则查找成功。函数中查找的范围从R[n]到R[１]，R[０]为监视 哨，起两个作用，其一，是为了省去判定 while循环中下 标越界的条件i≥1，从而节省比较时间，其二，保存要找值 的副本，若查找时，遇到它，表示查找不成功。若算法中 不设立监视哨R[0]，程序花费的时间将会增加，这时的算 法可写为下面形式。 int seqsearch(node R[n+1]，elemtype k) {int i=n; while(R[i].key!=k)&&(i>=1) i-; return i; } 当然上面算法也可以改成从表头向后扫描，将监视哨设在右 边，这种方法请读者自己完成
3.顺序香找性能分析假设在每个位置查找的概率相等，即有p=1/n，由于查找是从后往前扫描，则有每个位置的查找比较次数C=1C，=2，….，C,=n，于是，查找成功的平均查找ASL=p.c,(n-i+)=”,即它的时间复杂度为O(n)。这就是说，查找成功的平均比较次数约为表长的一半。若k值不在表中，则必须进行n+1次比较之后才能确定查找失败。另处，从ASL可知，当n较大时，ASL值较大查找的效率较低。顺序查找的优点是算法简单，对表结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序或无序，它都同样适用。顺序查找的缺点是查找效率低，当n较大时，不宜采用顺序查找，而必须寻求更好的查找方法
3.顺序查找性能分析 假设在每个位置查找的概率相等，即有pi =1/n，由于查 找是从后往前扫描，则有每个位置的查找比较次数Cn =1， Cn-1 =2，.，C1 =n，于是，查找成功的平均查找ASL= = = = ,即它 的时间复杂度为O(n)。 这就是说，查找成功的平均比较次数约为表长的一半。 若k值不在表中，则必须进行n+1次比较之后才能确定查 找失败。另处，从ASL可知，当n较大时，ASL值较大， 查找的效率较低。 n i i i p c 1 n i n n i 1 1 [ ( 1)] 2 n1 顺序查找的优点是算法简单，对表结构无任何要求，无 论是用向量还是用链表来存放结点，也无论结点之间是 否按关键字有序或无序，它都同样适用。顺序查找的缺 点是查找效率低，当n较大时，不宜采用顺序查找，而 必须寻求更好的查找方法
8.2.2有序表的查找（折半查找）1.二分查找的基本思想二分香查找，也称折半香找，它是一种高效率的香找方法但二分查找有条件限制：要求表必须用向量作存贮结构且表中元素必须按关键字有序（升序或降序均可）。我们不妨假设表中元素为升序排列。二分查找的基本思想是：首先将待查值K与有序表R[1]到R[n|的中点mid（=(1+n)/2取下界），上的关键字R[mid].key进行比较，若相等，则查找成功；否则，若R[mid].key>k，则在R[1]到R[mid-1]中继续查找，若有R[mid].key<k，则在R[mid+1]到R[n]中继续查找。每通过一次关键字的比较，区间的长度就缩小一半，区间的个数就增加一倍，如此不断进行下去直到找到关键字为K的元素：若当前的查找区间为空(表示查找失败）
8.2.2 有序表的查找(折半查找) 1.二分查找的基本思想 二分查找，也称折半查找，它是一种高效率的查找方法。 但二分查找有条件限制：要求表必须用向量作存贮结构， 且表中元素必须按关键字有序(升序或降序均可)。我们不 妨假设表中元素为升序排列。二分查找的基本思想是： 首先将待查值K与有序表R[1]到R[n]的中点mid（=(1+n)/2 取下界），上的关键字R[mid].key进行比较，若相等，则 查找成功；否则，若R[mid].key>k ， 则在R[1]到R[mid-1] 中继续查找，若有R[mid].key<k ， 则在R[mid+1]到R[n] 中继续查找。每通过一次关键字的比较，区间的长度就 缩小一半，区间的个数就增加一倍，如此不断进行下去， 直到找到关键字为K的元素；若当前的查找区间为空(表 示查找失败)