发布时间 : 星期日 文章(完整版)数据结构-习题集答案-(C语言版严蔚敏)更新完毕开始阅读9eb8c96b0b12a21614791711cc7931b764ce7b60
}
void AA(LNode *pa, LNode *pb) { }
解:(1) 如果L的长度不小于2,将L的首元结点变成尾元结点。
(2) 将单循环链表拆成两个单循环链表。
2.10 指出以下算法中的错误和低效之处,并将它改写为一个既正确又高效的算法。
Status DeleteK(SqList &a,int i,int k) {
//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素 if(i<1||k<0||i+k>a.length) return INFEASIBLE;//参数不合法 else {
for(count=1;count } 解: Status DeleteK(SqList &a,int i,int k) { } 2.11 设顺序表va中的数据元素递增有序。试写一算法,将x插入到顺序表的适当位置上,以保持该表的有序性。 解: Status InsertOrderList(SqList &va,ElemType x) { //在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法 int i; if(va.length==va.listsize)return(OVERFLOW); for(i=va.length;i>0,x va.elem[i]=va.elem[i-1]; va.elem[i]=x; //从顺序存储结构的线性表a中删除第i个元素起的k个元素 //注意i的编号从0开始 int j; if(i<0||i>a.length-1||k<0||k>a.length-i) return INFEASIBLE; for(j=0;j<=k;j++) a.elem[j+i]=a.elem[j+i+k]; a.length=a.length-k; return OK; } //删除第一个元素 for(j=a.length;j>=i+1;j--) a.elem[j-i]=a.elem[j]; a.length--; //pa和pb分别指向单循环链表中的两个结点 BB(pa,pb); BB(pb,pa); return OK; } 2.12 设 va.length++; return OK; A??a1,?,am?和B??b1,?,bn?均为顺序表,A?和B?分别为A和B中除去最大共同前 A??B??空表,则A?B;若A?=空表,而B??空表,或者两者均不为空表,且A?的首元小于B?的首元,则A?B;否则A?B。试写一个比较A,B大小的算法。 缀后的子表。若 解: Status CompareOrderList(SqList &A,SqList &B) { } 2.13 试写一算法在带头结点的单链表结构上实现线性表操作Locate(L,x); 解: int LocateElem_L(LinkList &L,ElemType x) { } 2.14 试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。 解: //返回单链表的长度 int ListLength_L(LinkList &L) { int i=0; LinkList p=L; if(p) p=p-next; while(p){ p=p->next; int i=0; LinkList p=L; while(p&&p->data!=x){ } if(!p) return 0; else return i; p=p->next; i++; int i,k,j; k=A.length>B.length?A.length:B.length; for(i=0;i if(A.length>k) j=1; if(B.length>k) j=-1; if(A.length==B.length) j=0; return j; if(A.elem[i]>B.elem[i]) j=1; if(A.elem[i] } 2.15 已知指针ha和hb分别指向两个单链表的头结点,并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起,假设指针hc指向连接后的链表的头结点,并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。 解: void MergeList_L(LinkList &ha,LinkList &hb,LinkList &hc) { } 2.16 已知指针la和lb分别指向两个无头结点单链表中的首元结点。下列算法是从表la中删除自第i个元素起共len个元素后,将它们插入到表lb中第i个元素之前。试问此算法是否正确?若有错,请改正之。 Status DeleteAndInsertSub(LinkedList la,LinkedList lb,int i,int j,int len) { } 解: Status DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len) if(i<0||j<0||len<0) return INFEASIBLE; p=la; q=p; while(k<=len){ q=q->next; s=lb; k=1; while(k s=s->next; k++; } q->next=s->next; k++; } k=1; p=p->next; k++; } while(k while(pa->next&&pb->next){ } if(!pa->next){ } else{ } hc=ha; while(pa->next) pa=pa->next; pa->next=hb->next; hc=hb; while(pb->next) pb=pb->next; pb->next=ha->next; pa=pa->next; pb=pb->next; } return i; i++; { } 2.17 试写一算法,在无头结点的动态单链表上实现线性表操作Insert(L,i,b),并和在带头结点的动态单链表上实现相同操作的算法进行比较。 2.18试写一算法,实现线性表操作Delete(L,i),并和在带头结点的动态单链表上实现相同操作的算法进行比较。 2.19 已知线性表中的元素以值递增有序排列,并以单链表作存储结构。试写一高效的算法,删除表中所有 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++;