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