算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專業(yè) 姓名 學(xué)號(hào) 實(shí)驗(yàn)1： ADT List（線性表） （3學(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)容及要求（1） 要求用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)兩個(gè)集合中的元素和最終的結(jié)果。（2） 集合的元素限定為十進(jìn)制數(shù)，程序應(yīng)對(duì)出現(xiàn)重復(fù)的數(shù)據(jù)進(jìn)行過(guò)濾，即鏈表中沒有重復(fù)數(shù)據(jù)。（3） 顯示兩個(gè)集合的內(nèi)容及其運(yùn)算結(jié)果。測(cè)試數(shù)據(jù)（1） set1=3, 8, 5, 8,11，set2=22, 6, 8, 3, 15,11,20 set1set2set1set2（2） set1=1, 3, 5, 7，set2=2, 3, 7, 14, 25,38set1set2set1set2思考（1）分析你所設(shè)計(jì)的算法的時(shí)間復(fù)雜度？(2) 若輸入兩個(gè)集合內(nèi)的元素是遞增的，見測(cè)試數(shù)據(jù)(2)，請(qǐng)你提出一種時(shí)間復(fù)雜度更少的算法思想，并分析時(shí)間復(fù)雜度是多少？算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專業(yè) 姓名 學(xué)號(hào) 實(shí)驗(yàn)2：利用棧將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式并進(jìn)行計(jì)算（3學(xué)時(shí)）問(wèn)題描述 中綴表達(dá)式是最普通的一種書寫表達(dá)式的方式，而后綴表達(dá)式不需要用括號(hào)來(lái)表示，計(jì)算機(jī)可簡(jiǎn)化對(duì)后綴表達(dá)式的計(jì)算過(guò)程，而該過(guò)程又是棧的一個(gè)典型應(yīng)用。實(shí)驗(yàn)?zāi)康?（1） 深入理解棧的特性。（2） 掌握棧結(jié)構(gòu)的構(gòu)造方法。實(shí)驗(yàn)內(nèi)容及要求（1） 中綴表達(dá)式中只包含、/ 運(yùn)算及（ 和 ）。 （2） 可以輸入任意中綴表達(dá)式,數(shù)據(jù)為一位整數(shù)。（3） 顯示中綴表達(dá)式及轉(zhuǎn)換后的后綴表達(dá)式(為清楚起見，要求每輸出一個(gè)數(shù)據(jù)用逗號(hào)隔開)。（4） 對(duì)轉(zhuǎn)換后的后綴表達(dá)式進(jìn)行計(jì)算。棧的類定義如下：#include <iostream.h>const int StackSize=50;class Stackchar *StackList;int top; public:Stack() StackList=new charStackSize; top=-1;bool IsEmpty();bool IsFull();void Push(char x);char Pop();char GetTop();void postexpression(); / Stack測(cè)試數(shù)據(jù)（1） 63*(9-7)-8/2 轉(zhuǎn)換后的后綴表達(dá)式為： 計(jì)算結(jié)果為：（2） (8-2)/(3-1)*(9-6) 轉(zhuǎn)換后的后綴表達(dá)式為：計(jì)算結(jié)果為：思考（1） 把中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式的好處？ （2） 考慮當(dāng)表達(dá)式中數(shù)據(jù)的位數(shù)超過(guò)一位時(shí)，如何修改你的程序？困難在哪？算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專業(yè) 姓名 學(xué)號(hào) 實(shí)驗(yàn)3：n皇后問(wèn)題（6學(xué)時(shí)）問(wèn)題描述在一個(gè)nn的國(guó)際象棋棋盤上按照每行順序擺放棋子，在棋盤上的每一個(gè)格中都可以擺放棋子，但任何兩個(gè)棋子不得在棋盤上的同一行、同一列、同一斜線上出現(xiàn)，利用遞歸算法解決該問(wèn)題，并給出該問(wèn)題的n個(gè)棋子的一個(gè)合理布局。實(shí)驗(yàn)?zāi)康模?） 深入理解棧的特性。（2） 掌握使用遞歸實(shí)現(xiàn)某些問(wèn)題。（3） 設(shè)計(jì)出應(yīng)用棧解決在實(shí)際問(wèn)題背景下對(duì)較復(fù)雜問(wèn)題的遞歸算法。實(shí)驗(yàn)內(nèi)容及要求（1） 從棋盤的第一行開始放起。（2） 輸出最后每個(gè)棋子的在棋盤上的坐標(biāo)(最好以矩陣形式輸出)。測(cè)試數(shù)據(jù) 自定n值。思考 （1） 設(shè)計(jì)一個(gè)遞歸算法的三要素是什么？（2） 考慮用非遞歸實(shí)現(xiàn)該問(wèn)題，并從中總結(jié)遞歸算法和非遞歸算法的優(yōu)、缺點(diǎn)各是什么？（3） 通過(guò)對(duì)遞歸算法的理解，總結(jié)把一個(gè)遞歸算法轉(zhuǎn)換為非遞歸算法的方法(可查參考書)，并把求n的階乘的遞歸算法轉(zhuǎn)換為非遞歸算法。算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專業(yè) 姓名 學(xué)號(hào) 實(shí)驗(yàn)4：打印二項(xiàng)展開式(a+b)n的系數(shù)（3學(xué)時(shí)）問(wèn)題描述將二項(xiàng)式(a+b)n展開，系數(shù)構(gòu)成著名的楊輝三角形，這是典型的對(duì)隊(duì)列的應(yīng)用。實(shí)驗(yàn)?zāi)康模?）深入理解隊(duì)列的特性。（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é)院 專業(yè) 姓名 學(xué)號(hào) 實(shí)驗(yàn)5： 實(shí)現(xiàn)二叉樹的基本操作 (6學(xué)時(shí))問(wèn)題描述 樹和二叉樹是最常用的非線性結(jié)構(gòu)(樹型結(jié)構(gòu))，其中以二叉樹最為常見，本實(shí)驗(yàn)題要求實(shí)現(xiàn)二叉樹的最基本操作，其中遍歷二叉樹是二叉樹各種操作的基礎(chǔ)，它分為先序、中序和后序。實(shí)驗(yàn)?zāi)康模?） 熟練掌握二叉樹的結(jié)構(gòu)特性。（2） 掌握二叉樹的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及實(shí)用范圍。（3） 通過(guò)二叉樹的基本操作的實(shí)現(xiàn)，從而思考一般樹的基本操作的實(shí)現(xiàn)。（4） 熟練掌握各種遍歷二叉樹的遞歸和非遞歸算法。實(shí)驗(yàn)內(nèi)容及要求（1）創(chuàng)建二叉樹：createBTree() 所謂創(chuàng)建二叉樹是指按照某一種或某兩種遍歷序列建立起來(lái)的二叉樹的存儲(chǔ)結(jié)構(gòu)。 （2）求葉結(jié)點(diǎn)的數(shù)目：getLeavesNum()（3）畫二叉樹：drawBTree()（4）輸出二叉樹的中序遍歷序列。測(cè)試數(shù)據(jù)（1） 以下圖所示1或2的形狀畫出二叉樹(不需畫線)，從中體會(huì)畫這兩種形狀的圖的難易程度。中序遍歷序列結(jié)果為：（2）自己設(shè)定幾組序列來(lái)驗(yàn)證程序的正確性。思考（1）若二叉樹采用順序存儲(chǔ)，有什么缺點(diǎn)？ （2）根據(jù)任意兩種遍歷序列重建二叉樹，然后給出另外一種遍歷序列。（3）在遍歷二叉樹的算法中，你用的是遞歸算法？還是非遞歸算法？若你用的是遞歸算法，請(qǐng)考慮用非遞歸算法實(shí)現(xiàn)對(duì)二叉樹的遍歷；反之考慮用遞歸算法實(shí)現(xiàn)對(duì)二叉樹的遍歷。算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專業(yè) 姓名 學(xué)號(hào) 實(shí)驗(yàn)6：哈夫曼樹的編/譯碼器系統(tǒng)的設(shè)計(jì)(6學(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ā)站寫一個(gè)哈夫曼的編譯碼系統(tǒng)。 實(shí)驗(yàn)?zāi)康?（1） 通過(guò)哈夫曼樹的定義，掌握構(gòu)造哈夫曼樹的意義。（2） 掌握構(gòu)造哈夫曼樹的算法思想。（3） 通過(guò)具體構(gòu)造哈夫曼樹，進(jìn)一步理解構(gòu)造哈夫曼樹編碼的意義。實(shí)驗(yàn)內(nèi)容及要求(1) 從終端讀入字符集大小為n（即字符的個(gè)數(shù)），逐一輸入n個(gè)字符和相應(yīng)的n個(gè)權(quán)值（即字符出現(xiàn)的頻度），建立哈夫曼樹，將它存于文件 hfmtree 中。并將建立好的哈夫曼樹以樹或凹入法形式輸出;對(duì)每個(gè)字符進(jìn)行編碼并且輸出。(2) 利用已建好的哈夫曼編碼文件 hfmtree ，對(duì)鍵盤輸入的正文進(jìn)行譯碼。輸出字符正文，再輸出該文的二進(jìn)制碼。 測(cè)試數(shù)據(jù) 用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹：字符ABCDEFGHIJKLMN頻度641322321032115475715322057字符OPQRSTUVWXYZ空格頻度63151485180238181161168并實(shí)現(xiàn)以下報(bào)文的譯碼和輸出：THIS PROGRAM IS MY FAVORITE思考(1) 利用哈夫曼編碼，為什么能使報(bào)文中的電文總長(zhǎng)度減少?(2) 為什么利用哈夫曼算法求出的一個(gè)字符的編碼都不是其它字符編碼的前綴？算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專業(yè) 姓名 學(xué)號(hào) 實(shí) 驗(yàn)7：圖的遍歷（6學(xué)時(shí)）問(wèn)題描述 給定一個(gè)無(wú)向圖或有向圖，利用深度優(yōu)先遍歷和廣度優(yōu)先遍歷對(duì)給定圖進(jìn)行遍歷。實(shí)驗(yàn)?zāi)康?（1） 熟悉圖的兩種常用的存儲(chǔ)結(jié)構(gòu)。（2） 掌握對(duì)圖的兩種遍歷方法，即深度優(yōu)先遍歷和廣度優(yōu)先遍歷。（3） 進(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）輸出以深度優(yōu)先遍歷和廣度優(yōu)先遍歷后的頂點(diǎn)序列。測(cè)試數(shù)據(jù) 以下圖作為測(cè)試數(shù)據(jù)： 輸出結(jié)果：思考（1） 在你所設(shè)計(jì)的算法中，使用了什么數(shù)據(jù)結(jié)構(gòu)？（2） 考慮如何把書上給出的遞歸實(shí)現(xiàn)的深度優(yōu)先遍歷算法改為非遞歸算法？算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專業(yè) 姓名 學(xué)號(hào) 實(shí) 驗(yàn)8：利用Kruskal算法求無(wú)向網(wǎng)的最小生成樹（6學(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)的最小生成樹問(wèn)題。實(shí)驗(yàn)?zāi)康?（1） 掌握?qǐng)D的各種存儲(chǔ)結(jié)構(gòu)和基本操作。（2） 對(duì)于實(shí)際問(wèn)題的求解會(huì)選用合適的存儲(chǔ)結(jié)構(gòu)。（3） 通過(guò)Kruskal算法理解如何求無(wú)向網(wǎng)的最小生成樹。實(shí)驗(yàn)內(nèi)容及要求 （1）構(gòu)造具有n個(gè)頂點(diǎn)的無(wú)向網(wǎng)，并利用Kruskal算法求網(wǎng)的最小生成樹。 （2）以文本形式輸出所求得的最小生成樹中各條邊以及它們的權(quán)值。測(cè)試數(shù)據(jù) 以下圖作為測(cè)試數(shù)據(jù)： 輸出結(jié)果：思考（1） 如何判斷輸入的無(wú)向網(wǎng)存在最小生成樹? 若不存在，請(qǐng)分析是何緣故?（2） 在輸入數(shù)據(jù)過(guò)程中，你如何處理一條邊(權(quán)值不同)輸入1次以上的情況?（3） 在設(shè)計(jì)該算法時(shí)，你遇到的最大困難是什么? 你是如何解決的?算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專業(yè) 姓名 學(xué)號(hào) 綜合設(shè)計(jì)實(shí)驗(yàn)題目以下綜合題目可根據(jù)實(shí)際情況選做。題目1：內(nèi)部排序算法比較 （6學(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)康?（1） 深刻理解排序的定義和各類排序的算法思想，并能靈活應(yīng)用。（2） 掌握各類排序的時(shí)間復(fù)雜度的分析方法，能從“關(guān)鍵字間的比較次數(shù)”分析算法的平均情況、最好情況和最壞情況。（3） 理解排序方法“穩(wěn)定”和“不穩(wěn)定”的含義。實(shí)驗(yàn)內(nèi)容及要求 數(shù)據(jù)由輸入或隨機(jī)函數(shù)產(chǎn)生。 實(shí)現(xiàn)快速排序、堆排序和歸并排序算法。 至少要用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ù)） 對(duì)結(jié)果作出簡(jiǎn)單的分析。 測(cè)試數(shù)據(jù) 由隨機(jī)函數(shù)產(chǎn)生（還應(yīng)考慮正序、逆序和隨機(jī)序列）。思考（1） 對(duì)于快速排序，就平均時(shí)間而言，它被認(rèn)為是目前最好的一種內(nèi)部排序方法，但它對(duì)應(yīng)某些特殊序列（例如正序和逆序），時(shí)間復(fù)雜度是最差的，你認(rèn)為這種原因是如何造成的？對(duì)算法如何做改進(jìn)可以避免這一情況？（2） 為什么利用堆排序比用簡(jiǎn)單選擇排序能降低時(shí)間復(fù)雜度？ （3） 歸并排序適用于元素個(gè)數(shù)少的還是多的？ 空間利用率怎么樣？（4） 分析快速排序、堆排序和歸并排序的時(shí)間復(fù)雜度在平均情況下和最壞情況下各為多少？算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告學(xué)院 專業(yè) 姓名 學(xué)號(hào) 題目2：伙伴系統(tǒng) （6學(xué)時(shí)）問(wèn)題描述 伙伴系統(tǒng)屬于動(dòng)態(tài)存儲(chǔ)管理系統(tǒng)中的一種，系統(tǒng)通過(guò)響應(yīng)用戶提出的“請(qǐng)求”和“釋放”內(nèi)存的大小而對(duì)內(nèi)存進(jìn)行管理，在用戶提出“請(qǐng)求”時(shí)，分配一塊大小“恰當(dāng)” 的內(nèi)存區(qū)給用戶；在用戶釋放內(nèi)存區(qū)時(shí)及時(shí)回收。與其它動(dòng)態(tài)存儲(chǔ)管理方法不同的是：無(wú)論是占用塊還是空閑塊，其大小均為2的k次冪（k為某個(gè)正整數(shù)）。實(shí)驗(yàn)?zāi)康模?） 掌握數(shù)組的應(yīng)用；（2） 掌握靜態(tài)鏈表的應(yīng)用；（3） 掌握內(nèi)存管理的分配與回收；實(shí)驗(yàn)內(nèi)容及要求（1） 最小內(nèi)存塊是4字節(jié)，最大是64K。（2） API有：initiate(int k):初始化, k 是空間的大小，即2的k次方。new(int k): 分配大小為2的k次方的塊。free(int ad):釋放首地址為ad的塊。getMap():按地址順序顯示內(nèi)存塊的情況，如：0 - 15 : 0 4 / 0 15 表示內(nèi)存塊的首尾地址， 0表示該塊空閑16 - 31 : 1 432 - 95 : 1 5 每行的格式為：a b : t ka b: 表示內(nèi)存塊的首尾地址； t: 0表示該塊空閑，1表示占用；k: 表示內(nèi)存塊的大小為2的k次方；（3） 構(gòu)造2個(gè)分配回收序列進(jìn)行測(cè)試，其中至少有5次分配，3次回收。測(cè)試數(shù)據(jù) （1） 你的測(cè)試序列1是：按測(cè)試序列執(zhí)行分配回收后內(nèi)存情況是：（2）你的測(cè)試序列2是：按測(cè)試序列執(zhí)行分配回收后內(nèi)存情況是：（3）執(zhí)行new(16) 后的結(jié)果是什么？ 之后在執(zhí)行new(4) 的結(jié)果是什么？