西安交通大學(xué)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料(文件)
【正文】 i的元素存儲頂點vi的信息。v vi鄰接表中的結(jié)點數(shù)，對于無向圖來說，等于vi的邊數(shù)，或鄰接點數(shù)或度數(shù)；對于有向圖來說，等于vi的出邊數(shù)、或出邊鄰接點數(shù)或出度數(shù)。為了便于隨機訪問任一頂點的鄰接表，需要把這n個表頭指針用一個向量(即一維數(shù)組)存儲起來，其中第i個分量存儲vi鄰接表的表頭指針。第九章 排序v 熟悉直接插入排序的方法以及描述其排序性能的指標(biāo)v 熟悉直接選擇排序、堆排序和交換排序的方法、性質(zhì)以及描述排序性能的指標(biāo)v 熟悉快速排序和歸并排序的方法、性質(zhì)及指標(biāo)v 通過比較各排序方法性能（時間復(fù)雜度和空間復(fù)雜度等）熟悉如何選擇合適的排序方法。圖的邊集數(shù)組的定義v 能根據(jù)鄰接矩陣或鄰接表或邊集數(shù)組來得到圖的結(jié)構(gòu)v 熟悉圖的深度和廣度優(yōu)先遍歷的方法，并能根據(jù)相應(yīng)遍歷方法對給定的圖寫出其遍歷序列v 了解圖的生成樹和最小生成樹的定義和性質(zhì)v 熟悉普里姆算法和克魯斯卡爾算法，并能寫出根據(jù)給定的圖用這兩種算法之一來構(gòu)成最小生成樹的過程。在這三個域中，鄰接點域和鏈域是必不可少的，權(quán)域可根據(jù)情況取舍，若表示的是無權(quán)圖，則可省去此域。v 為頂點vi建立的鄰接關(guān)系的單鏈表稱作vi鄰接表。v 圖的鄰接矩陣的存儲需要占用n n個整數(shù)存儲位置，所以其空間復(fù)雜度為O(n2)。若其值大于1則為該通路的權(quán)值。E(G)； A[i,j]= 237。 了解圖的鄰接矩陣、鄰接表、逆鄰接表和十字鄰接表的定義及性質(zhì)鄰接矩陣(adjacency matrix)是表示圖形中頂點之間相鄰關(guān)系的矩陣。 能根據(jù)給定的權(quán)值集合和結(jié)點集合構(gòu)成具有n個結(jié)點的哈夫曼樹(1) 根據(jù)與n個權(quán)值{w1,w2,…,wn}對應(yīng)的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) 重復(fù)(2)和(3)步，直到F中只含有一棵樹為止，此樹便是哈夫曼樹第七章 圖了解圖的定義以及基本性質(zhì)v 圖中的每個頂點，都允許有任意個前驅(qū)和后繼，即對每個頂點的前驅(qū)和后繼個數(shù)均不加以限制v 對于一個圖G，若E是有序?qū)Φ募?，則每個有序?qū)?yīng)圖形中的一條有向邊，若E是無序?qū)Φ募?，則每個無序?qū)?yīng)圖形中的一條無向邊，所以可把E看做為邊的集合。結(jié)點的帶權(quán)路徑長度規(guī)定為從樹根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點上權(quán)的乘積。也就是說，在二叉樹中，一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑。 大根堆的定義與上述類似，只要把小于等于改為大于等于就得到了。 由此可知，在二叉搜索樹上查找比在集合或線性表上進行順序查找的時間復(fù)雜度O(n)要小得多，這正是構(gòu)造二叉搜索樹的優(yōu)勢所在。 在一個二叉搜索樹中，當(dāng)每個結(jié)點的元素類型為簡單類型時，則結(jié)點的關(guān)鍵字就為該結(jié)點的值；當(dāng)結(jié)點的元素類型為記錄類型時，則結(jié)點的關(guān)鍵字為該結(jié)點的某一個域的值。 （遍歷的過程與先根級的遞歸遍歷類似） ② 訪問根結(jié)點； ③ 中序遍歷右子樹 （遍歷過程與先根級的遞歸遍歷相同）(3) 后序遍歷：若二叉樹為空，則空操作；否則 ① 后序遍歷左子樹； ② 后序遍歷右子樹。其結(jié)點結(jié)構(gòu)為：Leftdataright其中data表示值域，用于存儲對應(yīng)的數(shù)據(jù)元素，left和right分別表示左指針域和右指針域，用以分別存儲左孩子和右孩子結(jié)點的存貯位置（即指針）v 鏈接存儲的另一種方法是：在上面的結(jié)點結(jié)構(gòu)中再增加一個parent指針域，用來指向其雙親結(jié)點。 特點: v 除最后一層，第 i層有2i1個結(jié)點； v 葉子只可能出現(xiàn)在最后兩層；v 結(jié)點右子樹深度為i時，左子樹深度為i或i+1。log2n 此性質(zhì)可以從樹的相應(yīng)性質(zhì)中直接導(dǎo)出，也可以進行如下證明。log2(n+1)249。n/2表示對x進行向下取整。n/2性質(zhì)3：若二叉樹的葉子結(jié)點數(shù)為n0，度為2的結(jié)點有n2個,則有：n0=n2+1證明: (1)它是一種樹結(jié)構(gòu),在計算機領(lǐng)域有著廣泛地應(yīng)用。注： 233。 證明：設(shè)k叉樹的最小深度為h，則： 前h1層滿的 k叉樹結(jié)點數(shù) n≤ h層都滿的k叉樹結(jié)點數(shù)，因此有： 上式可變換為： kh1 n (k1)+1 ≤ kh 以k為底取對數(shù)可得： h1 logk( n(k1)+1) ≤h 即： logk( n(k1)+1) ≤h logk( n(k1)+1)+1因k只能為整數(shù)，所以： h=233。 證明：利用性質(zhì) 2來證明，k 叉樹的最大結(jié)點數(shù)為每一層最大結(jié)點數(shù)之和，則有： 當(dāng)一棵k叉樹上的結(jié)點數(shù)等于 時，則稱該樹為滿k叉樹。 用數(shù)學(xué)歸納法證明： 對于 i=1, ki1 =k0 =1 命題成立。 無序樹：結(jié)點的子樹順序任意。v 子孫結(jié)點：每個結(jié)點的所有子樹中的結(jié)點被稱為該結(jié)點的子孫結(jié)點v 祖先結(jié)點：從整個（子）樹的根結(jié)點到達該結(jié)點的路徑上經(jīng)過的所有分支結(jié)點v 結(jié)點層次：從根結(jié)點開始，根結(jié)點為第1層，根結(jié)點的孩子為第2層，依此類推 1 A ………..第1層 2 B 3 C 4 D …. 第2層 5 E 6 F G 7 …
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1