《《算法與數(shù)據(jù)結(jié)構(gòu)》實驗報告》由會員分享，可在線閱讀，更多相關《《算法與數(shù)據(jù)結(jié)構(gòu)》實驗報告（16頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、《算法與數(shù)據(jù)結(jié)構(gòu)》實驗報告 班級 姓名 學號 實驗 1：線性表的建立及操作( 6 學時) [問題描述 ] int BookNumber; //圖書編號 char BookName[50]; //書名 char AuthorName[30]; //第一作者姓名 double Price; //定價 Book *next; //指向下一個圖書對象的指針 定義一個圖書類和一個書庫類。 圖書類包括圖書編號、書名、 作者(只考慮第一作者) 定價等屬性； 定義如下： 書庫類包括一個指向圖書鏈表的頭指針以及操作鏈表的相關函數(shù)。 這兩個類的 class Book

2、 { public: void print(); // 輸出圖書的所有屬性 }; class BookStore { Book *book_head; // 圖書鏈表的頭指針 public: BookStore(); // 創(chuàng)建書庫對象，圖書鏈表的頭指針為空 Book* createBook(); // 創(chuàng)建一個圖書對象 void insertBook(Book *b); // 按定價從高到低將圖書對象插入到圖書鏈表 void deleteBook(int booknumber); // 從鏈表中刪除圖書編號為 booknumber 的圖書 double getTota

3、lPrice(); // 獲得該書庫中圖書的定價之和 int getBookCount(); // 獲得該書庫中圖書的數(shù)目 Book* findBook(int booknumber); // 按照圖書編號查找圖書，并輸出圖書信息 Book* findBook(char *str); // 按照書名或者作者查找圖書，并輸出圖書信息 void print(); // 輸出該書庫中所有圖書信息 ~BookStore（）; // 釋放書庫對象 //根據(jù)需要設置其它方法 }; [實驗目的 ] （ 1） 熟悉面向?qū)ο蟪绦蛟O計中鏈表結(jié)點的定義以及鏈表的建立過程； （ 2） 掌握鏈表的

4、基本操作，包括：遍歷鏈表、插入結(jié)點、刪除結(jié)點等。 [實驗內(nèi)容及要求 ] （1） 在 Visual C++ 6.0 環(huán)境下，編寫程序?qū)崿F(xiàn)圖書類和書庫類； （ 2） 在主函數(shù)中建立一個圖書鏈表，并測試圖書類和書庫類中的相關方法。 班級 姓名 學號 實驗2:線性表的應用(6學時) ［問題描述］ 通過單鏈表實現(xiàn)整數(shù)集合的交(Q)、并(U)、異或(XOR)運算。其中：兩個集合 A 和B的異或運算的結(jié)果是屬于 A且不屬于B的元素和屬于B且不屬于A的元素。 ［實驗目的］ (1) 熟練掌握鏈表的基本操作； (2) 運用鏈表解決實際問題。 ［實驗內(nèi)容及要求］ (1) 編寫程序，設計結(jié)點

5、類，通過鏈表描述整數(shù)集合； (2) 在主函數(shù)中建立兩個遞增排序的整數(shù)鏈表，對這兩個鏈表 依次執(zhí)行交、并、異 或運算，并輸出相應結(jié)果；如果運算結(jié)果為“空” ，則輸出“ NULL ”； (3) 由于同一個集合中不能同時存在兩個相同的元素， 因此在一個鏈表中不應存在 數(shù)值相同的兩個結(jié)點； (4) 當執(zhí)行集合的異或運算時，不開辟新空間，只在原有的兩個鏈表上進行操作。 ［示例輸入/輸出］ 示例輸入： 10 5 15 7 9 100 -43 18 9 -100 66 15 6 5 200 -9 88 7654 0 16 22 -12 -100 365 1 8 123 示例輸出：

6、第一個集合共有9個元素，分別是： -100 -43 5 7 9 15 18 66 100 第二個集合共有15個元素，分別是： -100 -12 -9 0 1 5 6 8 16 22 88 123 200 365 7654 兩個集合的交共有 2個元素，分別是： -100 5 兩個集合的并共有 22個元素，分別是： -100 -43 -12 -9 0 1 5 6 7 8 9 15 16 18 22 66 88 100 123 200 365 7654 兩個集合的異或共有 20 個元素，分別是： -43 -12 -9 0 1 6 7 8 9 15 7654 16 18 2

