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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上附錄 綜合實(shí)驗(yàn)1、實(shí)驗(yàn)?zāi)康谋菊n程的目標(biāo)之一是使得學(xué)生學(xué)會如何從問題出發(fā)，分析數(shù)據(jù)，構(gòu)造求解問題的數(shù)據(jù)結(jié)構(gòu)和算法，培養(yǎng)學(xué)生進(jìn)行較復(fù)雜程序設(shè)計的能力。本課程實(shí)踐性較強(qiáng)，為實(shí)現(xiàn)課程目標(biāo)，要求學(xué)生完成一定數(shù)量的上機(jī)實(shí)驗(yàn)。從而一方面使得學(xué)生加深對課內(nèi)所學(xué)的各種數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲表示和運(yùn)算的方法等基本內(nèi)容的理解，學(xué)習(xí)如何運(yùn)用所學(xué)的數(shù)據(jù)結(jié)構(gòu)和算法知識解決應(yīng)用問題的方法；另一方面，在程序設(shè)計方法、C語言編程環(huán)境以及程序的調(diào)試和測試等方面得到必要的訓(xùn)練。2、實(shí)驗(yàn)基本要求：1）學(xué)習(xí)使用自頂向下的分析方法，分析問題空間中存在哪些模塊，明確這些模塊之間的關(guān)系。2）使用結(jié)構(gòu)化的系統(tǒng)設(shè)計方法，

2、將系統(tǒng)中存在的各個模塊合理組織成層次結(jié)構(gòu)，并明確定義各個結(jié)構(gòu)體。確定模塊的主要數(shù)據(jù)結(jié)構(gòu)和接口。3）熟練使用C語言環(huán)境來實(shí)現(xiàn)或重用模塊，從而實(shí)現(xiàn)系統(tǒng)的層次結(jié)構(gòu)。模塊的實(shí)現(xiàn)包括結(jié)構(gòu)體的定義和函數(shù)的實(shí)現(xiàn)。4）學(xué)會利用數(shù)據(jù)結(jié)構(gòu)所學(xué)知識設(shè)計結(jié)構(gòu)清晰的算法和程序，并會分析所設(shè)計的算法的時間和空間復(fù)雜度。5）所有的算法和實(shí)現(xiàn)均使用C語言進(jìn)行描述，實(shí)驗(yàn)結(jié)束寫出實(shí)驗(yàn)報告。3、實(shí)驗(yàn)項目與內(nèi)容：1、線性表的基本運(yùn)算及多項式的算術(shù)運(yùn)算 內(nèi)容：實(shí)現(xiàn)順序表和單鏈表的基本運(yùn)算，多項式的加法和乘法算術(shù)運(yùn)算。 要求：能夠正確演示線性表的查找、插入、刪除運(yùn)算。實(shí)現(xiàn)多項式的加法和乘法運(yùn)算操作。2、二叉樹的基本操作及哈夫曼編碼譯碼系

3、統(tǒng)的實(shí)現(xiàn) 內(nèi)容：創(chuàng)建一棵二叉樹，實(shí)現(xiàn)先序、中序和后序遍歷一棵二叉樹，計算二叉樹結(jié)點(diǎn)個數(shù)等操作。哈夫曼編碼/譯碼系統(tǒng)。 要求：能成功演示二叉樹的有關(guān)運(yùn)算，實(shí)現(xiàn)哈夫曼編碼/譯碼的功能，運(yùn)算完畢后能成功釋放二叉樹所有結(jié)點(diǎn)占用的系統(tǒng)內(nèi)存。3、圖的基本運(yùn)算及智能交通中的最佳路徑選擇問題 內(nèi)容：在鄰接矩陣和鄰接表兩種不同存儲結(jié)構(gòu)上實(shí)現(xiàn)圖的基本運(yùn)算的算法，實(shí)現(xiàn)圖的深度和寬度優(yōu)先遍歷算法，解決智能交通中的路徑選擇問題。設(shè)有n個地點(diǎn)，編號為0n-1，m條路徑的起點(diǎn)、終點(diǎn)和代價由用戶輸入提供，尋找最佳路徑方案（例如花費(fèi)時間最少、路徑長度最短、交通費(fèi)用最小等，任選其一即可）。 要求：設(shè)計主函數(shù)，測試上述運(yùn)算。4、各

