《本科生《算法與數據結構》實驗報告3.doc》由會員分享，可在線閱讀，更多相關《本科生《算法與數據結構》實驗報告3.doc（20頁珍藏版）》請在裝配圖網上搜索。

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