經(jīng)貿大學2016年數(shù)據(jù)結構總復習

1、數(shù)據(jù)結構總復習總復習第一章 緒論n重點內容重點內容p 邏輯結構和物理結構邏輯結構和物理結構p 順序存儲和鏈式存儲順序存儲和鏈式存儲p 算法的五個特性算法的五個特性p 算法的時間復雜度算法的時間復雜度p 邏輯結構：數(shù)據(jù)元素之間的邏輯關系。邏輯結構：數(shù)據(jù)元素之間的邏輯關系。p 物理結構（存儲結構）：數(shù)據(jù)結構在計算機中的表物理結構（存儲結構）：數(shù)據(jù)結構在計算機中的表示，包括數(shù)據(jù)元素的表示和關系的表示。示，包括數(shù)據(jù)元素的表示和關系的表示。3 順序存儲結構順序存儲結構：用數(shù)據(jù)元素在存儲器中用數(shù)據(jù)元素在存儲器中的的相對位置相對位置來表示數(shù)據(jù)元素之間的邏輯來表示數(shù)據(jù)元素之間的邏輯結構結構( (關系關系) )

2、。數(shù)據(jù)元素存放的地址是連數(shù)據(jù)元素存放的地址是連續(xù)的續(xù)的 鏈式存儲結構：借助指示元素存儲地址鏈式存儲結構：借助指示元素存儲地址得指針表示數(shù)據(jù)之間的邏輯關系。得指針表示數(shù)據(jù)之間的邏輯關系。數(shù)據(jù)數(shù)據(jù)元素存放的地址是否連續(xù)沒有要求元素存放的地址是否連續(xù)沒有要求45 順序存儲順序存儲以存儲位置的相鄰表示后繼關系y的存儲位置和x的存儲位置之間差一個常量C 鏈式存儲鏈式存儲以附加信息(指針)表示后記關系，需要用一個和x在一起的附加信息指示y的存儲位置x yyxp算法是為了解決某類問題而給出的一個有限長的算法是為了解決某類問題而給出的一個有限長的指指令序列令序列。p 算法有以下算法有以下5個特性：個特性：n有

3、窮性：有窮步驟，每步都有有窮的時間有窮性：有窮步驟，每步都有有窮的時間n確定性：每條指令有確定的含義確定性：每條指令有確定的含義n可行性：是能行的，基本運算的有限次運算完成可行性：是能行的，基本運算的有限次運算完成n輸入：輸入：0 0個或多個輸入，取自某個特定對象集合個或多個輸入，取自某個特定對象集合n輸出：一個或多個輸出，同輸入有某些特定關系輸出：一個或多個輸出，同輸入有某些特定關系6一個一個“好好”的算法需滿足：的算法需滿足：7程序程序中不含語法錯誤；中不含語法錯誤；程序對于幾組給定的輸入可得到滿足要求的結果程序對于幾組給定的輸入可得到滿足要求的結果程序對于精心挑選的、典型的輸入也可得到滿

4、足程序對于精心挑選的、典型的輸入也可得到滿足要求的結果要求的結果程序對于一切合法的輸入均可以得出滿足要求的程序對于一切合法的輸入均可以得出滿足要求的結果結果8算法主要是為算法主要是為了人的閱讀與交流了人的閱讀與交流，其次才是為計算機執(zhí)其次才是為計算機執(zhí)行行。因此算法應該易于人的因此算法應該易于人的理解理解；另另一方面，晦澀難讀的程序易于隱藏較多錯誤而一方面，晦澀難讀的程序易于隱藏較多錯誤而難以調試和修改。難以調試和修改。9當當輸入輸入的數(shù)據(jù)非法的數(shù)據(jù)非法時，算法應當給予時，算法應當給予恰當?shù)姆磻‘數(shù)姆磻蜻M行相應的處理或進行相應的處理，而不是產(chǎn)生系統(tǒng)錯誤或莫名，而不是產(chǎn)生系統(tǒng)錯誤或莫名其妙的

5、結果其妙的結果。 處理出錯處理出錯的方法不應是中斷程序的執(zhí)行，的方法不應是中斷程序的執(zhí)行，而應而應該返回錯誤提示該返回錯誤提示，以便在更高抽象層次上進行處，以便在更高抽象層次上進行處理理。10假設，隨著問題規(guī)模假設，隨著問題規(guī)模n的增長，算法執(zhí)行時的增長，算法執(zhí)行時間的增長率和間的增長率和f(n)的增長率相同，則可記作：的增長率相同，則可記作： T(n)=O(f(n)稱稱T(n)為算為算法的（漸進）時間復雜度法的（漸進）時間復雜度11原操作原操作：固有數(shù)據(jù)類型的操作。固有數(shù)據(jù)類型的操作。（如：（如：+，-，/，nextn 因此，因此，鏈表不是隨機存取結構鏈表不是隨機存取結構n 設單鏈表的長度為

6、設單鏈表的長度為n，要查找表中第，要查找表中第i個結點，個結點，僅當僅當1in時，時，i的值是合法的的值是合法的單鏈表的插入實現(xiàn)步驟實現(xiàn)步驟：n 首先，找到首先，找到ai-1所在所在的結點的結點pn 然后，生成一個數(shù)據(jù)域為然后，生成一個數(shù)據(jù)域為e的新結點的新結點s，n s結點作為結點作為p的直接后繼結點，作為的直接后繼結點，作為ai結點的直結點的直接前驅結點。接前驅結點。bpabpaes s-data=e;s-next=p-next; p-next=s;單鏈表的刪除實現(xiàn)步驟實現(xiàn)步驟：n 首先找到首先找到ai-1的位置的位置p；n 然后令然后令pnext指向指向ai的直接后繼結點，即把的直接后繼

7、結點，即把ai從鏈上摘下從鏈上摘下n 最后釋放結點最后釋放結點ai的空間的空間aipai-1ai+1 q=p-next;p-next=q-next; e=q-data; free(q);靜態(tài)鏈表011ZHAO22QIAN33SUN44LI55ZHOU66WU77ZHENG88WANG0910011ZHAO22QIAN33SUN44LI95ZHOU66WU77ZHENG88WANG09SHI510011ZHAO22QIAN33SUN44LI95ZHOU66WU87ZHENG88WANG09SHI510修改前修改前在第在第5個位置個位置插入插入SHI刪除刪除ZHENG循環(huán)鏈表n 循環(huán)鏈表循環(huán)鏈表(

8、Circular Linked List)：是一種頭尾相：是一種頭尾相接的鏈表。其特點是最后一個結點的指針域指向接的鏈表。其特點是最后一個結點的指針域指向鏈表的頭結點，鏈表的頭結點，整個鏈表的指針域鏈接成一個環(huán)整個鏈表的指針域鏈接成一個環(huán)。n 從循環(huán)鏈表的從循環(huán)鏈表的任意一個結點出發(fā)任意一個結點出發(fā)都可以找到鏈表都可以找到鏈表中的其它結點，使得表處理更加方便靈活。中的其它結點，使得表處理更加方便靈活。空表空表非空表非空表a1 a2 anhead head 雙向鏈表的插入SepabSepab雙向鏈表的插入雙向鏈表的插入n 算法主要語句算法主要語句 S=(DulNode *)malloc(size

9、of(DulNode);S-data=e;S-prior=p-prior; p-prior-next=S;S-next=p; p-prior=S; n 設要刪除設要刪除的結點為的結點為p ，刪除時直接先斷鏈，刪除時直接先斷鏈，再，再釋放結點。部分語句組如下：釋放結點。部分語句組如下：p-prior-next=p-next;p-next-prior=p-prior;free(p);與單鏈與單鏈表的插入和刪除操作不同的是，在表的插入和刪除操作不同的是，在雙向鏈表中雙向鏈表中插入插入和和刪除刪除必須同時必須同時修改兩個方向上修改兩個方向上的指針域的指向的指針域的指向。雙向鏈表的刪除a1a2a3p優(yōu)點

10、優(yōu)點：易于查詢，索引快：易于查詢，索引快 缺點缺點：擴展性弱，不易刪除、添加。：擴展性弱，不易刪除、添加。優(yōu)點優(yōu)點：擴展性強，易于刪除、添加：擴展性強，易于刪除、添加缺點缺點：不易于查詢，索引慢：不易于查詢，索引慢二者優(yōu)缺點正好是互補關系，根據(jù)實際情況選擇使二者優(yōu)缺點正好是互補關系，根據(jù)實際情況選擇使用用順序存儲與鏈式存儲的對比第三章 棧和隊列n重點內容重點內容p 棧和隊列邏輯結構的特點棧和隊列邏輯結構的特點p 順序棧的棧滿、?？张袛囗樞驐５臈M、?？张袛鄍 循環(huán)隊列的滿與空的判斷循環(huán)隊列的滿與空的判斷p 壓棧、出棧算法壓棧、出棧算法p 進隊列、出隊列算法進隊列、出隊列算法n 棧棧(Stack

11、)：限制在表尾進行插入：限制在表尾進行插入和刪除操作的線性表。又稱為后和刪除操作的線性表。又稱為后進先出進先出LIFO (Last In First Out)n 棧頂棧頂(Top)：允許進行插入、刪：允許進行插入、刪除操作的一端除操作的一端 n 棧底棧底(Bottom)：是固定端，又稱：是固定端，又稱為表頭。為表頭。n 空?？諚＃簍op=basen 滿棧滿棧: topmaxsize+1a1a2an棧頂棧頂棧底棧底進棧進棧(Push)出棧出棧(Pop) 采用一組地址連續(xù)的存儲單元依次存放自棧底到采用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素：棧頂?shù)臄?shù)據(jù)元素：n 用base表示棧底指針，

12、棧底固定不變的；棧頂則隨著進棧和退棧操作而變化。n 用top(稱為棧頂指針)指示當前棧頂位置。n 用top=base作為棧空的標記，每次top指向棧頂數(shù)組中的下一個存儲位置。n 結點進棧：首先將數(shù)據(jù)元素保存到棧頂(top所指的當前位置)，然后執(zhí)行top加1，使top指向棧頂?shù)南乱粋€存儲位置;n 結點出棧：首先執(zhí)行top減1，使top指向棧頂元素的存儲位置，然后將棧頂元素取出?？諚？諚?bottomtop元素元素a進棧進棧bottomtopa元素元素b，c進棧進棧bottomtopabc元素元素c退棧退棧bottomtopabbottomtopabdef元素元素d，e，f進棧進棧3 元素進棧元素

