山大《數(shù)據(jù)結(jié)構(gòu)》實驗指導(dǎo)

1、數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)實驗一 抽象數(shù)據(jù)類型一 實驗任務(wù)抽象數(shù)據(jù)類型Triplet的表示和實現(xiàn)。二 實驗?zāi)康?）理解和掌握抽象數(shù)據(jù)類型的概念。2）熟悉數(shù)據(jù)結(jié)構(gòu)的定義及基本操作。3）實踐系統(tǒng)程序開發(fā)的規(guī)范步驟。三 實驗原理1抽象數(shù)據(jù)類型的定義 抽象數(shù)據(jù)類型（ADT，Abstract Data Type）由具有一定關(guān)系的一組數(shù)據(jù)和定義在該組數(shù)據(jù)上的操作組成。抽象數(shù)據(jù)類型為我們提供了一個描述數(shù)據(jù)結(jié)構(gòu)的架構(gòu)。抽象數(shù)據(jù)類型的定義一般包括數(shù)據(jù)定義和操作定義兩個部分。一個含抽象數(shù)據(jù)類型的模塊通常包含定義、表示和實現(xiàn)3個部分。抽象數(shù)據(jù)類型的形式表示為如下三元組：（ D, S, O ）其中：D是數(shù)據(jù)對象，S是D上的關(guān)系

2、集合，O是D上的基本操作集合。我們習(xí)慣上把抽象數(shù)據(jù)類型表示成如下格式：ADT 抽象數(shù)據(jù)類型名 數(shù)據(jù)對象：數(shù)據(jù)關(guān)系：基本操作：ADT抽象數(shù)據(jù)類型名例如，抽象數(shù)據(jù)類型Triplet的三元組定義：ADT Triplet 數(shù)據(jù)對象： D=e1, e2, e3 | e1, e2, e3 ElemSet 數(shù)據(jù)關(guān)系： R1= , 基本操作： InitTriplet ( & T, v1, v2, v3 ) 操作結(jié)果：構(gòu)造了三元組T，元素e1, e2 和e3分別被賦以參數(shù)v1, v2 和v3的值 DestroyTriplet ( & T) 操作結(jié)果：三元組T被銷毀。 Get ( T, i , &e ) 初始條件

3、：三元組T已存在，1 i 3。 操作結(jié)果：用e返回T的第i元的值。 Put(&T，i，e) 初始條件：三元組T已經(jīng)存在，1 i 3。 操作結(jié)果：改變T的第i元的值為e。 IsAscending(T) 初始條件：三元組T已存在。 操作結(jié)果：如果T的三個元素按升序排列，則返回1，否則返回0。 IsDescending(T) 初始條件：三元組T已存在。 操作結(jié)果：如果T的三個元素按降序排列，則返回1，否則返回0。 Max( T, &e) 初始條件：三元組T已存在。 操作結(jié)果：用e返回T中三個元素的最大值。 Min( T, &e) 初始條件：三元組T已存在。 操作結(jié)果：用e返回T中三個元素的最小值。

4、ADT Triplet 2抽象數(shù)據(jù)類型的表示與實現(xiàn)我們可以通過固有數(shù)據(jù)類型來表示和實現(xiàn)抽象數(shù)據(jù)類型，即利用處理器中已存在的數(shù)據(jù)類型來說明新的結(jié)構(gòu)，用已經(jīng)實現(xiàn)的操作來組合新的操作。我們約定以C語言作為數(shù)據(jù)結(jié)果的描述工具。例如，抽象數(shù)據(jù)類型Triplet的表示和實現(xiàn)如下：typedef ElemType * Triplet;/基本操作的實現(xiàn)Status InitTriplet ( Triplet & T, ElemType v1, ElemType v2, ElemType v3 ) /構(gòu)造三元組T，依次設(shè)置T 的三個元素的初值為v1, v2和v3。T=( ElemType * ) malloc

5、( 3*sizeof ( ElemType ) ) ;if ( ! T ) exit ( OVERFLOW ) ;T 0 = v1; T 1 = v2; T 2 = v3;return OK !Status DestroyTriplet ( Triplet & T) free ( T ) ; T=NULL ;return OK !Status Get ( Triplet T, int i , ElemType & e ) if ( i 3 ) return ERROR;e = T i - 1 ; return OK !Status Put ( Triplet & T , int i , Ele

6、mType e ) if ( i 3 ) return ERROR;T i - 1 = e; return OK !四 實驗設(shè)備、儀器、工具及資料 微機、VC五 實驗內(nèi)容通過C語言實現(xiàn)一個可無誤運行的完整程序，完成抽象數(shù)據(jù)類型Triplet的表示和實現(xiàn)。要求：程序運行時顯示基本操作的菜單，由用戶選擇執(zhí)行相應(yīng)操作（如：可利用switch語句等），以此整合Triplet的各基本操作，實現(xiàn)程序設(shè)計。六 實驗步驟（1）實驗預(yù)習(xí)1）預(yù)習(xí)本實驗原理中關(guān)于抽象數(shù)據(jù)類型Triplet的定義、表示及實現(xiàn)。2）熟悉程序運行環(huán)境VC的使用。（2）實驗步驟1）問題分析與系統(tǒng)的結(jié)構(gòu)設(shè)計。充分地分析和理解此實驗項目，弄清

7、要求作什么，限制條件是什么。按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊。最后寫出每個子程序（過程或函數(shù)）的規(guī)格說明，列出它們之間的調(diào)用關(guān)系，可以使用調(diào)用關(guān)系圖表示則更加清晰，這樣便完成了系統(tǒng)結(jié)構(gòu)設(shè)計。2）詳細設(shè)計和編碼。詳細設(shè)計的目的是對子程序（過程或函數(shù)）的進一步求精。用 IF 、WHILE和賦值語句等，以及自然語言寫出算法的框架。利用自然語言的目的是避免陷入細節(jié)。在編碼時，可以對詳細設(shè)計的結(jié)果進一步求精，用高級語言表示出來。3）在VC環(huán)境下調(diào)試程序。七 實驗報告要求實驗報告包含程序開發(fā)過程所形成的所有文檔資料，包括如下內(nèi)容：1）需求分析及規(guī)格說明：問題描述，求解的問題是什么。2）概要設(shè)計：本程序所

