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

《《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告（16頁(yè)珍藏版）》請(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í)) [問(wèn)題描述 ] int BookNumber; //圖書(shū)編號(hào) char BookName[50]; //書(shū)名 char AuthorName[30]; //第一作者姓名 double Price; //定價(jià) Book *next; //指向下一個(gè)圖書(shū)對(duì)象的指針 定義一個(gè)圖書(shū)類和一個(gè)書(shū)庫(kù)類。 圖書(shū)類包括圖書(shū)編號(hào)、書(shū)名、 作者(只考慮第一作者) 定價(jià)等屬性； 定義如下： 書(shū)庫(kù)類包括一個(gè)指向圖書(shū)鏈表的頭指針以及操作鏈表的相關(guān)函數(shù)。 這兩個(gè)類的 class Book

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

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

4、基本操作，包括：遍歷鏈表、插入結(jié)點(diǎn)、刪除結(jié)點(diǎn)等。 [實(shí)驗(yàn)內(nèi)容及要求 ] （1） 在 Visual C++ 6.0 環(huán)境下，編寫(xiě)程序?qū)崿F(xiàn)圖書(shū)類和書(shū)庫(kù)類； （ 2） 在主函數(shù)中建立一個(gè)圖書(shū)鏈表，并測(cè)試圖書(shū)類和書(shū)庫(kù)類中的相關(guān)方法。 班級(jí) 姓名 學(xué)號(hào) 實(shí)驗(yàn)2:線性表的應(yīng)用(6學(xué)時(shí)) ［問(wèn)題描述］ 通過(guò)單鏈表實(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í)際問(wèn)題。 ［實(shí)驗(yàn)內(nèi)容及要求］ (1) 編寫(xiě)程序，設(shè)計(jì)結(jié)點(diǎn)

5、類，通過(guò)鏈表描述整數(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í)，不開(kāi)辟新空間，只在原有的兩個(gè)鏈表上進(jìn)行操作。 ［示例輸入/輸出］ 示例輸入： 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、第一個(gè)集合共有9個(gè)元素，分別是： -100 -43 5 7 9 15 18 66 100 第二個(gè)集合共有15個(gè)元素，分別是： -100 -12 -9 0 1 5 6 8 16 22 88 123 200 365 7654 兩個(gè)集合的交共有 2個(gè)元素，分別是： -100 5 兩個(gè)集合的并共有 22個(gè)元素，分別是： -100 -43 -12 -9 0 1 5 6 7 8 9 15 16 18 22 66 88 100 123 200 365 7654 兩個(gè)集合的異或共有 20 個(gè)元素，分別是： -43 -12 -9 0 1 6 7 8 9 15 7654 16 18 2

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

8、停放在車場(chǎng)的車在它離開(kāi)停車場(chǎng)時(shí)， 必須按它停留的時(shí)間長(zhǎng)短交納費(fèi) 用。試為停車場(chǎng)編制按上述要求進(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í)際問(wèn)題。 [實(shí)驗(yàn)內(nèi)容及要求 ] 1） 以棧模擬停車場(chǎng)， 以隊(duì)列模擬停車場(chǎng)外的便道， 按照從終端讀入的輸入數(shù)據(jù)序 列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)： （i） 汽車“到達(dá)”或“離 去”信息， （ii） 汽車牌照號(hào)碼， （iii） 到達(dá)或離去的時(shí)刻。

9、 2） 對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為： 若是車輛到達(dá)， 則輸出汽車在停 車場(chǎng)內(nèi)或便道上的停車位置； 若是車輛離去， 則輸出汽車在停車場(chǎng)內(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í)停放為給要離去的汽車讓路 而從停車場(chǎng)退出來(lái)的汽車。棧中每個(gè)元素表示一輛汽車，包含兩個(gè)數(shù)據(jù)項(xiàng)：汽 車的牌照號(hào)碼和進(jìn)入停車場(chǎng)的時(shí)刻。 [示例輸入 /輸出 ] 設(shè)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 表示到達(dá)（Arrival）； D 表示離去（Departure）； E 表示程序結(jié)束（End）。 汽車 1 ?？吭谕＼噲?chǎng) 1 號(hào)位置 汽車 2 ?？吭谕＼噲?chǎng) 2 號(hào)位置 汽車 1 停車 13 小時(shí)， 繳納停車費(fèi) 65 元 汽車 3 ?？吭谕＼噲?chǎng) 2 號(hào)位置 汽車 4 ?？吭诒愕赖? 1 號(hào)位置 汽車 5 停靠在便道的 2 號(hào)位置 汽車 6 ?？吭诒愕赖? 3 號(hào)位置 汽車 2 停車 30 小時(shí)， 繳

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

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

