數據結構-實驗指導手冊-資料下載頁

　　

【正文】 醫院的路徑總和）；然后在這些和中找出一個最小值。252。 自己設定n個村莊的交通圖。例如下圖所示：實驗17：線性查找一、實驗目的1）熟悉查找的基本操作。2）掌握線性查找（順序查找、二分查找）的實現。3）加深對查找的理解，逐步培養解決實際問題的編程能力。二、實驗環境裝有Visual C＋＋。本次實驗共計2學時。三、實驗內容順序查找編寫一個程序，輸出在順序表中{3，6，2，10，1，8，5，7，4，9 }中采用順序查找的方法查找關鍵字5的過程。二分查找【基本要求】編寫一個程序，輸出在順序表中{1，2，3，4，5，6，7，8，9，10}中采用二分查找法查找關鍵字9的過程。【輸出結果】輸出結果例子如下：第1次查找:在[0,9]中查找到元素R[4]:5第2次查找:在[5,9]中查找到元素R[7]:8第3次查找:在[8,9]中查找到元素R[8]:9元素9的位置是8實驗18：哈希查找一、實驗目的1）熟悉查找的基本操作。2）掌握哈希查找的實現。3）加深對查找的理解，逐步培養解決實際問題的編程能力。二、實驗環境裝有Visual C＋＋。本次實驗共計2學時。三、實驗內容【基本要求】編寫一個程序，實現哈希表的相關運算，并在此基礎上完成如下功能：（1） 建立{16,74,60,43,54,90,46,31,29,88,77}哈希表A[0..12]，哈希函數為H(k)=key%p，（p取13），并采用線性探查法解決沖突。（2） 在上述哈希表中查找關鍵字為29的記錄。（3） 在上述哈希表中刪除關鍵字為77的記錄，再將其插入。【輸出結果】輸出結果例子如下：哈希表地址: 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表關鍵字: 77 54 16 43 31 29 46 60 74 88 90 搜索次數: 2 1 1 1 1 4 1 1 1 1 1 平均搜索長度ASL(11)= ha[6].key=29 刪除關鍵字77 哈希表地址: 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表關鍵字: 54 16 43 31 29 46 60 74 88 90 搜索次數: 1 1 1 1 4 1 1 1 1 1 平均搜索長度ASL(10)= 未找到77 插入關鍵字77 哈希表地址: 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表關鍵字: 77 54 16 43 31 29 46 60 74 88 90 搜索次數: 2 1 1 1 1 4 1 1 1 1 1 平均搜索長度ASL(11)=實驗19：查找綜合實驗一、實驗目的1）熟悉查找的基本操作。2）掌握二叉排序樹的基本運算。3）加深對查找的理解，逐步培養解決實際問題的編程能力。二、實驗環境裝有Visual C＋＋。本次實驗共計4學時。三、實驗內容統計字符串中字符出現的次數編寫一個程序，由鍵盤輸入一個字符串，統計該字符串中出現的字符及其次數。然后輸出結果。要求用一個二叉樹來保存處理結果，字符串中每個不同的字符用樹的結點表示，結點應該包含四個域：該字符、該字符出現的次數、左子樹指針、右子樹指針；其中左子樹的字符的ASCII碼均小于該字符，右子樹的字符的ASCII碼均大于該字符。提示：252。 從字符串中依次讀取字符，在二叉樹中查找該字符是否存在。252。 如果存在，則該字符的出現次數加1；如果不存在，則按照二叉排序樹的要求插入該字符結點，同時設置出現次數為1。252。 全部字符讀完以后，調用二叉樹的中序遍歷，有序的輸出每個字符及其出現的次數。二叉排序樹【基本要求】編寫一個程序，實現二叉排序樹的基本運算，并在此基礎上完成如下功能：（1） 由{4，9，0，1，8，6，3，5，2，7}創建一棵二叉排序樹bt，并以括號表示法輸出。（2） 判斷bt是否為一棵二叉排序樹。（3） 采用遞歸和非遞歸兩種方法查找關鍵字為6的結點，并輸出其查找路徑。（4） 分別刪除bt中的關鍵字為4和5的結點，并輸出刪除后的二叉排序。【輸出結果】輸出結果例子如下：創建一棵BST樹: 第1步,插入4:4 第2步,插入9:4(,9) 第3步,插入0:4(0,9) 第4步,插入1:4(0(,1),9) 第5步,插入8:4(0(,1),9(8)) 第6步,插入6:4(0(,1),9(8(6))) 第7步,插入3:4(0(,1(,3)),9(8(6))) 第8步,插入5:4(0(,1(,3)),9(8(6(5)))) 第9步,插入2:4(0(,1(,3(2))),9(8(6(5)))) 第10步,插入7:4(0(,1(,3(2))),9(8(6(5,7)))) BST:4(0(,1(,3(2))),9(8(6(5,7)))) bt是一棵BST 查找6關鍵字(遞歸): 4 9 8 6 查找6關鍵字(非遞歸): 6 8 9 4 刪除操作: 原BST:4(0(,1(,3(2))),9(8(6(5,7)))) 刪除結點4:3(0(,1(,2)),9(8(6(5,7)))) 刪除結點5:3(0(,1(,2)),9(8(6(,7))))實驗20：內排序一、實驗目的1）熟悉排序的基本操作。2）掌握各種內排序的操作。3）加深對排序的理解，逐步培養解決實際問題的編程能力。二、實驗環境裝有Visual C＋＋。本次實驗共計4學時。三、實驗內容【基本要求】a) 編寫一個程序，實現直接插入排序算法，并輸出{9,8,7,6,5,4,3,2,1,0}的排序過程。b) 編寫一個程序，實現冒泡排序算法，并輸出{9,8,7,6,5,4,3,2,1,0}的排序過程。c) 編寫一個程序，實現快速排序算法，并輸出{6,8,7,9,0,1,3,2,4,5}的排序過程。d) 編寫一個程序，實現直接選擇排序算法，并輸出{6,8,7,9,0,1,3,2,4,5}的排序過程。e) 編寫一個程序，實現堆排序算法，并輸出{6,8,7,9,0,1,3,2,4,5}的排序過程。【輸出結果】a）的輸出結果例子如下：其他的輸出結果類似，要求輸出排序每一步驟的狀態。 初始關鍵字 9 8 7 6 5 4 3 2 1 0 i=1 8 9 7 6 5 4 3 2 1 0 i=2 7 8 9 6 5 4 3 2 1 0 i=3 6 7 8 9 5 4 3 2 1 0 i=4 5 6 7 8 9 4 3 2 1 0 i=5 4 5 6 7 8 9 3 2 1 0 i=6 3 4 5 6 7 8 9 2 1 0 i=7 2 3 4 5 6 7 8 9 1 0 i=8 1 2 3 4 5 6 7 8 9 0 i=9 0 1 2 3 4 5 6 7 8 9 最后結果 0 1 2 3 4 5 6 7 8 9實驗21：內排序綜合實驗一、實驗目的1）熟悉排序的基本操作。2）掌握各種內排序的操作。3）加深對排序的理解，逐步培養解決實際問題的編程能力。二、實驗環境裝有Visual C＋＋。本次實驗共計4學時。三、實驗內容某個二維數組存放了一系列的字符串，試利用排序的一些算法（如插入、冒泡、快速排序等）對這些字符串按照字典順序進行排序。例如：二維數組的字符串如下：char s[][20]={“while”，”if”，“else”，”do”，“for”，”switch”，“case”}。第 33 頁