C語(yǔ)言合并兩個(gè)帶頭節(jié)點(diǎn)升序排列鏈表

更新時(shí)間：2019年03月03日 14:48:55 作者：Judy_c

這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言合并兩個(gè)帶頭節(jié)點(diǎn)升序排列鏈表的方法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

合并鏈表，顧名思義，就是將兩個(gè)按順序存放數(shù)據(jù)的鏈表中的數(shù)據(jù)合并為用一個(gè)鏈表存儲(chǔ)，比如在處理多項(xiàng)式的加減法時(shí)就需要將兩個(gè)多項(xiàng)式的數(shù)據(jù)進(jìn)行合并。合并方式有很多種：如果按照存儲(chǔ)方式的不同，可以將兩個(gè)鏈表的數(shù)據(jù)分別提取出來(lái)生成一個(gè)新的鏈表來(lái)存儲(chǔ)原先兩個(gè)鏈表的數(shù)據(jù)，還可以將其中一個(gè)鏈表的數(shù)據(jù)依次插入到另外一個(gè)鏈表的相應(yīng)位置當(dāng)中去。在遇到相同數(shù)據(jù)時(shí)可以采取只留下一個(gè)數(shù)據(jù)的方式和兩個(gè)數(shù)據(jù)均保留的方式。這些不同點(diǎn)需要到具體的問(wèn)題中具體分析，但是只是在細(xì)節(jié)上有一些差別，大體的思路都是一樣的，本文主要介紹將一個(gè)鏈表插入到另一個(gè)鏈表的相應(yīng)位置，插入完成后銷毀鏈表二，且遇到相同數(shù)據(jù)采用均保留的方式。

我們還是先拋開(kāi)鏈表的操作本身，先對(duì)兩組不同的數(shù)據(jù)進(jìn)行合并操作，知道兩組按升序排列的數(shù)據(jù)該如何合并成一組數(shù)據(jù)，我們來(lái)分析這樣幾組數(shù)據(jù)（將第二組的數(shù)據(jù)插入到第一組中）：

1 5 9 13 15

2 7 12

對(duì)于這組數(shù)據(jù)我們可以很輕易的說(shuō)出應(yīng)該把“2”插入到“1”的前面，應(yīng)該把“7”插入到“5”的前面... ... 那么我們又是如何得到這個(gè)結(jié)論的呢，接下來(lái)我們來(lái)用語(yǔ)言細(xì)致的描述一下我們剛才是如何得到這樣的結(jié)論的：“首先，遍歷第一組數(shù)據(jù)，找到第一個(gè)比要插入的數(shù)據(jù)大的數(shù)據(jù)的前一個(gè)數(shù)據(jù)“i”，再將要插入的數(shù)據(jù)插入到“i”的后面”。

上述描述解決了插入數(shù)據(jù)的一般性情況，包括我們用“比該數(shù)據(jù)大”這樣的話說(shuō)明了遇到相同數(shù)據(jù)時(shí)該如何處理，但是，問(wèn)題依然存在，我們來(lái)觀察下面一組數(shù)據(jù)：

2 4 7 9

1 3 6 8

我們要將第二組數(shù)據(jù)插入到第一組數(shù)據(jù)中，按照之前的說(shuō)法，找到第一個(gè)不比待插入數(shù)據(jù)小的數(shù)據(jù)的前一個(gè)數(shù)據(jù)“i”，但是我們發(fā)現(xiàn)第一組數(shù)據(jù)中第一個(gè)數(shù)據(jù)就符合我們的要求，那么它自然沒(méi)有前一個(gè)數(shù)據(jù)。這里我們給出一個(gè)方案：在進(jìn)行插入工作前，先對(duì)兩個(gè)鏈表的首元素進(jìn)行比較，如果鏈表一的首元素是小于第二個(gè)鏈表的首元素的，那么開(kāi)始合并工作，如果鏈表一的首元素不小于第二個(gè)鏈表的首元素，我們先交換兩個(gè)鏈表的頭結(jié)點(diǎn)，使得鏈表一變成鏈表二。但是這種方式僅適用于我們當(dāng)前的情況，因?yàn)槲覀円獙?shí)現(xiàn)的是將鏈表二的元素加入到鏈表一中，之后銷毀鏈表二，這就意味著我們最后只要得到一個(gè)鏈表就可以，只要使得傳遞過(guò)來(lái)的鏈表一在執(zhí)行完我們的合并鏈表程序后能夠變成合并后的結(jié)果鏈表就好了，因此我們可能要更改傳遞過(guò)來(lái)的鏈表的頭結(jié)點(diǎn)的值。

根據(jù)上面的說(shuō)法，我們就要在開(kāi)始進(jìn)行合并之前先對(duì)兩個(gè)鏈表的首元素進(jìn)行比較，如果鏈表二的首元素比鏈表一的首元素大，則交換兩個(gè)鏈表的控制頭，再執(zhí)行后續(xù)的合并工作。