13、進棧Status push(SqStack S , ElemType e) /* 使數(shù)據(jù)元素使數(shù)據(jù)元素e進棧成為新的棧頂進棧成為新的棧頂 */if (S.top - S.base = S.stacksize) /棧滿棧滿 S.base=(SElemType *) realloc (S.base, (S.stacksize+STACKINCREMENT) * sizeof(SElemType); if (!S.base) exit (OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e ; /* 棧

14、頂指針加棧頂指針加1 */return OK; /* 壓棧成功壓棧成功 */4 彈棧彈棧( (元素元素出棧出棧) )Status pop( SqStack &S, SElemType &e ) /*彈出棧頂元素彈出棧頂元素*/ if ( S.top=S.base)return ERROR ; /* ?？眨祷劐e誤標志?？眨祷劐e誤標志 */e=*-S.top;return OK ; n 隊列隊列 (Queue)：也是運算受限的線性表。是：也是運算受限的線性表。是一種先一種先進先出進先出(First In First Out ，簡稱，簡稱FIFO)的線性表。的線性表。n 只允許在

15、表的一端進行插入，而在另一端進行刪只允許在表的一端進行插入，而在另一端進行刪除除n 隊頭隊頭 (front) ：允許進行刪除的一端稱為隊頭。：允許進行刪除的一端稱為隊頭。 n 隊尾隊尾 (rear) ：允許進行插入的一端稱為隊尾。：允許進行插入的一端稱為隊尾。a1 , a2 , , an出隊出隊入隊入隊隊尾隊尾隊頭隊頭 n 隊列的鏈式存儲結構簡稱為鏈隊列隊列的鏈式存儲結構簡稱為鏈隊列n 它是限制僅在表頭進行刪除操作和表尾進行它是限制僅在表頭進行刪除操作和表尾進行插入操作的單鏈表。插入操作的單鏈表。n 需要兩類不同的結點：需要兩類不同的結點：數(shù)據(jù)元素數(shù)據(jù)元素結點，隊列結點，隊列的的隊首指針和隊尾

16、指針隊首指針和隊尾指針的結點的結點datafront rear(a) 空隊列空隊列front rear(b) x入隊入隊 x front rear(c) y再入隊再入隊 y front rear x(d) x出隊出隊 y xfront rear設立一個隊首指針設立一個隊首指針front ，一個隊尾指針，一個隊尾指針rear ，分，分別指向隊首和隊尾元素別指向隊首和隊尾元素。 初始化初始化：front=rear=0。 入隊入隊：將新元素插入將新元素插入rear所指的位置，然后所指的位置，然后rear加加1。 出隊出隊：刪去刪去front所指的元素，然后加所指的元素，然后加1并返回被刪元并返回被刪

17、元素。素。 隊列為空隊列為空：front=rear。 隊滿隊滿：rear=MAX_QUEUE_SIZE-1(a) 空隊列空隊列Q.frontQ.rear(b) 入隊入隊3個元素個元素a3a2a1Q.frontQ.rear(c) 出隊出隊3個元素個元素Q.frontQ.rear(d) 入隊入隊2個元素個元素a5a4Q.frontQ.rearfront=rear=0將新元素插將新元素插入入rear所指的所指的位置，然后位置，然后rear加加1刪去刪去front所指所指的元素，然后的元素，然后加加1并返回被刪并返回被刪元素元素隊列已滿，隊列已滿，但仍有存儲但仍有存儲空間空間n 充分利用向量空間充分利

18、用向量空間，克服上述，克服上述“假溢出假溢出”現(xiàn)象現(xiàn)象n 將為隊列分配的向量空間看成為一個首尾相接將為隊列分配的向量空間看成為一個首尾相接的圓環(huán)，并稱這種隊列為的圓環(huán)，并稱這種隊列為循環(huán)隊列循環(huán)隊列123450循環(huán)循環(huán)隊列隊列frontrear123450(a) 空隊列空隊列frontrear(b) d, e, b, g入入隊隊frontdebgrear(c) d, e出隊出隊bgfrontrear(d) i, j, k入入隊隊bgfrontijkrear(e) b, g出隊出隊ijkrearfront(f) r, p, s, t入隊入隊ijkfrontrprearStatus EnQueue

19、(SqQueue Q , ElemType e) /* 將數(shù)據(jù)元素e插入到循環(huán)隊列Q的隊尾 */if (Q.rear+1)%MAXSIZE= Q.front)return ERROR; /* 隊滿，返回錯誤標志 */Q.baseQ. rear=e ; /* 元素e入隊 */Q.rear = (Q.rear+1) % MAXSIZE ; /* 隊尾指針向前移動 */return OK; /* 入隊成功 */Status DeQueue(SqQueue Q, ElemType &e) /* 將循環(huán)隊列Q的隊首元素出隊 */if (Q.front= Q.rear)return ERROR ;

20、 /* 隊空，返回錯誤標志 */e = Q.baseQ.front ; /* 取隊首元素 */Q.front = (Q.front+1)% MAXSIZE ; /* 隊首指針向前移動 */return OK ;第四章 串n重點內容重點內容p 串的基本概念串的基本概念n 串串( (字符串字符串) )：是零個或多個字符組成的有限序列：是零個或多個字符組成的有限序列。記作。記作： S=a1a2a3n 其其中中S是串名，是串名，ai(1in)是單個，是單個，可以是字母、數(shù)字或可以是字母、數(shù)字或其它字符。其它字符。n 串值串值：雙引號括起來的字符序列是串值。：雙引號括起來的字符序列是串值。n 串長串長：

21、串中所包含的字符個數(shù)稱為該串的長度。：串中所包含的字符個數(shù)稱為該串的長度。n 空串空串( (空的字符串空的字符串) )：長度為零長度為零的串稱為空串，它不包含任的串稱為空串，它不包含任何字符。何字符。n 空空格串格串( (空白串空白串) )：構成串的所有：構成串的所有字符都是空格字符都是空格的串稱為空的串稱為空白串。白串。注意注意：空串和空白串的不同，例如：空串和空白串的不同，例如 和和分分別表示長度為別表示長度為1 1的空白串和長度為的空白串和長度為0的空串。的空串。第五章 數(shù)組和廣義表n重點內容重點內容p 稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲p 廣義表的基本概念、求表頭、表尾操作廣義表的基

22、本概念、求表頭、表尾操作兩種順序存儲方式兩種順序存儲方式n 行優(yōu)先順序行優(yōu)先順序(Row Major Order) ：將數(shù)組元素按行排列，第將數(shù)組元素按行排列，第i+1個行向量緊接在第個行向量緊接在第i個行向量后面。對二維數(shù)組，按行優(yōu)個行向量后面。對二維數(shù)組，按行優(yōu)先順序存儲的線性序列為：先順序存儲的線性序列為： a11,a12,a1n, a21,a22,a2n , am1,am2,amn PASCAL、C是按行優(yōu)先順序存儲的是按行優(yōu)先順序存儲的n 列優(yōu)先順序列優(yōu)先順序(Column Major Order) ：將數(shù)組元素按列向量將數(shù)組元素按列向量排列，第排列，第j+1個列向量緊接在第個列向量

23、緊接在第j個列向量之后，對二維數(shù)組，個列向量之后，對二維數(shù)組，按列優(yōu)先順序存儲的線性序列為：按列優(yōu)先順序存儲的線性序列為： a11,a21,am1, a12,a22,am2, , an1,an2,anm FORTRAN是按列優(yōu)先順序存儲的是按列優(yōu)先順序存儲的 a11 a12 a1n a21 a22 a2n am1 am2 amnA=(a) 二維數(shù)組的表示形式二維數(shù)組的表示形式(b) 行優(yōu)先順序存儲行優(yōu)先順序存儲(c) 列列優(yōu)先順序存儲優(yōu)先順序存儲a11 a12 a1n第第 1行行a21 a22 a2n第第2行行am1 am2 Amn 第第m行行a11 a21 am1第第1列列a12 a22 a

24、m2第第2列列a1m a2m amn第第n列列 給每一對對稱給每一對對稱元素元素aij和和aji(ij)分配分配1 1個存儲空間個存儲空間，則，則n2個元素壓縮存儲到個元素壓縮存儲到n(n+1)/2個存儲空間個存儲空間 假設按假設按“行優(yōu)先順序行優(yōu)先順序”存儲下三角形中的元素。存儲下三角形中的元素。 設用一維數(shù)組設用一維數(shù)組( (向量向量) )sa0n(n+1)/2存儲存儲n階對稱階對稱矩陣，矩陣， 為便于訪問，找出矩陣為便于訪問，找出矩陣A中的元素的下標值中的元素的下標值（i,j）和和向量向量sak的的下標值下標值k之間的對應關系。之間的對應關系。sa a00 a10 a11 an-1,0

25、an-1,1 an-1,n-1K 1 2 3 4 n(n-1)/2 n(n+1)/2對稱矩陣的對稱矩陣的壓縮存儲示例壓縮存儲示例n 廣義表廣義表(Lists，又稱為列表，又稱為列表 )：是由：是由n(n 0)個個元素組成的有窮序列：元素組成的有窮序列： LS=(a1，a2，an) a1(表中第一個元素表中第一個元素)稱為稱為表頭表頭； 其余元素組成的子表稱為其余元素組成的子表稱為表尾表尾；(a2，a3，an) 廣義表中所包含的元素廣義表中所包含的元素(包括原子和子表包括原子和子表)的的個數(shù)稱為個數(shù)稱為表的長度表的長度。 廣義表中括號的最大層數(shù)稱為表深廣義表中括號的最大層數(shù)稱為表深 (度度)。第

26、六章 樹和二叉樹n重點內容重點內容p 樹和二叉樹的定義及相關概念樹和二叉樹的定義及相關概念p 二叉樹的二叉樹的5 5個性質個性質p 二叉樹的各種存儲結構二叉樹的各種存儲結構p 樹的各種存儲結構樹的各種存儲結構p 二叉樹的各種遍歷方法、中序遍歷算法二叉樹的各種遍歷方法、中序遍歷算法p 線索二叉樹的畫法線索二叉樹的畫法p 樹的兩種遍歷方法樹的兩種遍歷方法p 哈夫曼樹的構造、哈夫曼編碼方法哈夫曼樹的構造、哈夫曼編碼方法樹樹的的基本術語基本術語n 結點結點(node)：數(shù)據(jù)元素：數(shù)據(jù)元素若干指向其子樹的分支若干指向其子樹的分支n 結點的度結點的度(degree) ：結點所擁有的子樹的個數(shù)稱為：結點所擁

27、有的子樹的個數(shù)稱為結點的度結點的度。n 樹樹的度：的度：樹中結點度的樹中結點度的最大值最大值。AABDCEGFHIMJNKL只有根結點只有根結點樹的基本術語樹的基本術語n葉子結點葉子結點：即度為即度為0 0的結點的結點n分支結點分支結點：除葉子結點之外的其它結點除葉子結點之外的其它結點n孩子孩子(Child)(Child)：若結點若結點x x有子樹，則子樹的根結有子樹，則子樹的根結點是點是x x的孩子。的孩子。n雙親(Parent)：若x有孩子結點，則該x結點稱為其孩子結點的雙親結點。58ABDCEGFHIMJNKL樹的基本術語樹的基本術語n兄弟結點：同一個雙親的孩子結點n祖先結點：從根結點到

28、該結點所經(jīng)路徑上的所有結點。n子孫結點：以某個結點為根的子樹以某個結點為根的子樹中的任何一個結點都稱為該結點的子孫結點n結點的層次：從根開始定義，根為第1層，根的孩子為第2層n堂兄弟：雙親結點在同一層上雙親結點在同一層上59ABDCEGFHIJ樹的基本術語樹的基本術語n 有序樹有序樹：樹中各個節(jié)點的子樹樹中各個節(jié)點的子樹T1，T2，T3，之間是之間是有次序的有次序的，即，即為有序樹。即各個子樹之間的左為有序樹。即各個子樹之間的左右次序不能互換右次序不能互換n 無序樹無序樹：樹中各個節(jié)點的子樹樹中各個節(jié)點的子樹T1，T2，T3，之間之間沒有次序關系沒有次序關系的，的，即為無序樹。即為無序樹。60

29、ABCDEACBDE樹的基本術語樹的基本術語n 樹的深度樹的深度：樹中節(jié)點的樹中節(jié)點的最大層次，最大層次，也稱為樹的也稱為樹的高度或深度。高度或深度。61ABCDDEFHIJKLM第第1層層第第2層層第第3層層第第4層層62二叉樹的定義二叉樹的定義n 二叉樹或者為空樹二叉樹或者為空樹n 或是由一個根結點加上兩棵分別稱為或是由一個根結點加上兩棵分別稱為左子樹左子樹和和右子樹右子樹的、的、互不相交互不相交的二叉樹組成。的二叉樹組成。EGBEFAAAAA(a)(b)(c)(d)(e)二叉樹有二叉樹有5種基本形態(tài)：種基本形態(tài)：二叉樹的特點：二叉樹的特點：1）每個結點的度）每個結點的度1，則其，則其雙親

30、結點雙親結點parent(i) 的編號是的編號是 i/2 。如果如果2in，則編號為，則編號為 i 的結點無左孩子（編號為的結點無左孩子（編號為 i 的結點為葉子結的結點為葉子結點）；否則其左孩子結點點）；否則其左孩子結點LChild(i)的編號是的編號是2i 。如果如果2i+1n，則編號為，則編號為 i 的結點無右孩子；否則其右孩子結點的結點無右孩子；否則其右孩子結點 RChild(i) 的編號是結點的編號是結點2i+1。ii+12i2i+12i+22i+3 i/2 (a) i和和i+1結點在同一層結點在同一層i+12i+22i+3i2i2i+1(b) i和和i+1結點不在同一層結點不在同一

31、層順序存儲結構順序存儲結構 二叉樹存儲結構的類型定義：二叉樹存儲結構的類型定義：# define MAX_SIZE 100 typedef telemtype sqbitreeMAX_SIZE;SqBiTree bt;n 用一組地址連續(xù)的存儲單元依次用一組地址連續(xù)的存儲單元依次“自上而下自上而下、自左自左至右至右”存儲完全二叉樹存儲完全二叉樹的數(shù)據(jù)元素的數(shù)據(jù)元素。n 對于完全二叉樹上對于完全二叉樹上編號為編號為i的結點元素存儲在一維的結點元素存儲在一維數(shù)組的下標值為數(shù)組的下標值為i-1的分量中的分量中n 對于一般的二叉樹，對于一般的二叉樹，將其每個結點與完全二叉樹上將其每個結點與完全二叉樹上的

32、結點相對照的結點相對照，存儲在一維數(shù)組中存儲在一維數(shù)組中abcdhiejklfg(a) 完全二叉樹完全二叉樹(b) 非完全二叉樹非完全二叉樹abcdefgh000 0 1 2 3 4 5 6 7 8 9 10 11 a b c d e f g h i j k l (c) 完全二叉樹的順序存儲形式完全二叉樹的順序存儲形式0 1 2 3 4 5 6 7 8 9 10 a b c d e 0 h 0 0 f g(d) 非完全二叉樹的順序存儲形式非完全二叉樹的順序存儲形式最壞的情況下，一個深度為最壞的情況下，一個深度為k且且只有只有k個結點的單支樹需要長度個結點的單支樹需要長度為為2k-1的一維數(shù)組的

33、一維數(shù)組。鏈式存儲結構鏈式存儲結構 二叉鏈表二叉鏈表。結點有三個域：結點有三個域：一個數(shù)據(jù)域一個數(shù)據(jù)域，兩個分別指向左右子結，兩個分別指向左右子結點的點的指針域指針域 typedef struct BTNode ElemType data ; struct BTNode *Lchild , *Rchild ; BTNode ; Lchild data Rchild(a) 二叉鏈表結點二叉鏈表結點 三三叉鏈表叉鏈表除二叉鏈表的三個域外，再增加一個指針域，除二叉鏈表的三個域外，再增加一個指針域，用來用來指向指向結點的父結點結點的父結點typedef struct BTNode_3 ElemType

34、 data ;struct BTNode_3 *Lchild , *Rchild , *parent ;BTNode_3 ; Lchild data parent Rchild三三叉鏈表結點叉鏈表結點(2) 二叉樹的鏈式存儲形式二叉樹的鏈式存儲形式(a) 二叉樹二叉樹afedcbg(c) 三三叉鏈表叉鏈表 a b c d e f g T(b) 二二叉鏈表叉鏈表 a b c d e g f T1 雙親表示法雙親表示法typedef struct PTNode NodesMAX_SIZE ;int r，n; / 根結點位置，結根結點位置，結點數(shù)點數(shù) Ptree ; FGHIRABCDE 樹的雙親存

35、儲結構樹的雙親存儲結構R -10A 01B 02C 03D 14E 15F 36G 67H 68I 69r=0n=10n 這種存儲結構利用了任一結點的這種存儲結構利用了任一結點的雙親結點唯一的性質。雙親結點唯一的性質?？梢苑奖憧梢苑奖愕刂苯诱业饺我唤Y點的雙親地直接找到任一結點的雙親n 但求結點的孩子結點時需要掃描但求結點的孩子結點時需要掃描整個數(shù)組。整個數(shù)組。nodes789 35 012 6 0123456789MAX_NODE-1rnA B C D E F G H I R 410孩子鏈表存儲結構孩子鏈表存儲結構孩子鏈表表示法孩子鏈表表示法FGHIRABCDE(b) 樹樹 FGRABCDE(

36、c) 孩子兄弟存儲結構孩子兄弟存儲結構 R A D C G B F E 孩子結點孩子結點兄弟結點兄弟結點firstchild data nextsibing(a) 結點結構結點結構3 孩子兄弟孩子兄弟表示法表示法先左先左后右的遍歷算法后右的遍歷算法n 先先(根根)序序的遍歷的遍歷算法算法DLRn 中中(根根)序序的遍歷的遍歷算法算法LDRn 后后(根根)序序的遍歷的遍歷算法算法LRD77根左左子樹子樹右右子樹子樹78n 遍歷序列可否唯一確定一棵二叉樹？遍歷序列可否唯一確定一棵二叉樹？ 先序序列：先序序列：ABIDEFGCHJ 中序序列：中序序列：IBFEDGAJHCABCIDEFGHJn 遍歷

37、二叉樹遍歷二叉樹的結果是求得結點的一個線性序列的結果是求得結點的一個線性序列。n 指向該線指向該線性序列中的性序列中的“前驅前驅”和和“后繼后繼”的指針，稱作的指針，稱作“線索線索”。n 包含包含“線索線索”的的存儲結構存儲結構稱作稱作“線索鏈表線索鏈表”；與其相應的；與其相應的二叉樹，稱為二叉樹，稱為“線索二叉樹線索二叉樹”。79AFHIEGBDCAFHIEGBDCNIL前序遍歷結點序列：前序遍歷結點序列：ABDCEGFHIAFHIEGBDC(a) 二叉樹二叉樹 (b) 先序線索樹的邏輯形式先序線索樹的邏輯形式 結點序列：結點序列：ABDCEGFHIAFHIEGBDCNIL(d) 后序線索樹

38、的邏輯形式后序線索樹的邏輯形式 結點序列：結點序列：DBGEHIFCA(c) 中序線索樹的邏輯形式中序線索樹的邏輯形式 結點序列：結點序列：DBAGECHFIAFHIEGBDCNILNILAFHIEGBDCNILn 線索二叉樹的指針信息存儲在哪里？線索二叉樹的指針信息存儲在哪里？p 設一棵二叉樹有設一棵二叉樹有n個結點，則有個結點，則有n-1條邊條邊 (指針指針連線連線) ， 而而n個結點共有個結點共有2n個指針域個指針域 (Lchild 和和 Rchild) ，顯然，顯然有有n+1個空閑指針域個空閑指針域未用。未用。p 可以利用這些空閑的指針域來存放結點的可以利用這些空閑的指針域來存放結點的

39、直直接前驅接前驅和和直接后繼直接后繼信息。信息。81對結點的指針域做如下規(guī)定：對結點的指針域做如下規(guī)定：n 若結點有左子樹，則若結點有左子樹，則Lchild指向其左子樹，指向其左子樹，Ltag0；否否則，指向其直接前驅，則，指向其直接前驅，Ltag1；n 若結點有右子樹，則若結點有右子樹，則Rchild指向其右子樹，指向其右子樹，Rtag0；否否則，指向其直接后繼，則，指向其直接后繼，Rtag1；Lchild Ltag data Rchild Rtag線索二叉樹的結點結構線索二叉樹的結點結構0：Lchild域指示結點的左孩子域指示結點的左孩子1 1：Lchild域指示結點的前驅域指示結點的前驅

40、Ltag=0 0：Rchild域指示結點的右孩子域指示結點的右孩子1 1：Rchild域指示結點的后繼域指示結點的后繼Rtag=6.4.3 樹和森林的遍歷樹和森林的遍歷1 樹的遍歷樹的遍歷 由樹結構的定義可知，樹的遍歷有二種方法。由樹結構的定義可知，樹的遍歷有二種方法。(1) 先根序遍歷先根序遍歷：先訪問根結點，然后：先訪問根結點，然后先序遍歷完先序遍歷完每棵子樹。每棵子樹。 (2) 后根序遍歷后根序遍歷：先：先依次后序遍歷完依次后序遍歷完每棵子樹，然后訪問根結每棵子樹，然后訪問根結點。點。ABDCKGJIFHE先序遍歷：先序遍歷：ABCDEFGIJHK后序遍歷：后序遍歷：CDBFIJGHEK

41、A基本概念基本概念 結點路徑結點路徑：從樹中一個結點到另一個結點的之間的分支：從樹中一個結點到另一個結點的之間的分支構成這兩個結點之間的路徑。構成這兩個結點之間的路徑。 路徑長度路徑長度：結點路徑上的分支數(shù)目稱為路徑長度：結點路徑上的分支數(shù)目稱為路徑長度。 樹的路徑長度樹的路徑長度：從樹根到每一個結點的路徑長度之和：從樹根到每一個結點的路徑長度之和。ABDCKGJIFHEA到到F ：結點路徑：結點路徑 AEF ；路徑長度路徑長度( (即邊的數(shù)目即邊的數(shù)目) )：2 ；樹的路徑長度樹的路徑長度：31+52+23=19 結點的帶權路徑長度結點的帶權路徑長度：從該結點的到樹的根結點之間的路：從該結點

42、的到樹的根結點之間的路徑長度與結點的權徑長度與結點的權( (值值) )的乘積的乘積。權權( (值值) )：各種：各種開銷開銷、代價代價、頻度頻度等的抽象稱呼等的抽象稱呼。 樹的帶權路徑長度樹的帶權路徑長度：樹中：樹中所有葉子結點所有葉子結點的帶權路徑長度之的帶權路徑長度之和，記做：和，記做： WPL=w1 l1+w2 l2+ +wn ln=wi li (i=1,2, ,n)其中：其中：n為葉子結點的個數(shù)為葉子結點的個數(shù)；wi為第為第i個結點的權值個結點的權值； li為第為第i個結點的路個結點的路徑長度。徑長度。 Huffman樹樹：具有：具有n個葉子結點個葉子結點(每個結點的權值為每個結點的權

43、值為wi) 的的二叉樹不止一棵，但在所有的這些二叉樹中，必定存在一棵二叉樹不止一棵，但在所有的這些二叉樹中，必定存在一棵WPL值最小的樹值最小的樹，稱這棵樹為，稱這棵樹為Huffman樹樹(或稱最優(yōu)樹或稱最優(yōu)樹) 。基本概念基本概念Huffman樹的構造樹的構造根據(jù)根據(jù)n個權值個權值w1, w2, ,wn，構造成，構造成n棵二叉樹的集合棵二叉樹的集合F=T1, T2, ,Tn，其中每棵二叉樹只有一個權值為，其中每棵二叉樹只有一個權值為wi的的根結點，沒有左、右子樹；根結點，沒有左、右子樹；在在F中中選取兩棵根結點權值最小選取兩棵根結點權值最小的樹作為左的樹作為左、右子樹構造右子樹構造一棵新的二

44、叉樹，且新的二叉樹根結點權值為其左一棵新的二叉樹，且新的二叉樹根結點權值為其左、右子右子樹根結點的權值之和；樹根結點的權值之和；在在F中刪除這兩棵樹，同時將新得到的樹加入中刪除這兩棵樹，同時將新得到的樹加入F中；中；重復、，直到重復、，直到F只含一顆樹為止。只含一顆樹為止。規(guī)定規(guī)定F=T1,T2, ,Tn中中權值小權值小的二叉樹作為新構造的二叉的二叉樹作為新構造的二叉樹的樹的左子樹左子樹，權值大的二叉樹作為新構造的二叉樹的右子權值大的二叉樹作為新構造的二叉樹的右子樹樹；在取值相等時，在取值相等時，深度小深度小的二叉樹作為新構造的二叉樹的的二叉樹作為新構造的二叉樹的左左子樹子樹，深度大的二叉樹作

45、為新構造的二叉樹的右子樹深度大的二叉樹作為新構造的二叉樹的右子樹。 權值集合權值集合W=8, 3, 4, 6, 5, 5構造構造Huffman樹的過樹的過程程。所構造的所構造的Huffman樹的樹的WPL是是： WPL=6 2+3 3+4 3+8 2+5 3+5 3 =79345568第一步5568第二步34768第三步34755108第四步5510634713第六步1111100000855101863471331第五步8551018634713例子例子Huffman編碼編碼p在電報收發(fā)等數(shù)據(jù)通訊中在電報收發(fā)等數(shù)據(jù)通訊中，常需要將傳送的文字常需要將傳送的文字轉換成由二進制字符轉換成由二進制字

46、符0、1組成的字符串來傳輸組成的字符串來傳輸。n 為了使收發(fā)的速度提高為了使收發(fā)的速度提高，要求電文要求電文編碼要盡可編碼要盡可能短能短。n 要設計要設計長短不等長短不等的編碼，還必須保證的編碼，還必須保證任意字符任意字符的編碼都不是另一個字符編碼的前綴的編碼都不是另一個字符編碼的前綴，稱為，稱為前前綴編碼綴編碼。pHuffman樹可以用來構造編碼長度不等且譯碼不樹可以用來構造編碼長度不等且譯碼不產(chǎn)生二義性的編碼產(chǎn)生二義性的編碼。Huffman編碼方法編碼方法 設電文中的字符集設電文中的字符集C=c1,c2, ,ci, ,cn，各個字符，各個字符出現(xiàn)的次數(shù)或頻度集出現(xiàn)的次數(shù)或頻度集W=w1,w

47、2, ,wi, ,wn。 以以字符集字符集C作為葉子結點作為葉子結點，次數(shù)或頻度集次數(shù)或頻度集W作為結作為結點點的權值的權值來構造來構造Huffman樹樹。 規(guī)規(guī)定定Huffman樹中左分支代表樹中左分支代表“0”，右分支代表，右分支代表“1” 。 從根結點到每個葉子結點所經(jīng)歷從根結點到每個葉子結點所經(jīng)歷的路徑分支上的的路徑分支上的“0”或或“1”所組成的字符串所組成的字符串，為該結點所對應的編碼為該結點所對應的編碼，稱稱之為之為Huffman編碼編碼。 * *由于每個字符都是葉子結點由于每個字符都是葉子結點，不可能出現(xiàn)在根結點到其它字符，不可能出現(xiàn)在根結點到其它字符結點的路徑上，所以一個字符

48、的結點的路徑上，所以一個字符的Huffman編碼不可能是另一個字編碼不可能是另一個字符的符的Huffman編碼的前綴編碼的前綴。第七章 圖n重點內容重點內容p 圖的定義及相關術語圖的定義及相關術語p 圖的各種存儲結構圖的各種存儲結構p 圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷法圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷法p 圖的最小生成樹的概念圖的最小生成樹的概念p 克魯斯卡爾算法、普里姆算法生成最小生成樹克魯斯卡爾算法、普里姆算法生成最小生成樹p 圖的拓撲排序、關鍵路徑的求法圖的拓撲排序、關鍵路徑的求法917.2 圖的存儲結構圖的存儲結構圖的數(shù)組存儲表示法基本思想基本思想：n 對于對于有有n個頂點的圖，用一維數(shù)組

49、個頂點的圖，用一維數(shù)組vexsn存存儲頂點信儲頂點信息息n 用二維數(shù)組用二維數(shù)組Ann存儲頂點之間關系的信存儲頂點之間關系的信息息n 該二維數(shù)組稱為該二維數(shù)組稱為鄰接矩陣鄰接矩陣n 在鄰接矩陣中在鄰接矩陣中：p 以頂點在vexs數(shù)組中的下標代表頂點p 鄰接矩陣中的元素Aij存放的是頂點i到頂點j之間關系的信息921 無向圖的數(shù)組表示無向圖的數(shù)組表示(1) 無權圖的鄰接矩陣無權圖的鄰接矩陣 無向無權圖無向無權圖G=(V，E)有有n(n1)個頂點，其鄰接矩陣是個頂點，其鄰接矩陣是n階對稱方陣階對稱方陣，其元素的定義如下：，其元素的定義如下：1 若若(vi , vj) E，即，即vi , vj鄰接鄰

50、接0 若若(vi , vj) E，即，即vi , vj不鄰接不鄰接Aij=(a) 無向圖無向圖 abcd(b) 頂點矩陣頂點矩陣vexsabcd0 1 1 11 0 1 11 1 0 11 1 1 0(c) 鄰接矩陣鄰接矩陣(2) 帶權圖（網(wǎng)）的鄰接矩陣帶權圖（網(wǎng)）的鄰接矩陣 無向帶權圖無向帶權圖G=(V，E) 的鄰接矩陣元素的定義如下：的鄰接矩陣元素的定義如下：帶權無向圖帶權無向圖 鄰接矩陣鄰接矩陣354126abcde3vexsabcde 6 2 6 3 4 32 3 1 4 3 5 3 5 Wij 若若(vi , vj) E，即，即vi , vj鄰接，權值為鄰接，權值為wij 若若(vi

51、 , vj) E，即，即vi , vj不鄰接時不鄰接時Aij=特點：特點：1、無向圖的鄰接矩陣是、無向圖的鄰接矩陣是對稱方陣對稱方陣；2、頂點、頂點vi的度數(shù)的度數(shù)是第是第i行的行的非非0元素的個數(shù)元素的個數(shù)；3 3、無向圖的邊數(shù)是上無向圖的邊數(shù)是上(或下或下)三角形矩陣中三角形矩陣中非非0元元素個數(shù)素個數(shù)。952 有向圖的數(shù)組表示有向圖的數(shù)組表示(1) 無權圖的鄰接矩陣無權圖的鄰接矩陣 有向無權圖有向無權圖G=(V，E)有有n(n1)個頂點，則其鄰接矩個頂點，則其鄰接矩陣是陣是n階對稱方陣階對稱方陣元素定義如下：元素定義如下：1 若若 E，從，從vi到到vj有弧有弧Aij=0 若若 E 從從

52、vi到到vj 沒有弧沒有弧(a) 有向圖有向圖acbde(b) 頂點矩陣頂點矩陣abcde(c) 鄰接矩陣鄰接矩陣0 1 1 0 10 0 0 0 00 0 0 1 11 1 0 0 00 0 0 1 0(2) 帶權圖的鄰接矩陣帶權圖的鄰接矩陣 有向帶權圖有向帶權圖G=(V，E)的鄰接矩陣元素的定義如下：的鄰接矩陣元素的定義如下：wij 若若 E，即，即vi , vj鄰接，權值為鄰接，權值為wij 若若 E，即，即vi , vj不鄰接時不鄰接時Aij=(b) 頂點矩陣頂點矩陣abcde(c) 鄰接矩陣鄰接矩陣 6 2 3 3 1 4 5 (a) 帶權有向圖帶權有向圖 354126abcde3特

53、點：特點：1 1、對于頂點對于頂點vi，第第i行行的非的非0元素的個數(shù)是其出度元素的個數(shù)是其出度OD(vi)；第第i列列的非的非0元素的個數(shù)是其入度元素的個數(shù)是其入度ID(vi) 。2、鄰接矩陣中、鄰接矩陣中非非0元素的個數(shù)就是圖的元素的個數(shù)就是圖的弧的數(shù)目弧的數(shù)目。7.2.2 鄰接鏈表法鄰接鏈表法 基本基本思想思想：n 對圖對圖的的每個頂點每個頂點建立一個建立一個單鏈表單鏈表，存儲該頂點所有，存儲該頂點所有鄰接頂點及其相關信息鄰接頂點及其相關信息。n 每一個單鏈表設一個每一個單鏈表設一個表頭結點表頭結點。n 第第i個單鏈表個單鏈表: 表示依附于頂點表示依附于頂點Vi的邊的邊 (對有向圖是以對

54、有向圖是以頂點頂點Vi為尾的為尾的弧弧)。1 結點結構與鄰接鏈表示例結點結構與鄰接鏈表示例n 鏈表中的結點稱為鏈表中的結點稱為表結點表結點，表結點由三個域組，表結點由三個域組成：成：p 鄰鄰接點域：指示與頂點接點域：指示與頂點Vi鄰接的頂點在圖鄰接的頂點在圖中的位置中的位置p 鏈域：指向下一個與頂點鏈域：指向下一個與頂點Vi鄰接的表結點，鄰接的表結點，p 數(shù)據(jù)域：存儲和邊或弧相關數(shù)據(jù)域：存儲和邊或弧相關的信息，如權值等。的信息，如權值等。n表頭結點表頭結點(稱為稱為頂點結點頂點結點)，由兩個域組成：，由兩個域組成：p 鏈域：指向鏈表鏈域：指向鏈表中的第一個結點中的第一個結點p 數(shù)據(jù)域數(shù)據(jù)域：

55、存儲頂點名或其他信息。存儲頂點名或其他信息。adjvex info nextarc表結點表結點：data firstarc表頭結點表頭結點：n 所有所有頂點結點頂點結點用一個向量以順序結構形式存儲，可用一個向量以順序結構形式存儲，可以隨機訪問任意頂點的鏈表，該向量稱為以隨機訪問任意頂點的鏈表，該向量稱為表頭向量表頭向量n 向向量的下標指示量的下標指示頂點的位置頂點的位置？v1v2v3v4v501234v1 v2v3 v4 v5 213 02 0314 204 23 無向圖鄰接表無向圖鄰接表有向圖有向圖v1v2v3v4v513 014 2 3 01234v1v2 v3v4 v5正鄰接鏈表正鄰接鏈

56、表出度直觀出度直觀2 02 2 01234MAX_VEX-1v1 v2 v3 v4 v53 04 逆鄰接鏈表逆鄰接鏈表入度直觀入度直觀有向圖鄰接表有向圖鄰接表n 有向圖的鄰接表有兩有向圖的鄰接表有兩種：種：正鄰接表正鄰接表和和逆鄰逆鄰接表接表n 正鄰接表正鄰接表是以頂點是以頂點Vi為出為出度而度而建立的鄰接表建立的鄰接表；n 逆鄰接表逆鄰接表是以頂點是以頂點Vi為入為入度而度而建立的鄰接表；建立的鄰接表；2 鄰接表法的特點鄰接表法的特點n 表頭向量中每個分量就是一個單鏈表的頭結點，表頭向量中每個分量就是一個單鏈表的頭結點，分量個數(shù)分量個數(shù)就是圖中的頂點數(shù)目就是圖中的頂點數(shù)目；n 在在邊或弧稀疏

57、邊或弧稀疏的情況下的情況下，用鄰接表表示比用鄰接矩陣表示，用鄰接表表示比用鄰接矩陣表示節(jié)省存儲空間；節(jié)省存儲空間；n 在無向圖，在無向圖，頂點頂點Vi的度是第的度是第i個鏈表的結點數(shù)個鏈表的結點數(shù)；n 在有向圖中在有向圖中，第，第i個鏈表中的結點數(shù)是頂點個鏈表中的結點數(shù)是頂點Vi的出的出 (或入或入)度；度；求入求入 (或出或出)度，須遍歷整個鄰接表；度，須遍歷整個鄰接表；n 在鄰接表上容易找出任一頂點的第一個鄰接點和下一個鄰在鄰接表上容易找出任一頂點的第一個鄰接點和下一個鄰接點接點；n 要判定兩個頂點要判定兩個頂點Vi和和Vj之間是否有邊，需要搜索第之間是否有邊，需要搜索第i個或第個或第j個

58、鏈表個鏈表7.3 圖的遍歷圖的遍歷n 圖圖的遍歷的遍歷(Travering Graph)：從圖的某一頂點出：從圖的某一頂點出發(fā)，訪遍圖中的其余頂點，發(fā)，訪遍圖中的其余頂點，且每個頂點僅被訪問且每個頂點僅被訪問一次一次。圖。圖的遍歷算法是各種圖操作的基礎的遍歷算法是各種圖操作的基礎。 復雜性：復雜性：圖的任意頂點可能和其余的頂點相鄰接，圖的任意頂點可能和其余的頂點相鄰接，可能在訪問了某個頂點后，沿某條路徑搜索后又回到原可能在訪問了某個頂點后，沿某條路徑搜索后又回到原頂點。頂點。 解決辦法解決辦法：在遍歷過程中記下已被訪問過的頂點。在遍歷過程中記下已被訪問過的頂點。設置一個輔助向量設置一個輔助向量

59、Visited1n(n為頂點數(shù)為頂點數(shù))，其初值為，其初值為0，一旦訪問了頂點一旦訪問了頂點vi后，使后，使Visitedi為為1或為訪問的次序號或為訪問的次序號。 n 圖圖的遍歷算法有的遍歷算法有深度優(yōu)先搜索算法深度優(yōu)先搜索算法和和廣度優(yōu)先搜廣度優(yōu)先搜索算法索算法。n 采用的數(shù)據(jù)結構采用的數(shù)據(jù)結構是是( (正正) )鄰接鏈表鄰接鏈表。7.3.1 深度優(yōu)先搜索算法深度優(yōu)先搜索算法 深度優(yōu)先搜索深度優(yōu)先搜索(Depth First Search-DFS)遍歷類似遍歷類似樹的先序遍歷樹的先序遍歷，是，是樹的先序遍歷的推廣樹的先序遍歷的推廣。1 算法思想算法思想設初始狀態(tài)時圖中的所有頂點未被訪問，則

60、：設初始狀態(tài)時圖中的所有頂點未被訪問，則： 從圖中某個頂點從圖中某個頂點vi出發(fā)出發(fā)，訪問，訪問vi；然后找到；然后找到vi的的一個鄰接一個鄰接頂點頂點vi1 ； 從從vi1出發(fā)，深度優(yōu)先搜索訪問和出發(fā)，深度優(yōu)先搜索訪問和vi1相相鄰接鄰接且且未被訪問未被訪問的的所有頂點；所有頂點； 轉轉 ，直到和，直到和vi相相鄰接的所有頂點都被訪問為止鄰接的所有頂點都被訪問為止 繼續(xù)選取圖中未被訪問頂點繼續(xù)選取圖中未被訪問頂點vj作為起始頂點，轉作為起始頂點，轉(1)，直到，直到圖中所有頂點都被訪問為止。圖中所有頂點都被訪問為止。(a) 無向圖無向圖Gv1v2v3v4v5(b) G的鄰接鏈表的鄰接鏈表01234v1 v2v3