《数据结构》实验学院：计算机学院专业：计算机科学与技术班级学号：计1203201207010323姓名：方荣实验一：实现两个链表的合并题目：实现两个链表的合并基本要求：（1）建立两个链表A和B，链表元素个数分别为m和n个；（2）假设元素分别为（x1,x2⋯xm）,和（y1,y2⋯yn）。把它们合并成一个线性表C:当m>=n时，C=x1,y1,x2,y2,⋯xn,yn,⋯xm当n>m时，C=（3）为统一起见，测试数据可以是{710，342，045，686，6，841，429，134，68，264}，也可以调用系统的随机函数产生。测试数据：{710，342，45，686，6，841，429，134，68，264}算法思想：这个两个链表的交叉合并算法主要运用到的是链表的基本操作，定义结点，链表的创建、计算链表的长度、链表A,B的交叉合并、输出链表等算法写成独立函数，通过主函数的调用，实现题目的要求。模块划分：1.单链表的存储结构。2.输出链表。3.用尾插法建立链表。4.计算链表的长度。5.合并链表。6.主函数。数据结构：源程序：#include#include#include#include#defineLsizeof(structNode)structNode{//构造结构体longintdata;structNode*next;};structNode*create(inta){intn;structNode*p1,*p2,*head;head=NULL;n=0;p2=p1=(structNode*)malloc(L);scanf("%ld",&p1->data);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->data);a--;}p2->next=NULL;return(head);}voidprint(structNode*head){//输出链表structNode*p;p=head;printf("\n");if(head!=NULL)do{printf("%ld",p->data);printf("");p=p->next;}while(p!=NULL);printf("\n");}structNode*inter_link(structNode*chain1,inta,structNode*chain2,intb){//链表合并函数inttemp;structNode*head,*p1,*p2,*pos;if(a>=b)//当链表p1元素个数大于链表p2元素个数{head=p1=chain1;//p1的第一个元素置于合成链表的表头p2=chain2;}else{head=p1=chain2;p2=chain1;temp=a;a=b;b=temp;}pos=head;while(p2!=NULL){p1=p1->next;pos->next=p2;pos=p2;p2=p2->next;pos->next=p1;pos=p1;}returnhead;}voidInserSort(structNode*p,intm){inti,j,t;structNode*k;k=p;for(i=0;idata>(p->next)->data){t=p->data;p->data=(p->next)->data;(p->next)->data=t;}p=p->next;}p=k;}}intmain(){//测试函数structNode*p1,*p2;inta,b,h;printf("***************************\n");printf("请输入第一个链表:\n");printf("***************************\n");printf("输入链表长度a:");scanf("%d",&a);printf("请输入链表数据:\n");p1=create(a);printf("你刚才输入的第一个链表信息:");print(p1);printf("\n***************************\n");printf("请输入第二个链表:\n");printf("***************************\n");printf("输入链表长度b:");scanf("%d",&b);printf("请输入链表数据:\n");p2=create(b);printf("你刚才输入的第二个链表信息:");print(p2);p1=inter_link(p1,a,p2,b);h=a+b;printf("\n合并后的链表:\n:");print(p1);InserSort(p1,h);printf("\n排序后的链表:\n");print(p1);return0;}测试情况：程序运行输出：测试结果分析：程序运行结果和人工模拟分析过程完全相同，说明程序设计正确。
