C语言合并两个带头节点升序排列链表 C语言合并两个带头节点升序排列链表
Judy_c 人气:0合并链表，顾名思义，就是将两个按顺序存放数据的链表中的数据合并为用一个链表存储，比如在处理多项式的加减法时就需要将两个多项式的数据进行合并。合并方式有很多种：如果按照存储方式的不同，可以将两个链表的数据分别提取出来生成一个新的链表来存储原先两个链表的数据，还可以将其中一个链表的数据依次插入到另外一个链表的相应位置当中去。在遇到相同数据时可以采取只留下一个数据的方式和两个数据均保留的方式。这些不同点需要到具体的问题中具体分析，但是只是在细节上有一些差别，大体的思路都是一样的，本文主要介绍将一个链表插入到另一个链表的相应位置，插入完成后销毁链表二，且遇到相同数据采用均保留的方式。
我们还是先抛开链表的操作本身，先对两组不同的数据进行合并操作，知道两组按升序排列的数据该如何合并成一组数据，我们来分析这样几组数据（将第二组的数据插入到第一组中）：
1 5 9 13 15
2 7 12
对于这组数据我们可以很轻易的说出应该把“2”插入到“1”的前面，应该把“7”插入到“5”的前面... ... 那么我们又是如何得到这个结论的呢，接下来我们来用语言细致的描述一下我们刚才是如何得到这样的结论的：“首先，遍历第一组数据，找到第一个比要插入的数据大的数据的前一个数据“i”，再将要插入的数据插入到“i”的后面”。
上述描述解决了插入数据的一般性情况，包括我们用“比该数据大”这样的话说明了遇到相同数据时该如何处理，但是，问题依然存在，我们来观察下面一组数据：
2 4 7 9
1 3 6 8
我们要将第二组数据插入到第一组数据中，按照之前的说法，找到第一个不比待插入数据小的数据的前一个数据“i”，但是我们发现第一组数据中第一个数据就符合我们的要求，那么它自然没有前一个数据。这里我们给出一个方案：在进行插入工作前，先对两个链表的首元素进行比较，如果链表一的首元素是小于第二个链表的首元素的，那么开始合并工作，如果链表一的首元素不小于第二个链表的首元素，我们先交换两个链表的头结点，使得链表一变成链表二。但是这种方式仅适用于我们当前的情况，因为我们要实现的是将链表二的元素加入到链表一中，之后销毁链表二，这就意味着我们最后只要得到一个链表就可以，只要使得传递过来的链表一在执行完我们的合并链表程序后能够变成合并后的结果链表就好了，因此我们可能要更改传递过来的链表的头结点的值。
根据上面的说法，我们就要在开始进行合并之前先对两个链表的首元素进行比较，如果链表二的首元素比链表一的首元素大，则交换两个链表的控制头，再执行后续的合并工作。
解决了上述问题，还差最后一种情况，我们来观察下面一组数据：
1 3 4 6 7
2 6 9 10 13
我们可以观察到，将第二组数据依次向第一组数据中插入，到了“9”的时候，第一组数据就没有可以插入的位置了，而应该在尾部追加，于是，我们就不能执行之前的操作了，而应该执行另外一项操作，我们具体实现是这样的：
如果我们在第一组数据中找不到比待插入数据大的数据，我们就将待插入数据的后面的数据连同待插入数据本身，追加到第一组数据的末尾。
根据如上分析，我们需要执行的有四种对链表的操作：1、在指定链中找到第一个比目标数据的大的节点的前驱节点； 2、将指定元素插入到指定链表的指定位置； 3、将链表中的制定位置后的所有元素追加到指定链表的末尾； 4、交换两个链表的头结点。
下面我们就分布解决这四种操作（注：A_LINE是我们自己定义的为了方便起见的一个结构体，只有一个int类型的num和一个A_LINE *类型的next成员不具有任何意义，仅仅是为了完成合并链表）：
1、在指定链中找到第一个比目标数据的大的节点的前驱节点：
A_LINE *getFirstLocalBiggerThanEle(A_LINE head, A_LINE ele) {
A_LINE *p;
A_LINE *q;
for (p = head.next; p->next != NULL && ele.num >= p->num; p = p->next)
q = p;
if (p->next == NULL) {
return NOT_FOUND;
}
return q;
}
我们用A_LINE *p来遍历链表一，用A_LINE *q来实时保存当前节点的前驱节点，链表没有遍历完而且当前元素依然小于等于目标元素，则循环继续。当循环结束后，判断循环结束的原因，如果是因为链表遍历完了而结束的循环，则说明整个链表里都没有比目标节点大的节点，返回NOT_FOUND;若是因为找到了比目标元素大的元素而结束的，那么返回该元素的前驱节点的地址“q”。
2、将指定元素插入到指定链表的指定位置：
void insertEleToLine(A_LINE *local, A_LINE ele) {
A_LINE *newEle;
newEle = (A_LINE *)calloc(1, sizeof(A_LINE));
newEle->next = local->next;
local->next = newEle;
newEle->num = ele.num;
}
在第一步中我们已经可以得到需要插入的位置的首地址了，下一步我们就要完成插入了，这对于学过链表的人并不是什么难事，本文不做为重点讲解。
3、将一段数据追加到指定链表的末尾：
void appendLineToLineEnd(A_LINE *line, A_LINE targetLine) {
A_LINE *tarP;
for (tarP = targetLine.next; tarP->next != NULL; tarP = tarP->next)
;
tarP->next = line;
}
这里给出的A_LINE *line代表着待插入链表的首元素的首地址，targetLine代表要插入到的链表的头结点。首先先定位目标链表的末节点的首地址，再将待插入链表的末节点的next成员更改为待插入链表的首元素的首地址。
但这里存在着问题，这里的赋值相当于直接把链表二的一部分节点直接放到链表一的末尾，并不是复制出来一份再追加到链表一的末尾，这样就使得链表二的那一部分节点又属于链表一又属于链表二，而链表二在最后是要被释放的，那么它的后几个节点也会被释放。为了防止这样的情况发生，我们必须将链表二中的要插入到链表一中的那一部分节点的前驱节点的next成员赋值为NULL，这样在就相当于将那一部分节点从链表二中删除，但是这样并不会引起内存泄漏，这些节点被连接到了链表一的末尾，因此在释放链表一的时候这些节点依然会被释放。
4、交换两个链表的头结点：
void exchangeLine(A_LINE *head1, A_LINE *head2) {
A_LINE temp;
temp = *head1;
*head1 = *head2;
*head2 = temp;
}
5、合并链表完整代码：
void margeLine(A_LINE *targetLine, A_LINE *resourceLine) {
A_LINE *tarP = targetLine->next;
A_LINE *srcP = resourceLine->next;
A_LINE *srcPreP;
A_LINE *local;
if (tarP->num >= srcP->num) {
exchangeLine(targetLine, resourceLine);
}
for (srcP = srcPreP = resourceLine->next; srcP != NULL; srcP = srcP->next) {
local = getFirstLocalBiggerThanEle(*targetLine, *srcP);
if (local != NOT_FOUND) {
insertEleToLine(local, *srcP);
}
else {
appendLineToLineEnd(srcPreP->next, *targetLine);
srcPreP->next = NULL;
destoryLine(resourceLine);
return;
}
srcPreP = srcP;
}
destoryLine(resourceLine);
}
最后我们给出整体的可测试的代码：
#include<stdio.h>
#include<malloc.h>
#define NOT_FOUND NULL
typedef struct A_LINE {
int num;
struct A_LINE *next;
} A_LINE;
void margeLine(A_LINE *targetLine, A_LINE *resourceLine);
A_LINE *getFirstLocalBiggerThanEle(A_LINE head, A_LINE ele);
void insertEleToLine(A_LINE *local, A_LINE ele);
void destoryLine(A_LINE *head);
void initLine(A_LINE *head);
void showLine(A_LINE head);
void exchangeLine(A_LINE *head1, A_LINE *head2);
void appendLineToLineEnd(A_LINE *line, A_LINE targetLine);
void appendLineToLineEnd(A_LINE *line, A_LINE targetLine) {
A_LINE *tarP;
for (tarP = targetLine.next; tarP->next != NULL; tarP = tarP->next)
;
tarP->next = line;
}
void exchangeLine(A_LINE *head1, A_LINE *head2) {
A_LINE temp;
temp = *head1;
*head1 = *head2;
*head2 = temp;
}
void showLine(A_LINE head) {
A_LINE *p;
for (p = head.next; p != NULL; p = p->next) {
printf("%d ", p->num);
}
}
void initLine(A_LINE *head) {
int num;
A_LINE *p = NULL;
printf("请输入一个数（-1表示结束）：");
scanf_s("%d", &num);
while (num != -1) {
if (head->next == NULL) {
head->next = (A_LINE *)calloc(1, sizeof(A_LINE));
(head->next)->num = num;
p = head->next;
}
else {
p->next = (A_LINE *)calloc(1, sizeof(A_LINE));
(p->next)->num = num;
p = p->next;
}
printf("请输入一个数（-1表示结束）");
scanf_s("%d", &num);
}
}
void destoryLine(A_LINE *head) {
A_LINE *p = head->next;
while (NULL != head->next) {
p = head->next;
head->next = p->next;
free(p);
}
}
void insertEleToLine(A_LINE *local, A_LINE ele) {
A_LINE *newEle;
newEle = (A_LINE *)calloc(1, sizeof(A_LINE));
newEle->next = local->next;
local->next = newEle;
newEle->num = ele.num;
}
A_LINE *getFirstLocalBiggerThanEle(A_LINE head, A_LINE ele) {
A_LINE *p = NULL;
A_LINE *q = NULL;
for (p = head.next; p != NULL && ele.num >= p->num; p = p->next)
q = p;
if (p == NULL) {
return NOT_FOUND;
}
return q;
}
void margeLine(A_LINE *targetLine, A_LINE *resourceLine) {
A_LINE *tarP = targetLine->next;
A_LINE *srcP = resourceLine->next;
A_LINE *srcPreP;
A_LINE *local;
if (tarP->num >= srcP->num) {
exchangeLine(targetLine, resourceLine);
}
for (srcP = srcPreP = resourceLine->next; srcP != NULL; srcP = srcP->next) {
local = getFirstLocalBiggerThanEle(*targetLine, *srcP);
if (local != NOT_FOUND) {
insertEleToLine(local, *srcP);
}
else {
appendLineToLineEnd(srcPreP->next, *targetLine);
srcPreP->next = NULL;
destoryLine(resourceLine);
return;
}
srcPreP = srcP;
}
destoryLine(resourceLine);
}
void main(void) {
A_LINE head1 = {0};
A_LINE head2 = {0};
printf("录入第一个链表：\n");
initLine(&head1);
printf("录入第二个链表\n");
initLine(&head2);
margeLine(&head1, &head2);
printf("链表一:\n");
showLine(head1);
printf("链表二:\n");
showLine(head2);
destoryLine(&head1);
}
加载全部内容