ch2部分习题解答.ppt
14页
Chapter2线性表练习：找出以下算法中的错误和低效之处，并将它改写为一个既正确又高效的算法intDeletek(SeqList*L,inti,intk)/*从顺序表L中删除第i个元素起的k个元素*/intcount,j;if(i0|kL-size)printf(“n参数不合法！”);return0;elsefor(count=1;countsize;j=i+1;j-)L-listj-1=L-listj;L-size-;return1;2021/6/71改进：intDeletek(SeqList*L,inti,intk)/*从顺序表L中删除第i个元素起的k个元素*/intcount,j;if(i0|kL-size)printf(“n参数不合法！”);return0;else/*删除k个元素*/for(j=i+k;jsize;j+)L-listj-k=L-listj;L-size-=k;return1;2021/6/722010考研题：设将n(n1)个整数存放到一维数组R中试设计一个在时间和空间两方面尽可能高效的算法，将R中的序列循环左移P（0Pn）个位置，即将R中的数据由（x0,x1,xn-1）变换为（xp,xp+1,xn-1,x0,x1,xp-1）。
(1)算法设计思想先将n个数（x0,x1,xp,xn-1）原地逆置，得到（xn-1,xp,xp-1,x0），然后再将前n-p个和后p个元素分别原地逆置，得到最终结果：xp,xp+1,xn-1,x0,x1,xp-1算法可以用两个函数实现一个是逆置函数reverse()，它将给定的数据逆置另一个是循环左移函数leftShift()，它调用reverse()函数三次，实现相应功能2021/6/73(2)算法实现voidreverse(intr,intleft,intright)inti=left,j=right,temp;/*i等于左边界left，j等于右边界right*/while(i0&pnext!=NULL)s=p-next;if(s-data=x)p-next=s-next;/*删除值为x的结点*/free(s);elsep=s;补充：已知一个带头结点的递增有序单链表L，试编写一高效算法：删除该链表中所有元素值大于x且小于y的结点2021/6/76补充：已知两个带表头结点的非递减有序单链表，头指针分别为la和lb，试编写算法，先将两个表合并为一个带表头结点的非递减有序单链表，然后删除表中结点值（data值）相同的冗余结点，最后返回新单链表的头指针。
要求新单链表利用原来两个链表的结点空间，不另外生成新结点2021/6/77voidListMergeDelete(SLNode*la,SLNode*lb,SLNode*lc)SLNode*pa,*pb,*pc;/*归并两个有序表*/(*lc)=la;pa=la-next;pb=lb-next;pc=la；while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;if(pa)pc-next=pa;elsepc-next=pb;free(lb);2021/6/78/*删除冗余结点*/pa=(*lc)-next;while(pa)pb=pa-next;while(pb&pb-data=pa-data)pc=pb;pb=pb-next;free(pc);pa-next=pb;pa=pb;2021/6/79书P46.2-21（判断两个集合是否存在包含关系）intListSetInclude(SLNode*L1,SLNode*L2)/*判断带头结点的单链表L1中的数据元素是否都是单链表L2中的数据元素*/SLNode*p1,*p2;p1=L1-next;while(p1!=NULL)p2=L2-next;while(p2!=NULL&p2-data!=p1-data)p2=p2-next;if(p2=NULL)return0;p1=p1-next;return1;2021/6/710补充作业1：创建单链表（从表头-表尾）intListCreate(SLNode*la,intn)/*从键盘输入n个数，建立以la为头指针的带头结点的单链表*/inti;SLNode*p,*q;if(*la)=(SLNode*)malloc(sizeof(SLNode)=NULL)printf(“内存空间不足！n”);return0;q=*la;for(i=0;idata);q-next=p;q=p;/*新结点p插入在表尾*/q-next=NULL;return1;2021/6/711补充作业2：已知一个带头结点的循环双向链表，从第二个结点至表尾递增有序。
编写一个算法，将第一个结点删除并插入表中适当位置，使整个链表递增有序voidListDIDL(DLNode*h)DLNode*p,*s;p=h-next;if(p!=h)h-next=p-next;p-next-prior=h;/*删除链表中的第一个结点，elsereturn;并用p指针保存*/s=h-next;while(s!=h&p-datas-data)s=s-next;/*查找p结点的插入位置*/p-prior=s-prior;s-prior-next=p;p-next=s;s-prior=p;/*p结点插入在s结点之前*/2021/6/7122009考研题：已知一个带头结点的单链表，假设该链表只给出了头指针，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个结点（k为正整数），若查找成功，算法输出该结点的data域的值，并返回1，否则，只返回0intLocatek(SLNode*h,intk)SLNode*p,*q;intcount;p=q=h-next;count=0;while(p!=NULL)/*先移动k次p指针，然后再同时移动p、q指针，直至p指针为空*/p=p-next;if(countnext;if(countdata);return1;2021/6/713部分资料从网络收集整理而来，供大家参考，感谢您的关注！。
