《数据结构查找 顺序查找和折半查找 》

//顺序查找

//思路:从表中最后一个记录开始，逐个进行记录的关键字和

//给定值的比较，若某个记录的关键字和给定值比较相等，则

//返回返回记录所在的位置，或查找完所有记录后还没有发现

//符合的记录，则查找失败。

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

#include <time.h>

#define N 10

typedef int DataType;//定义比较的元素类型 

//静态查找表的顺序存储结构

typedef struct{

    DataType * data;//数据元素存储空间基址，按实际长度分配，0号单元留空 

                    //建表时按实际长度分配，0 号单元留空 

    int length;//表长度 

}SSTable;

//创建一个静态表，内容为20以内的随机数

void createST(SSTable* ST,int n){

    int i;

    time_t t;

    if(ST!=NULL){

        ST->data=(DataType*)calloc(n+1,sizeof(DataType));

        if(ST->data!=NULL){

            srand((unsigned) time(&t)); 

            for(i=1;i<=n;i++){

                ST->data[i]=rand()  ;//产生20以内的随机数 

            } 

            ST->length=n;

        }

    }

}

//创建一个静态表，内容按从小到大排列，以便折半查找 

void createST_binary(SSTable* ST,int n){

    int i,j=0;

    time_t t;

    if(ST!=NULL){

        ST->data=(DataType*)calloc(n+1,sizeof(DataType));

        if(ST->data!=NULL){

            for(i=1;i<=n;i++){

                ST->data[i]=j;

                j+=4;

            } 

            ST->length=n;

        }

    }

}

//打印出静态表的内容 

void print_SSTable(SSTable* ST){

    int i,n=ST->length;

    if(ST!=NULL){

        for(i=1;i<=n;i++){

            printf("%d ",ST->data[i]);

        }

        printf("\n"); 

    }

}

//顺序查找(Sequential Search)

//思路:从表中最后一个记录开始，逐个进行记录的关键字和

//给定值的比较，若某个记录的关键字和给定值比较相等，则

//返回返回记录所在的位置，或查找完所有记录后还没有发现

//符合的记录，则查找失败。

//查找成功：返回记录所在位置

//查找失败：返回0 

int search_seq(SSTable ST,DataType key){

    int i;

    if(ST.data==NULL)return 0;

    ST.data[0]=key;//设置监视哨。目的在于免去查找过程中每一步都要检测整

                       //个表是否查找完毕，是一个很有效的程序设计技巧 。监视

                       //哨也可以设在高下标处。 

    for(i=ST.length;ST.data[i]!=key;i--);

    return i; 

}

//折半查找(Binary Search)

//当记录的key按关系有序时可以使用折半查找 

//思路：对于给定key值，逐步确定待查记录所在区间，每次将搜索空间减少一半（折半）， 

//直到查找成功或失败为止。 

int search_binary(SSTable ST,DataType key){

    int low,high,mid;

    low=1;

    high=ST.length;

    while(low<=high){//当表空间存在时

        mid=(low+high)/2;

        if(ST.data[mid]==key){

            return mid;//查找成功，返回mid 

        }

        if(key<ST.data[mid]){

            high=mid-1;//继续在前半区间查找 

        }else{

            low=mid+1;//继续在后半区间查找 

        } 

    }

    return 0;//查找失败 

}

//分块查找（只记录思想） 

//分块查找中，设记录表长为n，将表的n个记录分成b=n/s个块，每个s个记录

//最后一个记录数可以少于s个，且表分块有序，即后一个块的所有key值大于

//前一个块的所有key值 

//每块对应一个索引项，索引项记录了该块记录的最大key值和该块第一记录的指针（或序号） 

//算法：

//（1）由索引表确定待查找记录所在的块；

//（2）在块内顺序查找。

int main(){

    int n=20;//在20个数中查找,方便看结果，不要设置得太大 

    SSTable ST,ST_binary;//分别用于顺序查找和折半查找的静态表 

    index indtb[n+1];//索引表，用于分块查找 

    createST(&ST,n);//创建一个随机静态表 

    createST_binary(&ST_binary,n);//创建一个从小到大顺序排列的静态表 

    

    

    //采用顺序查找 

    printf("原始数据:"); 

    print_SSTable(&ST);

    printf("顺序查找5的结果:%d\n",search_seq(ST,5));

    printf("顺序查找10的结果:%d\n",search_seq(ST,10));

    printf("顺序查找12的结果:%d\n",search_seq(ST,12));

    printf("顺序查找15的结果:%d\n",search_seq(ST,15));

    printf("顺序查找20的结果:%d\n",search_seq(ST,20));

    

    printf("--------------------------------------------\n");

    //采用折半查找 

    printf("原始数据:"); 

    print_SSTable(&ST_binary);

    printf("折半查找5的结果:%d\n",search_binary(ST_binary,5));

    printf("折半查找10的结果:%d\n",search_binary(ST_binary,10));

    printf("折半查找12的结果:%d\n",search_binary(ST_binary,12));

    printf("折半查找15的结果:%d\n",search_binary(ST_binary,15));

    printf("折半查找20的结果:%d\n",search_binary(ST_binary,20));

    

    system("pause");//暂停一下，看看结果 

    free(ST.data);//不要忘了释放堆空间 

    return 0;

}