指出以下算法中的错误和低效之处并将它改写为一个既正确又高效的算法
Status DeleteK(SqList &aint iint k)
{
//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素
if(i<||k<||i+k>alength) return INFEASIBLE;//参数不合法
else {
for(count=;count<k;count++){
//删除第一个元素
for(j=alength;j>=i+;j) aelem[ji]=aelem[j];
alength;
}
return OK;
}
解
Status DeleteK(SqList &aint iint k)
{
//从顺序存储结构的线性表a中删除第i个元素起的k个元素
//注意i的编号从开始
int j;
if(i<||i>alength||k<||k>alengthi) return INFEASIBLE;
for(j=;j<=k;j++)
aelem[j+i]=aelem[j+i+k];
alength=alengthk;
return OK;
}
设顺序表va中的数据元素递增有序试写一算法将x插入到顺序表的适当位置上以保持该表的有序性
解
Status InsertOrderList(SqList &vaElemType x)
{
//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法
int i;
if(valength==valistsize)return(OVERFLOW);
for(i=valength;i>x<vaelem[i];i)
vaelem[i]=vaelem[i];
vaelem[i]=x;
valength++;
return OK;
}
试写一算法在带头结点的单链表结构上实现线性表操作Locate(Lx);
解
int LocateElem_L(LinkList &LElemType x)
{
int i=;
LinkList p=L;
while(p&&p>data!=x){
p=p>next;
i++;
}
if(!p) return ;
else return i;
}
试写一算法在带头结点的单链表结构上实现线性表操作Length(L)
解
//返回单链表的长度
int ListLength_L(LinkList &L)
{
int i=;
LinkList p=L;
if(p) p=pnext;
while(p){
p=p>next;
i++;
}
return i;
}
已知指针ha和hb分别指向两个单链表的头结点并且已知两个链表的长度分别为m和n试写一算法将这两个链表连接在一起假设指针hc指向连接后的链表的头结点并要求算法以尽可能短的时间完成连接运算请分析你的算法的时间复杂度
解
void MergeList_L(LinkList &haLinkList &hbLinkList &hc)
{
LinkList papb;
pa=ha;
pb=hb;
while(pa>next&&pb>next){
pa=pa>next;
pb=pb>next;
}
if(!pa>next){
hc=hb;
while(pb>next) pb=pb>next;
pb>next=ha>next;
}
else{
hc=ha;
while(pa>next) pa=pa>next;
pa>next=hb>next;
}
}
