登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

秒大刀 博客

好好学习 天天向上

 
 
 

日志

 
 
 
 

二分法插入  

2006-02-23 21:59:35|  分类: C/C++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

//2_11
/*
问题描述:
设顺序表va中的数据元素递增有序。试写一个算法, 将x插入到顺序表的适当位置上,
以保持该表的有序性。
*/
//作者:杨明哲
//完成日期:2005/3/7
//#include<cstdlib>
#include<iostream>

using namespace std;

typedef int ElemType;

bool Insert(ElemType*& pva,const unsigned va_len,const ElemType x)
{
int i(0),j(va_len-1),k;
if(x<pva[0])
k=0;
else if(x>pva[j])
k=j+1;
else//得到应该插入的位置,存入k
{
do
{
k=(i+j)/2;
#ifdef _DEBUG
cout<<"i="<<i<<" j="<<j<<" k="<<k<<endl;
#endif
if(x==pva[k])
break;
else if(x>pva[k])
i=k+1;
else//x<pva[k]
j=k;
}while(!(pva[k]<=x&&pva[k+1]>=x));
++k;
}
//////////////////////
#ifdef _DEBUG
cout<<"k= "<<k<<" x= "<<x<<endl;
for(int jj=0;jj<va_len;++jj)
{
cout<<pva[jj]<<' ';
}
cout<<endl<<"-----------------"<<endl;
for(jj=0;jj<=va_len;++jj)
cout<<jj<<' ';
cout<<endl<<"-----------------"<<endl;
#endif
ElemType* newp=new ElemType[va_len+1];
if(newp==NULL)
return false;
//拷贝k以前的内容到新位置
for(i=0;i<k;++i)
{
newp[i]=pva[i];
}
newp[i++]=x;//插入k
//将剩余内容写在k后面
for(;i<va_len+1;++i)
{
newp[i]=pva[i-1];
}
delete []pva;//const pointer can't be distructer.
pva=newp;//导出指针
#ifdef _DEBUG
for(jj=0;jj<va_len+1;++jj)
{
cout<<pva[jj]<<' ';
}
cout<<endl;
#endif
return true;
}
//以下为测试代码
int main()
{

int va_len=5;
int *pva=new int [va_len];
int x;
while(1)
{
pva[0]=2;
pva[1]=4;
pva[2]=6;
pva[3]=8;
pva[4]=10;

cout<<"Input x "<<endl;
cin>>x;
if(Insert(pva,va_len,x)==false)
{
cout<<"存贮分配失败,插入被取消"<<endl;
cin.get();
}
for(int i(0);i<va_len+1;++i)
{
cout<<pva[i]<<' ';
}
cout<<endl;
char c;
cout<<"Continue?"<<std::flush; 
cin>>c;
if(c=='n'||c=='N')
break;
}
delete pva;
return 0;
}

  评论这张
 
阅读(680)| 评论(0)

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018