數(shù)據(jù)結構操作題

1、實驗一線性表操作一、實驗目的熟悉并掌握線性表的邏輯結構、物理結構。熟悉并掌握順序表的存儲結構、基本操作和具體的函數(shù)定義。熟悉 VC+程序的基本結構，掌握程序中的用戶頭文件、實現(xiàn)文件和主文件之間的相互關系及各自的作用。熟悉 VC+操作環(huán)境的使用以及多文件的輸入、編輯、調試和運行的全過程。二、實驗要求實驗之前認真準備，編寫好源程序。實驗中認真調試程序，對運行結果進行分析，注意程序的正確性和健壯性的驗證。不斷積累程序的調試方法。三、實驗內容基本題:對元素類型為整型的順序存儲的線性表進行插入、刪除和查找操作。加強、提高題：2、編寫一個求解 Josephus問題的函數(shù)。用整數(shù)序列1, 2, 3, , n

2、 表示順序圍坐在圓桌周圍的人。然后使用n = 9, s = 1, m = 5 ，以及 n = 9, s = 1, m = 0 ，或者 n9, s = 1, m = 10 作為輸入數(shù)據(jù)，檢查你的程序的正確性和健壯性。最后分析所完成算法的時間復雜度。定義 JosephusCircle 類，其中含完成初始化、報數(shù)出圈成員函數(shù)、輸出顯示等方法。（可以選做其中之一）加強題：1、采用數(shù)組作為求解過程中使用的數(shù)據(jù)結構。提高題：2、采用循環(huán)鏈表作為求解過程中使用的數(shù)據(jù)結構。運行時允許指定任意 n、s、m數(shù)值，直至輸入 n = 0 退出程序。實驗二棧、隊列的實現(xiàn)、遞歸應用一、實驗目的熟悉棧、隊列這種特殊線性結構

3、的特性熟練掌握棧、隊列在順序存儲結構和鏈表存儲結構下的基本操作。二、實驗要求實驗之前認真準備，編寫好源程序。實驗中認真調試程序，對運行結果進行分析，注意程序的正確性和健壯性的驗證。不斷積累程序的調試方法。三、實驗內容基本題（必做）：分別就棧的順序存儲結構和鏈式存儲結構實現(xiàn)棧的各種基本操作。、假設以帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向對尾結點，不設頭指針，試設計相應的置隊空、入隊和出隊的程序。加強題：1、設線性表 A中有 n 個字符，試設計程序判斷字符串是否中心對稱，例如 xyzyx 和 xyzzyx都是中心對稱的字符串。提高題：1、試編寫程序：將中綴表達式計算轉換成后綴表達式。后綴

4、表達式的計算實現(xiàn)中的算法，要考慮實際運算時，后綴表達式中相鄰操作數(shù)的界定。實驗三樹、圖的實現(xiàn)與應用一、實驗目的理解樹結構的邏輯特性熟練掌握二叉樹的邏輯結構特性及各種存儲方法熟練掌握二插樹的各種基本操作，尤其是三種遍歷熟練掌握圖的存儲結構掌握圖的鄰接矩陣和鄰接表表示分別進行深度和廣度優(yōu)先搜索遍歷的算法。了解圖的最小生成樹算法。二、實驗要求實驗之前認真準備，編寫好源程序。實驗中認真調試程序，對運行結果進行分析，注意程序的正確性和健壯性的驗證。不斷積累程序的調試方法。三、實驗內容基本題1、給定一棵用鏈表表示的二叉樹，其根指針為root ，試寫出求二叉樹結點數(shù)目。2、對圖的鄰接矩陣和鄰接表表示分別進行

5、深度優(yōu)先搜索遍歷算法的實現(xiàn)。加強題1、試寫出中序遍歷二叉樹的遞歸和非遞歸程序并調試。2、寫出中序線索二叉樹的中序遍歷程序并調試。提高題1、實現(xiàn)霍夫曼編、解碼（1）輸入一系列字符及其出現(xiàn)頻率并以此構造霍夫曼樹進行編碼并輸出碼表，另輸入一段文字，對其進行霍夫曼編碼。例：CASTCASTSATATATASA（2）在 1 中已構成的霍夫曼樹的基礎上，輸入一段 01 編碼，要求輸出其解碼的原文。例：、校園導游咨詢。要求：（1）設計一個校園的平面圖，所含景點不少于8 個。以圖中的頂點表示校內各景點，存放景點名稱、代號、簡介等信息。以邊表示路徑，存放路徑長度等相關信息。（2）為來訪客人圖中任意景點相關信息的

6、查詢。（3）為來訪客人提供圖中任意景點的問路查詢，即查詢任意兩個景點之間的一條最短路。實驗四搜索一、實驗目的熟練掌握順序搜索、折半搜索和索引搜索等基本搜索算法，熟悉這些算法適合在何種存儲結構下實現(xiàn)熟練掌握二叉排序樹的特性、建立方法以及動態(tài)搜索算法熟練掌握散列表的特點及構造方法二、實驗要求實驗之前認真準備，編寫好源程序。實驗中認真調試程序，對運行結果進行分析，注意程序的正確性和健壯性的驗證。不斷積累程序的調試方法。三、實驗內容基本題1、實現(xiàn)基于有序順序表的折半搜索。2、設單鏈表的結點是按關鍵字的值從小到大排列的，試寫出對此表的搜索程序并調試。加強題1、若輸入 12000 個不同的整數(shù)，其值介于0

7、 和 19999之間，用散列法將這些數(shù)進行存儲，散列函數(shù)為 H(n)=n/2，請設計實現(xiàn)程序并調試。提高題1、建立二叉搜索樹、實現(xiàn)其刪除算法。要求：實現(xiàn)后分析其時間復雜度實驗五排序一、實驗目的熟練掌握各種內排序方法，深刻理解排序算法及其執(zhí)行過程學會分析各種內排序算法的性能了解各種排序方法的優(yōu)缺點，對于實際問題能夠選擇一種較好的排序方案二、實驗要求實驗之前認真準備，編寫好源程序。實驗中認真調試程序，對運行結果進行分析，注意程序的正確性和健壯性的驗證。不斷積累程序的調試方法。三、實驗內容基本題1、希爾排序算法的實現(xiàn)。2、快速排序算法的實現(xiàn)。加強題（可選擇其中之一）1、堆排序算法的實現(xiàn)2、給出 n 個學生的考試成績表，成績表由姓名和分數(shù)組成，試設計一個程序