解決了上述問(wèn)題，還差最后一種情況，我們來(lái)觀察下面一組數(shù)據(jù)：

1 3 4 6 7

2 6 9 10 13

我們可以觀察到，將第二組數(shù)據(jù)依次向第一組數(shù)據(jù)中插入，到了“9”的時(shí)候，第一組數(shù)據(jù)就沒(méi)有可以插入的位置了，而應(yīng)該在尾部追加，于是，我們就不能執(zhí)行之前的操作了，而應(yīng)該執(zhí)行另外一項(xiàng)操作，我們具體實(shí)現(xiàn)是這樣的：

如果我們?cè)诘谝唤M數(shù)據(jù)中找不到比待插入數(shù)據(jù)大的數(shù)據(jù)，我們就將待插入數(shù)據(jù)的后面的數(shù)據(jù)連同待插入數(shù)據(jù)本身，追加到第一組數(shù)據(jù)的末尾。

根據(jù)如上分析，我們需要執(zhí)行的有四種對(duì)鏈表的操作：1、在指定鏈中找到第一個(gè)比目標(biāo)數(shù)據(jù)的大的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)； 2、將指定元素插入到指定鏈表的指定位置； 3、將鏈表中的制定位置后的所有元素追加到指定鏈表的末尾； 4、交換兩個(gè)鏈表的頭結(jié)點(diǎn)。

下面我們就分布解決這四種操作（注：A_LINE是我們自己定義的為了方便起見(jiàn)的一個(gè)結(jié)構(gòu)體，只有一個(gè)int類型的num和一個(gè)A_LINE *類型的next成員不具有任何意義，僅僅是為了完成合并鏈表）：

1、在指定鏈中找到第一個(gè)比目標(biāo)數(shù)據(jù)的大的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)：

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來(lái)遍歷鏈表一，用A_LINE *q來(lái)實(shí)時(shí)保存當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，鏈表沒(méi)有遍歷完而且當(dāng)前元素依然小于等于目標(biāo)元素，則循環(huán)繼續(xù)。當(dāng)循環(huán)結(jié)束后，判斷循環(huán)結(jié)束的原因，如果是因?yàn)殒湵肀闅v完了而結(jié)束的循環(huán)，則說(shuō)明整個(gè)鏈表里都沒(méi)有比目標(biāo)節(jié)點(diǎn)大的節(jié)點(diǎn)，返回NOT_FOUND;若是因?yàn)檎业搅吮饶繕?biāo)元素大的元素而結(jié)束的，那么返回該元素的前驅(qū)節(jié)點(diǎn)的地址“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;
}

在第一步中我們已經(jīng)可以得到需要插入的位置的首地址了，下一步我們就要完成插入了，這對(duì)于學(xué)過(guò)鏈表的人并不是什么難事，本文不做為重點(diǎn)講解。

3、將一段數(shù)據(jù)追加到指定鏈表的末尾：

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代表要插入到的鏈表的頭結(jié)點(diǎn)。首先先定位目標(biāo)鏈表的末節(jié)點(diǎn)的首地址，再將待插入鏈表的末節(jié)點(diǎn)的next成員更改為待插入鏈表的首元素的首地址。

但這里存在著問(wèn)題，這里的賦值相當(dāng)于直接把鏈表二的一部分節(jié)點(diǎn)直接放到鏈表一的末尾，并不是復(fù)制出來(lái)一份再追加到鏈表一的末尾，這樣就使得鏈表二的那一部分節(jié)點(diǎn)又屬于鏈表一又屬于鏈表二，而鏈表二在最后是要被釋放的，那么它的后幾個(gè)節(jié)點(diǎn)也會(huì)被釋放。為了防止這樣的情況發(fā)生，我們必須將鏈表二中的要插入到鏈表一中的那一部分節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)的next成員賦值為NULL，這樣在就相當(dāng)于將那一部分節(jié)點(diǎn)從鏈表二中刪除，但是這樣并不會(huì)引起內(nèi)存泄漏，這些節(jié)點(diǎn)被連接到了鏈表一的末尾，因此在釋放鏈表一的時(shí)候這些節(jié)點(diǎn)依然會(huì)被釋放。

4、交換兩個(gè)鏈表的頭結(jié)點(diǎn)：

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);
}

最后我們給出整體的可測(cè)試的代碼：

#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("請(qǐng)輸入一個(gè)數(shù)（-1表示結(jié)束）：");
 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("請(qǐng)輸入一個(gè)數(shù)（-1表示結(jié)束）");
 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("錄入第一個(gè)鏈表：\n");
 initLine(&head1);
 printf("錄入第二個(gè)鏈表\n");
 initLine(&head2);
 
 margeLine(&head1, &head2);
 
 printf("鏈表一:\n");
 showLine(head1);
 printf("鏈表二:\n");
 showLine(head2);
 
  destoryLine(&head1);
}

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: