L3数据结构-查找（day12）_除余的结果是什么数据结构

一、查找的原理

1.查找的概念

设记录表L=(R1 R2……Rn)，其中Ri(l≤i≤n)为记录，对给定的某个值k，在表L中确定key=k的记录的过程，称为查找。
若表L中存在一个记录Ri的key=k，记为Ri.key=k，则查找成功，返回该记录在表L中的序号i(或Ri 的地址)，否则(查找失败)返回0(或空地址Null)。

查找方法有顺序查找、折半查找、分块查找、Hash表查找等等。查找算法的优劣将影响到计算机的使用效率，应根据应用场合选择相应的查找算法。

对查找算法，主要分析其T(n)。查找过程是key的比较过程，时间主要耗费在各记录的key与给定k值的比较上。比较次数越多，算法效率越差（即T(n)量级越高），故用“比较次数”刻画算法的T(n)。

一般以“平均查找长度”来衡量T(n)。
平均查找长度ASL（Average Search Length）：对给定k，查找表L中记录比较次数的期望值(或平均值)，即：

 Pi为查找Ri的概率。等概率情况下Pi=1/n；Ci为查找Ri时key的比较次数(或查找次数)。 

顺序表，是将表中记录(R1 R2……Rn)按其序号存储于一维数组空间
记录Ri的类型描述如下：
typedef struct
 { keytype key;    //记录key//
         ……   //记录其他项//
 } Retype;

二.顺序查找

算法思路：设给定值为k，在表(R1 R2……Rn)中，从Rn开始，查找key=k的记录。
    int sqsearch(sqlist r, keytype k)  
    {   int i;
                 r.data[0].key = k;  //k存入监视哨//
          i = r.len;  //取表长//
         while(r.data[i].key != k) i--;  
         return (i);
    }
 

故ASL = O(n)。而查找失败时，查找次数等于n+1，同样为O(n)。
对查找算法，若ASL=O(n)，则效率是很低的，意味着查找某记录几乎要扫描整个表，当表长n很大时，会令人无法忍受。

 三、折半查找

算法思路
对给定值k，逐步确定待查记录所在区间，每次将搜索空间减少一半(折半)，直到查找成功或失败为止。
设两个游标low、high，分别指向当前待查找表的上界(表头)和下界(表尾)。mid指向中间元素。

算法： 

int Binsearch(sqlist r, keytype k)    //对有序表r折半查找的算法//
{  int low, hig