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

1、第 PAGE 18頁(yè)算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專(zhuān)業(yè) 姓名 學(xué)號(hào) 實(shí)驗(yàn)1： ADT List（線性表）（6學(xué)時(shí)） 問(wèn)題描述線性表是典型的線性結(jié)構(gòu)，實(shí)現(xiàn)ADT List，并在此基礎(chǔ)上實(shí)現(xiàn)兩個(gè)集合的交運(yùn)算或并運(yùn)算。實(shí)驗(yàn)?zāi)康模?）掌握線性表的鏈表存儲(chǔ)結(jié)構(gòu)。（2）掌握在單鏈表上基本操作的實(shí)現(xiàn)。（3）在掌握單鏈表的基本操作上進(jìn)行綜合題的實(shí)現(xiàn)。實(shí)驗(yàn)內(nèi)容及要求要求用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)兩個(gè)集合中的元素和最終的結(jié)果。集合的元素限定為十進(jìn)制數(shù)，程序應(yīng)對(duì)出現(xiàn)重復(fù)的數(shù)據(jù)進(jìn)行過(guò)濾，即鏈表中沒(méi)有重復(fù)數(shù)據(jù)。顯示兩個(gè)集合的內(nèi)容及其運(yùn)算結(jié)果。 測(cè)試數(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è)計(jì)的算法的時(shí)間復(fù)雜度？(2) 若輸入兩個(gè)集合內(nèi)的元素是遞增的，見(jiàn)測(cè)試數(shù)據(jù)(2)，請(qǐng)你提出一種時(shí)間復(fù)雜度更少的算法思想，并分析時(shí)間復(fù)雜度是多少？算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專(zhuān)業(yè) 姓名 學(xué)號(hào) 實(shí)驗(yàn)2：利用棧將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式并進(jìn)行計(jì)算（6學(xué)時(shí)）問(wèn)題描述 中綴表達(dá)式是最普通的一種書(shū)寫(xiě)表達(dá)式的方式，而后綴表達(dá)式不需要用括號(hào)來(lái)表示，計(jì)算機(jī)可簡(jiǎn)化對(duì)后綴表達(dá)式的計(jì)算過(guò)程，而該過(guò)程又是棧的一個(gè)典型應(yīng)用。實(shí)驗(yàn)?zāi)康?（1） 深

3、入理解棧的特性。（2） 掌握棧結(jié)構(gòu)的構(gòu)造方法。實(shí)驗(yàn)內(nèi)容及要求中綴表達(dá)式中只包含、/ 運(yùn)算及（ 和 ）。 可以輸入任意中綴表達(dá)式,數(shù)據(jù)為一位整數(shù)。顯示中綴表達(dá)式及轉(zhuǎn)換后的后綴表達(dá)式(為清楚起見(jiàn)，要求每輸出一個(gè)數(shù)據(jù)用逗號(hào)隔開(kāi))。對(duì)轉(zhuǎn)換后的后綴表達(dá)式進(jìn)行計(jì)算。棧的類(lèi)定義如下：#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測(cè)試數(shù)據(jù)63*(9-7)-8/2 轉(zhuǎn)換后的后綴表達(dá)式為： 計(jì)算結(jié)果為：(8-2)/(3-1)*(9-6) 轉(zhuǎn)換后的后綴表達(dá)式為：計(jì)算結(jié)果為：思考把中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式的好處？ 考慮當(dāng)表達(dá)式中數(shù)據(jù)的位數(shù)超過(guò)一位時(shí)，如何修改你的程序？困難在哪？實(shí)驗(yàn)3：利用棧實(shí)現(xiàn)迷宮問(wèn)題的非遞歸解法（6學(xué)時(shí)） 問(wèn)題描述用一個(gè)二維數(shù)組mazem+2n+2 表示迷宮，0和1分別表示迷宮中的通道和障礙。數(shù)組的第0行和第m+1行，以及第0列和第n+1列是迷宮的圍墻。對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通

5、路，或得出沒(méi)有通路的結(jié)論。實(shí)驗(yàn)?zāi)康纳钊肓私鈼：完?duì)列的特性及區(qū)別。掌握棧和隊(duì)列這兩種結(jié)構(gòu)的構(gòu)造方法。設(shè)計(jì)出應(yīng)用棧解決在實(shí)際問(wèn)題背景下對(duì)較復(fù)雜問(wèn)題的遞歸算法。實(shí)驗(yàn)內(nèi)容及要求任意設(shè)定一個(gè)迷宮，入口是（1, 1），出口是（m, n）。每個(gè)位置有東南西北四個(gè)方向。以矩陣形式輸出迷宮及其通路（通路的位置用表示）。測(cè)試數(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è)計(jì)的算法的復(fù)雜度。設(shè)計(jì)遞歸和非遞歸算法的優(yōu)、缺點(diǎn)各是什么？設(shè)計(jì)一個(gè)遞歸算法的三要素是什么？算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專(zhuān)業(yè) 姓名 學(xué)號(hào) 實(shí)驗(yàn)4：n皇后問(wèn)題（6學(xué)時(shí)）問(wèn)題描述在一個(gè)nn的國(guó)際象棋棋盤(pán)上按照每行順序擺放棋子，在棋盤(pán)上的每一個(gè)格中都可以擺放棋子，但任何兩個(gè)棋子不得在棋盤(pán)上的同一行、同一列、同一斜線上出現(xiàn)，利用遞歸算法解決該問(wèn)題，并給出該問(wèn)題的n個(gè)棋子的一個(gè)合理布局。實(shí)驗(yàn)?zāi)康纳钊肜斫鈼５奶匦?。掌握使用遞歸實(shí)現(xiàn)某些問(wèn)題。設(shè)計(jì)出應(yīng)用棧解決

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

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

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

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

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

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

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

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