数据结构查找课件.ppt

1、数据结构数据结构1 1数据结构数据结构第第9 9章章 查找查找n什么是查找？什么是查找？n静态查找静态查找n动态查找动态查找n哈希表哈希表数据结构数据结构2 2n集合关系集合关系n查找表（查找表（search tablesearch table）数据结构数据结构3 3查找的基本概念查找的基本概念 n静态查找表静态查找表（Static Search TableStatic Search Table）：在使用时）：在使用时主要作前两种统称为主要作前两种统称为“查找查找”的操作。即的操作。即n动态查找表动态查找表（Dynamic Search TableDynamic Search Table）数据

2、结构数据结构4 4数据结构数据结构5 5查找过程的主要操作是关查找过程的主要操作是关键字的比较，所以通常以键字的比较，所以通常以“平均比较次数平均比较次数”来衡来衡量查找算法的时间效率。量查找算法的时间效率。niiiCP1数据结构数据结构6 6静态查找表静态查找表数据结构数据结构7 7顺序表的查找（顺序查找）顺序表的查找（顺序查找），以顺序表或线性链表表示静态查找表。，以顺序表或线性链表表示静态查找表。数据结构数据结构8 8顺序查找的实现顺序查找的实现n#define LIST_INIT_SIZE 100 #define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量线性表

3、存储空间的初始分配量 #define LISTINCREMENT 10 #define LISTINCREMENT 10 / /线性表存储空间的分配增量线性表存储空间的分配增量 typedef structtypedef struct ElemType ElemType * *elemelem; /; /存储空间基址存储空间基址intint length; / length; /当前长度当前长度int listsizeint listsize; /; /当前分配的存储容量当前分配的存储容量 SSTableSSTable; ; 数据结构数据结构9 9数据结构数据结构1010顺序查找算法分析顺序查

4、找算法分析1 .)1.(.21)1.(12111nniniiiPnpnPninnCP 11.pppnn数据结构数据结构11 11有序表的查找（折半查找）有序表的查找（折半查找）数据结构数据结构1212数据结构数据结构1313数据结构数据结构1414折半查找的实现折半查找的实现n折半查找的主要步骤为：折半查找的主要步骤为： （1 1）置初始查找范围：）置初始查找范围：low=1low=1，high=n high=n （2 2）求查找范围中间项：）求查找范围中间项：mid=(low+high)/2mid=(low+high)/2 （3 3）将指定的关键字值）将指定的关键字值k k与中间项与中间项a

5、mid.keyamid.key比较比较若相等，查找成功，找到的数据元素为此时若相等，查找成功，找到的数据元素为此时mid mid 指向的指向的位置；位置；若小于，查找范围的低端数据元素指针若小于，查找范围的低端数据元素指针lowlow不变，高端数不变，高端数据元素指针据元素指针highhigh更新为更新为mid-1;mid-1;若大于，查找范围的高端数据元素指针若大于，查找范围的高端数据元素指针highhigh不变，低端不变，低端数据元素指针数据元素指针lowlow更新为更新为mid+1;mid+1; （4 4）重复步骤（）重复步骤（2 2）、（）、（3 3）直到查找成功或查找范）直到查找成功

6、或查找范围空（围空（lowhighlowhigh），即查找失败为止。），即查找失败为止。数据结构数据结构1515索引顺序表的查找（分块查找）索引顺序表的查找（分块查找）数据结构数据结构1616数据结构数据结构1717分块查找的基本思想分块查找的基本思想数据结构数据结构1818数据结构数据结构1919数据结构数据结构2020二叉排序树二叉排序树数据结构数据结构2121数据结构数据结构2222数据结构数据结构2323 数据结构数据结构2424数据结构数据结构2525101iiicp310/ )3443221 (数据结构数据结构2626数据结构数据结构272730303030202030302020

7、4040303020204040101030302020404010102525303020204040101025254545数据结构数据结构2828 数据结构数据结构2929 Insert BST(BiTree &T, ElemTypeInsert BST(BiTree &T, ElemType e ) e )if (!SearchBST ( T, e.keyif (!SearchBST ( T, e.key, NULL, p ) / , NULL, p ) / 查找不成功查找不成功s = (BiTree)malloc(sizeof(BiTNodes = (BiTree)malloc(si

8、zeof(BiTNode););if (!s) exit(1);if (!s) exit(1); / / 存储分配失败存储分配失败s-data = e; s-lchild = s-rchilds-data = e; s-lchild = s-rchild = NULL; = NULL; if ( !p ) T = s; if ( !p ) T = s; / / 插入插入 * *s s 为新的根结点为新的根结点else if ( e.key data.keyelse if ( e.key data.key ) ) p-lchildp-lchild = s; = s;/ / 插入插入 * *s s

9、 为为 * *p p 的左孩子的左孩子else p-rchildelse p-rchild = s; = s; / / 插入插入 * *s s 为为 * *p p 的右孩子的右孩子return TRUE;return TRUE; / if / ifelse return FALSE;/else return FALSE;/树中已有关键字相同的结点，不再插入树中已有关键字相同的结点，不再插入 / Insert BST / Insert BST 数据结构数据结构30306060404070703030505036368080454575752020删除叶子结点删除叶子结点2020和和7575606

10、04040707030305050363680804545数据结构数据结构31316060404070703030505036368080454575752020删除只有左子树删除只有左子树的单孩子结点的单孩子结点5050606040407070303045453636808075752020数据结构数据结构3232606040407070303050503636808045457575202060603636707030305050808045457575202060604545707030305050363680807575202060607070303050503636808045457

11、5752020数据结构数据结构3333数据结构数据结构3434数据结构数据结构3535平衡二叉树平衡二叉树 数据结构数据结构3636数据结构数据结构3737数据结构数据结构3838数据结构数据结构3939A A2 2B B1 1B BL LB Br rA Ar rh hh hh hLLLL型型A A0 0B B0 0B BL LB Br rA Ar rh hh hh h数据结构数据结构4040A A-2-2B B-1-1B Br rB BL LA AL Lh hh hh hRRRR型型A A0 0B B0 0B Br rA AL LB BL Lh hh hh h数据结构数据结构4141A A2

12、 2B B-1-1A Ar rh hB BL Lh hLRLR型型C CC CL Lh-1h-1C Cr rh-1h-11 1A A-1-1B B0 0A Ar rh hB BL Lh hC CL Lh-1h-1C Cr rh-1h-1C C0 0数据结构数据结构4242B B-1-1A A0 0B Br rh hA AL Lh hC CL Lh-1h-1C Cr rh-1h-1C C0 0A A-2-2B B1 1B Br rh hA AL Lh hRLRL型型C CL Lh-1h-1C Cr rh-1h-1C C1 1数据结构数据结构4343数据结构数据结构4444数据结构数据结构4545

13、1201200 01201201 180800 01201202 280801 130300 01201200 080800 030300 01201201 18080-1-130300 090900 01201201 180800 03030-1-190900 045450 01201201 180800 03030-2-290900 04545-1-160600 01201201 180800 030300 090900 045450 060600 0数据结构数据结构4646数据结构数据结构4747B-B-树树数据结构数据结构4848数据结构数据结构49492 50 80root 160

14、153 143 122 197 188 1752 20 402 55 701 9021019数据结构数据结构5050n基于基于B-B-树的查找树的查找B-B-树的查找过程是一个顺指针查找结点和在结树的查找过程是一个顺指针查找结点和在结点的关键字中进行交叉进行的过程。点的关键字中进行交叉进行的过程。2 50 80root 160 153 143 122 197 188 1752 20 402 55 701 9021019数据结构数据结构5151Result SearchBTree(BTree T,KeyTypeResult SearchBTree(BTree T,KeyType K) K) p

15、= T; q = NULL; found = FALSE; i = 0; p = T; q = NULL; found = FALSE; i = 0; while (p & !found) while (p & !found) i = Search(p i = Search(p, K); , K); if (i0 & p-keyi=K) found = TRUE; if (i0 & p-keyi=K) found = TRUE; else q = p; p = p-ptri else q = p; p = p-ptri; ; j+; j+; if (found) / if (found) /

16、查找成功查找成功 R.pt = p; R.i = i; R.tagR.pt = p; R.i = i; R.tag = 1; = 1; else / else / 查找不成功，返回插入位置信息查找不成功，返回插入位置信息 R.pt = q; R.i = i; R.tagR.pt = q; R.i = i; R.tag = 0; = 0; return R; return R; / SearchBTree / SearchBTree数据结构数据结构5252SearchBTreeSearchBTree2 100 190 3 100 150 190 数据结构数据结构5353数据结构数据结构54542

17、 80 2204 90 120 140 160p3 80 120 220 2 90 1002 140 160prepreprekm/2 数据结构数据结构55556 8 15 166 8 15 166 86 8 1515 16 2216 22 6 8 106 8 10 1515 16 18 22 3216 18 22 32 6 8 106 8 10 15 2015 2016 1816 18 22 3222 326 8 106 8 10 121215 2015 2016 18 1916 18 1922 32 40 5022 32 40 506 8 10 126 8 10 1215 20 4015

18、20 4016 18 1916 18 1922 3222 3250 5650 56 6 8 6 8 9 15 20 409 15 20 4016 18 1916 18 1922 26 32 3622 26 32 3650 52 55 5650 52 55 56 10 12 10 12 6 8 6 8 9 159 1516 18 1916 18 1922 2622 2650 52 55 5650 52 55 56 10 12 10 12 36 3836 38202032 4032 40数据结构数据结构5656n基于基于B-B-树的删除树的删除数据结构数据结构575790 11590 1158 8

19、40402828150 200150 20085 12085 120505060 8060 8090 11590 1158 840402828150 200150 20085 12085 12060608080数据结构数据结构585890908 840402828150 200150 20085 12085 1205050808090 11590 1158 840402828150 200150 20085 12085 120505060 8060 80删除删除6060与与115115数据结构数据结构59591201208 84040282820020085 15085 15050508080

20、90908 840402828150 200150 20085 12085 12050508080数据结构数据结构60601201208 84040282820020085 15085 150505080808 840402828150 200150 200858550508080数据结构数据结构6161哈希表哈希表数据结构数据结构6262n例：对于关键字序列例：对于关键字序列Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei，可设关键字的哈希函数如下：，可设关键字的哈希函数如下：F(key)=|ord(CH1)-ord(A）+1/2|，其中，其中，CH1为关键字中第一个字

21、母，为关键字中第一个字母，ord为字符的次序函数。为字符的次序函数。数据结构数据结构6363数据结构数据结构6464哈希函数的构造哈希函数的构造p直接定址所得地址集的大小和关键字集的大小直接定址所得地址集的大小和关键字集的大小相同，关键字和地址一一对应，不会产生冲突。相同，关键字和地址一一对应，不会产生冲突。但实际应用中能采用直接定址的情况极少。但实际应用中能采用直接定址的情况极少。 数据结构数据结构6565数据结构数据结构6666212265 569数据结构数据结构6767冲突的处理冲突的处理数据结构数据结构6868数据结构数据结构6969哈希表的查找和插入哈希表的查找和插入数据结构数据结构

22、7070nStatus SearchHash (HashTable H, KeyType kval, Status SearchHash (HashTable H, KeyType kval, int &p, intint &p, int &c) &c)/ p/ p指示待查记录在表中位置或插入位置指示待查记录在表中位置或插入位置,c,c用以计冲突次数用以计冲突次数p = Hash(kvalp = Hash(kval););/ / 求得哈希地址求得哈希地址while ( H.elemp.keywhile ( H.elemp.key != NULLKEY != NULLKEY& ( H.elemp

23、.key != kval& ( H.elemp.key != kval) ) ) ) collision(pcollision(p, +c);/, +c);/求得下一探查地址求得下一探查地址p pif ( H.elemp.key = kvalif ( H.elemp.key = kval ) )return SUCCESS; return SUCCESS; else return UNSUCCESS; else return UNSUCCESS; / SearchHash / SearchHash数据结构数据结构7171nStatus InsertHash (HashTable &H, Ele

24、mtypeStatus InsertHash (HashTable &H, Elemtype e) e)c = 0;c = 0;if ( HashSearch(H, e.keyif ( HashSearch(H, e.key, j, c)=SUCCESS ), j, c)=SUCCESS )return DUPLICATE;return DUPLICATE; else if ( c hashsizeH.sizeindex/2 ) else if ( c hashsizeH.sizeindex/2 ) / / 冲突次数冲突次数c c未达到上限，（阀值未达到上限，（阀值c c可调）可调）H.elemj = e; +H.countH.elemj = e; +H.count; return OK; ; return OK; / if / if else RecreateHashTable(Helse RecreateHashTable(H); / ); / 重建哈希表重建哈希表 / InsertHash / InsertHash