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