內(nèi)蒙古大學《算法與數(shù)據(jù)結(jié)構(gòu)》實驗報告

1、第 PAGE 18頁算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學院 專業(yè) 姓名 學號 實驗1： ADT List（線性表）（6學時） 問題描述線性表是典型的線性結(jié)構(gòu)，實現(xiàn)ADT List，并在此基礎(chǔ)上實現(xiàn)兩個集合的交運算或并運算。實驗?zāi)康模?）掌握線性表的鏈表存儲結(jié)構(gòu)。（2）掌握在單鏈表上基本操作的實現(xiàn)。（3）在掌握單鏈表的基本操作上進行綜合題的實現(xiàn)。實驗內(nèi)容及要求要求用帶頭結(jié)點的單鏈表存儲兩個集合中的元素和最終的結(jié)果。集合的元素限定為十進制數(shù)，程序應(yīng)對出現(xiàn)重復的數(shù)據(jù)進行過濾，即鏈表中沒有重復數(shù)據(jù)。顯示兩個集合的內(nèi)容及其運算結(jié)果。 測試數(shù)據(jù)set1=3, 8, 5, 8,11，set2=22, 6, 8, 3,

2、15,11,20 set1set2set1set2set1=1, 3, 5, 7，set2=2, 3, 7, 14, 25,38set1set2set1set2思考（1）分析你所設(shè)計的算法的時間復雜度？(2) 若輸入兩個集合內(nèi)的元素是遞增的，見測試數(shù)據(jù)(2)，請你提出一種時間復雜度更少的算法思想，并分析時間復雜度是多少？算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學院 專業(yè) 姓名 學號 實驗2：利用棧將中綴表達式轉(zhuǎn)換為后綴表達式并進行計算（6學時）問題描述 中綴表達式是最普通的一種書寫表達式的方式，而后綴表達式不需要用括號來表示，計算機可簡化對后綴表達式的計算過程，而該過程又是棧的一個典型應(yīng)用。實驗?zāi)康?（1） 深

3、入理解棧的特性。（2） 掌握棧結(jié)構(gòu)的構(gòu)造方法。實驗內(nèi)容及要求中綴表達式中只包含、/ 運算及（ 和 ）。 可以輸入任意中綴表達式,數(shù)據(jù)為一位整數(shù)。顯示中綴表達式及轉(zhuǎn)換后的后綴表達式(為清楚起見，要求每輸出一個數(shù)據(jù)用逗號隔開)。對轉(zhuǎn)換后的后綴表達式進行計算。棧的類定義如下：#include const int StackSize=50;class Stackchar *StackList;int top; public:Stack() StackList=new charStackSize; top=-1;bool IsEmpty();bool IsFull();void Push(char x)

4、;char Pop();char GetTop();void postexpression(); / Stack測試數(shù)據(jù)63*(9-7)-8/2 轉(zhuǎn)換后的后綴表達式為： 計算結(jié)果為：(8-2)/(3-1)*(9-6) 轉(zhuǎn)換后的后綴表達式為：計算結(jié)果為：思考把中綴表達式轉(zhuǎn)化為后綴表達式的好處？ 考慮當表達式中數(shù)據(jù)的位數(shù)超過一位時，如何修改你的程序？困難在哪？實驗3：利用棧實現(xiàn)迷宮問題的非遞歸解法（6學時） 問題描述用一個二維數(shù)組mazem+2n+2 表示迷宮，0和1分別表示迷宮中的通道和障礙。數(shù)組的第0行和第m+1行，以及第0列和第n+1列是迷宮的圍墻。對任意設(shè)定的迷宮，求出一條從入口到出口的通

5、路，或得出沒有通路的結(jié)論。實驗?zāi)康纳钊肓私鈼：完犃械奶匦约皡^(qū)別。掌握棧和隊列這兩種結(jié)構(gòu)的構(gòu)造方法。設(shè)計出應(yīng)用棧解決在實際問題背景下對較復雜問題的遞歸算法。實驗內(nèi)容及要求任意設(shè)定一個迷宮，入口是（1, 1），出口是（m, n）。每個位置有東南西北四個方向。以矩陣形式輸出迷宮及其通路（通路的位置用表示）。測試數(shù)據(jù) 1 1 1 1 1 1 1 1 1 11 0 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 1 1 0 1 1 1 0 1 1 1 0 0 1 0 11 0 0 0 1 0 0 0 0 11 0 1 0 0 0 1 0 1 11 0 1 1

