实现两个链表的合并

实现两个链表的合并基本功能要求：（1）建立两个链表A和B，链表元素个数分别为m和n个。（2）假设元素分别为(x1,x2,…xm)，和(y1,y2,…yn)。把它们合并成一个线性表C，使得：当m=n时，C=x1,y1,x2,y2,…xn,yn,…,xm当nm时，C=y1,x1,y2,x2,…ym,xm,…,yn输出线性表C：（1）用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。测试数据：（1）A表（30，41，15，12，56，80）B表（23，56，78，23，12，33，79，90，55）（2）A表（30，41，15，12，56，80，23，12，34）B表（23，56，78，23，12）模块划分(1)结构体structNode的创建。(2)structNode*create（）链表的创建。(3)voidprint(structNode*head)功能是对链表进行输出。(4)structNode*inter_link(structNode*chain1,inta,structNode*chain2,intb)算法的功能是实现两个链表的交叉合并，并且可以根据两链表的长短将行不通的插入。(5)voidInsertSort(structNode*p,intm)算法的功能是对一合并好的链表进行升序插入排序。(6)main()函数主要是对算法进行测试。数据结构：数据结构定义如下：structNode{longintnumber;structNode*next;};源程序：#includestdlib.h#includestdio.h#includeconio.h#includemalloc.h#defineLsizeof(structNode)structNode//结构体{longintnumber;structNode*next;};structNode*create(inta)//链表创建函数{intn;structNode*p1,*p2,*head;head=NULL;n=0;p2=p1=(structNode*)malloc(L);//分配内存scanf(%ld,&p1-number);while(a)//录入链表信息{n=n+1;if(n==1)head=p1;elsep2-next=p1;p2=p1;p1=(structNode*)malloc(L);if(a!=1)//分配内存scanf(%ld,&p1-number);a--;//控制输入的个数}p2-next=NULL;return(head);}//链表创建函数结束voidprint(structNode*head)//输出函数{structNode*p;p=head;printf(数字:\n);if(head!=NULL)do//循环实现输出{printf(%ld,p-number);printf();p=p-next;}while(p!=NULL);printf(\n);}//链表的交叉合并算法structNode*inter_link(structNode*chain1,inta,structNode*chain2,intb){inttemp;structNode*head,*p1,*p2,*pos;/*判断a，b大小并合并*/if(a=b){head=p1=chain1;p2=chain2;}else/*ba*/{head=p1=chain2;p2=chain1;temp=a,a=b,b=temp;/*交换a和b*/}/*下面把p1的每个元素插在p2相应元素之前，p1长a,p2长b*/pos=head;/*此时pos指向p1中的第一个元素*/while(p2!=NULL){//漂亮，蛇形插入p1=p1-next;pos-next=p2;pos=p2;p2=p2-next;pos-next=p1;pos=p1;}returnhead;}//对合并好的链表进行排序voidInsertSort(structNode*p,intm)//排序函数{inti,j,t;structNode*k;k=p;for(i=0;im-1;i++){for(j=0;jm-i-1;j++){if(p-number(p-next)-number){t=p-number;p-number=(p-next)-number;(p-next)-number=t;}p=p-next;}p=k;}}//主函数intmain()//main函数{structNode*p1,*p2;inta;intb;inth;printf(请输入第一个链表:\n);printf(\n输入链表的长度a:\n);scanf(%d,&a);printf(请输入链表数据：);p1=create(a);printf(\n你刚才输入的第一个链表信息:\n);print(p1);printf(\n请输入第二个链表:\n);printf(\n输入链表的长度b:\n);scanf(%d,&b);printf(请输入链表数据：);p2=create(b);printf(\n你刚才输入的第二个链表的信息:\n);print(p2);p1=inter_link(p1,a,p2,b);h=a+b;printf(\n合并后的链表\n：);print(p1);InsertSort(p1,h);printf(\n排序后的链表:\n);print(p1);return0;}