实现两个链表的合并_两个链表合并为一个
实现两个链表的合并由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“两个链表合并为一个”。
实现两个链表的合并
基本功能要求：
（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=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)(2)(3)(4)结构体struct Node的创建。
struct Node *create（）链表的创建。
void print(struct Node *head)功能是对链表进行输出。
struct Node * inter_link(struct Node * chain1, int a, struct Node * chain2, int b)
算法的功能是实现两个链表的交叉合并，并且可以根据两链表的长短将行不通的插入。(5)void InsertSort(struct Node *p,int m)算法的功能是对一合并好的链表进行升序插入排序。
main()函数主要是对算法进行测试。(6)
数据结构：
数据结构定义如下：
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/*b>a*/ {
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
if(p->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 = inter_link(p1, a, p2, b);
h = a + b;
printf(“n合并后的链表n：”);
print(p1);
InsertSort(p1, h);
printf(“n排序后的链表:n”);
print(p1);
return 0;}