6、1 1 0 0 1 11 1 1 0 0 0 1 0 1 11 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1思考 分析你所設(shè)計的算法的復雜度。設(shè)計遞歸和非遞歸算法的優(yōu)、缺點各是什么？設(shè)計一個遞歸算法的三要素是什么？算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學院 專業(yè) 姓名 學號 實驗4：n皇后問題（6學時）問題描述在一個nn的國際象棋棋盤上按照每行順序擺放棋子，在棋盤上的每一個格中都可以擺放棋子，但任何兩個棋子不得在棋盤上的同一行、同一列、同一斜線上出現(xiàn)，利用遞歸算法解決該問題，并給出該問題的n個棋子的一個合理布局。實驗?zāi)康纳钊肜斫鈼５奶匦?。掌握使用遞歸實現(xiàn)某些問題。設(shè)計出應(yīng)用棧解決

7、在實際問題背景下對較復雜問題的遞歸算法。實驗內(nèi)容及要求從棋盤的第一行開始放起。輸出最后每個棋子的在棋盤上的坐標(最好以矩陣形式輸出)。測試數(shù)據(jù) 自定n值。思考 設(shè)計一個遞歸算法的三要素是什么？考慮用非遞歸實現(xiàn)該問題，并從中總結(jié)遞歸算法和非遞歸算法的優(yōu)、缺點各是什么？通過對遞歸算法的理解，總結(jié)把一個遞歸算法轉(zhuǎn)換為非遞歸算法的方法(可查參考書)，并把求n的階乘的遞歸算法轉(zhuǎn)換為非遞歸算法。算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學院 專業(yè) 姓名 學號 實驗5：打印二項展開式(a+b)n的系數(shù)（6學時）問題描述將二項式(a+b)n展開，系數(shù)構(gòu)成著名的楊輝三角形，這是典型的對隊列的應(yīng)用。實驗?zāi)康模?）深入理解隊列的特性。

8、（2）掌握使用隊列實現(xiàn)某些問題。實驗內(nèi)容及要求要求打印形式為 1 1 1 2 1 1 3 3 1 1 4 6 4 1 測試數(shù)據(jù) 自定n值。思考 （1）楊輝三角形中系數(shù)之間的關(guān)系是什么？（2）棧和隊列各應(yīng)用于什么范圍？算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學院 專業(yè) 姓名 學號 實驗6： 實現(xiàn)二叉樹的基本操作（9學時）問題描述 樹和二叉樹是最常用的非線性結(jié)構(gòu)(樹型結(jié)構(gòu))，其中以二叉樹最為常見，本實驗題要求實現(xiàn)二叉樹的最基本操作，其中遍歷二叉樹是二叉樹各種操作的基礎(chǔ)，它分為先序、中序和后序。實驗?zāi)康氖炀氄莆斩鏄涞慕Y(jié)構(gòu)特性。掌握二叉樹的各種存儲結(jié)構(gòu)的特點及實用范圍。通過二叉樹的基本操作的實現(xiàn)，從而思考一般樹的基本

9、操作的實現(xiàn)。熟練掌握各種遍歷二叉樹的遞歸和非遞歸算法。實驗內(nèi)容及要求（1）創(chuàng)建二叉樹：createBTree() 所謂創(chuàng)建二叉樹是指按照某一種或某兩種遍歷序列建立起來的二叉樹的存儲結(jié)構(gòu)。 （2）求葉結(jié)點的數(shù)目：getLeavesNum()（3）畫二叉樹：drawBTree()（4）輸出二叉樹的中序遍歷序列。測試數(shù)據(jù)以下圖所示1或2的形狀畫出二叉樹(不需畫線)，從中體會畫這兩種形狀的圖的難易程度。中序遍歷序列結(jié)果為：（2）自己設(shè)定幾組序列來驗證程序的正確性。思考（1）若二叉樹采用順序存儲，有什么缺點？ （2）根據(jù)任意兩種遍歷序列重建二叉樹，然后給出另外一種遍歷序列。（3）在遍歷二叉樹的算法中，你

10、用的是遞歸算法？還是非遞歸算法？若你用的是遞歸算法，請考慮用非遞歸算法實現(xiàn)對二叉樹的遍歷；反之考慮用遞歸算法實現(xiàn)對二叉樹的遍歷。算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學院 專業(yè) 姓名 學號 實驗7：哈夫曼樹的編/譯碼器系統(tǒng)的設(shè)計（9學時）問題描述利用哈夫曼編碼進行通訊可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)進行預先編碼；在接受端將傳來的數(shù)據(jù)進行解碼（復原）。對于可以雙向傳輸?shù)男诺?，每端都要有一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼的編譯碼系統(tǒng)。 實驗?zāi)康?通過哈夫曼樹的定義，掌握構(gòu)造哈夫曼樹的意義。掌握構(gòu)造哈夫曼樹的算法思想。通過具

