1、實驗六 查找/檢索一 實驗任務1）靜態查找方法的實現2）動態查找方法的實現二 實驗目的1）掌握典型的查找方法（折半查找、二叉樹查找）。2）了解各種查找方法的適用范圍和效率。三 實驗原理1 查找表表（Table）是由同一種類型數據元素（記錄）構成的集合。表的抽象數據類型定義如下：ADT Table數據對象：具有同種數據類型的數據元素的集合； 數據關系：數據元素之間無特定的次序關系，同屬一個集合； 基本操作： CreateTable (&L)操作結果：創建一個空表L。TableEmpty( L )初始條件：表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE。 TableInser

2、t(&L, newItem)初始條件：表L已存在，newItem為給定元素。操作結果：在表L中插入一個新數據元素newItem。 TableDelete(&L, searchKey)初始條件：表L已存在，searchKey為給定元素。操作結果：在表L中刪除一個關鍵字值等于searchKey 的數據元素。 TableSearch( L, searchKey)初始條件：表L已存在，searchKey為給定元素。操作結果：在表中查找一個關鍵字值等于searchKey 的數據元素。 TableTraverse( L, visit( )初始條件：表L已存在，visit( )是對元素操作的應用函數。操作結

3、果：按某種次序對L中元素調用函數visit( )一次且僅一次。一旦visit( )失敗，則操作失敗。 ADT Table若對表只作“查找”的操作，則稱此類表為靜態查找表(Static Search Table)。若在查找過程中同時插入表中不存在的數據元素，或者在表中刪除已存在的某個數據元素，則稱此類表為動態查找表(Dynamic Search Table)。2靜態查找（1）順序查找順序查找(Sequential Search)的方法是：從表的一端開始，逐個進行記錄的關鍵字和給定值的比較，若某個記錄的關鍵字和給定值比較相等，則查找成功，找到所查記錄；反之，若找遍了表中所有記錄，也未找到關鍵字與給

4、定值相等的記錄，則查找不成功。（2）折半查找折半查找（Binary Serach）的查找過程是：首先將給定的值key與有序表中間位置的記錄的關鍵字相比較，若兩者相等，則查找成功，否則根據比較結果確定下次查找范圍是在中間記錄的前半部分還是后半部分，然后在新的查找范圍內進行同樣操作，如此重復迭代，直到查找成功或失敗。折半查找優點是比較次數少，查找速度快，尤其當表的規模較大（n值較大）時，它的查找效率較高。但是，折半查找只適用于有序表，且限于順序存儲結構（對線性鏈表無法進行折半查找）。因此，在查找之前必須將順序表按關鍵字的大小排序。3動態查找（1）二叉查找樹二叉查找樹（Binary Search T

5、ree）又稱二叉排序樹（Binary Sort Tree），是這樣一棵二叉樹，它或為空，或者每個結點中包含一個關鍵字，并滿足如下條件：（1）若它的左子樹存在，則左子樹上所有結點的關鍵字值均小于根結點。（2）若它的右子樹存在，則右子樹上所有結點的關鍵字值均大于根結點。（3）它的左、右子樹也是一棵二叉查找樹。二叉查找樹結構兼有順序存儲結構和鏈式存儲結構的最佳特性，是實現動態查找的最佳選擇。（2）二叉查找樹的建立從空樹出發，經過一系列的插入操作之后，可以構建一棵二叉查找樹。若在二叉查找樹上插入一個元素，具體操作如下：將一個新結點插入到一棵空二叉查找樹中非常容易實現，只需將root指針指向新結點即可。

6、如果樹不空，則必須將插入結點的關鍵字值與根結點的關鍵字值比較。如果新插入結點的關鍵字值較小，則插入結點必須插入到該根結點的左子樹中；如果較大，則插入結點必須插入到該根結點的右子樹中。新插入結點一定是一個新添加的葉子結點，并且是在查找不成功時查找路徑上訪問的最后一個結點的左孩子或右孩子結點。（3）二叉查找樹的查找為了查找給定的目標，首先將它與樹根結點的關鍵字進行比較。如果相等，則完成查找，否則將依據給定的關鍵字值和根結點的關鍵字之間的大小關系，分別轉向左子樹或右子樹繼續查找，直到查找成功或命中一棵空子樹。四 實驗設備、儀器、工具與資料 微機、VC五 實驗內容（1）實驗任務1：靜態查找設計一個程序

7、，演示順序查找、折半查找方法，要求采用菜單的形式進行選擇。（2）實驗任務2：動態查找設計一個程序，實現二叉查找樹的建立、查找、刪除結點等操作。（3）實驗任務3：散列表查找（選做）針對你所在的班級的同學姓名設計一個散列表，使得平均查找長度不超過2，并完成相應的建表和查表程序。要求：散列函數采用質數除余法，沖突采用拉鏈法解決。六 實驗步驟（1）實驗預習1）預習本實驗原理中靜態查找和動態查找的實現原理。2）分析掌握教材168171頁中的算法6-16-2，為完成實驗任務1做好準備。3）分析掌握教材177184頁中的算法6-56-8，為完成實驗任務1做好準備。（2）實驗步驟1）問題分析。充分地分析和理解

8、此實驗任務，弄清要求作什么，限制條件是什么。2）系統的結構設計。按照以數據結構為中心的原則劃分模塊。最后寫出每個子程序（過程或函數）的規格說明，列出它們之間的調用關系，可以使用調用關系圖表示則更加清晰，這樣便完成了系統結構設計。3）詳細設計。詳細設計的目的是對子程序（過程或函數）的進一步求精。用 IF 、WHILE和賦值語句等，以及自然語言寫出算法的框架。利用自然語言的目的是避免陷入細節。4）編碼。在詳細設計的基礎上，對詳細設計的結果進一步求精，用C語言表示出來。5）在VC環境下調試程序。七 實驗報告要求實驗報告包含程序開發過程所形成的所有文檔資料，包括如下內容：1）需求分析及規格說明：問題描述，求解的問題是什么。2）概要設計：本程序所用的數據類型定義；主程序流程；程序模塊及相互關系。3）詳細設計：采