《数据结构课件、代码》第6章查找表.ppt
第6章 查找表,张成文北京邮电大学计算机学院,数据结构-第6章 查找,2,6.1 相关概念和术语,术语查找表 同一类型的记录(数据元素)的集合。数据元素之间存在着松散的关系。为了提高查找的效率，可在元素之间人为地附加某种确定的关系。关键字 记录(数据元素)中的某个数据项的值。主关键字 该关键字可以唯一地标识一个记录。次关键字 该关键字不能唯一标识一个记录。查找 指定某个值，在查找表中确定是否存在一个记录，该记录的关键字等于给定值。静态查找表 对查找表的查找仅是以查询为目的，不改动查找表中的数据。动态查找表 在查找的过程中同时插入不存在的记录，或删除某个已存在的记录。查找成功 查找表中存在满足查找条件的记录。查找不成功 查找表中不存在满足查找条件的记录。,数据项1 数据项2,记录（数据元素）,数据结构-第6章 查找,3,6.2 静态查找表,6.2.1 顺序表的查找6.2.2 有序表的查找6.2.3 索引顺序表的查找,数据稳定，变动很少的查找表,数据结构-第6章 查找,4,6.2.1 顺序表的查找 静态查找表以顺序表表示,0 1 2 n ST.elem0.n a1 a2 an算法描述,typedef struct ElemType*elem;int length;SSTable;,int Search_Seq1(SSTable ST,KeyType key)i=1；while(i=ST.length/Search_Seq1,int Search_Seq2(SSTable ST,KeyType key)ST.elem0.key=key;for(i=ST.length;ST.elemi.key!=key;i-)；return i;/Search_Seq2,数据结构-第6章 查找,5,程序设计技巧 设置监视哨，查找时每一步不必检测位置是否越界，提高算法效率。算法特点算法简单，对表中元素排列顺序无任何要求n很大时查找效率较低改进措施：非等概率查找时，可将查找概率高的记录尽量排在表前部。逐个查找的方法也可用于线性链表表示的静态查找表,数据结构-第6章 查找,6,6.2.2 有序表的查找,满足 ri.key ri+1.key,1 i n 仍可用顺序查找，但在找不到时不需比较到表尾，只需比较到比给定值大的记录就可终止。折半(对半/二分)查找法 0 1 2 3 4 5 6 7 8 9 10 11 05 13 19 21 37 56 64 75 80 88 92 low mid high=(low+high)/2 K=21 l h m K=85 l h m 1 11 6 1 11 6 1 5 3 7 11 9 4 5 4 10 11 10 10 9,数据结构-第6章 查找,7,算法描述,int Search_Bin(SSTable ST,keytype key)low=1;high=ST.length;/置区间初值 while(low=high)mid=(low+high)/2;if(key=ST.elemmid.key)return mid;/找到待查元素 else if(key ST.elemmid.key)high=mid-1;/继续在前半区间进行查找 else low=mid+1;/继续在后半区间进行查找 return 0;/顺序表中不存在待查元素/Search_Bin,数据结构-第6章 查找,8,6.2.3 索引顺序表的查找,表的构造 索引表 index1.b 最大关键字值 22 42 86 起始地址 1 5 9 主表 r 1.n（分块有序/有序）key 12 22 13 8 28 33 38 42 86 76 50 63 其它项 1 2 3 4 5 6 7 8 9 10 11 12,分块查找步骤1)折半或者顺序查找索引表，确定所在块2)在已确定的块中顺序查找/折半查找,数据结构-第6章 查找,9,性能分析,索引顺序查找的平均查找长度=查找“索引”的平均查找长度+查找“块”的平均查找长度,数据结构-第6章 查找,10,算法特点,实用中，各块大小不一定相等分块查找的代价是附加索引表的存储空间开销和建立索引表的时间开销可以在主表的每块后预留空闲位置，以便进行插入和删除操作时只涉及相应的块和该块的索引项。主表中各块可以集中顺序存储，也可以按块分别顺序存储；主表中的记录还可以采用单链表，或每块组成一个单链表。,数据结构-第6章 查找,11,6.3 动态查找表,二叉排序树,频繁进行插入、删除的查找表,数据结构-第6章 查找,12,二叉排序树BST(二叉查找/搜索树),1.定义 二叉排序树或者是空树，或者是满足如下性质的二叉树：1)若其左子树非空，则左子树上所有结点的值均小于根 结点的值；2)若其右子树非空，则右子树上所有结点的值均大于等 于根结点的值；3)其左右子树本身又各是一棵二叉排序树2.性质 中序遍历一棵二叉排序树，将得到 一个以关键字递增排列的有序序列,45,24,53,12,28,90,数据结构-第6章 查找,13,在二叉排序树上的操作 通常，取二叉链表作为存储结构,1)查找,Bitree SearchBST(BiTree T,KeyType key)/在二叉排序树T中查找关键字值为 key 的结点，/找到返回该结点的地址，否则返回空。if(（!T）|EQ(key,T-data.key)return(T);else if(LT(key,T-data.key)return(SearchBST(T-lchild,key);else return(SearchBST(T-rchild,key);/SearchBST P228-9.5（a）,key=28 查找成功,key=32 查找失败,数据结构-第6章 查找,14,Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree/SearchBST P228-9.5(b),Status InsertBST(BiTree else return FALSE/InsertBST P228-9.6,2)插入,数据结构-第6章 查找,15,3)生成 从空树出发，反复调用插入操作InsertBST即可。,例 10，18，3，8，12，2，7，3,10,数据结构-第6章 查找,16,4)删 除,53 20 90 10 50 86 95 4 12 41 52 88 91 30 45 87 89 92 39,(1),(2),(2),(3),被删除结点为*p的不同情况分析：p是叶子结点：修改其双亲指针即可,p只有左孩子：用p的左子树代替以p为根的子树 p只有右孩子：用p的右子树代替以p为根的子树,p有两个孩子：找到p的中序后继(或前趋)结点q；q的数据复制给p；删除只有右孩子(或左孩子)/无孩子的q。,数据结构-第6章 查找,17,之前各种查找表的结构特点：记录在表中的位置和它的关键字之间不存在一个确定的关系 查找的过程为给定值依次和集合中各个关键字进行比较，查找的效率取决于和给定值进行比较的关键字个数。不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。,6.4 哈希表,数据结构-第6章 查找,18,哈希表的基本思想 在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，理想状态不经过比较，一次存取就能得到所查元素。术语 哈希表 一个有限的连续的地址空间，用以容纳按哈希地址存储的记录。哈希函数 记录的存储位置与它的关键字之间存在的一种对应关系。Loc(ri)=H(keyi)冲突 对于keyikeyj，i j，出现的H(keyi)=H(keyj)的现象。,数据结构-第6章 查找,19,同义词 在同一地址出现冲突的各关键字。哈希(散列)地址 根据设定的哈希函数H(key)和处理冲突的方法确定的记录的存储位置。设计哈希表的过程 1)明确哈希表的地址空间范围。即确定哈希函数的值域。2)选择合理的哈希函数。该函数要保证所有可能的记录的哈希地址均在指定的值域内，并使冲突的可能性尽量小。3)设定处理冲突的方法。,
