C語言合并兩個帶頭節(jié)點升序排列鏈表
合并鏈表，顧名思義，就是將兩個按順序存放數(shù)據(jù)的鏈表中的數(shù)據(jù)合并為用一個鏈表存儲，比如在處理多項式的加減法時就需要將兩個多項式的數(shù)據(jù)進行合并。合并方式有很多種：如果按照存儲方式的不同，可以將兩個鏈表的數(shù)據(jù)分別提取出來生成一個新的鏈表來存儲原先兩個鏈表的數(shù)據(jù)，還可以將其中一個鏈表的數(shù)據(jù)依次插入到另外一個鏈表的相應(yīng)位置當中去。在遇到相同數(shù)據(jù)時可以采取只留下一個數(shù)據(jù)的方式和兩個數(shù)據(jù)均保留的方式。這些不同點需要到具體的問題中具體分析，但是只是在細節(jié)上有一些差別，大體的思路都是一樣的，本文主要介紹將一個鏈表插入到另一個鏈表的相應(yīng)位置，插入完成后銷毀鏈表二，且遇到相同數(shù)據(jù)采用均保留的方式。
我們還是先拋開鏈表的操作本身，先對兩組不同的數(shù)據(jù)進行合并操作，知道兩組按升序排列的數(shù)據(jù)該如何合并成一組數(shù)據(jù)，我們來分析這樣幾組數(shù)據(jù)（將第二組的數(shù)據(jù)插入到第一組中）：
1 5 9 13 15
2 7 12
對于這組數(shù)據(jù)我們可以很輕易的說出應(yīng)該把“2”插入到“1”的前面，應(yīng)該把“7”插入到“5”的前面... ... 那么我們又是如何得到這個結(jié)論的呢，接下來我們來用語言細致的描述一下我們剛才是如何得到這樣的結(jié)論的：“首先，遍歷第一組數(shù)據(jù)，找到第一個比要插入的數(shù)據(jù)大的數(shù)據(jù)的前一個數(shù)據(jù)“i”，再將要插入的數(shù)據(jù)插入到“i”的后面”。
上述描述解決了插入數(shù)據(jù)的一般性情況，包括我們用“比該數(shù)據(jù)大”這樣的話說明了遇到相同數(shù)據(jù)時該如何處理，但是，問題依然存在，我們來觀察下面一組數(shù)據(jù)：
2 4 7 9
1 3 6 8
我們要將第二組數(shù)據(jù)插入到第一組數(shù)據(jù)中，按照之前的說法，找到第一個不比待插入數(shù)據(jù)小的數(shù)據(jù)的前一個數(shù)據(jù)“i”，但是我們發(fā)現(xiàn)第一組數(shù)據(jù)中第一個數(shù)據(jù)就符合我們的要求，那么它自然沒有前一個數(shù)據(jù)。這里我們給出一個方案：在進行插入工作前，先對兩個鏈表的首元素進行比較，如果鏈表一的首元素是小于第二個鏈表的首元素的，那么開始合并工作，如果鏈表一的首元素不小于第二個鏈表的首元素，我們先交換兩個鏈表的頭結(jié)點，使得鏈表一變成鏈表二。但是這種方式僅適用于我們當前的情況，因為我們要實現(xiàn)的是將鏈表二的元素加入到鏈表一中，之后銷毀鏈表二，這就意味著我們最后只要得到一個鏈表就可以，只要使得傳遞過來的鏈表一在執(zhí)行完我們的合并鏈表程序后能夠變成合并后的結(jié)果鏈表就好了，因此我們可能要更改傳遞過來的鏈表的頭結(jié)點的值。
根據(jù)上面的說法，我們就要在開始進行合并之前先對兩個鏈表的首元素進行比較，如果鏈表二的首元素比鏈表一的首元素大，則交換兩個鏈表的控制頭，再執(zhí)行后續(xù)的合并工作。
解決了上述問題，還差最后一種情況，我們來觀察下面一組數(shù)據(jù)：
1 3 4 6 7
2 6 9 10 13
我們可以觀察到，將第二組數(shù)據(jù)依次向第一組數(shù)據(jù)中插入，到了“9”的時候，第一組數(shù)據(jù)就沒有可以插入的位置了，而應(yīng)該在尾部追加，于是，我們就不能執(zhí)行之前的操作了，而應(yīng)該執(zhí)行另外一項操作，我們具體實現(xiàn)是這樣的：
如果我們在第一組數(shù)據(jù)中找不到比待插入數(shù)據(jù)大的數(shù)據(jù)，我們就將待插入數(shù)據(jù)的后面的數(shù)據(jù)連同待插入數(shù)據(jù)本身，追加到第一組數(shù)據(jù)的末尾。
根據(jù)如上分析，我們需要執(zhí)行的有四種對鏈表的操作：1、在指定鏈中找到第一個比目標數(shù)據(jù)的大的節(jié)點的前驅(qū)節(jié)點； 2、將指定元素插入到指定鏈表的指定位置； 3、將鏈表中的制定位置后的所有元素追加到指定鏈表的末尾； 4、交換兩個鏈表的頭結(jié)點。
下面我們就分布解決這四種操作（注：A_LINE是我們自己定義的為了方便起見的一個結(jié)構(gòu)體，只有一個int類型的num和一個A_LINE *類型的next成員不具有任何意義，僅僅是為了完成合并鏈表）：
1、在指定鏈中找到第一個比目標數(shù)據(jù)的大的節(jié)點的前驅(qū)節(jié)點：
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來實時保存當前節(jié)點的前驅(qū)節(jié)點，鏈表沒有遍歷完而且當前元素依然小于等于目標元素，則循環(huán)繼續(xù)。當循環(huán)結(jié)束后，判斷循環(huán)結(jié)束的原因，如果是因為鏈表遍歷完了而結(jié)束的循環(huán)，則說明整個鏈表里都沒有比目標節(jié)點大的節(jié)點，返回NOT_FOUND;若是因為找到了比目標元素大的元素而結(jié)束的，那么返回該元素的前驅(qū)節(jié)點的地址“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)可以得到需要插入的位置的首地址了，下一步我們就要完成插入了，這對于學過鏈表的人并不是什么難事，本文不做為重點講解。
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é)點。首先先定位目標鏈表的末節(jié)點的首地址，再將待插入鏈表的末節(jié)點的next成員更改為待插入鏈表的首元素的首地址。
但這里存在著問題，這里的賦值相當于直接把鏈表二的一部分節(jié)點直接放到鏈表一的末尾，并不是復(fù)制出來一份再追加到鏈表一的末尾，這樣就使得鏈表二的那一部分節(jié)點又屬于鏈表一又屬于鏈表二，而鏈表二在最后是要被釋放的，那么它的后幾個節(jié)點也會被釋放。為了防止這樣的情況發(fā)生，我們必須將鏈表二中的要插入到鏈表一中的那一部分節(jié)點的前驅(qū)節(jié)點的next成員賦值為NULL，這樣在就相當于將那一部分節(jié)點從鏈表二中刪除，但是這樣并不會引起內(nèi)存泄漏，這些節(jié)點被連接到了鏈表一的末尾，因此在釋放鏈表一的時候這些節(jié)點依然會被釋放。
4、交換兩個鏈表的頭結(jié)點：
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("請輸入一個數(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("請輸入一個數(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("錄入第一個鏈表：\n");
initLine(&head1);
printf("錄入第二個鏈表\n");
initLine(&head2);
margeLine(&head1, &head2);
printf("鏈表一:\n");
showLine(head1);
printf("鏈表二:\n");
showLine(head2);
destoryLine(&head1);
}
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了C語言約瑟夫環(huán)的實現(xiàn)的相關(guān)資料,這里主要是利用數(shù)據(jù)數(shù)據(jù)結(jié)果中循環(huán)鏈表來實現(xiàn)，需要的朋友可以參考下2017-08-08
雙鏈表：在單鏈表的每個結(jié)點中，再設(shè)置一個指向其前驅(qū)結(jié)點的指針域，下面這篇文章主要給大家介紹了關(guān)于利用C++實現(xiàn)雙鏈表基本接口的相關(guān)資料，需要的朋友可以參考借鑒，下面來一起看看吧。2017-08-08
這篇文章主要介紹了詳解C++中的對象指針與對象數(shù)組,是C++入門學習中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
詳解C語言如何計算結(jié)構(gòu)體大小(結(jié)構(gòu)體的內(nèi)存對齊)
結(jié)構(gòu)體的內(nèi)存對齊是有關(guān)結(jié)構(gòu)體內(nèi)容的很重要一個知識點，主要考察方式是計算結(jié)構(gòu)體的字節(jié)大小，所以本文就給大家詳細介紹一下C語言如何計算結(jié)構(gòu)體大小，文中的代碼示例介紹的非常詳細,需要的朋友可以參考下2023-07-07
這篇文章為大家詳細主要介紹了Qt計時器的使用方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
這篇文章主要為大家詳細介紹了OpenCV實現(xiàn)雙邊濾波算法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
c++ lambda捕獲this 導(dǎo)致多線程下類釋放后還在使用的錯誤問題
Lambda表達式是現(xiàn)代C++的一個語法糖，挺好用的。但是如果使用不當，會導(dǎo)致內(nèi)存泄露或潛在的崩潰問題，這里總結(jié)下c++ lambda捕獲this 導(dǎo)致多線程下類釋放后還在使用的錯誤問題，感興趣的朋友一起看看吧2023-02-02
這篇文章主要介紹了C++非遞歸遍歷磁盤文件和遞歸遍歷磁盤文件的程序示例,大家可以參考使用二種方法2013-11-11
本文主要介紹了嵌入式QT移植的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-05-05
這篇文章主要介紹了LoadLibrary深入案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-08-08