1、數(shù)據(jù)結構復習指導一數(shù)據(jù)：是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。是計算機加工的原料。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。數(shù)據(jù)項：有時，一個數(shù)據(jù)元素可由多個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。2、數(shù)據(jù)對象、數(shù)據(jù)結構數(shù)據(jù)對象：是性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結構：是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。四類基本結構：集合、線性結構、樹形結構、圖形結構或網(wǎng)狀結構。數(shù)據(jù)結構的形式定義：數(shù)據(jù)結構是一個二元組Data_Structure=(D,S)其中，D是數(shù)據(jù)元素的有限集，S是D上關系的有限集。數(shù)據(jù)結構一般包括三

2、方面的內容：邏輯結構：數(shù)據(jù)元素之間的邏輯關系。存儲結構(物理結構)：數(shù)據(jù)元素及其關系在計算機存儲器的表示。用于表示數(shù)據(jù)元素的位串稱之為元素或結點。用于表示數(shù)據(jù)項的位串稱之為數(shù)據(jù)域。數(shù)據(jù)的運算：對數(shù)據(jù)施加的操作。算法的設計取決于選定的數(shù)據(jù)邏輯結構，而算法的實現(xiàn)依賴于采用的存儲結構。數(shù)據(jù)的兩種存儲結構：順序存儲結構：把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現(xiàn)。通常順序存儲結構是借助于語言的數(shù)組來描述的。鏈式存儲結構：不要求邏輯上相鄰的結點物理上也相鄰，結點間的邏輯關系是由附加的指針字段表示的，通常要借助于語言的指針類型來描述。算法和算法分析1、算

