严蔚敏版数据结构课后习题答案-完整版 下载本文

内容发布更新时间 : 2024/12/23 11:38:03星期一 下面是文章的全部内容请认真阅读。

if(i<0||j<0||len<0) return INFEASIBLE; // 在la表中查找第i个结点 p=la;

while(p&&k

if(!p)return INFEASIBLE; // 在la表中查找第i+len-1个结点 q=p; k=1; while(q&&k

if(!q)return INFEASIBLE;

// 完成删除,注意,i=1的情况需要特殊处理 if(!prev) la=q->next; else prev->next=q->next;

// 将从la中删除的结点插入到lb中 if(j=1){

q->next=lb; q=p->next; k++; prev=p; p=p->next; k++;

}

}

lb=p;

else{ }

return OK;

s=lb; k=1; while(s&&k

if(!s)return INFEASIBLE; q->next=s->next; s->next=p; //完成插入

s=s->next; k++;

2.17 试写一算法,在无头结点的动态单链表上实现线性表操作Insert(L,i,b),并和在带头结点的动态单链表上实现相同操作的算法进行比较。

2.18试写一算法,实现线性表操作Delete(L,i),并和在带头结点的动态单链表上实现相同操作的算法进行比较。

2.19 已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写一高效的算法,删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素),同时释放被删结点空间,并分析你的

算法的时间复杂度(注意,mink和maxk是给定的两个参变量,它们的值可以和表中的元素相同,也可以不同)。

解:

Status ListDelete_L(LinkList &L,ElemType mink,ElemType maxk) {

LinkList p,q,prev=NULL; if(mink>maxk)return ERROR; p=L; prev=p; p=p->next;

while(p&&p->data

if(p->data<=mink){ } else{ }

prev->next=p->next; q=p; p=p->next; free(q); prev=p; p=p->next;

}

}

return OK;

2.20 同2.19题条件,试写一高效的算法,删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同),同时释放被删结点空间,并分析你的算法的时间复杂度。

解:

void ListDelete_LSameNode(LinkList &L) { LinkList p,q,prev; p=L; prev=p; p=p->next; while(p){ prev=p; p=p->next;

if(p&&p->data==prev->data){ prev->next=p->next; q=p; p=p->next; free(q);

}

}

}

2.21 试写一算法,实现顺序表的就地逆置,即利用原表的存储空间将线性表?a1,?,an?逆置为?an,?,a1?。

解:

// 顺序表的逆置

Status ListOppose_Sq(SqList &L) { }

2.22 试写一算法,对单链表实现就地逆置。

解:

// 带头结点的单链表的逆置 Status ListOppose_L(LinkList &L) {

int i; ElemType x;

for(i=0;i

return OK;

x=L.elem[i];

L.elem[i]=L.elem[L.length-1-i]; L.elem[L.length-1-i]=x;