數(shù)據(jù)結(jié)構(gòu)集合與搜索算法

1、136集合與搜索一、復(fù)一、復(fù)習(xí)要點(diǎn)要點(diǎn)集合是最基本的抽象數(shù)據(jù)類(lèi)型之一。本章討論了集合的三種存儲(chǔ)表示：位數(shù)組表示、有序鏈表表示、并查集。在本章的后半部分，討論了與集合相關(guān)的搜索方法和簡(jiǎn)單的性能分析方法，包括適用于靜態(tài)搜索表的順序搜索和折半搜索及代表動(dòng)態(tài)搜索表的二叉搜索樹(shù)和AVL樹(shù)?？梢允褂脭U(kuò)充的二叉搜索樹(shù)描述順序搜索和折半搜索，從而推導(dǎo)出估算搜索效率的公式。靜態(tài)搜索表在整個(gè)程序的運(yùn)行期間結(jié)構(gòu)不會(huì)變化，其搜索效率隨著表中對(duì)象的個(gè)數(shù)n不斷增長(zhǎng)

2、。動(dòng)態(tài)搜索表因各個(gè)對(duì)象的輸入順序不同，得到的搜索表的形態(tài)不同，典型的是二叉搜索樹(shù)。在具有n個(gè)對(duì)象的二叉搜索樹(shù)中，搜索效率最高的是高度最低的二叉搜索樹(shù)。為確保二叉搜索樹(shù)始終保持搜索效率最高，必須在輸入新的對(duì)象時(shí)判斷二叉搜索樹(shù)是否“失去平衡”，并進(jìn)行適當(dāng)?shù)钠胶庑D(zhuǎn)，使二叉搜索樹(shù)的高度降到最低。這就是AVL樹(shù)。在AVL樹(shù)的討論中，4種平衡旋轉(zhuǎn)，選擇參加平衡旋轉(zhuǎn)的3個(gè)結(jié)點(diǎn)是關(guān)鍵，必須加以注意。本章復(fù)習(xí)的要點(diǎn)是：1、基本知識(shí)點(diǎn)必須理解集合及其表示

3、方法，包括位數(shù)組表示、有序鏈表表示及其相關(guān)操作的實(shí)現(xiàn)算法集合及其表示。理解并查集實(shí)現(xiàn)的方法。理解搜索的概念，理解靜態(tài)搜索表結(jié)構(gòu)，掌握靜態(tài)搜索表的順序搜索和折半搜索算法及其性能分析方法。掌握二叉搜索樹(shù)的表示、搜索、插入、刪除算法及其性能分析方法，掌握AVL樹(shù)的構(gòu)造、插入、刪除時(shí)的調(diào)整方法及其性能分析，重點(diǎn)是AVL樹(shù)的定義、平衡化旋轉(zhuǎn)、AVL樹(shù)的插入和刪除、AVL樹(shù)的高度。2、算法設(shè)計(jì)?用有序鏈表表示集合時(shí)的求集合的并、交、差的算法?并查集

4、中的構(gòu)造函數(shù)、求根及合并算法?并查集中根據(jù)樹(shù)的高度和根據(jù)樹(shù)中結(jié)點(diǎn)個(gè)數(shù)進(jìn)行合并的算法?設(shè)置監(jiān)視哨的順序搜索算法和不設(shè)監(jiān)視哨的順序搜索算法?有序順序表的順序搜索算法?有序順序表的折半搜索的遞歸算法和非遞歸算法?二叉搜索樹(shù)的搜索、插入和刪除算法?計(jì)算AVL樹(shù)中指定結(jié)點(diǎn)高度的遞歸算法及利用此算法計(jì)算結(jié)點(diǎn)平衡因子的算法二、二、難點(diǎn)和重點(diǎn)點(diǎn)和重點(diǎn)1、集合的概念：集合的基本運(yùn)算、集合的存儲(chǔ)表示?用位數(shù)組表示集合時(shí)集合基本運(yùn)算的實(shí)現(xiàn)?用有序鏈表表示集合

5、時(shí)集合基本運(yùn)算的實(shí)現(xiàn)2、并查集：并查集定義、并查集的三種基本運(yùn)算的實(shí)現(xiàn)3、基本搜索方法?對(duì)一般表的順序搜索算法(包括有監(jiān)視哨和沒(méi)有監(jiān)視哨)?對(duì)有序順序表的順序搜索算法，包括遞歸和非遞歸算法?用判定樹(shù)(即擴(kuò)充二叉搜索樹(shù))描述有序順序表的順序搜索，以及平均搜索長(zhǎng)度(成功與不成功)的計(jì)算。138ostreamreturnoutvoidtraverse(ostream輸出集合名及花括號(hào)elseif(s.Elemtype()==1)集合原子元素o

6、uts.GetData()輸出原子元素的值if(s.GetNext()!=NULL)out‘’else子集合traverse(s.GetSubSet())輸出子集合if(s.GetNext()!=NULL)out‘’traverse(s.GetNext())向同一集合下一元素搜索elseout‘’如果集合中包含有子集合，各個(gè)子集合之間沒(méi)有重復(fù)的元素，采用廣義表結(jié)構(gòu)比較合適。也可以使用并查集結(jié)構(gòu)。73當(dāng)全集合可以映射成1到N之間的整數(shù)時(shí)，

7、可以用位數(shù)組來(lái)表示它的任一子集合。當(dāng)全集合是下列集合時(shí)，應(yīng)當(dāng)建立什么樣的映射？用映射對(duì)照表表示。(1)整數(shù)01…99(2)從n到m的所有整數(shù)，n?m(3)整數(shù)nn2n4…n2k(4)字母‘a(chǎn)’‘b’‘c’…‘z’(5)兩個(gè)字母組成的字符串其中，每個(gè)字母取自‘a(chǎn)’‘b’‘c’…‘z’。【解答】(1)i→i的映射關(guān)系，i=012…99(2)i→ni的映射關(guān)系，i=nn1n2…m012mnnn1n2…m(3)i→(in)2的映射關(guān)系，i=nn