第六章课后习题.doc

第六章：4源程序如下：#include#define OVERFLOW -2using namespace std;struct chainchar data;struct chain *next;void reverse(chain*(&p);int main()int n,i;chain*head=NULL,*pm=NULL,*pend=NULL;cout请输入链表长度n:n;cout请输入链表的各个元素:endl;for(i=1;i(pm-data);if(i=1)head=pm;pend=pm;elsepend-next=pm;pend=pend-next;if(i=n)pend-next=NULL;reverse(head);cout逆转后的链表为:endl;for(pm=head;head!=NULL;pm=head)coutdatanext;free(pm);coutnext,*last=head-next-next;while(last!=NULL)mid-next=head;if(i=1)head-next=NULL;head=mid;mid=last;last=last-next;i+;j+;mid-next=head;if(j=0)head-next=NULL;head=mid;测试如下：5源程序如下：#include#include#define OVERFLOW -2using namespace std;struct chainint data;chain *next;chain *sort(chain*(&p);int main()int n,i;chain*head=NULL,*pm=NULL,*pend=NULL;cout请输入链表长度n:n;cout请输入链表的各个元素:endl;for(i=1;i(pm-data); /为每个结点赋值if(i=1) /若为头结点，则令头指针指向头结点head=pm;pend=pm;elsepend-next=pm; /其他节点（不是最后一个结点）的指针域指向下一个结点pend=pend-next;if(i=n) /尾结点的指针域置空pend-next=NULL;cout该链表的升序排列为:endl;for(pm=sort(head);head!=NULL;pm=head)coutdatanext;free(pm); coutnext!=NULL) /选择排序pc=pp-next;tag=pp;while(pc!=NULL)if(tag-datapc-data)tag=pc;pc=pc-next;if(pp-data!=tag-data)temp=tag-data;tag-data=pp-data;pp-data=temp;pp=pp-next;return head;测试如下：6源程序如下：#include#include#define OVERFLOW -2using namespace std;struct chainint data;struct chain *next;chain*pluschain(chain*(&p),chain*(&p2);int main()int n,m,i;chain*head1=NULL,*head2=NULL,*pm=NULL,*pend=NULL;cout请输入第一个升序链表长度n:n;cout请输入链表的各个元素:endl;for(i=1;i(pm-data);if(i=1)head1=pm;pend=pm;elsepend-next=pm;pend=pend-next;if(i=n)pend-next=NULL;cout请输入第二个升序链表长度m:m;cout请输入链表的各个元素:endl;for(i=1;i(pm-data);if(i=1)head2=pm;pend=pm;elsepend-next=pm;pend=pend-next;if(i=m)pend-next=NULL;cout合并后的升序链表为:endl;for(pm=pluschain(head1,head2);head!=NULL;pm=head)coutdatanext;free(pm);coutnext; /head1的作用是标记move指向元素的下一个元素，因若不标记move指向元素的下一个元素，move指向的元素插入链表2后，链表1中move指向元素之后的所有元素都将丢失。while(move2-datadata)if(move2-next=NULL)move2-next=move;return head2;if(move2-next-data=move-data)/此时找到了move指向元素在链表2中的位置help=move2; /help指针标示move指针指向元素在链表2中位置的前一个元素move2=move2-next;/move2指针标示move指针指向元素在链表2中位置的后一个元素i+;if(i=1)move-next=head2;head2=move;elsemove-next=move2;help-next=move;if(head1=NULL)/该判断条件表明此时head1指向的元素已是链表1中的最后一个元素。move2-next=NULL;break;move=head1;/move指针后移一位。return head2;测试如下：7源程序如下:#include#include#define OVERFLOW -2using namespace std;struct chainint data;struct chain *next;void reverse(chain*(&p1),chain*(&p2);int main()int n,m,i;chain*head1=NULL,*head2=NULL,*pm=NULL,*pend=NULL;cout请输入第一个链表长度n:n;cout请输入链表的各个元素:endl;for(i=1;i(pm-data);if(i=1)head1=pm;pend=pm;elsepend-next=pm;pend=pend-next;if(i=n)pend-next=NULL;cout请输入第二个链表长度m:m;cout请输入链表的各个元素:endl;for(i=1;i(pm-data);if(i=1)head2=pm;pend=pm;elsepend-next=pm;pend=pend-next;if(i=m)pend-next=NULL;reverse(head1,head2);for(pm=head1;pm!=NULL;pm=head1)head1=head1-next ;free(pm);for(pm=head2;pm!=NULL;pm=head2)head2=head2-next ;free(pm);return 0;void reverse(chain*(&head1),chain*(&head2)/判断链表1中的各个元素是否在链表2中int i=0;chain*pm,*pn;for(pn=head1;pn!=NULL;pn=pn-next) /链表1为