//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;
}
评论