數(shù)據(jù)結構集合與搜索算法

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

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

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

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

5、時集合基本運算的實現(xiàn)2、并查集：并查集定義、并查集的三種基本運算的實現(xiàn)3、基本搜索方法?對一般表的順序搜索算法(包括有監(jiān)視哨和沒有監(jiān)視哨)?對有序順序表的順序搜索算法，包括遞歸和非遞歸算法?用判定樹(即擴充二叉搜索樹)描述有序順序表的順序搜索，以及平均搜索長度(成功與不成功)的計算。138ostreamreturnoutvoidtraverse(ostream輸出集合名及花括號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‘’如果集合中包含有子集合，各個子集合之間沒有重復的元素，采用廣義表結構比較合適。也可以使用并查集結構。73當全集合可以映射成1到N之間的整數(shù)時，

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