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

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

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

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

5、算法分析的計(jì)算過(guò)程。）4. 實(shí)驗(yàn)過(guò)程描述： （列出實(shí)驗(yàn)所用的測(cè)試用例和相應(yīng)的程序運(yùn)行結(jié)果(需要程序運(yùn)行結(jié)果的屏幕截圖)，總結(jié)本次實(shí)驗(yàn)，包括對(duì)測(cè)試結(jié)果的分析，測(cè)試和調(diào)試過(guò)程遇到問(wèn)題的回顧和分析，軟件設(shè)計(jì)與實(shí)現(xiàn)的經(jīng)驗(yàn)和體會(huì)，進(jìn)一步改進(jìn)的設(shè)想。）實(shí)驗(yàn)1 線性表及多項(xiàng)式的運(yùn)算一、實(shí)驗(yàn)?zāi)康?、掌握線性表的兩種基本存儲(chǔ)結(jié)構(gòu)及其應(yīng)用場(chǎng)合：順序存儲(chǔ)和鏈接存儲(chǔ)。2、掌握順序表和鏈表的各種基本操作算法。3、理解線性表應(yīng)用于多項(xiàng)式的實(shí)現(xiàn)算法。二、實(shí)驗(yàn)內(nèi)容1、參照程序2.12.7，編寫(xiě)程序，完成順序表的初始化、查找、插入、刪除、輸出、撤銷(xiāo)等操作。2、已知帶表頭結(jié)點(diǎn)單鏈表的類(lèi)型定義如下：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，編寫(xiě)程序，完成帶表頭結(jié)點(diǎn)單鏈表的初始化、查找、插入、刪除、輸出、撤銷(xiāo)等操作。3、以題2所示帶表頭結(jié)點(diǎn)單鏈表為存儲(chǔ)結(jié)構(gòu)，編寫(xiě)程序?qū)崿F(xiàn)單鏈表的逆置操作。（原單鏈表為（a0，a1，an-1），逆置后為（an-1，an-2， ，a0），要求不引入新的存儲(chǔ)空間） 。4、以題2所示帶表頭結(jié)點(diǎn)單鏈表為存儲(chǔ)結(jié)構(gòu)，編寫(xiě)程序?qū)崿F(xiàn)將單鏈表排序成為有序單鏈表的操作。5、已知帶表

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

8、知二叉樹(shù)二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)定義如下：typedef struct BinaryTreeNode T Data； struct BinaryTreeNode * LChild，* RChild； BinaryTreeNode，* BinTree；參照程序5.15.4，編寫(xiě)程序，完成二叉樹(shù)的先序創(chuàng)建、先序遍歷、中序遍歷、后序遍歷等操作。2、以題1所示二叉鏈表為存儲(chǔ)結(jié)構(gòu)，編寫(xiě)程序?qū)崿F(xiàn)求二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)、葉子結(jié)點(diǎn)個(gè)數(shù)、二叉樹(shù)的高度以及交換二叉樹(shù)所有左右子樹(shù)的操作。3、已知哈夫曼樹(shù)結(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; 編寫(xiě)程序，實(shí)現(xiàn)哈夫曼樹(shù)的創(chuàng)建、哈夫曼編碼以及解碼的實(shí)現(xiàn)。實(shí)驗(yàn)3 圖的基本運(yùn)算及飛機(jī)換乘次數(shù)最少問(wèn)題該部分題目描述已經(jīng)修改，請(qǐng)根據(jù)前述題目描述修改本部分內(nèi)容！一、實(shí)驗(yàn)?zāi)康?、掌握?qǐng)D的鄰接矩陣和鄰接表的存儲(chǔ)實(shí)現(xiàn)方法。2、實(shí)現(xiàn)圖的深度優(yōu)先和寬度優(yōu)先遍歷運(yùn)算。3、學(xué)習(xí)使用圖算法解決應(yīng)用問(wèn)題的方法。二、實(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)間無(wú)邊時(shí)的值 mGraph;參照程序9.19.5，編寫(xiě)程序，完成鄰接矩陣的初始化、撤銷(xiāo)、邊的搜索、插入、刪除等操作。2、以題1所示鄰接矩陣為存儲(chǔ)結(jié)構(gòu)，編寫(xiě)程序，實(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; /指向下一個(gè)邊結(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，編寫(xiě)程序，完成鄰接表的初始化、撤銷(xiāo)、邊的搜索、插入、刪除等操作。4、以題3所示鄰接表為存儲(chǔ)結(jié)構(gòu)，編寫(xiě)程序，實(shí)現(xiàn)圖的深度、寬度優(yōu)先遍歷。5、編寫(xiě)程序，實(shí)現(xiàn)飛機(jī)最少換乘次數(shù)問(wèn)題：設(shè)有n個(gè)城市，編號(hào)為0n-1，m條航線的起點(diǎn)和終點(diǎn)由用戶(hù)輸入提供。 一條換乘次數(shù)最少的線路方案。（提示：可以使用有向圖表示城市間的航線；只要兩個(gè)城市間有航班，則圖中這兩點(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é)會(huì)分析各種內(nèi)排序算法的時(shí)間復(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)該為可比較類(lèi)型DataType data;/data包含數(shù)據(jù)元素中的其他數(shù)據(jù)項(xiàng);typedef struct list/順序表int n;/待排序數(shù)據(jù)元素?cái)?shù)量EntryDMaxSize;/靜態(tài)數(shù)組存儲(chǔ)數(shù)據(jù)元素List;參照程序10.110.7，編寫(xiě)算法，分別實(shí)現(xiàn)順序表的簡(jiǎn)單選擇排序、直接插入排序、冒泡排序、快速排序、兩路合并排序以