《《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告（16頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、算法與數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告班級(jí) 姓名 學(xué)號(hào) 實(shí)驗(yàn) 1：線性表的建立及操作( 6 學(xué)時(shí))問題描述 int BookNumber;/圖書編號(hào)char BookName50;/書名char AuthorName30;/第一作者姓名double Price;/定價(jià)Book *next;/指向下一個(gè)圖書對(duì)象的指針定義一個(gè)圖書類和一個(gè)書庫類。 圖書類包括圖書編號(hào)、書名、 作者(只考慮第一作者)定價(jià)等屬性；定義如下：書庫類包括一個(gè)指向圖書鏈表的頭指針以及操作鏈表的相關(guān)函數(shù)。 這兩個(gè)類的class Bookpublic:void print(); / 輸出圖書的所有屬性;class BookStoreBook *
2、book_head; / 圖書鏈表的頭指針public:BookStore(); / 創(chuàng)建書庫對(duì)象，圖書鏈表的頭指針為空Book* createBook(); / 創(chuàng)建一個(gè)圖書對(duì)象void insertBook(Book *b); / 按定價(jià)從高到低將圖書對(duì)象插入到圖書鏈表void deleteBook(int booknumber); / 從鏈表中刪除圖書編號(hào)為 booknumber 的圖書 double getTotalPrice(); / 獲得該書庫中圖書的定價(jià)之和int getBookCount(); / 獲得該書庫中圖書的數(shù)目Book* findBook(int booknumber
3、); / 按照?qǐng)D書編號(hào)查找圖書，并輸出圖書信息Book* findBook(char *str); / 按照書名或者作者查找圖書，并輸出圖書信息void print(); / 輸出該書庫中所有圖書信息BookStore（）; / 釋放書庫對(duì)象 /根據(jù)需要設(shè)置其它方法;實(shí)驗(yàn)?zāi)康?（ 1） 熟悉面向?qū)ο蟪绦蛟O(shè)計(jì)中鏈表結(jié)點(diǎn)的定義以及鏈表的建立過程； （ 2） 掌握鏈表的基本操作，包括：遍歷鏈表、插入結(jié)點(diǎn)、刪除結(jié)點(diǎn)等。實(shí)驗(yàn)內(nèi)容及要求 （1）在 Visual C+ 6.0 環(huán)境下，編寫程序?qū)崿F(xiàn)圖書類和書庫類；（ 2） 在主函數(shù)中建立一個(gè)圖書鏈表，并測試圖書類和書庫類中的相關(guān)方法。班級(jí)姓名學(xué)號(hào)實(shí)驗(yàn)2:線性
4、表的應(yīng)用(6學(xué)時(shí))問題描述通過單鏈表實(shí)現(xiàn)整數(shù)集合的交(Q)、并(U)、異或(XOR)運(yùn)算。其中：兩個(gè)集合 A 和B的異或運(yùn)算的結(jié)果是屬于 A且不屬于B的元素和屬于B且不屬于A的元素。實(shí)驗(yàn)?zāi)康?1) 熟練掌握鏈表的基本操作；(2) 運(yùn)用鏈表解決實(shí)際問題。實(shí)驗(yàn)內(nèi)容及要求(1) 編寫程序，設(shè)計(jì)結(jié)點(diǎn)類，通過鏈表描述整數(shù)集合；(2) 在主函數(shù)中建立兩個(gè)遞增排序的整數(shù)鏈表，對(duì)這兩個(gè)鏈表依次執(zhí)行交、并、異或運(yùn)算，并輸出相應(yīng)結(jié)果；如果運(yùn)算結(jié)果為“空” ，則輸出“ NULL ”；(3) 由于同一個(gè)集合中不能同時(shí)存在兩個(gè)相同的元素，因此在一個(gè)鏈表中不應(yīng)存在數(shù)值相同的兩個(gè)結(jié)點(diǎn)；(4) 當(dāng)執(zhí)行集合的異或運(yùn)算時(shí)，不開辟
5、新空間，只在原有的兩個(gè)鏈表上進(jìn)行操作。示例輸入/輸出示例輸入：105 157 9100-43189 -10066156 5200-9887654016 22-12-10036518123示例輸出：第一個(gè)集合共有9個(gè)元素，分別是：-100-43579151866100第二個(gè)集合共有15個(gè)元素，分別是：-100-12-9015 6816 22881232003657654兩個(gè)集合的交共有 2個(gè)元素，分別是：-1005兩個(gè)集合的并共有 22個(gè)元素，分別是：-100 -43 -12 -9 0 1 5 6 7 89 15 16 18 22 66 88 100 123 2003657654兩個(gè)集合的異或共
6、有 20 個(gè)元素，分別是：-43 -12 -9 0 1 6 7 8 9 15765416 18 22 66 88 100 123 200 365班級(jí) 姓名 學(xué)號(hào) 實(shí)驗(yàn) 3：棧和隊(duì)列的應(yīng)用（ 12 學(xué)時(shí)）問題描述 設(shè)停車場是一個(gè)可停放 n 輛汽車的狹長通道， 且只有一個(gè)大門可供汽車進(jìn)出。 汽車在停 車場內(nèi)按車輛到達(dá)時(shí)間的先后順序， 依次由北向南排列 （大門在最南端， 最先到達(dá)的第一輛 車停放在停車場的最北端） ，若停車場內(nèi)已停滿 n 輛汽車，則后來的汽車只能在門外的便道 上等候， 一旦有車開走， 則排在便道上的第一輛車即可開入停車場； 當(dāng)停車場內(nèi)某輛車要離 開時(shí)， 在它之后進(jìn)入的車輛必須先退出車
7、場為它讓路， 待該輛車開出大門外， 其他車輛再按 原次序進(jìn)入車場； 每輛停放在車場的車在它離開停車場時(shí)， 必須按它停留的時(shí)間長短交納費(fèi) 用。試為停車場編制按上述要求進(jìn)行管理的模擬程序。實(shí)驗(yàn)?zāi)康?1）理解棧（先進(jìn)后出）和隊(duì)列（先進(jìn)先出）的工作特點(diǎn)；2）掌握棧結(jié)構(gòu)的構(gòu)造方法以及棧的基本操作（出棧、入棧）3）掌握隊(duì)列的構(gòu)造方法以及隊(duì)列的基本操作（出隊(duì)列、入隊(duì)列）4）運(yùn)用棧和隊(duì)列解決實(shí)際問題。實(shí)驗(yàn)內(nèi)容及要求 1）以棧模擬停車場， 以隊(duì)列模擬停車場外的便道， 按照從終端讀入的輸入數(shù)據(jù)序 列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)： （i） 汽車“到達(dá)”或“離 去”信息， （ii） 汽車牌照號(hào)碼， （i
8、ii） 到達(dá)或離去的時(shí)刻。2）對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為： 若是車輛到達(dá)， 則輸出汽車在停 車場內(nèi)或便道上的停車位置； 若是車輛離去， 則輸出汽車在停車場內(nèi)停留的時(shí) 間（單位是小時(shí)）和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)） ，假設(shè)停車 費(fèi)為每小時(shí) m 元。3）棧和隊(duì)列均采用鏈表結(jié)構(gòu)實(shí)現(xiàn)。4）提示：需另設(shè)一個(gè)棧（也用鏈表結(jié)構(gòu)實(shí)現(xiàn)） ，臨時(shí)停放為給要離去的汽車讓路 而從停車場退出來的汽車。棧中每個(gè)元素表示一輛汽車，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽 車的牌照號(hào)碼和進(jìn)入停車場的時(shí)刻。示例輸入 /輸出 設(shè)n=2 , m=5，則輸入數(shù)據(jù)為:2 5A 1 10A 2 15D 1 20A323A428A531
9、A633D245D470E其中：A 表示到達(dá)（Arrival）； D 表示離去（Departure）； E 表示程序結(jié)束（End）。汽車 1 停靠在停車場1 號(hào)位置汽車 2 ?？吭谕＼噲? 號(hào)位置汽車 1 停車 13 小時(shí)，繳納停車費(fèi)65 元汽車 3 ?？吭谕＼噲? 號(hào)位置汽車 4 ?？吭诒愕赖? 號(hào)位置汽車 5 ?？吭诒愕赖? 號(hào)位置汽車 6 ?？吭诒愕赖? 號(hào)位置汽車 2 停車 30 小時(shí)，繳納停車費(fèi)150 元汽車 4 ?？吭谕＼噲? 號(hào)位置（說明：汽車汽車 4 停車 25 小時(shí)，繳納停車費(fèi)125 元輸出數(shù)據(jù)為：4 進(jìn)入停車場的時(shí)間為汽車 2 離開的時(shí)間）其中：停車場從北至南的序號(hào)依次為
10、1 （棧底）n （棧頂）；便道上的停車序號(hào)從 1 （隊(duì)列頭） 開始，往后依次增一。選作內(nèi)容 （ 1） 等候在便道上的汽車可以直接從便道上開走， 此時(shí)排在它前面的汽車要先開走讓路，然后再依次排到隊(duì)尾，并使得原來排在前面的汽車仍然排在前面。（ 2） 汽車可有不同種類，則他們的占地面積不同，收費(fèi)標(biāo)準(zhǔn)也不同，如：1 輛 7 座客車和 1.5 輛小汽車的占地面積相同，收費(fèi)為每小時(shí) 3元； 1 輛卡車占地面積 相當(dāng)于 2 輛小汽車的占地面積， 收費(fèi)為每小時(shí) 4 元；一輛公共汽車占地面積相 當(dāng)于 3量小汽車的占地面積，收費(fèi)為每小時(shí) 6 元等等；因此，等候在便道上的 汽車無法可能無法進(jìn)入停車場 （假設(shè)停車場總
11、面積為 M ，當(dāng)前停車場的空余面 積小于汽車所需占地面積） 。班級(jí) 姓名 學(xué)號(hào) 實(shí)驗(yàn) 4：面向數(shù)字圖像的 Huffman 編 /譯碼器的設(shè)計(jì)與實(shí)現(xiàn)（ 1215學(xué)時(shí)）問題描述 “ Huffman- 樹”不僅能對(duì)文本數(shù)據(jù)進(jìn)行編碼、譯碼，提高文本數(shù)據(jù)的傳輸效率，同時(shí)它 也能對(duì)多媒體數(shù)據(jù)（如：數(shù)字圖像、視頻等）進(jìn)行編碼、譯碼，從而實(shí)現(xiàn)多媒體數(shù)據(jù)的壓縮 存儲(chǔ)。目前，在 Web 互聯(lián)網(wǎng)上廣泛使用的 JPEG 圖像格式就采用了 Huffman 編碼，與其他 圖像格式（如： BMP 、TIF 等）相比，同一副圖像采用 JPEG 格式時(shí)所需的存儲(chǔ)空間是最少 的。在這個(gè)實(shí)驗(yàn)中，請(qǐng)?jiān)O(shè)計(jì)一個(gè)Huffman 編 /譯碼
12、器，并模擬數(shù)字圖像的壓縮存儲(chǔ)（編碼）和解碼顯示（譯碼）的過程。實(shí)驗(yàn)?zāi)康?（ 1 ） 掌握“ Huffman- 樹”的構(gòu)造過程；（ 2） 通過該實(shí)驗(yàn)，深入理解 Huffman 編碼的原理及作用；（ 3） 運(yùn)用 Huffman 編碼解決實(shí)際問題。實(shí)驗(yàn)內(nèi)容及要求 （ 1 ） 構(gòu)造“ Huffman- 樹”： . 讀入一個(gè)大小為 N*M （ N 為圖像的高度， M 為圖像的寬度）的灰度圖像 塊，該圖像中的每個(gè)像素（元素）的取值范圍是0255，取值為 0 表示該像素是“黑色”，取值為 255 表示該像素是 “白色”，其他取值表示介于 “黑 色”和“白色”之間的灰度值。 . 統(tǒng)計(jì)讀入圖像塊中每種灰度值出現(xiàn)
13、的次數(shù)，并去除出現(xiàn)次數(shù)為零的灰度 值，以此作為構(gòu)造“ Huffman- 樹”所需的權(quán)值。 . 說明：在構(gòu)造“ Huffman- 樹”的過程中，當(dāng)有多個(gè)待合并元素的權(quán)值相同 時(shí)，每次選擇灰度值較小的兩個(gè)元素進(jìn)行合并。（2）Huffman 編碼（壓縮存儲(chǔ)） ：讀入新的灰度圖像塊， 利用已建立好的 “ Huffman- 樹”對(duì)其進(jìn)行編碼，將圖像的寬度、高度信息和編碼結(jié)果保存到文件（如： compress_image.txt ）中，同時(shí)計(jì)算 Huffman 編碼的壓縮比并輸出。 壓縮比的計(jì) 算公式如下： 壓縮比 =原始圖像所需比特?cái)?shù) /壓縮后圖像所需比特?cái)?shù) 。（ 3） Huffman 譯碼（解碼顯示）
14、 ：讀入壓縮存儲(chǔ)的灰度圖像，利用已建立好的“ Huffman- 樹”對(duì)其進(jìn)行譯碼，將譯碼結(jié)果按照原有寬度、高度還原圖像，并 將還原之后的圖像保存到文件（如： decoding_image.txt ）中。示例輸入 /輸出 設(shè) N=8 ， M=8 ，則輸入數(shù)據(jù)為：8 816216216216116215716316116216216216116215716316116216216216116215716316116216216216116215716316116216216216116215716316116416415815516115915916016016016315816016215915
15、6159159155157158159156157512 比特/215 比特）輸出數(shù)據(jù)為：Huffman 編碼的壓縮比為 2.38:1班級(jí) 姓名 學(xué)號(hào) 實(shí)驗(yàn) 5：小型文本搜索引擎的實(shí)現(xiàn)（ 1215 學(xué)時(shí)）問題描述 隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展， 如何從海量數(shù)據(jù)中查找所需內(nèi)容， 不僅是科研人員關(guān)注的 熱點(diǎn)問題，許多IT公司也先后推出了各自的搜索引擎，如：Google、百度、Bing等。搜索引擎的核心是如何對(duì) Web 網(wǎng)頁構(gòu)建有效的索引，以便能夠快速查找和匹配查詢關(guān)鍵詞，并 及時(shí)地將搜索結(jié)果返回給用戶。 在這個(gè)實(shí)驗(yàn)中， 請(qǐng)實(shí)現(xiàn)一個(gè)英文單詞的二叉查找樹， 并可根 據(jù)輸入的英文單詞進(jìn)行搜索，同時(shí)可給出單詞
16、在文檔中的位置信息。實(shí)驗(yàn)?zāi)康?1）掌握二叉查找樹的構(gòu)造過程；2）掌握二叉查找樹中結(jié)點(diǎn)的插入、刪除等操作；3）掌握二叉樹的前序、中序遍歷；4）運(yùn)用二叉查找樹解決實(shí)際問題。實(shí)驗(yàn)內(nèi)容及要求 1）構(gòu)造二叉查找樹： . 從文件中讀入內(nèi)容， 過濾掉阿拉伯?dāng)?shù)字和標(biāo)點(diǎn)符號(hào)， 并將英文字母的大寫形式全部轉(zhuǎn)換成小寫形式。 . 按照英文字母表的順序構(gòu)造英文單詞的二叉查找樹。 當(dāng)兩個(gè)英文單詞的首字母相同時(shí)，按第二個(gè)字母進(jìn)行排序，依次類推。 . 為每個(gè)英文單詞建立一個(gè)單鏈表，用于存放該單詞在文檔中的位置信息（即：該單詞是文檔的第幾個(gè)單詞，序號(hào)從 1 開始）。如果一個(gè)單詞在文 檔中出現(xiàn)多次， 則該鏈表中將包含多個(gè)結(jié)點(diǎn)，
17、并按照單詞在文檔中出現(xiàn)的 次序（位置信息）遞增排序。2）遍歷二叉查找樹： . 實(shí)現(xiàn)二叉查找樹的先序遍歷，以便能夠找出出現(xiàn)次數(shù)最多的單詞； . 搜索：輸入一個(gè)待檢索單詞， 以先序遍歷的方式從二叉查找樹中查找單詞，如果能找到該單詞， 則輸出該單詞在原始文檔中出現(xiàn)的位置信息， 否則提 示文檔中不包含該檢索詞； . 實(shí)現(xiàn)二叉查找樹的中序遍歷， 并將遍歷結(jié)果保存到文件中 （ words.txt ）。（要求：每個(gè)單詞占一行，每行依次記錄單詞、該單詞出現(xiàn)的次數(shù)、以及該單 詞在文檔中的位置信息。 ）3）刪除結(jié)點(diǎn)：. 給定一個(gè)停用詞列表 （停用詞是指對(duì)搜索沒有作用的詞， 如： of, and, a, an, t
18、he等等），將二叉查找樹中的屬于停用詞表中的單詞依次刪除（不僅刪除結(jié)點(diǎn)，還需清空記錄該單詞位置信息的單鏈表） ； . 在搜索時(shí)，當(dāng)輸入的檢索詞是停用詞時(shí)，則不進(jìn)行查詢。選作內(nèi)容 （ 1） 允許一次輸入兩個(gè)或者更多個(gè)單詞進(jìn)行查詢，即： 先獲得這些單詞各自在文檔中出現(xiàn)的位置信息， 然后再分析這些單詞的位置信息， 判斷這些單詞在原始文 檔中是否存在連續(xù)出現(xiàn)的情況。（ 2） 嘗試實(shí)現(xiàn)從多個(gè)文檔中讀入內(nèi)容，構(gòu)建二叉查找樹，并實(shí)現(xiàn)多個(gè)文檔的搜索。班級(jí) 姓名 學(xué)號(hào) 實(shí)驗(yàn) 6：道路選擇問題（ 6 學(xué)時(shí)）問題描述 某省自從實(shí)行了暢通工程計(jì)劃后， 終于修建了很多路。 不過路多了也不好， 每次要從一 個(gè)城鎮(zhèn)到另一個(gè)
19、城鎮(zhèn)時(shí)， 都有許多種道路方案可以選擇， 而某些方案要比另一些方案行走的 距離要短很多。 這讓行人很困擾。現(xiàn)在， 已知起點(diǎn)和終點(diǎn)，請(qǐng)你設(shè)計(jì)程序計(jì)算出要從起點(diǎn)到 終點(diǎn)的最短距離。實(shí)驗(yàn)?zāi)康?（ 1） 掌握?qǐng)D的鄰接矩陣表示法和鄰接表表示法；（2）掌握無向圖的最小生成樹算法（ Prim 和 Kruskal ）；（ 3） 運(yùn)用最小生成樹算法解決實(shí)際問題。實(shí)驗(yàn)內(nèi)容及要求 （ 1） 本題目包含多組輸入數(shù)據(jù)。（2） 每組數(shù)據(jù)的第一行包含兩個(gè)正整數(shù) N 和 M （0N200 ， 0M1000 ），分別代 表現(xiàn)有的城鎮(zhèn)數(shù)目和已修建的道路數(shù)目。城鎮(zhèn)分別以 0N-1 編號(hào)。（3） 接下來是 M行道路信息。每一行有三個(gè)整
20、數(shù)A, B , X （0=A, BN ; A!=B ; 0X10000 ）,分別表示城鎮(zhèn) A、城鎮(zhèn)B,以及城鎮(zhèn)A和城鎮(zhèn)B之間有一條長 度為 X 的雙向道路。（4） 再接下一行有兩個(gè)整數(shù) S，T（ 0=S,Tb+1，如此下去，直至剩下一個(gè)數(shù)為止。在 所有按這種操作方式最后得到的數(shù)中，最大的數(shù)記做max，最小的數(shù)記做min，則該數(shù)列的極差定義為 M=max-min。實(shí)驗(yàn)?zāi)康?（ 1） 深刻理解排序的定義和各類排序的算法思想，并能靈活應(yīng)用。（ 2） 考慮產(chǎn)生整數(shù)的溢出。（ 3） 理解在實(shí)際問題中怎樣應(yīng)用排序算法。實(shí)驗(yàn)內(nèi)容及要求 （ 1） 數(shù)據(jù)由輸入或隨機(jī)函數(shù)產(chǎn)生。（ 2） 考慮整數(shù)的溢出，即：考慮如
21、何表示大整數(shù)。（ 3） 運(yùn)用所學(xué)排序算法來解決該問題。示例輸入 /輸出 輸入數(shù)據(jù)為：3 5 7輸出數(shù)據(jù)為：4Vi到0 表示班級(jí) 姓名 學(xué)號(hào) 實(shí)驗(yàn) 9：有向圖的路徑問題（ 9學(xué)時(shí)） （附加）問題描述 對(duì)于有向圖G=（V,E），任意兩個(gè)頂點(diǎn) Vi, Vj V，且i工。請(qǐng)編寫程序判斷從頂點(diǎn) Vj 是否存在路徑。實(shí)驗(yàn)?zāi)康?（1）掌握?qǐng)D的鄰接矩陣表示法和鄰接表表示法；（2）掌握有向圖的深度優(yōu)先遍歷算法；（ 3） 運(yùn)用深度優(yōu)先算法解決此問題。實(shí)驗(yàn)內(nèi)容及要求 （1） 有向圖采用鄰接表或鄰接矩陣存儲(chǔ)。（ 2） 設(shè)計(jì)算法完成問題求解。（3）設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)從頂點(diǎn)Vi到頂點(diǎn)Vj的路徑。（4）判斷在遍歷過程中是否訪問到頂點(diǎn) Vj （返回值為 0 或者 1即可，其中 不存在， 1 表示存在） 。班級(jí) 姓名 學(xué)號(hào)實(shí)驗(yàn) 10：N 皇后問題（ 9 學(xué)時(shí)） （附加）問題描述 N 個(gè)皇后，每行一個(gè)并使其。本實(shí)驗(yàn)求解 N 皇后的N 皇后問題是一個(gè)經(jīng)典的問題，在一個(gè) N*N 的棋盤上放置 不能互相攻擊（同一行、同一列、同一斜線上的皇后都會(huì)自動(dòng)攻擊） 第一個(gè)解及所有解的個(gè)數(shù)。實(shí)驗(yàn)?zāi)康?（ 1） 掌握遞歸的設(shè)計(jì)方法。（ 2） 掌握回溯的設(shè)計(jì)方法。實(shí)驗(yàn)內(nèi)容及要求 （1） 隨機(jī)生成正整數(shù) N 。（ 2） 設(shè)計(jì)數(shù)據(jù)機(jī)構(gòu)存儲(chǔ) N 皇后的第一個(gè)解。（ 3） 設(shè)計(jì)算法求解 N 皇后問題的第一個(gè)解及解個(gè)數(shù)。
《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告
