西安交通大學(xué)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料-wenkub.com
2025-04-14 12:21 本頁面
【正文】 第八章 查找v 了解順序查找、二分查找以及索引查找等查找方法的原理，并熟悉應(yīng)用各方法的先決條件，查找的結(jié)束條件，適宜的存儲結(jié)構(gòu)以及表示各種查找方法性能的時間復(fù)雜度指標(biāo)v 了解散列存儲和散列函數(shù)的概念以及如何借助于散列存儲結(jié)構(gòu)來實現(xiàn)散列查找v 熟悉常用的幾種散列函數(shù)構(gòu)成法v 熟悉幾種解決散列存儲地址沖突的幾種方法，以及各方法的優(yōu)點與不足v 熟悉散列存儲的各項性能指標(biāo)（時間復(fù)雜度和平均查找長度），并能結(jié)合具體的數(shù)據(jù)序列和沖突解決方法來計算相關(guān)性能指標(biāo)。v 對于每個頂點vi的鄰接表，需要設(shè)置一個表頭指針，若圖G中有n個頂點，則就有n個表頭指針。 vi鄰接表中的每個結(jié)點用來存儲以該頂點為端點或起點的一條邊的信息，因而被稱為邊結(jié)點。v 圖的鄰接矩陣存儲結(jié)構(gòu)用于表示稠密圖能夠充分利用存儲空間，但若用于表示稀疏圖，則將使鄰接矩陣變?yōu)橄∈杈仃嚕瑥亩斐纱鎯臻g的很大浪費。v 無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣可能是不對稱的。 對于有向圖，vi, vj206。設(shè)G=(V,E)是具有n個頂點的圖，頂點序號依次為0,1,2,…,n1，則G的鄰接矩陣是具有如下定義的n階方陣。這樣圖的二元組定義可敘述為： 圖由頂點集(vertex set)和邊集(edge set)所組成。(3) 樹的帶權(quán)路徑長度 樹的帶權(quán)路徑長度定義為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，通常記為： WPL= 其中n表示葉子結(jié)點的數(shù)目，wi和li分別表示葉子結(jié)點ki的權(quán)值和樹根結(jié)點到ki之間的路徑長度。因樹中每個結(jié)點只有一個雙親結(jié)點，所以它也是這兩個結(jié)點之間的惟一路徑。v 若一棵完全二叉樹是堆，則該樹中以每個結(jié)點為根的子樹也都是一個堆。二叉搜索樹查找的遞歸算法的空間復(fù)雜度平均情況為O(log2n)，最差情況為O(n)，非遞歸算法的空間復(fù)雜度為O(1)。v 由二叉搜索樹的定義可知，在一棵非空的二叉搜索樹中，其結(jié)點的關(guān)鍵字是按照左子樹、根和右子樹有序的，所以對它進(jìn)行中序遍歷得到的結(jié)點序列必然是一個有序序列。 ③ 訪問根結(jié)點；（4）按層遍歷二叉樹：① 訪問根結(jié)點；②遍歷左子樹根結(jié)點；③遍歷右子樹根結(jié)點。這種存儲結(jié)構(gòu)既便于查找孩子結(jié)點，也便于查找雙親結(jié)點，當(dāng)然也帶來存儲空間的相應(yīng)增加。理想平衡二叉樹：在一棵二叉樹中，若除最后一層外，其余層都是滿的，而最后一層上的結(jié)點可以任意分布，則稱此樹為理想平衡二叉樹,簡稱理想平衡樹或理想二叉樹。+1熟悉滿二叉樹、完全二叉樹以及平衡二叉樹等幾種特殊的二叉樹的性質(zhì)、特點，并能根據(jù)這些性質(zhì)進(jìn)行相關(guān)的推理和計算滿二叉樹:叉樹每層的結(jié)點數(shù)達(dá)到最大值。 證明：設(shè)所求完全二叉樹的深度為h，由完全二叉樹的定義可知，它的前h1層都是滿的，最后一層可以滿，也可以不滿，由此得到的如下不等式 2h11n≤2h1 ． 可變換為： 2h1n+1≤2h 取對數(shù)后得： h1log2(n+1)≤h 即： log2(n+1)≤hlog2(n+1)+1 因h只能取整數(shù)，所以： h= 233?；?35。,也就是說，當(dāng)i為偶數(shù)時，其雙親結(jié)點的編號為i/2，它是雙親結(jié)點的左孩子，當(dāng)i為奇數(shù)時，其雙親結(jié)點的編號為(i1)/2，它是雙親結(jié)點的右孩子。 (2) 若n為奇數(shù)，則樹中每個分支結(jié)點都既有左孩子，又有右孩子；若n為偶數(shù)，則編號最大的分支結(jié)點（編號為n/2）只有左孩子，沒有右孩子，其余分支結(jié)點左、右孩子都有。即2i≤n，則編號為i的結(jié)點為分支結(jié)點，否則為葉子結(jié)點。v 二叉樹的遞歸定義為：二叉樹或者是一棵空樹，或者是一棵由一個根結(jié)點和兩棵互不相交的分別稱做根的左子樹和右子樹所組成的非空樹，左子樹和右子樹又同樣都是一棵二叉樹。x 249。logk( n(k1)+1)249。v 性質(zhì)4：具有n個結(jié)點的k叉樹的最小深度為： 233。 假設(shè)第i1層(i1)命題成立，該層上有ki2 個結(jié)點。熟悉樹的性質(zhì)，并能根據(jù)這些性質(zhì)進(jìn)行相關(guān)推理和計算v 性質(zhì)1: 樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加1。有序樹：結(jié)點的子樹從左到右有序安排。v 雙親結(jié)點(parent)：一個結(jié)點是它的那些子樹的根的雙親結(jié)點。v 樹的度：一棵樹上所有結(jié)點的度的最大值就是這棵樹的度。向隊列中插入新元素稱為進(jìn)隊或入隊，新元素進(jìn)隊后就成為新的隊尾元素；從隊列中刪除元素稱為離隊或出隊，元素離隊后，其后繼元素就成為隊首元素。但在動態(tài)鏈表中進(jìn)行插入和刪除結(jié)點時，不需要移動結(jié)點，只需要修改指針。若線性表的操作主要是查找和讀取時，采用順序存儲結(jié)構(gòu)為宜；若線性表的操作主要是插入和刪除時，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)為宜。除了線性表第一個數(shù)據(jù)元素作為該鏈表的頭結(jié)點外，在某些線性鏈表存儲結(jié)構(gòu)中，還可在單鏈表第一個結(jié)點之前附加一個同結(jié)構(gòu)結(jié)點，稱為附加頭結(jié)點。循環(huán)鏈表和單鏈表的差別僅在于鏈表中最后一個結(jié)點的指針域不為“NULL”，而是指向頭一個結(jié)點，成為一個由鏈指針鏈結(jié)的環(huán)。v 插入、刪除運算靈活方便，不需移動結(jié)點，只要改變結(jié)點中指針域的值即可了解單鏈表、雙向鏈表和循環(huán)鏈表的結(jié)構(gòu)和特點通過每個結(jié)點的指針域?qū)個結(jié)點按其邏輯順序鏈接在一起的結(jié)點序列我們就稱為鏈表。熟悉順序線性表的插入、刪除和查找的算法思想和程序了解線性表鏈接存儲的結(jié)構(gòu)和特點v 假設(shè)數(shù)據(jù)結(jié)構(gòu)中的每一個數(shù)據(jù)結(jié)點對應(yīng)于一個存
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1