數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)手冊.

1、算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)手冊計算機(jī)教研室2008.61實(shí)驗(yàn)教學(xué)的目的：通過實(shí)驗(yàn)，加深對算法與數(shù)據(jù)結(jié)構(gòu)基本知識的理解，掌握數(shù)據(jù)結(jié)構(gòu)的理論和設(shè)計技術(shù)及其使用，培養(yǎng)學(xué)生數(shù)據(jù)結(jié)構(gòu)的設(shè)計、開發(fā)能力。2實(shí)驗(yàn)教學(xué)的要求：學(xué)生每次實(shí)驗(yàn)前必須根據(jù)實(shí)驗(yàn)指導(dǎo)手冊，設(shè)計出實(shí)驗(yàn)方案（程序和實(shí)驗(yàn)步驟）；在實(shí)驗(yàn)過程中要求獨(dú)立進(jìn)行程序調(diào)試和排錯，必須學(xué)會使用在線幫助解決實(shí)驗(yàn)中遇到的問題，必須應(yīng)用理論知識分析問題、解決問題。3實(shí)驗(yàn)內(nèi)容：實(shí)驗(yàn)1：VC6的使用一、實(shí)驗(yàn)?zāi)康睦斫夂驼莆杖绾问褂肰isual C6.0環(huán)境編寫C/C程序。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計4學(xué)時。三、實(shí)驗(yàn)內(nèi)容1、熟悉VC6環(huán)境掌握如

2、何創(chuàng)建控制臺應(yīng)用程序。掌握一些常用快捷鍵，例如編譯F7，運(yùn)行CtrlF5，調(diào)試運(yùn)行F5，單步運(yùn)行F10/F11，設(shè)置斷點(diǎn)F9，格式化代碼AltF8。2、掌握如何編譯程序理解編譯過程中的錯誤信息，并掌握如何排錯。3、掌握如何調(diào)試程序掌握如何通過設(shè)置斷點(diǎn)來單步調(diào)試程序，如何查看當(dāng)前變量的值。4、實(shí)驗(yàn)題：完成實(shí)驗(yàn)教材的實(shí)驗(yàn)題1.1、1.2、1.3。要求：實(shí)現(xiàn)該實(shí)驗(yàn)結(jié)果。通過該實(shí)驗(yàn)題，熟悉VC6環(huán)境下的程序編寫、編譯、調(diào)試。實(shí)驗(yàn)2：順序表基本運(yùn)算一、實(shí)驗(yàn)?zāi)康模?）掌握順序表的各種基本運(yùn)算的實(shí)現(xiàn)。（2）能夠利用基本運(yùn)算進(jìn)行順序表的操作。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計2學(xué)時。

3、三、實(shí)驗(yàn)內(nèi)容1、順序表基本運(yùn)算實(shí)現(xiàn)順序表的各種基本運(yùn)算；并在此基礎(chǔ)上設(shè)計一個主程序，完成如下功能：（1） 初始化順序表L（元素類型為char型）（2） 依次采用尾插法插入a, b, c, d, e元素（3） 輸出順序表L（4） 輸出順序表L的長度（5） 判斷順序表L是否為空（6） 輸出順序表L的第3個元素（7） 輸出元素a 的位置（8） 在第4個元素位置上插入f元素（9） 輸出順序表L（10） 刪除順序表L的第3個元素（11） 輸出順序表（12） 釋放順序表提示：可以參考上課教材、實(shí)驗(yàn)教材的實(shí)驗(yàn)題2.1。2、順序表的應(yīng)用（選做）（1）設(shè)計通訊錄（也可為其他應(yīng)用）文件的存儲格式和線性表的順序存儲

4、結(jié)構(gòu)（2）設(shè)計在通訊錄（也可為其他應(yīng)用）中添加、刪除、查找某個節(jié)點(diǎn)信息程序（3）調(diào)試程序?qū)嶒?yàn)3：單鏈表基本運(yùn)算一、實(shí)驗(yàn)?zāi)康模?）掌握鏈表的概念；掌握單鏈表的各種基本運(yùn)算的實(shí)現(xiàn)。（2）能夠利用基本運(yùn)算進(jìn)行單鏈表的操作。（3）加深對鏈?zhǔn)酱鎯?shù)據(jù)結(jié)構(gòu)的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計2學(xué)時。三、實(shí)驗(yàn)內(nèi)容實(shí)現(xiàn)單鏈表的各種基本運(yùn)算；并在此基礎(chǔ)上設(shè)計一個主程序，完成如下功能：（1）初始化單鏈表L（2）依次采用尾插法插入a, b, c, d, e元素（3）輸出單鏈表L（4）輸出單鏈表L的長度（5）判斷單鏈表L是否為空（6）輸出單鏈表L的第3個

