本科生《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告3.doc

《本科生《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告3.doc》由會員分享，可在線閱讀，更多相關(guān)《本科生《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告3.doc（20頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

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