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