資料結構複習之順序表查找

順序表查找

• 基本概念
• • 查找表表示
  • 平均查找長度asl
• 順序表查找
• • 資料結構定義
  • 一般順序表的查找算法
  • • 算法分析
  • 遞增有序查找算法
  • • 算法分析
  • 二分查找，必考
  • • 思想
    • 算法實作
    • • 遞歸實作
      • 非遞歸算法
    • 算法分析
  • 執行個體
  • • 算法實作
  • 索引順序查找
  • • 索引查找表的存儲結構
    • • 索引表
    • 基本思想
    • 查找長度
  • 三種順序查找比較

基本概念

給定一個值K，在含有n個結點的表中找出關鍵字等于給定值K的結點

查找表表示

（1）動态查找表和靜态查找表

若在查找的同時對表做修改操作(如插入和删除)，則相應的表稱之為動态查找表。否則稱之為靜态查找表。

（2）内查找和外查找

若整個查找過程都在記憶體進行，則稱之為内查找；反之，若查找過程中需要通路外存，則稱之為外查找。

平均查找長度asl

查找運算的主要操作是關鍵字的比較，是以通常把查找過程中對關鍵字需要執行的平均比較次數(也稱為平均查找長度)作為衡量一個查找算法效率優劣的标準。

其中：

① n是結點的個數；

② Ci是找到第i個結點所需進行的比較次數。

③Pi是查找第i個結點的機率.一般認為是等機率的，也就是1/n

順序表查找

資料結構定義

typedef struct {
    KeyType key;
    infoType data;
} NodeType;

typedef NodeType SeqList[n + 1]; //0号單元用作哨兵
           

一般順序表的查找算法

int SeqSearch(SeqList R, KeyType k, int n)
{
    //R[0]作為哨兵,用R[0].key==k作為循環下界的終結條件
    R[0].key = k; //設定哨兵
    i = n; //從後向前掃描
    while (R[i].key != k)
        i--;
    return i; //傳回其下标,若找不到,傳回0
}
           

算法分析

• 查找成功:查找成功時的平均查找長度=（1+2+3+…+n）/n=（n+1）/2
• 查找失敗時的查找長度=（n+1）
• 如果查找成功和不成功機會相等，順序查找的平均查找長度為（（n+1）/2+（n+1））/2= 3/4（n+1）

遞增有序查找算法

int SeqSearchl(SeqList R, KeyType k, int n) //有序表的順序查找算法
{
    int i = n; //從後向前掃描,表按遞增排序
    while (R[i].key > k)
        i--; //循環結束時,要麼R[i].key=k,要麼R[i].key<k
    if (R[i].key == k)
        return i; //找到,傳回其下标
    return 0; //沒找到,傳回O
}
           

算法分析

• 查找成功、失敗

  （n+1）/2

• 成功與失敗機會均等，平均查找長度也為（n+1）/2

二分查找，必考

前提是有序表

思想

首先将待查的k值和有序表R[1…n]的中間位置mid上的記錄的關鍵字進行比較，若R[mid].key>k，則k在左子表R[1…mid-1]中，接着再在左子表中進行二分查找即可。若R[mid].key<k，則說明待查記錄在右子表R[mid+l…n]中，接着隻要在右子表中進行二分查找即可…二分查找的過程是遞歸的。

算法實作

遞歸實作

int BinSearch(SeqList R, KeyType k, int low, int high)
{
    //在區間R[low...high]内進行二分遞歸,查找關鍵字值等于k的記錄
//1ow的初始值為1,high的初始值為n
    int mid;
    if (low <= high) {
        mid = (low + high) / 2;
        if (R[mid].key == k) return mid; //查找成功,傳回其下标
        if (R[mid].key > k)
            return BinSearch(R, k, low, mid - 1) ;//在左子表中繼續查找
        else
            return BinSearch(R, k, mid + 1, high); //在右子表中繼續查找
    } else
        return 0;
}
           

非遞歸算法