11、體構(gòu)造哈夫曼樹，進一步理解構(gòu)造哈夫曼樹編碼的意義。實驗內(nèi)容及要求(1) 從終端讀入字符集大小為n（即字符的個數(shù)），逐一輸入n個字符和相應(yīng)的n個權(quán)值（即字符出現(xiàn)的頻度），建立哈夫曼樹，將它存于文件 hfmtree 中。并將建立好的哈夫曼樹以樹或凹入法形式輸出;對每個字符進行編碼并且輸出。(2) 利用已建好的哈夫曼編碼文件 hfmtree ，對鍵盤輸入的正文進行譯碼。輸出字符正文，再輸出該文的二進制碼。 測試數(shù)據(jù) 用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹：字符ABCDEFGHIJKLMN頻度641322321032115475715322057字符OPQRSTUVWXYZ空格頻度6315

12、1485180238181161168并實現(xiàn)以下報文的譯碼和輸出：THIS PROGRAM IS MY FAVORITE思考利用哈夫曼編碼，為什么能使報文中的電文總長度減少?為什么利用哈夫曼算法求出的一個字符的編碼都不是其它字符編碼的前綴？算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學院 專業(yè) 姓名 學號 實 驗8：圖的遍歷（9學時）問題描述 給定一個無向圖或有向圖，利用深度優(yōu)先遍歷和廣度優(yōu)先遍歷對給定圖進行遍歷。實驗?zāi)康?熟悉圖的兩種常用的存儲結(jié)構(gòu)。掌握對圖的兩種遍歷方法，即深度優(yōu)先遍歷和廣度優(yōu)先遍歷。進一步掌握利用遞歸或隊列結(jié)構(gòu)進行算法設(shè)計方法。實驗內(nèi)容及要求（1）構(gòu)造一個具有n個頂點的無向圖或有向圖。（2）輸

13、出以深度優(yōu)先遍歷和廣度優(yōu)先遍歷后的頂點序列。測試數(shù)據(jù) 以下圖作為測試數(shù)據(jù)： 輸出結(jié)果：思考在你所設(shè)計的算法中，使用了什么數(shù)據(jù)結(jié)構(gòu)？考慮如何把書上給出的遞歸實現(xiàn)的深度優(yōu)先遍歷算法改為非遞歸算法？算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學院 專業(yè) 姓名 學號 實 驗9：利用Prim算法求無向網(wǎng)的最小生成樹（9學時）問題描述 如要在n個城市之間建設(shè)通信網(wǎng)絡(luò)，只需架設(shè)n-1條線路即可。如何以最低的經(jīng)濟代價建設(shè)這個通信網(wǎng)，是求一個無向網(wǎng)的最小生成樹問題。實驗?zāi)康?掌握圖的各種存儲結(jié)構(gòu)和基本操作。對于實際問題的求解會選用合適的存儲結(jié)構(gòu)。通過Priml算法理解如何求無向網(wǎng)的最小生成樹。實驗內(nèi)容及要求 （1）構(gòu)造具有n個頂點的

14、無向網(wǎng)，并利用Priml算法求網(wǎng)的最小生成樹。 （2）以文本形式輸出所求得的最小生成樹中各條邊以及它們的權(quán)值。測試數(shù)據(jù) 以下圖作為測試數(shù)據(jù)： 輸出結(jié)果：思考如何判斷輸入的無向網(wǎng)存在最小生成樹? 若不存在，請分析是何緣故?在輸入數(shù)據(jù)過程中，你如何處理一條邊(權(quán)值不同)輸入1次以上的情況?在設(shè)計該算法時，你遇到的最大困難是什么? 你是如何解決的?算法與數(shù)據(jù)結(jié)構(gòu)實驗報告學院 專業(yè) 姓名 學號 實 驗10：內(nèi)部排序算法比較 （9學時）問題描述排序是計算機程序設(shè)計中一種重要操作，它的功能是將一個數(shù)據(jù)元素（或記錄）的任意序列重新排列成一個按關(guān)鍵字有序的序列。本實驗熟悉幾種典型的排序方法，并對各種算法的特點、使用范圍和效率進行進一步的了解。實驗?zāi)康?深刻理解排序的定義和各類排序的算法思想，并能靈活應(yīng)用。掌握各類排序的時間復雜度的分析方法，能從“關(guān)鍵字間的比較次數(shù)”分析算法的平均情況、最好情況和最壞情況。理解排序方法“穩(wěn)定”和“不穩(wěn)定”的含義。實驗內(nèi)容及要求 = 1 * GB3 數(shù)據(jù)由輸入或隨機函數(shù)產(chǎn)生。 = 2 * GB3 實現(xiàn)快速排序、堆排序和歸并排序算法（任選二）。 = 3 * GB3 至少要用5組不同的輸入數(shù)據(jù)做比較（每組數(shù)據(jù)不小于100），統(tǒng)計測試數(shù)據(jù)的準確的關(guān)鍵字的比較次數(shù)和移動次數(shù)（需在算法的適當位置插入對關(guān)鍵字的比較次數(shù)和移動次數(shù)的計數(shù)） = 4 *