数据结构第8章查找(作业)

时间：2026-01-20

数据结构

第8章查找

第8章查找8.1 查找的基本概念 8.2 静态查找表 8.3 动态查找表 8.4 哈希表

数据结构

第8章查找

8.1 查找的基本概念关键字：数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。如果一个关键字可以唯一标识列表中的一个数据元素，则称其为主关键字，否则为次关键字。

当数据元素仅有一个数据项时，数据元素的值就是关键字。

数据结构

第8章查找

查找：根据给定的关键字值，在查找表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在查找表中的位置。若找到相应的数据元素，则称查找是成功的，否则称查

找是失败的，此时应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。

数据结构

第8章查找

8.2 静态查找表8.2.1 顺序查找法顺序查找法的过程是：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，否则查找失败。存储结构通常为顺序结构，也可为链式结构。

数据结构

第8章查找

//静态查找表的顺序存储结构 typedef struct { ElemType *elem; //数据元素存储空间基址，建 //表时按实际长度分配，0号单元留空 int length; //表长度 } SSTable;

数据结构

第8章查找基于顺序结构的算法如下： 

int Search_Seq(SSTable ST, KeyType key)

{ // 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。算法9.1 int i; ST.elem[0].key=key; // 哨兵

for(i=ST.length;!EQ(ST.elem[i].key,key);--i); // 从后往前找

return i;}

// 找不到时，i为0

其中ST.elem[0]称为监视哨，可以起到防止越界的作用。

数据结构

第8章查找

8.2.2 有序表的查找折半查找法又称二分法查找法，这种方法适用于有序表。

其基本过程是：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不

存在为止，此时查找不成功。

数据结构

第8章查找

图8.1 折半查找示意图

数据结构

第8章查找折半查找的算法如下： int Search_Bin(SSTable ST, KeyType key) { // 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0。算法9.2 low=1 ; high=ST.length; // 置区间初值 while(low<=high) { mid=(low+high)/2; if EQ(key,ST.elem[mid].key) // 找到待查元素 return mid; else if LT(key,ST.elem[mid].key) high=mid-1; // 继续在前半区间进行查找 else low=mid+1; // 继续在

后半区间进行查找 } return 0; // 顺序表中不存在待查元素 }

数据结构

第8章查找

8.2.3 索引顺序表的查找(分块查找法)分块查找法要求将列表组织成以下索引顺序结构：  首先将列表分成若干个块(子表)。一般情况下，块的长度均匀，最后一块可以不满。每块中元素任意排列，即块内无序，但块与块之间有序。 

构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置，以及每块中的最大关键字(或最小关键字)。索引表按关键字有序排列。

数据结构

第8章查找下图的索引顺序表包括三个块，第一个块起始地址0,块内最大关键字25;第二个块起始地址为5, 块内最大关键字 58;第三个块起始地址为10,块内最大关键字为88。 

索引表 25 58 88

各块内的最大关键字各块的起始地址

列表 18 14 12 25 0 1 2 3

8 4

28 32 45 36 58 60 88 71 5 6 7 8 9 10 11 12