13、視頻等）進(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 編 /譯碼器，并模擬數(shù)字圖像的壓縮存儲(chǔ)（編碼） 和解碼顯示（譯碼）的過(guò)程。 [實(shí)驗(yàn)?zāi)康?] （ 1 ） 掌握“ Huffman- 樹(shù)”的構(gòu)造過(guò)程； （ 2） 通過(guò)該實(shí)驗(yàn)，深入理解 Huffman 編碼的原理及作用； （ 3） 運(yùn)用 Huffman 編碼解決實(shí)際問(wèn)題。 [實(shí)驗(yàn)內(nèi)容及要求 ]

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

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

16、/輸出 ] 設(shè) 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 班級(jí) 姓名 學(xué)號(hào) 實(shí)驗(yàn) 5：小型文本搜索引擎的實(shí)現(xiàn)（ 12~15 學(xué)時(shí)） [問(wèn)題描述 ] 隨著互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展， 如何從海量數(shù)據(jù)中查找所需內(nèi)容， 不僅是科研人員關(guān)注的 熱點(diǎn)問(wèn)題，許多IT公司也先后推出了各自的搜索引擎，如： Google、百度、Bing等。搜索 引擎的核心是如何對(duì) Web 網(wǎng)頁(yè)構(gòu)建有效的索引，以便能夠快速查找和匹配查詢關(guān)鍵詞，并 及時(shí)地將搜索結(jié)果返回給用

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

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

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

21、續(xù)出現(xiàn)的情況。 （ 2） 嘗試實(shí)現(xiàn)從多個(gè)文檔中讀入內(nèi)容，構(gòu)建二叉查找樹(shù)，并實(shí)現(xiàn)多個(gè)文檔的搜索。 班級(jí) 姓名 學(xué)號(hào) 實(shí)驗(yàn) 6：道路選擇問(wèn)題（ 6 學(xué)時(shí)） [問(wèn)題描述 ] 某省自從實(shí)行了暢通工程計(jì)劃后， 終于修建了很多路。 不過(guò)路多了也不好， 每次要從一 個(gè)城鎮(zhèn)到另一個(gè)城鎮(zhèn)時(shí)， 都有許多種道路方案可以選擇， 而某些方案要比另一些方案行走的 距離要短很多。 這讓行人很困擾?，F(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） 掌握無(wú)向圖的最小生成樹(shù)算法（ Prim 和 Kruskal

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

23、對(duì)于每組輸入數(shù)據(jù)，利用 Prim 算法或者 Kruskal 算法構(gòu)建相應(yīng)的最小生成樹(shù)， 并輸出最短需要行走的距離。如果不存在從 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 班級(jí) 姓名 學(xué)號(hào) 實(shí)驗(yàn) 7：內(nèi)部排序算法比較（ 9 學(xué)時(shí)） [問(wèn)題描述 ] 排序是計(jì)算機(jī)程序設(shè)計(jì)中一種重要操作， 它的功能是將一個(gè)數(shù)據(jù)元素 （或記錄） 的任意 序列重新排列成一個(gè)按關(guān)鍵字有序的序列。 本實(shí)驗(yàn)熟悉幾種典型的排序方法， 并對(duì)各種算法 的特點(diǎn)、使用范

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

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

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

27、法； （2） 掌握有向圖的深度優(yōu)先遍歷算法； （ 3） 運(yùn)用深度優(yōu)先算法解決此問(wèn)題。 [實(shí)驗(yàn)內(nèi)容及要求 ] （1） 有向圖采用鄰接表或鄰接矩陣存儲(chǔ)。 （ 2） 設(shè)計(jì)算法完成問(wèn)題求解。 （3） 設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)從頂點(diǎn) Vi到頂點(diǎn)Vj的路徑。 （4） 判斷在遍歷過(guò)程中是否訪問(wèn)到頂點(diǎn) Vj （返回值為 0 或者 1即可，其中 不存在， 1 表示存在） 。 班級(jí) 姓名 學(xué)號(hào) 實(shí)驗(yàn) 10：N 皇后問(wèn)題（ 9 學(xué)時(shí)） （附加） [問(wèn)題描述 ] N 個(gè)皇后，每行一個(gè)并使其 。本實(shí)驗(yàn)求解 N 皇后的 N 皇后問(wèn)題是一個(gè)經(jīng)典的問(wèn)題，在一個(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 皇后問(wèn)題的第一個(gè)解及解個(gè)數(shù)。