計算機類大學(xué)生小學(xué)期實驗1

1、算法與數(shù)據(jù)結(jié)構(gòu)綜合訓(xùn)練報 告第一部分：基本算法訓(xùn)練 組號： 02 組長： 溫佳美 成員： 安秀芳、施璇、 丁子葉、黃城 2015年 7 月 9 日一、任務(wù)說明 1。分工及時間安排。溫佳美（組長）：3、Prim算法 11、希爾排序 14、歸并排序 15、四則表達式計算組員：安秀芳： 6、Dijkstra算法 9、二叉排序樹生成算法（含平衡化） 12、快速排序 PPT主講人施璇：10、哈希表生成及哈希查找算法 13、堆排序 16、矩陣運算 以及PPT制作丁子葉：1、哈夫曼編碼算法 2、由遍歷序列恢復(fù)二叉樹 4、Kruskal算法 8、關(guān)鍵路徑算法黃城：5、Floyd 算法 7、拓?fù)渑判?17、有向

2、圖的強連通分量求解 2。任務(wù)描述2、 設(shè)計1。抽象數(shù)據(jù)類型安秀芳： 6、Dijkstra算法 ：圖 9、二叉排序樹生成算法（含平衡化） ：樹，鏈表 12、快速排序 ：順序表施璇：10、哈希表生成及哈希查找算法：哈希表 13、堆排序：順序表 16、矩陣運算 ：無丁子葉：1.哈夫曼編碼：樹 2.遍歷序列恢復(fù)二叉樹：二叉樹 4.Kruskal算法:圖 8.關(guān)鍵路徑算法：圖，鄰接表2。主程序流程及各程序模塊的層次關(guān)系 本次實驗綜合為一個main.cpp文件，將所有的程序整合在一個main.cpp文件中。增加菜單函數(shù)，顯示所有的算法題目及作者名字，選擇想要的功能，并用switch()語句選擇功能并調(diào)用相

3、應(yīng)的函數(shù)實現(xiàn)功能。最后在主函數(shù)里調(diào)用menu()函數(shù)，通過whlie循環(huán)選擇返回主菜單還是直接退出。小組不同程序之間的相同的數(shù)據(jù)結(jié)構(gòu)及算法共享。3、 調(diào)試分析3、Prim算法： a.構(gòu)造數(shù)據(jù)結(jié)構(gòu)-圖。 b.采用鄰接矩陣法創(chuàng)建無向圖。 c.Prim算法“加點法”，求最小生成樹。算法實現(xiàn)需要一個輔助數(shù)組closedge，以記錄最小邊在U中的那個頂點，以及最小邊上的權(quán)值。在連通圖中，選取一個節(jié)點為頂點，加入U中，對其余的每個頂點，將closedgei初始化為到U的邊的信息。選出closedge中最小邊closedgek，將k加入U中，更新剩余每組最小邊的信息。循環(huán)直到所有節(jié)點加入。11、希爾排序：a

4、.構(gòu)造數(shù)據(jù)結(jié)構(gòu)-順序表。b.初始化順序表，輸入排序個數(shù)與排序序列。c.希爾排序采用分組插入，第一個去增量d1，所有間隔為d1的記錄分在同一趟，每組中進行直接插入。第二趟取增量d2，重復(fù)，直到取到增量1，每組直接插入排序為止。 14、歸并排序：順序表 a.構(gòu)造數(shù)據(jù)結(jié)構(gòu)-順序表。b.初始化順序表，輸入排序個數(shù)與排序序列。c.歸并排序，將順序表n個記錄遞歸一分為二，直到每個子序列的長度為1。然后進行2-路歸并排序，得到n/2個長度為2或1的有序子序列；再兩兩歸并。重復(fù)。 15、四則表達式計算：棧 a. 構(gòu)造數(shù)據(jù)類型棧，數(shù)棧和字符棧。 b. 定義數(shù)棧和字符棧的初始化、壓棧、彈棧、取棧頂元素的函數(shù)。 c

5、. 先在字符棧中壓入#。輸入字符串，當(dāng)輸入字符不是#，或字符棧頂元素不是#，循環(huán)操作，從第一個字符串開始判斷，若是數(shù)字字符，輸出（后序表達式），再向后判斷，直到遇到符號字符，將之前的字符串轉(zhuǎn)化為大整數(shù)，p=0;p=s*10+si,將其 -0變?yōu)檎?，壓入?shù)棧；若為符號字符，比較字符棧棧頂元素與所輸入的字符運算符高低，：將輸入字符壓入字符棧； :彈字符棧，輸出（后序表達式），兩次彈數(shù)棧，進行相應(yīng)操作，將結(jié)果壓入數(shù)棧；=：字符棧彈棧。1.哈夫曼編碼 首先建立赫夫曼樹，由于每個赫夫曼編碼是變長編碼，因此使用一個指針數(shù)組來存放每個字符編碼串的首地址。個字符的赫夫曼編碼存儲在由HuffmanCode定義