8、用的數(shù)據(jù)類型定義；主程序流程；程序模塊及相互關(guān)系。3）詳細設(shè)計：采用C語言定義的數(shù)據(jù)結(jié)構(gòu)；各模塊的偽碼算法；各函數(shù)調(diào)用關(guān)系。4）調(diào)試報告。5）本實驗項目的程序清單及運行結(jié)果。八 思考題 為什么用抽象數(shù)據(jù)類型描述數(shù)據(jù)結(jié)構(gòu)？實驗二 線性表一 實驗任務(wù)1）線性表的順序表示和實現(xiàn)2）線性表的鏈式結(jié)構(gòu)表示和實現(xiàn)二 實驗?zāi)康?）掌握線性表的類型定義和結(jié)構(gòu)特點。2）掌握線性表的順序存儲表示、鏈式存儲表示及其C語言實現(xiàn)。3）掌握順序表的各種基本操作的實現(xiàn)。4）掌握線性表在鏈式存儲結(jié)構(gòu)上的各種操作。三 實驗原理 1線性表的邏輯結(jié)構(gòu)及特性所謂線性表（Linear_List），就是n（n0）個數(shù)據(jù)元素的集合 a1,

9、 a2, , an ，這些數(shù)據(jù)元素之間有邏輯上的線性關(guān)系。線性表的抽象數(shù)據(jù)類型定義如下：ADT List 數(shù)據(jù)對象：D=ai| aiElemSet, i=1,2, ,n, n0數(shù)據(jù)關(guān)系：R1= | ai1, aiD, i =2, n基本操作：CreatList(&L) 操作結(jié)果：生成一個空的線性表L。ListLength(L) 初始條件：線性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù)。ListInsert(&L, i, e) 初始條件：線性表L已存在，1iListLength(L)+1。 操作結(jié)果：在L中第i個位置之前插入新的數(shù)據(jù)元素e，L的長度加1。ListDelete(&L, i, &e)

10、初始條件：線性表L已存在且非空，1iListLength(L)。操作結(jié)果：刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的長度減1。GetElem(L, i, &e) 初始條件：線性表L已存在，1iListLength(L)。操作結(jié)果：用e返回L中第i個數(shù)據(jù)元素的值。LocateElem(L, e, compare( ) 初始條件：線性表L已存在，compare( )是數(shù)據(jù)元素判定函數(shù)。 操作結(jié)果：返回L中第1個與e滿足關(guān)系compare( )的數(shù)據(jù)元素的位序。若這樣的數(shù)據(jù)元素不存在，則返回值為0。ListEmpty(L) 初始條件：線性表L已存在。 操作結(jié)果：若L為空表，則返回TRUE，否則返回

11、FALSE。ClearList(&L) 初始條件：線性表L已存在。 操作結(jié)果：將L重置為空表。DestroyList(&L) 初始條件：線性表L已存在。 操作結(jié)果：銷毀線性表L。 ADT List2線性表的順序表示線性表的順序表示就是利用一組地址連續(xù)的內(nèi)存空間依次存儲線性表的各個數(shù)據(jù)元素，即以元素在計算機內(nèi)“物理位置相鄰”來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系。由于順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)，所以通常利用C語言中動態(tài)分配的一組連續(xù)的存儲單元作為順序存儲結(jié)構(gòu)所需要的存儲空間?？赏ㄟ^定義結(jié)構(gòu)體類型來實現(xiàn)線性表的動態(tài)分配順序存儲結(jié)構(gòu)。具體數(shù)據(jù)類型描述如下：#define MAXLEN 100

12、#define LIST_INCREASE 10 /線性表存儲空間的動態(tài)分配增量typedef structElemType *list; /線性表的存儲空間的基地址int length; /線性表的當前長度int maxsize; /線性表當前分配的存儲容量List_Sq;3線性表的鏈式結(jié)構(gòu)鏈式存儲結(jié)構(gòu)具有以下特點：不要求邏輯上相鄰的元素在物理結(jié)構(gòu)上也相鄰；允許迅速簡單地插入或刪除結(jié)點，而不必移動大量元素；但只能順序存取而不能隨機存取線性表中任一元素。線性表的鏈式存儲結(jié)構(gòu)可通過單鏈表來實現(xiàn)。此時，線性表中的每個元素對應(yīng)單鏈表中的一個結(jié)點，每個結(jié)點的數(shù)據(jù)域存儲線性表的數(shù)據(jù)元素，每個結(jié)點的指針域

13、存儲其后繼元素所在結(jié)點的地址，可以通過每個結(jié)點的指針域訪問到其后繼結(jié)點，如圖2.1所示。 圖2.1 線性鏈表示例因此，單鏈表中每個結(jié)點都是由包含這個數(shù)據(jù)元素的信息和一個指示其直接后繼的指針組成的一個結(jié)構(gòu)體類型，具體描述如下：typedef struct LNodeElemType data;struct LNode * next; LNode, * List_Link;每個單鏈表的頭指針L是List_Link型的變量，指向鏈表中第一個結(jié)點。由表頭指針出發(fā)可以依次訪問到每個結(jié)點，存取相應(yīng)的數(shù)據(jù)元素值。線性表中數(shù)據(jù)元素間的線性關(guān)系都可以通過單鏈表中結(jié)點指針域的鏈接關(guān)系反映出來。當L=NULL時，意

14、味著所表示的線性表為“空”表，其長度n為“零”。四 實驗設(shè)備、儀器、工具及資料 微機、VC五 實驗內(nèi)容（1）實驗任務(wù)1：順序表的表示與實現(xiàn)請編制C程序，利用順序存儲方式來實現(xiàn)下列功能：1）建立主程序菜單，使之具有建立線性表、插入元素、刪除元素、查找元素、銷毀線性表、結(jié)束程序運行等菜單項。2）根據(jù)鍵盤輸入數(shù)據(jù)生成一個線性表，并輸出該原始線性表。3）根據(jù)屏幕菜單的提示選擇，進行數(shù)據(jù)插入、刪除、查找等操作。4）最后，輸出修改之后的線性表并結(jié)束程序的運行。（2）實驗任務(wù)2：線性表的鏈式存儲表示與實現(xiàn)請編制C程序，利用鏈式存儲方式來實現(xiàn)下列功能：1）建立主程序菜單，使之具有建立線性表、插入元素、刪除元素

15、、查找元素、銷毀線性表、結(jié)束程序運行等菜單項。2）根據(jù)鍵盤輸入數(shù)據(jù)生成一個單鏈表，并輸出該原始單鏈表。3）根據(jù)屏幕菜單的提示選擇，進行數(shù)據(jù)插入、刪除、查找等操作。4）最后，輸出修改之后的單鏈表并結(jié)束程序的運行。（3）實驗任務(wù)3：線性表的合并（選做）編制C程序?qū)崿F(xiàn)下列功能：1）建立兩個線性表（順序存儲表示或鏈式存儲表示）。2）對已建立的兩個線性表進行升序排序。3）合并這兩個有序表。六 實驗步驟（1）實驗預(yù)習(xí)1）預(yù)習(xí)本實驗原理中關(guān)于線性表的定義、順序存儲表示和鏈式存儲結(jié)構(gòu)。2）分析掌握教材2123頁中的算法2-12-5，為完成實驗任務(wù)1做好準備。3）分析掌握教材2730頁中的算法2-92-13，為

