数据结构与算法（C语言版）----查找_数据结构无序查找和有序查找c语言程序

查找表

一种以集合为逻辑结构，以查找为核心运算，同时包括其他运算的数据结构；

由同一类型的数据元素构成的集合。

查找表 ： 静态查找表、动态查找表

查找

给定某个值，再查找表中确定一个关键字等于给定值的记录或数据元素。

关键字（key）

数据元素中某个数据项的值；

当数据元素只有一个数据项时，其关键字就是该数据元素的值。

            Pi  查找第i个元素的概率

            Ci  查找第i个元素时同给定值k的比较次数

         

顺序查找

存储方式    影响    方法的实现

//数据元素定义
typedef struct{
   KeyType key;//关键字域
   InfoType otherinfo;//其他域
}ElemType;
//顺序表定义
typedef struct{
ElemType *R;//存储空间基地址
int length;//当前长度
}SSTable;
int Search_Seq(SSTable ST,KeyType key)
{//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0
  for（i=ST.length;i>=1;--i）
  if(ST.R[i].key==key) return i;
return 0;
}
//设置监视哨的顺序查找
int Search_Seq(SSTable ST,KeyType key)
{//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0
ST.R[0].key=key;//监视哨
for(i=ST.length;ST.R[i].key!=key;--i);//从后往前找
return i;
}

                                                     

折半查找（二分查找）

要求：线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

int Search_Bin(SSTable ST,KeyType key)
{//在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0
  low=1;high=ST.length;//置查找区间初值
   while(low<=high)
      {
         mid=(low+high/2);
         if(key==ST.R[mid].key) return mid;
//找到待查元素
        else if(key<ST.R[mid].key) high=mid-1;
//继续在前一子表继续查找
        else low=mid+1;
//继续在后一子表继续查找
}
return 0;
//表中不存在待查元素
}

   分块查找（索引顺序查找）

1.除了表本身，需建立一个索引表

2.查找过程分两步进行：确定待查元素所在的块（子表）、在块中顺序查找（顺序查找和折半查找的简单合成）

三种查找效率关系       折半查找>分块查找>顺序查找

排序与查找比较次数