折半查找法

算法 | 2008-06-27 00:41:16 | 阅读 4888 次 | 评论(0)
// cfree 2008.6.10
#include "iostream"
#include "math.h"
using namespace std;
#define MAXSIZE 200
typedef int KeyType;
typedef int DataType;
typedef struct
{
    KeyType key;
    DataType data;
}NodeType;
typedef NodeType SeqList[MAXSIZE];


void SeqSearch(SeqList S,int n,KeyType k)
{
    int i;
    
    for(i=0;i<n&&S[i].key!=k;i++);
    if(i&lt;n)
    {
        cout&lt;&lt;"该数在第 "&lt;&lt;i+1&lt;&lt;" 位"&lt;&lt;endl;
        cout&lt;&lt;"顺序查找次数为"&lt;&lt;i&lt;&lt;endl;
    }
    else
    {
        cout&lt;&lt;"The number is not exist!SeqSearch has searched "&lt;&lt;i&lt;&lt;" times"&lt;&lt;endl;
    }

}

void BinSearch(SeqList S,int n,KeyType k)
{
    int low=0,high=n-1,mid,num=0;
    while(low&lt;=high)
    {
        mid=(low+high)/2;
        num++;
        if(S[mid].key==k)
        {
            cout&lt;&lt;"折半查找次数为 "&lt;&lt;num&lt;&lt;endl;
            exit(0);
        }
            
        else if(S[mid].key&lt;k)
            low=mid+1;
        else
            high=mid-1;
    }
    cout&lt;&lt;"The number is not exist!BinSearch has searched "&lt;&lt;num&lt;&lt;" times"&lt;&lt;endl;
}

void AreaSearch(SeqList S,int n,KeyType k)
{
    int i,j,length=(int)sqrt(n);//分块的块长
    bool check=false;//查到与否的标志
    int b=n%length==0?0:1;
    int num=n/length+b;//分的组数
    for(i=0;i&lt;num;i++)
    {
        int NUM=(i*num+num)&lt;=n?(i*num+num):n;
        if(k&lt;S[NUM].key)
        {
           for(j=i*num;j&lt;(NUM)&&k!=S[j].key;j++);
           if(j&lt;(NUM))
           {
               cout&lt;&lt;"分块查找次数为 "&lt;&lt;(i+j-i*num+1)&lt;&lt;endl;
               check=true;
               break;
           }
           else
           {
               cout&lt;&lt;"The number is not exist!AreaSearch has searched "&lt;&lt;(i+j-i*num+1)&lt;&lt;" times"&lt;&lt;endl;
               check=true;
               break;
           }
        }
        else if(k==S[NUM].key)
        {
            cout&lt;&lt;"分块查找次数为 "&lt;&lt;i+1&lt;&lt;endl;
            check=true;
            break;
        }
    }
    if(!check)
        cout&lt;&lt;"没有找到!分块查找次数为 "&lt;&lt;i+1&lt;&lt;endl;    
}

void Init(SeqList &Q,int &m,int &n)
{
    
    while(m>MAXSIZE||m<0)
    {
        cout&lt;&lt;"请输入数组的长度(不要超过"&lt;&lt;MAXSIZE&lt;&lt;"):";
        cin>&gt;m;
    }
    cout<&lt;endl;
    for(unsigned i=0;i&lt;m;i++)
    {
        Q[i].key=i;
        cout&lt;&lt;Q[i].key&lt;&lt;" ";
        if((i+1)%10==0)
            cout&lt;&lt;endl;
    }
    cout&lt;&lt;endl&lt;&lt;"请输要查找的数据:";
    cin>&gt;n;
}

void main()
{
    SeqList Q;
    int n;//number you want to find
    int m;//length of array
    Init(Q,m,n);
    SeqSearch(Q,m,n);
    AreaSearch(Q,m,n);
    BinSearch(Q,m,n);
}
文章评论,共0条
游客请输入验证码
浏览1861232次