5、元素（7）輸出元素a 的位置（8）在第4個元素位置上插入f元素（9）輸出單鏈表L（10）刪除單鏈表L的第3個元素（11）輸出單鏈表L（12）釋放單鏈表L提示：可以參考上課教材、實(shí)驗(yàn)教材的實(shí)驗(yàn)題2.2。實(shí)驗(yàn)4：單鏈表綜合實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康模?）能夠利用單鏈表的基本運(yùn)算進(jìn)行單鏈表的相關(guān)操作。（2）掌握文件的應(yīng)用（3）加深對鏈?zhǔn)酱鎯?shù)據(jù)結(jié)構(gòu)的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計4學(xué)時。三、實(shí)驗(yàn)內(nèi)容1、通訊錄設(shè)計設(shè)計一個班級同學(xué)的通訊錄，要求如下：ü 通訊錄中每個同學(xué)的信息包含以下內(nèi)容：學(xué)號（id）、姓名（name）、電話號碼（te

6、l）。如果需要更多其他信息，請自行添加。ü 程序主菜單包含以下幾個功能：（1） 添加記錄：通過鍵盤輸入信息，添加一條通訊錄記錄。（2） 刪除記錄：通過鍵盤輸入學(xué)號，刪除該學(xué)號的記錄。（3） 輸出記錄：輸出通訊錄全部記錄。（4） 按姓名查找：通過鍵盤輸入姓名，輸出該同學(xué)的所有信息。（5） 保存記錄：把通訊錄中所有的記錄保存到文件中。（6） 清空記錄：刪除通訊錄中的全部記錄，并刪除文件。（7） 退出提示：ü 程序啟動時應(yīng)判斷是否存在記錄文件，如果存在，則讀取每條記錄到鏈表中。ü 用戶選擇并完成主菜單某功能后，除了退出程序，應(yīng)該返回主菜單。ü 添加一條記錄時，

7、插入到鏈表的尾部。ü 查找、刪除記錄時，如果該記錄不存在，則應(yīng)該輸出不存在的提示。ü 添加記錄、刪除記錄時不需要寫文件。ü 保存記錄時，用覆蓋寫文件的方法。（或者先刪除原文件，再保存全部記錄信息）ü 各個功能模塊寫成函數(shù)，由主函數(shù)調(diào)用。選做：ü 主菜單增加一個排序功能選項，可以按照學(xué)號從小到大進(jìn)行排序。排序方法可以用冒泡排序或者插入排序。實(shí)驗(yàn)5：鏈棧的基本操作一、實(shí)驗(yàn)?zāi)康?）熟悉棧的定義和棧的基本操作。2）掌握鏈?zhǔn)酱鎯５幕具\(yùn)算。3）加深對棧數(shù)據(jù)結(jié)構(gòu)的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)

8、驗(yàn)共計2學(xué)時。三、實(shí)驗(yàn)內(nèi)容必做內(nèi)容： 鏈棧的基本操作編寫棧的基本操作函數(shù)1 棧類型的定義，數(shù)據(jù)域使用char型typedef char ElemType;typedef struct node ElemType data; struct node *next; LinkStack;2初始化空棧：函數(shù)原型如下： void InitLinkStack（ LinkStack * & s）其中函數(shù)參數(shù)為LinkStack * & 類型，表示指向創(chuàng)建的空棧的指針，并且用引用方式傳入。3. 判斷是否空棧：函數(shù)原型如下：int IsEmptyLinkStack（LinkStack *s ）

9、其中函數(shù)參數(shù)為棧指針；返回值為int型，1表示是空棧，0表示不是空棧。4. 入棧：函數(shù)原型如下：void PushLinkStack（LinkStack* &s , ElemType x） 其中函數(shù)參數(shù)s為棧指針，x為入棧的數(shù)據(jù)。 5. 出棧：函數(shù)原型如下：int PopLinkStack (LinkStack* & s, ElemType &x)其中函數(shù)參數(shù)s為棧指針，x為出棧的數(shù)據(jù)的引用；返回值為int型，1表示出棧成功，0表示出棧失敗。6取棧頂元素：(棧保持不變)函數(shù)原型如下：int GetLinkStackTop (LinkStack* s, ElemType

10、&x)其中函數(shù)參數(shù)s為棧指針，x存放棧頂元素值；返回值為int型，1表示成功，0表示失敗。編寫主函數(shù)調(diào)用上述函數(shù)實(shí)現(xiàn)下列操作。1初始化空棧。2. 鍵盤輸入字符，使得輸入的字符依次入棧（結(jié)束符號自定，例如回車鍵(值為10)或'#'） 每插入一個元素，必須輸出當(dāng)時的棧頂元素(調(diào)用GetLinkStackTop函數(shù))。 3判斷鏈棧是否為空。輸出判斷結(jié)果。4調(diào)用出棧函數(shù)，打印出棧元素的值；反復(fù)此步驟，直至棧為空。5判斷鏈棧是否為空。輸出判斷結(jié)果。6釋放鏈棧。選做內(nèi)容（一）：判斷對稱字符串設(shè)計一個算法，調(diào)用棧的基本運(yùn)算，判斷一個字符串是否為對稱字符串。若是返回1；否則返回0。例如

11、：“abcba”和“abba”都是對稱字符串。實(shí)驗(yàn)6：隊列的基本操作一、實(shí)驗(yàn)?zāi)康?）熟悉隊列的定義和隊列的基本操作。2）掌握順序循環(huán)隊列和鏈?zhǔn)酱鎯﹃犃械幕具\(yùn)算。3）加深對隊列數(shù)據(jù)結(jié)構(gòu)的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計2學(xué)時。三、實(shí)驗(yàn)內(nèi)容隊列的基本操作隊列的存儲結(jié)構(gòu)從順序循環(huán)隊列或者鏈隊任選一種。編寫一個程序，實(shí)現(xiàn)隊列的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計一個主程序，完成如下功能：（1） 初始化隊列q（2） 判斷q是否非空（3） 依次進(jìn)隊元素a，b，c（4） 出隊一個元素，輸出該元素（5） 輸出隊列q的元素個數(shù)（6） 依次進(jìn)隊列元素d

12、，e，f（7） 輸出隊列q的元素個數(shù)（8） 輸出出隊序列（9） 釋放隊列實(shí)驗(yàn)7：棧和隊列綜合實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康模?）能夠利用棧和隊列的基本運(yùn)算進(jìn)行相關(guān)操作。（2）進(jìn)一步熟悉文件的應(yīng)用（3）加深隊列和棧的數(shù)據(jù)結(jié)構(gòu)理解，逐步培養(yǎng)解決實(shí)際問題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計4學(xué)時。三、實(shí)驗(yàn)內(nèi)容以下兩個實(shí)驗(yàn)任選一個。1、 迷宮求解設(shè)計一個迷宮求解程序，要求如下：ü 以M × N表示長方陣表示迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。ü 能任意設(shè)定的迷宮ü （選作）如果有通路，列出所有通路提示：ü 以一

13、個二維數(shù)組來表示迷宮，0和1分別表示迷宮中的通路和障礙，如下圖迷宮數(shù)據(jù)為：1111111111100100010110010001011000011001101110000110001000011010001001101110110111000000011111111111入口位置：1 1出口位置：8 8ü 探索過程可采用如下算法，設(shè)定當(dāng)前位置的初值為入口位置；do 若當(dāng)前位置可通，則將當(dāng)前位置插入棧頂；若該位置是出口位置，則結(jié)束；否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置； 否則， 若棧不空且棧頂位置尚有其他方向未經(jīng)探索，則設(shè)定新的當(dāng)前位置為沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊

14、；若棧不空但棧頂位置的四周均不可通，則刪去棧頂位置；/從路徑中刪去該通道塊若棧不空，則重新測試新的棧頂位置，直至找到一個可通的相鄰塊出棧至棧空；while (棧不空)；2、機(jī)場飛機(jī)起降的過程模擬熟悉隊列的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計一個主程序，完成如下功能：ü 模擬一個機(jī)場飛機(jī)起降的過程ü 機(jī)場僅有一條跑道，要求起飛與降落不能同時進(jìn)行ü 進(jìn)場飛機(jī)若暫時沒有跑道可用須在空中盤旋等候ü 離場飛機(jī)若暫時沒有跑道可用須在地面排隊等候ü 僅當(dāng)空中無飛機(jī)等待降落時地面飛機(jī)方可起飛ü 飛機(jī)的申請進(jìn)場、降落、申請離場和起飛分別視為獨(dú)立事件ü

15、; 每個事件的發(fā)生占用一個時間單位。除降落和起飛外，各事件可以同時發(fā)生提示：ü 設(shè)定一個待飛隊列用于存放排隊等候的航班信息ü 設(shè)定一個待降落隊列用于存放等待降落的航班信息ü 飛機(jī)的申請進(jìn)場、降落、申請離場和起飛可以通過航班事先設(shè)定的起飛時間、飛行時間長度或者降落時間信息來確定，這些信息可以存放在一個文件中，程序運(yùn)行時從文件中讀出。ü 航班當(dāng)前狀態(tài)可表示為：起飛，降落，申請進(jìn)場，申請離場，空閑ü 每個事件的發(fā)生占用一個時間單位可以自己約定，起飛，降落可以設(shè)定為30分鐘實(shí)驗(yàn)8：順序串的基本操作一、實(shí)驗(yàn)?zāi)康?）熟悉串的定義和串的基本操作。2）掌握順序

16、串的基本運(yùn)算。3）加深對串?dāng)?shù)據(jù)結(jié)構(gòu)的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計2學(xué)時。三、實(shí)驗(yàn)內(nèi)容編寫一個程序，實(shí)現(xiàn)順序串的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計一個主程序。具體如下：編寫棧的基本操作函數(shù)順序串類型定義如下所示：typedef struct char chMAXSIZE; int len; SeqString;（1）串賦值 Assign(s,t)n 將一個字符串常量賦給串s,即生成一個其值等于t的串s（2）串復(fù)制 StrCopy(s,t)n 將串t賦給串s（3）計算串長度 StrLength(s)n 返回串s中字符個數(shù)（4）判斷串

17、相等StrEqual(s,t)n 若兩個串s與t相等則返回1；否則返回0。（5）串連接 Concat(s,t) n 返回由兩個串s和t連接在一起形成的新串。（6）求子串 SubStr(s,i,j)n 返回串s中從第i(1iStrLength(s)個字符開始的、由連續(xù)j個字符組成的子串。（7）插入InsStr (s,i,t)n 將串t插入到串s的第i(1iStrLength(s)+1)個字符中,即將t的第一個字符作為s的第i個字符,并返回產(chǎn)生的新串（8）串刪除 DelStr (s,i,j)n 從串s中刪去從第i(1iStrLength(s)個字符開始的長度為j的子串,并返回產(chǎn)生的新串。（9）串替

18、換 RepStr (s,s1,s2)n 在串s中,將所有出現(xiàn)的子串s1均替換成s2。（10）輸出串DispStr(s)n 輸出串s的所有元素值（11）判斷串是否為空 IsEmpty(s)編寫主函數(shù)調(diào)用上述函數(shù)實(shí)現(xiàn)下列操作：（1） 建立串s=“abcdefghijklmn”，串s1=“xyz”，串t“hijk”（2） 復(fù)制串t到t1，并輸出t1的長度（3） 在串s的第9個字符位置插入串s1而產(chǎn)生串s2，并輸出s2（4） 刪除s第2個字符開始的5個字符而產(chǎn)生串s3，并輸出s3（5） 將串s第2個字符開始的3個字符替換成串s1而產(chǎn)生串s4，并輸出s4（6） 提取串s的第8個字符開始的4個字符而產(chǎn)生串

19、s5，并輸出s5（7） 將串s1和串t連接起來而產(chǎn)生串s6，并輸出s6（8） 比較串s1和s5是否相等，輸出結(jié)果實(shí)驗(yàn)9：矩陣的基本操作一、實(shí)驗(yàn)?zāi)康?）熟悉數(shù)組、矩陣的定義和基本操作。2）掌握對稱矩陣、稀疏矩陣等特殊矩陣的存儲方式和基本運(yùn)算。3）加深對數(shù)組、矩陣的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計2學(xué)時。三、實(shí)驗(yàn)內(nèi)容以下兩個實(shí)驗(yàn)任選一個。1、實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置、求和假設(shè)m×n的稀疏矩陣用三元組表示，編寫一個程序?qū)崿F(xiàn)如下功能：（1） 生成如下兩個稀疏矩陣的三元組a和b，并輸出三元組表示。1 0 3 00 1 0 00 0 1

20、 00 0 1 03 0 0 00 4 0 00 0 1 00 0 0 2提示：程序中可以用int A44和B44二維數(shù)組表示原始矩陣A和B。（2） 輸出a的轉(zhuǎn)置矩陣的三元組表示。（3） 設(shè)cab，輸出c的三元組表示。2、求對稱矩陣之和、乘積已知A和B為兩個n×n階的對稱矩陣，編寫一個程序?qū)崿F(xiàn)：（1） 將其下三角元素存儲在一維數(shù)組a和b中，并輸出。1 1 2 41 2 3 52 3 4 64 5 6 71 1 1 11 1 1 11 1 1 11 1 1 1提示：程序中可以用int A44和B44二維數(shù)組表示原始矩陣A和B。（2） 設(shè)CAB，以矩陣方式輸出C。（3） 設(shè)DA×

21、;B，以矩陣方式輸出D。實(shí)驗(yàn)10：字符串綜合實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康?）熟悉串的定義和串的基本操作。2）加深對串?dāng)?shù)據(jù)結(jié)構(gòu)的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計4學(xué)時。三、實(shí)驗(yàn)內(nèi)容以下兩個實(shí)驗(yàn)任選一個。1、凱撒加密算法凱撒密碼（caeser）是羅馬擴(kuò)張時期朱利斯凱撒（Julius Caesar）創(chuàng)造的，用于加密通過信使傳遞的作戰(zhàn)命令。它將字母表中的字母移動一定位置而實(shí)現(xiàn)加密。他的原理很簡單，說到底就是字母與字母之間的替換。每一個字母按字母表順序向后移3位，如a加密后變成d，b加密后變成e，····

22、83;·x加密后變成a，y加密后變成b，z加密后變成c。例如：“baidu”用凱撒密碼法加密后字符串變?yōu)椤癳dlgx”。試寫一個算法，將鍵盤輸入的文本字符串（只包含az的字符）進(jìn)行加密后輸出。另寫一個算法，將已加密后的字符串解密后輸出。提示：ü 如果有字符變量c加密后則a（c-a3）26ü 采用順序結(jié)構(gòu)存儲串，鍵盤輸入字符串后保存到順序串中；輸出用順序串的輸出函數(shù)。2、求一個串中出現(xiàn)的第一個最長重復(fù)子串采用順序結(jié)構(gòu)存儲串，編寫一個程序，求串s中出現(xiàn)的第一個最長重復(fù)子串的下標(biāo)和長度。實(shí)驗(yàn)11：遞歸綜合實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康?）熟悉遞歸的定義和遞歸的算法設(shè)計。2）加深對遞歸

23、算法的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計4學(xué)時。三、實(shí)驗(yàn)內(nèi)容以下兩個實(shí)驗(yàn)任選一個。1、求解n皇后問題編寫一個程序，求解皇后問題：在n×n的方格棋盤上，放置n個皇后，要求每個皇后不同行、不同列、不同對角線。要求：使用遞歸算法求解；皇后的個數(shù)n由用戶輸入，其值不能超過20。2、求解漢諾塔問題設(shè)有3個分別命名為X,Y和Z的塔座,在塔座X上有n個直徑各不相同,從小到大依次編號為1,2,n的盤片,現(xiàn)要求將X塔座上的n個盤片移到塔座Z上并仍按同樣順序疊放,盤片移動時必須遵守以下規(guī)則：每次只能移動一個盤片；盤片可以插在X,Y和Z中任一

24、塔座；任何時候都不能將一個較大的盤片放在較小的盤片上。設(shè)計遞歸求解算法。要求：使用遞歸算法求解；盤片的個數(shù)n由用戶輸入，其值不能超過12。實(shí)驗(yàn)12：二叉樹的操作一、實(shí)驗(yàn)?zāi)康?）熟悉二叉樹樹的基本操作。2）掌握二叉樹的實(shí)現(xiàn)以及實(shí)際應(yīng)用。3）加深二叉樹的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計4學(xué)時。三、實(shí)驗(yàn)內(nèi)容1、二叉樹的基本操作【問題描述】現(xiàn)需要編寫一套二叉樹的操作函數(shù)，以便用戶能夠方便的利用這些函數(shù)來實(shí)現(xiàn)自己的應(yīng)用。其中操作函數(shù)包括：1> 創(chuàng)建二叉樹CreateBTNode(*b,*str)：根據(jù)二叉樹括號表示法的字符串*str

25、生成對應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)。2> 輸出二叉樹DispBTNode(*b)：以括號表示法輸出一棵二叉樹。3> 查找結(jié)點(diǎn)FindNode(*b,x)：在二叉樹b中尋找data域值為x的結(jié)點(diǎn),并返回指向該結(jié)點(diǎn)的指針。4> 求高度BTNodeDepth(*b)：求二叉樹b的高度。若二叉樹為空,則其高度為0；否則,其高度等于左子樹與右子樹中的最大高度加l。5> 求二叉樹的結(jié)點(diǎn)個數(shù)NodesCount(BTNode *b)6> 先序遍歷的遞歸算法：void PreOrder(BTNode *b) 7> 中序遍歷的遞歸算法：void InOrder(BTNode *b) 8&

26、gt; 后序遍歷遞歸算法：void PostOrder(BTNode *b) 9> 層次遍歷算法void LevelOrder(BTNode *b)【基本要求】實(shí)現(xiàn)以上9個函數(shù)。主函數(shù)中實(shí)現(xiàn)以下功能：創(chuàng)建下圖中的樹b輸出二叉樹b找到H節(jié)點(diǎn)，輸出其左右孩子值輸出b的高度輸出b的節(jié)點(diǎn)個數(shù)輸出b的四種遍歷順序ABDCEHJKLMNFGI【實(shí)驗(yàn)提示】數(shù)據(jù)結(jié)構(gòu)的定義：#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct nodeElemType

27、 data;/*數(shù)據(jù)元素*/struct node *lchild;/*指向左孩子*/struct node *rchild;/*指向右孩子*/ BTNode;各個函數(shù)的定義：void CreateBTNode(BTNode *&b,char *str);BTNode *FindNode(BTNode *b,ElemType x);int BTNodeDepth(BTNode *b);void DispBTNode(BTNode *b);int NodesCount(BTNode *b);void PreOrder(BTNode *b);void InOrder(BTNode *b);

28、void PostOrder(BTNode *b);void TravLevel(BTNode *b);主函數(shù)的結(jié)構(gòu)：void main()BTNode *b,*p,*lp,*rp;char str="A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)"CreateBTNode(b,str); printf("n");printf("輸出二叉樹:");DispBTNode(b);printf("n");printf("'H'結(jié)點(diǎn):");p=FindNode(b,

29、9;H');if (p!=NULL)/此處輸出p的左右孩子節(jié)點(diǎn)的值printf("n");printf("二叉樹b的深度:%dn",BTNodeDepth(b);printf("二叉樹b的結(jié)點(diǎn)個數(shù):%dn",NodesCount(b);printf("n");printf(" 先序遍歷序列:n");printf(" 遞歸算法:");PreOrder(b);printf("n");printf(" 中序遍歷序列:n");print

30、f(" 遞歸算法:");InOrder(b);printf("n");printf(" 后序遍歷序列:n");printf(" 遞歸算法:");PostOrder(b);printf("n");printf(" 層次遍歷序列:"); printf("n");TravLevel(b); printf("n");2.2 二叉樹的線索化【問題描述】編寫一個程序，實(shí)現(xiàn)中序線索化二叉樹，輸出線索中序序列?！净疽蟆坑蒙蠄D的二叉樹b來驗(yàn)證你的程序

31、。【實(shí)驗(yàn)提示】數(shù)據(jù)結(jié)構(gòu)的定義：#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct node ElemType data;int ltag,rtag; /*增加的線索標(biāo)記*/struct node *lchild;struct node *rchild; TBTNode;TBTNode *pre;各個函數(shù)的定義：void CreateTBTNode(TBTNode * &b,char *str)void DispTBTNode(TB

32、TNode *b)void Thread(TBTNode *&p)TBTNode *CreaThread(TBTNode *b) /*中序線索化二叉樹*/void ThInOrder(TBTNode *tb)主函數(shù)的結(jié)構(gòu)：void main()TBTNode *b,*tb;CreateTBTNode(b,"A(B(D,E(H(J,K(L,M(,N),C(F,G(,I)"); printf(" 二叉樹:");DispTBTNode(b);printf("n");tb=CreaThread(b);printf(" 線索中

33、序序列:");ThInOrder(tb);printf("n");3實(shí)驗(yàn)結(jié)果此處填寫程序運(yùn)行結(jié)果。4實(shí)驗(yàn)心得此處填寫你的實(shí)驗(yàn)心得體會。實(shí)驗(yàn)13：哈夫曼編碼一、實(shí)驗(yàn)?zāi)康?）熟悉哈夫曼樹的基本操作。2）掌握哈夫曼編碼的實(shí)現(xiàn)以及實(shí)際應(yīng)用。3）加深對哈夫曼樹、哈夫曼編碼的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計4學(xué)時。三、實(shí)驗(yàn)內(nèi)容【問題描述】利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求發(fā)送端通過一個編碼系統(tǒng)對數(shù)據(jù)進(jìn)行編碼，在接受端將傳來的數(shù)據(jù)進(jìn)行譯碼。試為這樣的信息收發(fā)

34、站寫一個哈夫曼編碼/譯碼系統(tǒng)?！净疽蟆勘鞠到y(tǒng)應(yīng)實(shí)現(xiàn)以下功能：（功能13必做，4為選做，請課后自行完成）（1） 初始化：字符集（字母az，空格）共27個字符，以及其權(quán)值。建立哈夫曼樹。并建立各個字符的哈夫曼編碼。（2） 打印字符集的哈夫曼編碼。（3） 編碼：從終端讀入字符串，實(shí)現(xiàn)該字符串的編碼。（4） 譯碼：實(shí)現(xiàn)剛才生成的哈夫曼編碼還原為字符串。（選做）【已知條件】（1）字符集的權(quán)值如下表：【實(shí)驗(yàn)提示】數(shù)據(jù)結(jié)構(gòu)的定義：#define N 50/*葉子結(jié)點(diǎn)數(shù)*/#define M 2*N-1/*樹中結(jié)點(diǎn)總數(shù)*/typedef structchar data;/*結(jié)點(diǎn)值*/int weight;

35、/*權(quán)重*/int parent;/*雙親結(jié)點(diǎn)*/int lchild;/*左孩子結(jié)點(diǎn)*/int rchild;/*右孩子結(jié)點(diǎn)*/ HTNode;typedef structchar cdN;/*存放哈夫曼碼*/int start; HCode;各個函數(shù)的定義：void CreateHT(HTNode ht,int n)/*創(chuàng)建哈夫曼樹*/void CreateHCode(HTNode ht,HCode hcd,int n)/*創(chuàng)建哈夫曼編碼*/void DispHCode(HTNode ht,HCode hcd,int n)/*顯示各個字符的哈夫曼編碼*/void Encode(char *

36、s,HTNode ht,HCode hcd,int n) /*顯示字符串s的哈夫曼編碼*/主函數(shù)的結(jié)構(gòu)：char str=' ','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s'

37、,'t','u','v','w','x','y','z' /*字符集*/int fnum=186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1; /*字符集對應(yīng)的權(quán)值*/CreateHT();CreateHCode();DispHCode();gets(s);Encode();實(shí)驗(yàn)14：圖的存儲和遍歷一、實(shí)驗(yàn)?zāi)康?）熟悉圖的基本操作。2）掌握圖的存儲實(shí)現(xiàn)以及遍歷操作。3）加深對圖的理解

38、，逐步培養(yǎng)解決實(shí)際問題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計2學(xué)時。三、實(shí)驗(yàn)內(nèi)容【基本要求】1、用鄰接矩陣存儲方式，表示下面的圖，并輸出。2、由上面的鄰接矩陣產(chǎn)生鄰接表，并輸出。3、編程完成從頂點(diǎn)0開始的深度優(yōu)先遍歷和廣度優(yōu)先遍歷?！据敵鼋Y(jié)果】輸出結(jié)果例子如下：有向圖G的鄰接矩陣: 0 5 0 7 0 0 0 0 4 0 0 0 8 0 0 0 0 9 0 0 5 0 0 6 0 0 0 5 0 0 3 0 0 0 1 0 圖G的鄰接矩陣轉(zhuǎn)換成鄰接表: 0: 1 3 1: 2 2: 0 5 3: 2 5 4: 3 5: 0 4從頂點(diǎn)0開始的DFS: 0 1 2

39、 5 4 3從頂點(diǎn)0開始的BFS: 0 1 3 2 5 4【提示】#include <stdio.h>#include <malloc.h>#defineMAXV 100/*最大頂點(diǎn)個數(shù)*/#define INF 32767 /*INF表示*/typedef int InfoType;/*以下定義鄰接矩陣類型*/typedef struct int no;/*頂點(diǎn)編號*/InfoType info;/*頂點(diǎn)其他信息*/ VertexType;/*頂點(diǎn)類型*/typedef struct /*圖的定義*/ int edgesMAXVMAXV; /*鄰接矩陣*/ int v

40、exnum,arcnum; /*頂點(diǎn)數(shù)，弧數(shù)*/VertexType vexsMAXV;/*存放頂點(diǎn)信息*/ MGraph;/*圖的鄰接矩陣類型*/*以下定義鄰接表類型*/typedef struct ANode /*弧的結(jié)點(diǎn)結(jié)構(gòu)類型*/int adjvex; /*該弧的終點(diǎn)位置*/ struct ANode *nextarc; /*指向下一條弧的指針*/ InfoType info; /*該弧的相關(guān)信息,這里用于存放權(quán)值*/ ArcNode;typedef int Vertex;typedef struct Vnode /*鄰接表頭結(jié)點(diǎn)的類型*/Vertex data; /*頂點(diǎn)信息*/ A

41、rcNode *firstarc; /*指向第一條弧*/ VNode;typedef VNode AdjListMAXV;/*AdjList是鄰接表類型*/typedef struct AdjList adjlist; /*鄰接表*/ int n,e; /*圖中頂點(diǎn)數(shù)n和邊數(shù)e*/ ALGraph; /*圖的鄰接表類型*/int visitedMAXV;/*全局?jǐn)?shù)組*/void MatToList(MGraph,ALGraph *&);/*鄰接矩陣轉(zhuǎn)為鄰接表*/void DispMat(MGraph);/*輸出鄰接矩陣*/void DispAdj(ALGraph *);/*輸出鄰接表*

42、/void DFS(ALGraph *G,int v);/*深度優(yōu)先遍歷*/void BFS(ALGraph *G,int v);/*廣度優(yōu)先遍歷*/void main()int i,j;MGraph g;ALGraph *G;int AMAXV6=0,5,0,7,0,0,0,0,4,0,0,0,8,0,0,0,0,9,0,0,5,0,0,6,0,0,0,5,0,0,3,0,0,0,1,0;g.vexnum=6;g.arcnum=10;for (i=0;i<g.vexnum;i+)for (j=0;j<g.vexnum;j+)g.edgesij=Aij;printf("n

43、");printf(" 有向圖G的鄰接矩陣:n");DispMat(g);G=(ALGraph *)malloc(sizeof(ALGraph);printf(" 圖G的鄰接矩陣轉(zhuǎn)換成鄰接表:n");MatToList(g,G);DispAdj(G);printf("n");printf("從頂點(diǎn)0開始的DFS:n");DFS(G,0);printf("n");printf("從頂點(diǎn)0開始的BFS:n");BFS(G,0);printf("n")

44、;void MatToList(MGraph g,ALGraph *&G)/*將鄰接矩陣g轉(zhuǎn)換成鄰接表G*/*輸入代碼*/void DispMat(MGraph g)/*輸出鄰接矩陣g*/*輸入代碼*/void DispAdj(ALGraph *G)/*輸出鄰接表G*/*輸入代碼*/void DFS(ALGraph *G,int v) /*輸入代碼*/void BFS(ALGraph *G,int v) /*輸入代碼*/實(shí)驗(yàn)15：Prim算法求最小生成樹一、實(shí)驗(yàn)?zāi)康?）熟悉圖的基本操作。2）掌握利用Prim算法求圖的最小生成樹。3）加深對圖的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力。二、實(shí)