16、完成實驗任務(wù)2做好準備。4）分析掌握教材25頁中的算法2-72-8或教材3132頁中的算法2-152-16，為完成實驗任務(wù)3做好準備。（2）實驗步驟1）問題分析。充分地分析和理解此實驗任務(wù)，弄清要求作什么，限制條件是什么。2）系統(tǒng)的結(jié)構(gòu)設(shè)計。按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊。最后寫出每個子程序（過程或函數(shù)）的規(guī)格說明，列出它們之間的調(diào)用關(guān)系，可以使用調(diào)用關(guān)系圖表示則更加清晰，這樣便完成了系統(tǒng)結(jié)構(gòu)設(shè)計。3）詳細設(shè)計。詳細設(shè)計的目的是對子程序（過程或函數(shù)）的進一步求精。用 IF 、WHILE和賦值語句等，以及自然語言寫出算法的框架。利用自然語言的目的是避免陷入細節(jié)。4）編碼。在詳細設(shè)計的基礎(chǔ)上，

17、對詳細設(shè)計的結(jié)果進一步求精，用C語言表示出來。5）在VC環(huán)境下調(diào)試程序。七 實驗報告要求實驗報告包含程序開發(fā)過程所形成的所有文檔資料，包括如下內(nèi)容：1）需求分析及規(guī)格說明：問題描述，求解的問題是什么。2）概要設(shè)計：本程序所用的數(shù)據(jù)類型定義；主程序流程；程序模塊及相互關(guān)系。3）詳細設(shè)計：采用C語言定義的數(shù)據(jù)結(jié)構(gòu)；各模塊的偽碼算法；各函數(shù)調(diào)用關(guān)系。4）調(diào)試報告。5）本實驗任務(wù)1、2的程序清單及運行結(jié)果。八 思考題1）通過實驗任務(wù)1、2的實現(xiàn)比較線性表的兩種存儲結(jié)構(gòu)的優(yōu)缺點。2）實現(xiàn)任務(wù)3種采用哪種存儲表示更容易些？實驗三 棧與隊列一 實驗任務(wù)1）棧的應(yīng)用2）隊列的表示與實現(xiàn)二 實驗?zāi)康?）了解棧與

18、隊列的特性2）掌握棧的順序、鏈式存儲表示及實現(xiàn)3）掌握隊列的順序、鏈式存儲表示及實現(xiàn)4）掌握棧與隊列在實際問題中的應(yīng)用三 實驗原理1棧的特性棧（Stack）又稱堆棧，是一種特殊的線性表，可定義為插入、刪除和訪問只能在某一端進行的線性數(shù)據(jù)結(jié)構(gòu)。堆棧允許插入、刪除和訪問的一端稱為棧頂（Top），另一端稱為棧底（Bottom）。棧頂?shù)牡谝粋€元素被稱為棧頂元素。堆棧的性質(zhì)決定它的數(shù)據(jù)是按“先進后出”的順序被訪問，即最先存儲的元素最后被訪問、刪除，最后存儲的元素最先被訪問、刪除，所以棧也稱為“LIFO”（Last_In, First_Out）。棧的抽象數(shù)據(jù)類型定義如下：ADT Stack數(shù)據(jù)對象：D=a

19、i | ai ElemSet, i = 1,2,n, n0數(shù)據(jù)關(guān)系：R = | ai-1, ai D, i = 2, n 約定an端為棧頂，a1端為棧底。基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個空棧S。Push(&S, e )初始條件：棧S已存在。操作結(jié)果：插入元素e為新的棧頂元素。Pop(&S, &e) 初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，并用e返回其值。GetTop(S, &e)初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。StackEmpty(S)初始條件：棧S已存在。操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSE。StackLe