7、2 66 88 100 123 200 365 班級 姓名 學號 實驗 3：棧和隊列的應用（ 12 學時） [問題描述 ] 設停車場是一個可停放 n 輛汽車的狹長通道， 且只有一個大門可供汽車進出。 汽車在停 車場內(nèi)按車輛到達時間的先后順序， 依次由北向南排列 （大門在最南端， 最先到達的第一輛 車停放在停車場的最北端） ，若停車場內(nèi)已停滿 n 輛汽車，則后來的汽車只能在門外的便道 上等候， 一旦有車開走， 則排在便道上的第一輛車即可開入停車場； 當停車場內(nèi)某輛車要離 開時， 在它之后進入的車輛必須先退出車場為它讓路， 待該輛車開出大門外， 其他車輛再按 原次序進入車場； 每輛

8、停放在車場的車在它離開停車場時， 必須按它停留的時間長短交納費 用。試為停車場編制按上述要求進行管理的模擬程序。 [實驗目的 ] 1） 理解棧（先進后出）和隊列（先進先出）的工作特點； 2） 掌握棧結(jié)構(gòu)的構(gòu)造方法以及棧的基本操作（出棧、入棧） 3） 掌握隊列的構(gòu)造方法以及隊列的基本操作（出隊列、入隊列） 4） 運用棧和隊列解決實際問題。 [實驗內(nèi)容及要求 ] 1） 以棧模擬停車場， 以隊列模擬停車場外的便道， 按照從終端讀入的輸入數(shù)據(jù)序 列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項： （i） 汽車“到達”或“離 去”信息， （ii） 汽車牌照號碼， （iii） 到達或離去的時刻。

9、 2） 對每一組輸入數(shù)據(jù)進行操作后的輸出信息為： 若是車輛到達， 則輸出汽車在停 車場內(nèi)或便道上的停車位置； 若是車輛離去， 則輸出汽車在停車場內(nèi)停留的時 間（單位是小時）和應交納的費用（在便道上停留的時間不收費） ，假設停車 費為每小時 m 元。 3） 棧和隊列均采用鏈表結(jié)構(gòu)實現(xiàn)。 4） 提示：需另設一個棧（也用鏈表結(jié)構(gòu)實現(xiàn)） ，臨時停放為給要離去的汽車讓路 而從停車場退出來的汽車。棧中每個元素表示一輛汽車，包含兩個數(shù)據(jù)項：汽 車的牌照號碼和進入停車場的時刻。 [示例輸入 /輸出 ] 設n=2 , m=5，則輸入數(shù)據(jù)為: 2 5 A 1 10 A 2 15 D 1 20

10、A 3 23 A 4 28 A 5 31 A 6 33 D 2 45 D 4 70 E 其中： A 表示到達（Arrival）； D 表示離去（Departure）； E 表示程序結(jié)束（End）。 汽車 1 停靠在停車場 1 號位置 汽車 2 ?？吭谕＼噲? 2 號位置 汽車 1 停車 13 小時， 繳納停車費 65 元 汽車 3 ?？吭谕＼噲? 2 號位置 汽車 4 ?？吭诒愕赖? 1 號位置 汽車 5 停靠在便道的 2 號位置 汽車 6 ?？吭诒愕赖? 3 號位置 汽車 2 停車 30 小時， 繳

11、納停車費 150 元 汽車 4 ?？吭谕＼噲? 2 號位置 （說明：汽車 汽車 4 停車 25 小時， 繳納停車費 125 元 輸出數(shù)據(jù)為： 4 進入停車場的時間為汽車 2 離開的時間） 其中：停車場從北至南的序號依次為 1 （棧底）~n （棧頂）；便道上的停車序號從 1 （隊列頭） 開始，往后依次增一。 [選作內(nèi)容 ] （ 1） 等候在便道上的汽車可以直接從便道上開走， 此時排在它前面的汽車要先開走 讓路，然后再依次排到隊尾，并使得原來排在前面的汽車仍然排在前面。 （ 2） 汽車可有不同種類，則他們的占地面積不同，收費標準也不同，如： 1 輛 7 座 客車和