3、法(Algorithm)是對特定問題求解步驟的一種描述，它是指令的有限序列。算法具有五個重要特性：有窮性、確定性、可行性、輸入、輸出2、算法設計的要求正確性、可讀性、健壯性和效率與低存儲量要求3、算法效率的度量算法時間是由控制結構和原操作的決定的。做法：選取一種是基本操作的原操作，以該基本操作重復的次數(shù)作為算法的時間量度。時間復雜度：算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，T(n)=O(f(n)它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同。語句的頻度：是改語句重復執(zhí)行的次數(shù)。4、算法的存儲空間需求空間復雜度：S(n)=O(f(n)第二章線性表線性結構

4、的特點：在數(shù)據(jù)元素的非空有限集中存在唯一的一個被稱做第一個的數(shù)據(jù)元素；存在唯一的一個被稱做最后一個的數(shù)據(jù)元素；除第一個之外，每個元素都只有一個前驅；除最后一個之外，每個元素都只有一個后繼。線性表的順序表示和實現(xiàn)1、線性表的順序表示：指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。用物理位置來表示邏輯結構。LOC(ai+1)=LOC(ai)+l LOC(ai)=LOC(a1)+(i-1)*l 2、順序表的特點：隨機存取的存儲結構。只要確定了存儲線性表的起始位置，線性表中的任一數(shù)據(jù)元素可隨機存取。3、線性表的動態(tài)分配順序存儲結構(用一維數(shù)組)#define LIST_INIT_SIZE 1

5、00#define LISTINCREAMENT 10 type structElemType*elem；int length；int listsize；SqList 4、順序線性表的操作順序表容易實現(xiàn)訪問操作，可隨機存取元素。但插入和刪除操作主要是移動元素。插入操作算法思想：在第i個位置上插入一個新元素，將第n至(i+1)個元素逐一向后移動一個位置。刪除操作：算法思想：刪除第i個元素，將第(i+1)至第n個元素逐一向前移動一個位置。線性表的鏈式存儲結構一、1、線性表的鏈式存儲結構的特點：是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素。數(shù)據(jù)元素的映象用一個結點來表示。結點的一個域表示元素本身，另一

6、個是能指示其后繼的指針，用來表示線性表數(shù)據(jù)元素的邏輯關系。結點(Node)、數(shù)據(jù)域、指針域、指針、鏈、頭指針2、鏈式存儲結構的特點：插入、刪除操作是不再需要移動大量的元素，但失去了順序表的可隨機存取特點。鏈表可分為單鏈表、循環(huán)鏈表和雙向鏈表。二、線性鏈表：1、單鏈表：鏈表中的每一個結點中只包含一個指針域的稱為單鏈表或線性鏈表。2、單鏈表的存儲結構單鏈表可由頭指針唯一確定，在C語言中，用結構指針來描述。typedef struc LNodeElemType data；struct LNode*nextLNode,*LinkList 3、單鏈表的操作：插入操作：要在數(shù)據(jù)元素a和b之間插入元素x。算

7、法思想：決定a和b之間的相鄰關系是由a的指針決定的。若要實現(xiàn)插入，生成x結點，然后讓a的指針指向x且x的指針指向b。實現(xiàn)三個元a、x和b的邏輯關系。設p為指向結點a的指針，s為指向結點x的指針，則修改s、a的指針：snext=pnext；pnext=s；刪除操作：在單鏈表數(shù)據(jù)元素a、b、c三個相鄰的元素中刪除b，算法思想：就是要讓a的指針直接指向c，使b從鏈表中脫離。即，pnext=pnextnext第三章棧和隊列棧1、堆棧的定義堆棧是只準在一端進行插入和刪除的線性表，稱為LIFO表。允許插入和刪除的一端叫棧頂，另一端叫棧底。棧的抽象數(shù)據(jù)類型：ADT Stack 2、堆棧的基本運算(1)入棧P

8、ush(&S,e)往棧S中插入一個元素e；(2)出棧Pop(&S,&e)棧頂指針下移；(3)取棧頂元素Gettop(&S,e)，將棧s的棧頂元素賦值給x；(4)判?？誗tackempty(&S)若?？?，則結果為true,否則為false；3、棧的順序存儲結構順序棧：利用一組地址連續(xù)的存儲單元依次存放自棧底到棧定的數(shù)據(jù)元素，同時附設指針top指示棧頂元素的在順序棧中的位置。typedef structSelemType*base；SelemType*top；int stacksize；SqStack；base：棧底指針，指向棧底的位置。base=NULL，棧的結構不存在top：棧頂指針，其初值指

9、向棧底，top=base是?？盏臉酥尽２迦霑r，top增1；刪除時，top-1；top始終在棧頂元素的下一個位置。隊列1、隊列的定義隊列是允許在一端進行插入而在另一端進行刪除的線性表。允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。隊列也稱為先進先出表(FIFO)。隊列的抽象數(shù)據(jù)類型：ADT Queue 2、隊列的運算(1)入隊Enqueue(&Q,e)在隊列Q中插入元素e。(2)出隊Dequeue(&Q,&e)若隊列Q不空，則刪除其隊頭元素。(3)取隊頭元素Gethead(&Q,&e)若隊列Q不空，用e返回隊頭元素。(4)判隊列是否為空Queueempty(Q)若隊列Q為空，返回true，否則

10、，返回false。3、隊列的鏈式表示和實現(xiàn)鏈隊列：用鏈表示的隊列typedef struct QNodeQelemType data；struct QNode*next；QNode,*QueuePtr；typedef structQueuePtr*front；QueuePtr*rear；front：隊頭指針，指向頭結點rear：隊尾指針，指向尾結點。空鏈隊列：隊頭指針和隊尾指針均指向頭結點。4、隊列操作在鏈式存儲結構下的實現(xiàn)(1)入隊Enqueue(&Q,e)p=(QueuePtr)malloc(sizeof(node)；/*生成結點*/p-data=e；p-next=NUllt；Q.rear

11、-next=p；Q.rear=p(2)出隊Dequeue(&Q,&e)if(Q.front=Q.rear)return Error；p=Q.front-next；e=p-data；Q.front-next=p-next；if(Q.rear=p)Q.rear=Q.front；free(p)；第四章串串類型的定義1、串：是由零個或多個字符組成的有限序列。S=a1 a2.an(n 0)串值：用單引號括起來的字符序列。長度：串中字符的數(shù)目?？沾洪L度為零。子串：子序列。位置：字符在序列中的序號。相等：當且僅當兩個串的值相等。空格串：由一個或多個空格組成的串。2、串的操作：以串的整體為操作對象。串的基本

12、操作：求串長(strlength)、串聯(lián)接(concat)、求子串(substring)、查子串的位置(index)、串的替換(replace)、插入子串(strinsert)、刪除子串(strdelete)串的最小操作子集：串賦值、串比較、求串長、串連接、求子串。串的表示和實現(xiàn)1、定長順序存儲表示表示：用一組地址連續(xù)的存儲單元存儲串值的字符序列?？捎枚ㄩL數(shù)組描述。#define MAXSTRLEN 255 typedef unsigned char SstringMAXSTRLEN+1；串操作的實現(xiàn)：實現(xiàn)串操作的原操作為字符序列的復制。操作的時間復雜度基于復制字符序列的長度。串連接：復制、截

13、尾。求子串：復制。2、堆分配存儲表示表示：以一組地址連續(xù)的存儲單元存放串值字符序列，但它們的存儲空間是在程序執(zhí)行的過程中動態(tài)分配而得。typedef structchar*ch；int length；Hstring；堆分配存儲結構有順序順序存儲結構的特點，處理方便，且操作中對串長沒有限制。第五章數(shù)組和廣義表第六章樹和二叉樹樹和二叉樹樹的定義和基本術語1、樹的定義樹是包含n個結點的有限集合(n 0)Tree=(D,R)其中，D是具有相同性質的數(shù)據(jù)元素的集合，若D中只有一個元素，則R為空集，否則R是D上某個二元關系H的集合，H是如下描述的二元關系：(1)在D中存在唯一一個稱為根的元素r0,它在關系

14、H下無前驅；(2)除結點r0外,K中每個結點對于關系H來說，都有且只有一個前驅。(3)結點r0外的任何結點r R，都存在一個結點序列r0,r1,.,rs,H(1=i=s),這樣一個結點序列稱為根到結點r的路徑。樹的例子：家族，機構等3、樹的表示方法樹形表示法：自然界倒長的樹(Knuth開初用正長的樹表示)文氏表示法：用集合表示凹入表示法：類似書目嵌套括號表示法：廣義表表示法表示的多樣性說明了樹的應用的廣泛性。4、樹的術語結點：數(shù)據(jù)元素和指向子樹的分枝；終端結點(葉子)，分枝結點子女：結點的子樹的根稱為結點的子女，該結點稱為子女的雙親；層次：根為第一層，根的子女為第二層，以此類推深度：樹中結點的

15、最大層次稱為樹的深度(或高度)度：結點的分枝數(shù)目樹的度：樹中結點的最大度兄弟：同一雙親的子女互稱兄弟，其父母為兄弟的結點互稱堂兄祖先：結點的祖先是從根到該結點所經(jīng)分支上的所有結點子孫：以某結點為根的子樹中的任一結點都稱為該結點的子孫。有序樹：結點的子樹從左到右有順序，否則，稱為無序樹森林：樹的不相交集合，除去根結點后的子樹集合就是森林二叉樹的概念及性質1、二叉樹的定義二叉樹的定義二叉樹是一種重要的樹型結構，它是n(n=0)個結點的有限集，其子樹分為互不相交的兩個集合，分別稱為左子樹和右子樹，左子樹和右子樹也是如上定義的二叉樹。二叉樹不是樹的特例。抽象數(shù)據(jù)類型二叉樹的定義：ADT BinaryT

16、ree數(shù)據(jù)對象D：數(shù)據(jù)關系R：基本操作P：二叉樹的5種形態(tài)空(二叉樹)；只有根結點；根結點和左子樹；根結點和右子樹；根結點和左右子樹。2、二叉樹的性質二叉樹的5個性質非常重要，都應會證明。(1)二叉樹的第i層至多有2i-1個結點；(2)深度為k的二叉樹至多有2k-1個結點；(3)對于任何一棵二叉樹T，若其終端結點(葉子)數(shù)為n0，度為1的結點數(shù)為n1，度為2的結點數(shù)n2，則n0=n2+1。該性質應擴展到K叉樹。在介紹第四個性質前，先介紹兩個概念：滿二叉樹：深度為k結點數(shù)為2k-1的二叉樹稱為滿二叉樹。完全二叉樹：若對滿二叉樹的結點從上到下從左至右進行編號，則深度為k且有n個結點的二叉樹，當且僅

17、當其每一個結點都與深度為k的滿二叉樹的編號從1到n一一對應時，稱為完全二叉樹。從完全二叉樹的定義可見，其葉子結點只能在最下面兩層上，且從左到右的排滿，即如果一個結點無左子樹，該結點肯定就不應有右子樹。(深度k的滿二叉樹可在最下層從右到左刪除0=n=2k-1-1個結點。)(4)具有n個結點的完全二叉樹的深度是ë；log2nû；+1；(5)對于一棵完全二叉樹，從上到下從左至右對結點進行編號，根結點為1，則對任一結點i(1=i=n)，有：若i=1,則結點是二叉樹的根，無雙親，否則，其雙親是ë；û；如果2i n，則結點i無左子女，否則，其左子女為2i；如果2i+1

18、n，則結點i無右子女，否則，其右子女為2i+1；3、二叉樹的存儲結構順序存儲結構#define MAX_TREE_SIZE 100 typedef TElemType SqBiTreeMAX_TREE_SIZE；SqBiTree bt；二叉樹按順序結構存儲必須按完全二叉樹形式，這樣，會浪費空間。例如，在最壞情況下，n個結點的單枝樹，要占用2n-1個元素的存儲空間。二叉鏈表lchild data rchild元素結點除包括元素自身的信息外，還包括指向其左右子樹的指針。即結點要包括數(shù)據(jù)域，左子樹指針域和右子樹指針域，可形式定義如下：typedef struct BiTNodeTElemType d

19、ata；struct BiTNode*lchild,*rchild；BiTNode,*Bitree；注意，n個結點的二叉樹有n+1個空鏈域。遍歷二叉樹遍歷是樹結構的一種常用的、重要的運算，是樹的其它運算的基礎。1、遍歷二叉樹結構的概念和方法遍歷也稱周游，是指按一定的規(guī)律，訪問二叉樹樹的結點，使每個結點被訪問一次，且只被訪問一次。訪問的含義可以是查詢某元素、修改某元素、輸出某元素的值，以及對元素作某種運算等等。遍歷的過程就是把非線性結構的二叉樹中的結點排成一個線性序列的過程。2、二叉樹的遍歷二叉樹遍歷方法可分為兩大類，一類是寬度優(yōu)先法，即從根結點開始，由上到下，從左往右一層一層的遍歷；另一類是深

20、度優(yōu)先法，即一棵子樹一棵子樹的遍歷。從二叉樹結構的整體看，二叉樹可以分為根結點，左子樹和右子樹三部分，只要遍歷了這三部分，就算遍歷了二叉樹。設D表示根結點，L表示左子樹，R表示右子樹，則DLR的組合共有6種，即DLR，DRL，LDR，LRD，RDL，RLD。若限定先左后右，則只有DLR，LDR，LRD三種，分別稱為先(前)序法(先根次序法)，中序法(中根次序法，對稱法)，后序法(后根次序法)。三種遍歷的遞歸算法如下：(1)先序法(DLR)若二叉樹為空，則空操作，否則：訪問根結點；先序遍歷左子樹；先序遍歷右子樹。(2)中序法(LDR)若二叉樹為空，則空操作，否則：中序遍歷左子樹；訪問根結點；中序

21、遍歷右子樹。(3)后序法(LRD)若二叉樹為空，則空操作，否則：后序遍歷左子樹；后序遍歷右子樹。訪問根結點；遍歷二叉樹的應用：(1)已知二叉樹的先序序列和中序序列，可以唯一確定一棵二叉樹。(2)已知二叉樹的后序序列和中序序列，可以唯一確定一棵二叉樹；3)已知二叉樹的先序序列和后序序列，不能唯一確定一棵二叉樹。樹的存儲結構1、雙親表示法以一組連續(xù)的存儲空間存放樹的結點，每個結點中附設一個指針指示其雙親結點在這連續(xù)的存儲空間中的位置(下標，這種結構屬靜態(tài)鏈表),可形式表示如下：typrdef struct tnodedatatype data；int parent；treen2、孩子表示法用多重鏈

22、表表示。有兩種方法：同構：按最大度的結點設置各結點結構，即一個數(shù)據(jù)域和d個指針域，這容易造成空間浪費；異構：結點有幾棵子樹設幾個指針，這樣操作困難。可將其子女鏈在一個單鏈表中。其形式描述如下：typrdef struct tagnode/*表結點*/int child；struct tagnode*next；node,*link；typedef struct/*頭結點*/datatype data；link headptr；headnode；typedef headnode childlinkmaxnode；/*表頭數(shù)組*/帶雙親的孩子鏈表表示法：typedef struct/*頭結點*/da

23、tatype data；int parent；link headptr；headnode1；3、孩子兄弟表示法該方法又稱二叉樹表示法，或二叉鏈表表示法，即以二叉鏈表作存儲結構，結點的兩個鏈域分別指向該結點的第一個孩子和下一個兄弟，分別命名為fch和nsib?？尚问矫枋鋈缦拢簍ypedef struct treenodedatatype data；struct treenode*fch,*nsib；treenode,*tree；樹的這種表示本質上是二叉樹的二叉鏈表表示。由于二叉樹和樹這種存儲結構的一致性，從而導致樹和二叉樹可以相互轉換。森林與二叉樹的相互轉換1、森林轉為二叉樹樹(樹林)轉換成二叉

24、樹時結果是唯一的。其轉換可以遞歸的描述如下：若樹(樹林)為空，則二叉樹為空；否則，樹(樹林)中第一棵樹的根是二叉樹的根，第一棵樹除去根結點后的子樹林是二叉樹的左子樹，樹林中除去第一棵樹后的樹林形成二叉樹的右子樹。形象的說轉換過程可用下面的三步曲來說明：三步曲：連線切線旋轉連線：將兄弟結點連接起來切線：保留雙親到第一個子女的連線，將雙親到其它子女的連線切掉。旋轉：以根為軸，平面向下順時針方向旋轉450。2、二叉樹轉為樹林二叉樹轉換成樹(樹林)時結果也是唯一的。其轉換可以遞歸的描述，若二叉樹為空，則樹(樹林)為空；否則，二叉樹的根是樹(樹林)中第一棵樹的根，二叉樹的左子樹構成樹(樹林)中第一棵樹除

25、去根結點后的子樹林，二叉樹的右子樹構成樹林中除去第一棵樹后的樹林。形象的說是上面三步曲的逆。哈夫曼樹最優(yōu)二叉樹(哈夫曼樹-帶權路徑長度最短的樹)哈夫曼樹的基本概念(1)路徑從樹中一個結點到另一個結點之間的分支。(2)路徑長度路徑上的分支數(shù)目稱為路徑長度。(3)樹的路徑長度從樹根到每一結點的路徑長度之和，稱為樹的路徑長度，完全二叉樹是路徑長度最短的二叉樹。(4)結點的帶權路徑長度從該結點到樹根之間的路徑長度和結點上權的乘積。(5)樹的帶權路徑長度樹中所有葉子結點的帶權路徑長度之和，通常記為WPL=wili，(6)哈夫曼樹(最優(yōu)二叉樹)帶權路徑長度之和最小的二叉樹稱為哈夫曼樹(最優(yōu)二叉樹)(7)哈

26、夫曼編碼在哈夫曼樹上，左分枝為0，右分枝為1，從根結點開始，直到葉子結點所組成的編碼序列，稱為葉子結點的哈夫曼編碼。如何構造哈夫曼樹(1)根據(jù)給定的n個權值w1,w2,.,wn，構成n棵二叉樹的集合F=T1,T2,.,Tn，每棵二叉樹Ti只有根結點。(2)在F中選兩棵根結點權值最小的樹作為左右子樹，構造一棵二叉樹，新二叉樹根結點的權值等于其左右子樹根結點權值之和。(3)在F中刪除這兩棵子樹，同時將新得到的二叉樹加入F中。(4)重復(2)和(3)，直到F中只剩一棵樹(即哈夫曼樹)為止。應該說明，哈夫曼樹的形態(tài)不是唯一的，但對具有一組權值的各哈夫曼樹的WPL是唯一的。第七章圖圖是重要的一類非線性結

27、構，應用極為廣泛。圖最早的應用一般都引用16世紀東普魯士的七橋問題。本章只介紹圖的基本概念、存儲結構、圖的遍歷和簡單應用。圖的定義和術語1、圖的定義圖是一種數(shù)據(jù)結構，其形式化定義可寫為Graph=(V,R)其中，V=x|x datatypeR=VRVR=|P(x,y)(x,y V)在圖中，數(shù)據(jù)元素常稱為頂點，V是頂點的有窮集合；R是邊(弧)的有窮集合。2、圖的術語概念(1)有向圖、無向圖?。?；邊(x,y)。(2)有(無)向完全圖稀疏圖稠密圖子圖無向完全圖：n個頂點n(n-1)/2條邊；有向完全圖：n個頂點n(n-1)條?。?3)權、網(wǎng)和邊(弧)相關的數(shù)叫權，帶權的圖稱網(wǎng)。(4)鄰接、鄰接點無向

28、圖：一條邊連起來的兩個頂點，互稱鄰接點；有向圖：若從頂點x到頂點y有一條弧，則說頂點x鄰接到頂點y，而頂點y鄰接自頂點x。(5)度、出度、入度無向圖中和頂點相關的邊(e)的個數(shù)叫頂點的度。e=有向圖中從頂點出發(fā)的弧的個數(shù)叫該頂點的出度，入到該頂點的弧的個數(shù)叫該頂點的入度。TD(v)=ID(v)+OD(v)(6)路徑、路徑長度、回路(環(huán))、簡單路徑(7)連通、連通圖、連通分量無向圖頂點v1到頂點v2有路徑，則說v1和v2連通。若任意兩個頂點都連通，則說該圖是連通的。連通分量是無向圖中的極大連通子圖。(8)強連通圖、強連通分量(9)生成樹、有向樹、生成森林一個連通圖的生成樹是一個極小連通子圖，它含

29、有圖的全部頂點，但只有足以構成一棵樹的n-1條邊。若有向圖中只有一個頂點的入度為0，其余頂點的入度均為1，則該有向圖稱為有向樹。有向圖的生成森林由若干棵有向樹組成，含有圖的全部頂點，但只有足以構成若干棵不相交的有向樹的弧。圖的遍歷圖的遍歷指，從圖的某頂點出發(fā)，訪問圖的各頂點，使每個頂點被訪問一次，且只被訪問一次。訪問的含義可以是輸出個頂點的值，查詢頂點，修改頂點等等。本節(jié)介紹圖的遍歷的兩種方法：深度優(yōu)先遍歷和寬度優(yōu)先遍歷，還介紹生成樹的概念。為了遍歷方便，設輔助數(shù)組visited，初始時，數(shù)組元素的值均為0或false，表示未被遍歷，一旦遍歷，就置為1或true。深度優(yōu)先遍歷深度優(yōu)先遍歷的思想

30、在圖中從任意一個頂點(設為v0)開始，進行遍歷,接著找v0的第一鄰接點，若該鄰接點未被遍歷，則遍歷之，再找該鄰接點的第一鄰接點，若該第一鄰接點已被遍歷，則找其下一鄰接點。若下一鄰接點未被遍歷，則遍歷，再找它的第一鄰接點，就這樣遞歸向下進行。若遇到第一鄰接點不存在，或下一鄰接點也不存在時，則退回到調用的上一層。如此下去，若不能遍歷完所有頂點(說明不是連通圖)，則再選一個未遍歷的頂點，重新開始以上過程，直至所有頂點遍歷完畢。廣度優(yōu)先遍歷寬度優(yōu)先遍歷的基本思想寬度優(yōu)先遍歷又稱廣度優(yōu)先遍歷，和樹的層次遍歷類似。從圖中任意一個頂點(設為v0)開始遍歷,接著依次遍歷v0的所有鄰接點(每個鄰接點被遍歷一次且

31、只一次)，再遍歷這些鄰接點的鄰接點，.。如此下去，若不能遍歷完所有頂點(說明不是連通圖)，則再選一個未遍歷的頂點，重新開始以上過程，直至所有頂點遍歷完畢。最小生成樹1、問題的提出假設n個城市間建立通信聯(lián)絡網(wǎng)，連通n個城市需要n-1條線路，而n個城市間最多有n(n-1)/2條線路，如何從n(n-1)/2條中選取n-1條線路，使總的耗費最少。2、由無向連通圖構造最小生成樹的方法(1)從圖中任意頂點開始，將其包括在最小生成樹中；(2)再選取權值最小的邊，使其一個頂點已在生成樹中，而另一個頂點尚不在生成樹中，將該頂點加入生成樹。若這樣的邊有多個，任選一個。(3)重復(2)，直至所有頂點都包括在生成樹中。這就是最小生成樹。具體說，構造最小生成樹有兩種方法：普里母(prim)和克魯斯卡爾(kruskal)方法。拓撲排序1、拓撲排序的基本概念(1)AOV網(wǎng)頂點表示活動，弧表示活動間的優(yōu)先關系的有向圖，叫頂點表示活動的網(wǎng)(Activity On Vertex Network)。(2)拓撲序列將AOV網(wǎng)上的所以頂點排成一個線性序列，且該序列滿足若在AOV網(wǎng)中，頂點vi到vj有一條路徑，則在該線性序列中vi必在vj的前面。這樣的序列稱為拓撲序列。(3)拓撲排序對AOV網(wǎng)構造拓撲序列的操作叫拓撲排序。(4)在AOV網(wǎng)中不應有環(huán)，否則就會自己以自