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

1、實(shí)驗(yàn)指導(dǎo)-數(shù)據(jù)結(jié)構(gòu) B精品文檔附錄綜合實(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)告。收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔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)式的加法和乘

3、法運(yùn)算操作。2、二叉樹(shù)的基本操作及哈夫曼編碼譯碼系統(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à)由用戶輸入提供，尋找最佳路徑方案（例如花費(fèi)時(shí)間最少、路徑長(zhǎng)度最短、交通費(fèi)用最小等，

4、任選其一即可）。要求：設(shè)計(jì)主函數(shù)，測(cè)試上述運(yùn)算。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)行比較。收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(liá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ù)傳遞方式

5、，給出核心算法的C 源代碼，并加上詳細(xì)注釋?zhuān)治鲋饕惴ǖ臅r(shí)間復(fù)雜度，必要時(shí)分析空間復(fù)雜度，給出算法分析的計(jì)算過(guò)程。）4. 實(shí)驗(yàn)過(guò)程描述：收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔（ 列出實(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è)想。）收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔實(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)式

6、的實(shí)現(xiàn)算法。二、實(shí)驗(yàn)內(nèi)容1、參照程序 2.12.7，編寫(xiě)程序，完成順序表的初始化、查找、插入、刪除、輸出、撤銷(xiāo)等操作。2、已知帶表頭結(jié)點(diǎn)單鏈表的類(lèi)型定義如下：typedef struct nodeElemType element; /結(jié)點(diǎn)的數(shù)據(jù)域struct node *link;/ 結(jié)點(diǎn)的指針域node;typedef structstruct 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)單鏈表的逆置操作。（原單鏈表為（

7、 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、已知帶表頭結(jié)點(diǎn)一元多項(xiàng)式的類(lèi)型定義如下：typedef struct pNode收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔int coef;int exp;struct pNode* link; pNode; typedef structstruct pNode *head; polynominal;編寫(xiě)程序?qū)崿F(xiàn)一元多項(xiàng)式的創(chuàng)建、輸出、撤銷(xiāo)以及兩個(gè)一元多項(xiàng)式相加和相乘的操作。收集于網(wǎng)絡(luò)，如

8、有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔實(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、已知二叉樹(shù)二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)定義如下：typedef struct BinaryTreeNodeT Data；struct BinaryTreeNode * LChild ， * RChild； BinaryTreeNode， * BinTree；參照程序 5.15.4，編寫(xiě)程序，完成二叉樹(shù)的先序

9、創(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, lchild, rchild;/結(jié)點(diǎn)的雙親、左孩子、右孩子HFMTNode;編寫(xiě)程序，實(shí)現(xiàn)哈夫曼樹(shù)的創(chuàng)建、哈夫曼編碼以及解碼的實(shí)現(xiàn)。收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔實(shí)驗(yàn) 3 圖的基本運(yùn)算及飛機(jī)換乘次數(shù)最少問(wèn)題一、實(shí)驗(yàn)?zāi)康?、掌握?qǐng)D的鄰接矩陣和鄰接表的存儲(chǔ)實(shí)現(xiàn)方法。2、實(shí)

10、現(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 structElemType *a;/鄰接矩陣int n;/圖的當(dāng)前頂點(diǎn)數(shù)int e;/圖的當(dāng)前邊數(shù)ElemType 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 eNodeint adjVe

11、x;/任意頂點(diǎn) u 相鄰接的頂點(diǎn)ElemType w;/邊的權(quán)值struct eNode* nextArc;/指向下一個(gè)邊結(jié)點(diǎn)收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔eNode;typedef structint n;/圖的當(dāng)前頂點(diǎn)數(shù)int e;/圖的當(dāng)前邊數(shù)eNode *a;/指向一維指針數(shù)組lGraph;參照程序 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)由用戶輸入提供。一條換乘次

12、數(shù)最少的線路方案。（提示：可以使用有向圖表示城市間的航線；只要兩個(gè)城市間有航班，則圖中這兩點(diǎn)間存在一條權(quán)為 1 的邊；可以使用 Dijkstra 算法實(shí)現(xiàn)）收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(liá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.1 10.7，編寫(xiě)算法，分別實(shí)現(xiàn)順序表的簡(jiǎn)單選擇排序、直接插入排序、冒泡排序、快速排序、兩路合并排序以及堆排序。2、編寫(xiě)