6、的動態(tài)分配的數(shù)組HC中，構(gòu)成赫夫曼樹之后，為求編碼需從葉子結(jié)點出發(fā)走一條從葉子到跟的路徑，這樣生成的編碼與要求的編碼反序，出將生成的的代碼先從后往前一次存放在一個臨時的一維數(shù)組cd中，并設(shè)一個變量start記錄編碼在cd中起始位置，當(dāng)某字符編碼完成時，從cd的start處將編碼到該字符相應(yīng)的編碼串中。此程序較簡單，沒什么問題。 2. 遍歷恢復(fù)二叉樹由先序和中序或后序和中序可唯一確定一棵二叉樹，主要問題是恢復(fù)二叉樹出現(xiàn)問題，后經(jīng)反復(fù)調(diào)試發(fā)現(xiàn)只要不輸入相同的結(jié)點就可以。4. Kruskal算法對于教材中的Locate()函數(shù)來獲取結(jié)點下標(biāo)沒有思路，但我覺得直接使用序號作為結(jié)點更簡單，所以采用了后者

7、。8. 關(guān)鍵路徑算法代碼課本上基本都有，沒什么大問題，但從中也了解到知識學(xué)過了也得多回頭溫習(xí)，溫故而知新。6、Dijkstra算法 采用鄰接矩陣創(chuàng)建有向網(wǎng)，每次求得v0到某個頂點v的最短路徑，將v加到s集，更新最短路徑的長度同時更改Vi的前驅(qū)。通過終點依次找到其前驅(qū)，利用for語句倒序輸出即為最短路徑。在找前驅(qū)時數(shù)組起始位置沒有寫對，經(jīng)過反復(fù)查看得出正確答案。 9、二叉排序樹生成算法（含平衡化） 使用二叉排序樹的二叉鏈表作為存儲結(jié)構(gòu)，創(chuàng)建二叉樹，插入一個結(jié)點，若樹中已存在相同關(guān)鍵字結(jié)點，不再插入，調(diào)試過程中平衡二叉樹的輸出形態(tài)位置不對，通過比對結(jié)果，反復(fù)修改結(jié)點的位置，最終得出正確的平衡二叉樹

8、形態(tài)。10、 哈希表生成及哈希查找算法：利用除留余數(shù)法構(gòu)造散列函數(shù)。解決沖突的方法為：利用開放地址法中的線性探測法。當(dāng)發(fā)生沖突時，從沖突地址的下一個單元順序?qū)ふ铱諉卧?，如果到最后一個位置也沒找到空單元，則回到表頭開始繼續(xù)查找，直到找到一個空位，就把此元素放到此空位中。如果找不到空位，則說明散列表已滿，需要進行溢出處理。12、快速排序 在從大到小排序的過程中出現(xiàn)錯誤，樞軸的選擇出現(xiàn)錯誤，通過參考從小到大排序的過程，修改數(shù)據(jù)交換的條件，從而得出正確結(jié)果。13、 堆排序：首先用篩選法調(diào)整堆，然后反復(fù)調(diào)用調(diào)整堆的函數(shù)建初堆，把無序序列建成大根堆或者小根堆，最后對順序表進行堆排序并輸出每一次排序之后的序

9、列。16、矩陣運算 ：首先用一個輸入函數(shù)，進行矩陣的輸入，然后建立加減法和乘法的函數(shù)。在做加減法的時候要注意兩個矩陣的行數(shù)和列數(shù)相同，在進行矩陣乘法時兩個矩陣只要保證一個矩陣的列數(shù)和另一個矩陣的行數(shù)相等即可。4、 系統(tǒng)測試及結(jié)果 （結(jié)果附截圖）3、Prim算法： 測試：課本圖P140頁11、希爾排序： 測試:課本例題P21349 38 65 97 76 13 27 49 55 04步長：5 13 27 49 55 4 49 38 65 97 76步長：3 13 4 49 38 27 49 55 65 97 76步長：1 4 13 27 38 49 49 55 65 76 97 14、歸并排序：

10、 測試：數(shù)據(jù)課本P22615、四則表達式計算： 測試：數(shù)據(jù)12*(10-5)/(20-12)=7.5后序表達式為：12 10 5 - * 20 12 （去括號）1.赫夫曼編碼.2. 遍歷恢復(fù)二叉樹4. Kruskal6、Dijkstra算法8. 關(guān)鍵路徑算法9、二叉排序樹生成算法（含平衡化） 10、哈希表生成及哈希查找算法 12、 快速排序 13、 堆排序 16、矩陣運算5、 總結(jié)與體會 通過幾天的小學(xué)期訓(xùn)練，讓我們重新回顧并鞏固了數(shù)據(jù)結(jié)構(gòu)與算法的相關(guān)知識。在編程的時候，我們都能很明顯地感覺到以前學(xué)過的知識有很多都已經(jīng)遺忘，所以編程的時候不免有些吃力。一開始，老師就說過數(shù)據(jù)結(jié)構(gòu)是基礎(chǔ)，基礎(chǔ)不牢固，越往后越難走。因此，我們應(yīng)該在不斷學(xué)習(xí)的過程