12、1.5 輛小汽車的占地面積相同，收費為每小時 3元； 1 輛卡車占地面積 相當于 2 輛小汽車的占地面積， 收費為每小時 4 元；一輛公共汽車占地面積相 當于 3量小汽車的占地面積，收費為每小時 6 元等等；因此，等候在便道上的 汽車無法可能無法進入停車場 （假設停車場總面積為 M ，當前停車場的空余面 積小于汽車所需占地面積） 。 班級 姓名 學號 實驗 4：面向數(shù)字圖像的 Huffman 編 /譯碼器的設計與實現(xiàn)（ 12~15 學時） [問題描述 ] “ Huffman- 樹”不僅能對文本數(shù)據(jù)進行編碼、譯碼，提高文本數(shù)據(jù)的傳輸效率，同時它 也能對多媒體數(shù)據(jù)（如：數(shù)字圖像、

13、視頻等）進行編碼、譯碼，從而實現(xiàn)多媒體數(shù)據(jù)的壓縮 存儲。目前，在 Web 互聯(lián)網(wǎng)上廣泛使用的 JPEG 圖像格式就采用了 Huffman 編碼，與其他 圖像格式（如： BMP 、TIF 等）相比，同一副圖像采用 JPEG 格式時所需的存儲空間是最少 的。在這個實驗中，請設計一個 Huffman 編 /譯碼器，并模擬數(shù)字圖像的壓縮存儲（編碼） 和解碼顯示（譯碼）的過程。 [實驗目的 ] （ 1 ） 掌握“ Huffman- 樹”的構(gòu)造過程； （ 2） 通過該實驗，深入理解 Huffman 編碼的原理及作用； （ 3） 運用 Huffman 編碼解決實際問題。 [實驗內(nèi)容及要求 ]

14、（ 1 ） 構(gòu)造“ Huffman- 樹”： ① . 讀入一個大小為 N*M （ N 為圖像的高度， M 為圖像的寬度）的灰度圖像 塊，該圖像中的每個像素（元素）的取值范圍是 0~255，取值為 0 表示該 像素是“黑色”，取值為 255 表示該像素是 “白色”，其他取值表示介于 “黑 色”和“白色”之間的灰度值。 ② . 統(tǒng)計讀入圖像塊中每種灰度值出現(xiàn)的次數(shù)，并去除出現(xiàn)次數(shù)為零的灰度 值，以此作為構(gòu)造“ Huffman- 樹”所需的權值。 ③ . 說明：在構(gòu)造“ Huffman- 樹”的過程中，當有多個待合并元素的權值相同 時，每次選擇灰度值較小的兩個元素進行合并。 （2） Huf

15、fman 編碼（壓縮存儲） ：讀入新的灰度圖像塊， 利用已建立好的 “ Huffman- 樹”對其進行編碼，將圖像的寬度、高度信息和編碼結(jié)果保存到文件（如： compress_image.txt ）中，同時計算 Huffman 編碼的壓縮比并輸出。 壓縮比的計 算公式如下： 壓縮比 =原始圖像所需比特數(shù) /壓縮后圖像所需比特數(shù) 。 （ 3） Huffman 譯碼（解碼顯示） ：讀入壓縮存儲的灰度圖像，利用已建立好的 “ Huffman- 樹”對其進行譯碼，將譯碼結(jié)果按照原有寬度、高度還原圖像，并 將還原之后的圖像保存到文件（如： decoding_image.txt ）中。 [示例輸入

16、/輸出 ] 設 N=8 ， M=8 ，則輸入數(shù)據(jù)為： 8 8 162 162 162 161 162 157 163 161 162 162 162 161 162 157 163 161 162 162 162 161 162 157 163 161 162 162 162 161 162 157 163 161 162 162 162 161 162 157 163 161 164 164 158 155 161 159 159 160 160 160 163 158 160 1

17、62 159 156 159 159 155 157 158 159 156 157 512 比特/215 比特） 輸出數(shù)據(jù)為： Huffman 編碼的壓縮比為 2.38:1 班級 姓名 學號 實驗 5：小型文本搜索引擎的實現(xiàn)（ 12~15 學時） [問題描述 ] 隨著互聯(lián)網(wǎng)技術的飛速發(fā)展， 如何從海量數(shù)據(jù)中查找所需內(nèi)容， 不僅是科研人員關注的 熱點問題，許多IT公司也先后推出了各自的搜索引擎，如： Google、百度、Bing等。搜索 引擎的核心是如何對 Web 網(wǎng)頁構(gòu)建有效的索引，以便能夠快速查找和匹配查詢關鍵詞，并 及時地將搜索結(jié)果返回給用

