【正文】 的線性表速度最快。實驗三、八皇后問題一、實驗類別：設(shè)計型實驗。二、問題描述：在n*n 的國際象棋棋盤上放置n個皇后，使每個皇后不受其他皇后的攻擊。三、實驗?zāi)康模簷z查學(xué)生對堆棧和遞歸程序掌握程度。四、實驗學(xué)時：2小時五、實驗組人數(shù)：1人。六、實驗設(shè)備環(huán)境：計算機。七、實驗原理及要點（知識點）：遞歸程序與堆棧八、實驗內(nèi)容和要求： 分別用遞歸和堆棧完成此試驗。統(tǒng)計程序運行時間與問題規(guī)模n 的關(guān)系。九、可研究與探索的問題：問題的復(fù)雜度。當(dāng)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 , Data Structures with C++, China Machine Press, 2002.[3] Mark Allen Weiss, Data Structures and Problem Solving Using C++, 2ed, 清華大學(xué)出版社。2004年。[4] Robert Sedgewick，Algorithms in C Part 1 – 4: Fundamentals, Data Structures, Sorting, rdSearching, 3, 中國電力出版社，2003年。[5] 嚴蔚敏、吳偉民，數(shù)據(jù)結(jié)構(gòu)(C語言版)，清華大學(xué)出版社，2006年