4、種內(nèi)排序算法的實(shí)現(xiàn)及性能比較 內(nèi)容：驗(yàn)證教材的各種內(nèi)排序算法。分析各種排序算法的時間復(fù)雜度。 要求：使用隨機(jī)數(shù)產(chǎn)生器產(chǎn)生較大規(guī)模數(shù)據(jù)集合，運(yùn)行上述各種排序算法，使用系統(tǒng)時鐘測量各算法所需的實(shí)際時間，并進(jìn)行比較。4、實(shí)驗(yàn)報告范例：實(shí)驗(yàn) 班級_姓名_學(xué)號_日期_1. 實(shí)驗(yàn)?zāi)康模?（扼要而準(zhǔn)確地描述所求解的實(shí)驗(yàn)項目的目的。）2. 實(shí)驗(yàn)任務(wù)： （明確實(shí)驗(yàn)項目的任務(wù)和演示程序的主要功能。）3. 實(shí)驗(yàn)內(nèi)容： （使用模塊和流程圖表示系統(tǒng)分析和設(shè)計的結(jié)果，描述各模塊之間的層次結(jié)構(gòu)，給出函數(shù)之間的調(diào)用關(guān)系和數(shù)據(jù)傳遞方式，給出核心算法的C源代碼，并加上詳細(xì)注釋，分析主要算法的時間復(fù)雜度，必要時分析空間復(fù)雜度，給出

5、算法分析的計算過程。）4. 實(shí)驗(yàn)過程描述： （列出實(shí)驗(yàn)所用的測試用例和相應(yīng)的程序運(yùn)行結(jié)果(需要程序運(yùn)行結(jié)果的屏幕截圖)，總結(jié)本次實(shí)驗(yàn)，包括對測試結(jié)果的分析，測試和調(diào)試過程遇到問題的回顧和分析，軟件設(shè)計與實(shí)現(xiàn)的經(jīng)驗(yàn)和體會，進(jìn)一步改進(jìn)的設(shè)想。）實(shí)驗(yàn)1 線性表及多項式的運(yùn)算一、實(shí)驗(yàn)?zāi)康?、掌握線性表的兩種基本存儲結(jié)構(gòu)及其應(yīng)用場合：順序存儲和鏈接存儲。2、掌握順序表和鏈表的各種基本操作算法。3、理解線性表應(yīng)用于多項式的實(shí)現(xiàn)算法。二、實(shí)驗(yàn)內(nèi)容1、參照程序2.12.7，編寫程序，完成順序表的初始化、查找、插入、刪除、輸出、撤銷等操作。2、已知帶表頭結(jié)點(diǎn)單鏈表的類型定義如下：typedef struct n

6、odeElemType element; /結(jié)點(diǎn)的數(shù)據(jù)域struct node *link; /結(jié)點(diǎn)的指針域node;typedef struct struct node * head;int n;headerList;參照程序2.82.14，編寫程序，完成帶表頭結(jié)點(diǎn)單鏈表的初始化、查找、插入、刪除、輸出、撤銷等操作。3、以題2所示帶表頭結(jié)點(diǎn)單鏈表為存儲結(jié)構(gòu)，編寫程序?qū)崿F(xiàn)單鏈表的逆置操作。（原單鏈表為（a0，a1，an-1），逆置后為（an-1，an-2， ，a0），要求不引入新的存儲空間） 。4、以題2所示帶表頭結(jié)點(diǎn)單鏈表為存儲結(jié)構(gòu)，編寫程序?qū)崿F(xiàn)將單鏈表排序成為有序單鏈表的操作。5、已知帶表

7、頭結(jié)點(diǎn)一元多項式的類型定義如下：typedef struct pNodeint coef;int exp;struct pNode* link; pNode;typedef struct struct pNode *head; polynominal;編寫程序?qū)崿F(xiàn)一元多項式的創(chuàng)建、輸出、撤銷以及兩個一元多項式相加和相乘的操作。實(shí)驗(yàn)2 二叉樹的基本操作及哈夫曼編碼譯碼系統(tǒng)的實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康?、掌握二叉樹的二叉鏈表存儲表示及遍歷操作實(shí)現(xiàn)方法。2、實(shí)現(xiàn)二叉樹遍歷運(yùn)算的應(yīng)用：求二叉樹中葉子結(jié)點(diǎn)個數(shù)、結(jié)點(diǎn)總數(shù)、二叉樹的高度、交換二叉樹的左右子樹等。3、掌握二叉樹的應(yīng)用哈夫曼編碼的實(shí)現(xiàn)。二、實(shí)驗(yàn)內(nèi)容1、已