20、ngth(S)初始條件：棧S已存在。操作結(jié)果：返回S的元素個數(shù)，即棧的長度。StackTraverse(S，visit( )初始條件：棧S已存在且非空。操作結(jié)果：從棧底到棧頂依次對S的每個數(shù)據(jù)元素調(diào)用函數(shù)visit ( ) 。一旦visit ( ) 失敗，則操作失敗。ClearStack(&S)初始條件：棧S已存在。操作結(jié)果：將S清為空棧。DestroyStack(&S)初始條件：棧S已存在。操作結(jié)果：棧S被銷毀 。 ADT Stack2棧的順序表示棧的順序存儲結(jié)構(gòu)，即順序棧，是利用一組連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時通過指針top指示棧頂元素在順序棧中的位置。由于很難估計棧

21、在使用過程中所需要的最大空間的大小，所以通常利用C語言中動態(tài)分配的一組連續(xù)的存儲單元作為順序棧所需要的存儲空間。順序棧所需要的具體數(shù)據(jù)類型描述如下：#define MAXLEN 100#define STACK_INCREASE 10 /順序棧存儲空間的動態(tài)分配增量typedef structElemType *base; /棧的存儲空間的基地址，即棧底指針ElemType *top; /棧頂指針int maxsize; /棧當前分配的存儲容量SqStack;其中，maxsize指示棧當前可使用的最大容量；base為棧底指針，在順序棧中，它始終指向棧底的位置，若base=NULL，則表明棧結(jié)構(gòu)

22、不存在；top為棧頂指針，起初值為棧底指針值，即top=base，這也可作為?？盏臉擞?。棧插入新元素時，將新元素插入到棧頂指針所指向的位置，同時指針top增1，刪除棧頂元素時，指針top減1。3棧的鏈式存儲表示棧的鏈式存儲結(jié)構(gòu)，即鏈棧，與線性表的鏈式存儲結(jié)構(gòu)類似，是通過由結(jié)點構(gòu)成的單鏈表實現(xiàn)的，但每個結(jié)點的指針指向其前驅(qū)結(jié)點（在其之前進棧的結(jié)點）。此時，表頭指針稱為棧頂指針，其指向的結(jié)點即為棧頂結(jié)點。所需要的具體數(shù)據(jù)類型描述如下：typedef struct SNodeElemType data;struct SNode *prior; /prior將指向其前一次入棧的元素SNode, *SL

23、ink;4隊列的特性隊列（Queue）簡稱隊，也是一種特殊的線性表，可定義為只允許在表的一端進行插入，而在表的另一端進行刪除的線性結(jié)構(gòu)。隊列允許插入的一端稱為隊尾（Rear），允許刪除的一端稱為隊首（Front）。由于隊列的插入和刪除分別在不同的兩端進行，因而先插入者自然先從另一端刪除，所以隊列具有“先進先出”的特點，簡稱為FIFO（First-In, First-Out）。隊列的抽象數(shù)據(jù)類型定義如下：ADT Queue 數(shù)據(jù)對象：D=ai | ai ElemSet, i = 1,2,n, n0數(shù)據(jù)關(guān)系：R1= | ai-1, ai D, i = 2, n 約定其中a1端為隊首，an端為隊尾。

24、基本操作：InitQueue(&Q) 操作結(jié)果：構(gòu)造一個空隊列Q。QueueEmpty(Q) 初始條件：隊列Q已存在。 操作結(jié)果：若Q為空隊列，則返回TRUE，否則FALSE。QueueLength(Q) 初始條件：隊列Q已存在。 操作結(jié)果：返回Q的元素個數(shù)，即隊列的長度。EnQueue(&Q, e) 初始條件：隊列Q已存在。 操作結(jié)果：插入元素e為Q的新的隊尾元素。DeQueue(&Q, &e) 初始條件：Q為非空隊列。操作結(jié)果：刪除Q的隊首元素，并用e返回其值。GetHead(Q, &e) 初始條件：Q為非空隊列。 操作結(jié)果：用e返回Q的隊首元素。QueueTraverse(Q, visi

25、t( ) ) 初始條件：Q已存在且非空。 操作結(jié)果：從隊首到隊尾，依次對Q 的每個數(shù)據(jù)元素調(diào)用函數(shù)visit( )。一旦visit( )失敗，則操作失敗。ClearQueue(&Q) 初始條件：隊列Q已存在。 操作結(jié)果：將Q清為空隊列。DestroyQueue(&Q) 初始條件：隊列Q已存在。 操作結(jié)果：隊列Q被銷毀，不再存在。ADT Queue5隊列的順序表示隊列的順序存儲結(jié)構(gòu)，用一組地址連續(xù)的存儲單元依次存放從隊首到隊尾的元素，同時附設(shè)兩個指針front和rear分別指示隊首元素及隊尾元素的位置。循環(huán)隊列所需要的具體數(shù)據(jù)類型描述如下：#define MAXQSIZE 100 /最大隊列長度

26、typedef struct ElemType * base; /初始化的動態(tài)分配存儲空間 int front; /頭指針，若隊列不空，指向隊首元素 int rear; /尾指針，若隊列不空，指向隊尾元素的下一個位置SqQueue;6隊列的鏈式存儲表示隊列的鏈接存儲結(jié)構(gòu)，簡稱鏈隊列。鏈隊列所需要的具體數(shù)據(jù)類型描述如下：typedef struct QNode ElemType data; /值域 struct QNode * next; /鏈接指針域QNode, * QueuePtr;typedef struct QueuePtr front; /頭指針 QueuePtr rear; /尾指針

27、LinkQueue;四 實驗設(shè)備、儀器、工具與材料 微機、VC五 實驗內(nèi)容（1）實驗任務(wù)1：棧的應(yīng)用迷宮求解編制C程序完成迷宮問題。程序基本要求：用戶輸入迷宮數(shù)據(jù)初始化迷宮；利用棧的順序表示以及入棧、出棧等基本操作，實現(xiàn)迷宮路徑的求解；輸出求解得到的完整路徑（或提示迷宮無通路）。（2）實驗任務(wù)2：隊列的表示與實現(xiàn)編寫一個C程序?qū)崿F(xiàn)順序隊列的各種基本操作，并在此基礎(chǔ)上設(shè)計一個主程序，完成如下功能：1）建立循環(huán)隊列2）入隊列3）出隊列4）判斷隊列是否為空5）遍歷隊列6）取隊首元素六 實驗步驟（1）實驗預(yù)習(xí)1）預(yù)習(xí)本實驗原理中關(guān)于棧與隊列的定義、順序存儲表示。2）分析掌握教材4850頁中的算法3-1

28、3-4，為完成實驗任務(wù)1做好準備。3）分析掌握教材5760頁中迷宮問題及求解算法3-13，為完成實驗任務(wù)1做好準備。4）分析掌握教材7073頁中的算法3-153-20，為完成實驗任務(wù)2做好準備。（2）實驗步驟1）問題分析。充分地分析和理解此實驗任務(wù)，弄清要求作什么，限制條件是什么。2）系統(tǒng)的結(jié)構(gòu)設(shè)計。按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊。最后寫出每個子程序（過程或函數(shù)）的規(guī)格說明，列出它們之間的調(diào)用關(guān)系，可以使用調(diào)用關(guān)系圖表示則更加清晰，這樣便完成了系統(tǒng)結(jié)構(gòu)設(shè)計。3）詳細設(shè)計。詳細設(shè)計的目的是對子程序（過程或函數(shù)）的進一步求精。用 IF 、WHILE和賦值語句等，以及自然語言寫出算法的框架。利用

29、自然語言的目的是避免陷入細節(jié)。4）編碼。在詳細設(shè)計的基礎(chǔ)上，對詳細設(shè)計的結(jié)果進一步求精，用C語言表示出來。5）在VC環(huán)境下調(diào)試程序。七 實驗報告要求實驗報告包含程序開發(fā)過程所形成的所有文檔資料，包括如下內(nèi)容：1）需求分析及規(guī)格說明：問題描述，求解的問題是什么。2）概要設(shè)計：本程序所用的數(shù)據(jù)類型定義；主程序流程；程序模塊及相互關(guān)系。3）詳細設(shè)計：采用C語言定義的數(shù)據(jù)結(jié)構(gòu)；各模塊的偽碼算法；各函數(shù)調(diào)用關(guān)系。4）調(diào)試報告。5）本實驗任務(wù)1、2的程序清單及運行結(jié)果。八 思考題如果一個程序中用到兩個棧，為了不發(fā)生溢出錯誤，就必須給每個棧預(yù)先一個較大的存儲空間。若每個棧都預(yù)先分配過大的存儲空間，勢必造成系

30、統(tǒng)空間緊張，如何解決這個問題？實驗四 樹和二叉樹一 實驗任務(wù)1）二叉樹的表示與實現(xiàn)2）Huffman編碼二 實驗?zāi)康?）掌握二叉樹的類型定義和結(jié)構(gòu)特點。2）掌握二叉樹的鏈式存儲表示和實現(xiàn)。3）掌握赫夫曼樹及其應(yīng)用三 實驗原理1二叉樹的定義所謂二叉樹，是指結(jié)點的一個有限集合，它或為空集，或為滿足下列性質(zhì)的非空集合：有且只有一個根結(jié)點，其余結(jié)點分成左右兩個互不相交的集合TL、TR，且TL、TR均為二叉樹。二叉樹的抽象數(shù)據(jù)類型定義如下：ADT BinaryTree 數(shù)據(jù)對象D：D=ai | aiElemSet, i=1,2, ,n, n0數(shù)據(jù)關(guān)系R：若D為空集，則稱為空二叉樹。若D僅含一個數(shù)據(jù)元素，