18、戶。 在這個實驗中， 請實現(xiàn)一個英文單詞的二叉查找樹， 并可根 據(jù)輸入的英文單詞進行搜索，同時可給出單詞在文檔中的位置信息。 [實驗目的 ] 1） 掌握二叉查找樹的構(gòu)造過程； 2） 掌握二叉查找樹中結(jié)點的插入、刪除等操作； 3） 掌握二叉樹的前序、中序遍歷； 4） 運用二叉查找樹解決實際問題。 [實驗內(nèi)容及要求 ] 1） 構(gòu)造二叉查找樹： ① . 從文件中讀入內(nèi)容， 過濾掉阿拉伯數(shù)字和標點符號， 并將英文字母的大寫 形式全部轉(zhuǎn)換成小寫形式。 ② . 按照英文字母表的順序構(gòu)造英文單詞的二叉查找樹。 當兩個英文單詞的首 字母相同時，按第二個字母進行排序，依次類推。 ③ .

19、為每個英文單詞建立一個單鏈表，用于存放該單詞在文檔中的位置信息 （即：該單詞是文檔的第幾個單詞，序號從 1 開始）。如果一個單詞在文 檔中出現(xiàn)多次， 則該鏈表中將包含多個結(jié)點， 并按照單詞在文檔中出現(xiàn)的 次序（位置信息）遞增排序。 2） 遍歷二叉查找樹： ① . 實現(xiàn)二叉查找樹的先序遍歷，以便能夠找出出現(xiàn)次數(shù)最多的單詞； ② . 搜索：輸入一個待檢索單詞， 以先序遍歷的方式從二叉查找樹中查找單詞， 如果能找到該單詞， 則輸出該單詞在原始文檔中出現(xiàn)的位置信息， 否則提 示文檔中不包含該檢索詞； ③ . 實現(xiàn)二叉查找樹的中序遍歷， 并將遍歷結(jié)果保存到文件中 （ words.txt ）。

20、（要 求：每個單詞占一行，每行依次記錄單詞、該單詞出現(xiàn)的次數(shù)、以及該單 詞在文檔中的位置信息。 ） 3） 刪除結(jié)點： ①. 給定一個停用詞列表 （停用詞是指對搜索沒有作用的詞， 如： of, and, a, an, the等等），將二叉查找樹中的屬于停用詞表中的單詞依次刪除 （不僅刪除 結(jié)點，還需清空記錄該單詞位置信息的單鏈表） ； ② . 在搜索時，當輸入的檢索詞是停用詞時，則不進行查詢。 [選作內(nèi)容 ] （ 1） 允許一次輸入兩個或者更多個單詞進行查詢， 即： 先獲得這些單詞各自在文檔 中出現(xiàn)的位置信息， 然后再分析這些單詞的位置信息， 判斷這些單詞在原始文 檔中是否存在連

21、續(xù)出現(xiàn)的情況。 （ 2） 嘗試實現(xiàn)從多個文檔中讀入內(nèi)容，構(gòu)建二叉查找樹，并實現(xiàn)多個文檔的搜索。 班級 姓名 學號 實驗 6：道路選擇問題（ 6 學時） [問題描述 ] 某省自從實行了暢通工程計劃后， 終于修建了很多路。 不過路多了也不好， 每次要從一 個城鎮(zhèn)到另一個城鎮(zhèn)時， 都有許多種道路方案可以選擇， 而某些方案要比另一些方案行走的 距離要短很多。 這讓行人很困擾?，F(xiàn)在， 已知起點和終點，請你設計程序計算出要從起點到 終點的最短距離。 [實驗目的 ] （ 1） 掌握圖的鄰接矩陣表示法和鄰接表表示法； （2） 掌握無向圖的最小生成樹算法（ Prim 和 Kruskal

22、）； （ 3） 運用最小生成樹算法解決實際問題。 [實驗內(nèi)容及要求 ] （ 1） 本題目包含多組輸入數(shù)據(jù)。 （2） 每組數(shù)據(jù)的第一行包含兩個正整數(shù) N 和 M （0

23、對于每組輸入數(shù)據(jù)，利用 Prim 算法或者 Kruskal 算法構(gòu)建相應的最小生成樹， 并輸出最短需要行走的距離。如果不存在從 S到T的路線，則輸出-1。 [示例輸入 /輸出 ] 輸入數(shù)據(jù)為： 3 3 0 1 1 0 2 3 1 2 1 0 2 3 1 0 1 1 1 2 輸出數(shù)據(jù)為： 2 -1 班級 姓名 學號 實驗 7：內(nèi)部排序算法比較（ 9 學時） [問題描述 ] 排序是計算機程序設計中一種重要操作， 它的功能是將一個數(shù)據(jù)元素 （或記錄） 的任意 序列重新排列成一個按關鍵字有序的序列。 本實驗熟悉幾種典型的排序方法， 并對各種算法 的特點、使用范

