数据结构：第6章 查找表

《数据结构：第6章 查找表》由会员分享，可在线阅读，更多相关《数据结构：第6章 查找表（18页珍藏版）》请在金锄头文库上搜索。

1、第6章 查找表数据结构-第6章 查找26.1 相关概念和术语相关概念和术语 术语术语 查找表查找表 同一类型的记录(数据元素)的集合集合。 数据元素之间存在着松散的关系。数据元素之间存在着松散的关系。为了提高查找的效率，可在元素之间人为地附加人为地附加某种确定的关系。关键字关键字 记录(数据元素)中可以唯一地标识记录的某个数据项的值。查找查找 指定某个值，在查找表中确定是否存在一个记录，该记录的关键字关键字等于给定值。静态查找表静态查找表 对查找表的查找仅是以查询为目的，不改动查找表中的数据。动态查找表动态查找表 在查找的过程中同时插入不存在的记录，或删除某个已存在的记录。查找成功查找成功 查

2、找表中存在满足查找条件的记录。查找不成功查找不成功 查找表中不存在满足查找条件的记录。数据项数据项1 1 数据项数据项2 2 记录（数据元素）记录（数据元素）数据结构-第6章 查找36.2 静态查找表静态查找表6.2.1 6.2.1 顺序表的查找顺序表的查找6.2.2 6.2.2 有序表的查找有序表的查找6.2.3 6.2.3 索引顺序表的查找索引顺序表的查找数据稳定，变动很少的查找表数据稳定，变动很少的查找表数据结构-第6章 查找46.2.1 顺序表的查找顺序表的查找 静态查找表以顺序表表示静态查找表以顺序表表示 0 1 2 n ST.elem0.n a1 a2 an算法描述算法描述type

3、def struct ElemType *elem;int length;SSTable;keyint Search_Seq1( SSTable ST, KeyType key) i=1； while (i=ST.length & ST.elemi.key!=key) i+;if (i=ST.length) return i; else return 0;/Search_Seq1int Search_Seq2( SSTable ST, KeyType key) ST.elem0.key=key; for (i=ST.length; ST.elemi.key!=key; i-)；return i

4、;/Search_Seq2数据结构-第6章 查找5程序设计技巧程序设计技巧 设置监视哨，查找时每一步不必检测位置是否越界，提高算法效率。算法特点算法特点算法简单，对表中元素排列顺序无任何要求n很大时查找效率较低改进措施：非等概率查找时，可将查找概率高的记录尽量排在表前部。逐个查找的方法也可用于线性链表线性链表表示的静态查找表数据结构-第6章 查找66.2.2 有序表的查找有序表的查找 满足 ri.key ri+1.key, 1 i n 仍可用顺序查找，但在找不到时不需比较到表尾，只需比较到比给定值大的记录就可终止。折半折半(对半对半/二分二分)查找法查找法 0 1 2 3 4 5 6 7 8

5、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) r

6、eturn mid; / 找到待查元素 else if ( keydata. key ) ) return ( T ) ; else if ( LT( key , T -data. key ) ) return (SearchBST ( T - lchild, key ); else return (SearchBST ( T - rchild, key ); /SearchBST452453122890 Tkey=28 查找成功key=32 查找失败nullnull数据结构-第6章 查找14452453122890T32fStatus SearchBST(BiTree T, KeyType

7、key, BiTree f, BiTree &p)/f指向当前结点的双亲,初始调用值为NULL。/查找成功，p指向该结点，并返回TRUE；/查找失败，p指向查找路径上的最后一个结点，并返回FALSE if (!T) p=f; return FALSE; else if EQ(key, T-data.key) p=T; return TRUE; else if LT(key, T-data.key) return SearchBST(T-lchild, key, T, p ); else return SearchBST(T-rchild, key, T, p);/SearchBSTStatus

8、 InsertBST (BiTree &T,ElemType e) if (!SearchBST(T, e.key, NULL, P) s=(BiTree)malloc(sizeof(BiTNode); s-data=e; s-lchild=s-rchild=NULL; if (!T) T=s; else if LT(e.key, p-data.key) p-lchild = s; else p-rchild = s; return TRUE; else return FALSE /InsertBST2) 插入插入数据结构-第6章 查找153) 生成生成 从空树出发，反复调用插入操作Inser

9、tBST即可。例 10， 18， 3， 8， 12， 2， 7， 310101810183101838101838 12101838 122101838 1227101838 12273数据结构-第6章 查找16之前各种查找表的结构特点：之前各种查找表的结构特点： 记录在表中的位置和它的关键字之间不存在一个确定的关系 查找的过程为给定值依次和集合中各个关键字进行比较，查找的效率取决于和给定值进行比较的关键字个数。 不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。6.4 哈希表哈希表数据结构-第6章 查找17哈希表的基本思想哈希表的基本思想 在记录的存储地址和它的关键字之间建立一

10、个确定的对应关系；这样，理想状态不经过比较，一次存取就能得到所查元素。术语术语 哈希表哈希表 一个有限的连续的地址空间，用以容纳按哈希地址存储的记录。 哈希函数哈希函数 记录的存储位置与它的关键字之间存在的一种对应关系。 Loc(ri)=H(keyi) 冲突冲突 对于keyikeyj， i j， 出现的H(keyi) = H(keyj)的现象。 数据结构-第6章 查找18 同义词同义词 在同一地址出现冲突的各关键字。 哈希哈希(散列散列)地址地址 根据设定的哈希函数H(key)和处理冲突的方法确定的记录的存储位置。 设计哈希表的过程设计哈希表的过程 1)明确哈希表的地址空间范围。即确定哈希函数的值域。 2)选择合理的哈希函数。该函数要保证所有可能的记录的哈希地址均在指定的值域内，并使冲突的可能性尽量小。 3)设定处理冲突的方法。