西安交通大學數(shù)據(jù)結(jié)構(gòu)復習資料-資料下載頁
2025-04-17 12:21本頁面
【正文】 為從樹根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點上權(quán)的乘積。(3) 樹的帶權(quán)路徑長度 樹的帶權(quán)路徑長度定義為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，通常記為： WPL= 其中n表示葉子結(jié)點的數(shù)目，wi和li分別表示葉子結(jié)點ki的權(quán)值和樹根結(jié)點到ki之間的路徑長度。v 哈夫曼(Huffman)樹又稱作最優(yōu)二叉樹。它是n個帶權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中，帶權(quán)路徑長度WPL最小的二叉樹。 能根據(jù)給定的權(quán)值集合和結(jié)點集合構(gòu)成具有n個結(jié)點的哈夫曼樹(1) 根據(jù)與n個權(quán)值{w1,w2,…,wn}對應的n個結(jié)點構(gòu)成具有n棵二叉樹的森林F={T1,T2,…,Tn}，其中每棵二叉樹Ti(1≤i≤n)都只有一個權(quán)值為wi的根結(jié)點，其左、右子樹均為空； (2) 在森林F中選出兩棵根結(jié)點的權(quán)值最小的樹作為一棵新樹的左、右子樹，且置新樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和； (3) 從F中刪除構(gòu)成新樹的那兩棵樹，同時把新樹加入F中； (4) 重復(2)和(3)步，直到F中只含有一棵樹為止，此樹便是哈夫曼樹第七章 圖了解圖的定義以及基本性質(zhì)v 圖中的每個頂點，都允許有任意個前驅(qū)和后繼，即對每個頂點的前驅(qū)和后繼個數(shù)均不加以限制v 對于一個圖G，若E是有序?qū)Φ募?，則每個有序?qū)獔D形中的一條有向邊，若E是無序?qū)Φ募?，則每個無序?qū)獔D形中的一條無向邊，所以可把E看做為邊的集合。這樣圖的二元組定義可敘述為： 圖由頂點集(vertex set)和邊集(edge set)所組成。針對圖G，頂點集和邊集可分別記為V(G)和E(G)。若頂點集為空，則邊集必然為空，若頂點集非空，則邊集可空可不空，當邊集為空時，圖G中的頂點均為孤立頂點。 了解圖的鄰接矩陣、鄰接表、逆鄰接表和十字鄰接表的定義及性質(zhì)鄰接矩陣(adjacency matrix)是表示圖形中頂點之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是具有n個頂點的圖，頂點序號依次為0,1,2,…,n1，則G的鄰接矩陣是具有如下定義的n階方陣。 236。 1, 對于無向圖，(vi,vj)或(vj, vi)206。E(G)； A[i,j]= 237。 對于有向圖，vi, vj206。E(G) 238。 0, 對應邊不存在于E(G)中v 從鄰接矩陣中可查兩個結(jié)點的之間是否存在通路，若兩個結(jié)點的坐標的交叉其值不為零并不是一個很大的值的話，則有通路，否則沒有通路。若其值大于1則為該通路的權(quán)值。v 無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣可能是不對稱的。v 在有向圖中, 統(tǒng)計第 i 行 中1的個數(shù)可得頂點 i 的出度，統(tǒng)計第 j 列中 1 的個數(shù)可得頂點 j 的入度。v 在無向圖中, 統(tǒng)計第 i 行 (列)中 1 的個數(shù)可得頂點i 的度。v 圖的鄰接矩陣的存儲需要占用n n個整數(shù)存儲位置，所以其空間復雜度為O(n2)。v 圖的鄰接矩陣存儲結(jié)構(gòu)用于表示稠密圖能夠充分利用存儲空間，但若用于表示稀疏圖，則將使鄰接矩陣變?yōu)橄∈杈仃?，從而造成存儲空間的很大浪費。v 圖的鄰接矩陣表示，需要使用一個二維數(shù)組存儲頂點之間相鄰的關(guān)系，為了存儲圖中n個頂點元素的信息，通常還需要使用一個一維數(shù)組，用數(shù)組中下標為i的元素存儲頂點vi的信息。鄰接表(adjacency list)是對圖中的每個頂點建立一個鄰接關(guān)系的單鏈表，并把它們的表頭指針用向量存儲的一種圖的表示方法。v 為頂點vi建立的鄰接關(guān)系的單鏈表稱作vi鄰接表。 vi鄰接表中的每個結(jié)點用來存儲以該頂點為端點或起點的一條邊的信息，因而被稱為邊結(jié)點。v vi鄰接表中的結(jié)點數(shù)，對于無向圖來說，等于vi的邊數(shù)，或鄰接點數(shù)或度數(shù)；對于有向圖來說，等于vi的出邊數(shù)、或出邊鄰接點數(shù)或出度數(shù)。v 邊結(jié)點通常包含三個域：一是鄰接點域(adjvex)，用以存儲頂點vi的一個鄰接頂點vj的序號j；二是權(quán)域(weight)，用以存儲邊(vi, vj)或 vi, vj 上的權(quán)；三是鏈域(next)，用以鏈接vi鄰接表中的下一個邊結(jié)點。在這三個域中，鄰接點域和鏈域是必不可少的，權(quán)域可根據(jù)情況取舍，若表示的是無權(quán)圖，則可省去此域。v 對于每個頂點vi的鄰接表，需要設(shè)置一個表頭指針，若圖G中有n個頂點，則就有n個表頭指針。為了便于隨機訪問任一頂點的鄰接表，需要把這n個表頭指針用一個向量(即一維數(shù)組)存儲起來，其中第i個分量存儲vi鄰接表的表頭指針。這樣，圖G就可以由這個表頭向量來表示和存取。圖的邊集數(shù)組的定義v 能根據(jù)鄰接矩陣或鄰接表或邊集數(shù)組來得到圖的結(jié)構(gòu)v 熟悉圖的深度和廣度優(yōu)先遍歷的方法，并能根據(jù)相應遍歷方法對給定的圖寫出其遍歷序列v 了解圖的生成樹和最小生成樹的定義和性質(zhì)v 熟悉普里姆算法和克魯斯卡爾算法，并能寫出根據(jù)給定的圖用這兩種算法之一來構(gòu)成最小生成樹的過程。第八章 查找v 了解順序查找、二分查找以及索引查找等查找方法的原理，并熟悉應用各方法的先決條件，查找的結(jié)束條件，適宜的存儲結(jié)構(gòu)以及表示各種查找方法性能的時間復雜度指標v 了解散列存儲和散列函數(shù)的概念以及如何借助于散列存儲結(jié)構(gòu)來實現(xiàn)散列查找v 熟悉常用的幾種散列函數(shù)構(gòu)成法v 熟悉幾種解決散列存儲地址沖突的幾種方法，以及各方法的優(yōu)點與不足v 熟悉散列存儲的各項性能指標（時間復雜度和平均查找長度），并能結(jié)合具體的數(shù)據(jù)序列和沖突解決方法來計算相關(guān)性能指標。第九章 排序v 熟悉直接插入排序的方法以及描述其排序性能的指標v 熟悉直接選擇排序、堆排序和交換排序的方法、性質(zhì)以及描述排序性能的指標v 熟悉快速排序和歸并排序的方法、性質(zhì)及指標v 通過比較各排序方法性能（時間復雜度和空間復雜度等）熟悉如何選擇合適的排序方法。
教學教案相關(guān)推薦
鄂ICP備17016276號-1