本書討論了各種線性數據結構和非線性數據結構的邏輯特性、存儲表示及其應用, 并詳細論述了查找和排序的多種算法及其綜合比較分析。全書采用C語言作為數據結構和算法的描述語言。
本書為教育部高等學校電子信息類專業教學指導委員會規劃教材，適用于電類非計算機專業，配套教學課件，下載地址為清華大學出版社網站本書頁面。本書特色如下：（1） 系統性：涵蓋了計算機軟件技術基礎課程中的經典內容；全書以數據結構為主體，兼顧介紹了軟件開發中所需要的操作系統、軟件工程和數據庫等方面的知識。（2） 實用性：圍繞軟件開發實踐展開全面論述，解決軟件開發中的普遍技術問題，配備豐富的例題和練習題。（3） 針對性：簡明扼要地論述基本概念，深入淺出地闡明軟件開發涉及的基本技術；本書非常適合于電類非計算機專業的授課需求。
前言
隨著計算機應用領域的擴大和深入，非計算機專業的工程技術人員掌握必要的計算機軟件技術基礎知識是提高計算機應用水平、利用計算機技術解決本專業工作中的具體問題的重要途徑。非計算機類專業本科生既熟悉自己所從事的專業，又掌握計算機的應用知識是一個優勢。事實上，許多應用軟件都是由非計算機專業出身的計算機應用人員研發的。計算機軟件基礎是高等學校電子信息類專業的一門學科基礎必修課，被一些高校列為電子類各專業的重點課程或核心課程。通過多年來對本課程的教學研究和教學改革，我們在教學內容、教學方法和考核方式上已基本形成一套比較完整的體系，以切實提高學生的程序設計能力。好的教材源于教學改革和教學實踐，能體現出良好的成果。在多年教學經驗的基礎上，通過對已有教材的分析研究，結合自己的教研工作，編寫此教材。本教材的特點是強調實用性，以應用為目的，含有豐富的實例； 可讀性強，深入淺出，通俗易懂，力求概念準確，表述清楚，簡明扼要； 所有算法采用C語言描述； 適合非計算機專業的學生閱讀。全書內容以數據結構為主，同時包含操作系統、軟件工程和數據庫三部分內容。教學時可根據具體情況對講授內容進行適當取舍。本書由汪友生編寫線性表、棧和隊列、串和數組、樹等部分； 張新峰編寫緒論、排序和軟件開發等部分； 王眾編寫查找部分； 張小玲編寫資源管理部分； 劉芳編寫數據庫設計部分； 郭民編寫圖部分。全書由汪友生統稿。本書在編寫時，參考了大量的文獻資料，對相關作者表示真誠的感謝！由于編者水平有限，書中難免存在疏漏和不妥之處，懇請各位讀者批評指正。編者2016年6月
第1章緒論
1．1計算機軟件
1．1．1計算機軟件的概念
1．1．2計算機語言
1．1．3計算機軟件的分類
1．1．4計算機軟件的發展
1．2數據結構概述
1．2．1數據基本概念
1．2．2數據結構
1．2．3數據類型
1．3算法及算法分析
1．3．1算法
1．3．2算法的性能分析
1．4小結
1.5習題
第2章線性數據結構
2．1線性表的定義
2．2線性表的順序存儲及其運算
2．2．1順序表
2．2．2順序表的基本運算
2．2．3插入和刪除的時間復雜度
2．2．4線性表順序存儲結構的優缺點
2．3線性表的鏈式存儲及其運算
2．3．1單鏈表
2．3．2單循環鏈表
2．3．3雙向鏈表
2．4線性表的應用
2．4．1有序表
2．4．2多項式的表示與運算
2．5棧
2．5．1棧的基本概念
2．5．2棧的運算
2．5．3棧的應用
2．6隊列
2．6．1隊列的基本概念
2．6．2順序(循環)隊列及其運算
2．6．3鏈式隊列及其運算
2．6．4隊列的應用
2．7串
2．7．1串的定義
2．7．2串的運算
2.7.3串的存儲方式
2．7．4串的模式匹配
2．8數組
2．8．1數組的定義
2．8．2數組的順序存儲
2．8．3矩陣的壓縮存儲
2．9小結
2.10習題
第3章非線性數據結構
3．1樹的概念
3．2二叉樹
3．2．1二叉樹的定義
3．2．2二叉樹的主要性質
3．2．3二叉樹的存儲結構
3．3二叉樹的遍歷
3．3．1遍歷的概念
3．3．2二叉樹遍歷算法
3．3．3二叉樹遍歷算法的應用
3．4樹和森林
3．4．1樹和森林的存儲結構
3．4．2樹和森林與二叉樹之間的轉換
3．4．3樹和森林的遍歷
3．5二叉樹的應用
3．5．1哈夫曼樹及其應用
3．5．2二叉排序樹
3．6圖
3．6．1圖的基本概念
3.6.2圖的存儲方法
3.6.3圖的遍歷
3.6.4圖的應用
3.7小結
3.8習題
第4章排序和查找
4.1排序的基本概念
4.2插入排序
4.2.1直接插入排序
4.2.2折半插入排序
4.2.3希爾排序
4.3交換排序
4.3.1冒泡排序
4.3.2快速排序
4.4選擇排序
4.4.1簡單選擇排序
4.4.2堆排序
4.5其他排序
4.5.1歸并排序
4.5.2基數排序
4.6各種排序方法的比較和選擇
4.7查找的基本概念
4.8靜態查找表與算法
4.8.1順序查找
4.8.2折半查找
4.8.3分塊查找
4.9動態查找表
4.9.1二叉搜索樹
4.9.2平衡二叉樹
4.10哈希表及其查找
4.10.1哈希表的概念
4.10.2幾種哈希函數
4.10.3處理沖突的方法
4.10.4哈希表的算法
4.10.5哈希表的應用
4.11小結
4.12習題
第5章資源管理
5.1操作系統的概念
5.1.1操作系統的定義
5.1.2操作系統的分類
5.1.3操作系統的特征
5.1.4操作系統的功能
5.2多道程序設計
5.2.1并發程序設計
5.2.2進程
5.2.3進程之間的通信
5.2.4多道程序的組織
5.3存儲空間的管理
5.3.1內存儲器的管理
5.3.2外存儲器中文件的組織結構
5.4小結
5.5習題
第6章軟件開發
6.1軟件工程概述
6.1.1軟件工程的概念
6.1.2軟件生命周期
6.2軟件的需求分析
6.2.1需求分析概述
6.2.2結構化分析方法
6.2.3數據流圖
6.2.4數據字典
6.3軟件的設計
6.3.1軟件設計概述
6.3.2結構化設計方法
6.3.3詳細設計方法
6.3.4面向對象的程序設計方法
6.4軟件的編程
6.5軟件的測試
6.5.1軟件測試概述
6.5.2軟件測試的過程
6.5.3測試用例的設計
6.6軟件的調試
6.6.1軟件調試的方法
6.6.2常用的調試策略
6.7軟件維護
6.8小結
6.9習題
第7章數據庫設計
7.1數據庫基本概念
7.1.1數據庫技術與數據庫系統
7.1.2數據模型
7.1.3數據庫系統的結構
7.2關系數據庫語言SQL
7.2.1SQL語言概述
7.2.2數據定義功能
7.2.3數據查詢功能
7.2.4數據更新功能
7.3數據庫設計
7.3.1數據庫設計概述
7.3.2需求分析
7.3.3概念設計
7.3.4邏輯設計
7.3.5物理設計
7.3.6數據庫的實施
7.3.7數據庫的運行和維護
7.4小結
7.5習題
附錄部分習題參考答案
參考文獻
第3章非線性數據結構第2章介紹的是線性數據結構，線性數據結構中的每個元素有唯一的前驅元素和唯一的后繼元素，即前驅元素和后繼元素是一對一的關系。本章將介紹非線性數據結構，包括樹和圖，樹的元素有唯一的前驅元素和多個后繼元素，即前驅元素和后繼元素是一對多的關系。樹形結構是非常重要的一種數據結構，在實際應用中也非常廣泛，它主要應用在文件系統、目錄組織等大量的數據處理中。圖是另一種非線性數據結構，是一種更為復雜的數據結構。在圖中，數據元素之間是多對多的關系，即一個數據元素對應多個直接前驅元素和多個直接后繼元素。圖的應用領域十分廣泛，例如工程設計、遺傳學、人工智能等。3．1樹的概念樹是由n (n ≥ 0)個結點組成的有限集合。如果n = 0，稱為空樹； 如果n > 0，則有且僅有一個特定的稱之為根(Root)的結點，它只有直接后繼，但沒有直接前驅； 當n > 1，除根以外的其他結點劃分為m (m >0)個互不相交的有限集合T1, T2 ,…, Tm，其中每個集合本身又是一棵樹，并且稱為根的子樹(SubTree)。如圖31所示。
T = { A，B，C，D，E，F，G，H，I，J }，其中A是根，其余結點可以劃分為兩個互不相交的集合，T1= { B，D，G，H，I }，T2 ={ C，E， F，G }，這兩個集合本身又各是一棵樹，它們是A的子樹。對于T2，C是根，其余結點可以劃分為兩個互不相交的集合，T21 ={ E，J }，T22 ={ F }，T21，T22是C的子樹。樹的結構定義是一個遞歸的定義，即在樹的定義中又用到了樹的概念，它道出了樹的固有特性。如圖32中的子樹T1和T2就是根結點A的子樹， D,G,H,I組成的樹又是B結點的子樹，E,J組成的樹是C結點的子樹。
圖31一般的樹
圖32兩棵子樹
對于樹的定義還需要注意兩點。(1) n>0時，根結點是唯一的，不可能存在多個根結點。(2) m>0時，子樹的個數沒有限制，但它們一定是互不相交的。如圖33中的兩個結構就不符合樹的定義。
圖33非樹的表示
樹的邏輯表示方法可以分為4種，分別是樹形表示法、文氏圖表示法、廣義表表示法和凹入表示法。(1) 樹形表示法。圖31就是樹形表示法。樹形表示法是最常見的一種表示方法，它可以直觀、形象地表示出樹的邏輯結構，可以清晰地反映出樹中結點之間的邏輯關系。(2) 文氏圖表示法。文氏圖表示法是利用數學中集合的圖形化表示來描述樹的邏輯關系。圖31的樹，可用文氏圖表示如圖34所示。(3) 廣義表表示法。采用廣義表的形式表示樹的邏輯結構，廣義表的子表表示結點的子樹。圖31的樹，利用廣義表表示為(A(B(D(G,H,I)),C(E(J),F)))。(4) 凹入表示法。凹入表示法類似于書的目錄、章、節、條、款、項逐個凹入。圖31的樹，可用凹入表示法如圖35所示。
圖34樹的文氏圖表示法
圖35樹的凹入表示法
下面列出樹結構中的一些術語。結點： 樹的結點包含一個數據元素及若干指向其子樹的分支。孩子結點： 結點的子樹的根稱為該結點的孩子。如圖31中D是B的孩子。雙親結點： B結點是A結點的孩子，則A結點是B結點的雙親。如圖31中B是D的雙親。兄弟結點： 同一雙親的孩子結點。如圖31中G、H和I互為兄弟。堂兄結點： 其雙親結點互為兄弟的結點。如圖31中D的雙親結點B與E的父結點C互為兄弟，則稱D與E互為堂兄。祖先結點： 結點的祖先是從根到該結點所經分支上的所有結點。如圖31中F的祖先為A、C。子孫結點： 以某結點為根的子樹中的任一結點稱為該結點的子孫。如圖31中A的子孫為B、C、D、E、F等。結點的度： 結點擁有的子樹的個數為結點的度。如圖31中A結點的度為2。葉子： 度為0的結點為葉子或者終端結點。如圖31的G,H,I,J。樹的度： 樹內各結點的度的最大值。如圖31樹的度為3。層次： 結點的層次(Level)從根開始定義起，根為第一層，根的孩子為第二層，以此類推。樹中結點的最大層次為樹的深度或高度，如圖31所示的樹的深度為4。若將樹中每個結點的各子樹看成是從左到右有次序的(即不能互換)，則稱該樹為有序樹(OrderedTree)； 否則稱為無序樹(UnorderedTree)。若不特別指明，一般討論的樹都是有序樹。森林(Forest)是m(m≥0)棵互不相交的樹的集合。對樹中每個結點，其子樹的集合即為森林。樹和森林的概念相近。刪去一棵樹的根，就得到一個森林； 反之，加上一個結點作樹根，森林就變為一棵樹。樹的基本操作主要有(1) 初始化操作Initate(T)： 創建一棵空樹T。(2) 銷毀樹操作Destory(T):銷毀樹T。(3) 構造樹操作Creat(T,definition):按definition構造樹T，definition給出樹的定義。(4) 清空樹操作Clear(T):將樹T清為空樹。(5) 求根函數Root(T):求樹T的根。(6) 插入操作Insert(T,x,i,y)： 將以y為根的子樹插入到樹T中作為結點x的第i棵子樹。(7) 刪除操作Delete(T,x,i):將樹T中結點x的第i棵子樹刪除。(8) 遍歷樹操作Traverse(T)： 按某種次序對樹T中的每個結點訪問一次且僅一次。（9） 求雙親操作Parent(T, x)： 若x是T的非根結點，則返回它的雙親，否則函數值返回“空”。（10） 求右兄弟操作RightSibling(T, X)： 若x有右兄弟結點，則返回它的右兄弟，否則返回“空”。（11） 求孩子操作Child(T, x, i)： 若x是T的非葉子結點，則返回它的第i個孩子，否則返回“空”。3．2二叉樹樹結構中有一種應用較為廣泛的樹——二叉樹（Binary Tree）。二叉樹的度為2，而且是一棵有序樹，即樹中結點的子樹從左到右有次序。3．2．1二叉樹的定義二叉樹是一個有限元素的集合，該集合或者為空、或者由一個稱為根(root)的元素及兩個不相交的、分別稱為左子樹和右子樹的二叉樹組成。值得注意的是，度為2的有序樹與二叉樹是不同的。假設要在有兩個孩子的結點中刪除第一個孩子。在度為2的有序樹中，刪除了第一個孩子，原來第2個孩子改稱為第1個孩子； 二叉樹中，如果刪除了左孩子，右孩子依然是右孩子。二叉樹是另外一種樹形結構，即不存在度大于2的結點，每個結點至多只有兩棵子樹，二叉樹的子樹有左右之分，左、右子樹不能顛倒，即使只有一棵子樹也要進行區分，說明它是左子樹，還是右子樹。另外，二叉樹是遞歸結構，二叉樹的定義中又用到了二叉樹的概念。圖36列出了二叉樹的5種基本形態。
圖36二叉樹的5種基本狀態
3．2．2二叉樹的主要性質二叉樹具有下列重要性質： （1） 性質1： 二叉樹的第i層上至多有2i-1個結點(i ≥ 1)。［證明用歸納法］證明： 當i=1時，只有根結點，2i-1=20=1。假設對所有j， 1≤j
圖37特殊形態的二叉樹
(4) 性質4： 具有 n 個結點的完全二叉樹的深度為 log2n 1。證明： 設完全二叉樹的深度為 k，則根據性質2和完全二叉樹的定義有2k-1-11，則其雙親是結點i/2。② 如果2i>n，則結點i為葉子結點，無左孩子； 否則，其左孩子是結點2i。③ 如果2i＋1>n，則結點i無右孩子； 否則，其右孩子是結點2i＋1。證明： 此性質可采用數學歸納法證明。因為1與2、3是相對應的，所以只需證明2和3。當 i=1時，根據結點編號方法可知，根的左、右孩子編號分別是2和3，結論成立。假定i-1時結論成立，即結點i-1的左右孩子編號滿足 lchild(i-1)=2(i-1)； rchild(i-1)=2(i-1) 1。通過完全二叉樹可知，結點 i 或者與結點i-1同層且緊靠其右，或者結點i-1在某層最右端，而結點i在其下一層最左端。但是，無論如何，結點i的左孩子的編號都是緊接著結點i-1的右孩子的編號，故lchild(i)=rchild(i-1) 1=2i； rchild(i)=lchild(i) 1=2i 1命題成立。3．2．3二叉樹的存儲結構二叉樹的存儲結構有兩種，分別是順序存儲表示和鏈式存儲表示。1． 順序存儲結構所謂順序存儲結構，就是用一組連續的存儲單元存儲二叉樹的數據元素，結點在這個序列中的相互位置能反映出結點之間的邏輯關系。二叉樹中結點之間的關系就是雙親結點與左右孩子結點間的關系。因此，必須把二叉樹的所有結點安排成為一個恰當的序列。C語言中，這種存儲形式的類型定義如下所示。
#define MaxTreeNodeNum 100 /*二叉樹的最大結點數*/
typedef struct {
DataType data［MaxTreeNodeNum］; /*0號結點存放根結點*/
int n;
} QBiTree;
通常，按照二叉樹結點從上至下、從左到右的順序存儲，但這樣結點在存儲位置上的前驅后繼關系并不一定就是它們在邏輯上的鄰接關系。依據二叉樹的性質，完全二叉樹和滿二叉樹采用順序存儲比較合適，樹中結點的序號可以唯一地反映出結點之間的邏輯關系，既能夠最大可能地節省存儲空間，又可以利用數組元素的下標值確定結點在二叉樹中的位置，以及結點之間的關系。圖38(a)為圖37(b)所示的完全二叉樹的順序存儲結構。對于一般的二叉樹，則應將其每個結點與完全二叉樹上的結點相對照，存儲在一維數組的相應分量中，如圖37(c)所示二叉樹的順序存儲結構如圖38(b)所示，圖中以“0”表示不存在的結點。由此可見，這種順序存儲結構僅適用于完全二叉樹。因為，在最壞的情況下，一個深度為k且只有k個結點的單支樹(樹中不存在度為2的結點)卻需要長度為2k-1的一維數組。
圖38二叉樹的順序存儲結構
完全二叉樹的編號特點為除最下面一層外，各層都充滿了結點。每一層的結點個數恰好是上一層結點個數的2倍。從一個結點的編號就可推得其雙親，左、右孩子，兄弟等結點的編號。假設編號為i的結點是Ki(1≤i≤n)，則有（1） 若i>1，則Ki的雙親編號為i/2； 若i=1，則Ki是根結點，無雙親。 （2） 若2i≤n，則Ki的左孩子編號為2i； 否則，Ki無左孩子，即Ki必定是葉子。（3） 若2i 1≤n，則Ki的右孩子編號為2i 1； 否則，Ki無右孩子。（4） 若i為奇數且不為1，則Ki的左兄弟編號為i-1； 否則，Ki無左兄弟。（5） 若i為偶數且小于n，則Ki的右兄弟編號為i 1； 否則，Ki無右兄弟。順序存儲的優缺點是適合于完全二叉樹，既不浪費存儲空間，又能很快確定結點的存放位置，以及結點的雙親和左右孩子的存放位置。但對一般二叉樹，可能造成存儲空間的浪費。2． 鏈式存儲結構所謂鏈式存儲是指用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。通常有下面兩種形式。1) 二叉鏈表存儲鏈表中每個結點由3個域組成，即數據域和兩個指針域。data域存放某結點的數據信息； lchild與rchild分別存放指向左孩子和右孩子的指針。當左孩子或右孩子不存在時，相應指針域值為空(用符號∧或NULL表示)。結點的存儲結構如圖39所示。
圖39二叉鏈表存儲結構
C語言中，這種存儲形式的類型定義如下所示。
typedef char DataType； /*用戶可根據具體應用定義DataType的實際類型*/
typedef struct bnode {
DataType data;
struct bnode *lchild, *rchild; /*左右孩子指針*/
} BiTree;
圖310(b)給出了圖310(a)所示的一棵二叉樹的二叉鏈表存儲結構。鏈頭的指針指向二叉樹的根結點。容易證得，在含有n個結點的二叉鏈表中有n 1個空鏈表域。
圖310鏈表存儲結構
2) 三叉鏈表存儲每個結點由4個域組成，具體結構如圖311所示。
圖311三叉鏈表存儲結構
其中，data、lchild及rchild三個域的意義與二叉鏈表結構相同； parent域為指向該結點雙親結點的指針。這種存儲結構既便于查找孩子結點，又便于查找雙親結點； 但是，相對于二叉鏈表存儲結構，它增加了空間開銷。圖310(c)給出了圖310(a)所示的一棵二叉樹的三叉鏈表存儲結構。盡管，在二叉鏈表中無法由結點直接找到其雙親，但由于二叉鏈表結構靈活，操作方便，對于一般情況的二叉樹，甚至比順序存儲結構還節省空間。例如，深度為4的右單支二叉樹共有4個結點，二叉鏈表的8個指針域3個非空，順序存儲24-1共15個元素空間僅使用了4個。因此，二叉鏈表是最常用的二叉樹存儲方式。本書后面涉及的二叉樹的鏈式存儲結構，如不加特別說明都是指二叉鏈表結構。3． 二叉樹的基本操作采用二叉鏈表存儲結構表示的二叉樹的基本操作實現如下所示。1) 二叉樹的初始化操作二叉樹的初始化需要將指向二叉樹的根結點指針置為空，代碼如下：
void InitBitTree(BiTree *T) /*二叉樹的初始化操作*/
{
T=NULL;
}
2) 二叉樹的銷毀操作如果二叉樹存在，將二叉樹的存儲空間釋放。
void DestoryBitTree(BiTree *T) /*銷毀二叉樹*/
{
if(T) /*如果是非空二叉樹*/
{
if(T-lchild)
DestoryBitTree(T-lchild));
if((T)-rchild)
DestoryBitTree(T-rchild));
free(T);
T=NULL;
}
}
3) 創建二叉樹操作根據二叉樹的遞歸定義，先生成二叉樹的根結點，將元素值賦值給結點的數據域，然后遞歸創建左子樹和右子樹。其中“#”表示空。代碼如下：
void CreateBitTree(BiTree *T) /*遞歸創建二叉樹*/
{
DataType ch;
scanf("%c", &ch);
if(ch==’#’)
T=NULL;
else
{
T=(BiTree *)malloc(sizeof(bnode)); /*生成根結點*/
if(!T)
exit(-1);
T-data=ch;
CreateBitTree(T-lchild)); /*構造左子樹*/
CreateBitTree(T-rchild)); /*構造右子樹*/
}
}
4) 二叉樹的左插入操作指針p指向二叉樹T的某個結點，將子樹c插入到T中，使c成為p指向結點的左子樹，p指向結點的原來左子樹成為c的右子樹。代碼如下：
int InsertLeftChild(BiTree p,BiTree c) /*二叉樹的左插入操作*/
{
if(p) /*如果指針p不空*/
{
c-rchild=p-lchild; /*p的原來的左子樹成為c的右子樹*/
p-lchild=c; /*子樹c作為p的左子樹*/
return 1;
}
return 0;
}
5) 二叉樹的右插入操作指針p指向二叉樹T的某個結點，將子樹c插入到T中，使c成為p指向結點的右子樹，p指向結點的原來左子樹成為c的右子樹。代碼如下：
int InsertReftChild(BiTree p,BiTree c) /*二叉樹的右插入操作*/
{
if(p) /*如果指針p不空*/
{
c-rchild=p-rchild; /* p的原來的右子樹成為c的右子樹*/
p-rchild=c; /*子樹c作為p的右子樹*/
return 1;
}
return 0;
}
6) 二叉樹的左刪除操作二叉樹中，指針p指向二叉樹中的某個結點，將p所指向的結點的左子樹刪除。如果刪除成功，返回1； 否則，返回0。代碼如下：
Int DeleteLeftChild(BiTree p) /*二叉樹的左刪除操作*/
{
if(p)
{
DestoryBiTree(p-lchild); /*刪除p指向結點的左子樹*/
return 1;
}
return 0;
}
7) 二叉樹的右刪除操作二叉樹中，指針p指向二叉樹中的某個結點，將p所指向的結點的右子樹刪除。如果刪除成功，返回1； 否則，返回0。代碼如下：
Int DeleteRightChild(BiTree p) /*二叉樹的右刪除操作*/
{
if(p)
{
DestoryBiTree(&(p-rchild)); /*刪除p指向結點的右子樹*/
return 1;
}
return 0;
}
8) 返回二叉樹的左孩子元素值基本操作如果元素值為e的結點存在，并且該結點的左孩子結點存在，則將該結點的左孩子結點的元素值返回。代碼如下：
DataType LeftChild(BiTree T, DataType e) /*返回二叉樹的左孩子結點元素值操作*/
{
BiTree p; /*如果二叉樹非空*/
if(T)
{
p=Point(T, e); /*p是元素值e的結點的指針*/
if(p&&p-lchild) /*如果p不為空，且p的左孩子結點存在*/
return p-lchild-data; /*返回p的左孩子結點的元素值*/
}
return;
}
9) 返回二叉樹的右孩子元素值基本操作如果元素值為e的結點存在，并且該結點的右孩子結點存在，則將該結點的右孩子結點的元素值返回。代碼如下：
DataType LeftChild(BiTree T, DataType e) /*返回二叉樹的右孩子結點元素值操作*/
{
BiTree p; /*如果二叉樹非空*/
if(T)
{
p=Point(T, e); /*p是元素值e的結點的指針*/
if(p&&p-rchild) /*如果p不為空，且p的右孩子結點存在*/
return p-rchild-data; /*返回p的右孩子結點的元素值*/
}
return;
}
3．3二叉樹的遍歷3．3．1遍歷的概念
二叉樹的遍歷指按照某種順序訪問二叉樹中的每個結點，使每個結點被訪問一次且僅被訪問一次。這里提到的“訪問”含義很廣，可以是查詢、修改、輸出某元素的值，以及對元素做某種運算等，但要求這種訪問不破壞它原來的數據結構。遍歷一個線性結構很簡單，只須從開始結點出發，順序掃描每個結點。但對二叉樹這樣的非線性結構，每個結點可能有兩個后繼結點，因此需要尋找一種規律來系統訪問樹中的各結點。遍歷是二叉樹中經常用到的一種操作。因為在實際應用問題中，常常需要按一定順序對二叉樹中的每個結點逐個進行訪問，查找具有某一特點的結點，然后對這些滿足條件的結點進行處理。通過一次完整的遍歷，可使二叉樹中結點信息由非線性排列變為某種意義上的線性序列。也就是說，遍歷操作可使非線性結構線性化。3．3．2二叉樹遍歷算法1． 二叉樹的遍歷方法及遞歸實現
由于二叉樹的定義是遞歸的，它是由3個基本單元組成，即根結點、左子樹和右子樹。因此，遍歷一棵非空二叉樹的問題可以分解為3個子問題，即訪問根結點、遍歷左子樹、遍歷右子樹，只要依次遍歷這3部分，就可以遍歷整個二叉樹。由于實際問題一般都要求左子樹較右子樹先遍歷，通常習慣先左后右的原則，放棄了先右后左的次序。于是，將根結點放在左、右子樹的前、中、后，得到3種遍歷次序，分別稱為先序遍歷、中序遍歷和后序遍歷。令L，R，T分別代表二叉樹的左子樹、右子樹、根結點，則有TLR、LTR、LRT 3種遍歷規則。1) 先序遍歷二叉樹(TLR)先序遍歷的遞歸過程為： 若二叉樹為空，遍歷結束。否則，（1） 訪問根結點。（2） 先序遍歷根結點的左子樹。（3） 先序遍歷根結點的右子樹。先序遍歷二叉樹的遞歸算法如下：
void PreOrder(BiTree *bt)
{/*先序遍歷二叉樹bt*/
if (bt==NULL) return; /*遞歸調用的結束條件*/
Visit(bt-data); /*訪問結點的數據域*/
PreOrder(bt-lchild); /*先序遞歸遍歷bt 的左子樹*/
PreOrder(bt-rchild); /*先序遞歸遍歷bt 的右子樹*/
}
2) 中序遍歷二叉樹(LTR)中序遍歷的遞歸過程為： 若二叉樹為空，遍歷結束。否則，(1) 中序遍歷根結點的左子樹。(2) 訪問根結點。(3) 中序遍歷根結點的右子樹。中序遍歷二叉樹的遞歸算法如下：
void InOrder(BiTree *bt)
{/*中序遍歷二叉樹bt*/
if (bt==NULL) return; /*遞歸調用的結束條件*/
InOrder(bt-lchild); /*中序遞歸遍歷bt 的左子樹*/
Visit(bt-data); /*訪問結點的數據域*/
InOrder(bt-rchild); /*中序遞歸遍歷bt 的右子樹*/
}
3) 后序遍歷二叉樹(LRT)后序遍歷的遞歸過程為： 若二叉樹為空，遍歷結束。否則，（1） 后序遍歷根結點的左子樹。（2） 后序遍歷根結點的右子樹。（3） 訪問根結點。后序遍歷二叉樹的遞歸算法如下：
void PostOrder(BiTree *bt)
{/*后序遍歷二叉樹bt*/
if (bt==NULL) return; /*遞歸調用的結束條件*/
PostOrder(bt-lchild); /*后序遞歸遍歷bt 的左子樹*/
PostOrder(bt-rchild); /*后序遞歸遍歷bt 的右子樹*/
Visit(bt-data); /*訪問結點的數據域*/
}
圖312二叉樹
如圖312所示的二叉樹，若要先序遍歷此二叉樹，按訪問結點的先后順序將結點排列起來，可以得到該二叉樹的先序序列ABDGCEF。類似地，中序遍歷此二叉樹，可以得到二叉樹的中序序列DGBAECF。后序遍歷此二叉樹，可以得到二叉樹的后序序列GDBEFCA。
2． 二叉樹遍歷的非遞歸實現先序、中序、后序遍歷的非遞歸算法共同之處，即用棧來保存先前走過的路徑，以便在訪問完子樹后,可以利用棧中的信息，回退到當前節點的雙親節點,進行下一步操作。1) 先序遍歷二叉樹算法實現： 從二叉樹根結點開始，沿左子樹一直走到末端(左子樹為空)為止，在走的過程中，訪問所遇結點，并依次把遇到的結點進棧。當左子樹為空時，從棧頂退出某結點，并將指針指向該結點的右子樹。如此重復，直到棧為空或指針為空止。先序遍歷非遞歸算法如下：
void PreOrder (BiTree *t) /*非遞歸先序遍歷二叉樹t，對每個元素調用Visit函數*/
{PSeqStack S;
bnode * p = t;
S=Init_SeqStack ( );
while ( p ||!Empty_SeqStack ( S))
{if ( p) /*二叉樹非空*/
{Visit (p-data) ; /*訪問結點的數據域*/
Push_SeqStack ( S, p);
p = p-lchild; /*遍歷左子樹*/
}
else
{
Pop_SeqStack (S,&p );
p = p-rchild; /*向右跨一步，以便遍歷右子樹*/
}
}
}
2) 中序遍歷二叉樹算法實現： 設根指針為p，可能有以下兩種情況。（1） 若p！=NULL，則p入棧，遍歷其左子樹。（2） 若p==NULL，則返回。此時，① 若棧空，則整個遍歷結束； ② 否則，表明棧頂結點的左子樹已遍歷結束。此時，退棧，訪問p，并遍歷其右子樹。中序遍歷非遞歸算法如下：
void InOrder (BiTree *t ) /*非遞歸中序遍歷二叉樹t，對每個元素調用Visit函數*/
{PSeqStack S;
bnode * p = t;
S=Init_SeqStack ( );
while ( p ||!Empty_SeqStack ( S))
{
if ( p) /*二叉樹非空*/
{
Push_SeqStack ( S, p);
p = p-lchild;
}
else
{
Pop_SeqStack (S,&p );
Visit (p-data) ;
p = p-rchild;
}
}
}
3) 后序遍歷二叉樹算法實現： 利用棧來實現二叉樹的后序遍歷要比先序和中序遍歷復雜得多。后序遍歷中，當搜索指針指向某一個結點時，不能馬上進行訪問，而先要遍歷左子樹，所以此結點應先進棧保存，當遍歷完它的左子樹后，再次回到該結點，還不能訪問它，還需先遍歷其右子樹，所以該結點必須再次進棧，只有等它的右子樹遍歷完后，再次退棧時，才能訪問該結點。為了區分同一結點的兩次進棧，引入一個棧次數的標志，元素第1次進棧標志為0，第2次進標志為1，當退出的元素標志為1時，訪問結點。設根指針為p，可能有以下兩種情況。（1） 若p！=NULL，則p及標志flag(=0)入棧，遍歷其左子樹。（2） 若p==NULL，則返回。此時，① 若棧空，則整個遍歷結束； ② 否則，表明棧頂結點的左子樹或右子樹已遍歷結束。此時，若棧頂結點的flag=0，則修改為1，并遍歷其右子樹； 否則，訪問棧頂結點并退棧，再轉至（1）。后序遍歷非遞歸算法如下：
typedef struct
{
bnode *node;
int flag;
} DataType;
void PostOrder (BiTree* t ) /*非遞歸后序遍歷二叉樹t，對每個元素調用Visit函數*/
{
PSeqStack S;
DataType Sq;
bnode * p = t;
S=Init_SeqStack( );
while ( p ||!Empty_SeqStack (S ))
{
if ( p)
{
Sq.flag=0;
Sq.node=p;
Push_SeqStack (S, Sq);
p = p-lchild; }
else
{
Pop_SeqStack (S,&Sq);
p = Sq.node;
if (Sq.flag==0)
{
Sq.flag=1;
Push_SeqStack (S,Sq);
p= p-rchild; }
else
{
Visit (p-data );
p=NULL; }
}
}
}
3． 二叉樹的層次遍歷所謂二叉樹的層次遍歷，就是指從二叉樹的第1層(根結點)開始，從上到下逐層遍歷，同一層中，則按照從左到右的順序對結點逐個訪問。對于圖312所示的二叉樹，按層次遍歷所得到的結果序列為ABCDEFG。按層次遍歷二叉樹的算法描述： 使用一個隊列結構完成這項操作。所謂記錄訪問結點就是入隊操作； 取出記錄的結點就是出隊操作。(1) 訪問根結點，并將根結點入隊。(2) 當隊列不空時，重復下列操作： ① 從隊列退出一個結點； ② 若其有左孩子，則訪問左孩子，并將其左孩子入隊； ③ 若其有右孩子，則訪問右孩子，并將其右孩子入隊。下面的層次遍歷算法中，二叉樹以二叉鏈表存放，一維數組Queue［MAXNODE］用以實現隊列，變量front和rear分別表示當前隊首元素和隊尾元素在數組中的位置。
void LevelOrder(BiTree *bt)
/*層次遍歷二叉樹bt*/
{
BiTree Queue［MAXNODE］;
int front,rear;
if (bt==NULL) return;
front=-1;
rear=0;
queue［rear］=bt;
while(front!=rear)
{
front ;
Visit(queue［front］-data); /*訪問隊首結點的數據域*/
if (queue［front］-lchild!=NULL) /*將隊首結點的左孩子結點入隊列*/
{
rear ;
queue［rear］=queue［front］-lchild;
}
if (queue［front］-rchild!=NULL) /*將隊首結點的右孩子結點入隊列*/
{
rear ;
queue［rear］=queue［front］-rchild;
}
}
}
二叉樹遍歷算法的時間和空間復雜度分析，由于遍歷二叉樹算法中的基本操作是訪問結點，則不論按哪種次序進行遍歷，對含有n個結點的二叉樹，其時間復雜度均為O(n)。所需輔助空間為遍歷過程中棧的最大容量，即樹的深度，最壞情況下為n，則空間復雜度也為O(n)。3．3．3二叉樹遍歷算法的應用二叉樹的遍歷應用很廣泛，本書主要通過幾個例子來說明二叉樹遍歷的典型應用。1． 編寫求二叉樹結點個數的算法算法1： 在中序(或先序、后序)遍歷算法中對遍歷到的結點進行計數(count應定義成全局變量，初值為0)。
void InOrder ( BiTree *t )/*將二叉樹t中的結點數累加到全局變量count中，count的初值0*/
{
if (t)
{InOrder ( t-lchild );
count=count 1;
InOrder ( t-rchild );
}
}
算法2： 將一棵二叉樹看成由樹根、左子樹和右子樹3個部分組成，所以總的結點數是這3部分結點數之和，樹根的結點數或者是1或者是0(為空時)，而求左右子樹結點數的方法和求整棵二叉樹結點數的方法相同，可用遞歸方法。
int Count ( BiTree *t )
{
int lcount,rcount;
if (t==NULL) return 0;
lcount=Count(t-lchild);
rcount=Count(t-rchild);
return lcount rcount 1; }
2． 設計算法求二叉樹的高度算法1： 使用全局變量。
void High( BiTree *bt )
{/*求二叉樹bt的高度并存儲到全局變量h中，h初值為0*/
int hl;
if(bt==NULL) h=0; /*bt為空時，高度為0*/
else{
High(bt-lchild); /*求左子樹的高度并存儲到全局變量h中*/
hl=h;
High(bt-rchild); /*求右子樹的高度并存儲到全局變量h中*/
h=(hlh? hl:h) 1; /*若二叉樹不空，其高度應是其左右子樹高度的最大值再加1*/
}
}
算法2： 使用帶指針形參。
void High( BiTree *bt, int *h )
{/*求二叉樹bt的高度并存儲到h所指向的內存單元*/
int hl, hr;
if(bt==NULL) *h=0; /*bt為空時，高度為0*/
else{
High(bt-lchild,&hl); /*求左子樹的高度并存儲到局部變量hl中*/
High(bt-rchild,&hr); /*求右子樹的高度并存儲到局部變量hr中*/
*h=(hlhr? hl:hr) 1; /*若二叉樹不空，其高度應是其左右子樹高度的最大值再加1*/
}
}
算法3： 通過函數值返回結點數。
int High( BiTree *bt )
{/*求二叉樹bt的高度并通過函數值返回*/
int hl,hr,h;
if(bt==NULL) h=0; /*bt為空時，高度為0*/
else{
hl=High(bt-lchild); /*求左子樹的高度并暫時存儲到局部變量hl中*/
hr=High(bt-rchild); /*求右子樹的高度并暫時存儲到局部變量hr中*/
h=(hlh? hl:h) 1; /*若二叉樹不空，其高度應是其左右子樹高度的最大值再加1*/
}
return h；
}
3． 創建二叉樹的二叉鏈表存儲結構由二叉樹的先序、中序、后序序列中的任何一個序列是不能唯一確定一棵二叉樹的，原因是不能確定左右子樹的大小或者說不知其子樹結束的位置。針對這種情況，做如下處理。將二叉樹中每個結點的空指針處再引出一個“孩子”結點，其值為特定值，如用0標識其指針為空。例如，要建立如圖312所示的二叉樹，其先序輸入序列應該是ABD0G00CE00F00。根據二叉樹的遞歸定義，先生成二叉樹的根結點，將元素值賦值給結點的數據域，然后遞歸創建左子樹和右子樹。
void CreateBinTree(BiTree *T)
{/*以加入結點的先序序列輸入，構造二叉鏈表*/
char ch;
scanf("＼n%c",&ch);
if (ch=='0') *T=NULL; /*讀入0 時，將相應結點置空*/
else {*T=(BinTNode*)malloc(sizeof(bnode)); /*生成結點空間*/
(*T)-data=ch;
CreateBinTree(&(*T)-lchild); /*構造二叉樹的左子樹*/
CreateBinTree(&(*T)-rchild); /*構造二叉樹的右子樹*/
}
}
void InOrderOut(BiTree *T)
{/*中序遍歷輸出二叉樹T 的結點值*/
if (T)
{InOrderOut(T-lchild); /*中序遍歷二叉樹的左子樹*/
printf("%3c",T-data); /*訪問結點的數據*/
InOrderOut(T-rchild); /*中序遍歷二叉樹的右子樹*/
}
}
main()
{
BiTree bt;
CreateBinTree(&bt);
InOrderOut(bt);
}
4． 查找數據元素下面的算法Search(bt，x)實現在非空二叉樹bt中查找數據元素x。若查找成功，則返回該結點的指針； 若查找失敗，則返回空指針。
BiTree Search(BiTree *bt, int x)
{/*先序查找，在以bt為根的二叉樹中值為x的結點是不是存在*/
BiTree *temp;
if(bt==NULL) return NULL;
if(x==bt-data) return bt;
temp=search(bt-lchild, x); /*在bt-lchild為根的二叉樹中查找數據x*/
if(temp!=NULL) return temp;
else return search(bt-rchild, x); /*在bt-rchild為根的二叉樹中查找數據x*/
}
5． 設計算法求二叉樹每層結點的個數算法思想： 先序或者中序遍歷時，都是從一個結點向它的左孩子或者右孩子移動，如果當前結點位于L層，則它的左孩子或者右孩子肯定是在L 1層。在遍歷算法中給當前訪問到的結點增設一個指示該結點所位于的層次變量L，設二叉樹高度為H,定義一個全局數組num［1…H］,初始值為0，num［i］表示第i層上的結點個數。
void Levcount (BiTree *t, int L)
{if ( t)
{
Visit (t-data); num［L］ ;
Levcount (t-lchild, L 1);
Levcount (t-rchild, L 1);
}
}
}
3．4樹和森林樹、 森林和二叉樹本身都是樹的一種，它們之間都可以相互轉換，本節將討論樹和森林的存儲結構，并建立森林與二叉樹的對應關系。3．4．1樹和森林的存儲結構1. 樹的存儲結構
在大量的應用中，人們曾使用多種形式的存儲結構來表示樹。這里，介紹3種常用的鏈表結構，分別是雙親表示法、孩子表示法和孩子兄弟表示法。1） 雙親表示法由樹的定義可知，樹中根結點無雙親，其他任何一個結點都只有唯一的雙親。根據這一特性，可以以一組連續的空間存儲樹的結點，通過保存每個結點的雙親結點位置，表示樹中結點之間的結構關系，樹的這種存儲方法稱為雙親表示法。雙親表示法的存儲結構定義可以描述為
#define MaxNodeNum 100 /*樹中結點的最大個數*/
typedef struct { /*結點結構*/
DataType data;
int parent;
} Parentlist;
typedef struct { /*樹結構*/
Parentlist elem［MaxNodeNum］;
int r, n; /*雙親結點的位置和結點個數*/
} ParentTree;
圖313所示的是一棵樹及其雙親表示的存儲結構。圖313中用parent域的值為-1表示該結點無雙親結點，即該結點是一個根結點。
圖313樹的雙親表示法
樹的雙親表示法對于實現Parent(T,x)操作和Root(T)操作很方便，但若求某結點的孩子結點，即實現Child(T,x,i)操作時，則需要查詢整個數組。此外，這種存儲方式不能反映各兄弟結點之間的關系，所以實現RightSibling(T,x)操作也比較困難。實際中，如果需要實現這些操作，可在結點結構中增設存放第一個孩子的域和存放右兄弟的域，就能較方便地實現上述操作。2） 孩子表示法由于每個結點可能有多棵子樹，可以考慮使用多重鏈表，即每個結點有多個指針域，其中每個指針指向一棵子樹的根結點，這種方法稱為多重鏈表表示法。不過樹的每個結點的度，也就是它的孩子個數是不同的，所以可以設計兩種方案來解決。方案1： 根據樹的度d為每個結點設置d個指針域，多重鏈表中的結點是同構的。由于樹中很多結點的度小于d，所以鏈表中有很多空鏈域，造成存儲空間浪費。不難推出，在一棵有n個結點，度為d的樹中必有n(d-1) 1個空鏈域。不過，若樹的各結點度相差很小時，就意味著開辟的空間都利用了，這時缺點反而變成了優點。其結構如圖314所示。
圖314方案1結構圖
方案2： 每個結點指針域的個數等于該結點的度，專門取一個位置來存儲結點指針域的個數。在結點中設置degree域，指出結點的度。其結構如圖315所示：
圖315方案2結構圖
這種方法克服了浪費空間的缺點，對空間的利用率很高，但是各個結點的鏈表是不相同的結構，加上要維護結點的度的數值，運算上就會帶來時間的損耗。那么有沒有更好的方法呢？既可以減少空指針的浪費，又能使結點結構相同。那就是用孩子表示法。具體辦法是，把每個結點的孩子排列起來，以單鏈表做存儲結構，則n個結點有n個孩子鏈表，如果是葉子結點則此單鏈表為空。然后n個頭指針又組成一個線性表，采用順序存儲結構，存放進一個一維數組中。針對圖313所示的樹，其孩子表示法如圖316所示。
圖316樹的孩子表示法
樹的孩子表示法使得查找已知結點的孩子結點非常容易。通過查找某結點的鏈表，可以找到該結點的每個孩子。但是查找雙親結點不方便，為此可以將雙親表示法與孩子表示法結合起來使用，圖317就是將兩者結合起來的帶雙親的孩子鏈表。
圖317帶雙親的孩子鏈表
樹的孩子表示法的類型定義如下：
#define MAXNODE 100 /*樹中結點的最大個數*/
struct ChildNode{ /*孩子結點*/
int childcode;
struct ChildNode *nextchild;
}
typedef struct {
elemtype data;
struct ChildNode *firstchild; /*孩子鏈表頭指針*/
}NodeType;
NodeType t［MAXNODE］;
3） 孩子兄弟表示法這種表示法又稱為二叉樹表示法，或二叉鏈表表示法。即以二叉鏈表作為樹的存儲結構，鏈表中結點的兩個域分別指向該結點的第一個孩子和下一個兄弟，分別命名為firstchild和nextsibling域。樹的孩子兄弟表示法的類型定義如下：
typedef struct tnode {
DataType data;
struct tnode *firstchild, *nextsibling;
} Tnode;
圖313所示的樹對應的孩子兄弟表示如圖318。利用樹的孩子兄弟鏈表這種存儲結構便于實現各種樹的操作。例如，找某結點的第i個孩子，則只要先從左指針域中找到第1個孩子結點，然后沿著孩子結點的nextsibling域連續走i-1步便可找到第i個孩子。如增加一個parent域，也能方便實現求雙親的操作。
圖318樹的孩子兄弟表示法
2. 森林的存儲結構森林的存儲方式也采用二叉鏈表的形式。森林實際上是多棵樹結構的集合，而且在樹的孩子兄弟表示法中表示每棵樹的根結點的右指針必然為空。因此采用這樣的方法，對于第N 1棵樹將其根結點掛到表示第N棵樹的根節點的右指針上即可。3．4．2樹和森林與二叉樹之間的轉換
從樹的孩子兄弟表示法可以看出，如果設定一定規則，就可以用二叉樹結構表示樹和森林。這樣，對樹的操作實現就可以借助二叉樹存儲，利用二叉樹上的操作來實現。本節將討論樹和森林與二叉樹之間的轉換。1． 樹與二叉樹的相互轉換1） 樹轉換為二叉樹對于一棵無序樹，樹中結點的各孩子結點的次序無關緊要，而二叉樹中結點的左、右孩子結點是有區別的。為避免發生混淆，約定樹中每個結點的孩子結點按從左到右的次序編號。將一棵樹轉換成二叉樹的方法是(1) 加線： 在兄弟之間加一連線。(2) 抹線： 對每個結點，除了其左孩子外，去除其與其余孩子之間的關系。(3) 旋轉： 以樹的根結點為軸心，將整樹順時針轉45°。圖319展示了樹轉換為二叉樹的過程。經過這種方法轉換后，對應的二叉樹是唯一的。
圖319樹轉為二叉樹的過程
由圖319的轉換可以看出，二叉樹中，左分支上的各結點在原來的樹中是父子關系，而右分支上的各結點在原來的樹中是兄弟關系。由于樹的根結點沒有兄弟，所以變換后二叉樹的根結點的右孩子必為空。2） 二叉樹還原為樹二叉樹轉換為樹，就是將樹轉換為二叉樹的逆過程。樹轉換為二叉樹，二叉樹的根結點一定沒有右孩子，對于一棵缺少右子樹的二叉樹也有唯一的一棵樹與之對應。將一棵二叉樹還原為樹的的步驟如下： (1) 加線： 若p結點是雙親結點的左孩子，則將p的右孩子，右孩子的右孩子……，沿分支找到的所有右孩子，都與p的雙親用線連起來。(2) 抹線： 抹掉原二叉樹中雙親與右孩子之間的連線。(3) 調整： 將結點按層次排列，形成樹結構。圖320展示了二叉樹還原為樹的過程。一棵沒有右子樹的二叉樹經過這種方法還原后，對應的樹也是唯一的。
圖320二叉樹還原成樹的過程
2． 森林與二叉樹的相互轉換1） 森林轉換為二叉樹由森林的概念可知，森林是由若干棵樹組成的集合，樹可以轉換為二叉樹，那么森林也可以轉換為二叉樹。如果將森林中的每棵樹轉換為對應的二叉樹，則再將這些二叉樹按照規則轉換為一棵二叉樹，就實現了森林到二叉樹的轉換。森林轉換為對應的二叉樹的步驟如下： (1) 將森林中各棵樹分別轉換成二叉樹。（2） 第1棵二叉樹不動，從第2棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連在一起后，所得到的二叉樹就是由森林轉換得到的二叉樹。
圖321森林轉化為二叉樹的過程
2） 二叉樹還原為森林將二叉樹還原為森林的方法不難構造，具體還原過程如下： (1) 抹線： 將二叉樹中根結點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹。(2) 還原： 將孤立的二叉樹還原成樹。(3) 調整： 將還原后的樹的根結點排列成一排。圖322展示了二叉樹還原為森林的過程。一棵具有左子樹和右子樹的二叉樹經過這種方法還原后，對應的森林是唯一的。
圖322二叉樹還原為森林的過程
3．4．3樹和森林的遍歷由樹結構的定義可引出樹的兩種次序的遍歷。一種是先根遍歷樹，即先訪問樹的根結點，然后依次先根遍歷樹的每棵子樹； 另一種是后根遍歷，即先依次后根遍歷每棵子樹，然后訪問根結點。對圖31的樹進行先根遍歷，可得到樹的先根遍歷序列為
ABDGHICEJF
若對此樹進行后根遍歷，則得到樹的后根序列為
GHIDBJEFCA
按照森林和樹相互遞歸的定義，可以推出森林的兩種遍歷方法。1． 先序遍歷森林若森林非空，則可按下述規則遍歷。(1) 訪問森林中的第一棵樹的根結點。(2) 先序遍歷第一棵樹中根結點的子樹森林。(3) 先序遍歷除去第一棵子樹之后剩余的樹構成的森林。2． 中序遍歷森林若森林非空，則可按下述規則遍歷。(1) 中序遍歷森林中第一棵樹中根結點的子樹森林。(2) 訪問第一棵子樹的根結點。(3) 中序遍歷除去第一棵子樹之后剩余的樹構成的森林。對圖322中森林進行先序遍歷，可得到森林的先序序列為
ABCDEFGHIJ
若對此森林進行中序遍歷，則得到森林的中序序列為
BCDAFEHJIG
由3.4.2節森林與二叉樹之間轉換的規則可知，當森林轉換成二叉樹時，其第一棵樹的子樹森林轉換成左子樹，剩余樹的森林轉換為右子樹，則上述森林的先序和中序遍歷即為其對應的二叉樹的先序和中序遍歷。由此可見，當以二叉鏈表作為樹的存儲結構時，樹的先根遍歷和后根遍歷可借用二叉樹的先序遍歷和中序遍歷的算法來實現。
3．5二叉樹的應用3．5．1哈夫曼樹及其應用
哈夫曼樹也稱為最優二叉樹。它是一種帶權路徑最短的樹，應用非常廣泛。本節主要介紹哈夫曼樹的定義、哈夫曼編碼及哈夫曼編碼算法的實現。1． 哈夫曼樹的定義先介紹幾個基本概念和術語。一棵樹中，從一個結點往下可以達到的孩子或子孫結點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規定根結點的層數為1，則從根結點到第L層結點的路徑長度為L-1。若將樹中結點賦給一個有著某種含義的數值，則這個數值稱為該結點的權。從根結點到該結點之間的路徑長度與該結點的權的乘積稱為結點的帶權路徑長度。樹的帶權路徑長度(Weighted Path Length of Tree，簡記為WPL)規定為所有葉子結點的帶權路徑長度之和：WPL=∑ni=1wi*li（31）其中n為葉子結點數目，wi為第i 個葉子結點的權值，li 為第i個葉子結點的路徑長度。在一棵二叉樹中，若樹的帶權路徑長度達到最小，稱這樣的二叉樹為最優二叉樹，也稱為哈夫曼樹。
【例31】有4個結點，權值分別為7，5，2，4，構造有4個葉子結點的二叉樹。由這4個葉子結點可以構造出形態不同的二叉樹，如圖323所示。
圖323具有不同帶權路徑長度的二叉樹
從帶權路徑長度最小，這一角度來看，完全二叉樹不一定是最優二叉樹。圖323(c)樹的WPL最小，此樹就是哈夫曼樹。由n個帶權葉子結點所構成的二叉樹中，滿二叉樹和完全二叉樹不一定是最優二叉樹。權值越大的結點離根結點越近的二叉樹才是最優二叉樹。2． 哈夫曼樹的建立根據哈夫曼樹的定義，一棵二叉樹要使其WPL值最小，必須使權值越大的葉子結點越靠近根結點，而權值越小的葉子結點越遠離根結點。哈夫曼依據這一特點提出了一種構造最優二叉樹的方法，其基本思想如下： （1） 根據給定的n個權值w1，w2，…，wn構成n棵二叉樹的森林F={T1，T2，…，Tn}。其中，每棵二叉樹Ti中都只有一個權值為wi的根結點，其左右子樹均空。（2） 在森林F中選出兩棵根結點權值最小的樹(當這樣的樹不止兩棵樹時，可以從中任選兩棵)，將這兩棵樹合并成一棵新樹，為了保證新樹仍是二叉樹，需要增加一個新結點作為新樹的根，并將所選的兩棵樹的根分別作為新根的左右孩子(誰左，誰右無關緊要)，將這兩個孩子的權值之和作為新樹根的權值。（3） 對新的森林F重復（2），直到森林F中只剩下一棵樹為止。這棵樹便是哈夫曼樹。例如，假設給定一組權值{7, 5, 2, 4}，按照哈夫曼樹構造的算法，對集合的權重構造哈夫曼樹的過程如圖324所示。
圖324哈夫曼樹的構造過程
構造哈夫曼樹時，可以設置一個結構數組HuffNode保存哈夫曼樹中各結點的信息。根據二叉樹的性質可知，具有n個葉子結點的哈夫曼樹共有2n-1個結點，所以數組HuffNode的大小設置為2n-1，數組元素的結構形式如圖325所示。
圖325數組元素的結構形式
其中，weight域保存結點的權值，lchild和rchild域分別保存該結點的左右孩子結點在數組HuffNode中的序號，從而建立起結點之間的關系。為了判定一個結點是否已加入到要建立的哈夫曼樹中，可以通過當初parent的值為-1，當結點加入到樹中時，該結點parent的值為其雙親結點在數組HuffNode中的序號，就不會是-1了。構造哈夫曼樹時，首先將由n個權值形成的n個葉子結點存放到數組HuffNode的前n個分量中，然后根據前面介紹的哈夫曼方法的基本思想，不斷將兩個小子樹合并為一個較大的子樹，每次構成的新子樹的根結點順序放在HuffNode數組中的前n個分量的后面。哈夫曼樹的構造算法如下：
#define MAXVALUE 10000 /*定義最大權值*/
#define MAXLEAF 30 /*定義哈夫曼樹中葉子結點的最大個數*/
#define MAXNODE MAXLEAF *2-1 /*定義哈夫曼樹中結點的最大個數*/
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
}HNode, HuffmanTree［MAXNODE］;
void CrtHuffmanTree(HuffmanTree ht, int w［］, int n)/*數組w［］傳遞n個權值*/
{
int i,j,m1,m2,x1,x2;
for(i=0;i2*n-1;i ){/*ht初始化*/
ht［i］.weight=0;
ht［i］.parent=-1;
ht［i］.lchild=-1;
ht［i］.rchild=-1;
}
for(i=0;in;i ) ht［i］.weight=w［i］; /*賦予n個葉子結點的權值*/
for(i=0;in-1;i ) /*構造哈夫曼樹*/
{
m1=m2=MAXVALUE;
x1=x2=0;
for(j=0;jn i;j ) /*尋找權值最小和次小的兩棵樹*/
{
if(ht［j］.weightm1&&ht［j］.parent==-1)
{
m2=m1; x2=x1; x1=j;
m1=ht［j］.weight;
}
else if (ht(j),weightm2&&ht［j］.parent==-1)
{
m2=ht［j］.weight;
x2=j;
}
}
/*將兩棵子樹合并成一棵子樹*/
ht［x1］.parent=n i; ht［x2］.parent=n i;
ht［n i］.weight=ht［x1］.weight ht［x2］.lweight;
ht［n i］.lchild=x1; ht［n i］.rchild=x2;
}
}
3． 哈夫曼編碼哈夫曼編碼常應用在數據通信中，數據傳送時，需要將字符轉換為二進制的編碼串。例如，假設傳送的電文是ABDAACDA,電文中有A、B、C、D 4種字符，如果規定A、B、C、D的編碼分別為00、01、10、11，則上面的電文代碼為0001110000101100，總共16個二進制數。傳送電文時，總是希望電文代碼盡可能短，采用哈夫曼編碼構造的電文的總長最短。通信中，可以采用0、1的不同排列來表示不同的字符，稱為二進制編碼。若每個字符出現的頻率不同，可以采用不等長的二進制編碼，頻率較大的采用位數較少的編碼，頻率較小的字符采用位數較多的編碼，這樣可以使字符的整體編碼長度最小，這就是最小冗余編碼的問題。哈夫曼編碼就是一種不等長的二進制編碼，且哈夫曼樹是一種最優二叉樹，它的編碼也是一種最優編碼。利用哈夫曼樹編碼來構造編碼方案，就是哈夫曼樹的典型應用。具體做法如下： 設需要編碼的字符集合為D={d1，d2，…，dn}，它們在電文中出現的次數或頻率集合為{w1，w2，…，wn}，以d1，d2，…，dn作為葉結點，w1，w2，…，wn作為它們的權值，構造一棵哈夫曼樹，規定哈夫曼樹中的左分支代表0，右分支代表1，則從根結點到每個葉結點所經過的路徑分支組成的0和1的序列便為該結點對應字符的編碼，稱之為哈夫曼編碼。這樣的哈夫曼樹亦成為哈夫曼編碼樹。
按照以上構造方法，字符集合為{A,B,C,D}，各個字符相應的出現次數為{4,1,1,2}，這些字符作為葉子結點構成的哈夫曼樹如圖326所示，
圖326哈夫曼編碼樹
字符A的編碼為0，字符B的編碼為110，字符C的編碼為111，字符D的編碼為10。
哈夫曼編碼樹中，樹的帶權路徑長度的含義是各個字符的碼長與其出現次數的乘積之和，也就是報文的代碼總長，所以采用哈夫曼樹的編碼是一種能夠使報文代碼總長最短的不定長編碼。設計不等長編碼時，必須使任何一個字符的編碼都不是另外一個字符編碼的前綴。例如，字符A的編碼為10，字符B的編碼是100，則字符A的編碼就稱為字符B編碼的前綴。如果一個代碼是10010，在進行譯碼時，無法確定是將前兩位譯為A，還是將前三位譯為B。但是在利用哈夫曼樹進行編碼時，每個編碼是葉子結點的編碼，一個字符是不會出現在另一個字符前面的，也就不會出現一個字符的編碼是另一個字符編碼的前綴編碼。任何一個字符的編碼都不是另一個字符編碼的前綴,這種編碼稱為前綴編碼。哈夫曼編碼的算法實現如下： 前面已經給出了哈夫曼樹的構造算法，為實現哈夫曼樹，自然需要定義一個編碼表的存儲結構。定義如下：
typedef struct codenode
{ char ch; /*存放要表示的符號*/
char *code; /*存放相應的代碼*/
}CodeNode
typedef CodeNode HuffmanCode［MAXLEAF］;
哈夫曼編碼的算法思路是在哈夫曼樹中，從每個葉子結點開始，一直往上搜索，判斷該結點是其雙親結點的左孩子還是右孩子，若是左孩子，則相應位置上的代碼為0，否則是1，直至搜索到根結點為止。算法如下：
void CrtHuffmanCode(HuffmanTree ht,HuffmanCode hc,int n)
/*從葉子結點到根，逆向搜索求每個葉子結點對應符號的哈夫曼編碼*/
{
char *cd;
int i,c,p,start;
cd=malloc(n*sizeof(char)); /*為當前工作區分配空間*/
cd［n-1］=’＼0’; /*從右到左逐位存放編碼，首先存放結束符*/
for(i=1;i=n;i ) /*求n個葉子結點對應的哈夫曼編碼*/
{
start=n-1; /*編碼存放的起始位置*/
c=i;p=ht［i］.parent; /*從葉子結點開始往上搜索*/
while(p!=0)
{
- - start;
if(ht［p］.lchild==c) cd［start］=’0’ /*左分支標0*/
else cd［start］=’1’; /*右分支標1*/
c=p; p=ht［p］.parent; /*向上倒推*/
}
hc［i］=malloc((n-start)*sizeof(char)); /*為第i個編碼分配空間*/
scanf("%c",&(hc［i］.ch)); /*輸入相應待編碼字符*/
strcpy(hc［i］,&ch［start］); /*將工作區中編碼復制到編碼表中*/
}
free(cd);
}
3．5．2二叉排序樹
圖327二叉排序樹
二叉排序樹又稱二叉查找樹、二叉搜索樹。它或者是一棵空樹。或者是具有下列性質的二叉樹： 若左子樹不空，則左子樹上所有結點的值均小于它根結點的值； 若右子樹不空，則右子樹上所有結點的值均大于等于它根結點的值； 左、右子樹也分別為二叉排序樹。二叉排序樹的相關算法參見4.9.1節。
例如，圖327所示的二叉排序樹。
由給定的數據序列生成二叉排序樹的過程是在二叉排序樹上插入結點的過程，對于一個數據序列(R1，R2，…，Rn)： （1） 設R1為二叉排序樹的根。（2） 若R249，且76>65，則應插入成為(65)的右子樹根結點……。以此類推，最后得到如圖328(i)所示的二叉排序樹。
圖328由關鍵字生序列生成二叉排序樹的過程
3．6圖圖(Graph)是一種比線性表和樹更為復雜的非線性數據結構。圖中元素的關系既不像線性表中的元素至多只有一個直接前趨和一個直接后繼，也不像樹形結構中的元素具有明顯的層次關系。圖中元素之間的關系可以是任意的，每個元素(也稱為頂點)可以具有多個直接前趨和后繼，所以圖可以表達數據元素之間廣泛存在著的更為復雜的關系。圖在語言學、邏輯學、數學、物理、化學、通信和計算機科學等領域中得到了廣泛的應用。3．6．1圖的基本概念1. 圖的定義
圖(G)是一種非線性數據結構，它由兩個集合V(G)和E(G)組成，形式上記為G=(V, E)。其中，V(G)是頂點(Vertex)的非空有限集合，E(G)是V(G)中任意兩個頂點之間的關系集合，又稱為邊(Edge)的有限集合。當G中的每條邊有方向時，稱G為有向圖。有向邊使用一對尖括號(< >)將兩個頂點組成的有序對括起來，記為<起始頂點，終止頂點>。有向邊又稱為弧，因此弧的起始頂點就稱為弧尾，終止頂點稱為弧頭。圖329給出了一個有向圖的示例，該圖的頂點集和邊集分別為
V(G1)={V1, V2, V3, V4}
E(G1)={, , , }
圖329有向圖示例
圖330無向圖示例
若G中的每條邊是無方向時，稱G為無向圖。這時，兩個頂點之間最多只存在一條邊。無向圖的一條邊使用一對圓括號(( ))將兩個頂點組成的無序對括起來，記為(頂點1，頂點2)或(頂點2，頂點1)。圖330給出了一個無向圖的示例。該圖的頂點集和邊集分別為
V(G2)={V1, V2, V3, V4}
E(G2)={(V1, V2), (V1, V3), (V1, V4), (V3, V4)}={(V2, V1), (V3, V1), (V4, V1), (V4, V3)}
2. 基本術語1） 完全圖、稀疏圖和稠密圖下面的討論中，不考慮頂點到其自身的邊，也不允許一條邊在圖中重復出現。在以上兩條約束下，邊和頂點之間存在以下關系。(1) 對一個無向圖，它的頂點數n和邊數e滿足0≤e≤n(n-1)/2的關系。如果e=n(n-1)/2，則該無向圖稱為完全無向圖。(2) 對一個有向圖，它的頂點數n和邊數e滿足0≤e≤n(n-1)的關系。如果e=n(n-1)，則稱該有向圖為完全有向圖。(3) 如果e
圖331圖與子圖
3） 鄰接點無向圖G中，若邊(Vi, Vj)∈E(G)，則稱頂點Vi和Vj相互鄰接，兩個頂點互為鄰接點，并稱邊(Vi, Vj)關聯于頂點Vi和Vj或稱邊(Vi, Vj)與頂點Vi和Vj相關聯。例如，在圖330中的頂點1與頂點2、頂點3和頂點4互為鄰接點，關聯于頂點1的邊是(V1, V2)、(V1, V3)和(V1, V4)。有向圖G中，若弧∈E(G)，則稱頂點Vi鄰接到Vj或Vj鄰接自Vi，并稱弧關聯于頂點Vi和Vj或稱弧與頂點Vi和Vj相關聯。例如，在圖329中的頂點1鄰接到頂點2和頂點3，或稱頂點2或頂點3鄰接自頂點1，而頂點4鄰接到頂點1，或稱頂點1鄰接自頂點4。4） 度、入度和出度無向圖中關聯于某一頂點Vi的邊的數目稱為Vi的度，記為D(Vi)。例如，圖330中的頂點1的度為3。有向圖中，把以頂點Vi為終點的邊的數目稱為Vi的入度，記為ID(Vi)； 把以頂點Vi為起點的邊的數目稱為Vi的出度，記為OD(Vi)； 把頂點Vi的度定義為該頂點的入度和出度之和。例如，圖329中頂點1的入度為1，出度為2，度為3。
如果圖G中有n個頂點，e條邊，且每個頂點的度為D(Vi)(1≤i≤n)，則存在以下關系：
圖332網（帶權圖）
e=∑ni=1D(vi)/2(32)5） 權與網一個圖中，如果圖的邊或弧具有一個與它相關的數時，這個數就稱為該邊或弧的權，這個數常用來表示一個頂點到另一個頂點的距離或耗費。如果圖中的每一條邊都具有權時，這個帶權圖稱為網絡，簡稱為網，如圖332所示。
6） 路徑與回路一個圖中，若從頂點V1出發，沿著一些邊經過頂點V1, V2, …, Vn-1到達頂點Vn，則稱頂點序列(V1, V2, …, Vn-1, Vn)為從V1到Vn的一條路徑。例如，圖330中(V4, V3, V1)是一條路徑。而在圖329中，(V4, V3, V1)就不是一條路徑。將無權圖沿路徑所經過的邊數，稱為該路徑的長度。而對有權圖，取沿路徑各邊的權之和作為此路徑的長度。圖331所示的G3中頂點1到頂點3的路徑長度為2。若路徑中的頂點不重復出現，則這條路徑稱為簡單路徑。起點和終點相同并且路徑長度不小于2的簡單路徑稱為簡單回路或簡單環。例如，圖330的無向圖中頂點序列(V4, V3, V1)是一條簡單路徑，而(V4, V3, V1, V4)是一個簡單環。7） 圖的連通性一個有向圖中，若存在一個頂點V，從該頂點有路徑可到達圖中其他所有頂點，則稱這個有向圖為有根圖，V稱為該圖的根。例如，圖329就是一個有根圖，該圖的根是V1、V3和V4。無向圖G中，若頂點Vi和Vj(i≠j)有路徑相通，則稱Vi和Vj連通。如果V(G)中的任意兩個頂點都連通，則稱G是連通圖，否則為非連通圖，如圖333 (a) 所示。無向圖G中的極大連通子圖稱為G的連通分量。對任何連通圖而言，連通分量就是其自身，對非連通圖可有多個連通分量，如圖333 (b)所示。有向圖G中，若從Vi到Vj(i≠j)、從Vj到Vi都存在路徑，則稱Vi和Vj強連通。若有向圖V(G)中的任意兩個頂點都是強連通的，則稱該圖為強連通圖。有向圖中的極大連通子圖稱作有向圖的強連通分量。例如，圖329中的頂點V1、V3和V4是強連通的，但該有向圖不是一個強連通圖。
圖333無向圖及其連通分量
3.6.2圖的存儲方法由于圖的結構復雜，任意兩個頂點之間都可能存在聯系，所以無法以數據元素在存儲區中的物理位置來表示元素之間的關系，但仍可以借助一個二維數組中各單元的數據取值或用多重鏈表來表示元素間的關系。無論采用什么存儲方法，都需要存儲圖中各頂點本身的信息和存儲頂點與頂點之間的關系。事先對圖中的每個頂點進行順序編號以后，各個頂點的數據信息即可保存在一個一維數組中，且頂點的編號與一維數組下標一一對應。因此，研究圖的存儲方法，主要是解決如何實現各個頂點之間關系的表示問題。圖的存儲方法很多，常用的有鄰接矩陣存儲方法、鄰接表存儲方法、十字鏈表存儲方法和多重鄰接表存儲方法。選擇存儲方法的依據取決于具體的應用和所要施加的運算。這里僅介紹鄰接矩陣存儲方法和鄰接表存儲方法。1. 鄰接矩陣存儲方法根據圖的定義可知，一個圖的邏輯結構分兩部分，一部分是組成圖的頂點的集合； 另一部分是頂點之間的聯系，即邊或弧的集合。因此，計算機中存儲圖需要解決這兩部分的存儲表示。鄰接矩陣存儲方法中，使用一個一維數組來存放圖中每個頂點的數據信息，而利用一個二維數組(又稱為鄰接矩陣)來表示圖中各頂點之間的關系。對一個有n個頂點的圖G而言，將使用一個n×n的矩陣來表示其頂點間的關系，矩陣的每一行和每一列都順序對應每一個頂點。矩陣中的元素A［i, j］可按以下規則取值。A［i, j］=1,若(vi,vj)或∈E(G)0，若(vi,vj)或E(G)0≤i,j≤n－1(33)
一般情況下，大家不關心圖中頂點的情況，若頂點編號為1～vtxnum，設弧上或邊上無權值，則使用C語言可以將圖的存儲結構簡化為一個二維數組，如下所示。
intadjmatrix［vtxnum］［vtxnum］;
如圖330中的G2和圖331中的G3，其鄰接矩陣分別如圖334中A1、A2所示。
圖334圖G2和G3的鄰接矩陣
借助于鄰接矩陣，可以很容易地求出圖中頂點的度。從上例可以看出，鄰接矩陣有如下結論。(1) 無向圖的鄰接矩陣是對稱的，而有向圖的鄰接矩陣不一定對稱。對無向圖可考慮只存下三角(或上三角)元素。(2)對于無向圖，鄰接矩陣第i行(或第i列)的元素之和是頂點Vi的度。(3)對于有向圖，鄰接矩陣第i行元素之和為頂點Vi的出度； 第i列的元素之和為頂點Vi的入度。對于網絡，鄰接矩陣元素A［i, j］可按以下規則取值。A［i, j］=Wij,若(vi,vj)或∈E(G)
0或∞,若(vi,vj)或vi,vj>E(G)0≤i,j≤n－1(34)其中,Wij是邊(Vi, Vj)或弧< Vi, Vj>上的權值。當一個圖用鄰接矩陣表示時，使用C語言編寫算法可用以下數據類型說明。
#define n /* 圖的頂點數 */
#define e /* 圖的邊數 */
typedef char vextype; /* 頂點的數據類型 */
typedef float adjtype; /* 頂點權值的數據類型 */
typedef struct {
vextype vexs［n］; /* 頂點數組 */
adjtype arcs［n］［n］; /* 鄰接矩陣 */
} graph;
下面給出了一個無向網絡鄰接矩陣利用上述類型說明的建立算法。
CREATGRAPH(graph *g)
{/* 建立無向網絡 */
int i, j, k;
float w;
for(i=0; in; i )
g-vexs［i］=getchar( ); /* 讀入頂點信息，建立頂點表 */
for(i=0; in; i )
for(j=0; jn; j )
g-arcs［i］［j］=0; /* 鄰接矩陣初始化 */
for(k=0; ke; k ) {
scanf("%d%d%f", &i, &j, &w); /* 讀入邊(Vi, Vj)上的權w */
g-arcs［i］［j］=w; /* 寫入鄰接矩陣 */
g-arcs［j］［i］=w; }
}
如果要建立無向圖，可在以上算法中改變w的類型，并使輸入值為1即可； 如果要建立有向網絡，只需將寫入矩陣的兩個語句中的后一個語句去除即可。以上算法中，如果鄰接矩陣是一個稀疏矩陣，則存在存儲空間浪費現象。該算法的執行時間是O(n n2 e)。通常e<#define VTXUNM n /*n為圖中頂點個數的最大可能值*/
#define ETXUNM e /*e為圖中邊數的最大可能值*/
typedef char vextype; /* 定義頂點數據信息類型 */
struct arcnode { /* 鄰接鏈表結點 */
int adjvex; /* 鄰接點域 */
float data; /* 權值(無權圖不含此項) */
struct arcnode *nextarc; /* 鏈域 */
};
typedef struct arcnode ARCNODE;
struct headnode {
vextype vexdata; /* 頂點域 */
ARCNODE *firstarc; /* 指針域 */
}adjlist［VTXUNM］; /* 頂點表 */
對于無向圖，Vi的鄰接鏈表中每個結點都對應與Vi相關聯的一條邊，第i個單鏈表的結點個數就是此結點的度，所以將無向圖的鄰接鏈表稱為邊表。對于有向圖，Vi的鄰接鏈表中每個結點都對應于以Vi為起始點射出的一條邊，其鄰接表中第i個單鏈表的結點個數就是此結點的出度，所以有向圖的鄰接鏈表也稱為出邊表。有向圖還有一種逆鄰接表表示法，這種方法的Vi鄰接鏈表中的每個結點對應于以Vi為終點的一條邊，其鄰接表中第i個單鏈表的結點個數就是此結點的入度，因而稱這種鄰接鏈表為入邊表。對于圖335(a)的有向圖和圖336(a)的無向圖，其鄰接表存儲結構分別如圖335(b)和圖336(b)所示。
圖335有向帶權圖及其鄰接表
圖336無向圖及其鄰接表
鄰接表上容易找到任一頂點的第一個鄰接點和下一個鄰接點，但要判定任意兩個頂點(Vi和Vj)之間是否有邊或弧相連，則需搜索第i個或第j個鏈表，因此不及鄰接矩陣方便。無論是無向圖還是有向圖，其鄰接表的建立都比較簡單，下面給出無向圖鄰接表的建立算法。
CREATADJLIST(struct headnode ga［ ］)
{/* 建立無向圖的鄰接表 */
int i, j, k;
ARCNODE *s;
for(i=0; iVTXUNM; i )
{
ga［i］. vexdata = getchar( ); /* 讀入頂點信息和邊表頭指針初始化 */
ga［i］. firstarc = NULL; }
for(k=0; kETXUNM; k )
{/* 建立邊表 */
scanf("%d%d", &i, &j); /* 讀入邊(Vi, Vj)的頂點序號 */
s=malloc(sizeof(ARCNODE)); /* 生成鄰接點序號為j的邊表結點*s */
s-adjvex=j;
s- nextarc =ga［i］.firstarc;
ga［i］.firstarc =s; /* 將*s插入頂點Vi的邊表頭部 */
s=malloc(sizeof(ARCNODE)); /* 生成鄰接點序號為i的邊表結點*s */
s-adjvex=i;
s- nextarc =ga［j］.firstarc;
ga［j］.firstarc =s; } /* 將*s插入頂點Vj的邊表頭部 */
}
如果要建立有向圖的鄰接表，則只需去除上述算法中“生成鄰接點序號為i的邊表結點*s”部分，僅僅保留“生成鄰接點序號為j的邊表結點*s”那一段語句組即可。若要建立網絡的鄰接表，只要在邊表的每個結點中增加一個存儲邊上權值的數據域即可。該算法的執行時間是O(n e)。鄰接矩陣和鄰接表是圖中最常用的存儲結構，它們各有所長，具體體現在以下幾點： (1) 一個圖的鄰接矩陣表示是唯一的，而其鄰接表表示不唯一，這是因為鄰接鏈表中的結點的鏈接次序取決于建立鄰接表的算法和邊的輸入次序。(2) 鄰接矩陣表示中判定(Vi, Vj)或是否是圖中的一條邊，只需判定矩陣中的第i行第j列的元素是否為零即可。而在鄰接表中，需要掃描Vi對應的鄰接鏈表，最壞情況下需要的執行時間為O(n)。(3) 求圖中邊的數目時，使用鄰接矩陣必須檢測完整個矩陣之后才能確定，所消耗的時間為O(n2)； 而在鄰接表中，只需對每個邊表中的結點個數計數便可確定。當e<
圖337連通圖G、鄰接表及其鄰接矩陣
求解過程是先訪問V1，再訪問與V1鄰接的V2，再訪問V2的第一個鄰接點，因V1已被訪問過，則訪問V2的下一個鄰接點V4，然后依次訪問V8，V5。這時，與V5相鄰接的頂點均已被訪問，于是反向回到V8去訪問與V8相鄰接且尚未被訪問的V6，接著訪問V3，V7，至此，全部頂點均被訪問。相應的訪問序列為V1→V2→V4→V8→V5→V6→V3→V7。下面給出以鄰接表作為存儲結構的深度優先搜索遞歸算法DFSL。
#define VTXUNM n /*n為圖中頂點個數的最大可能值*/
typedef char vextype; /* 定義頂點數據信息類型 */
struct arcnode {
int adjvex;
float data;
struct arcnode *nextarc;
};
typedef struct arcnode ARCNODE;
struct headnode {
vextype vexdata;
ARCNODE *firstarc;
};
struct headnode G［VTXUNM 1］;
int visited［VTXUNM 1］;
void DFSL(struct headnode G［］, int v) {
ARCNODE *p;
printf(''%c-'', G［v］.vexdata);
visited［v］=1;
p=G［v］.firstarc;
while (p!=NULL) { /* 當鄰接點存在時*/
if (visited［p-adjvex］==0)
DFSL(G, p-adjvex);
p=p-nextarc; /* 找下一鄰接點*/
}
}
void traver(struct headnode G［］) {
int v;
for(v=1;v= VTXUNM;v )
visited［v］=0;
for(v=1; v= VTXUNM;v )
if(visited［v］==0) DFSL(G, v);
}
如果采用深度優先搜索的非遞歸算法DFSL，則程序如下：
#define VTXUNM n
void traver_ DFSL(struct headnode G［］,int v) {
int stack［VTXUNM］;
int top=-1;
int i;
ARCNODE *p;
printf(''%c-'', G［v］.vexdata);
visited［v］=1;
top ;
stack［top］=v; /*訪問過的頂點進棧*/
p=G［v］.firstarc;
while ((top!= -1)||(p!=NULL)) {
while(p!=NULL) {
if (visited［p-adjvex］==1)
p=p-nextarc;
else {
printf(''%c-'', G［p-adjvex］.vexdata);
visited［p-adjvex］=1;
top ;
stack［top］=p-adjvex;
p=G［p-adjvex］.firstarc;
}
}
if(top!= -1) {
v=stack［top］;
top--;
p=G［v］.firstarc;
p=p-nextarc;
}
}
}
因為搜索n個頂點的所有鄰接點需要對邊表各結點掃描一遍，而邊表結點的數目為2e，所以算法的時間復雜度為O(2e n)，空間復雜度為O(n)。選擇鄰接矩陣作為圖的存儲結構時，圖337(a)所示的連通圖G的鄰接矩陣表示如圖337(c)所示，其深度優先搜索遍歷算法DFSA描述如下：
#define VTXUNM n/*n為圖中頂點個數的最大可能值*/
typedef char vextype; /* 頂點的數據類型 */
typedef int adjtype; /* 頂點權值的數據類型 */
typedef struct {
vextype vexs［VTXUNM］; /* 頂點數組 */
adjtype arcs［VTXUNM］［VTXUNM］; /* 鄰接矩陣 */
} graph;
graph g; /* g為全局變量 */
int visited［VTXUNM］;
void DFSA (int i) { /* 從Vi出發深度優先搜索圖g，g用鄰接矩陣表示 */
int j;
printf("node: %c＼n", g.vexs［i］); /* 訪問出發點Vi */
visited［i］=1; /* 標記Vi已被訪問 */
for(j=0; jn; j ) /* 依次搜索Vi的鄰接點 */
if ((g.arcs［i］［j］==1)&&(visited［j］==0))
DFSA(j); /* 若Vi的鄰接點Vj未被訪問過，則從Vj出發進行深度優先搜索遍歷 */
} /* DFSA */
上述算法中，每進行一次DFSA(i)的調用，for循環中v的變化范圍都是0~n-1，而DFSA(i)要被調用n次，所以算法的時間復雜度為O(n2)。因為是遞歸調用，需要使用一個長度為n-1的工作棧和長度為n的輔助數組，所以算法的空間復雜度為O(n)。2. 廣度優先搜索遍歷對于一個圖，按廣度優先搜索遍歷先后順序得到的頂點序列稱為該圖的廣度優先搜索(BFS, BreadthFirst Search)遍歷序列，簡稱為BFS序列。圖的廣度優先搜索遍歷類似于樹的按層次遍歷。一個圖的BFS序列不是唯一的，它與算法、圖的存儲結構和初始出發點有關。當確定了有多個鄰接點時，按鄰接點的序號從小到大進行選擇和指定初始出發點后，以鄰接矩陣作為存儲結構得到的BFS序列是唯一的，而以鄰接表作為存儲結構得到的BFS序列并不唯一，它取決于鄰接表中邊表結點的鏈接次序。假設初始狀態是圖中所有頂點都未被訪問，BFS方法從圖中某一頂點V0出發，先訪問V0，然后訪問V0的各個未被訪問過的鄰接點，再分別從這些鄰接點出發廣度優先搜索遍歷圖，以此類推，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。如果是非連通圖，則選擇一個未曾被訪問的頂點作為起始點，重復以上過程，直到圖中所有頂點都被訪問為止。具體遍歷步驟如下： (1)訪問V0。(2)從V0出發，依次訪問V0的未被訪問過的鄰接點V1，V2，…，Vt。然后依次從V1，V2，…，Vt出發，訪問各自未被訪問過的鄰接點。(3)重復步驟(2)，直到所有頂點的鄰接點均被訪問過為止。在這種方法的遍歷過程中，先被訪問的頂點，其鄰接點也先被訪問，具有先進先出的特性，實現算法時，使用一個隊列來保存每次已訪問過的頂點，然后將隊頭頂點出列，去訪問與它鄰接的所有頂點，重復上述過程，直至隊空。為了避免重復訪問一個頂點，使用一個輔助數組visited［n］來標記頂點的訪問情況。針對圖337所示的連通圖G、鄰接表及其鄰接矩陣存儲結構表示，假設從頂點V1出發，按廣度優先搜索法先訪問V1，然后訪問V1的鄰接點V2和V3，再依次訪問V2和V3的未被訪問的鄰接點V4、V5、V6及V7，最后訪問V4的鄰接點V8。遍歷序列描述如下： V0→V1→V2→V3→V4→V5→V6→V7下面給出以鄰接矩陣為存儲結構時的廣度優先搜索遍歷算法BFSA。
#define VTXUNM n
graph g; /* g為全局變量 */
int visited［VTXUNM］;
void BFSA(int k)
{ /* 從Vk出發廣度優先搜索遍歷圖g，g用鄰接矩陣表示 */
int queue［VTXUNM］;
int rear=VTXUNM-1; front=VTXUNM-1;/* queue置為空隊 */
int i, j;
printf("%c＼n", g.vexs［k］); /* 訪問出發點 Vk */
visited［k］=1; /* 標記Vk已被訪問 */
rear ;
queue［rear］=k; /* 訪問過的頂點序號入隊 */
while(front!=rear)
{ /* 隊非空時執行下列操作 */
front ;
i=queue［front］ /* 隊頭元素序號出隊 */
for(j=0; jn; j )
if((g.arcs［i］［j］==1)&&(visited［j］!=1))
{
printf("%c＼n", g.vexs［j］); /* 訪問Vi未被訪問的鄰接點Vj */
visited［j］=1;
rear ;
queue［rear］=j; /* 訪問過的頂點入隊 */
}
}
} /* BFSA */
當選擇鄰接表作為圖的存儲結構時，圖337(a)所示的連通圖G的廣度優先搜索遍歷算法BFSL描述如下：
#define VTXUNM n
void BFSL(struct headnode G［］, int v)
struct headnode G［VIXUNM 1］;
int Visited［VIXUNM 1］;
{
int queue［VTXUNM］;
int rear=-1; front=-1; /* queue置為空隊 */
int i;
ARCNODE *p;
printf(''%d-'', G［v］.vexdata);
visited［v］=1;
rear ;
queue［rear］=v; /*訪問過的頂點進隊列*/
while (rear!=front)
{
front ;
v=queue［front］;
p=G［v］.firstarc;
while(p!=NULL) {
if (visited［p-adjvex］==0) {
printf(''%d-'', G［p-adjvex］.vexdata);
visited［p-adjvex］=1;
rear ;
queue［rear］=p-adjvex;
}
p=p-nextarc;
}
}
} /* BFSL */
對于有n個頂點和e條邊的連通圖，BFSA算法的while循環和for循環都需執行n次，所以BFSA算法的時間復雜度為O(n2)，同時BFSA算法使用了兩個長度均為n的隊列和輔助標志數組，所以空間復雜度為O(n)； BFSL算法的外while循環要執行n次，而內while循環執行次數總計是邊表結點的總個數2e，所以BFSL算法的時間復雜度為O(n 2e)； 同時，BFSL算法也使用了兩個長度均為n的隊列和輔助標志數組，所以空間復雜度為O(n)。3.6.4圖的應用1. 生成樹和最小生成樹
圖論中，樹是指一個無回路存在的連通圖。一個連通圖G的生成樹指的是一個包含了G的所有頂點的樹。對于一個有n個頂點的連通圖G，其生成樹包含了n-1條邊，從而生成樹是G的一個極小連通的子圖。所謂極小指該子圖具有連通所需的最小邊數，若去掉一條邊，該子圖就變成了非連通圖； 若任意增加一條邊，該子圖就有回路產生。當給定一個無向連通圖G后，可以從G的任意頂點出發，作一次深度優先搜索或廣度優先搜索來訪問G中的n個頂點，并將順次訪問的兩個頂點之間的路徑記錄下來。這樣，G中的n個頂點和從初始點出發順次訪問余下的n-1個頂點所經過的n-1條邊就構成了G的極小連通子圖，也就是G的一棵生成樹。通常，將深度優先搜索得到的生成樹稱為深度優先搜索生成樹，簡稱為DFS生成樹； 而將廣度優先搜索得到的生成樹稱為廣度優先搜索生成樹，簡稱為BFS生成樹。對于前面所給的DFSA和BFSA算法，只需在if語句中的DFSA調用語句前或if語句中加入將(vi, vj)打印出來的語句，即構成相應的生成樹算法。連通圖的生成樹不是唯一的，它取決于遍歷方法和遍歷的起始頂點。遍歷方法確定后，從不同的頂點出發進行遍歷，可以得到不同的生成樹。對于非連通圖，每個連通分量中的頂點集和遍歷時走過的邊一起構成一棵生成樹，這些連通分量的生成樹組成非連通圖的生成森林。算法實現時，可通過多次調用由DFSA或BFSA構成的生成樹算法求出非連通圖中各連通分量對應的生成樹，這些生成樹構成了非連通圖的生成森林。使用DFSA構成的生成樹算法和BFSA構成的生成樹算法，對圖337(a)所示連通圖G從頂點1開始進行遍歷得到的深度優先生成樹和廣度優先生成樹分別如圖338(a)、(b)所示。
圖338G從V1出發的兩種生成樹
圖339所示為G(圖333(a))的深度優先生成森林，它由3棵深度優先生成樹組成。
圖339圖G的深度優先生成森林
對一個連通網絡構造生成樹時，可以得到一個帶權的生成樹。把生成樹各邊的權值總和作為生成樹的權，而具有最小權值的生成樹構成了連通網絡的最小生成樹。也就是說，構造最小生成樹就是在給定n個頂點所對應的權矩陣(代價矩陣)的條件下，給出代價最小的生成樹。最小生成樹的構造有實際應用價值。例如，要在n個城市之間建立通信網絡，則連通n個城市只需n-1條線路。若以n個城市做圖的頂點，n-1條線路做圖的邊，則該圖的生成樹就是可行的建造方案。而不同城市之間建立通信線路需要一定的花費(相當于邊上的權)，所以對n個頂點的連通網可以建立許多不同的生成樹，每棵生成樹都可以是一個通信網，當然希望選擇一個總耗費最小的生成樹，即最小代價生成樹。例如，圖340(a)是個連通網，它的最小生成樹如圖340(b)所示。
圖340連通網及其最小生成樹
構造最小生成樹的算法有多種，大多數算法都利用了最小生成樹的一個性質，簡稱為MST性質。MST性質指出，假設G=(V, E)是一個連通網絡，U是V中的一個真子集，若存在頂點u∈U和頂點v∈V-U的邊(u, v)是一條具有最小權的邊，則必存在G的一棵最小生成樹包括這條邊(u, v)。
圖341含有(u,v)的回路
MST性質可用反證法加以證明，假設G中的任何一棵最小生成樹T都不包含(u, v)，其中u∈U和v∈V-U。由于T是最小生成樹，所以必然有一條邊(u′, v′)(其中u′∈U和v′∈V-U)連接兩個頂點集U和V-U。當(u, v)加入到T中時，T中必然存在一條包含了(u, v)的回路，如圖341所示。如果在T中保留(u, v)，去掉(u′, v′)，則得到另一棵生成樹T′。因為(u, v)的權小于(u′, v′)的權，故T′的權小于T的權，這與假設矛盾，因此MST性質得證。
下面介紹構造最小生成樹的兩種常用算法，Prim(普里姆)算法和Kruskal(克魯斯卡爾)算法。1) Prim算法設G(V, E)是有n個頂點的連通網絡，T=(U, TE)是要構造的生成樹，初始時U={Φ}，TE={Φ}。首先，從V中取出一個頂點u0放入生成樹的頂點集U中作為第一個頂點，此時T=({u0}, {Φ})； 然后從u∈U，v∈V-U的邊(u, v)中找一條代價最小的邊(u*,v*)，將其放入TE中并將v*放入U中，此時T=({u0, v*}, {(u0, v*)})； 繼續從u∈U, v∈V-U的邊(u, v)中找一條代價最小的邊(u*, v*)，將其放入TE中并將v*放入U中，直到U=V為止。這時T的TE中必有n-1條邊，構成所要構造的最小生成樹。顯然，Prim算法的關鍵是如何找到連接U和V-U的最短邊(代價最小邊)來擴充T。設當前生成樹T中已有k個頂點，則U和V-U中可能存在的邊數最多為k(n-k)條，在如此多的邊中尋找一條代價最小的邊是困難的。注意在相鄰的尋找最小代價的邊的過程中，有些操作具有重復性，所以可通過將前一次尋找所得到的最小邊存儲起來，然后與新找到的邊進行比較，如果新找到的邊比原來已找到的邊短，則用新找到的邊代替原有的邊，否則保持不變。為此設立以下邊的存儲結構。
typedef struct {
int fromvex, endvex;/* 邊的起點和終點 */
float length; /* 邊的權值 */
} edge;
edge T［n-1］;
float dist［n］［n］; /* 連通網絡的帶權鄰接矩陣 */
相應的Prim算法描述如下：
Prim(int i)
{/* i給出選取的第一個頂點的下標，最終結果保存在T［n-1］數組中 */
int j, k, m, v, min, max=100000;
float d;
edge e;
v=i; /* 將選定頂點送入中間變量 */
for(j=0; j=n-2; j )
{/* 構造第一個頂點 */
T［j］.fromvex=v;
if(j=v)
{
T［j］.endvex=j 1;
T［j］.length=dist［v］［j 1］; }
else
{
T［j］.endvex=j;
T［j］.length=dist［v］［j］; }
}
for(k=0; kn-1; k ) { /* 求第k條邊 */
min=max;
for(j=k; jn-1; j ) /* 找出最短的邊并將最短邊的下標記錄在m中 */
if(T［j］.lengthmin) {
min=T［j］.length;
m=j; }
e=T［m］; T［m］=T［k］; T［k］=e; /* 將最短的邊交換到T［k］單元 */
v=T［k］.endvex; /* v中存放新找到的最短邊在V-U中的頂點*/
for(j=k 1; jn-1; j )
{/* 修改所存儲的最小邊集 */
d=dist［v］［T［j］.endvex］;
if(dT［j］.length)
{
T［j］.length=d;
T［j］.fromvex=v; }
}
}
} /* Prim */
以上算法中構造第一個頂點所需的時間是O(n)，求k條邊的時間大約是∑n－2k=0(∑n－2j=kO(1) ∑n－2j=k 1O(1))≈2∑n－2k=0∑n－2j=kO(1)(35)其中，O(1)表示某一正常數C，所以上述公式的時間復雜度是O(n2)。下面結合圖342所示的例子來觀察算法（34）的工作過程。設選定的第一個頂點為2。首先將頂點值2寫入T［i］.fromvex，并將其余頂點值寫入相應的T［i］.endvex，然后從dist矩陣中取出第2行寫入相應的T［i］.length中，得到圖343(a)； 在該圖中找出具有最小權值的邊(2, 1)，將其交換到下標值為0的單元中，然后從dist矩陣中取出第1行的權值與相應的T［i］.length作比較，若取出的權值小于相應的T［i］.length，則進行替換，否則保持不變。由于邊(2, 0)和(2, 5)的權值大于邊(1, 0)和(1, 5)的權值，進行相應的替換可得到圖343(b)； 在該圖中找出具有最小權值的邊(2, 3)，將其交換到下標值為1的單元中，然后從dist矩陣中取出第3行的權值與相應的T［i］.length作比較，可見邊(3, 4)的權值小于邊(2, 4)的權值，故進行相應的替換得到圖343(c)； 在該圖中找出具有最小權值的邊(1, 0)，因其已在下標為2的單元中，故交換后仍然保持不變，然后從dist矩陣中取出第0行的權值與相應的T［i］.length作比較，可見邊(0, 4)和(0, 5)的權值大于邊(3, 4)和(1, 5)的權值，故不進行替換，得到圖343(d)； 在該圖中找出具有最小權值的邊(1, 5)，將其交換到下標值為3的單元中，然后從dist矩陣中取出第5行的權值與相應的T［i］.length作比較； 因邊(5, 4)的權值大于邊(3, 4)的權值，故不替換，得到圖343(e)。至此整個算法結束，得出了如圖343(f)所示的最小生成樹。
圖342一個網絡及其鄰接矩陣
圖343T數組變化情況及最小生成樹
2) Kruskal算法Kruskal算法是從另一條途徑來求網絡的最小生成樹。設G=(V, E)是一個有n個頂點的連通圖，令最小生成樹的初值狀態為只有n個頂點而無任何邊的非連通圖T=(V, {Φ})，此時圖中每個頂點自成一個連通分量。按照權值遞增的順序依次選擇E中的邊，若該邊依附于T中兩個不同的連通分量，則將此邊加入TE中，否則舍去此邊而選擇下一條代價最小的邊，直到T中所有頂點都在同一連通分量上為止。這時的T便是G的一棵最小生成樹。對于圖343所示的網絡，按Kruskal算法構造最小生成樹的過程如圖344所示。
圖344Kruskal算法構造最小生成樹的過程
圖344(c)中選擇最短邊(2, 3)時，也可以選擇邊(1, 3)，這樣所構造出的最小生成樹是不同的，即最小生成樹的形式不唯一，但權值的總和相同。選擇了最短邊(2, 3)之后，在圖344(d)中首先選擇邊(1, 3)，因其頂點在同一分量上，故舍去這條邊而選擇下一條代價最小的邊。在圖344(f)中也首先選擇邊(3, 5)，但因頂點3和5在同一個分量上，故舍去此邊而選擇下一條代價最小邊(3, 4)。Kruskal算法中，每次都要選擇所有邊中最短的邊，若用鄰接矩陣實現，則每找一條最短的邊就需要對整個鄰接矩陣掃描一遍。這樣，整個算法復雜度太高，而使用鄰接表時，由于每條邊都被連接兩次，這也使尋找最短邊的計算時間加倍，所以采用以下的存儲結構來對圖中的邊進行表示。
typedef struct {
int fromvex, endvex;/* 邊的起點和終點 */
float length; /* 邊的權值 */
int sign; /* 該邊是否已選擇過的標志信息 */
} edge;
edge T［e］; /* e為圖中的邊數 */
int G［n］; /* 判斷該邊的兩個頂點是不是在同一個分量上的數組，n為頂點數 */
Kruskal算法中，如何判定所選擇的邊是否在同一個分量上，是整個算法的關鍵和難點。為此，設置一個G數組，利用G數組的每一個單元中存放一個頂點信息的特性，通過判斷兩個頂點對應單元的信息是否相同來判定所選擇的邊是否在同一個分量上。具體算法如下：
Kruskal(int n, int e)
{/* n表示圖中的頂點數目，e表示圖中的邊數目 */
int i, j, k, l, min, t;
for(i=0; i=n-1; i ) /* 數組G置初值 */
G［i］=i;
for(i=0; i=e-1; i ) { /* 輸入邊信息 */
scanf("%d%d%f", &T［i］.fromvex, &T［i］.endvex, &T［i］.length);
T［i］.sign=0; }
j=0;
while(jn-1)
{
min=1000;
for(i=0; i=e-1; i )
{ /* 尋找最短邊 */
if(T［i］.sign==0)
if(T［i］.lengthmin)
{
k=T［i］.fromvex;
l=T［i］.endvex;
T［i］.sign=l; }
if(G［k］==G［l］) T［i］.sign=2; /* 在同一分量上舍去 */
else {
j ;
for(t=0; tn; t ) /* 將最短邊的兩個頂點并入同一分量 */
if(G［t］==l) G［t］=k; }
}
}
} /* Kruskal */
如果邊的信息是按權值從小到大依次存儲到T數組中，則Kruskal算法的時間復雜度約為O(e)。一般情況下，Kruskal算法的時間復雜度約為O(elge)，與網中的邊數有關，故適合于求邊稀疏網絡的最小生成樹； 而Prim算法的時間復雜度為O(n2)，與網中的邊數無關，適合于邊稠密網絡的最小生成樹。2. 最短路徑一個實際的交通網絡在計算機中可用圖的結構來表示。這類問題中經常考慮的問題有兩個，一是兩個頂點之間是否存在路徑； 二是在有多條路徑的條件下，哪條路徑最短。由于交通網絡中的運輸路線往往有方向性，因此將以有向網絡進行討論，無向網絡的情況與此相似。討論中，習慣上稱路徑的開始點為源點(Source)，路徑的最后一個頂點為終點(Destination)，而最短路徑意味著沿路徑的各邊權值之和為最小。求最短路徑時，為方便起見，規定鄰接矩陣中某一頂點到自身的權值為0，即當i=j時，dist［i］［j］=0。最短路徑問題的研究分為兩種情況，一是從某個源點到其余各頂點的最短路徑； 二是每一對頂點之間的最短路徑。1) 從某個源點到其余各頂點的最短路徑迪杰斯特拉(Dijkstra)通過對大量的圖中某個源點到其余頂點的最短路徑的頂點構成集合和路徑長度之間關系的研究發現，若按長度遞增的次序來產生源點到其余頂點的最短路徑，則當前正要生成的最短路徑除終點外，其余頂點的最短路徑已生成，即設A為源點，U為已求得的最短路徑的終點的集合(初態時為空集)，則下一條長度較長的最短路徑(設它的終點為X)或者是弧(A, X)或者是中間只經過U集合中的頂點，最后到達X的路徑。例如，在圖345中要生成從F點到其他頂點的最短路徑。首先應找到最短的路徑F→B，然后找到最短的路徑F→B→C。這里除終點C以外，其余頂點的最短路徑F→B已生成。迪杰斯特拉提出的按路徑長度遞增次序來產生源點到各頂點的最短路徑的算法思想是，對有n個頂點的有向連通網絡G=(V, E)，首先從V中取出源點u0放入最短路徑頂點集合U中，這時的最短路徑網絡S=({u0}, {}); 然后從u∈U和v∈V－U中找一條代價最小的邊(u*, v*)加入到S中,此時S=({u0, v*}, {(u0, v*)})。每往U中增加一個頂點，都需要對V－U中各頂點的權值進行一次修正。如果加進v*作為中間頂點，使得從u0到其他屬于V－U的頂點vi的路徑比不加v*時最短，則修改u0到vi的權值，即以(u0, v*)的權值加上(v*, vi )的權值來代替原(u0, vi )的權值，否則不修改u0到vi的權值。接著再從權值修正后的V－U中選擇最短的邊加入S中，如此反復，直到U=V為止。
圖345有向網絡G和F到其他頂點的最短距離
圖346Dijkstra算法求最短路徑示例
對圖345中的有向網絡按以上算法思想處理，所求得的從源點F到其余頂點的最短路徑的過程如圖346所示。其中，單圓圈表示U中的頂點，而雙圓圈表示V－U中的頂點。連接U中兩個頂點的有向邊用實線表示，連接U和V－U中兩個頂點的有向邊用虛線表示。圓圈旁的數字為源點到該頂點當前的距離值。初始時，S中只有一個源點F，它到V－U中各頂點的路徑如圖346(a)所示； 選擇圖346(a)中最小代價邊(F, B)，同時由于路徑(F, A)大于(F, B, A)和(F, C)大于(F, B, C)，進行相應調整可得到圖346(b)； 選擇圖346(b)中的最小代價邊(B, C)，同時由于(F, B, A)大于(F, B, C, A)，進行相應調整可得到圖346(c)； 選擇圖346(c)中最小代價邊(C, A)即可得到圖346(d)； 選擇圖346(d)中最小代價邊(F, D) 即可得到圖346(e)D; 最后選擇(F, E)即可得到圖346(f)。計算機上實現此算法時，需要設置一個用于存放源點到其他頂點的最短距離數組D［n］，以便于從其中找出最短路徑; 因為不僅希望得到最短路徑長度，而且也希望能給出最短路徑具體經過那些頂點的信息，所以設置一個路徑數組p［n］，其中p［i］表示從源點到達頂點i時，頂點i的前趨頂點； 為了防止對已經生成的最短路徑進行重復操作，使用一個標識數組s［n］來記錄最短路徑生成情況，若s［i］=1表示源點到頂點i的最短路徑已產生，而s［i］=0表示最短路徑還未產生。當頂點A, B, C, D, E, F對應標號0, 1, 2, 3，4, 5時，具體算法描述如下：
float D［n］;
int p［n］, s［n］;
Dijkstra(int v, float dist［］［］)/* 求源點v到其余頂點的最短路徑及長度 */
{int i, j, k, v1, min, max=10000, pre; /* Max中的值用以表示dist矩陣中的值∞ */
v1=v;
for( i=0; in; i ) /* 各數組進行初始化 */
{D［i］=dist［v1］［i］;
if( D［i］ != max )p［i］= v1 1;
else p［i］=0;
s［i］=0;
}
s［v1］=1; /* 將源點送U */
for( i=0; in-1; i ) /* 求源點到其余頂點的最短距離 */
{min=10001; /* minmax,以保證值為∞的頂點也能加入U*/
for( j=0; jn-1; j )
if ( ( !s［j］ )&&(D［j］min) ) /* 找出到源點具有最短距離的邊 */
{min=D［j］;
k=j;
}
s［k］=1; /* 將找到的頂點k送入U */
for(j=0; jn; j )
if ( (!s［j］)&&(D［j］D［k］ dist［k］［j］) ) /* 調整V－U中各頂點的距離值 */
{D［j］=D［k］ dist［k］［j］;
p［j］=k 1; /* k是j的前趨 */
}
} /* 所有頂點已擴充到U中 */
for( i=0; in; i )
{printf(" %f %d ", D［i］, i);
pre=p［i］;
while ((pre!=0)&&(pre!=v 1))
{printf (" －%d ", pre-1);
pre=p［pre-1］;
}
printf(" －%d ", v);
}
} /* Dijkstra */
對圖345中的有向網絡G，以F點為源點，執行上述算法時,D、p、s數組的變化狀況如表31所示。
表31Dijkstra算法動態執行情況
循環UkD［0］,…, D［5］p［0］,…, p［5］s［0］,…, s［5］初始化{F}--24 5 max 25 max 06 6 0 6 0 60 0 0 0 0 11{F, B}123 5 12 25 max 02 6 2 6 0 60 1 0 0 0 12{F,B,C}221 5 12 25 max 03 6 2 6 0 60 1 1 0 0 13{F,B,C,A}021 5 12 25 max 03 6 2 6 0 61 1 1 0 0 14{F,B,C,A,D}321 5 12 25 max 03 6 2 6 0 61 1 1 1 0 15{F,B,C,A,D,E}421 5 12 25 max 03 6 2 6 0 61 1 1 1 1 1
打印輸出的結果為
210← 2← 1← 5
51← 5
122← 1← 5
253← 5
100004← 5
05← 5
Dijkstra算法的時間復雜度為O(n2)，占用的輔助空間是O(n)。
2) 每一對頂點之間的最短路徑求一個有n個頂點的有向網絡G=(V, E)中的每一對頂點之間的最短路徑，可以依次把有向網絡的每個頂點作為源點，重復執行n次Dijkstra算法，從而得到每對頂點之間的最短路徑。這種方法的時間復雜度為O(n3)。弗洛伊德(Floyd)于1962年提出了解決這一問題的另一種算法，它形式比較簡單，易于理解，而時間復雜度同樣為O(n3)。Floyd算法根據給定有向網絡的鄰接矩陣dist［n］［n］求頂點vi到頂點vj的最短路徑。這一算法的基本思想是假設vi和vj之間存在一條路徑，但這并不一定是最短路徑，試著在vi和vj之間增加一個中間頂點vk。若增加vk后的路徑(vi, vk, vj) 比(vi, vj)短，則以新的路徑代替原路徑，并且修改dist［i］［j］的值為新路徑的權值； 若增加vk后的路徑比(vi, vj)更長，則維持dist［i］［j］不變。在修改后的dist矩陣中，另選一個頂點作為中間頂點，重復以上操作，直到除vi和vj頂點的其余頂點都做過中間頂點為止。對初始的鄰接矩陣dist［n］［n］，依次以頂點v1, v2, …, vn為中間頂點實施以上操作時，將遞推地產生出一個矩陣序列dist(k)［n］［n］(k=0, 1, 2, …, n)。這里初始鄰接矩陣dist［n］［n］看作dist(0)［n］［n］，它給出每一對頂點之間的直接路徑的權值; dist(k)［n］［n］(1≤kint path［n］［n］;/* 路徑矩陣 */
Floyd(float A［ ］［n］, dist［ ］［n］) /* A是路徑長度矩陣, dist是有向網絡G的帶權鄰接矩陣 */
{int i, j, k, next, max=10000;
for (i=0; in; i ) /* 設置A和path的初值 */
for (j=0; jn; j )
{if (dist［i］［j］ !=max )path［i］［j］=i 1; /* i是j的前趨 */
else path［i］［j］=0;
A［i］［j］=dist［i］［j］;
}
for (k=0; kn; k ) /* 以0, 1, …, n-1為中間頂點執行n次 */
for (i=0; in; i )
for (j=0; jn; j )
if (A［i］［j］(A［i］［k］ A［k］［j］))
{A［i］［j］=A［i］［k］ A［k］［j］; /* 修改路徑長度 */
path［i］［j］=path［k］［j］; /* 修改路徑 */
}
for (i=0; in; i ) /* 輸出所有頂點對i, j之間最短路徑的長度和路徑 */
for (j=0; jn; j )
{printf ( " %f%d ", A［i］［j］, j);
pre=path［i］［j］;
while ((pre!=0)&&(pre!=i 1)) {
printf ("-%d ", pre-1);
pre=path［i］［pre-1］;
}
printf ("-%d＼n ", i);
}
} /* Floyd */
對圖345中的有向網絡G執行以上算法，矩陣A和path的變化狀況如下所示。A(0)=06∞810000∞1807∞∞109∞015∞∞∞∞120∞∞∞∞4∞0∞245∞25∞0path(0)=110100222002303300004400005050660606
A(1)=06∞8∞∞180726∞10915015∞∞∞∞120∞∞∞∞4∞0∞245∞25∞0path(1)=110100222102313300004400005050660606
A(2)=06138∞16180726∞10915015∞25∞∞120∞∞∞∞4∞0∞2351225∞0path(2)=112102
222102
313302
004400
005050
262606
A(3)=061381000016160722∞10915015∞252127120∞3713194190292151225∞0path(3)=112102322302313302314402315352362606
A(4)=06138∞16160722∞10915015∞252127120∞3713194190292151225∞0
path(4)=112102322302313302314402315352362606
由于A(4)=A(5)=A(6)和path(4)=path(5)=path(6)，所以表中省略了A(5), A(6)和path(5), path(6)，打印輸出的結果為
00←0
61←0
132←1←0
83←0
100004←0
165←1←0
……
253←5
100004←5
05←5
3. AOV網與拓撲排序現實世界中，很多問題都由一系列的有序活動而構成。例如，一個工程項目的開展、一種產品的生產過程或大學期間所學專業的系列課程學習。這些活動可以是一個工程項目中的子工程、一種產品生產過程中的零部件生產或專業課程學習中的某一門課程。所有這些按一定順序展開的活動，可以使用有向圖表示。其中，頂點表示活動，頂點之間的有向邊表示活動之間的先后關系，這種有向圖稱為頂點表示活動網絡(Activity On Vertex network，簡稱AOV網)。AOV網中的頂點可以帶有權值，該權值可以表示一項
圖347表示課程先后關系的AOV網
活動完成所需要的時間或所需要投入的費用。AOV網中的有向邊表示了活動之間的制約關系。例如，大學本科專業的學生必須學完一系列的課程才能畢業，其中一部分課程是基礎課，無須先修其他課程便可學習； 另一部分課程則要求必須學完相關的基礎先修課程后，才能進行學習。上述課程和課程之間關系的一個抽象表示示例如表32所示。該示例也可以用圖347的AOV網表示，這里有向邊＜Ci , Cj＞表示了課程Ci是課程Cj的先修課程。
表32專業課程設置及其關系
課程代號課程名稱先修課程課程代號課程名稱先修課程C1課程1無C7課程7C3,C5C2課程2C1C8課程8C3,C6C3課程3C1,C2C9課程9無
C4課程4C1C10課程10C9
續表
課程代號課程名稱先修課程課程代號課程名稱先修課程C5課程5C3,C4C11課程11C9C6課程6C11C12課程12C1,C9,C10
當限制各個活動只能串行進行時，如果可以將AOV網中的所有頂點排列成一個線性序列vi1, vi2, …, vin； 并且這個序列同時滿足如果在AOV網中從頂點vi到頂點vj存在一條路徑，則在線性序列中vi必在vj之前，就稱這個線性序列為拓撲序列。把對AOV網構造拓撲序列的操作稱為拓撲排序。AOV網的拓撲排序序列給出了各個活動按順序完成的一種可行方案，但并非任何AOV網的頂點都可排成拓撲序列。當AOV網中存在有向環時，就無法得到該網的拓撲序列。對于實際問題，AOV網中存在的有向環就意味著某些活動是以自己為先決條件，這顯然不合理。例如，對于程序的數據流圖，AOV網中存在環就意味著程序存在一個死循環。任何一個無環的AOV網中的所有頂點都可排列在一個拓撲序列里，拓撲排序的基本操作如表32所示。(1)從網中選擇一個入度為0的頂點并且將其輸出。(2)從網中刪除此頂點及所有由它發出的邊。(3)重復上述兩步，直到網中再沒有入度為0的頂點為止。以上操作會產生兩種結果，一種結果是網中的全部頂點都被輸出，整個拓撲排序完成； 另一種結果是網中頂點未被全部輸出，剩余頂點的入度均不為0，此時說明網中存在有向環。用以上操作對圖347的AOV網拓撲排序的過程如圖348所示。這里得到了一種拓撲序列C1, C2 , C3, C4, C5, C7, C9, C10, C12, C11, C6, C8。
圖348AOV網拓撲排序過程
從構造拓撲序列的過程中可以看出，許多情況下，入度為0的頂點可能有多個，這樣就可以給出多種拓撲序列。若按所給出的拓撲序列順序進行課程學習，可保證在學習任一門課程時，這門課程的先修課程已經學過。
拓撲排序可在有向圖的不同存儲結構表示方法上實現。下面針對圖349(a)所給出的AOV網進行討論。
圖349AOV網G及其鄰接表
鄰接矩陣存儲結構中，由于某個頂點的入度由這個頂點相對應列上的1的個數所確定，而它的出度由頂點所對應行上的1的個數所確定，所以在這種存儲結構上實現拓撲排序算法的步驟是(1) 取1作為第一個序號。(2) 找一個還沒有獲得序號的全零元素的矩陣列，若沒有則停止尋找。此時，如果矩陣中所有列都已獲得了序號，則拓撲排序完成； 否則，說明該有向圖中有環存在。(3) 把序號值賦給找到的列，并將該列對應的頂點輸出。(4) 將找到列所對應的行中所有為1的元素清零。(5) 序號值增1，重復執行步驟(2)~(5)。
根據以上步驟，使用一個長度為n的數組來存放序號值時，可以給出如下的實現算法。
TOPOSORTA(graph *g，int n) /*對有n個頂點的有向圖，使用鄰接矩陣求拓撲排序*/
{int i, j, k, t, v, D［n］=0;
v=1; /* 序號變量置1 */
for (k=0; kn; k ) {
for (j=0; jn; j ) /*尋找全零列*/
if (D［j］= =0) {
t=1;
for (i=0; in; i )
if (g－arcs［i］［j］= =1) {
t=0;
break;
} /* 若第j列上有1，則跳出循環 */
if (t= =1) {
m=j;
break;
} /*找到第j列為全0列*/
}
if ( j!=n ) {
D［m］=v; /* 將新序號賦給找到的列 */
printf (" %d＼t ", g－vexs［m］); /* 將排序結果輸出 */
for (i=0; in; i )
g－arcs［m］［i］=0; /*將找到的列的相應行置全0*/
v ; /*新序號增1*/
}
else break;
}
if( v－1n ) printf (" ＼n The network has a cycle ＼n ");
} /* TOPOSORTA */
圖349中G的鄰接矩陣應用以上算法得到的拓撲排序序列為v1,v2, v4, v3, v5, v6, v7。利用鄰接矩陣進行拓撲排序時，程序雖然簡單，但效率不高，算法的時間復雜度約為O(n3)。 而利用鄰接表使尋找頂點入度為0的操作簡化，從而提高拓撲排序算法的效率。鄰接表存儲結構中，為了便于檢查每個頂點的入度，可在頂點表中增加一個入度域(id)。此時，只需要對由n個元素構成的頂點表進行檢查就能找出入度為0的頂點。為避免對每個入度為0的頂點重復訪問，可用一個鏈棧來存儲所有入度為0的頂點。進行拓撲排序前，只要對頂點表進行一次掃描，便可將所有入度為0的頂點都入棧。以后，每次從棧頂取出入度為0的頂點，并將其輸出即可。一旦排序過程中出現了新的入度為0的頂點，同樣又將其入棧。入度為0的頂點出棧后，根據頂點的序號找到相應的頂點和以該頂點為起點的出邊，再根據出邊上的鄰接點域的值使相應頂點的入度值減1，便完成了刪除所找到的入度為0的頂點的出邊的功能。鄰接表存儲結構中實現拓撲排序算法的步驟為(1) 掃描頂點表，將入度為0的頂點入棧。(2) 當棧非空時執行以下操作： ① 將棧頂頂點vi的序號彈出，并輸出之； ② 檢查vi的出邊表，將每條出邊表鄰接點域所對應的頂點的入度域值減1，若該頂點入度為0，則將其入棧。(3) 若輸出的頂點數小于n，則輸出有回路，否則拓撲排序正常結束。具體實現時，鏈棧無須占用額外空間，只需利用頂點表中入度域值為0的入度域來存放鏈棧的指針（即指向下一個存放鏈棧指針的單元的下標），并用一個棧頂指針top指向該鏈棧的頂部即可。由此給出以下的具體算法。
typedef int datetype;
typedef int vextype;
typedef struct node {
int adjvex; /* 鄰接點域 */
struct node *next; /* 鏈域 */
} edgenode; /* 邊表結點 */
typedef struct {
vextype vertex; /*頂點信息 */
int id; /*入度域 */
edgenode *link; /* 邊表頭指針 */
} vexnode; /*頂點表結點*/
vexnode ga［n］;
TOPOSORTB(vexnode ga［ ］) { /* AOV網的鄰接表 */
{int i, j, k, m=0, top=－1; /* m為輸出頂點個數計數器，top為棧指針 */
edgenode *p;
for (i=0; in; i ) /* 初始化，建立入度為0的頂點鏈棧 */
if (ga［i］.id= =0) {
ga［i］.id=top;
top=i;
}
while( top!=－1 ) { /* 棧非空執行排序操作 */
j=top;
top=ga［top］.id; /* 第j 1個頂點退棧 */
printf (" %d＼t ", ga［j］.vertex); /* 輸出退棧頂點 */
m ; /* 輸出頂點計數 */
p=ga［j］.link;
while(p) { /* 刪去所有以vj 1為起點的出邊 */
k=p－adjvex－1;
ga［k］.id--; /* vk 1入度減1 */
if (ga［k］.id= =0) { /*將入度為0的頂點入棧*/
ga［k］.id=top;
top=k;
}
p=p－next; /* 找vj 1的下一條邊 */
}
}
if (mn) /* 輸出頂點數小于n，有回路存在 */
printf (" ＼n The network has a cycle＼n ");
} /* TOPOSORTB */
對于圖349中的鄰接表執行以上算法時，入度域的變化情況如圖350所示。這時得到的拓撲序列為v4, v5, v1, v3, v2, v7, v6。
圖350排序過程中入度域變化示例
對一個具有n個頂點，e條邊的AOV網來說，初始化部分執行時間是O(n)； 排序中，若AOV網無回路，則每個頂點入棧和出棧各一次，每個邊表結點檢查一次，執行時間為O(n e)，故總的算法時間復雜度為O(n e)。
3.7小結本章介紹了兩種非線性的數據結構——樹和圖。樹在存儲結構中占據非常重要的地位，在樹形結構中樹是一種具有層次特征的數據結構，二叉樹是一種非常重要、簡單、典型的數據結構。二叉樹的5個性質揭示了二叉樹的主要特征。二叉樹的存儲結構有順序存儲結構和鏈式存儲結構兩種。采用順序存儲結構可能會浪費大量的空間，因此常常利用順序存儲結構存儲滿二叉樹和完全二叉樹，而一般二叉樹大多采用鏈式存儲結構。二叉樹的遍歷是對二叉樹進行各種操作的基礎，無論遞歸算法還是非遞歸算法都要很好掌握。二叉樹的遍歷是一種常用的操作。二叉樹的遍歷分為先序遍歷、中序遍歷和后序遍歷。二叉樹的遍歷過程就是將二叉樹這種非線性結構轉換成線性結構。樹和森林的存儲有多種方法，和二叉樹一樣，對樹和森林的遍歷是對樹結構操作的基礎，通常有先根和后根兩種遍歷方法，分別對應于二叉樹的先序和中序遍歷，所以能利用二叉樹的遍歷來實現。樹、森林和二叉樹可以相互轉化，樹實現起來不是很方便，實際應用中，可以將問題轉化為二叉樹的相關問題加以實現。哈夫曼樹是n個帶權葉子結點構成的帶權路徑長度最短的二叉樹。哈夫曼樹是二叉樹的應用之一，要掌握哈夫曼樹的建立方法及哈夫曼編碼生成算法，值得注意的是哈夫曼樹通常采用靜態鏈式存儲結構。圖的存儲結構有4種，分別是鄰接矩陣存儲結構、鄰接表存儲結構、十字鏈表存儲結構和鄰接多重表存儲結構。其中，最常用的是鄰接矩陣存儲和鄰接表存儲。圖的遍歷分為兩種，分別是廣度優先遍歷和深度優先遍歷。圖的廣度優先遍歷類似于樹的層次遍歷，圖的深度優先遍歷類似于樹的先根遍歷。構造最小生成樹的算法主要有兩個，分別是普里姆算法和克魯斯卡爾算法。最短路徑是一個與實際關系密切的，最短路徑表示完成工程的最短工期，通常用圖的頂點表示事件，弧表示活動，權值表示活動的持續時間。樹和圖是數據結構中的難點，學好樹和圖的第一步就是要搞清楚樹和圖中的一些概念，然后多看算法，耐心研究算法，從多方面認真學習樹和圖。3.8習題1. 單項選擇題
(1) 樹形結構的特點是任意一個結點（）。
A. 可以有多個直接前趨B. 可以有多個直接后繼C. 至少有1個前趨D. 只有一個后繼(2) 將一棵有100個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根結點編號為1，則編號為49的結點的左孩子的編號為（）。A. 98B. 99C. 50D. 48(3) 對具有100個結點的二叉樹，若用二叉鏈表存儲，則其指針域部分用來指向結點的左、右孩子，一共有（）個指針域為空。A. 55B. 99C. 100D. 101(4) 如果T1是由有序樹T轉換來的二叉樹，則T中結點的后序排列是T1結點的（）排列。A. 先序B. 后序C. 中序D. 層序(5) 設有13個值，用它們組成一棵Huffman樹，則該Huffman樹中共有（）個結點。A. 13B. 12C. 26D. 25(6) 若對一棵有20個結點的完全二叉樹按層編號，則編號為5的結點x，它的雙親結點及左孩子結點的編號分別為（）。A. 2,11B. 2,10C. 3,9D. 3,10(7) 將一棵有100個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根結點編號為1，則編號最大的非葉結點的編號為（）。A. 48B. 49C. 50D. 51(8) 在有n個結點的二叉鏈表中，值為非空的鏈域的個數為（）。A. n-1B. 2n-1C. n 1D. 2n 1(9) 由64個結點構成的完全二叉樹，其深度為（）。A. 8B. 7C. 6D. 5(10) 一棵含18個結點的二叉樹的高度至少為（）。
A. 3B. 4C. 5D. 6(11) 在一個無向圖中，所有頂點的度之和等于邊數的（）倍。A. 1/2B. 1C. 2D. 4(12) 在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（）倍。A. 1/2B. 1C. 2D. 4(13) 設有6個頂點的無向圖，該圖至少應有（）條邊，才能確保它是一個連通圖。A. 5B. 6C. 7D. 8(14) 具有5個頂點的無向完全圖共有()條邊。A. 5B. 10C. 15D. 20(15) 對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是（）。A. nB. (n-1)×(n-1)C. n-1D. n×n(16) 對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭向量的大小是（）。A. nB. n 1C. e 1D. e(17) 對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則所有鄰接表中的結點總數是（）。A. e/2B. eC. 2eD. n e(18) 無向圖的鄰接矩陣是一個（）。A. 對稱矩陣B. 零矩陣C. 上三角矩陣D. 對角矩陣(19) 在含n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數為（）。A. eB. 2eC. n2-eD. n2-2e(20) 假設一個有n個頂點和e條弧的有向圖用鄰接表表示，則刪除與某個頂點vi相關的所有弧的時間復雜度是（）。A. O(n)B. O(e)C. O(n e)D. O(n*e)2. 填空題(1) 不考慮順序的3個結點可構成種不同形態的樹，種不同形態的二叉樹。(2) 已知某棵完全二叉樹的第4層有5個結點，則該完全二叉樹葉子結點的總數為。(3) 已知一棵完全二叉樹的第5層有3個結點，其葉子結點數是。(4) 已知一棵完全二叉樹中共有768個結點，則該樹中共有個葉子結點。(5) 一棵具有110個結點的完全二叉樹，若i＝54，則結點i的雙親編號是； 結點i的左孩子結點的編號是，結點i的右孩子結點的編號是。(6) 一棵具有48個結點的完全二叉樹，若i＝20，則結點i的雙親編號是； 結點i的左孩子結點編號是，右孩子結點編號是。(7) 一棵樹T采用二叉鏈表存儲，如果樹T中某結點為葉子結點，則在二叉鏈表BT中所對應的結點一定。(8) 已知在一棵含有n個結點的樹中，只有度為k的分支結點和度為0的葉子結點，則該樹中含有的葉子結點的數目為。(9) 在有n個葉子結點的Huffman樹中，總的結點數是。(10) 圖是一種非線性數據結構，它由兩個集合V(G)和E(G)組成，V(G)是的非空有限集合，E(G)是的有限集合。（11） 在無權圖G的鄰接矩陣A中，若(vi,vj)或＜vi,vj＞屬于圖G的邊集合，則對應元素A［i］［j］等于。（12） 設某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結構，則頂點i和頂點j互為鄰接點的條件是。(13) 圖G有n個頂點和e條邊，以鄰接表形式存儲，進行深度優先搜索的時間復雜度為。（14） 設無向圖G中有n個頂點e條邊，則用鄰接矩陣作為圖的存儲結構進行深度優先或廣度優先遍歷時的時間復雜度為。（15） 具有n個頂點的無向圖，擁有最少的連通分量個數是，擁有最多的連通分量個數是。(16) 圖的遍歷基本方法中是一個遞歸過程。(17) n個頂點的有向圖最多有條弧。(18) n個頂點的無向圖最多有條邊。(19) 在無向圖G的鄰接矩陣A中，若A［i,j］等于1，則A［j,i］等于。(20) 在一個具有n個頂點的無向圖中，要連通全部頂點至少需要條邊。3. 判斷題(1) （）非線性數據結構可以順序存儲，也可以鏈接存儲。(2) （）非線性數據結構只能用鏈接方式才能表示其中數據元素的相互關系。(3) （）完全二叉樹一定是滿二叉樹。(4) （）平衡二叉樹中，任意結點左右子樹的高度差（絕對值）不超過1。(5) （）若一棵二叉樹的任意一個非葉子結點的度為2，則該二叉樹為滿二叉樹。(6) （）度為1的有序樹與度為1的二叉樹等價。(7) （）一棵樹中的葉子結點數一定等于與其對應的二叉樹中的葉子結點數。(8) （）二叉樹的先序遍歷序列中，任意一個結點均排列在其孩子結點的前面。(9) （）若二叉樹的葉子結點數為1，則其先序序列和后序序列一定相反。(10) （）已知一棵二叉樹的先序序列和后序序列，就一定能構造出該二叉樹。(11) （）鄰接表表示法是采用鏈式存儲結構表示圖的一種方法。(12) （）用鄰接表表示圖的方法優于用鄰接矩陣表示圖的方法。(13) （）在邊稀疏的情況下，用鄰接表表示圖要比用鄰接矩陣節省存儲空間。(14) （）用鄰接矩陣方法存儲圖比用鄰接表方法存儲圖更容易確定圖中任意兩個頂點之間是否有邊相連。(15) （）在有向圖中，逆鄰接表表示法是指將原有鄰接表所有數據按相反順序重新排列的一種表示方法。(16) （）在有向圖中，采用逆鄰接表表示法是為了便于確定頂點的入度。(17) （）無向圖的連通分量至少有一個。(18) （）有向圖的強連通分量最多有一個。(19) （）簡單路徑是指圖中所有頂點均不相同而形成的一條路徑。(20) （）簡單回路是指一條起始點和終止點相同的簡單路徑所構成的回路。4. 綜合題(1) 如圖351所示的兩棵二叉樹，分別給出它們的順序存儲結構。
圖351兩棵叉樹
(2) 已知一棵二叉樹的中序、后序序列分別如下： 中序D C E F B H G A K J L I M后序D F E C H G B K L J M I A要求① 畫出該二叉樹；
② 寫出該二叉樹的先序序列。(3) 將圖352所示的樹轉換成二叉樹，并寫出轉換后二叉樹的先序、中序、后序遍歷結果。
圖352樹
(4) 寫出圖353中的二叉樹先序和后序遍歷序列。
圖353二叉樹（1）
(5) 請畫出與圖354所示二叉樹對應的森林。
圖354二叉樹（2）
(6) 從空樹起，依次插入關鍵字40、8、90、15、62、95、12、23、56、32，構造一棵二叉排序樹。要求① 畫出該二叉排序樹；
② 畫出刪去該樹中結點元素值為90之后的二叉排序樹。(7) 輸入一個正整數序列{100，50，302，450，66，200，30，260}，建立一棵二叉排序樹，要求① 畫出該二叉排序樹；
② 畫出刪除結點302后的二叉排序樹。(8) 按給出的一組權值{4，5，7，8，11}，建立一個哈夫曼樹，并計算出該樹的帶權路徑長度WPL。
(9) 給出如圖355所示無向圖的鄰接矩陣和鄰接表。
圖355無向圖(1)
(10) 求出圖356的一棵最小生成樹。
圖356無向圖(2)
(11) 如圖357所示的有向圖，請給出它的① 每個頂點的入度和出度； ② 鄰接矩陣； ③ 鄰接表； ④ 強連通分量。
圖357有向圖(1)
(12) 給出有向圖358的鄰接矩陣、鄰接表形式的存儲結構，并計算出每個頂點的入度和出度。
圖358有向圖(2)
(13) 已知圖359所示，其頂點按a、b、c、d、e、f順序存放在鄰接表的頂點表中，請畫出該圖的鄰接表，使得按此鄰接表進行深度優先遍歷時得到的頂點序列為acbefd，進行廣度優先遍歷時得到的頂點序列為acbdfe。
圖359有向圖(3)
(14) 已知一組數據序列D={d1, d2, …, d9}，其數據間的關系為R={(d1, d3), (d1, d8), (d2, d3), (d2, d4), (d2, d5), (d3, d9), (d5, d6), (d8, d9), (d9, d7), (d4, d7), (d4, d6)}。請畫出此數據序列的邏輯結構圖，并說明該圖屬于哪種結構。(15) 已知數據結構的形式定義為DS={D,S}，其中
D={1,2,3,4}，S=={R}，R={1,2,1,3,2,3,2,4,3,4}
試畫出此結構的圖形表示。(16) 已知圖G的鄰接表如圖360所示，頂點v1為出發點，完成以下要求： ① 寫出按深度優先搜索的頂點序列。② 寫出按廣度優先搜索的頂點序列。
圖360鄰接表（1）
(17) 已知某無向圖的鄰接表存儲結構如圖360所示，要求①畫出此無向圖； ②給出無向圖的鄰接矩陣表示。 (18) 已知一帶權連通圖G=(V,E)的鄰接表如圖361所示。畫出該圖，并分別以BFS和DFS遍歷，寫出遍歷序列，并畫出該圖的一個最小生成樹。示意圖362為表結點的結構圖（以V1為初始點）。
圖361鄰接表（2）
圖362示意圖
新書資訊