快捷導(dǎo)航

C語言合并兩個帶頭節(jié)點升序排列鏈表

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

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

合并鏈表，顧名思義，就是將兩個按順序存放數(shù)據(jù)的鏈表中的數(shù)據(jù)合并為用一個鏈表存儲，比如在處理多項式的加減法時就需要將兩個多項式的數(shù)據(jù)進行合并。合并方式有很多種：如果按照存儲方式的不同，可以將兩個鏈表的數(shù)據(jù)分別提取出來生成一個新的鏈表來存儲原先兩個鏈表的數(shù)據(jù)，還可以將其中一個鏈表的數(shù)據(jù)依次插入到另外一個鏈表的相應(yīng)位置當(dā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é)點，使得鏈表一變成鏈表二。但是這種方式僅適用于我們當(dāng)前的情況，因為我們要實現(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來實時保存當(dāng)前節(jié)點的前驅(qū)節(jié)點，鏈表沒有遍歷完而且當(dāng)前元素依然小于等于目標元素，則循環(huán)繼續(xù)。當(dāng)循環(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)可以得到需要插入的位置的首地址了，下一步我們就要完成插入了，這對于學(xué)過鏈表的人并不是什么難事，本文不做為重點講解。

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成員更改為待插入鏈表的首元素的首地址。

但這里存在著問題，這里的賦值相當(dāng)于直接把鏈表二的一部分節(jié)點直接放到鏈表一的末尾，并不是復(fù)制出來一份再追加到鏈表一的末尾，這樣就使得鏈表二的那一部分節(jié)點又屬于鏈表一又屬于鏈表二，而鏈表二在最后是要被釋放的，那么它的后幾個節(jié)點也會被釋放。為了防止這樣的情況發(fā)生，我們必須將鏈表二中的要插入到鏈表一中的那一部分節(jié)點的前驅(qū)節(jié)點的next成員賦值為NULL，這樣在就相當(dāng)于將那一部分節(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)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: