實(shí)驗(yàn)指導(dǎo)手冊(cè)

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)指導(dǎo)手冊(cè)計(jì)算機(jī)教研室2023.61．實(shí)驗(yàn)教學(xué)的目的：通過(guò)實(shí)驗(yàn)，加深對(duì)算法與數(shù)據(jù)結(jié)構(gòu)基本知識(shí)的理解，掌握數(shù)據(jù)結(jié)構(gòu)的理論和設(shè)計(jì)技術(shù)及其使用，培養(yǎng)學(xué)生數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)、開發(fā)能力。2．實(shí)驗(yàn)教學(xué)的規(guī)定：學(xué)生每次實(shí)驗(yàn)前必須根據(jù)實(shí)驗(yàn)指導(dǎo)手冊(cè)，設(shè)計(jì)出實(shí)驗(yàn)方案（程序和實(shí)驗(yàn)環(huán)節(jié)）；在實(shí)驗(yàn)過(guò)程中規(guī)定獨(dú)立進(jìn)行程序調(diào)試和排錯(cuò)，必須學(xué)會(huì)使用在線幫助解決實(shí)驗(yàn)中碰到的問(wèn)題，必須應(yīng)用理論知識(shí)分析問(wèn)題、解決問(wèn)題。3．實(shí)驗(yàn)內(nèi)容：實(shí)驗(yàn)1：VC6的使用一、實(shí)驗(yàn)?zāi)康睦斫夂驼莆杖绾问褂肰isualC＋＋6.0環(huán)境編寫C/C＋＋程序。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)4學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容1、熟悉VC6環(huán)境掌握如何創(chuàng)建控制臺(tái)應(yīng)用程序。掌握一些常用快捷鍵，例如編譯F7，運(yùn)營(yíng)Ctrl＋F5，調(diào)試運(yùn)營(yíng)F5，單步運(yùn)營(yíng)F10/F11，設(shè)立斷點(diǎn)F9，格式化代碼Alt＋F8。2、掌握如何編譯程序理解編譯過(guò)程中的錯(cuò)誤信息，并掌握如何排錯(cuò)。3、掌握如何調(diào)試程序掌握如何通過(guò)設(shè)立斷點(diǎn)來(lái)單步調(diào)試程序，如何查看當(dāng)前變量的值。4、實(shí)驗(yàn)題：完畢實(shí)驗(yàn)教材的實(shí)驗(yàn)題1.1、1.2、1.3。規(guī)定：實(shí)現(xiàn)該實(shí)驗(yàn)結(jié)果。通過(guò)該實(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)用基本運(yùn)算進(jìn)行順序表的操作。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)2學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容1、順序表基本運(yùn)算實(shí)現(xiàn)順序表的各種基本運(yùn)算；并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序，完畢如下功能：初始化順序表L（元素類型為char型）依次采用尾插法插入a,b,c,d,e元素輸出順序表L輸出順序表L的長(zhǎng)度判斷順序表L是否為空輸出順序表L的第3個(gè)元素輸出元素’a’的位置在第4個(gè)元素位置上插入’f’元素輸出順序表L刪除順序表L的第3個(gè)元素輸出順序表釋放順序表提醒：可以參考上課教材、實(shí)驗(yàn)教材的實(shí)驗(yàn)題2.1。2、順序表的應(yīng)用（選做）（1）設(shè)計(jì)通訊錄（也可為其他應(yīng)用）文獻(xiàn)的存儲(chǔ)格式和線性表的順序存儲(chǔ)結(jié)構(gòu)（2）設(shè)計(jì)在通訊錄（也可為其他應(yīng)用）中添加、刪除、查找某個(gè)節(jié)點(diǎn)信息程序（3）調(diào)試程序?qū)嶒?yàn)3：?jiǎn)捂湵砘具\(yùn)算一、實(shí)驗(yàn)?zāi)康模?）掌握鏈表的概念；掌握單鏈表的各種基本運(yùn)算的實(shí)現(xiàn)。（2）可以運(yùn)用基本運(yùn)算進(jìn)行單鏈表的操作。（3）加深對(duì)鏈?zhǔn)酱鎯?chǔ)數(shù)據(jù)結(jié)構(gòu)的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)2學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容實(shí)現(xiàn)單鏈表的各種基本運(yùn)算；并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序，完畢如下功能：（1） 初始化單鏈表L（2） 依次采用尾插法插入a,b,c,d,e元素（3） 輸出單鏈表L（4） 輸出單鏈表L的長(zhǎng)度（5） 判斷單鏈表L是否為空（6） 輸出單鏈表L的第3個(gè)元素（7） 輸出元素’a’的位置（8） 在第4個(gè)元素位置上插入’f’元素（9） 輸出單鏈表L（10） 刪除單鏈表L的第3個(gè)元素（11） 輸出單鏈表L（12） 釋放單鏈表L提醒：可以參考上課教材、實(shí)驗(yàn)教材的實(shí)驗(yàn)題2.2。實(shí)驗(yàn)4：?jiǎn)捂湵砭C合實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康模?）可以運(yùn)用單鏈表的基本運(yùn)算進(jìn)行單鏈表的相關(guān)操作。（2）掌握文獻(xiàn)的應(yīng)用（3）加深對(duì)鏈?zhǔn)酱鎯?chǔ)數(shù)據(jù)結(jié)構(gòu)的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)4學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容1、通訊錄設(shè)計(jì)設(shè)計(jì)一個(gè)班級(jí)同學(xué)的通訊錄，規(guī)定如下：通訊錄中每個(gè)同學(xué)的信息包含以下內(nèi)容：學(xué)號(hào)（id）、姓名（name）、電話號(hào)碼（tel）。假如需要更多其他信息，請(qǐng)自行添加。程序主菜單包含以下幾個(gè)功能：添加記錄：通過(guò)鍵盤輸入信息，添加一條通訊錄記錄。刪除記錄：通過(guò)鍵盤輸入學(xué)號(hào)，刪除該學(xué)號(hào)的記錄。輸出記錄：輸出通訊錄所有記錄。按姓名查找：通過(guò)鍵盤輸入姓名，輸出該同學(xué)的所有信息。保存記錄：把通訊錄中所有的記錄保存到文獻(xiàn)中。清空記錄：刪除通訊錄中的所有記錄，并刪除文獻(xiàn)。退出提醒：程序啟動(dòng)時(shí)應(yīng)判斷是否存在記錄文獻(xiàn)，假如存在，則讀取每條記錄到鏈表中。用戶選擇并完畢主菜單某功能后，除了退出程序，應(yīng)當(dāng)返回主菜單。添加一條記錄時(shí)，插入到鏈表的尾部。查找、刪除記錄時(shí)，假如該記錄不存在，則應(yīng)當(dāng)輸出不存在的提醒。添加記錄、刪除記錄時(shí)不需要寫文獻(xiàn)。保存記錄時(shí)，用覆蓋寫文獻(xiàn)的方法。（或者先刪除原文獻(xiàn)，再保存所有記錄信息）各個(gè)功能模塊寫成函數(shù)，由主函數(shù)調(diào)用。選做：主菜單增長(zhǎng)一個(gè)排序功能選項(xiàng)，可以按照學(xué)號(hào)從小到大進(jìn)行排序。排序方法可以用冒泡排序或者插入排序。實(shí)驗(yàn)5：鏈棧的基本操作一、實(shí)驗(yàn)?zāi)康?）熟悉棧的定義和棧的基本操作。2）掌握鏈?zhǔn)酱鎯?chǔ)棧的基本運(yùn)算。3）加深對(duì)棧數(shù)據(jù)結(jié)構(gòu)的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)2學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容必做內(nèi)容：鏈棧的基本操作編寫棧的基本操作函數(shù)棧類型的定義，數(shù)據(jù)域使用char型typedefcharElemType;typedefstructnode{ ElemTypedata; structnode*next;}LinkStack;2．初始化空棧：函數(shù)原型如下：voidInitLinkStack（LinkStack*&s）其中函數(shù)參數(shù)為L(zhǎng)inkStack*&類型，表達(dá)指向創(chuàng)建的空棧的指針，并且用引用方式傳入。3.判斷是否空棧：函數(shù)原型如下：intIsEmptyLinkStack（LinkStack*s）其中函數(shù)參數(shù)為棧指針；返回值為int型，1表達(dá)是空棧，0表達(dá)不是空棧。4.入棧：函數(shù)原型如下：voidPushLinkStack（LinkStack*&s,ElemTypex）其中函數(shù)參數(shù)s為棧指針，x為入棧的數(shù)據(jù)。5.出棧：函數(shù)原型如下：intPopLinkStack(LinkStack*&s,ElemType&x)其中函數(shù)參數(shù)s為棧指針，x為出棧的數(shù)據(jù)的引用；返回值為int型，1表達(dá)出棧成功，0表達(dá)出棧失敗。6．取棧頂元素：(棧保持不變)函數(shù)原型如下：intGetLinkStackTop(LinkStack*s,ElemType&x)其中函數(shù)參數(shù)s為棧指針，x存放棧頂元素值；返回值為int型，1表達(dá)成功，0表達(dá)失敗。編寫主函數(shù)調(diào)用上述函數(shù)實(shí)現(xiàn)下列操作。1．初始化空棧。2.鍵盤輸入字符，使得輸入的字符依次入棧（結(jié)束符號(hào)自定，例如回車鍵(值為10)或'#'）每插入一個(gè)元素，必須輸出當(dāng)時(shí)的棧頂元素(調(diào)用GetLinkStackTop函數(shù))。3．判斷鏈棧是否為空。輸出判斷結(jié)果。4．調(diào)用出棧函數(shù)，打印出棧元素的值；反復(fù)此環(huán)節(jié)，直至棧為空。5．判斷鏈棧是否為空。輸出判斷結(jié)果。6．釋放鏈棧。選做內(nèi)容（一）：判斷對(duì)稱字符串設(shè)計(jì)一個(gè)算法，調(diào)用棧的基本運(yùn)算，判斷一個(gè)字符串是否為對(duì)稱字符串。若是返回1；否則返回0。例如：“abcba”和“abba”都是對(duì)稱字符串。實(shí)驗(yàn)6：隊(duì)列的基本操作一、實(shí)驗(yàn)?zāi)康?）熟悉隊(duì)列的定義和隊(duì)列的基本操作。2）掌握順序循環(huán)隊(duì)列和鏈?zhǔn)酱鎯?chǔ)隊(duì)列的基本運(yùn)算。3）加深對(duì)隊(duì)列數(shù)據(jù)結(jié)構(gòu)的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)2學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容隊(duì)列的基本操作隊(duì)列的存儲(chǔ)結(jié)構(gòu)從順序循環(huán)隊(duì)列或者鏈隊(duì)任選一種。編寫一個(gè)程序，實(shí)現(xiàn)隊(duì)列的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序，完畢如下功能：初始化隊(duì)列q判斷q是否非空依次進(jìn)隊(duì)元素a，b，c出隊(duì)一個(gè)元素，輸出該元素輸出隊(duì)列q的元素個(gè)數(shù)依次進(jìn)隊(duì)列元素d，e，f輸出隊(duì)列q的元素個(gè)數(shù)輸出出隊(duì)序列釋放隊(duì)列實(shí)驗(yàn)7：棧和隊(duì)列綜合實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康模?）可以運(yùn)用棧和隊(duì)列的基本運(yùn)算進(jìn)行相關(guān)操作。（2）進(jìn)一步熟悉文獻(xiàn)的應(yīng)用（3）加深隊(duì)列和棧的數(shù)據(jù)結(jié)構(gòu)理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)4學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容以下兩個(gè)實(shí)驗(yàn)任選一個(gè)。迷宮求解設(shè)計(jì)一個(gè)迷宮求解程序，規(guī)定如下：以M×N表達(dá)長(zhǎng)方陣表達(dá)迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論。能任意設(shè)定的迷宮（選作）假如有通路，列出所有通路提醒：以一個(gè)二維數(shù)組來(lái)表達(dá)迷宮，0和1分別表達(dá)迷宮中的通路和障礙，如下圖迷宮數(shù)據(jù)為：入口位置：11出口位置：88探索過(guò)程可采用如下算法，設(shè)定當(dāng)前位置的初值為入口位置；do{ 若當(dāng)前位置可通， 則｛將當(dāng)前位置插入棧頂； 若該位置是出口位置，則結(jié)束； 否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；｝否則，｛ 若棧不空且棧頂位置尚有其他方向未經(jīng)探索， 則設(shè)定新的當(dāng)前位置為沿順時(shí)針?lè)较蛐D(zhuǎn)找到的棧頂位置的下一相鄰塊； 若棧不空但棧頂位置的四周均不可通， 則｛刪去棧頂位置；//從途徑中刪去該通道塊若棧不空，則重新測(cè)試新的棧頂位置， 直至找到一個(gè)可通的相鄰塊出棧至?？?； ｝｝｝while(棧不空)；2、機(jī)場(chǎng)飛機(jī)起降的過(guò)程模擬熟悉隊(duì)列的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序，完畢如下功能：模擬一個(gè)機(jī)場(chǎng)飛機(jī)起降的過(guò)程機(jī)場(chǎng)僅有一條跑道，規(guī)定起飛與降落不能同時(shí)進(jìn)行進(jìn)場(chǎng)飛機(jī)若暫時(shí)沒(méi)有跑道可用須在空中盤旋等候離場(chǎng)飛機(jī)若暫時(shí)沒(méi)有跑道可用須在地面排隊(duì)等候僅當(dāng)空中無(wú)飛機(jī)等待降落時(shí)地面飛機(jī)方可起飛飛機(jī)的申請(qǐng)進(jìn)場(chǎng)、降落、申請(qǐng)離場(chǎng)和起飛分別視為獨(dú)立事件每個(gè)事件的發(fā)生占用一個(gè)時(shí)間單位。除降落和起飛外，各事件可以同時(shí)發(fā)生提醒：設(shè)定一個(gè)待飛隊(duì)列用于存放排隊(duì)等候的航班信息設(shè)定一個(gè)待降落隊(duì)列用于存放等待降落的航班信息飛機(jī)的申請(qǐng)進(jìn)場(chǎng)、降落、申請(qǐng)離場(chǎng)和起飛可以通過(guò)航班事先設(shè)定的起飛時(shí)間、飛行時(shí)間長(zhǎng)度或者降落時(shí)間信息來(lái)擬定，這些信息可以存放在一個(gè)文獻(xiàn)中，程序運(yùn)營(yíng)時(shí)從文獻(xiàn)中讀出。航班當(dāng)前狀態(tài)可表達(dá)為：起飛，降落，申請(qǐng)進(jìn)場(chǎng)，申請(qǐng)離場(chǎng)，空閑每個(gè)事件的發(fā)生占用一個(gè)時(shí)間單位可以自己約定，起飛，降落可以設(shè)定為30分鐘實(shí)驗(yàn)8：順序串的基本操作一、實(shí)驗(yàn)?zāi)康?）熟悉串的定義和串的基本操作。2）掌握順序串的基本運(yùn)算。3）加深對(duì)串?dāng)?shù)據(jù)結(jié)構(gòu)的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)2學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容編寫一個(gè)程序，實(shí)現(xiàn)順序串的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序。具體如下：編寫棧的基本操作函數(shù)順序串類型定義如下所示：typedefstruct{charch[MAXSIZE];intlen;}SeqString;（1）串賦值A(chǔ)ssign(s,t)將一個(gè)字符串常量賦給串s,即生成一個(gè)其值等于t的串s（2）串復(fù)制StrCopy(s,t)將串t賦給串s（3）計(jì)算串長(zhǎng)度StrLength(s)返回串s中字符個(gè)數(shù)（4）判斷串相等StrEqual(s,t)若兩個(gè)串s與t相等則返回1；否則返回0。（5）串連接Concat(s,t)返回由兩個(gè)串s和t連接在一起形成的新串。（6）求子串SubStr(s,i,j)返回串s中從第i(1≤i≤StrLength(s))個(gè)字符開始的、由連續(xù)j個(gè)字符組成的子串。（7）插入InsStr(s,i,t)將串t插入到串s的第i(1≤i≤StrLength(s)+1)個(gè)字符中,即將t的第一個(gè)字符作為s的第i個(gè)字符,并返回產(chǎn)生的新串（8）串刪除DelStr(s,i,j)從串s中刪去從第i(1≤i≤StrLength(s))個(gè)字符開始的長(zhǎng)度為j的子串,并返回產(chǎn)生的新串。（9）串替換RepStr(s,s1,s2)在串s中,將所有出現(xiàn)的子串s1均替換成s2。（10）輸出串DispStr(s)輸出串s的所有元素值（11）判斷串是否為空IsEmpty(s)編寫主函數(shù)調(diào)用上述函數(shù)實(shí)現(xiàn)下列操作：建立串s=“abcdefghijklmn”，串s1=“xyz”，串t＝“hijk”復(fù)制串t到t1，并輸出t1的長(zhǎng)度在串s的第9個(gè)字符位置插入串s1而產(chǎn)生串s2，并輸出s2刪除s第2個(gè)字符開始的5個(gè)字符而產(chǎn)生串s3，并輸出s3將串s第2個(gè)字符開始的3個(gè)字符替換成串s1而產(chǎn)生串s4，并輸出s4提取串s的第8個(gè)字符開始的4個(gè)字符而產(chǎn)生串s5，并輸出s5將串s1和串t連接起來(lái)而產(chǎn)生串s6，并輸出s6比較串s1和s5是否相等，輸出結(jié)果實(shí)驗(yàn)9：矩陣的基本操作一、實(shí)驗(yàn)?zāi)康?）熟悉數(shù)組、矩陣的定義和基本操作。2）掌握對(duì)稱矩陣、稀疏矩陣等特殊矩陣的存儲(chǔ)方式和基本運(yùn)算。3）加深對(duì)數(shù)組、矩陣的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)2學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容以下兩個(gè)實(shí)驗(yàn)任選一個(gè)。1、實(shí)現(xiàn)稀疏矩陣的轉(zhuǎn)置、求和假設(shè)m×n的稀疏矩陣用三元組表達(dá)，編寫一個(gè)程序?qū)崿F(xiàn)如下功能：生成如下兩個(gè)稀疏矩陣的三元組a和b，并輸出三元組表達(dá)。103010300100001000103000040000100002提醒：程序中可以用intA[4][4]和B[4][4]二維數(shù)組表達(dá)原始矩陣A和B。輸出a的轉(zhuǎn)置矩陣的三元組表達(dá)。設(shè)c＝a＋b，輸出c的三元組表達(dá)。2、求對(duì)稱矩陣之和、乘積已知A和B為兩個(gè)n×n階的對(duì)稱矩陣，編寫一個(gè)程序?qū)崿F(xiàn)：將其下三角元素存儲(chǔ)在一維數(shù)組a和b中，并輸出。112411241235234645671111111111111111提醒：程序中可以用intA[4][4]和B[4][4]二維數(shù)組表達(dá)原始矩陣A和B。設(shè)C＝A＋B，以矩陣方式輸出C。設(shè)D＝A×B，以矩陣方式輸出D。實(shí)驗(yàn)10：字符串綜合實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康?）熟悉串的定義和串的基本操作。2）加深對(duì)串?dāng)?shù)據(jù)結(jié)構(gòu)的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)4學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容以下兩個(gè)實(shí)驗(yàn)任選一個(gè)。1、凱撒加密算法凱撒密碼（caeser）是羅馬擴(kuò)張時(shí)期朱利斯?凱撒（JuliusCaesar）發(fā)明的，用于加密通過(guò)信使傳遞的作戰(zhàn)命令。它將字母表中的字母移動(dòng)一定位置而實(shí)現(xiàn)加密。他的原理很簡(jiǎn)樸，說(shuō)到底就是字母與字母之間的替換。每一個(gè)字母按字母表順序向后移3位，如a加密后變成d，b加密后變成e，······x加密后變成a，y加密后變成b，z加密后變成c。例如：“baidu”用凱撒密碼法加密后字符串變?yōu)椤癳dlgx”。試寫一個(gè)算法，將鍵盤輸入的文本字符串（只包含a～z的字符）進(jìn)行加密后輸出。另寫一個(gè)算法，將已加密后的字符串解密后輸出。提醒：假如有字符變量c加密后則＝’a’＋（c-‘a(chǎn)’＋3）％26采用順序結(jié)構(gòu)存儲(chǔ)串，鍵盤輸入字符串后保存到順序串中；輸出用順序串的輸出函數(shù)。2、求一個(gè)串中出現(xiàn)的第一個(gè)最長(zhǎng)反復(fù)子串 采用順序結(jié)構(gòu)存儲(chǔ)串，編寫一個(gè)程序，求串s中出現(xiàn)的第一個(gè)最長(zhǎng)反復(fù)子串的下標(biāo)和長(zhǎng)度。實(shí)驗(yàn)11：遞歸綜合實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康?）熟悉遞歸的定義和遞歸的算法設(shè)計(jì)。2）加深對(duì)遞歸算法的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)4學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容以下兩個(gè)實(shí)驗(yàn)任選一個(gè)。1、求解n皇后問(wèn)題編寫一個(gè)程序，求解皇后問(wèn)題：在n×n的方格棋盤上，放置n個(gè)皇后，規(guī)定每個(gè)皇后不同行、不同列、不同對(duì)角線。 規(guī)定：使用遞歸算法求解；皇后的個(gè)數(shù)n由用戶輸入，其值不能超過(guò)20。2、求解漢諾塔問(wèn)題 設(shè)有3個(gè)分別命名為X,Y和Z的塔座,在塔座X上有n個(gè)直徑各不相同,從小到大依次編號(hào)為1,2,…,n的盤片,現(xiàn)規(guī)定將X塔座上的n個(gè)盤片移到塔座Z上并仍按同樣順序疊放,盤片移動(dòng)時(shí)必須遵守以下規(guī)則：每次只能移動(dòng)一個(gè)盤片；盤片可以插在X,Y和Z中任一塔座；任何時(shí)候都不能將一個(gè)較大的盤片放在較小的盤片上。設(shè)計(jì)遞歸求解算法。規(guī)定：使用遞歸算法求解；盤片的個(gè)數(shù)n由用戶輸入，其值不能超過(guò)12。實(shí)驗(yàn)12：二叉樹的操作一、實(shí)驗(yàn)?zāi)康?）熟悉二叉樹樹的基本操作。2）掌握二叉樹的實(shí)現(xiàn)以及實(shí)際應(yīng)用。3）加深二叉樹的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)4學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容1、二叉樹的基本操作【問(wèn)題描述】 現(xiàn)需要編寫一套二叉樹的操作函數(shù)，以便用戶可以方便的運(yùn)用這些函數(shù)來(lái)實(shí)現(xiàn)自己的應(yīng)用。其中操作函數(shù)涉及：創(chuàng)建二叉樹CreateBTNode(*b,*str)：根據(jù)二叉樹括號(hào)表達(dá)法的字符串*str生成相應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。輸出二叉樹DispBTNode(*b)：以括號(hào)表達(dá)法輸出一棵二叉樹。查找結(jié)點(diǎn)FindNode(*b,x)：在二叉樹b中尋找data域值為x的結(jié)點(diǎn),并返回指向該結(jié)點(diǎn)的指針。求高度BTNodeDepth(*b)：求二叉樹b的高度。若二叉樹為空,則其高度為0；否則,其高度等于左子樹與右子樹中的最大高度加l。求二叉樹的結(jié)點(diǎn)個(gè)數(shù)NodesCount(BTNode*b) 先序遍歷的遞歸算法：voidPreOrder(BTNode*b) 中序遍歷的遞歸算法：voidInOrder(BTNode*b) 后序遍歷遞歸算法：voidPostOrder(BTNode*b)層次遍歷算法voidLevelOrder(BTNode*b)【基本規(guī)定】實(shí)現(xiàn)以上9個(gè)函數(shù)。主函數(shù)中實(shí)現(xiàn)以下功能：創(chuàng)建下圖中的樹b輸出二叉樹b找到’H’節(jié)點(diǎn)，輸出其左右孩子值輸出b的高度輸出b的節(jié)點(diǎn)個(gè)數(shù)輸出b的四種遍歷順序AABDCEHJKLMNFGI【實(shí)驗(yàn)提醒】數(shù)據(jù)結(jié)構(gòu)的定義：#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefcharElemType;typedefstructnode{ ElemTypedata; /*數(shù)據(jù)元素*/ structnode*lchild; /*指向左孩子*/ structnode*rchild; /*指向右孩子*/}BTNode;各個(gè)函數(shù)的定義：voidCreateBTNode(BTNode*&b,char*str);BTNode*FindNode(BTNode*b,ElemTypex);intBTNodeDepth(BTNode*b);voidDispBTNode(BTNode*b);intNodesCount(BTNode*b);voidPreOrder(BTNode*b);voidInOrder(BTNode*b);voidPostOrder(BTNode*b);voidTravLevel(BTNode*b);主函數(shù)的結(jié)構(gòu)：voidmain(){ BTNode*b,*p,*lp,*rp;; charstr[]="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,'H'); if(p!=NULL) { //此處輸出p的左右孩子節(jié)點(diǎn)的值 } printf("\n"); printf("二叉樹b的深度:%d\n",BTNodeDepth(b)); printf("二叉樹b的結(jié)點(diǎn)個(gè)數(shù):%d\n",NodesCount(b)); printf("\n"); printf("先序遍歷序列:\n"); printf("遞歸算法:");PreOrder(b);printf("\n"); printf("中序遍歷序列:\n"); printf("遞歸算法:");InOrder(b);printf("\n"); printf("后序遍歷序列:\n"); printf("遞歸算法:");PostOrder(b);printf("\n");printf("層次遍歷序列:");printf("\n"); TravLevel(b);printf("\n");}2.2二叉樹的線索化【問(wèn)題描述】編寫一個(gè)程序，實(shí)現(xiàn)中序線索化二叉樹，輸出線索中序序列?！净疽?guī)定】用上圖的二叉樹b來(lái)驗(yàn)證你的程序?！緦?shí)驗(yàn)提醒】數(shù)據(jù)結(jié)構(gòu)的定義：#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefcharElemType;typedefstructnode{ ElemTypedata; intltag,rtag;/*增長(zhǎng)的線索標(biāo)記*/ structnode*lchild; structnode*rchild;}TBTNode;TBTNode*pre;各個(gè)函數(shù)的定義：voidCreateTBTNode(TBTNode*&b,char*str)voidDispTBTNode(TBTNode*b)voidThread(TBTNode*&p)TBTNode*CreaThread(TBTNode*b)/*中序線索化二叉樹*/voidThInOrder(TBTNode*tb)主函數(shù)的結(jié)構(gòu)：voidmain(){ 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("線索中序序列:");ThInOrder(tb);printf("\n");}3．實(shí)驗(yàn)結(jié)果此處填寫程序運(yùn)營(yíng)結(jié)果。4．實(shí)驗(yàn)心得此處填寫你的實(shí)驗(yàn)心得體會(huì)。實(shí)驗(yàn)13：哈夫曼編碼一、實(shí)驗(yàn)?zāi)康?）熟悉哈夫曼樹的基本操作。2）掌握哈夫曼編碼的實(shí)現(xiàn)以及實(shí)際應(yīng)用。3）加深對(duì)哈夫曼樹、哈夫曼編碼的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)4學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容【問(wèn)題描述】 運(yùn)用哈夫曼編碼進(jìn)行通信可以大大提高信道運(yùn)用率，縮短信息傳輸時(shí)間，減少傳輸成本。但是，這規(guī)定發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)數(shù)據(jù)進(jìn)行編碼，在接受端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼編碼/譯碼系統(tǒng)?！净疽?guī)定】本系統(tǒng)應(yīng)實(shí)現(xiàn)以下功能：（功能1～3必做，4為選做，請(qǐng)課后自行完畢）初始化：字符集（字母a～z，空格）共27個(gè)字符，以及其權(quán)值。建立哈夫曼樹。并建立各個(gè)字符的哈夫曼編碼。打印字符集的哈夫曼編碼。編碼：從終端讀入字符串，實(shí)現(xiàn)該字符串的編碼。譯碼：實(shí)現(xiàn)剛才生成的哈夫曼編碼還原為字符串。（選做）【已知條件】 （1）字符集的權(quán)值如下表：【實(shí)驗(yàn)提醒】數(shù)據(jù)結(jié)構(gòu)的定義：#defineN50 /*葉子結(jié)點(diǎn)數(shù)*/#defineM2*N-1 /*樹中結(jié)點(diǎn)總數(shù)*/typedefstruct{ chardata; /*結(jié)點(diǎn)值*/ intweight; /*權(quán)重*/ intparent; /*雙親結(jié)點(diǎn)*/ intlchild; /*左孩子結(jié)點(diǎn)*/ intrchild; /*右孩子結(jié)點(diǎn)*/}HTNode;typedefstruct{ charcd[N]; /*存放哈夫曼碼*/ intstart;}HCode;各個(gè)函數(shù)的定義：voidCreateHT(HTNodeht[],intn) /*創(chuàng)建哈夫曼樹*/voidCreateHCode(HTNodeht[],HCodehcd[],intn) /*創(chuàng)建哈夫曼編碼*/voidDispHCode(HTNodeht[],HCodehcd[],intn) /*顯示各個(gè)字符的哈夫曼編碼*/voidEncode(char*s,HTNodeht[],HCodehcd[],intn)/*顯示字符串s的哈夫曼編碼*/主函數(shù)的結(jié)構(gòu)： charstr[]={'','a','b','c','d','e','f','g','h','i','j','k','l','m','n', 'o','p','q','r','s','t','u','v','w','x','y','z'};/*字符集*/ intfnum[]={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：圖的存儲(chǔ)和遍歷一、實(shí)驗(yàn)?zāi)康?）熟悉圖的基本操作。2）掌握?qǐng)D的存儲(chǔ)實(shí)現(xiàn)以及遍歷操作。3）加深對(duì)圖的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)2學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容【基本規(guī)定】1、用鄰接矩陣存儲(chǔ)方式，表達(dá)下面的圖，并輸出。2、由上面的鄰接矩陣產(chǎn)生鄰接表，并輸出。3、編程完畢從頂點(diǎn)0開始的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。【輸出結(jié)果】輸出結(jié)果例子如下：有向圖G的鄰接矩陣:有向圖G的鄰接矩陣:050700004000800009005006000500300010圖G的鄰接矩陣轉(zhuǎn)換成鄰接表:0:131:22:053:254:35:04從頂點(diǎn)0開始的DFS:012543從頂點(diǎn)0開始的BFS:013254【提醒】#include<stdio.h>#include<malloc.h>#define MAXV100 /*最大頂點(diǎn)個(gè)數(shù)*/#defineINF32767/*INF表達(dá)∞*/typedefintInfoType;/*以下定義鄰接矩陣類型*/typedefstruct{ intno; /*頂點(diǎn)編號(hào)*/ InfoTypeinfo; /*頂點(diǎn)其他信息*/}VertexType; /*頂點(diǎn)類型*/typedefstruct /*圖的定義*/{ intedges[MAXV][MAXV]; /*鄰接矩陣*/ intvexnum,arcnum; /*頂點(diǎn)數(shù)，弧數(shù)*/ VertexTypevexs[MAXV]; /*存放頂點(diǎn)信息*/}MGraph; /*圖的鄰接矩陣類型*//*以下定義鄰接表類型*/typedefstructANode /*弧的結(jié)點(diǎn)結(jié)構(gòu)類型*/{ intadjvex; /*該弧的終點(diǎn)位置*/ structANode*nextarc; /*指向下一條弧的指針*/ InfoTypeinfo; /*該弧的相關(guān)信息,這里用于存放權(quán)值*/}ArcNode;typedefintVertex;typedefstructVnode /*鄰接表頭結(jié)點(diǎn)的類型*/{ Vertexdata; /*頂點(diǎn)信息*/ArcNode*firstarc; /*指向第一條弧*/}VNode;typedefVNodeAdjList[MAXV]; /*AdjList是鄰接表類型*/typedefstruct{ AdjListadjlist; /*鄰接表*/intn,e; /*圖中頂點(diǎn)數(shù)n和邊數(shù)e*/}ALGraph; /*圖的鄰接表類型*/intvisited[MAXV]; /*全局?jǐn)?shù)組*/voidMatToList(MGraph,ALGraph*&); /*鄰接矩陣轉(zhuǎn)為鄰接表*/voidDispMat(MGraph); /*輸出鄰接矩陣*/voidDispAdj(ALGraph*); /*輸出鄰接表*/voidDFS(ALGraph*G,intv); /*深度優(yōu)先遍歷*/voidBFS(ALGraph*G,intv); /*廣度優(yōu)先遍歷*/voidmain(){ inti,j; MGraphg; ALGraph*G; intA[MAXV][6]={ {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.edges[i][j]=A[i][j]; printf("\n"); 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");}voidMatToList(MGraphg,ALGraph*&G)/*將鄰接矩陣g轉(zhuǎn)換成鄰接表G*/{/*輸入代碼*/}voidDispMat(MGraphg)/*輸出鄰接矩陣g*/{/*輸入代碼*/}voidDispAdj(ALGraph*G)/*輸出鄰接表G*/{/*輸入代碼*/}voidDFS(ALGraph*G,intv){/*輸入代碼*/}voidBFS(ALGraph*G,intv){/*輸入代碼*/}實(shí)驗(yàn)15：Prim算法求最小生成樹一、實(shí)驗(yàn)?zāi)康?）熟悉圖的基本操作。2）掌握運(yùn)用Prim算法求圖的最小生成樹。3）加深對(duì)圖的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)2學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容【基本規(guī)定】編寫一個(gè)程序，對(duì)于如下的無(wú)向帶權(quán)圖，運(yùn)用Prim算法輸出從頂點(diǎn)0出發(fā)的最小生成樹。實(shí)驗(yàn)16：圖綜合實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康?）熟悉圖的基本操作。2）掌握求圖的最短途徑算法。3）加深對(duì)圖的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)4學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容【基本規(guī)定】給定n個(gè)村莊之間的交通圖。若村莊i和j之間有路可通，則i和j用邊連接，邊上的權(quán)值Wij表達(dá)這條道路的長(zhǎng)度?，F(xiàn)打算在這n個(gè)村莊中選定一個(gè)村莊建一所醫(yī)院。編寫如下算法：求出該醫(yī)院應(yīng)建在哪個(gè)村莊，才干使距離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路程最短。求出該醫(yī)院應(yīng)建在哪個(gè)村莊，能使其它所有村莊到醫(yī)院的途徑總和最短?！咎嵝选繉?duì)于問(wèn)題（1），可以先求出每個(gè)村莊到其它所有村莊的最短途徑，保存其最大值（表達(dá)假設(shè)醫(yī)院建在該村莊，距離醫(yī)院最遠(yuǎn)的村莊的途徑長(zhǎng)度）；然后在這些最大值中找出一個(gè)最小值。對(duì)于問(wèn)題（2），可以先求出每個(gè)村莊到其它所有村莊的最短途徑，保存其累加和（表達(dá)假設(shè)醫(yī)院建在該村莊，其它所有村莊距離醫(yī)院的途徑總和）；然后在這些和中找出一個(gè)最小值。自己設(shè)定n個(gè)村莊的交通圖。例如下圖所示：實(shí)驗(yàn)17：線性查找一、實(shí)驗(yàn)?zāi)康?）熟悉查找的基本操作。2）掌握線性查找（順序查找、二分查找）的實(shí)現(xiàn)。3）加深對(duì)查找的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)2學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容1、順序查找編寫一個(gè)程序，輸出在順序表中{3，6，2，10，1，8，5，7，4，9}中采用順序查找的方法查找關(guān)鍵字5的過(guò)程。2、二分查找【基本規(guī)定】編寫一個(gè)程序，輸出在順序表中{1，2，3，4，5，6，7，8，9，10}中采用二分查找法查找關(guān)鍵字9的過(guò)程?！据敵鼋Y(jié)果】輸出結(jié)果例子如下：第1次查找:在[0,9]中查找到元素R[4]:5第1次查找:在[0,9]中查找到元素R[4]:5第2次查找:在[5,9]中查找到元素R[7]:8第3次查找:在[8,9]中查找到元素R[8]:9元素9的位置是8實(shí)驗(yàn)18：哈希查找一、實(shí)驗(yàn)?zāi)康?）熟悉查找的基本操作。2）掌握哈希查找的實(shí)現(xiàn)。3）加深對(duì)查找的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)2學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容【基本規(guī)定】編寫一個(gè)程序，實(shí)現(xiàn)哈希表的相關(guān)運(yùn)算，并在此基礎(chǔ)上完畢如下功能：建立{16,74,60,43,54,90,46,31,29,88,77}哈希表A[0..12]，哈希函數(shù)為H(k)=key%p，（p取13），并采用線性探查法解決沖突。在上述哈希表中查找關(guān)鍵字為29的記錄。在上述哈希表中刪除關(guān)鍵字為77的記錄，再將其插入。【輸出結(jié)果】輸出結(jié)果例子如下：哈希表地址:0123456789101112哈希表地址:0123456789101112哈希表關(guān)鍵字:7754164331294660748890搜索次數(shù):21111411111平均搜索長(zhǎng)度ASL(11)=1.36364ha[6].key=29刪除關(guān)鍵字77哈希表地址:0123456789101112哈希表關(guān)鍵字:54164331294660748890搜索次數(shù):1111411111平均搜索長(zhǎng)度ASL(10)=1.3未找到77插入關(guān)鍵字77哈希表地址:0123456789101112哈希表關(guān)鍵字:7754164331294660748890搜索次數(shù):21111411111平均搜索長(zhǎng)度ASL(11)=1.36364實(shí)驗(yàn)19：查找綜合實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康?）熟悉查找的基本操作。2）掌握二叉排序樹的基本運(yùn)算。3）加深對(duì)查找的理解，逐步培養(yǎng)解決實(shí)際問(wèn)題的編程能力。二、實(shí)驗(yàn)環(huán)境裝有VisualC＋＋6.0的計(jì)算機(jī)。本次實(shí)驗(yàn)共計(jì)4學(xué)時(shí)。三、實(shí)驗(yàn)內(nèi)容1、記錄字符串中字符出現(xiàn)的次數(shù)編寫一個(gè)程序，由鍵盤輸入一個(gè)字符串，記錄該字符串中出現(xiàn)的字符及另一方面數(shù)。然后輸出結(jié)果。規(guī)定用一個(gè)二叉樹來(lái)保存解決結(jié)果，字符串中每個(gè)不同的字符用樹的結(jié)點(diǎn)表達(dá)，結(jié)點(diǎn)應(yīng)當(dāng)包含四個(gè)域：該字符、該字符出現(xiàn)的次數(shù)、左子樹指針、右子樹指針；其中左子樹的字符的ASCII碼均小于該字符，右子樹的字符的ASCII碼均大于該字符。提醒：從字符串中依次讀取字符，在二叉樹中查找該字符是否存在。假如存在，則該字符的出現(xiàn)次數(shù)加1；假如不存在，則按照二叉排序樹的規(guī)定插入該字符結(jié)點(diǎn)，同時(shí)設(shè)立出現(xiàn)次數(shù)為1。所有字符讀完以后，調(diào)用二叉樹的中序遍歷，有序的輸出每個(gè)字符及其出現(xiàn)的次數(shù)。2、二叉排序樹【基本規(guī)定】編寫一個(gè)程序，實(shí)現(xiàn)二叉排序樹的基本運(yùn)算，并在此基礎(chǔ)上完畢如下功能：由{4，9，0，1，8，6，3，5，2，7}創(chuàng)建一棵二叉排序樹bt，并以括號(hào)表達(dá)法輸出。判斷bt是否為一棵二叉排序樹。采用遞歸和非遞歸兩種方法查找關(guān)鍵字為6的結(jié)點(diǎn)，并