动态折半查找

--------------------------------------------------------------------------------

题目描述:


我用的是vc6.0,希望到时可以运行，用c或者c++,
对整型有序关键码序列进行折半查找，待排序序列以数组存储。如果找到待查记录，返回找到的位置下标，并删除该关键码记录；如果没找到待查记录，返回0，并将待查记录插入到适当位置，即该查找属于动态查找。输出查找过程中每一轮的low，mid，high 值，以及与给定值相比较的关键码值，并输出最后找到的位置，及变化后的数组。

注意：该数组为整型，数组中关键码存储位置为r[1]~r[n]，r[0]留作它用，且关键码个数大于4.


--------------------------------------------------------------------------------

输入样例:


10
1 2 5 8 10 17 22 23 68 87
5
11
23
--------------------------------------------------------------------------------

输出样例:


1 5 10 10
1 2 4 2
3
1 2 8 10 17 22 23 68 87
1 5 9 17
1 2 4 2
3 3 4 8
4 4 4 10
0
1 2 8 10 11 17 22 23 68 87
1 5 10 11
8
1 2 8 10 11 17 22 68 87
--------------------------------------------------------------------------------

输入描述:


第一行输入数组中记录个数n
第二行输入n个有序的整型关键码，以空格隔开
接下来输入三个待查关键码，每个关键码占一行


--------------------------------------------------------------------------------

输出描述:


对于每个关键码，分别输出：
找到给定值之前的每一轮的low，mid，high及相比较的待查找序列中的关键码，以空格隔开
接下来一行输出查找到的位置
接下来一行输出变化后的待查找序列


--------------------------------------------------------------------------------

程序限制:

程序可使用最大内存:10000K
程序运行最长耗时:10000MS(毫秒)
--------------------------------------------------------------------------------



[ 本帖最后由 wbfiow 于 2011-5-9 15:18 编辑 ]

大家帮帮忙哈。。

#include<iostream.h>
int mid(int h,int l)//计算mid，
{
    int mid;
    mid=(h-l)/2+l;
    return mid;
}
void main()
{
    int n,c[3],i,j,l,m,h,y,s;
    int *r;
    cout<<"数组的大小"<<endl;
    cin>>n;
    r=new int[n];
    cout<<"输入数组的数据"<<endl;
    for(i=0;i<n;i++)
    {
        cin>>j;
        r[i]=j;
    }
    cout<<"输入待查的关键数"<<endl;
    for(i=0;i<3;i++)
    {
        cin>>j;
        c[i]=j;
    }
    for(s=0;s<3;s++)
    {
        h=n;l=1;
        while(h!=l)
        {
            m=mid(h,l);
            j=m-1;//中间数对应数据的下标是减一
            y=r[j];
            cout<<1<<" "<<m<<" "<<n<<" "<<y<<endl;
            if(c[s]<y) //如果小于，往左找，则把m-1复给h；l不变   
            {
                h=m-1;
                m=mid(h,l);
                j=m-1;
                y=r[j];
                cout<<l<<" "<<m<<" "<<h<<" "<<y<<endl;
            }
            if(c[s]>y)//如果大于，往右找，则把m+1复给l，h不变
            {
                l=m+1;
                h=h;
                m=mid(h,l);
                j=m-1;
                y=r[j];
                cout<<l<<" "<<m<<" "<<h<<" "<<y<<endl;
            }
            if(c[s]==y) //相等，则找到，把相应的一位删掉，即把数组的j位以后向左移一位
            {
                cout<<j+1<<endl;
                for(i=j;i<n-1;i++) r[i]=r[i+1];
                n--;
                break;
            }
        }
        if((h==l))//最后只剩下一位时，判断是否相等，若不相等，则没又找到，返回0，并且将此数加入相应位
        {
        
            if(c[s]==r[l-1])
            {
                j=l-1;
                cout<<l<<" "<<l<<" "<<l<<" "<<r[l-1]<<endl;
                cout<<j+1<<endl;
                for(i=j;i<n-1;i++) r[i]=r[i+1];
                n--;
            }
            else
            {
                cout<<0<<endl;
                n++;
                for(i=n-1;l-1<i;i--)
                {
                    r[i]=r[i-1];
                }
            }
        }
        for(i=0;i<n;i++)//输出变化后的数组
        {
            cout<<r[i]<<" ";
        }
        cout<<endl;
    }
}