您好,登錄后才能下訂單哦!
這篇文章將為大家詳細(xì)講解有關(guān)C語言如何合并兩個(gè)帶頭節(jié)點(diǎn)升序排列鏈表,小編覺得挺實(shí)用的,因此分享給大家做個(gè)參考,希望大家閱讀完這篇文章后可以有所收獲。
合并鏈表,顧名思義,就是將兩個(gè)按順序存放數(shù)據(jù)的鏈表中的數(shù)據(jù)合并為用一個(gè)鏈表存儲(chǔ),比如在處理多項(xiàng)式的加減法時(shí)就需要將兩個(gè)多項(xiàng)式的數(shù)據(jù)進(jìn)行合并。合并方式有很多種:如果按照存儲(chǔ)方式的不同,可以將兩個(gè)鏈表的數(shù)據(jù)分別提取出來生成一個(gè)新的鏈表來存儲(chǔ)原先兩個(gè)鏈表的數(shù)據(jù),還可以將其中一個(gè)鏈表的數(shù)據(jù)依次插入到另外一個(gè)鏈表的相應(yīng)位置當(dāng)中去。在遇到相同數(shù)據(jù)時(shí)可以采取只留下一個(gè)數(shù)據(jù)的方式和兩個(gè)數(shù)據(jù)均保留的方式。這些不同點(diǎn)需要到具體的問題中具體分析,但是只是在細(xì)節(jié)上有一些差別,大體的思路都是一樣的,本文主要介紹將一個(gè)鏈表插入到另一個(gè)鏈表的相應(yīng)位置,插入完成后銷毀鏈表二,且遇到相同數(shù)據(jù)采用均保留的方式。
我們還是先拋開鏈表的操作本身,先對(duì)兩組不同的數(shù)據(jù)進(jìn)行合并操作,知道兩組按升序排列的數(shù)據(jù)該如何合并成一組數(shù)據(jù),我們來分析這樣幾組數(shù)據(jù)(將第二組的數(shù)據(jù)插入到第一組中):
1 5 9 13 15
2 7 12
對(duì)于這組數(shù)據(jù)我們可以很輕易的說出應(yīng)該把“2”插入到“1”的前面,應(yīng)該把“7”插入到“5”的前面... ... 那么我們又是如何得到這個(gè)結(jié)論的呢,接下來我們來用語言細(xì)致的描述一下我們剛才是如何得到這樣的結(jié)論的:“首先,遍歷第一組數(shù)據(jù),找到第一個(gè)比要插入的數(shù)據(jù)大的數(shù)據(jù)的前一個(gè)數(shù)據(jù)“i”,再將要插入的數(shù)據(jù)插入到“i”的后面”。
上述描述解決了插入數(shù)據(jù)的一般性情況,包括我們用“比該數(shù)據(jù)大”這樣的話說明了遇到相同數(shù)據(jù)時(shí)該如何處理,但是,問題依然存在,我們來觀察下面一組數(shù)據(jù):
2 4 7 9
1 3 6 8
我們要將第二組數(shù)據(jù)插入到第一組數(shù)據(jù)中,按照之前的說法,找到第一個(gè)不比待插入數(shù)據(jù)小的數(shù)據(jù)的前一個(gè)數(shù)據(jù)“i”,但是我們發(fā)現(xiàn)第一組數(shù)據(jù)中第一個(gè)數(shù)據(jù)就符合我們的要求,那么它自然沒有前一個(gè)數(shù)據(jù)。這里我們給出一個(gè)方案:在進(jìn)行插入工作前,先對(duì)兩個(gè)鏈表的首元素進(jìn)行比較,如果鏈表一的首元素是小于第二個(gè)鏈表的首元素的,那么開始合并工作,如果鏈表一的首元素不小于第二個(gè)鏈表的首元素,我們先交換兩個(gè)鏈表的頭結(jié)點(diǎn),使得鏈表一變成鏈表二。但是這種方式僅適用于我們當(dāng)前的情況,因?yàn)槲覀円獙?shí)現(xiàn)的是將鏈表二的元素加入到鏈表一中,之后銷毀鏈表二,這就意味著我們最后只要得到一個(gè)鏈表就可以,只要使得傳遞過來的鏈表一在執(zhí)行完我們的合并鏈表程序后能夠變成合并后的結(jié)果鏈表就好了,因此我們可能要更改傳遞過來的鏈表的頭結(jié)點(diǎn)的值。
根據(jù)上面的說法,我們就要在開始進(jìn)行合并之前先對(duì)兩個(gè)鏈表的首元素進(jìn)行比較,如果鏈表二的首元素比鏈表一的首元素大,則交換兩個(gè)鏈表的控制頭,再執(zhí)行后續(xù)的合并工作。
解決了上述問題,還差最后一種情況,我們來觀察下面一組數(shù)據(jù):
1 3 4 6 7
2 6 9 10 13
我們可以觀察到,將第二組數(shù)據(jù)依次向第一組數(shù)據(jù)中插入,到了“9”的時(shí)候,第一組數(shù)據(jù)就沒有可以插入的位置了,而應(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是我們自己定義的為了方便起見的一個(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來遍歷鏈表一,用A_LINE *q來實(shí)時(shí)保存當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn),鏈表沒有遍歷完而且當(dāng)前元素依然小于等于目標(biāo)元素,則循環(huán)繼續(xù)。當(dāng)循環(huán)結(jié)束后,判斷循環(huán)結(jié)束的原因,如果是因?yàn)殒湵肀闅v完了而結(jié)束的循環(huán),則說明整個(gè)鏈表里都沒有比目標(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é)過鏈表的人并不是什么難事,本文不做為重點(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成員更改為待插入鏈表的首元素的首地址。
但這里存在著問題,這里的賦值相當(dāng)于直接把鏈表二的一部分節(jié)點(diǎn)直接放到鏈表一的末尾,并不是復(fù)制出來一份再追加到鏈表一的末尾,這樣就使得鏈表二的那一部分節(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); }
關(guān)于“C語言如何合并兩個(gè)帶頭節(jié)點(diǎn)升序排列鏈表”這篇文章就分享到這里了,希望以上內(nèi)容可以對(duì)大家有一定的幫助,使各位可以學(xué)到更多知識(shí),如果覺得文章不錯(cuò),請(qǐng)把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。