【正文】 楊俊、徐塞虹、漆濤 編著2006年9月 算法與數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)指導(dǎo)書目錄實(shí)驗(yàn)要求....................................................................................................................................3 試驗(yàn)一、約瑟夫環(huán)..............................................................................…………………..……4 試驗(yàn)二、長整數(shù)四則運(yùn)算運(yùn)算………………………………………………………………4 實(shí)驗(yàn)三、八皇后.....................................……..........................................................................5 實(shí)驗(yàn)四、騎士遍歷......................................……………………..............................................5 實(shí)驗(yàn)五、桌面計(jì)算器...............................……………..............................................................6 實(shí)驗(yàn)六、平衡排序二叉樹....................…...…….....................................................................6 試驗(yàn)七、多重集合的實(shí)現(xiàn)……......................................………………………………………7 試驗(yàn)八、圖論………………………………………………………………………….……..8 實(shí)驗(yàn)八、內(nèi)部排序性能的比較..........………………….............................................................8 教材及主要參考文獻(xiàn)………………………………………………………………………………..9 2 北京郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 算法與數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)指導(dǎo)書實(shí)驗(yàn)要求一、本課程在講課期間需要做上機(jī)實(shí)驗(yàn)，目的之一是檢查學(xué)生對所學(xué)算法的掌握和理解程度；其次是鍛煉學(xué)生的團(tuán)隊(duì)合作精神。二、成績：編碼：占整個(gè)實(shí)驗(yàn)成績的50%；測試：占整個(gè)實(shí)驗(yàn)成績的20%；文檔：占整個(gè)實(shí)驗(yàn)成績的30%。三、按時(shí)提交上機(jī)文檔，實(shí)驗(yàn)文檔包含以下各項(xiàng)：問題描述：實(shí)驗(yàn)題目、內(nèi)容和要求；算法思路：實(shí)驗(yàn)小組對問題的解決方法的文字描述；算法描述：用類算法語言等對算法進(jìn)行描述；源程序及驅(qū)動程序：上機(jī)實(shí)驗(yàn)編制的代碼源程序及程序運(yùn)行環(huán)境；測試數(shù)據(jù)：對算法的測試用例；結(jié)果分析和結(jié)論：對算法及測試結(jié)果的分析及結(jié)論；心得體會：通過實(shí)驗(yàn)獲得的心得體會；分工及簽名：最后是小組成員的分工及簽名。北京郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院1算法與數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)指導(dǎo)書實(shí)驗(yàn)一、約瑟夫環(huán)一、實(shí)驗(yàn)類別：設(shè)計(jì)型實(shí)驗(yàn)。二、問題描述：約瑟夫環(huán)問題是：n個(gè)人p0,p1,…pn 圍坐成一個(gè)圓環(huán)。每個(gè)人pk持有一個(gè)秘密的數(shù)字ck。0 ck 三、實(shí)驗(yàn)?zāi)康模簷z查學(xué)生對各種線性表的實(shí)現(xiàn)的掌握程度。四、實(shí)驗(yàn)學(xué)時(shí)：2小時(shí)五、實(shí)驗(yàn)組人數(shù)：1人。六、實(shí)驗(yàn)設(shè)備環(huán)境：計(jì)算機(jī)。七、實(shí)驗(yàn)原理及要點(diǎn)（知識點(diǎn)）：各種隊(duì)列的實(shí)現(xiàn)。八、實(shí)驗(yàn)內(nèi)容和要求：至少用3種以上的線性表來完成此試驗(yàn)。可以在帶頭節(jié)點(diǎn)的和不帶頭節(jié)點(diǎn)的線性表、循環(huán)的和非循環(huán)線性表、動態(tài)鏈表和靜態(tài)鏈表以及向量（數(shù)組）之間選擇三種。從空表開始，為每個(gè)人生成一個(gè)隨機(jī)數(shù)。然后將此人加入到線性表之中。九、可研究與探索的問題：給出各種實(shí)現(xiàn)的優(yōu)缺點(diǎn)比較。十、驗(yàn)收及實(shí)驗(yàn)報(bào)告要求：現(xiàn)場操作及運(yùn)行效果驗(yàn)收。要求程序必須上機(jī)編譯通過并且正確運(yùn)行。給出試驗(yàn)報(bào)告。給出各種線性表實(shí)現(xiàn)的優(yōu)缺點(diǎn)分析。實(shí)驗(yàn)二、長整數(shù)四則運(yùn)算一、實(shí)驗(yàn)類別：驗(yàn)證實(shí)驗(yàn)。二、問題描述：計(jì)算機(jī)CPU本身可以做32位或者64位的整數(shù)四則運(yùn)算。本試驗(yàn)要求對任意大小的整數(shù)實(shí)現(xiàn)其四則運(yùn)算。將一個(gè)整數(shù)N表示為N = 177。(d0 + d1*B + d2*B2 + ….+ bk*Bk)其中 1 B 三、實(shí)驗(yàn)?zāi)康模簩唧w的問題選擇適當(dāng)?shù)木€性表實(shí)現(xiàn)。四、實(shí)驗(yàn)學(xué)時(shí)：2小時(shí)五、實(shí)驗(yàn)組人數(shù)：3人。六、實(shí)驗(yàn)設(shè)備環(huán)境：計(jì)算機(jī)。七、實(shí)驗(yàn)原理及要點(diǎn)（知識點(diǎn)）：各種隊(duì)列的實(shí)現(xiàn)。八、實(shí)驗(yàn)內(nèi)容和要求：至少用2種以上的線性表來完成此試驗(yàn)。比較不同線性表實(shí)現(xiàn)的速度。九、可研究與探索的問題：1）對具體問題選擇合適的線性表實(shí)現(xiàn)。2）B 的選取問題?？?否選擇更大的基B。B的選擇所應(yīng)考慮的因素。十、驗(yàn)收及實(shí)驗(yàn)報(bào)告要求：現(xiàn)場操作及運(yùn)行效果驗(yàn)收。要求程序必須上機(jī)編譯通過并且正確運(yùn)行。給出試驗(yàn)報(bào)告。能夠得出用向量（數(shù)組）實(shí)現(xiàn)的線性表速度最快。實(shí)驗(yàn)三、八皇后問題一、實(shí)驗(yàn)類別：設(shè)計(jì)型實(shí)驗(yàn)。二、問題描述：在n*n 的國際象棋棋盤上放置n個(gè)皇后，使每個(gè)皇后不受其他皇后的攻擊。三、實(shí)驗(yàn)?zāi)康模簷z查學(xué)生對堆棧和遞歸程序掌握程度。四、實(shí)驗(yàn)學(xué)時(shí)：2小時(shí)五、實(shí)驗(yàn)組人數(shù)：1人。六、實(shí)驗(yàn)設(shè)備環(huán)境：計(jì)算機(jī)。七、實(shí)驗(yàn)原理及要點(diǎn)（知識點(diǎn)）：遞歸程序與堆棧八、實(shí)驗(yàn)內(nèi)容和要求： 分別用遞歸和堆棧完成此試驗(yàn)。統(tǒng)計(jì)程序運(yùn)行時(shí)間與問題規(guī)模n 的關(guān)系。九、可研究與探索的問題：問題的復(fù)雜度。當(dāng)n 比較大時(shí)，討論提高程序運(yùn)行的方法。十、驗(yàn)收及實(shí)驗(yàn)報(bào)告要求：現(xiàn)場操作及運(yùn)行效果驗(yàn)收。要求程序必須上機(jī)編譯通過并且正確運(yùn)行。給出試驗(yàn)報(bào)告。找出程序運(yùn)行速度的瓶頸。實(shí)驗(yàn)四、騎士遍歷一、實(shí)驗(yàn)類別：設(shè)計(jì)型實(shí)驗(yàn)。二、問題描述：在國際象棋n*n的棋盤中，一匹馬從棋盤中任意一格出發(fā)，要求用n21步走完所有的n2個(gè)格子。每個(gè)格子走且只走過一次。應(yīng)如何走？ 試給出算法實(shí)現(xiàn)。三、實(shí)驗(yàn)?zāi)康模簷z查學(xué)生對堆棧與回溯算法的掌握。四、實(shí)驗(yàn)學(xué)時(shí)：2小時(shí)五、實(shí)驗(yàn)組人數(shù)：3人。六、實(shí)驗(yàn)設(shè)備環(huán)境：計(jì)算機(jī)。七、實(shí)驗(yàn)原理及要點(diǎn)（知識點(diǎn)）：堆棧與回溯八、實(shí)驗(yàn)內(nèi)容和要求：用堆棧完成此試驗(yàn)。統(tǒng)計(jì)程序運(yùn)行時(shí)間與問題規(guī)模n 的關(guān)系。九、可研究與探索的問題：怎樣枚舉所有馬下一步可走的位置。選擇下一步所走位置的策略。注意由于這個(gè)程序非常耗時(shí)，在初期程序調(diào)試時(shí)應(yīng)取較小的n。十、驗(yàn)收及實(shí)驗(yàn)報(bào)告要求：現(xiàn)場操作及運(yùn)行效果驗(yàn)收。要求程序必須上機(jī)編譯通過并且正確運(yùn)行。給出試驗(yàn)報(bào)告。找出程序運(yùn)行速度的瓶頸。給出不同選擇策略的程序運(yùn)行 速度的比較結(jié)果。實(shí)驗(yàn)五、桌面計(jì)算器（表達(dá)式求值）一、實(shí)驗(yàn)類別：設(shè)計(jì)型實(shí)驗(yàn)。二、問題描述：模仿Unix系統(tǒng)下的dc命令。輸入表達(dá)式字符串，按回車鍵后給出表達(dá)式的值。操作數(shù)為實(shí)數(shù)。1）操作符有 “+”、“”、“*”、“/”、“^”（乘方）2）還可以有臨時(shí)變量。用法如 pi = ，r = 3, r*pi^2 3）還可以有事先定義的函數(shù)如：“sin()”（正弦）、“cos()”（余弦）、“l(fā)og()”（對數(shù)）、“l(fā)n()”（自然對數(shù)）等函數(shù)。三、實(shí)驗(yàn)?zāi)康模簷z查學(xué)生用堆棧解決實(shí)際問題。為本課程后續(xù)的內(nèi)容提供伏筆。也為后繼的課程如編譯原理預(yù)習(xí)。四、實(shí)驗(yàn)學(xué)時(shí)：2小時(shí)五、實(shí)驗(yàn)組人數(shù)：3人。六、實(shí)驗(yàn)設(shè)備環(huán)境：計(jì)算機(jī)。七、實(shí)驗(yàn)原理及要點(diǎn)（知識點(diǎn)）：堆棧，線性表，命令行參數(shù)的處理。八、實(shí)驗(yàn)內(nèi)容和要求：學(xué)生應(yīng)至少應(yīng)實(shí)現(xiàn)處理五個(gè)運(yùn)算符：“+”、“”、“*”、“/”、“^”（乘方）。可以用一個(gè)線性表來存儲臨時(shí)變量。另一個(gè)線性表來存儲預(yù)定義的函數(shù)名。九、可研究與探索的問題：查找臨時(shí)變量名的不同方法。如哈希表，二叉樹。十、驗(yàn)收及實(shí)驗(yàn)報(bào)告要求：現(xiàn)場操作及運(yùn)行效果驗(yàn)收。要求程序必須上機(jī)編譯通過并且正確運(yùn)行。給出試驗(yàn)報(bào)告。實(shí)驗(yàn)六、平衡排序二叉樹一、實(shí)驗(yàn)類別：設(shè)計(jì)型實(shí)驗(yàn)。二、問題描述：隨機(jī)生成一組整數(shù)p0,p1,…pn－１。將這組整數(shù)按生成的次序插入到一個(gè)平衡排序二叉樹中。然后將p0,p1,…pn－１隨機(jī)重新排列為q0,q1,…qn－１。再按照次次序?qū)⑦@些整數(shù)從生成的平衡排序二叉樹刪除。三、實(shí)驗(yàn)?zāi)康模浩胶馀判蚨鏄涞牟迦牒蛣h除。四、實(shí)驗(yàn)學(xué)時(shí)：2小時(shí)五、實(shí)驗(yàn)組人數(shù)：3人。六、實(shí)驗(yàn)設(shè)備環(huán)境：計(jì)算機(jī)。七、實(shí)驗(yàn)原理及要點(diǎn)（知識點(diǎn)）：平衡排序二叉樹的插入和刪除中的旋轉(zhuǎn)。八、實(shí)驗(yàn)內(nèi)容和要求：統(tǒng)計(jì)在平衡排序二叉樹的插入和刪除過程中各種旋轉(zhuǎn)的出現(xiàn)次數(shù)。九、可研究與探索的問題：研究平衡排序二叉樹與一般的排序二叉樹在插入和刪除方面的性能比較。十、驗(yàn)收及實(shí)驗(yàn)報(bào)告要求：現(xiàn)場操作及運(yùn)行效果驗(yàn)收。要求程序必須上機(jī)編譯通過并且正確運(yùn)行。給出試驗(yàn)報(bào)告。給出在均勻的隨機(jī)分布下，平衡排序二叉樹與一般排序二叉樹的性能比較。實(shí)驗(yàn)七、多重集合的實(shí)現(xiàn)一、實(shí)驗(yàn)類別：設(shè)計(jì)型實(shí)驗(yàn)。二、問題描述：實(shí)現(xiàn)數(shù)學(xué)上多重集合。所謂的多重集合類似于集合，但是一件東西可以放置多個(gè)副本。就如一個(gè)菜籃子里面可以放兩個(gè)蘋果。三、實(shí)驗(yàn)?zāi)康模翰檎医Y(jié)構(gòu)的各種實(shí)現(xiàn)。四、實(shí)驗(yàn)學(xué)時(shí)：2小時(shí)五、實(shí)驗(yàn)組人數(shù)：3人。六、實(shí)驗(yàn)設(shè)備環(huán)境：計(jì)算機(jī)。七、實(shí)驗(yàn)原理及要點(diǎn)（知識點(diǎn)）：平衡排序二叉樹的插入和刪除、遍歷，查找。哈希查找結(jié)構(gòu)。八、實(shí)驗(yàn)內(nèi)容和要求： 假設(shè)集合中包含的元素是可以排序的。將多重集合封裝成一個(gè)類。具體的實(shí)現(xiàn)可以是中序線索化的平衡排序二叉樹，或者帶父節(jié)點(diǎn)指針的平衡排序二叉樹。多重集合的界面如下：template //假設(shè)類型 T 是可以排序的 class Multi_set{Multi_set(void)。//構(gòu)造函數(shù)，初始化為空集合~Multi_set(void)。//析構(gòu)函數(shù)Multi_setamp。 operator=(Multi_set const a)。//重載運(yùn)算符=bool contains(T constamp。 v)const。//如果集合包含v 則返回true，否則返回falseMulti_setamp。 operator+=(Multi_set constamp。a)。//將集合a 并到自身中。Multi_setamp。 operator=(Multi_set constamp。 a)。//自身減去集合aMulti_setamp。 operator=(T constamp。 a)。//自身減去一個(gè)元素a}。//~class Multi_set//返回集合a,b的并template Multi_set Mult_set:: operator+(Multi_set constamp。 a，Multi_set constamp。 b)。//返回集合a,b的差template Multi_set Mult_set:: operator(Multi_set constamp。 a，Multi_set constamp。 b)。//返回 a –{v}templateMulti_set Multi_set::operator(Multi_set constamp。 a,T constamp。 v)。九、可研究與探索的問題：哈希函數(shù)的選取。比較哈希與平衡排序二叉樹的優(yōu)缺點(diǎn)、性能和速度。十、驗(yàn)收及實(shí)驗(yàn)報(bào)告要求：現(xiàn)場操作及運(yùn)行效果驗(yàn)收。要求程序必須上機(jī)編譯通過并且正確運(yùn)行。給出試驗(yàn)報(bào)告。給出平衡排序二叉樹實(shí)現(xiàn)的多重集合和用哈希實(shí)現(xiàn)的多重集合的性能比較。實(shí)驗(yàn)八、圖論一、實(shí)驗(yàn)類別：設(shè)計(jì)型實(shí)驗(yàn)。二、問題描述：實(shí)現(xiàn)圖論中的各種算法。1）最小代價(jià)生成樹的Krscal 算法和Prim算法。2）單源點(diǎn)的最短路徑的Dijstra 算法。3）深度優(yōu)先遍歷與廣度優(yōu)先遍歷。4）拓?fù)渑判?）求所有節(jié)點(diǎn)之間的最短路徑Floyd算法（在這五個(gè)小題中只要選作一個(gè)即可。）三、實(shí)驗(yàn)?zāi)康模簩W(xué)習(xí)根據(jù)不同的運(yùn)算來選取不同的存儲結(jié)構(gòu)。四、實(shí)驗(yàn)學(xué)時(shí)：2小時(shí)五、實(shí)驗(yàn)組人數(shù)：3人。六、實(shí)驗(yàn)設(shè)備環(huán)境：計(jì)算機(jī)。七、實(shí)驗(yàn)原理及要點(diǎn)（知識點(diǎn)）：圖論中的各種算法及其復(fù)雜度。根據(jù)不同的操作來決定圖的存儲結(jié)構(gòu)。八、實(shí)驗(yàn)內(nèi)容和要求：至少實(shí)現(xiàn)上面五個(gè)小題目中的一個(gè)。從文件中讀入一個(gè)圖的信息。九、可研究與探索的問題：高級數(shù)據(jù)結(jié)構(gòu)如堆、并查集在圖論算法中的應(yīng)用。十、驗(yàn)收及實(shí)驗(yàn)報(bào)告要求：現(xiàn)場操作及運(yùn)行效果驗(yàn)收。要求程序必須上機(jī)編譯通過并且正確運(yùn)行。給出試驗(yàn)報(bào)告。給出在均勻的隨機(jī)分布下，平衡排序二叉樹與一般排序二叉樹的性能比較。實(shí)驗(yàn)九、內(nèi)部排序性能的比較一、實(shí)驗(yàn)類別：設(shè)計(jì)型實(shí)驗(yàn)。二、問題描述：隨機(jī)生成一組整數(shù)p0,p1,…pn－１。對這組數(shù)據(jù)進(jìn)行排序。三、實(shí)驗(yàn)?zāi)康模罕容^不同排序算法的性能。四、實(shí)驗(yàn)學(xué)時(shí)：2小時(shí)五、實(shí)驗(yàn)組人數(shù)：3人。六、實(shí)驗(yàn)設(shè)備環(huán)境：計(jì)算機(jī)。七、實(shí)驗(yàn)原理及要點(diǎn)（知識點(diǎn)）：各種內(nèi)部排序算法。八、實(shí)驗(yàn)內(nèi)容和要求： 1）實(shí)現(xiàn)插入排序，選擇排序，希爾排序，堆排序以及快速排序。2）快速排序的多種版本。3）對單鏈表實(shí)現(xiàn)歸并排序。4）基數(shù)排序。5）對小型問題（n = 10）、中型問題（n = 1000）以及大型問題（n = 1百萬）分別統(tǒng)計(jì)不同排序算法的鍵值比較次數(shù)、鍵值移動次數(shù)以及程序運(yùn)行時(shí)間。26）排序算法的時(shí)間復(fù)雜度可以有O(n)和 O(n log n)。對相同復(fù)雜度的算法，給出他們運(yùn)行時(shí)間與時(shí)間復(fù)雜度的比值。九、可研究與探索的問題：研究快速排序算法的不同改進(jìn)方法。自省排序算法。只需要移動而不需要交換的快速排序方法。十、驗(yàn)收及實(shí)驗(yàn)報(bào)告要求：現(xiàn)場操作及運(yùn)行效果驗(yàn)收。要求程序必須上機(jī)編譯通過并且正確運(yùn)行。給出試驗(yàn)報(bào)告。給出在均勻的隨機(jī)分布下，對大中小問題的最快的排序算法。教材及主要參考文獻(xiàn)[1] 嚴(yán)蔚敏、吳偉民，數(shù)據(jù)結(jié)構(gòu)習(xí)題集，清華大學(xué)出版社，1999年[2] John , D