24、圍和效率進行進一步的了解。 [實驗目的 ] （ 1） 深刻理解排序的定義和各類排序的算法思想，并能靈活應用。 （ 2） 掌握各類排序的時間復雜度的分析方法，能從“關鍵字間的比較次數(shù)”分析 算法的平均情況、最好情況和最壞情況。 （ 3） 理解排序方法“穩(wěn)定”和“不穩(wěn)定”的含義。 [實驗內(nèi)容及要求 ] （ 1） 數(shù)據(jù)由輸入或隨機函數(shù)產(chǎn)生。 （ 2） 實現(xiàn)簡單插入排序、簡單選擇排序、快速排序、堆排序和歸并排序算法等。 （ 3） 至少要用 5 組不同的輸入數(shù)據(jù)做比較（每組數(shù)據(jù)不小于 100，應考慮正序、 逆序和隨機序列） ，統(tǒng)計關鍵字的比較次數(shù)和移動次數(shù)（需在算法的適當位 置插入對關

25、鍵字的比較次數(shù)和移動次數(shù)的計數(shù)） 、穩(wěn)定性、最好情況、最壞 情況、平均情況等。 （ 4） 對結(jié)果做出簡單的分析。 班級 姓名 學號 實驗 8：數(shù)列極差問題（ 9 學時） （附加） [問題描述 ] 隨機生成 n 個正整數(shù)排成一個數(shù)列，進行如下操作：每次去掉其中兩個數(shù) a 和b,然后在數(shù)列中的加入一個數(shù) a>b+1，如此下去，直至剩下一個數(shù)為止。在 所有按這種操作方式最后得到的數(shù)中，最大的數(shù)記做 max，最小的數(shù)記做min， 則該數(shù)列的極差定義為 M=max-min。 [實驗目的 ] （ 1） 深刻理解排序的定義和各類排序的算法思想，并能靈活應用。 （ 2） 考慮產(chǎn)生整數(shù)

26、的溢出。 （ 3） 理解在實際問題中怎樣應用排序算法。 [實驗內(nèi)容及要求 ] （ 1） 數(shù)據(jù)由輸入或隨機函數(shù)產(chǎn)生。 （ 2） 考慮整數(shù)的溢出，即：考慮如何表示大整數(shù)。 （ 3） 運用所學排序算法來解決該問題。 [示例輸入 /輸出 ] 輸入數(shù)據(jù)為： 3 5 7 輸出數(shù)據(jù)為： 4 Vi到 0 表示 班級 姓名 學號 實驗 9：有向圖的路徑問題（ 9學時） （附加） [問題描述 ] 對于有向圖G=（V,E），任意兩個頂點 Vi, Vj € V，且i工。請編寫程序判斷從頂點 Vj 是否存在路徑。 [實驗目的 ] （1） 掌握圖的鄰接矩陣表示法和鄰接表表示

27、法； （2） 掌握有向圖的深度優(yōu)先遍歷算法； （ 3） 運用深度優(yōu)先算法解決此問題。 [實驗內(nèi)容及要求 ] （1） 有向圖采用鄰接表或鄰接矩陣存儲。 （ 2） 設計算法完成問題求解。 （3） 設計存儲結(jié)構(gòu)，存儲從頂點 Vi到頂點Vj的路徑。 （4） 判斷在遍歷過程中是否訪問到頂點 Vj （返回值為 0 或者 1即可，其中 不存在， 1 表示存在） 。 班級 姓名 學號 實驗 10：N 皇后問題（ 9 學時） （附加） [問題描述 ] N 個皇后，每行一個并使其 。本實驗求解 N 皇后的 N 皇后問題是一個經(jīng)典的問題，在一個 N*N 的棋盤上放置 不能互相攻擊（同一行、同一列、同一斜線上的皇后都會自動攻擊） 第一個解及所有解的個數(shù)。 [實驗目的 ] （ 1） 掌握遞歸的設計方法。 （ 2） 掌握回溯的設計方法。 [實驗內(nèi)容及要求 ] （1） 隨機生成正整數(shù) N 。 （ 2） 設計數(shù)據(jù)機構(gòu)存儲 N 皇后的第一個解。 （ 3） 設計算法求解 N 皇后問題的第一個解及解個數(shù)。