45、驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計2學(xué)時。三、實(shí)驗(yàn)內(nèi)容【基本要求】編寫一個程序，對于如下的無向帶權(quán)圖，利用Prim算法輸出從頂點(diǎn)0出發(fā)的最小生成樹。實(shí)驗(yàn)16：圖綜合實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康?）熟悉圖的基本操作。2）掌握求圖的最短路徑算法。3）加深對圖的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計4學(xué)時。三、實(shí)驗(yàn)內(nèi)容【基本要求】給定n個村莊之間的交通圖。若村莊i和j之間有路可通，則i和j用邊連接，邊上的權(quán)值Wij表示這條道路的長度。現(xiàn)打算在這n個村莊中選定一個村莊建一所醫(yī)院。編寫如下算法：（1） 求出該醫(yī)院應(yīng)建在哪個村莊，才能使距

46、離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路程最短。（2） 求出該醫(yī)院應(yīng)建在哪個村莊，能使其它所有村莊到醫(yī)院的路徑總和最短?！咎崾尽?#252; 對于問題（1），可以先求出每個村莊到其它所有村莊的最短路徑，保存其最大值（表示假設(shè)醫(yī)院建在該村莊，距離醫(yī)院最遠(yuǎn)的村莊的路徑長度）；然后在這些最大值中找出一個最小值。ü 對于問題（2），可以先求出每個村莊到其它所有村莊的最短路徑，保存其累加和（表示假設(shè)醫(yī)院建在該村莊，其它所有村莊距離醫(yī)院的路徑總和）；然后在這些和中找出一個最小值。ü 自己設(shè)定n個村莊的交通圖。例如下圖所示：實(shí)驗(yàn)17：線性查找一、實(shí)驗(yàn)?zāi)康?）熟悉查找的基本操作。2）掌握線性查找（順序查

47、找、二分查找）的實(shí)現(xiàn)。3）加深對查找的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計2學(xué)時。三、實(shí)驗(yàn)內(nèi)容1、順序查找編寫一個程序，輸出在順序表中3，6，2，10，1，8，5，7，4，9 中采用順序查找的方法查找關(guān)鍵字5的過程。2、二分查找【基本要求】編寫一個程序，輸出在順序表中1，2，3，4，5，6，7，8，9，10中采用二分查找法查找關(guān)鍵字9的過程。【輸出結(jié)果】輸出結(jié)果例子如下：第1次查找:在0,9中查找到元素R4:5第2次查找:在5,9中查找到元素R7:8第3次查找:在8,9中查找到元素R8:9元素9的位置是8實(shí)驗(yàn)18：哈希查找一、實(shí)驗(yàn)?zāi)?/p>

48、的1）熟悉查找的基本操作。2）掌握哈希查找的實(shí)現(xiàn)。3）加深對查找的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計2學(xué)時。三、實(shí)驗(yàn)內(nèi)容【基本要求】編寫一個程序，實(shí)現(xiàn)哈希表的相關(guān)運(yùn)算，并在此基礎(chǔ)上完成如下功能：（1） 建立16,74,60,43,54,90,46,31,29,88,77哈希表A0.12，哈希函數(shù)為H(k)=key%p，（p取13），并采用線性探查法解決沖突。（2） 在上述哈希表中查找關(guān)鍵字為29的記錄。（3） 在上述哈希表中刪除關(guān)鍵字為77的記錄，再將其插入。【輸出結(jié)果】輸出結(jié)果例子如下：哈希表地址: 0 1 2 3 4 5 6

49、7 8 9 10 11 12 哈希表關(guān)鍵字: 77 54 16 43 31 29 46 60 74 88 90 搜索次數(shù): 2 1 1 1 1 4 1 1 1 1 1 平均搜索長度ASL(11)=1.36364 ha6.key=29 刪除關(guān)鍵字77 哈希表地址: 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表關(guān)鍵字: 54 16 43 31 29 46 60 74 88 90 搜索次數(shù): 1 1 1 1 4 1 1 1 1 1 平均搜索長度ASL(10)=1.3 未找到77 插入關(guān)鍵字77 哈希表地址: 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表關(guān)鍵字:

50、 77 54 16 43 31 29 46 60 74 88 90 搜索次數(shù): 2 1 1 1 1 4 1 1 1 1 1 平均搜索長度ASL(11)=1.36364實(shí)驗(yàn)19：查找綜合實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康?）熟悉查找的基本操作。2）掌握二叉排序樹的基本運(yùn)算。3）加深對查找的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有Visual C6.0的計算機(jī)。本次實(shí)驗(yàn)共計4學(xué)時。三、實(shí)驗(yàn)內(nèi)容1、統(tǒng)計字符串中字符出現(xiàn)的次數(shù)編寫一個程序，由鍵盤輸入一個字符串，統(tǒng)計該字符串中出現(xiàn)的字符及其次數(shù)。然后輸出結(jié)果。要求用一個二叉樹來保存處理結(jié)果，字符串中每個不同的字符用樹的結(jié)點(diǎn)表示，結(jié)點(diǎn)應(yīng)該包含四個域：該字符、該字符出現(xiàn)的次數(shù)、左子樹指針、右子樹指針；其中左子樹的字符的