A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

                                                                      《顺序查找与折半查找小总结》

一、           顺序查找

1、  基本思想:从表的一端开始,顺序扫描线性表,依次将扫描到的结点关键宇和给定值K相比较。

       若当前扫描到的结点关键字与K相等,则查找成功;若扫描结束后,仍未找到关键字等于K的结点,则查找失败。


2、  存储结构要求既适用于线性表的顺序存储结构,也适用于线性表的链式存储结构(使用单链表

         作存储结构时,扫描必须从第一个结点开始)


3、  基于顺序结构的顺序查找算法


(1)
//类型说明

typedef struct{
    KeyType key;
    InfoType otherinfo; //此类型依赖于应用
}NodeType;
typedef NodeType SeqList[n+1]; //0号单元用作哨兵

(2)  //具体算法
int SeqSearch(Seqlist R,KeyType K)
{ //在顺序表R[1..n]中顺序查找关键字为K的结点,
    //成功时返回找到的结点位置,失败时返回0
    int i;
    R[0].key=K; //设置哨兵
    for(i=n;R.key!=K;i--); //从表后往前找
        return i; //若i为0,表示查找失败,否则R是要找的结点

        } //SeqSearch


4、  优点:算法简单,且对表的结构无任何要求,无论是用向量还是用链表来存放结点,

         也无论结点之间是否按关键字有序,它都同样适用。


5、  缺点:查找效率低,因此,当n较大时不宜采用顺序查找。


二、            折半查找

折半查找,又称二分查找,是种效率较高的查找算法。


1、要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构。不妨设有序表是递增有序的。


2、基本思想:


(1)首先确定该区间的中点位置:mid = (low + high) / 2


(2)然后将待查的K值与R[mid].key比较:若相等,则查找成功并返回此位置,否则须确定新的查找区间,

         继续二分查找,具体方法如下:


     ①若R[mid].key>K,则由表的有序性可知R[mid..n].keys  均大于K,因此若表中存在关键字等于K的结点,

         则该结点必定是在位置mid左边的子表R[1..mid-1]中,故新的查找区间是左子表R[1..mid-1]。


     ②类似地,若R[mid].key<k,则要查找的K必在mid的右子表R[mid+1..n]中,即新的查找区间是右子表R[mid+1..n]。

         下一次查找是针对新的查找区间进行的。</k


     因此,从初始的查找区间R[1..n]开始,每经过一次与当前查找区间的中点位置上的结点关键字的比较,

        就可确定查找是否成功,不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点

         


3、算法:


    int BinSearch(SeqList R,KeyType K)

    { //在有序表R[1..n]中进行二分查找,成功时返回结点的位置,失败时返回零
        int low=1,high=n,mid; //置当前查找区间上、下界的初值
        while(low<=high){ //当前查找区间R[low..high]非空
            mid=(low+high)/2;
            if(R[mid].key==K) return mid; //查找成功返回
                if(R[mid].key>K)
                    high=mid-1; //继续在R[low..mid-1]中查找
                else
                    low=mid+1; //继续在R[mid+1..high]中查找
                    }
        return 0; //当low>high时表示查找区间为空,查找失败
    } //BinSeareh




0 个回复

您需要登录后才可以回帖 登录 | 加入黑马