发布时间 : 2024/5/17 16:07:29 星期五 文章(完整版)数据结构-习题集答案-(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(knext=p; return OK;

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++;