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

算法的时间复杂度（注意，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;

}

LinkList p,q; p=L; p=p->next; L->next=NULL; while(p){ }

return OK;

q=p; p=p->next; q->next=L->next; L->next=q;

2.23 设线性表A??a1,a2,?,am?，B??b1,b2,?,bn?，试写一个按下列规则合并A，B为线性表C的算法，即使得

C??a1,b1,?,am,bm,bm?1,?,bn? 当m?n时； C??a1,b1,?,an,bn,an?1,?,am? 当m?n时。

线性表A，B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。

解：

// 将合并后的结果放在C表中，并删除B表

Status ListMerge_L(LinkList &A,LinkList &B,LinkList &C) {