31、則R為空集，否則RH，H滿足關(guān)系：(1) T中存在唯一的一個結(jié)點，它沒有前驅(qū)，稱為樹的根，用root表示，在集合D中用a1表示；(2) 若D中元素個數(shù)大于1，對于任意的數(shù)據(jù)元素ajD且j2，存在唯一的數(shù)據(jù)元素aiD，有H；(3) 若D中元素個數(shù)大于1，對于任意的數(shù)據(jù)元素aiD，僅存在不多于2個數(shù)據(jù)元素aj,akD且j, ki，有 , H，其中，若jK，則稱aj為ai的左孩子節(jié)點，ak為ai的右孩子節(jié)點?；静僮鱌：InitBiTree(&T);操作結(jié)果：構(gòu)造空二叉樹T。CreateBiTree(&T, tree);初始條件：tree給出二叉樹T的表示形式。操作結(jié)果：按tree構(gòu)造二叉樹T。Bi

32、TreeEmpty(T);初始條件：二叉樹T存在。操作結(jié)果：若T為空樹，則返回TRUE，否則返回FALSE。BiTreeDepth(T);初始條件：二叉樹T存在。操作結(jié)果：返回T的深度。Root(T);初始條件：二叉樹T存在。操作結(jié)果：返回T的根。Value(T, e);初始條件：二叉樹T存在，e是需尋找的結(jié)點的值。操作結(jié)果：若找到該結(jié)點，則函數(shù)返回TRUE，否則返回FALSE。Assign(T, e, value);初始條件：二叉樹T存在，e是需尋找的結(jié)點的值。操作結(jié)果：若找到該結(jié)點，結(jié)點e賦值為value，則函數(shù)返回TRUE，否則返回FALSE。Parent(T, e, P);初始條件：二

33、叉樹T存在，e是需尋找的結(jié)點的值。操作結(jié)果：若樹中存在值為e的結(jié)點，則函數(shù)返回TRUE，否則返回FALSE；若存在該結(jié)點，用P返回雙親結(jié)點的位置，若結(jié)點為根結(jié)點，則P返回空。LeftChild(T, e, P);初始條件：二叉樹T存在，e是需尋找的結(jié)點的值。操作結(jié)果：若樹中存在值為e的結(jié)點，則函數(shù)返回TRUE，否則返回FALSE；若存在該結(jié)點，用P返回左孩子結(jié)點的位置，若結(jié)點無左孩子結(jié)點，則P返回空。RightChild(T, e, P);初始條件：二叉樹T存在，e是需尋找的結(jié)點的值。操作結(jié)果：若樹中存在值為e的結(jié)點，則函數(shù)返回TRUE，否則返回FALSE；若存在該結(jié)點，用P返回右孩子結(jié)點的位

34、置，若結(jié)點無右孩子結(jié)點，則P返回空。DelBiTreeNode(&T，P);初始條件：二叉樹T存在，P指向該二叉樹中的一個結(jié)點。操作結(jié)果：刪除P所指向的結(jié)點及其子樹。TraverseBiTree(T, visit( );初始條件：二叉樹T存在，visit是對結(jié)點操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)的每個結(jié)點調(diào)用函數(shù)visit( )一次且至多一次。一旦visit( )失敗，則操作失敗。ClearBiTree(&T);初始條件：二叉樹T存在。操作結(jié)果：將二叉樹T清空。ADT BinaryTree2二叉樹的鏈式存儲表示二叉樹的鏈式存儲結(jié)構(gòu)通常采用二叉鏈表形式，即在每個結(jié)點中設(shè)置三個域，分別為數(shù)據(jù)

35、域data、左指針域left和右指針域right。其中，數(shù)據(jù)域用于存儲對應(yīng)的數(shù)據(jù)元素，left和right用來分別存儲左孩子和右孩子結(jié)點的存儲位置。二叉鏈表的結(jié)點類型可定義為：typedef struct BiTreeNodeElemType data;struct BiTreeNode *left;struct BiTreeNode *right; BiTreeNode, * BiTreePtr;3二叉樹的遍歷二叉樹的遍歷是二叉樹中最重要的運算，也是各種操作的基礎(chǔ)。二叉樹的遍歷是指按照某個搜索路徑尋訪樹中的每個結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。在遍歷的過程中，可以對結(jié)點進行各

36、種操作。根據(jù)二叉樹的遞歸定義，一棵非空二叉樹由根結(jié)點、左子樹和右子樹組成，因此，遍歷一棵二叉樹可以分解為三個問題：訪問根結(jié)點、遍歷左子樹、遍歷右子樹。若分別用D、L、R表示上述三個子問題，則可能有DLR、LDR、LRD、DRL、RDL、RLD幾種情況。若限定先左后右，則只有前3種情況：（1）DLR，此時訪問根結(jié)點的操作在遍歷左、右子樹之前，故稱之為先序遍歷或先根遍歷；（2）LDR，此時訪問根結(jié)點的操作在遍歷左子樹之后、右子樹之前，故稱之為中序遍歷或中根遍歷；（3）LRD，此時訪問根結(jié)點的操作在遍歷左、右子樹之后，故稱之為后序遍歷或后根遍歷。4赫夫曼樹n個帶權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中，帶權(quán)路徑

37、長度WPL最小的二叉樹稱作赫夫曼樹。權(quán)值越大的結(jié)點離根越近的二叉樹才是最優(yōu)二叉樹。赫夫曼樹構(gòu)造算法，具體敘述如下：(1) 給定n個權(quán)值w1, w2, , wn，對應(yīng)n個結(jié)點，構(gòu)成具有n棵二叉樹的森林F=T1, T2, , Tn，其中每棵二叉樹Ti（1in）都只有一個權(quán)值為wi的根結(jié)點，其左右子樹均為空。(2) 在森林F中選出兩棵根結(jié)點的權(quán)值最小的樹作為一棵新樹的左、右子樹，且置新樹的根結(jié)點的權(quán)值為其左、右子樹上根結(jié)點的權(quán)值之和。(3) 從F中刪除構(gòu)成新樹的那兩棵樹，同時把新樹加入F中。(4) 重復(fù)(2)和(3)，直到F中只含有一棵樹為止，此樹就是赫夫曼樹。5赫夫曼編碼若要設(shè)計長短不等的編碼，則

38、要求字符集中任一個字符的編碼都不是另一個字符的編碼的前綴，這種編碼稱做前綴編碼。為了使不等長編碼為前綴編碼，可用該字符集中的每個字符作為葉子結(jié)點生成一棵編碼二叉樹，將每個字符出現(xiàn)的次數(shù)作為字符結(jié)點的權(quán)值賦予該結(jié)點上，求出此樹的最小帶權(quán)路徑長度，也就是傳送電文的最短長度。因此，求傳送電文的最短長度問題就轉(zhuǎn)化為求由字符集中的所有字符作為葉子結(jié)點且由字符的出現(xiàn)頻率作為其權(quán)值所產(chǎn)生的赫夫曼樹的問題。四 實驗設(shè)備、儀器、工具與資料 微機、VC五 實驗內(nèi)容（1）實驗任務(wù)1：二叉樹建立和遍歷編制C程序?qū)崿F(xiàn)下列功能：1）建立二叉樹。2）按先序、中序、后序方式遍歷二叉樹。程序的基本要求：采用二叉鏈表存儲結(jié)構(gòu)表示

39、二叉樹；通過二叉樹廣義表輸入所有結(jié)點建立二叉樹；通過遞歸算法實現(xiàn)二叉樹的遍歷并輸出結(jié)點數(shù)據(jù)信息。（2）實驗任務(wù)2：赫夫曼編碼從鍵盤上輸入n個字符及其權(quán)值，編制C程序建立赫夫曼樹，并編碼輸出。六 實驗步驟（1）實驗預(yù)習(xí)1）預(yù)習(xí)本實驗原理中關(guān)于二叉樹的定義、二叉鏈表存儲表示。2）分析掌握教材9399頁中的算法4-14-4、算法4-74-7，為完成實驗任務(wù)1做好準備。3）預(yù)習(xí)本實驗原理中關(guān)于赫夫曼樹、赫夫曼編碼的含義及赫夫曼樹的構(gòu)造方法。4）分析掌握教材112115頁中的算法4-144-15，為完成實驗任務(wù)2做好準備。（2）實驗步驟1）問題分析。充分地分析和理解此實驗任務(wù)，弄清要求作什么，限制條件是

40、什么。2）系統(tǒng)的結(jié)構(gòu)設(shè)計。按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊。最后寫出每個子程序（過程或函數(shù)）的規(guī)格說明，列出它們之間的調(diào)用關(guān)系，可以使用調(diào)用關(guān)系圖表示則更加清晰，這樣便完成了系統(tǒng)結(jié)構(gòu)設(shè)計。3）詳細設(shè)計。詳細設(shè)計的目的是對子程序（過程或函數(shù)）的進一步求精。用 IF 、WHILE和賦值語句等，以及自然語言寫出算法的框架。利用自然語言的目的是避免陷入細節(jié)。4）編碼。在詳細設(shè)計的基礎(chǔ)上，對詳細設(shè)計的結(jié)果進一步求精，用C語言表示出來。5）在VC環(huán)境下調(diào)試程序。七 實驗報告要求實驗報告包含程序開發(fā)過程所形成的所有文檔資料，包括如下內(nèi)容：1）需求分析及規(guī)格說明：問題描述，求解的問題是什么。2）概要設(shè)計：本

41、程序所用的數(shù)據(jù)類型定義；主程序流程；程序模塊及相互關(guān)系。3）詳細設(shè)計：采用C語言定義的數(shù)據(jù)結(jié)構(gòu)；各模塊的偽碼算法；各函數(shù)調(diào)用關(guān)系。4）調(diào)試報告。5）本實驗任務(wù)1、2的程序清單及運行結(jié)果。八 思考題1）如何以廣義表的形式輸出二叉樹？2）如何用非遞歸算法實現(xiàn)二叉樹的中序遍歷？ 3）如何利用已建好的赫夫曼編碼對輸入的正文進行譯碼？實驗五 圖一 實驗任務(wù)1）圖的鄰接表存儲與遍歷2）圖的最短路徑求解二 實驗?zāi)康?）圖的基本存儲方法。2）掌握圖的兩種搜索路徑的遍歷方法。3）掌握圖的有關(guān)應(yīng)用（最短路徑）。三 實驗原理1圖圖G由兩個集合組成：頂點（結(jié)點）集合V和連接頂點的邊的集合E，集合E由集合V中的不同的頂

42、點對組成，通常記為G=（V，E）。圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在圖形結(jié)構(gòu)中，結(jié)點之間的關(guān)系可以是任意的，圖中任意兩個數(shù)據(jù)元素之間都可能有關(guān)。圖的抽象數(shù)據(jù)類型定義如下： ADT Graph/Digraph 數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。 數(shù)據(jù)關(guān)系R：R= VR 對于有向圖VR= V，w| v， wV且P(v，w), V，w表示從v到w的弧， 謂詞 P(v， w)定義了弧V， w的意義或信息 對于無向圖VR= (v，w)| v， wV且P(v，w), (v，w) 表示從v到w的邊， 謂詞 P(v， w)定義了邊(v， w)的意義或信息 基本操作P： Crea

43、teGraph（G，V，VR） 返回結(jié)果：V是圖的頂點集，VR是圖中邊或弧集合。按V和VR的定義構(gòu)造圖G。 DestoryGraph（G） 初始條件：G是已經(jīng)存在的一個圖。 操作結(jié)果：銷毀圖G。 Exist（G，v，w） 初始條件：G是已經(jīng)存在的一個圖，v、w是兩個頂點。 操作結(jié)果：如果存在邊（v，w）或弧V，w，則返回TRUE，否則返回FALSE。 Edges（G） 初始條件：G是已經(jīng)存在的一個圖。 操作結(jié)果：返回圖中邊的數(shù)目。 Vertices（G） 初始條件：G是已經(jīng)存在的一個圖。 操作結(jié)果：返回圖中頂點的數(shù)目。 Add（G，v，w） 初始條件：圖G已存在，v，w是兩個頂點。 操作結(jié)果：

44、如果G是有向圖，則在G中添加一條弧V，w；如果G是無向圖，則在G中添加一條邊（v，w）。 Delete（G，v，w） 初始條件：圖G已存在，v，w是兩個頂點。 操作結(jié)果：如果G是有向圖，則在G中刪除一條弧V，w；如果G是無向圖，則在G中刪除一條邊（v，w）。 Degree（G，v） 初始條件：圖G及頂點v已存在。 操作結(jié)果：返回圖G中頂點v的度。 Indegree（G，v） 初始條件：圖G及頂點v已存在。 操作結(jié)果：如果G是有向圖，則返回頂點v的入度；如果G是無向圖，則返回圖G中頂點v的度。Outdegree（G，v） 初始條件：圖G及頂點v已存在。 操作結(jié)果：如果G是有向圖，則返回頂點v的出

45、度；如果G是無向圖，則返回圖G中頂點v的度。 DFSTraverse（G，v，visit（） 初始條件：圖G已存在，v是G中的某個頂點，visit是頂點的應(yīng)用函數(shù)。 操作結(jié)果：從頂點v起深度優(yōu)先遍歷圖G，并對頂點調(diào)用函數(shù)visit一次且僅一次。一旦visit失敗，則操作失敗。 BFSTraverse （G，v，visit（） 初始條件：圖G已存在，v是G中的某個頂點，visit是頂點的應(yīng)用函數(shù)。 操作結(jié)果：從頂點v起廣度優(yōu)先遍歷圖G，并對頂點調(diào)用函數(shù)visit一次且僅一次。一旦visit失敗，則操作失敗。 ADT Graph/Digraph2圖的存儲結(jié)構(gòu)（1）鄰接矩陣一個n個頂點的圖G=（V，

46、E）的鄰接矩陣（Adjacency Matrix）是一個nn矩陣AdjMatrix， AdjMatrix中的每個元素是0或1。假設(shè)圖G中頂點集合：V=1，2，n，那么AdjMatrix中的元素定義如下： AdjMatrix ij= 圖的鄰接矩陣存儲結(jié)構(gòu)的C語言描述形式如下：#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20typedef enum DG=1, AG, DN, AN GraphKind； /有向圖、無向圖；有向網(wǎng)、無向網(wǎng) typedef struct node VertexType vextex；/頂點信息Node；typedef

47、struct arcs int adj；/ 頂點鄰接關(guān)系 /該邊或弧的相關(guān)信息指針 Arcs;typedef struct Node nodesMAX_VERTEX_NUM；/頂點集合 Arcs arcsMAX_VERTEX_NUMMAX_VERTEX_NUM； /鄰接矩陣 int vexnum, arcnum； /頂點數(shù)和弧數(shù) GraphKind kind;/kind取值1、2、3、4分別表示有向圖、無向圖、有向網(wǎng)、無向網(wǎng)Graph;（2）鄰接表鄰接表（Adjacency List）是一種順序存儲與鏈式存儲相結(jié)合的存儲結(jié)構(gòu)，順序存儲部分用來保存圖中頂點信息，鏈式存儲部分保存圖中邊或弧的信息。

48、具體做法是：圖G被表示為一個數(shù)組或向量v1，v2，vn，每個元素對應(yīng)圖中一個頂點。每個vi存儲頂點vi的信息，以及一個指向包含所有依附于頂點vi的邊組成的單鏈表的指針，vi稱之為頭結(jié)點。頭結(jié)點結(jié)構(gòu)如下圖所示：其中data存放與頂點相關(guān)的信息，firstarc是指針；鄰接單鏈表中每個結(jié)點表示依附于該頂點的一條邊（對于有向圖則是以頂點vi為尾的弧），稱為邊（?。┙Y(jié)點，其結(jié)構(gòu)如下圖所示：其中adjvex存放依附于該邊的另一個頂點在一維數(shù)組中的序號，對于有向圖，存放的是該弧結(jié)點所表示的弧的弧頭頂點在一維數(shù)組中的序號；nextarc為指向下一條邊（或?。┙Y(jié)點的指針；info存儲和邊或弧相關(guān)的信息，如權(quán)值

49、等。圖的鄰接表存儲結(jié)構(gòu)的C語言描述形式如下：#define MAXLEN 10typedef struct node /*邊結(jié)點結(jié)構(gòu)*/int adjvex; /*存放與頭結(jié)點相鄰接的頂點在數(shù)組中的序號*/int info; /*權(quán)值等信息*/struct node *nextarc; /*指向與頭結(jié)點相鄰接下一個頂點的表結(jié)點*/ EdgeNode;typedef struct /*頭結(jié)點結(jié)構(gòu)*/int id; /*頂點入度*/char data; /*頂點信息*/EdgeNode *firstarc; /*指向頭結(jié)點對應(yīng)的單鏈表中的表結(jié)點*/ VexNode;typedef struct /

50、*鄰接表結(jié)構(gòu)*/VexNode adjsMAXLEN; /*鄰接表的頭結(jié)點集合*/int vexnum,arcnum; /*頂點數(shù),邊數(shù)*/int kind; /*圖的種類*/ AdjList;3圖的遍歷圖有兩種搜索路徑的遍歷方法：深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。圖的深度優(yōu)先搜索（Depth-First Search，DFS）策略是從給定頂點v出發(fā)，在回溯之前，沿著從v出發(fā)的一條路徑盡可能深入前進。其遍歷規(guī)則為：從v出發(fā)，訪問v的一個未被訪問的鄰接頂點w1，再從w1出發(fā)，訪問w1的一個未被訪問的鄰接頂點w2，然后從w2出發(fā)，訪問w2的一個未被訪問的鄰接頂點w3，如此下去，直到一個所有鄰接點

51、都被訪問過的頂點為止。然后回溯到尚有鄰接點未被訪問的頂點，重復(fù)上述過程，直到圖中所有與v有路徑相通的頂點都被訪問過；此時，若圖中還存在未被訪問過的頂點，則從其中一個未被訪問過的頂點出發(fā)，重復(fù)上述過程，直到圖中所有頂點都被訪問為止。圖的廣度優(yōu)先搜索（Broad-First Search，BFS）策略是在訪問給定頂點v之后，先訪問與v鄰接的所有頂點w1、w2、wk，然后再依次從w1、w2、wk出發(fā)，訪問它們的未被訪問過的鄰接頂點，重復(fù)上述操作，直到圖中所有被訪問過的頂點的鄰接頂點都被訪問為止。若此時圖中還有未被訪問過的頂點，則從一個未被訪問過的頂點出發(fā)，重復(fù)上述過程，直到圖中所有的頂點都被訪問過為

52、止。4最短路徑圖的最短路徑問題有：一是求從一個頂點（源點）到其它各頂點的最短路徑；二是求每對頂點之間的最短路徑。第一種情況采用迪杰斯特拉算法解決，這是一個按路徑長度遞增的順序逐步產(chǎn)生最短路徑的算法。第二種情況采用Floyd算法求解。（1）Dijkstra算法的實現(xiàn)設(shè)有向網(wǎng)G =（V，E），它采用鄰接矩陣作為存儲結(jié)構(gòu)。若鄰接矩陣為Cost，并規(guī)定：設(shè)立兩個一維數(shù)組S和Distance，其中S存放已經(jīng)找到最短路徑的頂點，它的初始狀態(tài)為：集合S中只含有起始頂點（源點）。并規(guī)定： Distance的每個分量Distancei表示當前所找到的從起始頂點v到每個目的頂點vi的最短路徑長度。它的初始狀態(tài)為：

