顺序表的静态查找

定义被查找的顺序表类型定义如下：

#define MAXLEN
typedef struct{
    KeyType key;
    InfoTye data;
}SeqList;

1.简单顺序查找

顺序查找算法的时间复杂度为O(n)。

 

typedef int KeyType;
int SeqSearch(SeqList A[],int n,KeyType k)
{
    int i;
    int find = 0;
    for(i=0;i<n;i )
    {
        if(A[i].key == k)
        {
            find =1;
            break;
        }
    }
    return (find?i:-1);
}

 

优点：算法简单且适应面广，对表的结构无任何要求，无论是用顺序表还是用链表存放记录，也无论记录是否按关键字有序均可使用。

缺点：平均查找长度较大，当n很多大时，查找效率较低。因此，当n较大时不宜采用顺序查找。

2.二分查找

如果查找表已经按关键字排列有序，则可采用二分查找。

 

int BinSearch(SeqList A[],int n, KeyType k)
{
    int low=0,high =n-1,mid;
    while(low<=high){
        mid=(low+high)/2;
        if(A[i].key==k)return mid;
        else if (A[i].key>k) high =mid-1;
        else low = mid+1;
    }
    return -1;
}

 

二分查找算法比顺序查找算法的比较次数少，查找速度快。虽然二分查找的效率高，但是要先将表按关键字排序。而排序本身是一种很费时的运算，即使采用高效率的排序方法也要花费O(nlogn)的时间。另外，二分查找只适用顺序存储结构，不适用与链表结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的记录。因此，二分查找特别适用于那种一经建立就很少改动，而又经常需要查找的线性表。

3.分块查找

分块查找又称索引顺序查找，是顺序查找法和二分查找法的一种结合。其基本思想是：首先将表长为n的线性表分成b块，前b-1块记录个数为s=n/b，第b块的记录个数小于等于s。在每一块中，结点的存放不一定有序，但块与块之间必须是有序的，假定按结点的关键字值递增有序，即后一个块中所有记录的关键字值都应比前一个块中所有记录的关键字值大。为实现分块搜索，还需建立一个索引表。索引表的每个元素对应一个块，其中包括该块内最大关键字值和块中第一个记录位置的地址指针。

索引表结点的数据类型定义如下：

 

#define MaxIndex
typedef struct{
    KeyType key;
    int link;
}IdxType;

查找过程分为两步：首先查找索引表。因为索引表是有序表，所以可以采用二分查找或顺序查找，以确定给定值所在的块。因为块中的记录可以是任意排列的，所以再在已确定的块中进行顺序查找。

分块算法如下：

 

int IdxSearch(SeqList A[],IdxType index[],int b,KeyType k,int n)
{
    int low=0,high=b-1,mid,i;
    int s=n/b;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(index[mid].key<k)low=mid+1;
        else high=mid-1;
    }
    if(low<b)
    {
        for(i=index[low].link;i<=index[low].link+s-1 && i<n;i++)
        {
            if(A[i].key==k)return i;
        }
        return -1;
    }
    return -1;
}