数据结构习题集答案(C语言严版)

Status DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len) { } 2.19 解：

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

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

LinkList p,q,s,prev=NULL; int k=1;

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){ } else{ }

return OK;

s=lb; }

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

k=1;

while(s&&k

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

}

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

解：

void ListDelete_LSameNode(LinkList &L) { } 2.21

解：

// 顺序表的逆置

Status ListOppose_Sq(SqList &L) {

int i; ElemType x;

for(i=0;i

x=L.elem[i];

L.elem[i]=L.elem[L.length-1-i]; 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);

prev=p; p=p->next;

while(p&&p->data

return OK;

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

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

}

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

解：

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

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

Status ListMerge_L(LinkList &A,LinkList &B,LinkList &C) { } 2.24 解：

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

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

LinkList pa,pb,qa,qb; pa=A;

LinkList pa,pb,qa,qb; pa=A->next; pb=B->next; C=A;

while(pa&&pb){ }

if(!pa)qb->next=pb; pb=B; free(pb); return OK;

qa=pa;

qb=pb;

pa=pa->next; pb=pb->next; qb->next=qa->next; qa->next=qb; 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; }

return OK;

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

} 2.25解：

// 将A、B求交后的结果放在C表中

Status ListCross_Sq(SqList &A,SqList &B,SqList &C) {

int i=0,j=0,k=0;

while(i

if(A.elem[i]

if(A.elem[i]>B.elem[j]) j++;

pb=B; qa=pa; qb=pb;

// 保存pa的前驱指针 // 保存pb的前驱指针

pa=pa->next; pb=pb->next; A->next=NULL; C=A;

while(pa&&pb){ }

while(pa){ }

while(pb){ } pb=B; free(pb); return OK;

qb=pb; pb=pb->next; qb->next=A->next; A->next=qb; qa=pa; pa=pa->next; qa->next=A->next; A->next=qa;

if(pa->datadata){ } else{ }

qb=pb; pb=pb->next;

qb->next=A->next; //将当前最小结点插入A表表头 A->next=qb; qa=pa; pa=pa->next;

qa->next=A->next; //将当前最小结点插入A表表头 A->next=qa;