【自考】資料結構第六章查找，期末不掛科指南，第10篇-有解無憂

查找的一些基本概念

查找表是由同一型別的資料元素 構成的集合，它是一種以查找為“核心”，同時包括其他運算的非常靈活的資料結構，

上面概念中的集合和數學上的定義是一致的，簡單地說就是由任意一些可分辨的物件構成的整體

作為一個數學概念，集合的元素是沒有任何限制，

作為一種資料結構，查找表的邏輯結構是集合，對查找表進行的操作包括 查找表中的某一元素，讀取表中特定資料元素，插入和洗掉一個資料元素等，

若對查找表只進行前兩項操作，則稱此類查找表為 靜態查找表，
若在查找程序中，向表中插入不存在的資料元素，或者從表中洗掉某個資料元素，則稱此類查找表為動態查找表，

靜態查找表

順序表上的查找

具體的代碼就不實作了，有興趣的可以自行查閱，主要說的是概念與邏輯

對于查找運算，其基本操作是“資料元素的鍵值與給定值的比較”，所以通常用“資料元素的鍵值與給定值的比較次數”作為衡量查找演算法好壞的依據，稱上述比較次數為查找長度，但是查找長度與鍵值在順序表中的位置有關，且差別很大，例如，若鍵值在順序表的第n個位置上，則查找長度為1，而如果鍵值在順序表的第1個位置上，查找長度為n，

基于上述內容引入一個新的概念，叫做“查找成功時的平均查找長度（記作ASL）”

它的定義是這樣的：為找到資料元素在查找表中的位置，與給定值進行比較的鍵值個數的期望值，
當查找表有n個元素時，有

$$ASL=\sum_{r=1}^nP_iC_i$$

其中P_i為查找第i個元素（即給定值key與順序表中第i個元素的鍵值相等）的概率，且$\sum_{r=1}^nP_i=1$，C_i表示在找第i個元素時，與給定值已進行比較的鍵值個數，

假設順序表為（b₁，b₂，b₃）查找b₁，b₂，b₃的概率分別是0.2,0.2,0.6,則順序查找法的平均查找長度為 $0.2 * 3+0.22+0.61 = 1.6$ 即平均需要1.6 次鍵值與給定值的比較才能找到待查元素，

由于多種元素P_i值不好確定，所以通常讓P_i概率相等，即對所有的i,有 $P_i =\frac{1}{n}$，并在此假設下確定查找演算法的平均查找長度，

$$ASL=\sum_{r=1}^{nP_iC_i=\sum_{r=1}}n\frac{1}{n}*(n-i+1)=\frac{n+1}{2}$$

上述內容記住結論即可，

有序表上的查找

如果順序表中資料元素是按照鍵值大小的順序排列的，則稱為有序表，

這種存盤結構，查找運算可以用效率更高的二分查找法

直接看例題即可

現在有一個含有9個資料元素的有序表（關鍵字即為資料元素的值）
（10,13,17,20,30,55,68,89,95）用二分查找演算法查找key=17的程序

第一步，找到查找區間，合計9個資料元素，那么[1,9]就是區間
（1+9）/ 2 = 5
找到位置5的資料元素30,30>17 進入第二步

第二步，縮小查找區間，合計4個資料元素，那么[1,4]就是區間
（1+4）/ 2 = 2.5 去尾法等于2
找到位置2的資料元素13,13<17 進入第三步

第三步，縮小查找區間，那么[3,4]就是區間
（3+4） / 2 = 3.5 去尾法等于3
找到位置3的資料元素17，正好是待查元素，查找成功，回傳結果為mid=3

索引順序表上的查找

索引順序表由兩部分組成：一個索引表和一個順序表
其中順序表在組織形式上與普通的順序表完全相同，而索引表本身在組織形式上也是一個順序表，
索引表通過索引將順序表分割為若干塊，而順序表呈現出“按塊有序”的形式

若靜態查找表用索引順序表表示，則查找操作可用分塊查找來實作，也稱為 索引順序查找，
分為兩步進行：
（1）先確定待查資料元素所在的塊
（2）然后在塊內順序查找

結論：
靜態查找表有順序查找、二分查找、分塊查找
三種特點分別為：

順序查找效率最低但限制最少
二分查找效率最高，但限制最多
分塊查找介于上述二者之間

二叉排序樹

一棵二叉排序樹（又稱二叉查找樹）具備如下性質

若它的左子樹不空，則左子樹上所有結點的鍵值均小于它的根結點鍵值；
若它的右子樹不空，則右子樹上所有結點的鍵值均小于它的根結點鍵值；
根的左、右子樹也分別為二叉排序樹，

二叉排序樹的案例如下圖所示
資料結構自考

關于二叉排序樹，教材中涉及了部分代碼，分別如下

二叉排序樹上的查找
二叉排序樹上的插入

二叉排序樹的查找分析

需要記住的一些小點如下

二叉排序樹上的平均查找長度是介于O(n)和O($\log_2n$)之間，

以下兩個樹的平均查找長度分別為

資料結構自考

散串列

一些基本概念要普及一下

資料元素的鍵值和存盤位置之間建立的對應關系H成為散列函式，
用鍵值通過散列函式獲取存盤位置的這種存盤方式構造的存盤結構成為散串列，這一映射程序稱為散列
如果選定了某個散列函式H及其對應的散串列L，則對每個資料元素X，函式值H（H.Key）就是X在散串列L中的存盤位置，這個存盤位置也稱為散列地址，