int BinSearch(SeqLiSt R, KeyType k, int n) //初始化上下界
{
    int low = 1, mid, high = n;
    while (low <= high) {
        mid = (low + high) / 2;
        if (R[mid].key == k)
            return mid; //查找成功,傳回其下标
        if (R[mid].key > k)
            high = mid - 1; //修改上界
        else low = mid + 1; //修改下界
    }
    return 0; //查找失敗,傳回0值
}
           

算法分析

二分查找方法可以用一棵判定樹描述，查找任一進制素的過程對應該樹中從根結點到相應結點的一條路徑。

最短的查找長度為1，最長的查找長度為對應判定樹的深度log2n+1,下取整.

平均查找長度為 （n+1）/n log2（n+1）-1≈log2（n+1）-1。

二分查找隻适用于順序結構上的有序表，對鍊式結構無法進行二分查找。

執行個體

利用二分查找算法在有序表R中插入一個元素x，并保持表的有序性。

算法實作

void BinInsert(SeqList R, KeyType x, InfoType y, int n)
{
    int low = 1, high = n, mid, inspace, i ;
    int find = 0; //find是作為是否找到與x相等的關鍵字,先假設未發現
    while (low <= high && ! find) {
        mid = (low + high) / 2;
        if (x < R[mid].key) high = mid - 1;
        else if (x > R[mid].key) low = mid + 1;
        else find = 1;
    }
    if (find)
        inspace = mid; //找到關鍵字與x相等,mid為x的插入位置
    else
        inspace = low; //所指向的結點關鍵字正好大于x,此時low即為插入位置
    for (i = n; i >= inspace; i--)
        R[i + 1] = R[i]; //後移結點,留出插入的空位
    R[inspace].key = x; //插入結點,x是該結點的關鍵字,y是其他資料
    R[inspace].data = y;
}
           

索引順序查找

分塊查找。它是一種性能介于順序查找和二分查找之間的查找方法。

索引查找表的存儲結構

塊内無序，但塊間有序

索引表

抽取各塊中的最大關鍵字及其起始位置構成一個索引表

基本思想

（1）首先查找索引表

索引表是有序表，可采用二分查找或順序查找，以确定待查的結點在哪一塊。

（2）然後在已确定的塊中進行順序查找

由于塊内無序，隻能用順序查找

查找長度

（1）查找索引表采用二分查找時的平均查找長度

ASLblk=log2（b+1）-1+（s+1）/2≈log2（n/s+1）+s/2

（2）查找索引表采用順序查找時的平均查找長度

ASLblk＝（b+1）/2＋（s+1）/2＝（b+s）/2+1＝（n/s+s）/2+1 =（塊數+塊長）/2+1

當s取 根号n（即s=b）時， ASLblk 達到最小值 根号n+1，即當采用順序查找确定塊時，應将各塊中的結點數標明為 根号n。

三種順序查找比較

• 順序查找

  優點：算法簡單，對表的存儲結構無任何要求。

  缺點：查找效率低，查找成功的平均查找長度為（n+1)／2，查找失敗的查找長度為（n+1）。

• 二分查找

  優點：二分查找的速度快，效率高，查找成功的平均查找長度約為log2(n+1)-l。

  缺點：要求表以順序存儲表示并且是按關鍵字有序，使用高效率的排序方法也要花費O(nlog2n)的時間。另外，當對表結點進行插入或删除時，需要移動大量的元素，是以二分查找适用于表不易變動且又經常查找的情況。

• 分塊查找，索引

  優點：在表中插入或删除一個記錄時，隻要找到該記錄所屬的塊，就可以在該塊内進行插入或删除運算。因為塊内記錄是無序的，是以插入或删除比較容易，無需移動大量記錄。

  缺點：是需要增加一個輔助數組的存儲空間和将初始表塊排序的運算，它也不适宜用鍊式存儲結構。

  此外，順序查找、二分查找和分塊查找三種查找算法的時間複雜度分别為：O(n)、O(log2n)和O(根号n )。