实现两个链表的合并.doc

实现两个链表的合并基本功能要求：（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) 结构体struct Node的创建。(2) struct Node *create（）链表的创建。(3) void print(struct Node *head)功能是对链表进行输出。(4) struct Node * inter_link(struct Node * chain1, int a, struct Node * chain2, int b)算法的功能是实现两个链表的交叉合并，并且可以根据两链表的长短将行不通的插入。(5) void InsertSort(struct Node *p,int m)算法的功能是对一合并好的链表进行升序插入排序。(6) main()函数主要是对算法进行测试。数据结构：数据结构定义如下：struct Node long int number; struct Node *next;源程序：#include#include#include#include#define L sizeof(struct Node)struct Node /结构体 long int number; struct Node *next;struct Node *create(int a)/链表创建函数 int n; struct Node *p1, *p2, *head; head = NULL; n = 0; p2 = p1 = (struct Node *) malloc(L); /分配内存 scanf(%ld, &p1-number); while (a)/录入链表信息 n = n + 1; if (n = 1) head = p1; else p2-next = p1; p2 = p1; p1 = (struct Node *) malloc(L); if (a != 1)/分配内存 scanf(%ld, &p1-number); a-; /控制输入的个数 p2-next = NULL; return (head);/链表创建函数结束void print(struct Node *head)/输出函数 struct Node *p; p = head; printf(数字:n); if (head != NULL) do/循环实现输出 printf(%ld, p-number); printf( ); p = p-next; while (p != NULL); printf(n);/链表的交叉合并算法struct Node * inter_link(struct Node * chain1, int a, struct Node * chain2, int b) int temp; struct Node *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; return head;/对合并好的链表进行排序void InsertSort(struct Node *p, int m)/排序函数 int i, j, t; struct Node *k; k = p; for (i = 0; i m - 1; i+) for (j = 0; j number (p-next)-number) t = p-number; p-number = (p-next)-number; (p-next)-number = t; p = p-next; p = k; /主函数int main()/main函数 struct Node *p1, *p2; int a; int b; int h; 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 = i