ch2部分习题解答.ppt

《ch2部分习题解答.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Chapter2线性表练习：找出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法。intDeletek(SeqList*L,inti,intk)/*从顺序表L中删除第i个元素起的k个元素*/{intcount,j;if(i<0

2、

3、k<0

4、

5、i+k>L->size){printf(“参数不合法！”);return0;}else{for(count=1;countsize;j>=i+1;j--)L->list[j-1]=L->list[j];L->size--;}

6、return1;}}改进：intDeletek(SeqList*L,inti,intk)/*从顺序表L中删除第i个元素起的k个元素*/{intcount,j;if(i<0

7、

8、k<=0

9、

10、i+k>L->size){printf(“参数不合法！”);return0;}else{/*删除k个元素*/for(j=i+k;jsize;j++)L->list[j-k]=L->list[j];L->size-=k;return1;}}2010考研题：设将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面尽可能高效的算法，将R

11、中的序列循环左移P（0

12、现相应功能。(2)算法实现voidreverse(intr[],intleft,intright){inti=left,j=right,temp;/*i等于左边界left，j等于右边界right*/while(i0&&p

13、n-p-1);/*将前n-p个元素逆置*/reverse(r,n-p,n-1);/*将后p个元素逆置*/}}(3)算法复杂性算法的时间复杂度为O(n)，空间复杂度为O(1)。书P46.2-19voidListDeleteMore(SLNode*L,DataTypex)/*在带头结点的单链表中删除所有值为x的数据元素*/{SLNode*p,*s;p=L;while(p->next!=NULL){s=p->next;if(s->data==x){p->next=s->next;/*删除值为x的结点*/free(s);}elsep=s;}}补充

14、：已知一个带头结点的递增有序单链表L，试编写一高效算法：删除该链表中所有元素值大于x且小于y的结点。补充：已知两个带表头结点的非递减有序单链表，头指针分别为la和lb，试编写算法，先将两个表合并为一个带表头结点的非递减有序单链表，然后删除表中结点值（data值）相同的冗余结点，最后返回新单链表的头指针。要求新单链表利用原来两个链表的结点空间，不另外生成新结点。voidListMergeDelete(SLNode*la,SLNode*lb,SLNode**lc){SLNode*pa,*pb,*pc;/*归并两个有序表*/(*lc)=la;p

15、a=la->next;pb=lb->next;pc=la；while(pa&&pb)if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}if(pa)pc->next=pa;elsepc->next=pb;free(lb);/*删除冗余结点*/pa=(*lc)->next;while(pa){pb=pa->next;while(pb&&pb->data==pa->data){pc=pb;pb=pb->next;fr

16、ee(pc);}pa->next=pb;pa=pb;}}书P46.2-21（判断两个集合是否存在包含关系）intListSetInclude(SLNode*L1,SLNode*L2)/*判断带