【正文】 1 3 4 5 6 2 3 3 0 2 0 5 6 2 3 1 4 Union(2, 0) 63 void UFSets :: WeightedUnion (int Root1, int Root2) { //按 Union的加權(quán)規(guī)則改進的算法 int temp = parent[Root1] + parent[Root2]。 //Root2中結(jié)點數(shù)多 parent[Root2] = temp。 //Root1中結(jié)點數(shù)多 parent[Root1] = temp。 64 ? 按樹高度合并 ? 高度高的樹的根結(jié)點作根 1 1 1 1 1 0 1 2 3 4 1 1 0 3 2 5 6 3 2 2 2 3 3 2 0 1 3 4 5 6 2 3 3 0 2 0 5 6 2 3 1 4 Union(2, 0) 65 Union操作的折疊規(guī)則 ? 為進一步改進樹的性能 ， 可以使用如下折疊規(guī)則來 “ 壓縮路徑 ” 。 0 0 6 7 8 6 7 8 1 9 1 9 3 5 3 5 從 i = 5 壓縮路徑 0 0 0 0 0 0 0 0 7 7 7 9 9 9 8 8 66 int UFSets::CollapsingFind (int i) { //使用折疊規(guī)則的搜索算法 for (int j = i。 j = parent[j])。 parent[i] = j。 } return j。 ? 文件（ File） ? 表格（ Table） ? 在討論字典抽象數(shù)據(jù)類型時，把字典定義為名字 屬性 對的集合。 68 ? 例如，在圖書館檢索目錄中，名字是書名，屬性是索書號及作者等信息；在計算機活動文件表中，名字是文件名，屬性是文件地址、大小等信息。 69 字典的抽象數(shù)據(jù)類型 const int DefaultSize = 26。 //構(gòu)造函數(shù) bool Member (Name name)。 //在字典中搜索關(guān)鍵碼與 name匹配的表項 70 void Insert (Name name, Attribute attr)。 否則插入 name, Attr到字典中 void Remove (Name name)。 ? 用文件記錄（ record）或表格的表項（ entry）來表示單個元素時，用： （關(guān)鍵碼 key，記錄或表項位置指針 adr） ? 構(gòu)成搜索某一指定記錄或表項的索引項。為了適應(yīng)這種描述方式，可以定義有序順序表和有序鏈表。因此，在一個有序鏈表中尋找一個指定元素時，一般不用搜索整個鏈表。 template class E, class K class SortedList : public SeqList { public: int Search (K k1) const。 e1)。 e1)。 有序順序表的類定義 73 基于有序順序表的順序搜索算法 template class E, class K int SortedListE, K::Search (K k1) const { //順序搜索關(guān)鍵碼為 x的數(shù)據(jù)對象 for (int i = 1。 i++) if (data[i1] == k1) return i。 return 0。 ? 算法中的 “ ==”和 “ ”都是重載函數(shù)，在定義E時定義它們的實現(xiàn)。 ? 設(shè)搜索第 i 個元素的概率為 pi, 搜索到第 i 個元素所需比較次數(shù)為 ci, 則搜索成功的平均搜索長度 : ???????niiniiis u c c pcpAS L11) 1 ( .75 ? 在順序搜索情形，搜索第 i (1≤i≤n) 個元素需要比較 i 次，假定按等概率搜索各元素： ? 這與一般順序表情形相同。 ? 設(shè)一個有 n 個表項的表，查找失敗的位置有n+1個，可以用判定樹加以描述。 2121)(1111??????? ????nnnnincpAS Lniiniis u c c76 ? 例如，有序順序表 (10, 20, 30, 40, 50, 60)的順序搜索的分析（使用判定樹） 10 50 60 = = = = = = 20 30 40 2726161 61???? ??is u c c iAS L727671 61????????????iu n s u c ciA S L77 ? 判定樹是一種擴充二叉樹。 ? 假定表中所有失敗位置的搜索概率相同，則搜索不成功的平均搜索長度： ? 時間代價為 O(n)。 ?????? ??? ??niu n s u c c ninAS L11178 基于有序順序表的折半搜索 ? 設(shè) n 個元素存放在一個有序順序表中 。 ? 如果搜索區(qū)間已縮小到一個對象 ， 仍未找到想要搜索的對象 ， 則搜索失敗 。 //元素序號從 1開始 if (low = high) { mid = (low + high) / 2。 else if (data[mid1] k1) mid = BinarySearch (k1, low, mid 1)。 }。 //元素序號從 1開始 while (low = high) { mid = (low + high) / 2。 //右縮搜索區(qū)間 else if (data[mid1] k1) high = mid1。 //搜索成功 } return 0。搜索不成功時檢測指針停留在某個外結(jié)點（失敗結(jié)點）上。 2h = n+1, h = log2(n+1) ? 第 1層結(jié)點有 1個 , 搜索第 1層結(jié)點要比較 1次 。 …, 第 i (1≤ i≤ h) 層結(jié)點有 2i1 個 , 搜索第 i 層結(jié)點要比較 i 次， … 。 ChainNodeE, K *link。 //構(gòu)造函數(shù) ChainNode (Eamp。 }。 assert (first != NULL)。 ～ SortedChain ()。 //搜索 void Insert (const K k1, Eamp。 //插入 bool Remove (const K k1, Eamp。 //刪除 89 ChainNodeE, K *Begin () { return firstlink。 else return NULL。 //鏈表的頭指針 }。 while (p != NULL amp。 pdata k1) p = plink。amp。 //重載：元素判等于 else return NULL。 91 template class E, class K void SortedChainE, K:: Insert (const K k1, Eamp。 while (p != NULL amp。 pdata = k1) //重載：元素判小于等于 { pre = p。 } //尋找插入位置 if (p != NULL amp。 pdata == k1) pdata = e1。 if (newNode == NULL) { 92 cerr “存儲分配失敗 ！” endl。 } newNodelink = p。 } }。 e1) { ChainNodeE, K *p = firstlink, *pre = first； while (p != NULL amp。 pdata k1) 93 { pre = p。 } //尋找刪除位置 if (p != NULL amp。 pdata == k1) { //重載：元素關(guān)鍵碼判等于 prelink = plink。 delete p。 } else return false。 94 鏈表中的操作符重載 class person { friend void main (void)。 //關(guān)鍵碼 other。 } //提取元素關(guān)鍵碼 personamp。 return *this。 } //元素與關(guān)鍵碼判小于 bool operator == (long k1) { return key == k1。 } //元素與關(guān)鍵碼判不等 bool operator (personamp。 } //元素之間判小于 96 bool operator == (personamp。 } //元素之間判等于 bool operator = (personamp。 } //元素間判小于等于 }。但是在有序鏈表中進行搜索，只能順序搜索，需要執(zhí)行 O(n)次關(guān)鍵碼比較。在搜索時，首先用要搜索元素與中間元素進行比較，如果要搜索元素小于中間元素，則僅需搜索鏈表的前半部分，否則只要在鏈表的后半部分進行比較即可。 1 級鏈 包括 6 三個元素。 ? 為了搜索值為 30 的元素，首先搜索 2 級鏈，與中間元素 40 進行比較，在 2 級鏈中只需比較 1次。由于 30 20，可到 0 級鏈繼續(xù)搜索，與鏈表中元素進行比較。 100 ? 圖 (c)就是跳表，有一組分層的鏈， 0級鏈 是包含所有元素的有序鏈表，有 n個元素。 ? 1 級鏈的第 22, 2?22, 3?22, ?個結(jié)點鏈接起來形成 2級鏈 ，依此類推， 第 i級鏈 所包含的元素是第 i1級鏈 的子集。 ? 若一個元素在 0～ i級鏈上，而不在 i+1級鏈（如果存在）上時，就可稱該元素是 i級鏈元素。 template class E, class K struct SkipNode { //跳表結(jié)點類定義 E data。 //指針數(shù)組域 SkipNode (int size = defaultSize) { //構(gòu)造函數(shù) link = new SkipNodeE, K *[size]。 exit(1)。 } //析構(gòu)函數(shù) }。 //所允許的最大級數(shù) int Levels。 //其中存有一個大值 SkipNodeE, K *head。 //表尾結(jié)點 SkipNodeE, K **last。 103 SkipNodeE, K *SaveSearch (K k1)。 ～ SkipList()。 e1) const。 getData (SkipNodeE, K *current) { if (current != NULL) return amp。 else return NULL。 e1)。 e1)。 104 跳表的構(gòu)造函數(shù)和析構(gòu)函數(shù) template class E, class K SkipListE, K::SkipList (K large, int maxLev) { //構(gòu)造函數(shù)：建立空的多級鏈 maxLevel = maxLev。 //控制掃描的最大關(guān)鍵碼 Levels