| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 467 人关注过本帖
标题:动态折半查找 (
只看楼主 加入收藏
wbfiow
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2011-5-7
结帖率:50%
收藏
已结贴  问题点数:10 回复次数:2 
动态折半查找 (
动态折半查找

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

题目描述:


我用的是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 编辑 ]
搜索更多相关主题的帖子: 动态 记录 
2011-05-09 15:11
wbfiow
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2011-5-7
收藏
得分:0 
大家帮帮忙哈。。
2011-05-10 22:24
lly10120303
Rank: 2
等 级:论坛游民
帖 子:11
专家分:12
注 册:2011-3-30
收藏
得分:10 
#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;
    }
}
2011-05-11 11:47
快速回复:动态折半查找 (
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.091660 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved