資源簡介

第1章 緒論
第2章 線性表
第3章 棧
第4章 隊列
第5章 樹和二叉樹
第6章 圖
第1章 緒論
程序設計就是使用計算機解決現實世界中的實際問題。對于給定的一個實際問題，在進行程序設計時，首先要把實際問題中用到的信息抽象為能夠用計算機表示的數據；第二要把抽象出來的這些數據建立一個數據模型，這個數據模型也稱為邏輯結構，即建立數據的邏輯結構；第三要把邏輯結構中的數據及數據之間的關系存放到計算機中，即建立數據的存儲結構；最后在所建立的存儲結構上實現對數據元素的各種操作，即算法的實現。
本章就是要使大家了解計算機中的數據表示，理解數據元素、邏輯結構、存儲結構和算法的有關概念；掌握基本邏輯結構和常用的存儲方法，能夠選擇合適的數據的邏輯結構和存儲結構；掌握算法及算法的五個重要特性，能夠對算法進行時間復雜度分析，從而選擇一個好的算法，為后面的學習打下良好的基礎。
1.1基本概念和術語
1.數據(data)：
是對客觀事物的符號的表示,是所有能輸入到計算機中并被計算機程序處理的符號的總稱。
2.數據元素(data element):
是數據的基本單位，在計算機程序中通常作為一個整體來處理。一個數據元素由多個數據項（data item）組成，數據項是數據不可分割的最小單位。
3.數據結構(data structure):
是相互之間存在一種或多種特定關系的數據元素的集合。數據結構是一個二元組，記為:
data_structure=(D,S).其中D為數據元素的集合，S是D上關系的集合。
數據元素相互之間的關系稱為結構（structure）。根據數據元素之間關系的不同特性，通常由下列四類基本結構：
（1）集合:數據元素間的關系是同屬一個集合。（圖1）
（2）線性結構:數據元素間存在一對一的關系。（圖2）
（3）樹形結構：結構中的元素間的關系是一對多的關系。（圖3）
（4）圖（網）狀結構：結構中的元素間的關系是多對多的關系。（圖4）
圖1 圖2
圖3 圖4
1.2 數據的邏輯結構和物理結構
1.邏輯結構：數據元素之間存在的關系（邏輯關系）叫數據的邏輯結構。即上面給出的四種結構。
2.物理結構：數據結構在計算機中的表示（映象）叫數據的物理結構，又稱存儲結構。
一種邏輯結構可映象成不同的存儲結構：順序存儲結構和非順序存儲結構（鏈式存儲結構和散列結構）。
1.3算法及算法分析
1. 算法：是對特定問題求解步驟的一種描述，是指令的有限序列。一個算法是一系列將輸入轉換為輸出的計算步驟。
2. 算法的重要特性
①輸入：一個算法應該有零個或多個輸入。
②有窮性：一個算法必須在執行有窮步驟后正常結束，而不能形成無窮循環。
③確定性：算法中的每一條指令必須有確切的含義，不能產生多義性。
④可行性：算法中的每一條指令必須是切實可執行的，即原則上可以通過已經實現的基本運算執行有限次來實現。
⑤輸出：一個算法應該有一個或多個輸出，這些輸出是同輸入有某個特定關系的量。
3. 算法的時間復雜度
①定義：設問題的規模為n，把一個算法的時間耗費T(n)稱為該算法的時間復雜度，它是問題規模為n的函數。
②算法的漸進時間復雜度
設T(n)為一個算法的時間復雜度，如果當n趨向無窮大時T(n)與函數f(n)的比值的極限是一個非零常數M，即記作T(n)=O(f(n))，則稱O(f(n))為算法的漸進時間復雜度，簡稱時間復雜度，也稱T(n)與f(n)的數量級相同，通常，f(n)應該是算法中頻度最大的語句的頻度。
③常用的算法的時間復雜度的順序
O(1)④算法的時間復雜度不僅僅依賴于問題的規模，還與輸入實例的初始狀態有關。
例如：在數組A[0...n-1]中查找給定值K的算法如下：
(1)i=n-1;
(2)while(i>=0&&(A[i]!=k))
(3)?i--;
(4)return i;
此算法中的語句(3)的頻度不僅與問題規模n有關，還與輸入實例中A的各元素取值及K的取值有關：
若A中沒有與K相等的元素，則語句(3)的頻度f(n)=n；
若A的最后一個元素等于K，則語句(3)的頻度f(n)是常數0。
⑤最壞時間復雜度和平均時間復雜度
最壞情況下的時間復雜度稱為最壞時間復雜度。一般不特別說明，討論的時間復雜度均是最壞情況下的時間復雜度。
這樣做的原因是：最壞情況下的時間復雜度是算法在任何輸入實例上運行時間的上界，這就保證了算法的運行時間不會比任何情況下更長。
平均時間復雜度是指所有可能的輸入實例均以等概率出現的情況下，算法的期望運行時間。
例1 求下列交換兩個變量i和j的值的算法的時間復雜度。
(1) i=10;
(2) j=20;
(3) t=i;
(4) i=j;
(5) j=t;
解：各行語句的執行次數均為1，所以該算法的時間耗費T(n)= 1+1+1+1+1=5，該算法的時間耗費T(n)與問題的規模n無關，因此，該算法的時間復雜度T(n)=O(1)。
例2 求兩個n階方陣的乘積C=A×B，其算法如下，計算該時間復雜度。
程序段：
(1) for(i=0; i(2) for(j=0; j(3) {c[i][j]=0;
(4) for(k=0; k(5) c[i][j]+=a[i][k]*b[k][j];
}
解：解法1
計算程序段中的每一行的執行次數。
第(1)行for(i=0; i第(2)行for(j=0; j第(3)行c[i][j]=0;在表達式i第(4)行for(k=0; k第(5)行c[i][j]+=a[i][k]*b[k][j]; 在表達式i因此，各行執行次數分別為：n+1，n（n+1），n2，n2（n+1），n3。
如果用T(n)表示該算法的時間耗費，則
T(n)= n+1+n（n+1）+n2+n2（n+1）+n3=2n3+3n2+2n+1
由此可知，該算法的時間耗費T(n)是矩陣階數n的函數，T(n)=O(n3)。
解法2
只計算執行頻度最高的行。
顯然，在該程序段中，執行頻度最高的行為c[i][j]+=a[i][k]*b[k][j]; 在表達式i【課堂實踐】分析并計算下面程序段執行的時間復雜度。
i=1; k=0;?
while(i<=n-1)
{ k+=10*i;
i++;
}
第2章 線性表
線性表是最常用且最簡單的一種數據結構，一個線性表是n個數據元素的有序系列，每個數據元素可以是一個數或一個符號，也可以使一頁書，甚至其他更復雜的信息。如26個字母的字母表：（A,B,C,D…..,Z）在復雜的線性表中，一個數據元素可以由若干個數據項組成，在這種情況下，常把數據元素稱為一個記錄，含有大量記錄的線性表又稱文件。如圖
綜合上述例子，可以將線性表描述為：
線性表是由n個數據元素的有限序列(a1,a2,…,an)組成的，其中每一個數據元素ai的具體含義可以按不同的情況和要求定義具體的內容，它可以是一個數、一個符號、一串文字，甚至是其他更復雜的信息。線性表中數據元素的個數n稱為線性表的長度。
2.1 線性表的邏輯結構及基本運算
1.線性表簡單的定義
n個數據元素的有限序列其特點是除了表頭和表尾外，表中的每一個元素有且僅有唯一的前驅和唯一的后繼，表頭有且只有一個后繼，表尾有且只有一個前驅。線性表中的數據元素不僅可以進行訪問，還可進行插入和刪除。
若n=0，則表示一個空表，即沒有任何數據元素的線性表；若n>0，則除a1和an外，有且僅有一個直接前驅和一個直接后繼，即ai(其中1< i2.線性表的基本運算
（1）線性表初始化
格式：InitList(L)
初始條件：線性表L不存在。
操作結果：構造一個空的線性表L。
（2）求線性表的長度
格式：LengthList(L)
初始條件：線性表L存在。
操作結果：返回線性表L中所有元素的個數。
（3）取表元
格式：GetList(L，i)
初始條件：線性表L存在，且1≤i≤LengthList(L)。
操作結果：返回線性表L的第i個元素(ai)的值。
（4）按值查找
格式：LocateList(L，x)
初始條件：線性表L存在，x有確定的值。
操作結果：在線性表L中查找值為x的數據元素，并返回該元素在L中的位置。若L中有多個元素的值與x相同，則返回首次找到的元素的位置；若L中沒有值為x的數據元素，返回一個特殊值（通常為-1）表示查找失敗。
（5）插入操作
格式：InsertList(L，i，x)
初始條件：線性表L存在，i為插入位置（1≤i≤n+1，n為插入前的表長）。
操作結果：在線性表L的第i個元素(ai)位置上插入值為x的新元素，原序號為i,i+1, …,n的數據元素的序號插入后變為i+1,i+2, …,n+1，插入后表長=原表長+1。
（6）刪除操作
格式：DeleteList(L，i)
初始條件：線性表L存在，i（1≤i≤n）為給定的待刪除元素的位置值。
操作結果：在線性表L中刪除序號為i的數據元素(ai)，刪除后，原序號為i+1,i+2, …,n的數據元素的序號變為i,i+1, …,n-1，刪除后表長=原表長-1。
注：以上給出的是線性表的基本運算，并不是全部運算，其它運算可用這些基本運算來實現，這些運算都是定義在邏輯結構層次上的運算，只有確定了存儲結構之后，才能具體實現這些運算。
例1 假設兩個線性表LA,LB分別代表兩個集合A和B:求A=A U B
void union(List &La ,List &Lb){
//將所有在線性表Lb中，但不在La中的數插入到La中
La.len=ListLength(La);
Lb.len=ListLength(Lb); //求兩表的長度
for(i=1;i<=Lb.len;i++)
GetElem(Lb,i,e);//取Lb中第i個的元素復制給e
If(!LocateElem(La,e,equal))
ListInsert(La,++La.len,e);//若其中不存在相同的，則插入
}//union
例2 已知線性表la，lb中的數據元素按值非遞減有序排列，現要求將la，lb歸并為一個新的線性表lc且lc按值非遞減。
例如 la=（3,5,8,11）,
Lb=(2,6,8,9,11,15,20)
則lc=(2,3,5,6,8,8,9,11,11,15,20)
分析：由于兩表都是按照一定順序進行排列，所有設置2個指針，分別指向a、b表，先分別比較比較最初指向的兩數據，比較一下大小，誰小就放入到c表中，然后數小的指針向下移動，再進行比較。直到2表有一表結束,再將剩余的表存放到c中。
Void MergeList(List La, List Lb,List &Lc){
//已知線性表la和lb中的數據元素
InitList(Lc);//初始化表c
Int i=j=1;k=0;
La.len=ListLength(La);
Lb.len= ListLength(Lb);
While((i<= La.len)&&( (j<= Lb.len)){
GetElem（La,i,ai）;
GetElem（Lb,j,bj）;//獲取數值
If(ai<=bj){
ListInsert(Lc,++k,ai);
i++;
}else{
ListInsert(Lc,++k,bj);
j++;
}//if結束
}//whie結束,其中一表結束；
While(i<=La.len){//表B數據全訪問完，表a未到最后
GetElem（La,i++,ai）;
ListInsert(Lc,++k,ai);
}
While(j<=Lb.len){//表a數據全訪問完，表b未到最后
GetElem（Lb,j++,bj）;
ListInsert(Lc,++k,bj);
}
}//程序結束
分析：上述2個算法的時間復雜度（基本操作的執行時間），例1為O(ListLength(La)*ListLength(Lb)),例2的時間復雜度為O(ListLength(La)+ListLength(Lb))。
2.2 線性表的順序存儲結構
線性表的順序存儲即用一組地址連續的存儲單元依次存儲線性表中的元素。設線性表中每個元素需占用r個存儲單元則
loc（ai+1 ）=loc（ai）+r
loc（ai）=loc（a1）+（i-1）*r
線性表的這種機內表示稱做線性表的順序存儲結構或順序映像，通常，稱這種存儲結構的線性表為順序表。只要確定了存儲線性表的起始位置，線性表中任一數據元素可隨機存儲，所以線性表的順序結構是一種隨機存儲的存儲結構。
//======線性表的動態順序存儲結構
#define LIST_INIT_SIZE 100 // 初始分配量
#define LISTINCREMENT 10 //分配增量
Typedef struct{
Elemtype *elem; //存儲空間基址
Int length; //當前長度
Int listsize; //當前分配的存儲容量
}SqList;
Elem表示基地址，length指示線性表的當前長度。上述的含義是為順序表分配一個預定義大小的數據空間，并將當前的長度設為0；
Status InitList_sq(SqList &L){
//====創建一個空的線性表
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));// ElemType指數據類型，malloc新分配空間
If(!L.elem) exit(OVERFLOW);//存儲分配失敗
L.length=0;//空表長度為0
L.listsize= LIST_INIT_SIZE;//初始存儲容量
Return ok；
}//InitList_sq
在這種存儲方式下，容易實現對表的遍歷。要在表的尾部插入一個新元素，也很容易。但是要在表的中間位置插入一個新元素，就必須先將其后面的所有元素都后移一個單元，才能騰出新元素所需的位置。
Status ListInsert_sq(SqList &L,int I,ElemType e){
//在順序表中插入一個新元素 e
If(i<1||i>L.length+1) return Error;
If(L.length>= L.listsize){//當前存儲空間已滿，增加分配
Newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType));// ElemType指數據類型，realloc再次分配，L.elem存儲基地址
}//if
q=&(L.elem[i-1]);//q為插入位置
for(p=&(L.elem[L.length-1]);p>=q;--p){
*(p+1)=*q;
}//for
*q=e;//插入e
++ L.length；
Return ok；
}
執行刪除運算的情形類似。如果被刪除的元素不是表中最后一個元素，則必須將它后面的所有元素前移一個位置，以填補由于刪除所造成的空缺。這兩種運算的時間復雜度均為O(n)n為表的長度。
Status ListDelete_sq(SqList &L,int I,ElemType &e){
//在順序表中插入一個新元素 e
If(i<1||i>L.length+1) return Error;
p=&(L.elem[i-1]);//p為刪除位置
e=*p;
q=L.elem+L.length-1;
for(++p;p<=q;++p){
*(p-1)=*p;
}//for
-- L.length；
Return ok；
}
2.3 線性表的鏈式存儲結構
線性表順序結構的特點是邏輯關系上相鄰的兩個元素在物理位置上也相鄰，因此可以隨機存儲表中的任一元素，但是在插入刪除時須移動大量元素。而線性表的鏈式存儲由于其不要求邏輯上相鄰，因此它沒有順序存儲結構的弱點，但同時也失去了順序表可隨機存取的優點。
1.單鏈表
線性鏈表的特點是用一組任意的存儲單元存儲線性表的元素，用指針將存儲表元素的那些單元依次串聯在一起。這種方法避免了在數組中用連續的單元存儲元素的缺點，因而在執行插入或刪除運算時，不再需要移動元素來騰出空間或填補空缺。然而我們為此付出的代價是，需要在每個單元中設置指針來表示表中元素之間的邏輯關系，因而增加了額外的存儲空間的開銷。
為了將存儲表元素的所有單元用指針串聯起來，我們讓每個單元包含一個元素域和一個指針域如圖所示：
其中，存儲單元由兩部分構成，即數據域存儲數據元素，指針域存儲下一個元素所在的單元
如果表是a1,a2,…,an ，那么含有元素ai的那個單元中的指針應指向含有元素ai+1的單元(i=1,2,…,n-1)。含有an的那個單元中的指針是空指針null。此外，通常我們還為每一個表設置一個表頭單元header，其中的指針指向開始元素中所在的單元，但表頭單元header中不含任何元素。設置表頭單元的目的是為了使表運算中的一些邊界條件更容易處理。這一點我們在后面可以看到。如果我們愿意單獨地處理諸如在表的第一個位置上進行插人與刪除操作等邊界情況，也可以簡單地用一個指向表的第一個單元的指針來代替表頭單元。
上述這種用指針來表示表的結構通常稱為單鏈接表，或簡稱為單鏈表或鏈表。單鏈表的邏輯結構如圖1所示。表示空表的單鏈表只有一個單元，即表頭單元header，其中的指針是空指針null。

圖1 單鏈表示意圖
為了便于實現表的各種運算，在單鏈表中位置變量的意義與用數組實現的表不同。在單鏈表中位置i是一個指針，它所指向的單元是元素ai-1所在的單元，而不是元素ai所在的單元(i=2,3,…,n)。位置1是指向表頭單元header的指針。位置End(L)是指向單鏈表L中最后一個單元的指針。這樣做的目的是為了避免在修改單鏈表指針時需要找一個元素的前驅元素的麻煩，因為在單鏈表中只設置指向后繼元素的指針，而沒有設置指向前驅元素的指針。
單鏈表存儲結構
Typedef struct Lnode{
ElemType data;
Struct Lnode *next;//指向后繼節點的指針
}Lnode, *LinkList;//線性鏈表的實質就是指針
基本運算
(1)ListInsert.L(L,i,e)
功能:在表L的位置p處插入元素x，并將原來占據位置p的元素及其后面的元素都向后推移一個位置。例如，設L為a1,a2,…,an，那么在執行Insert(x,p)后，表L變為a1,a2,…ap-1,x,ap,…,an 。若p為End(L)，那么表L變為a1,a2,…,an,x 。若表L中沒有位置p，則該運算無定義。
實現P為指向a節點的指針，s為指向X節點的指針:s->next=p->next; p->next=s;
上述算法中，鏈表指針的修改情況見圖2
圖2(a)是執行Insert運算之前的情況。我們要在指針p所指的單元之后插入一個新元素x。圖2(b)是執行Insert運算以后的結果，其中的虛線表示新的指針。在上述Insert算法中，位置變量p指向單鏈表中一個合法位置，要插入的新元素x應緊接在p所指單元的后面。指針p的合法性應在執行Insert運算之前判定。往一個單鏈表中插入新元素通常在表頭或表尾進行，因此p的合法性容易判定。Insert運算所需的時間顯然為O(1)。
(2)Delete(p)
功能:從表L中刪除位置p的下一元素。例如，當L為a1,a2,…,an時，執行Delete(p)后，L變為a1,a2,…,ap-1,ap+1,…,an 。當L中沒有位置p或p=End(L)時，該運算無定義。實現:p.next=p.next.next;
這個過程很簡單，其指針的修改如圖3所示。
若要從一個表中刪除一個元素x，但不知道它在表中的位置，則應先用Locate(x,L)找出指示要刪除的元素的位置，然后再用Delete刪除該位置指示的元素。Delete過程所需的時間顯然也為O(1)。
2.靜態鏈表
靜態鏈表：用游標指示數組單元地址的下標值，它屬整數類型數組元素是記錄類型，記錄中包含一個表元素和一個作為游標的整數；具體說明如下:
type jid=record
data:datatype;
next:integer;
end;
var alist=array[0..maxsize] of jid
游標即我們可以用游標來模擬指針, 對于一個表L，我們用一個整型變量Lhead(如Lhead=0)作為L的表頭游標。。這樣，我們就可以用游標來模擬指針，實現單鏈表中的各種運算。當i>1時，表示第i個位置的位置變量pi的值是數組alist中存儲表L的第i-1個元素next值,用p:=alist(p).next后移。照此，我們雖然是用數組來存儲表中的元素，但在作表的插人和刪除運算時，不需要移動元素，只要修改游標，從而保持了用指針實現表的優點。因此，有時也將這種用游標實現的表稱為靜態鏈表。
3.循環鏈表
循環鏈表是另一種鏈式存儲結構，特點是表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環。因此，可由表中任一結點出發均可找到表中其他結點。如圖6所示的是一個單鏈的循環鏈表或簡稱為單循環鏈表。
(a)非空表
(b)空表
圖6單循環鏈表
在單循環鏈表上實現表的各種運算的算法與單鏈表的情形是類似的。它們僅在循環終止條件上有所不同:前者是p或p^.next指向表頭單元；后者是p或p^.next指向空(nil)。在單鏈表中我們用指向表頭單元的指針表示一個表L，這樣就可以在O(1)時間內找到表L中的第一個元素。然而要找到表L中最后一個元素就要花O(n)時間遍歷整個鏈表。在單循環鏈表中，我們也可以用指向表頭單元的指針表示一個表L。但是，如果我們用指向表尾的指針表示一個表L時，我們就可以在O(1)時間內找到表上中最后一個元素。同時通過表尾單元中指向表頭單元的指針，我們也可以在O(1)時間內找到表L中的第一個元素。在許多情況下，用這種表示方法可以簡化一些關于表的運算。
4.雙鏈表
單循環鏈表中，只有一個指示直接后繼的指針域，雖然從任一單元出發，可以找到其前驅單元，但需要O(n)時間。如果我們希望能快速確定表中任一元素的前驅和后繼元素所在的單元，可以在鏈表的每個單元中設置兩個指針，一個指向后繼，另一個指向前驅，形成圖8所示的雙向鏈表或簡稱為雙鏈表。
圖8 雙鏈表
由于在雙鏈表中可以直接確定一個單元的前驅單元和后繼單元，我們可以用一種更自然的方式表示元素的位置，即用指向雙鏈表中第i個單元而不是指向其前一個單元的指針來表示表的第i個位置。
雙鏈表的單元類型定義如下。

和單鏈的循環表類似，雙鏈表也可以有相應的循環表。我們用一個表頭單元將雙鏈表首尾相接，即將表頭單元中的previous指針指向表尾，并將表尾單元的next指針指向表頭單元，構成如圖9所示的雙向循環鏈表。
圖9 雙向循環鏈表
下面僅以雙向循環鏈表為例給出三種基本運算的實現。
(1)在雙向循環鏈表L的位置p處插入一個新元素x的過程Insert可實現如下。

上述算法對鏈表指針的修改情況見圖10。
圖10 在雙向循環鏈表中插入一個元素
算法Insert中沒有檢查位置p的合法性，因此在調用Insert之前應保證位置p的合法性。由于插入通常是在表的頭尾兩端進行的，所以容易檢查位置p的合法性。
(2)從雙向循環鏈表L中刪除位置p處的元素可實現如下:
上述算法對鏈表指針的修改情況見圖11。
圖11 從雙向循環鏈表中刪除一個元素
5.鏈表的應用
例1：求 (A-B)U(B-A)其中A,B代表兩個集合（用靜態鏈表）
例2 求p1(x)+p2(x) (兩個多項式的和）
練習題：
1.約瑟夫問題:
有M個猴子圍成一圈，每個有一個編號，編號從1到M。打算從中選出一個大王。經過協商，決定選大王的規則如下：從第一個開始，每隔N個，數到的猴子出圈，最后剩下來的就是大王。
要求：從鍵盤輸入M，N，編程計算哪一個編號的猴子成為大王。(_?¨????_）
2.求多項式的減與乘法.(_?¨????_）
第3章 棧
棧是一種特殊的線性表，它的邏輯結構與線性表相同，只是其運算規則較線性表有更多的限制，故又稱它為運算受限的線性表。
3.1 棧的概念及運算
棧（Stack）是限制僅在表的一端進行插入和刪除運算的線性表。向棧中插入元素稱為進（入）棧，從棧中刪除元素稱為退（出）棧。
通常插入、刪除的這一端稱為棧頂，由于元素的進棧和退棧，使得棧頂的位置經常是變動的，因此需要用一個整型量Top指示棧頂的位置，通常稱Top 為棧頂指針；另一端稱為棧底。
當表中沒有元素時稱為空棧，即Top=-1。
棧的修改是按后進先出的原則進行。每次刪除的總是當前棧中“最新”的元素，即最后插入的元素，而最先插入的是被放在棧的底部，要到最后才能刪除。。
假設一個棧S中的元素為an,an-1,..,a1，則稱a1為棧底元素，an為棧頂元素。棧中的元素按a1 ,a2,..,an-1,an的次序進棧。在任何時候，出棧的元素都是棧頂元素。換句話說，棧的修改是按后進先出的原則進行的，如圖1所示。因此，棧又稱為后進先出(Last In First Out)表，簡稱為LIFO表。所以，只要問題滿足LIFO原則，就可以使用棧。　

圖1
棧的運算：為一種抽象數據類型，常用的棧運算有:
運算 含義
inistack(S) 使S成為一個空棧。
getTop(S) 這是一個函數，函數值為S中的棧頂元素。
Pop(S) 從棧S中刪除棧頂元素，簡稱為拋棧。
Push(S,x) 在S的棧頂插入元素x，簡稱為將元素x入棧。
Empty(S) 這是一個函數。當S為空棧時，函數值為true，否則函數值為false。
3.2 棧的存儲與實現
1.順序棧及基本操作的實現
由于棧是運算受限線性表，因此線性表的存儲結構對棧也適用，而線性表有順序存儲和鏈式存儲兩種，所以，棧也有順序存儲和鏈式存儲兩種。
（1）順序棧：棧的順序存儲結構簡稱為順序棧，它是運算受限的順序表。
（2）順序棧的描述
#define StackSize 100 //假定棧空間最多為100個元素
typedef char DataType;//假定棧元素的類型為字符類型
typedef struct{
DataType data[StackSize];//棧元素定義
int top;//棧指針定義
}SeqStack;
SeqStack *S;// 定義棧S
設S是SeqStack類型的指針變量，則棧頂指針可表示為S-> top；若棧底位置在向量的低端，則S->data[0]是棧底元素，棧頂元素可表示為S->data[S-> top]。
注意：
①有元素x進棧時，需要先將S->top加1，然后再將元素進棧，即依次完成下列操作：++S->top;S->data[S-> top]=x;。
②當棧頂元素做退棧操作后，需要將S->top減1，即完成操作：S->top--;。
③條件S->top==StackSize-1表示棧滿；S->top==-1表示棧空。
④當棧滿時，再做進棧運算所產生的空間溢出現象稱為上溢。上溢是一種出錯狀態，應設法避免。
⑤當棧空時，做退棧運算所產生的溢出現象稱為下溢。
3、順序棧上基本運算的算法
①置棧空
void InitStack（SeqStack *S）{//將順序棧置空
???? S->top=-1;
}
②判棧空
如果棧S為空，則S->top==-1，此時應該返回1，而關系表達式S->top==-1的值為1；如果棧S為非空，則S->top!=-1，此時應該返回0，而關系表達式S->top==-1的值為0，因此，無論怎樣只需返回S->top==-1的值。
int StackEmpty（SeqStack *S）{
return S->top==-1;
}
③判棧滿
與判棧空的道理相同，只需返回S->top==StackSize-1。
int StackFull（SeqStack *S）{
return S->top==StackSize-1;
}
④進棧
進棧操作需要將棧和進棧元素的值作為函數參數，由于使用棧指針作為函數參數，對棧進行操作，所以進棧函數不需要有返回值；進棧操作時，需要判斷是否棧滿，當棧不滿時，先將棧頂指針加1，再進棧。
int Push（SeqStack *S，DataType x）{
if (StackFull(S))
{puts("棧滿"); return 0;}
S->data[++S->top]=x;//棧頂指針加1后將x入棧
return 1;
}
⑤退棧
退棧操作需要將棧指針作為函數參數，并返回棧頂元素的值，所以函數返回值的類型為DataType；退棧操作時，需要判斷是否棧空，當棧不空時，先退棧，再將棧頂指針減1，可以先將棧頂元素的值記錄下來，然后棧頂指針減1，最后返回記錄下來的值，也可以像給出的退棧函數那樣來操作。
DataType Pop（SeqStack * S）{
if(StackEmpty(S))
{puts("棧空"); return 0;}
return S->data[S->top--];//返回棧頂元素并將棧頂指針減1
}
⑥取棧頂元素
取棧頂元素與退棧的區別在于，退棧需要改變棧的狀態，而取棧頂元素不需要改變棧的狀態。
DataType StackTop（SeqStack *S）{
if(StackEmpty(S))
{puts("棧空"); return 0;}
return S->data[S->top];
}
由于棧的插入和刪除操作具有它的特殊性，所以用順序存儲結構表示的棧并不存在插入刪除數據元素時需要移動的問題，但棧容量難以擴充的弱點仍就沒有擺脫。
例 元素a1，a2，a3，a4依次進入順序棧，則下列不可能的出棧序列是
A．a4, a3, a2, a1 B．a3, a2, a4, a1
C．a3, a4, a2, a1 D．a3, a1, a4, a2
分析：對于A，由于元素a1，a2，a3，a4依次進棧，而a4先出棧，說明a1，a2，a3已經入棧，所以出棧順序只能是a4，a3，a2，a1，因此A是正確的出棧序列；對于B，C，D，由于都是a3先出棧，說明a1，a2已經入棧，所以a1，a2的相對位置一定是不變的，這就是a2一定在a1之前出棧，比較上述三個答案，只有D中的a1出現在a2的前面，這顯然是錯誤的。因此，答案為D。
2.鏈棧及基本操作的實現
若棧中元素的數目變化范圍較大或不清楚棧元素的數目，就應該考慮使用鏈式存儲結構。用鏈式存儲結構表示的棧稱作“鏈棧”。鏈棧通常用一個無頭結點的單鏈表表示。
由于棧的插入刪除操作只能在一端進行，而對于單鏈表來說，在首端插入刪除結點要比尾端相對地容易一些，所以，我們將單鏈表的首端作為棧頂端，即將單鏈表的頭指針作為棧頂指針。鏈棧如圖3.2。
（1）鏈棧：棧的鏈式存儲結構稱為鏈棧，它是運算受限的單鏈表，其插入和刪除操作僅限制在表頭位置上進行，棧頂指針就是鏈表的頭指針。
（2）鏈棧的描述
typedef char DataType;//假定棧元素的類型為字符類型
typedef struct stacknode{//結點的描述
DataType data;
struct stacknode *next;
}StackNode;
typedef struct{//棧的描述
StackNode??*top;? //棧頂指針
}LinkStack;
LinkStack *S; //定義指向鏈棧的指針S
設S是LinkStack類型的指針變量，則S是指向鏈棧的指針，鏈棧棧頂指針可表示為S-> top；鏈棧棧頂元素可表示為S-> top ->data。
設p是StackNode類型的指針變量，則p是指向鏈棧某結點的指針，該結點的數據域可表示為p ->data，該結點的指針域可表示為p -> next。
注意：
①LinkStack結構類型的定義是為了方便在函數體中修改top指針本身。
②若要記錄棧中元素個數，可將元素個數屬性作為LinkStack類型中的成員定義。
③條件S->top== NULL表示空棧，鏈棧沒有棧滿的情況。
3、鏈棧上基本運算的算法
①置棧空
void InitStack（LinkStack *S）{//將鏈棧置空
S->top=NULL;
}
②判棧空
int StackEmpty（LinkStack *S）{
return S->top==NULL;
}
③進棧
void Push（LinkStack *S，DataType x ）{//將元素x插入鏈棧頭部
StackNode *p=(StackNode *)malloc(sizeof(StackNode));
p->data=x;
p->next=S->top;//將新結點*p插入鏈棧頭部
S->top=p; //棧頂指針指向新結點
}
④退棧
DataType Pop（LinkStack *S）{
DataType x;
StackNode *p=S->top;//保存棧頂指針
if(StackEmpty(S))
{puts(“棧空”); return 0;}//下溢，退出運行
x=p->data;? //保存棧頂結點數據
S->top=p->next;? //將棧頂結點從鏈上摘下
free(p);
return x;
}
⑤取棧頂元素
DataType StackTop（LinkStack *S）{
if(StackEmpty(S))
{puts(“棧空”); return 0;}
return S->top->data;
}
注：由于鏈棧中的結點是動態分配的，可以不考慮上溢，所以無須定義StackFull運算。
3.3 棧的應用
1.數值轉換
十進制整數N向其它進制數d(二、八、十六)的轉換是計算機實現計算的基本問題。
轉換法則：該轉換法則對應于一個簡單算法原理:n=(n div d)*d+n mod d
其中：div為整除運算,mod為求余運算
例如 (1348)10= (2504)8，其運算過程如下：
n n div 8 n mod 8
1348 168 4
168 21 0
21 2 5
2 0 2
采用靜態順序棧方式實現
void conversion(int n , int d) { /*將十進制整數N轉換為d(2或8)進制數*/
SqStack S ; int k, *e ;
S=Init_Stack();
while (n>0) { k=n%d ; push(S , k) ; n=n/d ;
} /* 求出所有的余數，進棧 */
while (S.top!=0) { /* 棧不空時出棧，輸出 */
pop(S, e) ;
printf(“%1d” , *e) ;
}
}
2.表達式的求值
問題:能否設計算法，編制一個程序，讓計算機掃描如下表達式，并將其值打印出來。
　　# 3 * ( 4 + 8 ) / 2 -5 #
　　注：給表達式設置#，標志掃描的開始和結束。
這個表達式的計算順序是：3*（4+8）/2-5=3*12/2-5=36/2-5=18-5=13
任何一個表達式都是由操作數、運算符和界位符組成的，操作數可以使一些常數也可以使一些變量或是常量的標示符，運算符則分為算數運算符、關系運算符和邏輯運算符；基本界位符有左右括號和表達式結束。一般將運算符和界位符看做是界符。
　　提示算法：為實現算符優先算法，可以實現2個工作棧，一個是操作數棧opnd，用來存放操作數，如3、4、8等，另一個是運算符棧optr，用來存放運算符。
　　首先將標志“#”進運算符棧的棧底。
　　然后依次掃描，按照棧的后進先出原則進行：
　　（1）遇到操作數，進操作數棧；
　　（2）遇到運算符時，則需將此運算符的優先級與棧頂運算符的優先級比較，
　　若若高于棧頂元素則進棧，繼續掃描下一符號，
　　否則，將運算符棧的棧頂元素退棧，形成一個操作碼Q，同時操作數棧的棧頂元素兩次退棧，形成兩個操作數a、b，讓計算機對操作數與操作碼完成一次運算操作，即aQb，并將其運算結果存放在操作數棧中……
模擬計算機處理算術表達式過程。從鍵盤上輸入算術表達式串（只含＋、－、×、÷運算符，充許含括號），輸出算術表達式的值。設輸入的表達式串是合法的。
附源程序：
3.背包問題
問題：假設有n件質量分配為w1，w2，...，wn的物品和一個最多能裝載總質量為T的背包，能否從這n件物品中選擇若干件物品裝入背包，使得被選物品的總質量恰好等于背包所能裝載的最大質量，即wi1+wi2+...+wik=T。若能，則背包問題有解，否則無解。
　　算法思想：首先將n件物品排成一列，依次選取；若裝入某件物品后，背包內物品的總質量不超過背包最大裝載質量時，則裝入（進棧）；否則放棄這件物品的選擇，選擇下一件物品試探，直至裝入的物品總和正好是背包的最大轉載質量為止。這時我們稱背包裝滿。
　　若裝入若干物品的背包沒有滿，而且又無其他物品可以選入背包，說明已裝入背包的物品中有不合格者，需從背包中取出最后裝入的物品（退棧），然后在未裝入的物品中挑選，重復此過程，直至裝滿背包（有解），或無物品可選（無解）為止。
　　具體實現：設用數組weight[1..N]，stack[1,N]分別存放物品重量和已經裝入背包（棧）的物品序號，MaxW表示背包的最大裝載量。每進棧一個物品，就從MaxW中減去該物品的質量,設i為待選物品序號,若MaxW-weight[i]>=0，則該物品可選；若MaxW-weight[i] < 0，則該物品不可選,且若i>n，則需退棧，若此時棧空，則說明無解。
練習:完整完成背包問題
第4章 隊列
隊列與棧一樣都是運算受限的線性表，但與棧的限制不同。
4.1 隊列的概念及運算
隊列是一種特殊的線性表，對這種線性表，刪除操作只在表頭(稱為隊頭)進行，插入操作只在表尾(稱為隊尾)進行。隊列的修改是按先進先出的原則進行的，所以隊列又稱為先進先出(First In First Out)表，簡稱FIFO表。
假設隊列為a1,a2,..,an，那么a1就是隊頭元素，an為隊尾元素。隊列中的元素是按a1,a2,..,an的順序進入的，退出隊列也只能按照這個次序依次退出。也就是說，只有在a1離開隊列之后，a2才能退出隊列，只有在a1,a2,..,an-1都離開隊列之后，an才能退出隊列。圖1是隊列的示意圖。
圖1
隊列的運算：
為一種抽象數據類型，常用的隊列運算有:
　
4.2 隊列的存儲與實現
隊列是一種特殊的表，因此凡是可以用來實現表的數據結構都可以用來實現隊列。不過，隊列的中的元素的個數通常不固定，因此常用循環數組和鏈表兩種方法實現隊列。
1.順序隊列及基本操作
（1）順序隊列：隊列的順序存儲結構稱為順序隊列，它是運算受限的順序表。
（2）順序隊列的表示
①和順序表一樣，順序隊列用一個數組來存放當前隊列中的元素。
②由于隨著入隊和出隊操作的變化，隊列的隊頭和隊尾的位置是變動的，所以應設置兩個整型量front和rear分別指示隊頭和隊尾在向量空間中的位置，它們的初值在隊列初始化時均應置為0。通常稱front為隊頭指針，稱rear為隊尾指針。
（3）順序隊列的基本操作
①入隊：入隊時將新元素插入rear所指的位置，然后將rear加1。
②出隊：出隊時刪去front所指的元素，然后將front加1并返回被刪元素。
注意：
①當頭尾指針相等時，隊列為空。
②在非空隊列里，隊頭指針始終指向隊頭元素，尾指針始終指向隊尾元素的下一位置。
順序隊列基本操作如圖3.3。
（4）順序隊列中的溢出現象
①“下溢”現象：當隊列為空時，做出隊操作產生的溢出現象。
②“真上溢”現象：當隊列滿時，做入隊操作產生空間溢出的現象。“真上溢”是一種出錯狀態，應設法避免。
③“假上溢”現象：由于入隊和出隊操作中，頭尾指針只增加不減少，致使被刪元素的空間永遠無法重新利用。當隊列中實際元素個數遠遠小于向量空間的規模時，也可能由于尾指針已超越向量空間的上界而不能做入隊操作。該現象稱為“假上溢”現象。
（5）解決“假上溢”現象的方法
①當出現“假上溢”現象時，把所有的元素向低位移動，使得空位從低位區移向高位區，顯然這種方法很浪費時間。
②把隊列的向量空間的元素位置0~Queuesize-1看成一個首尾相接的環形，當進隊的隊尾指針等于最大容量，即rear==Queuesize時，使rear=0。
2.循環隊列
（1）循環隊列：把向量空間的元素位置首尾相接的順序隊列稱為循環隊列。
例如，設隊列的容量Queuesize=8，元素a1，a2，a3，a4，a5，a6，a7依次入隊，然后a1，a2，a3出隊的循環隊列如圖3.4。
（2）循環隊列頭尾指針的操作
循環隊列Q進行出隊、入隊操作時，頭尾指針仍要加1。當頭尾指針指向向量上界（QueueSize-1）時，其加1操作的結果是指向向量的下界0。這種循環意義下的加1操作可以描述為：
①利用選擇結構
if(i+1==QueueSize)//i為Q->front或Q->rear
i=0;
else
i++;
②利用模運算
i=(i+1)%QueueSize;//i為Q->front或Q->rear
我們將采用此方法實現循環意義下的隊頭、隊尾指針的加1操作。
（3）循環隊列邊界條件的處理方法
循環隊列Q中，由于入隊時尾指針向前追趕頭指針；出隊時頭指針向前追趕尾指針，造成隊空和隊滿時頭尾指針均相等。因此，無法通過條件Q->front== Q->rear來判別隊列是“空”還是“滿”。解決這個問題的方法至少有三種：
①另設一標志變量flag以區別隊列的空和滿，比如當條件Q->front== Q->rear成立，且 flag 為0時表示隊列空，而為1時表示隊列滿。
②少用一個元素的空間。約定入隊前，測試尾指針在循環意義下加1后是否等于隊頭指針，若相等則認為隊滿（注意：rear所指的單元始終為空），此時隊空的條件是Q->front== Q->rear，隊滿的條件是(Q->rear+1)%QueueSize== Q->front。
③使用一個計數器count記錄隊列中元素的總數，當Q->count ==0時表示隊列空；當Q->count ==QueueSize時表示隊列滿。 我們將使用此方法。
（4）循環隊列的描述
#define QueueSize 100?? //定義隊列最大容量
typedef char DataType;? //定義隊列元素類型
typedef struct cirqueue{
DataType data[QueueSize];//隊列元素定義
int front; //隊頭指針定義
int rear; //隊尾指針定義
int count; //計數器定義
}CirQueue;
CirQueue *Q; //定義循環隊列Q
設Q是CirQueue類型的指針變量，則Q是指向循環隊列的指針，隊頭指針、隊尾指可分別表示為Q->front、Q-> rear，計數器可表示為Q-> count，隊頭元素可表示為Q->data[Q->front]，隊尾元素可表示為Q->data[Q-> rear]。
（5）循環隊列的基本運算的算法
① 置隊空
void InitQueue(CirQueue *Q){
Q->front=Q->rear=0;
Q->count=0;???? //計數器置0
}
② 判隊空
int QueueEmpty(CirQueue *Q){
return Q->count==0;? //隊列無元素為空
}
③ 判隊滿
int QueueFull(CirQueue *Q){
return Q->count==QueueSize;?//隊中元素個數等于QueueSize時隊滿
?}
④ 入隊
int EnQueue(CirQueue *Q,DataType x){
if(QueueFull(Q))?
{puts(“隊滿”); return 0;} ???? //隊滿上溢
Q->count ++;?? //隊列元素個數加1
Q->data[Q->rear]=x;? //新元素插入隊尾
Q->rear=(Q->rear+1)%QueueSize;? //循環意義下將尾指針加1
return 1;
}
⑤ 出隊
DataType DeQueue(CirQueue *Q){
DataType temp;
if(QueueEmpty(Q))
{puts(“隊空”); return 0;} //隊空下溢
temp=Q->data[Q->front];
Q->count--; //隊列元素個數減1
Q->front=(Q->front+1)%QueueSize;?? //循環意義下的頭指針加1
return temp;
}
⑥取隊頭元素
DataType QueueFront(CirQueue *Q){
if(QueueEmpty(Q))
{puts(“隊空”); return 0;}
return Q->data[Q->front];
}
3．鏈隊列及基本操作的實現
（1）鏈隊列：隊列的鏈式存儲結構稱為鏈隊列，它是限制僅在表頭刪除和表尾插入的單鏈表。由于需要在表尾進行插入操作，所以為操作方便除頭指針外有必要再增加一個指向尾結點的指針。
（2）鏈隊列的描述
typedef char DataType; //定義隊列元素類型
typedef struct queuenode{//隊列中結點的類型
DataType data;
struct queuenode *next;
}QueueNode;
typedef struct{
QueueNode *front;?//隊頭指針
QueueNode *rear;? //隊尾指針
}LinkQueue;
LinkQueue *Q; //定義鏈隊列Q
設Q是LinkQueue類型的指針變量，則Q是指向鏈隊列的指針，隊頭指針、隊尾指可分別表示為Q->front、Q-> rear。
設p是QueueNode類型的指針變量，則p是指向鏈隊列某結點的指針，該結點的數據域可表示為p ->data，該結點的指針域可表示為p -> next。
（3）鏈隊列示意圖
鏈隊列如圖3.5。
（4）鏈隊列的基本運算
由于鏈隊列結點的存儲空間是動態分配的，所以無須考慮判隊滿的運算。
①置空隊
void InitQueue(LinkQueue *Q){
????? Q->front=Q->rear=NULL;
}
②判隊空
int QueueEmpty(LinkQueue *Q){
return Q->front==NULL&&Q->rear==NULL;//實際上只須判斷隊頭指針是否為空即可
}
③入隊
void EnQueue(LinkQueue *Q,DataType x){//將元素x插入鏈隊列尾部
QueueNode *p;
p=(QueueNode *)malloc(sizeof(QueueNode));
p->data=x;?? p->next=NULL;
if(QueueEmpty(Q))
Q->front=Q->rear=p;? //將x插入空隊列
else { //x插入非空隊列的尾
Q->rear->next=p;???? //*p鏈到原隊尾結點后
Q->rear=p;?????????? //隊尾指針指向新的尾
}
}
④出隊
DataType DeQueue (LinkQueue *Q){
DataType x;
QueueNode *p;
if(QueueEmpty(Q))
{puts(“隊空”); return 0;}
p=Q->front;?????//指向隊頭結點
x=p->data;???????//保存隊頭結點的數據
Q->front=p->next;??//將對頭結點從鏈上摘下
if(Q->rear==p)//原隊中只有一個結點，刪去后隊列變空，此時隊頭指針已為空
Q->rear=NULL;
free(p);?? //釋放被刪隊頭結點
return x;? //返回原隊頭數據
?}
⑤取隊頭元素
DataType QueueFront(LinkQueue *Q)
{
if(QueueEmpty(Q))
{puts(“隊空”); return 0;}
return Q->front->data;
}
注意：在出隊算法中，一般只需修改隊頭指針。但當原隊中只有一個結點時，該結點既是隊頭也是隊尾，故刪去此結點時亦需修改尾指針，且刪去此結點后隊列變空。
4.3 隊列的應用
例1：一矩形陣列由數字0到9組成,數字1到9代表細胞,細胞的定義為沿細胞數字上下左右還是細胞數字則為同一細胞,求給定矩形陣列的細胞個數。
如:陣列
0234500067
1034560500
2045600671
0000000089
有4個細胞。
算法步驟：
1． 從文件中讀入m*n矩陣陣列，將其轉換為boolean矩陣存入bz數組中；
2． 沿bz數組矩陣從上到下，從左到右，找到遇到的第一個細胞；
3． 將細胞的位置入隊h，并沿其上、下、左、右四個方向上的細胞位置入隊，入隊后的位置bz數組置為FLASE；
4． 將h隊的隊頭出隊，沿其上、下、左、右四個方向上的細胞位置入隊，入隊后的位置bz數組置為FLASE；
5． 重復4，直至h隊空為止，則此時找出了一個細胞；
6． 重復2，直至矩陣找不到細胞；
7． 輸出找到的細胞數。
程序：練習：如下圖：求圖中被*圍成的封閉區域的面積（方格的個數不包括*所在的方格，且*不在最外一層）。
第5章 樹和二叉樹
樹型結構是一類重要的非線性結構。樹型結構是結點之間有分支，并具有層次關系的結構。它非常類似于自然界中的樹。
樹型結構在客觀世界中是大量存在的，在計算機領域中也有著廣泛的應用，如在編譯程序中，用樹來表示源程序的語法結構；在數據庫系統可用樹來組織信息。
5.1樹的概念
1.樹的遞歸定義
樹是n(n≥0)個結點的有限集T，T為空時稱為空樹，否則它滿足如下兩個條件：
①有且僅有一個特定的稱為根(Root)的結點；
②其余的結點可分為m(m≥0)個互不相交的有限子集Tl，T2，…，Tm，其中每個子集本身又是一棵樹，并稱其為根的子樹(Subtree)。
注意：樹的遞歸定義刻畫了樹的固有特性：一棵非空樹是由若干棵子樹構成的，而子樹又可由若干棵更小的子樹構成。
2.樹結構的基本術語
（1）結點的度
①結點的度：一個結點擁有子樹的個數稱為該結點的度。
例如圖5.1表示的樹中結點A的度為3，其它結點的度都為2或0。
②樹的度：該樹中結點的最大度數稱為該樹的度。
例如圖5.1表示的樹的度為3。
③葉子結點：度為零的結點稱為葉子結點或終端結點。
例如圖5.1表示的樹中結點C、E、G、H、I、J都是葉子結點。
④分支結點：度不為零的結點稱分支結點或非終端結點。即除葉子結點外的結點均為分支結點。
例如圖5.1表示的樹中結點A、B、D、F都是分支結點。
⑤內部結點：除根結點之外的分支結點統稱為內部結點。
⑥開始結點：根結點又稱為開始結點。
例如圖5.1表示的樹中結點A是開始結點。
（2）結點之間的關系
①孩子結點：樹中某個結點的子樹的根稱為該結點的孩子結點。
例如圖5.1表示的樹中結點B、C、D都是結點A的孩子結點，結點E、F都是結點B的孩子結點，結點G、H都是結點D的孩子結點。
②雙親結點：孩子結點的根稱為該結點的雙親。
例如圖5.1表示的樹中結點A是結點B、C、D的雙親結點，結點B是結點E、F的雙親結點，結點D是結點G、H的雙親結點。
③兄弟結點：同一個雙親的孩子互稱為兄弟結點。
例如圖5.1表示的樹中結點B、C、D互為兄弟結點，結點E、F互為兄弟結點，而結點F和G非兄弟結點。
④堂兄弟：在后面介紹。
⑤祖先和子孫：在后面介紹。
（3）路徑
①路徑或道路：若樹中存在一個結點序列k1,k2,…,kj,使得ki是ki+1的雙親(1≤i②路徑的長度：指路徑所經過的邊的數目。
注意：若一個結點序列是路徑，則在樹的樹形圖表示中，該結點序列“自上而下”地通過路徑上的每條邊。從樹的根結點到樹中其余結點均存在一條惟一的路徑。
例如圖5.1表示的樹中結點序列ABFI是結點A到I的一條路徑，因為自上而下A是B的雙親，B是F的雙親，F是I的雙親。該路徑的長度為3。而結點B和G之間不存在路徑，因為既不能從B出發自上而下地經過若干個結點到達G，也不能從G出發自上而下地經過若干個結點到達B。
③祖先和子孫：若樹中結點k到ks存在一條路徑，則稱k是ks的祖先，ks是k的子孫。一個結點的祖先是從根結點到該結點路徑上所經過的所有結點，而一個結點的子孫則是以該結點為根的子樹中的所有結點。
約定：結點k的祖先和子孫不包含結點k本身。
（4）結點的層數和樹的深度
①結點的層數：根結點的層數為1，其余結點的層數等于其雙親結點的層數加1。
②堂兄弟：雙親在同一層的結點互為堂兄弟。
③樹的深度：樹中結點的最大層數稱為樹的深度。
要注意結點的度、樹的度和樹的深度的區別。
（5）有序樹和無序樹
若將樹中每個結點的各子樹看成是從左到右有次序的，則稱該樹為有序樹；否則稱為無序樹。
若不特別指明，一般討論的樹都是有序樹。
（6）森林
森林是m(m≥0)棵互不相交的樹的集合。
刪去一棵樹的根，就得到一個森林；反之，加上一個結點作樹根，森林就變為一棵樹。
5.2 二叉樹
二叉樹是樹型結構的一個重要類型。許多實際問題抽象出來的數據結構往往是二叉樹形式，即使是一般的樹也能簡單地轉換為二叉樹，而且二叉樹的存儲結構及其算法都較為簡單，因此二叉樹顯得特別重要。二叉樹的特點是每個結點最多只能有兩棵子樹，且有左右之分。
1.二叉樹的定義
（1）二叉樹的遞歸定義
二叉樹是n(n≥0)個結點的有限集，它或者是空集(n=0)，或者由一個根結點及兩棵互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹組成。
（2）二叉樹的五種基本形態
二叉樹可以是空集；可以有空的左子樹或空的右子樹；或者左、右子樹皆為空。
二叉樹的五種基本形態如圖5.3。
圖中(a)為空二叉樹，(b)是僅有一個根結點的二叉樹，(c)是右子樹為空的二叉樹，(d) 是左子樹為空的二叉樹，(e)是左右子樹均非空的二叉樹。
2. 二叉樹的性質
性質1 二叉樹第i層上的結點數目最多為2i-1(i≥1)個。
證明：假設樹非空，用數學歸納法證明。
當i=1時，因為第1層上只有一個根結點，而2i-1=20=1。所以命題成立。
假設對所有的j(1≤j根據歸納假設，第i-1層上至多有2i-2個結點。由于二叉樹的每個結點至多有兩個孩子，故第i層上的結點數至多是第i-1層上的最大結點數的2倍。即j=i時，該層上至多有2?2i-2=2i-1個結點，故命題成立。
性質2 深度為k的二叉樹至多有2k-1(k≥1)個結點。
證明：由性質1，第i層至多有2i-1個(1≤i≤k)結點，所以深度為k的二叉樹的結點總數至多為20+21+…+2k-1=2k-1個。
性質3 在任意一棵非空二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則n0=n2+1。
證明：因為二叉樹中所有結點的度數均不大于2，所以結點總數（記為n）應等于0度結點數n0、1度結點數n1和2度結點數n2之和：
n=n0+n1+n2
另一方面，1度結點有一個孩子，2度結點有兩個孩子，故二叉樹中孩子結點總數是：nl+2?n2，而樹中只有根結點不是任何結點的孩子，故二叉樹中的結點總數又可表示為：
n=n1+2?n2+1
綜合以上兩個式子得到：
n0=n2+1
性質3說明：在任意非空二叉樹中葉子結點數總比度為2的結點數多1個。
例如，如圖5.4所示的二叉樹中
葉子結點數為6，度為2的結點數為5，葉子結點數正好比度為2的結點數多1個。
（1）滿二叉樹：一棵深度為k且有2k-1個結點的二叉樹稱為滿二叉樹。
滿二叉樹的特點：
①每一層上的結點數都達到最大值。即對給定的高度，它是具有最多結點數的二叉樹。
②滿二叉樹中不存在度數為1的結點，每個分支結點均有兩棵高度相同的子樹，且樹葉都在最下一層。
例如，如圖5.5所示的二叉樹
是一棵深度為4的滿二叉樹，每一層上的結點數都達到最大值2i-1(i≥1) 。不存在度數為1的結點，每個分支結點均有兩棵高度相同的子樹，且樹葉都在最下一層。
（2）完全二叉樹
若一棵二叉樹至多只有最下面的兩層上結點的度數可以小于2，并且最下一層上的結點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。
完全二叉樹特點：
①在滿二叉樹的最下一層上，從最右邊開始連續刪去若干結點后得到的二叉樹是一棵完全二叉樹。
②滿二叉樹是完全二叉樹，但完全二叉樹不一定是滿二叉樹。
③在完全二叉樹中，若某個結點沒有左孩子，則它一定沒有右孩子，即該結點必是葉結點。
④深度為k的完全二叉樹的前k-1層是深度為k-1的滿二叉樹，一共有2k-1-1個結點。
例如，如圖5.6所示的兩顆二叉樹中
1）(a)是滿二叉樹，也是完全二叉樹； (b)是完全二叉樹，但不是滿二叉樹。
2）在(a)的最下一層上，從最右邊開始連續刪去3個結點后得到完全二叉樹(b) 。
3）在完全二叉樹(b)中，結點6沒有左孩子，也一定沒有右孩子，即該結點6是葉結點。
4）(b)是深度為4的完全二叉樹，它的前3層是深度為3的滿二叉樹，一共有23-1=7個結點。
性質4 具有n個結點的完全二叉樹的深度為或，其中表示取小于等于lgn的整數部分，表示取大于等于lg(n+1)的整數部分，lg表示以2為底的對數。
證明：設所求完全二叉樹的深度為k。由完全二叉樹特點知：深度為k的完全二叉樹的前k-1層是深度為k-1的滿二叉樹，一共有2k-1-1個結點。
由于完全二叉樹深度為k，故第k層上還有若干個結點，因此該完全二叉樹的結點個數n>2k-1-1。
另一方面，由性質2知：深度為k的二叉樹至多有2k-1(k≥1)個結點，因此，n≤2k-1，
即：2k-1-l又因k-1和k是相鄰的兩個整數，故有
由此即得：。
另外，由2k-1-l3.二叉樹的存儲結構：
　　(1) 順序存儲方式
用一組地址連續的存儲單元依次“自上而下、自左至右”存儲完全二叉樹的數據元素。對于完全二叉樹上編號為i的結點元素存儲在一維數組的下標值為i-1的分量中，如圖所示。對于一般的二叉樹，將其每個結點與完全二叉樹上的結點相對照，存儲在一維數組中，如圖所示。
(2)鏈表存儲方式，如：設計不同的結點結構可構成不同的鏈式存儲結構。
二叉鏈表結點。有三個域：一個數據域，兩個分別指向左右子結點的指針域，如圖6-7(a)所示。
typedef struct BTNode
{ ElemType data ;
struct BTNode *Lchild , *Rchild ;
}BTNode ;
　
4.普通樹轉換成二叉樹：凡是兄弟就用線連起來，然后去掉父親到兒子的連線，只留下父母到其第一個子女的連線。　　　　　
5.二叉樹的遍歷運算（遞歸定義）
(1)先序遍歷
訪問根；按先序遍歷左子樹；按先序遍歷右子樹
算法的遞歸定義是：
若二叉樹為空，則遍歷結束；否則
訪問根結點
先序遍歷左子樹(遞歸調用本算法)；
先序遍歷右子樹(遞歸調用本算法)。
void PreorderTraverse(BTNode *T){
if (T!=NULL) {
visit(T->data) ; /* 訪問根結點 */
PreorderTraverse(T->Lchild) ;
PreorderTraverse(T->Rchild) ;
}
}
(2)中序遍歷
按中序遍歷左子樹；訪問根；按中序遍歷右子樹
void InorderTraverse(BTNode *T){
if (T!=NULL) {
InorderTraverse(T->Lchild) ;
visit(T->data) ; /* 訪問根結點 */
InorderTraverse(T->Rchild) ;
}
}
(3)后序遍歷
按后序遍歷左子樹；按后序遍歷右子樹；訪問根
void PostorderTraverse(BTNode *T){
if (T!=NULL) {
PostorderTraverse(T->Lchild) ;
PostorderTraverse(T->Rchild) ;
visit(T->data) ; /* 訪問根結點 */
}
}
例1.用順序存儲方式建立一棵有31個結點的滿二叉樹，并對其進行先序遍歷。　　
例2.用順序存儲方式建立一棵如圖所示的二叉樹，并對其進行先序遍歷。
例3 用鏈表存儲方式生成上述二叉樹，中序遍歷之。
1.將上述二叉樹用廣義表表示為A(B(D,E(G)),C(F(,H)))
2.根據廣義表串（以#結束）生成二叉樹。
5.3二叉樹的應用
1. 哈夫曼樹與哈夫曼碼
樹的路徑長度：一棵樹的每一個葉結點到根結點的路徑長度的和。
帶權二叉樹：給樹的葉結點賦上某個實數值（稱葉結點的權）。
帶權路徑長度：各葉結點的路徑長度與其權值的積的總和。
哈夫曼樹（最優二叉樹）：帶權路徑長度最小的二叉樹。
如何構建哈夫樹：（思想是：權越大離跟越近）
哈夫曼碼：哈夫曼樹的非葉結點到左右孩子的路徑分別用0，1 表示，從根到葉的路徑序列即為哈夫曼碼。
哈夫曼碼是不會發生譯碼多義性的不等長編碼，廣泛應用實際中。
2.排序二叉樹
排序二叉樹：每一個參加排列的數據對應二叉樹的一個結點，且任一結點如果有左（右）子樹，則左（右）子樹各結點的數據必須小（大）于該結點的數據。中序遍歷排序二叉樹即得排序結果。程序如下：
3.堆排序
堆：設有數據元素的集合（R1,R2,R3,...Rn)它們是一棵順序二叉樹的結點且有 Ri<=R2i 和Ri<=R2i+1(或>=)
堆的性質：堆的根結點上的元素是堆中的最小元素，且堆的每一條路徑上的元素都是有序的。
堆排序的思想是：
1）建初始堆（將結點[n/2],[ n/2]-1,...3,2,1分別調成堆）
2）當未排序完時
輸出堆頂元素，刪除堆頂元素，將剩余的元素重新建堆。
第6章 圖
圖(Graph)是一種復雜的非線性結構，在圖結構中，對結點的前驅和后繼的個數沒有任何限制，結點之間的關系是任意的，圖中任意兩個結點之間都可能有關系。圖結構在計算機科學、人工智能、工程、數學、物理等領域中，有著廣泛的應用。
6.1圖的概念
1.圖的二元組定義
圖G由兩個集合V和E組成，記為：G=(V，E)
其中：V是有限的非空集合，V中的元素稱為頂點或結點，E是V中頂點偶對(vi,vj)的集合，E中的元素稱為邊。
說明：圖G的頂點集和邊集也可記為V(G)和E(G)。E(G)可以是空集，若為空，則圖G只有頂點沒有邊；圖中的邊(vi,vj)描述了兩個頂點之間是相關的。
圖6.1中G1給出了一個圖的示例，在該圖中：
集合V＝{v1,v2,v3,v4,v5}；
集合E＝{(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5) }。
圖6.1 無向圖G1 圖6.2 有向圖G2
2.無向圖和有向圖
（1）無向圖
若圖G中的每條邊都是沒有方向的，則稱G為無向圖。
無向圖中邊的表示：無向圖中的邊均是頂點的無序對，無序對通常用圓括號表示，無序對(vi,vj)和(vj,vi) 表示圖中的同一條邊。
如圖6.1所示圖G1是一個無向圖。
（2）有向圖
若圖G中的每條邊都是有方向的，則稱G為有向圖。
有向圖中邊的表示：有向圖中的邊是由頂點的有序對組成，有序對通常用尖括號表示，有序對和 表示的是圖中不同的邊。有向邊也稱為弧，邊的始點稱為弧尾，終點稱為弧頭。
說明：
①若(v1，v2)或是E(G)中的一條邊，則要求v1≠v2；
②不允許一條邊在圖中重復出現；
③不允許在同一個圖中既有有向邊又有無向邊。
如圖6.2所示圖G2是一個有向圖：
G2=(V2,E2)
V2={v1,v2,v3,v4}
E2={,,,}
（3）完全圖
①無向完全圖：若G是具有n個頂點e條邊的無向圖，則頂點數與邊數的關系為0≤e≤n(n-1)/2。把恰有n(n-1)/2條邊的無向圖稱為無向完全圖。
②有向完全圖：若G是具有n個頂點e條邊的有向圖，則頂點數與邊數的關系為0≤e≤n(n-1)。把恰有n(n-1)條邊的有向圖稱為有向完全圖。
說明：完全圖具有最多的邊數。任意一對頂點間均有邊相連。
3.圖的邊和頂點的關系
（1）無向邊和頂點關系
若(vi,vj)是一條無向邊，則稱頂點vi和vj互為鄰接頂點，或稱vi和vj相鄰接；并稱(vi,vj)依附或關聯于頂點vi和vj，或稱(vi,vj)與頂點vi和vj相關聯。
（2）有向邊和頂點關系
若是一條有向邊，則稱頂點vi鄰接到vj，頂點vi鄰接于頂點vj；并稱邊關聯于vi和vj或稱與頂點vi和vj相關聯。
（3）頂點的度
①無向圖中頂點v的度：無向圖中頂點v的度是關聯于該頂點的邊的數目，記為D(v)。
②有向圖頂點v的入度：有向圖中，以頂點v為終點的邊的數目稱為v的入度，記為ID(v)。
③有向圖頂點v的出度：有向圖中，以頂點v為始點的邊的數目，稱為v的出度，記為OD(v)
④有向圖頂點v的度：有向圖中，頂點v的度定義為該頂點的入度和出度之和，即D(v)=ID(v)+OD(v)。
⑤無論有向圖還是無向圖，頂點數n、邊數e和度數之間有如下關系：
例如，在圖6.1無向圖G1中有：
D(v1)=2 D(v2)=3 D(v3)=3 D(v4)=2 D(v5)=2
在圖6.2有向圖G2中有：
ID(v1)=1 OD(v1)=2 D(v1)=3
ID(v2)=1 OD(v2)=0 D(v2)=1
ID(v3)=1 OD(v3)=1 D(v3)=2
ID(v4)=1 OD(v4)=1 D(v4)=2
4.子圖
設G=(V，E)是一個圖，若V'是V的子集，E'是E的子集，且E'中的邊所關聯的頂點均在V'中，則G'=(V'，E')也是一個圖，并稱其為G的子圖。
圖G1和G2的子圖如圖6.3所示。


圖6.3 圖G1和G2的兩個子圖
5.路徑
（1）無向圖的路徑
在無向圖G中，若存在一個頂點序列vp，vi1，vi2，…，vim，vq，使得(vp,vi1)，(vi1,vi2)，…，(vim,vq)均屬于E(G)，則稱該序列為頂點vp到vq的一條路徑。
（2）有向圖的路徑
在有向圖G中，若存在一個頂點序列vp，vi1，vi2，…，vim，vq，使得有向邊，，…，均屬于E(G) ，則稱該序列為頂點vp到vq的一條路徑。
（3）路徑長度
路徑長度定義為該路徑上邊的數目。
（4）簡單路徑
若一條路徑除兩端頂點可以相同外，其余頂點均不相同，則稱此路徑為一條簡單路徑。
（5）回路
起點和終點相同的路徑稱為回路。
（6）簡單回路或簡單環
起點和終點相同的簡單路徑稱為簡單回路或簡單環。
（7）有根圖和圖的根
在一個有向圖中，若存在一個頂點v，從該頂點有路徑可以到達圖中其它所有頂點，則稱此有向圖為有根圖，v稱作圖的根。
6.連通圖和連通分量
（1）頂點間的連通性
在無向圖G中，若從頂點vi到頂點vj有路徑，則稱vi和vj是連通的。
（2）連通圖
若在無向圖G中，任意兩個不同的頂點vi和vj都連通(即有路徑)，則稱G為連通圖。
（3）連通分量
無向圖G的極大連通子圖稱為G的連通分量。示意圖見圖6.4。
說明：
①任何連通圖的連通分量只有一個，即是其自身；
②非連通的無向圖有多個連通分量。
7.強連通圖和強連通分量
（1）強連通圖
有向圖G中，若對于V(G)中任意兩個不同的頂點vi和vj，都存在從vi到vj以及從vj到vi的路徑，則稱G是強連通圖。
（2）強連通分量
有向圖的極大強連通子圖稱為G的強連通分量。
說明：
①強連通圖只有一個強連通分量，即是其自身；
②非強連通的有向圖有多個強連分量。
有向圖的強連通分量見圖6.5。
8.網絡
若將圖的每條邊都賦上一個權，則稱這種帶權圖為網絡(Network)。
如圖6.6。
說明：權是表示兩個頂點之間的距離、耗費等具有某種意義的數。
6.2 圖的存儲結構
圖的存儲表示方法很多，這里介紹兩種最常用的方法。至于具體選擇哪一種方法，主要取決于具體的應用和要施加的操作。
為了適合用C語言描述，以下假定頂點序號從0開始，即n個頂點圖G頂點集是V(G)={v0,v1,…,vn-1}。
1.圖的鄰接矩陣表示法
（1）圖的鄰接矩陣
設G=(V，E)是具有n個頂點的圖，則G的鄰接矩陣是元素具有如下性質的n階方陣：
（2）圖的鄰接矩陣表示法
①用鄰接矩陣表示頂點間的相鄰關系；
②用一個順序表來存儲頂點信息。
（3）網絡的鄰接矩陣
若G是網絡，則鄰接矩陣可定義為：
其中：wij表示邊上的權值；∞表示一個計算機允許的、大于所有邊上權值的數。網絡的鄰接矩陣如圖6.8。
【課堂實踐6.1】分別寫出圖6.1的無向圖G1和圖6.2的有向圖G2的鄰接矩陣。
（4）圖的鄰接矩陣存儲結構的描述
#define VertexNum 20 //最大頂點數
typedef char VertexType;//頂點類型定義
typedef int EdgeType;//權值類型定義
typedef struct{
VertexType vexs[VertexNum]; //頂點表
EdgeType edges[VertexNum][VertexNum];//鄰接矩陣，可看作邊表
int n,e;//圖中當前的頂點數和邊數
}MGraph;
（5）建立無向網絡的算法
void CreateMGraph(MGraph *G){//建立無向網(圖)的鄰接矩陣表示
int i,j,k,w;
scanf("%d%d",&G->n,&G->e); //輸入頂點數邊數
getchar();
printf("讀入頂點信息，建立頂點表:");
for(i=0;in;i++) //讀入頂點信息，建立頂點表
G->vexs[i]=getchar();
getchar();
for(i=0;in;i++)
for(j=0;jn;j++)
G->edges[i][j]=0; //鄰接矩陣初始化
for(k=0;ke;k++){//讀入e條邊,建立鄰接矩陣
scanf("%d%d%d",&i,&j,&w);//輸入權w
G->edges[i][j]=w;
G->edges[j][i]=w;
}
}
2.圖的鄰接表表示法
（1）圖的鄰接表
對于圖G中的每個頂點vi，把所有鄰接于vi的頂點vj鏈成一個帶頭結點的單鏈表，這個單鏈表就稱為頂點vi的鄰接表(Adjacency List)。
（2）鄰接表的結點結構
①表結點結構
鄰接表中每個表結點均有兩個域
（1）鄰接點域adjvex,存放與vi相鄰接的頂點vj的序號j；
（2）鏈域next,將鄰接表的所有表結點鏈在一起。
注意：若要表示邊上的信息(如權值)，則在表結點中還應增加一個數據域。
②頭結點結構
頂點vi鄰接表的頭結點包含兩個域
（1）頂點域vertex,存放頂點vi的信息；
（2）指針域firstedge,vi的鄰接表的頭指針。
（3）無向圖的鄰接表
對于無向圖，vi的鄰接表中每個表結點都對應于與vi相關聯的一條邊。因此，將鄰接表的表頭向量稱為頂點表。將無向圖的鄰接表稱為邊表。
圖6.7的無向圖的鄰接表如圖6.9。
序號 vertex firstedge
1 3 ∧
0 2 3 ∧


0 1 ∧


注意：n個頂點e條邊的無向圖的鄰接表表示中有n個頂點表結點和2e個邊表結點。
（4）有向圖的鄰接表
對于有向圖，vi的鄰接表中每個表結點都對應于以vi為始點射出的一條邊。因此，將有向圖的鄰接表稱為出邊表。
圖6.2的有向圖G2的鄰接表如圖6.10(a)。
注意：n個頂點e條邊的有向圖，它的鄰接表表示中有n個頂點表結點和e個邊表結點。
（5）有向圖的逆鄰接表
?在有向圖中，為圖中每個頂點vi建立一個入邊表的方法稱逆鄰接表表示法。入邊表中的每個表結點均對應一條以vi為終點(即射入vi)的邊。
圖6.2的有向圖G2的逆鄰接表如圖6.10(b)。

（6）圖的鄰接表存儲結構的描述
圖的鄰接表存儲結構的描述
typedef struct node{//邊表結點定義
int adjvex; //鄰接點域
struct node *next; //鏈域
//若要表示邊上的權，則應增加一個數據域
}EdgeNode;
typedef struct vnode{ //頂點表結點定義
VertexType vertex; //頂點域
EdgeNode *firstedge;//邊表頭指針
}VertexNode;
typedef VertexNode AdjList[VertexNum];//AdjList是鄰接表類型
typedef struct{//鄰接表定義
AdjList adjlist;//鄰接表
int n,e; //圖中當前頂點數和邊數
}ALGraph;
（7）建立無向圖的鄰接表算法
建立無向圖的鄰接表算法：
void CreateALGraph(ALGraph *G){//建立無向圖的鄰接表表示
int i,j,k;
EdgeNode *s;
scanf("%d%d",&G->n,&G->e); //讀入頂點數和邊數
getchar();
for(i=0;in;i++){//建立頂點表
G->adjlist[i].vertex=getchar(); //讀入頂點信息
G->adjlist[i].firstedge=NULL;//邊表置為空表
}
for(k=0;ke;k++){//建立邊表
scanf("%d%d",&i,&j);//讀入邊(vi,vj)頂點對序號
s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成邊表結點
s->adjvex=j; //鄰接點序號為j
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s;//將新結點*s插入頂點vi的邊表頭部
s=(EdgeNode *)malloc(sizeof(EdgeNode));
s->adjvex=i; //鄰接點序號為i
s->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=s;//將新結點*s插入頂點vj的邊表頭部
}
}
6.3 圖的遍歷
從圖的某個頂點出發，沿著某條搜索路徑對圖中每個頂點各做一次且僅做一次訪問，這一過程稱為圖的遍歷。它是許多圖的算法的基礎。深度優先遍歷和廣度優先遍歷是最為重要的兩種遍歷圖的方法。它們對無向圖和有向圖均適用。由于圖中任一頂點都可能和其它頂點相鄰接，所以在遍歷圖時，訪問了某頂點之后，有可能順著某條回路又回到了該頂點。為了避免重復訪問同一個頂點，必須記住每個已訪問的頂點。為此，可設一向量visited[0…n-1]，該向量的每個元素的初值均為0，如果訪問了頂點Vi，就將visited[i]置為1，這樣便可通過visited[i]的值來標志頂點Vi是否被訪問過。以下假定遍歷過程中訪問頂點的操作是簡單地輸出頂點。
1.圖的深度優先遍歷
假設給定圖G的初態是所有頂點均未曾訪問過。在G中任選一頂點v為初始出發點(源點)。
（1）遞歸定義
首先訪問出發點v，并將其標記為已訪問過；然后依次從v出發搜索v的每個鄰接點w。若w未曾訪問過，則以w為新的出發點繼續進行深度優先遍歷，直至圖中所有和源點v有路徑相通的頂點(亦稱為從源點可達的頂點)均已被訪問為止。若此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重復上述過程，直至圖中所有頂點均已被訪問為止。
說明：圖的深度優先遍歷類似于樹的前序遍歷。采用的搜索方法的特點是盡可能先對縱深方向進行搜索。這種搜索方法稱為深度優先搜索(Depth-First Search)。相應地，用此方法遍歷圖就很自然地稱之為圖的深度優先遍歷。
（2）深度優先搜索的過程
設x是當前被訪問頂點，在對x做過訪問標記后，選擇一條從x出發的未檢測過的邊(x，y)。若發現頂點y已訪問過，則重新選擇另一條從x出發的未檢測過的邊，否則沿邊(x，y)到達未曾訪問過的y，對y訪問并將其標記為已訪問過；然后從y開始搜索，直到搜索完從y出發的所有路徑，即訪問完所有從y出發可達的頂點之后，才回溯到頂點x，并且再選擇一條從x出發的未檢測過的邊。上述過程直至從x出發的所有邊都已檢測過為止。此時，若x不是源點，則回溯到在x之前被訪問過的頂點；否則圖中所有和源點有路徑相通的頂點(即從源點可達的所有頂點)都已被訪問過，若圖G是連通圖，則遍歷過程結束，否則繼續選擇一個尚未被訪問的頂點作為新源點，進行新的搜索過程。
（3）深度優先遍歷的遞歸算法(DFS算法)?
①鄰接矩陣表示的深度優先遍歷算法
int visited[VertexNum]={0};//定義標志向量
void DFSM(MGraph *G,int i)
{//以vi為出發點進行搜索，設鄰接矩陣是0,l矩陣
int j;
printf("%4c",G->vexs[i]);//訪問頂點vi
visited[i]=1;
for(j=0;jn;j++) //依次搜索vi的鄰接點
if((G->edges[i][j]==1)&&(!visited[j]))
DFSM(G,j); //(vi,vj)∈E，且vj未訪問過
}
void DFSTraverse(MGraph *G)
{ //深度優先遍歷以鄰接矩陣表示G
int i;
for(i=0;in;i++)
visited[i]=0; //標志向量初始化
for(i=0;in;i++)
if(!visited[i]) //vi未訪問過
DFSM(G,i); //以vi為源點開始DFSM搜索
}
②鄰接表表示的深度優先搜索算法
int visited[VertexNum]={0};//定義標志向量
void DFS(ALGraph *G,int i)
{//以vi為出發點進行深度優先搜索
EdgeNode *p;
printf("%4c",G->adjlist[i].vertex);//訪問頂點vi
visited[i]=1; //標記vi已訪問
p=G->adjlist[i].firstedge; //取vi邊表的頭指針
while(p){//依次搜索vi的鄰接點vj，這里j=p->adjvex
if (!visited[p->adjvex])//若vi尚未被訪問
DFS(G,p->adjvex);//則以vj為出發點向縱深搜索
p=p->next; //找vi的下一鄰接點
}
}
void DFSTraverse(ALGraph *G)
{//深度優先遍歷以鄰接表表示G
int i;
for(i=0;in;i++)
visited[i]=0; //標志向量初始化
for(i=0;in;i++)
if(!visited[i]) //vi未訪問過
DFS(G,i); //以vi為源點開始DFS搜索
}
【課堂實踐6.3】已知含6個頂點(v0，v1，v2，v3，v4，v5)的無向圖的鄰接矩陣如下，求從頂點v0出發進行深度優先遍歷得到的頂點訪問序列。
2.圖的廣度優先遍歷
設圖G的初態是所有頂點均未訪問過。在G中任選一頂點v為源點，則廣度優先遍歷可以定義為：
（1）遞歸定義
首先訪問出發點v，接著依次訪問v的所有鄰接點w1，w2，…，wt，然后再依次訪問與wl，w2，…，wt鄰接的所有未曾訪問過的頂點。依此類推，直至圖中所有和源點v有路徑相通的頂點都已訪問到為止。此時從v開始的搜索過程結束。
若G是連通圖，則遍歷完成；否則，在圖G中另選一個尚未訪問的頂點作為新源點繼續上述的搜索過程，直至G中所有頂點均已被訪問為止。
廣度優先遍歷類似于樹的按層次遍歷。采用的搜索方法的特點是盡可能先對橫向進行搜索，故稱其為廣度優先搜索(Breadth-FirstSearch)。相應的遍歷也就自然地稱為廣度優先遍歷。
（2）廣度優先搜索的過程
在廣度優先搜索過程中，設x和y是兩個相繼要被訪問的未訪問過的頂點。它們的鄰接點分別記為x1，x2，…，xs和y1，y2，…，yt。
為確保先訪問的頂點其鄰接點亦先被訪問，在搜索過程中使用FIFO隊列來保存已訪問過的頂點。當訪問x和y時，這兩個頂點相繼入隊。此后，當x和y相繼出隊時，我們分別從x和y出發搜索其鄰接點x1，x2，…，xs和y1，y2，…，yt，對其中未訪者進行訪問并將其入隊。這種方法是將每個已訪問的頂點入隊，故保證了每個頂點至多只有一次入隊。
（3）廣度優先遍歷的遞歸算法(BFS算法)
①鄰接矩陣表示的廣度優先遍歷算法
int visited[VertexNum]={0};//定義標志向量
void BFSM(MGraph *G,int k){//以vk為源點對用鄰接矩陣表示的圖G進行廣度優先搜索
int i,j;
CirQueue Q;
InitQueue(&Q);
printf("%4c",G->vexs[k]);//訪問源點vk
visited[k]=1;
EnQueue(&Q,k);
while(!QueueEmpty(&Q)){
i=DeQueue(&Q);//vi出隊
for(j=0;jn;j++)//依次搜索vi的鄰接點vj
if(G->edges[i][j]==1&&!visited[j]){//vi未訪問
printf("%4c",G->vexs[j]);//訪問vi
visited[j]=1;
EnQueue(&Q,j);//訪問過的vi入隊
}
}
}
void DFSTraverse(MGraph *G){//廣度優先遍歷以鄰接矩陣表示G
int i;
for(i=0;in;i++)
visited[i]=0; //標志向量初始化
for(i=0;in;i++)
if(!visited[i]) //vi未訪問過
BFSM(G,i); //以vi為源點開始DFSM搜索
}
②鄰接表表示的廣度優先遍歷算法
int visited[VertexNum]={0};//定義標志向量
void BFS(ALGraph*G,int k)
{// 以vk為源點對用鄰接表表示的圖G進行廣度優先搜索
int i;
CirQueue Q;//須將隊列定義中DataType改為int
EdgeNode *p;
InitQueue(&Q);//隊列初始化
printf("%4c",G->adjlist[k].vertex); //訪問源點vk
visited[k]=1;
EnQueue(&Q,k);//vk已訪問，將其入隊。（實際上是將其序號入隊）
while(!QueueEmpty(&Q)){//隊非空則執行
i=DeQueue(&Q);//相當于vi出隊
p=G->adjlist[i].firstedge;//取vi的邊表頭指針
while(p){//依次搜索vi的鄰接點vj(令p->adjvex=j)
if(!visited[p->adjvex]){ //若vj未訪問過
printf("%4c",G->adjlist[p->adjvex].vertex);//訪問vj
visited[p->adjvex]=1;
EnQueue(&Q,p->adjvex);//訪問過的vj人隊
}//endif
p=p->next;//找vi的下一鄰接點
}//endwhile
}//endwhile
}
6.4 最小生成樹
1.生成樹
在圖論中，通常將一個無回路的聯通圖定義成樹。無回路的連通圖叫做自由樹(在自由樹中選定一頂點作根，則成為一棵通常的樹)。
（1）生成樹
如果連通圖G的一個子圖是一棵包含G的所有頂點的樹，則該子圖稱為G的生成樹。
例如：下面是一個連通圖G和它的生成樹。
G （a） （b）
圖 6.12
(a)圖是從v0出發按深度優先搜索得到的生成樹。
(b)圖是從v4出發按深度優先搜索得到的生成樹。
說明：
①生成樹是連通圖的包含圖中的所有頂點的極小連通子圖；
②圖的生成樹不惟一。從不同的頂點出發進行遍歷，可以得到不同的生成樹。
（2）生成樹的求解方法
設圖G=(V，E)是一個具有n個頂點的連通圖。則從G的任一頂點(源點)出發，作一次深度(廣度)優先搜索，搜索到的n個頂點和搜索過程中從一個已訪問過的頂點vi搜索到一個未曾訪問過的鄰接點vj，所經過的邊(vi，vj)(共n-1條)組成的極小連通子圖就是生成樹(源點是生成樹的根) 。
（3）深度優先生成樹和廣度優先生成樹
由深度優先搜索得到的生成樹稱為深度優先生成樹，簡稱為DFS生成樹；由廣度優先搜索得到的生成樹稱為廣度優先生成樹，簡稱為BFS生成樹。
2.最小生成樹
（1）最小生成樹
對于連通的帶權圖(連通網)G，其生成樹也是帶權的。生成樹T各邊的權值總和稱為該樹的權，記作：
其中：TE表示T的邊集，w(u,v)表示邊(u,v)的權。
權最小的生成樹稱為G的最小生成樹(Minimum SpannirngTree)。最小生成樹可簡記為MST。
（2）普里姆(Prim)算法
假設G=(V,E)是連通圖，最小生成樹為T=(V,TE)，求T的步驟如下：
①初始化：U={u0},TE={Φ}, u0是圖G中任意一個頂點；
②在所有u∈U,v∈V-U中，找一條權值最小的邊(u’,v’),令TE+{(u’,v’)}=>TE,U+{v’}=>U；
③如果U=V，則算法結束，否則重復步驟②。
普里姆算法的執行過程：
對圖6.13(a)的圖G，使用普里姆算法求最小生成樹T的執行過程如圖6.13(b)~(l)。





（3）克魯斯卡爾(Kruskal)算法
假設G=(V,E)是連通圖，最小生成樹為T=(V,TE)，求T的步驟如下：
①T的初始狀態是只有n個頂點而無邊的非連通圖T=(V,?)。
②按邊長遞增的順序選擇E中的邊(u,v)加入到T中，要求u、v分屬于T的兩個連通分量；若u、v是T的當前同一個連通分量中的頂點，則舍去此邊。
③重復步驟②直到T中所有頂點都在同一連通分量上為止。
克魯斯卡爾算法的執行過程：
對圖6.13(a)的圖G，使用克魯斯卡爾算法求最小生成樹T的執行過程如圖6.14(a)~(f)。



說明：Prim算法的時間復雜度與圖中邊數無關，適合稠密圖。Cruskal算法的時間取決于邊數，適合于稀疏圖。
【課堂實踐6.5】分別用Prim算法和Cruskal算法求如圖6.8所示的無向帶權圖的最小生成樹。
6.5 最短路徑
1.帶權圖的最短路徑問題
（1）帶權圖的最短路徑問題
求兩個頂點間長度最短的路徑。路徑長度是指路徑上各邊的權值總和。例如，交通網絡中常常提出的如下問題就是帶權圖中求最短路徑的問題。
兩地之間是否有路相通？
在有多條通路的情況下，哪一條最短？
其中:交通網絡可以用帶權圖表示：圖中頂點表示城鎮，邊表示兩個城鎮之間的道路，邊上的權值可表示兩城鎮間的距離、交通費用或途中所需的時間等等。
由于交通網絡存在有向性，所以一般以有向網絡表示交通網絡。
（2）源點和終點
習慣上稱路徑的開始頂點為源點(Source)，路徑的最后一個頂點為終點(Destination)。
為了討論方便，設頂點集V={0，1，…，n-1}，并假定所有邊上的權值均是表示長度的非負實數。
2.最短路徑問題
（1）單源最短路徑問題
已知有向帶權圖(簡稱有向網) G=(V，E)，找出從某個源點s∈V到V中其余各頂點的最短路徑。后3個問題可由此問題解決。
（2）單目標最短路徑問題
找出圖中每一頂點v到某指定頂點u的最短路徑。
（3）單頂點對間最短路徑問題
對圖中某對頂點u和v，找出從u到v的一條最短路徑。
（4）所有頂點對間最短路徑問題
對圖中每對頂點u和v，找出從u到v的一條最短路徑。
3.迪杰斯特拉(Dijkstra)算法求單源最短路徑
由Dijkstra提出的一種按路徑長度遞增序產生各頂點最短路徑的算法。
（1）例子
在有向圖6.14有向圖中，從源點0到其余各頂點的最短路徑如表6.1：
說明：表中源點到各終點的最短路徑按遞增順序排列；源點到每個終點的最短路徑途徑的頂點都已生成最短路徑。
（2）按路徑長度遞增序產生各頂點最短路徑
當前正在生成的最短路徑上除終點以外，其余頂點的最短路徑均已生成(將源點到其自身的路徑看作0)。
（3）算法的基本思想
（1）將頂點集V分成 S(開始只包含源點s, S包含的點都是已經計算出最短路徑的點) 和 V-S 集合（V-S 包含那些未確定最短路徑的點）；
（2）從V-S中選取這樣一個頂點w: 滿足經過S集合中任意頂點 v到w的路徑最短, 即滿足{v到w的路徑}最小的那個w。 其中v 屬于S, w屬于V-S。將w 加入S, 并從V-S中移除w；
（3）如此反復，直到V-S變空集為止。
說明：
①開始 S中只有源點s, 從V-S中選取離s最近的點w, 則s直接到w的路徑一定最短，將w加入S，并從V-S中移除w；s直接到w的路徑一定最短是因為如果存在另一個點w2, 使得 s->w2->w 的路徑比s 直接到w短，那么w2就是我們要選取的w。
②設經過算法的一些步驟后S中已有頂點v1,v2,...,vk，V-S中剩下頂點w1,w2,...,wn-k。下面選取V-S中離S集合最近的頂點w，用D[x]表示從源點到x的最短路徑長，則w必然滿足 D[w]=Min{D[v]+D[v to w]}，將w加入 S集合。這個w 此時一定取得了最短路徑D[w], 因為如果有其他的路徑，假設是 S集合某路徑->wi->w, 那么就應當去選取wi做為該點而不是w。因為 S集合某路徑長D[v] + D[v to wi ] < D[v]+D[v to w] 與w滿足的公式矛盾。
用迪杰斯特拉算法求單源最短路徑的過程：
以圖6.13為例說明求解過程：
①設源點為頂點0，
則S={0},V-S={1,2,3,4}；
②從S中的頂點0到V-S的頂點{1,2,3,4}的帶
權邊{<0,1>(10),<0,3>(30),<0,4>(100)}中取離
0最近的點1,將1加入S，并從V-S中移除1,則S={0,1(10)},V-S={2,3,4}；
③從S中的頂點{0,1}到V-S的頂點{2,3,4}的帶權邊{<0,3>(30), <0,4>(100),<1,2>(50)}中取離0最近的點3,將3加入S，并從V-S中移除3,則S={0,1(10),3(30)},V-S={2, 4}；
④從S中的頂點{0,1,3}到V-S的頂點{2,4}的帶權邊
{<0,4>(100),<1,2>(50),<3,2>(20),<3,4>(60)}中取離0最近的點2,將2加入S，并從V-S中移除2,則S={0,1(10), 3(30), 2(50)},V-S={4}；
⑤從S中的 {0,1,3,2}到V-S的頂點{4}的帶權邊{<0,4>(100), <3,4>(60),<2,4>(10)}中取離0最近的點4,將4加入S，并從V-S中移除4,則S={0,1(10), 3(30),2(50),4(60)},V-S=Φ。
6.6 拓撲排序
對一個有向無環圖G進行拓撲排序，是指將G中所有頂點排成一個線性序列，使得對圖中任意一對頂點u和v，若∈E(G),則u在線性序列中出現在v之前。通常將這樣的線性序列稱為滿足拓撲次序的序列，簡稱拓撲序列。若將圖中頂點按拓撲次序排成一行，則圖中所有的有向邊均是從左指向右的。顯然，若圖中存在有向環，則不可能使頂點滿足拓撲次序。
一個有向圖經常用來說明事件之間的先后關系。通常將事件表示為頂點，而事件間的依賴關系表示為有向邊。若事件u必須先于事件v完成且u完成后直接導致v的發生，則在頂點u和v有一條邊，可將u稱為v的直接前趨，v稱為u的直接后繼。1個DAG的拓撲序列通常表示某種方案切實可行。
表6.2 計算機專業的必修課示例
課程代號 課程名稱 先修課程
C0 高等數學 無
C1 程序設計基礎 無
C2 離散數學 C0,C1
C3 數據結構 C2,C4
C4 程序設計語言 C1
C5 編譯技術 C3,C4
C6 操作系統 C3,C8
C7 普通物理 C0
C8 計算機原理 C7
以表6.2為例說明上述的有關概念。該表可用有向圖G(見圖6.14（a）)更清楚地表示，圖中頂點表示課程代號，是一對有向邊當且僅當課程i是課程j的先修課程。因為該圖是一個DAG，故至少存在一個拓撲序列。一般情況下，一個DAG可能有多個拓撲序列。例如，我們對圖6.14（a）的圖進行拓撲排序，至少可得到如下的兩個（實際上遠不止兩個）拓撲序列：C0,C1,C2,C4,C3,C5,C7,C8,C6和C0,C7,C8,C1,C4,C2,C3,C6,C5.若某學生每學期只能修一門課程，則該生必須按某一拓撲序列安排學習計劃，方能保證學習任一課程時其先修課程均已學過。若將此圖按上述的第一個拓撲序列排成一行，則可得到該圖的另一表示（見圖6.15（b）），使得邊均從左指向右。
當有向圖存在環時，若將頂點排成一行，則無論如何安排，必定至少有一條邊是和其余邊反向的，亦即該圖的拓撲序列不存在。例如圖6.16 (a)圖中的有向環重排后如(b)所示，有向邊和其它邊反向。若有向圖被用來表示某項工程實施方案或某項工作計劃，則找不到該圖的拓撲序列(即含有向環)，就意味著該方案或計劃是不可行的。
圖6.16 有向環示例
對于一個有向圖的拓撲序列仔細分析，我們會發現這樣一個事實：在一個拓撲序列里，每個頂點必定出現在它的所有后繼頂點之前。因此我們有兩種方法對有向圖進行拓撲排序。
1.無前趨的頂點優先
該方法的每一步總是輸出當前無前趨(即入度為零)的頂點，其抽象算法可描述為：
NonPreFirstTopSort(G){//優先輸出無前趨的頂點
while(G中有人度為0的頂點)do{
從G中選擇一個人度為0的頂點v且輸出之；
從G中刪去v及其所有出邊；
}
if(輸出的頂點數目<|V(G)|)
//若此條件不成立，則表示所有頂點均已輸出，排序成功。
Error("G中存在有向環，排序失敗！")；
}
注意：無前驅的頂點優先的拓撲排序算法在具體存儲結構下，為便于考察每個頂點的入度，

展開更多......

收起↑