53、若從v到vi有弧，則Distancei為弧上的權(quán)值，否則置Distancei為，即Distancei = CostLocateVex（v）i，LocateVex用于確定頂點v在G中的位序。 利用Distance的各個分量的值，選取當前具有的最短路徑的頂點vj，使得 Distancej = minDistancei viVS然后將頂點vj加入集合S中，即令Sj=1，同時對于所有Si=0的頂點vi，修改源點到它們可達的最短路徑為 Distancei = minDistancei，Distancej+ Costji上述過程重復(fù)執(zhí)行n-1次，就可以得到源點到其它頂點的最短路徑值。（2）Floyd算法的

54、思想假設(shè)求從頂點vi到頂點vj的最短路徑。如果從頂點vi到頂點vj有弧，則從頂點vi到頂點vj存在一條長度為Costij的路徑，該路徑不一定是最短路徑，尚需進行n次試探。首先考慮路徑（vi，v0，vj）是否存在（即判斷弧（vi，v0）和（v0，vj）是否存在）。如果存在，則比較（vi，v0，vj）和（vi，vj）的路徑長度，然后取長度較短者為頂點vi到頂點vj的中間頂點的序號不大于0的最短路徑。假如在路徑上再增加一個頂點v1，也就是說，如果（vi，v1）和（v1，vj）分別是當前找到的中間頂點的序號不大于0的最短路徑，那么（vi，v1，vj）就有可能是從vi到頂點vj的中間頂點的序號不大于l的

55、最短路徑。將它和已經(jīng)得到的從vi到頂點vj的中間頂點序號不大于0的最短路徑相比較，從中選出中間頂點的序號不大于1的最短路徑之后，再增加一個頂點v2，繼續(xù)進行試探。依次類推。在一般情況下，若（vi，vk）和（vk，vj）分別是從vi到頂點vk和從vk到頂點vj的中間頂點的序號不大于k-1的最短路徑，則將（vi，vk，vj）和已經(jīng)得到的從vi到vj且中間頂點序號不大于k-1的最短路徑相比較，其長度較短者便是從頂點vi到頂點vj的中間序號不大于k的最短路徑。這樣，在經(jīng)過n次比較后，最后求得的必是從頂點vi到頂點vj的最短路徑。按此方法，可以同時求得各對頂點的最短路徑。四 實驗設(shè)備、儀器、工具與資料

56、微機、VC五 實驗內(nèi)容（1）實驗任務(wù)1：圖的遍歷針對下圖所示的有向圖，編寫C程序完成如下功能：1）建立有向圖的鄰接表2）并在鄰接表存儲基礎(chǔ)上完成深度優(yōu)先遍歷和廣度優(yōu)先遍歷。（2）實驗任務(wù)2：求解圖的最短路徑給出五個城市的交通圖如圖5-2所示，弧上數(shù)字表示城市之間的道路長度?，F(xiàn)要在五個城市中選擇一個城市建造一個物流配送中心。問這個物流配送中心應(yīng)設(shè)在哪個城市到其他城市的路程之和最短？請編程解決這個問題。六 實驗步驟（1）實驗預(yù)習(xí)1）預(yù)習(xí)本實驗原理中關(guān)于圖的存儲表示。2）分析掌握教材128頁中C程序以及133134頁算法5-3，為完成實驗任務(wù)1做好準備。3）分析掌握教材139142頁中的算法5-55

57、-6，為完成實驗任務(wù)1做好準備。4）分析掌握教材158160頁中的算法5-105-11，為完成實驗任務(wù)2做好準備。（2）實驗步驟1）問題分析。充分地分析和理解此實驗任務(wù)，弄清要求作什么，限制條件是什么。2）系統(tǒng)的結(jié)構(gòu)設(shè)計。按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊。最后寫出每個子程序（過程或函數(shù)）的規(guī)格說明，列出它們之間的調(diào)用關(guān)系，可以使用調(diào)用關(guān)系圖表示則更加清晰，這樣便完成了系統(tǒng)結(jié)構(gòu)設(shè)計。3）詳細設(shè)計。詳細設(shè)計的目的是對子程序（過程或函數(shù)）的進一步求精。用 IF 、WHILE和賦值語句等，以及自然語言寫出算法的框架。利用自然語言的目的是避免陷入細節(jié)。4）編碼。在詳細設(shè)計的基礎(chǔ)上，對詳細設(shè)計的結(jié)果進一

58、步求精，用C語言表示出來。5）在VC環(huán)境下調(diào)試程序。七 實驗報告要求實驗報告包含程序開發(fā)過程所形成的所有文檔資料，包括如下內(nèi)容：1）需求分析及規(guī)格說明：問題描述，求解的問題是什么。2）概要設(shè)計：本程序所用的數(shù)據(jù)類型定義；主程序流程；程序模塊及相互關(guān)系。3）詳細設(shè)計：采用C語言定義的數(shù)據(jù)結(jié)構(gòu)；各模塊的偽碼算法；各函數(shù)調(diào)用關(guān)系。4）調(diào)試報告。5）本實驗任務(wù)1、2的程序清單及運行結(jié)果。八 思考題 1）為什么實現(xiàn)圖的遍歷操作時采用鄰接表存儲結(jié)構(gòu)，而求解最短路徑問題時采用鄰接矩陣存儲結(jié)構(gòu)？ 2）如何由圖的鄰接矩陣得到圖的鄰接表？實驗六 查找/檢索一 實驗任務(wù)1）靜態(tài)查找方法的實現(xiàn)2）動態(tài)查找方法的實現(xiàn)二

59、 實驗?zāi)康?）掌握典型的查找方法（折半查找、二叉樹查找）。2）了解各種查找方法的適用范圍和效率。三 實驗原理1 查找表表（Table）是由同一種類型數(shù)據(jù)元素（記錄）構(gòu)成的集合。表的抽象數(shù)據(jù)類型定義如下：ADT Table數(shù)據(jù)對象：具有同種數(shù)據(jù)類型的數(shù)據(jù)元素的集合； 數(shù)據(jù)關(guān)系：數(shù)據(jù)元素之間無特定的次序關(guān)系，同屬一個集合； 基本操作： CreateTable (&L)操作結(jié)果：創(chuàng)建一個空表L。TableEmpty( L )初始條件：表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE。 TableInsert(&L, newItem)初始條件：表L已存在，newItem為給定元素。

60、操作結(jié)果：在表L中插入一個新數(shù)據(jù)元素newItem。 TableDelete(&L, searchKey)初始條件：表L已存在，searchKey為給定元素。操作結(jié)果：在表L中刪除一個關(guān)鍵字值等于searchKey 的數(shù)據(jù)元素。 TableSearch( L, searchKey)初始條件：表L已存在，searchKey為給定元素。操作結(jié)果：在表中查找一個關(guān)鍵字值等于searchKey 的數(shù)據(jù)元素。 TableTraverse( L, visit( )初始條件：表L已存在，visit( )是對元素操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)中元素調(diào)用函數(shù)visit( )一次且僅一次。一旦visit