8、知二叉樹二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)定義如下：typedef struct BinaryTreeNode T Data； struct BinaryTreeNode * LChild，* RChild； BinaryTreeNode，* BinTree；參照程序5.15.4，編寫程序，完成二叉樹的先序創(chuàng)建、先序遍歷、中序遍歷、后序遍歷等操作。2、以題1所示二叉鏈表為存儲結(jié)構(gòu)，編寫程序?qū)崿F(xiàn)求二叉樹結(jié)點(diǎn)個數(shù)、葉子結(jié)點(diǎn)個數(shù)、二叉樹的高度以及交換二叉樹所有左右子樹的操作。3、已知哈夫曼樹結(jié)點(diǎn)結(jié)構(gòu)定義如下：typedefElementType Data; /結(jié)點(diǎn)的數(shù)據(jù)域int w; /結(jié)點(diǎn)的權(quán)值int parent

9、, lchild, rchild; /結(jié)點(diǎn)的雙親、左孩子、右孩子HFMTNode; 編寫程序，實(shí)現(xiàn)哈夫曼樹的創(chuàng)建、哈夫曼編碼以及解碼的實(shí)現(xiàn)。實(shí)驗(yàn)3 圖的基本運(yùn)算及飛機(jī)換乘次數(shù)最少問題該部分題目描述已經(jīng)修改，請根據(jù)前述題目描述修改本部分內(nèi)容！一、實(shí)驗(yàn)?zāi)康?、掌握圖的鄰接矩陣和鄰接表的存儲實(shí)現(xiàn)方法。2、實(shí)現(xiàn)圖的深度優(yōu)先和寬度優(yōu)先遍歷運(yùn)算。3、學(xué)習(xí)使用圖算法解決應(yīng)用問題的方法。二、實(shí)驗(yàn)內(nèi)容1、已知圖的鄰接矩陣結(jié)構(gòu)定義如下：typedef int ElemType; typedef struct ElemType *a; /鄰接矩陣int n; /圖的當(dāng)前頂點(diǎn)數(shù)int e; /圖的當(dāng)前邊數(shù) ElemT

10、ype noEdge; /兩頂點(diǎn)間無邊時的值 mGraph;參照程序9.19.5，編寫程序，完成鄰接矩陣的初始化、撤銷、邊的搜索、插入、刪除等操作。2、以題1所示鄰接矩陣為存儲結(jié)構(gòu)，編寫程序，實(shí)現(xiàn)圖的深度、寬度優(yōu)先遍歷。3、已知圖的鄰接表結(jié)構(gòu)定義如下：typedef struct eNode int adjVex; /任意頂點(diǎn)u相鄰接的頂點(diǎn) ElemType w; /邊的權(quán)值 struct eNode* nextArc; /指向下一個邊結(jié)點(diǎn)eNode;typedef struct int n; /圖的當(dāng)前頂點(diǎn)數(shù) int e; /圖的當(dāng)前邊數(shù) eNode *a; /指向一維指針數(shù)組lGraph;

11、參照程序9.69.10，編寫程序，完成鄰接表的初始化、撤銷、邊的搜索、插入、刪除等操作。4、以題3所示鄰接表為存儲結(jié)構(gòu)，編寫程序，實(shí)現(xiàn)圖的深度、寬度優(yōu)先遍歷。5、編寫程序，實(shí)現(xiàn)飛機(jī)最少換乘次數(shù)問題：設(shè)有n個城市，編號為0n-1，m條航線的起點(diǎn)和終點(diǎn)由用戶輸入提供。 一條換乘次數(shù)最少的線路方案。（提示：可以使用有向圖表示城市間的航線；只要兩個城市間有航班，則圖中這兩點(diǎn)間存在一條權(quán)為1的邊；可以使用Dijkstra算法實(shí)現(xiàn)）實(shí)驗(yàn)4 各種內(nèi)排序算法的實(shí)現(xiàn)及性能比較一、實(shí)驗(yàn)?zāi)康?、掌握各種內(nèi)排序算法的實(shí)現(xiàn)方法。2、學(xué)會分析各種內(nèi)排序算法的時間復(fù)雜度。二、實(shí)驗(yàn)內(nèi)容1、已知待排序序列以順序表結(jié)構(gòu)實(shí)現(xiàn)，數(shù)據(jù)元素以及表結(jié)構(gòu)定義如下：typedef struct entry /數(shù)據(jù)元素KeyType key;/排序關(guān)鍵字，KeyType應(yīng)該為可比較類型DataType data;/data包含數(shù)據(jù)元素中的其他數(shù)據(jù)項;typedef struct list/順序表int n;/待排序數(shù)據(jù)元素數(shù)量EntryDMaxSize;/靜態(tài)數(shù)組存儲數(shù)據(jù)元素List;參照程序10.110.7，編寫算法，分別實(shí)現(xiàn)順序表的簡單選擇排序、直接插入排序、冒泡排序、快速排序、兩路合并排序以