第2章布置作业的参考答案

《第2章布置作业的参考答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章线性表布置的作业共6题：基础知识题：2.8算法设计题：2.102.212.222.342.352.8已知P结点是双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。a．在P结点后插入S结点的语句序列是-----------76123。b．在P结点前插入S结点的语句序列是-----------58134。c．删除P结点的直接后继结点的语句序列是----------1511118。d．删除P结点的直接前驱结点的语句序列是----------1621018。e．删除P结点的语句序列是------------91417。(1)P->next=P->next->

2、next;(10)P->prior->next=P;(2)P->prior=P->prior->prior;(11)P->next->prior=P;(3)P->next=S;(12)P->next->prior=S;(4)P->prior=S;(13)P->prior->next=S;(5)S->next=P;(14)P->next->prior=P->prior(6)S->prior=P;(15)Q=P->next;(7)S->next=P->next;(16)Q=P->prior;(8)S->prior=P->prior;(17)free(P);(9)P->p

3、rior->next=p->next;(18)free(Q);解答：a.（12）（7）（3）（6）3必须在12和7的后面，其余的顺序可变b.（13）（8）（4）（5）同上c.（15）（1）（11）（18）不可变d.（16）（2）（10）（18）不可变e.（9）（14）（17）62.10指出以下算法中的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。StatusDeleteK(SqList&a,inti,intk){//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素if(i<1

4、

5、k<0

6、

7、i+k>a.length)returnINFEASI

8、BLE;//参数不合法else{for(count=1;count=i+1;j--)a.elem[j-1]=a.elem[j];a.length--;}returnOK;}//DeleteK解答（见书P183）：错误有两处：（1）参数不合法的判别条件不完整。合法的入口参数条件为(0

9、,intk)//删除线性表a中第i个元素起的k个元素{if(i<1

10、

11、k<0

12、

13、i+k-1>a.length)returnINFEASIBLE;for(count=1;i+count-1<=a.length-k;count++)//注意循环结束的条件a.elem[i+count-1]=a.elem[i+count+k-1];a.length-=k;returnOK;}//DeleteK2.10StatusDeleteK(SqList&a,inti,intk)//删除线性表a中第i个元素起的k个元素{if(i<1

14、

15、k<0

16、

17、i+k-1>a.length)return

18、INFEASIBLE;for(count=1;count<=a.length-k-(i-1);count++)a.elem[i+count-1]=a.elem[i+count+k-1];a.length-=k;returnOK;}//DeleteK62.21试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,……..,an）逆置为（an，an-1，…….,a1）。参考程序：voidreverse(SqList&A)//顺序表的就地逆置{for(i=1,j=A.length;iA.elem[j];}

19、//reverse或templatevoidinverse(TypeA[],intn){Typetemp;for(inti=0;i<=(n-1)/2;i++){//循环次数为表长的一半temp=A[i];A[i]=A[n-i-1];A[n-i-1]=temp;}}62.22试写一算法，对单链表实现就地逆置。解答（P185）：以单链表作存储结构进行就地逆置的正确做法应该是：将原链表中的头结点和第一个元素结点断开（令其指针域为空），先构成一个新的空表，然后将原链表中各结点，从第一个结点起，依次插入这个新表的头部（即令每个插入的结点成为新的第一个