c語(yǔ)言單鏈表尾添加的深入講解
前言
猶豫了幾天，看了很多大牛寫(xiě)的關(guān)于c語(yǔ)言鏈表，感觸很多，終于下定決心，把自己對(duì)于鏈表的理解隨之附上，可用與否，自行裁奪。由于作者水平有限也是第一次寫(xiě)，不足之處，竭誠(chéng)希望得到各位大神的批評(píng)指正。制作不易，不喜勿噴，謝謝?。。?/p>
在正文開(kāi)始之前，我先對(duì)數(shù)組和鏈表進(jìn)行簡(jiǎn)單的對(duì)比分析。
鏈表也是一種很常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，不同于數(shù)組的是它是動(dòng)態(tài)進(jìn)行存儲(chǔ)分配的一種結(jié)構(gòu)。數(shù)組存放數(shù)據(jù)時(shí)，必須要事先知道元素的個(gè)數(shù)。舉個(gè)例子，比如一個(gè)班有40個(gè)人，另一個(gè)班有100個(gè)人，如果要用同一個(gè)數(shù)組先后來(lái)存放這兩個(gè)班的學(xué)生數(shù)據(jù)，那么必須得定義長(zhǎng)度為100的數(shù)組。如果事先不確定一個(gè)班的人數(shù)，只能把數(shù)組定義的足夠大，以能存放任何班級(jí)的學(xué)生數(shù)據(jù)。這樣就很浪費(fèi)內(nèi)存，而且數(shù)組對(duì)于內(nèi)存的要求必須是是連續(xù)的，數(shù)據(jù)小的話還好說(shuō)，數(shù)據(jù)大的話內(nèi)存分配就會(huì)失敗，數(shù)組定義當(dāng)然也就失敗。還有數(shù)組對(duì)于插入以及刪除元素的效率也很低這就不一一介紹了。然而鏈表就相對(duì)于比較完美，它很好的解決了數(shù)組存在的那些問(wèn)題。它儲(chǔ)存數(shù)據(jù)時(shí)就不需要分配連續(xù)的空間，對(duì)于元素的插入以及刪除效率就很高?？梢哉f(shuō)鏈表對(duì)于內(nèi)存就是隨用隨拿，不像數(shù)組要事先申請(qǐng)。當(dāng)然，有優(yōu)點(diǎn)就必然有缺點(diǎn)，就比如說(shuō)鏈表里每一個(gè)元素里面都多包含一個(gè)地址，或者說(shuō)多包含一個(gè)存放地址的指針變量，所以內(nèi)存開(kāi)銷(xiāo)就很大。還有因?yàn)殒湵淼膬?nèi)存空間不是連續(xù)的，所以想找到其中的某一個(gè)數(shù)據(jù)就沒(méi)有數(shù)組那么方便，必須先得到該元素的上一個(gè)元素，根據(jù)上一個(gè)元素提供的下一元素地址去找到該元素。所以不提供“頭指針”（下文中“頭指針”為“PHead”），那么整個(gè)鏈表將無(wú)法訪問(wèn)。鏈表就相當(dāng)于一條鐵鏈一環(huán)扣一環(huán)（這個(gè)稍后會(huì)詳細(xì)的說(shuō)）。
鏈表
上面我提到過(guò)鏈表是動(dòng)態(tài)進(jìn)行存儲(chǔ)分配的一種結(jié)構(gòu)。鏈表中的每一個(gè)元素稱(chēng)為“結(jié)點(diǎn)”，每個(gè)結(jié)點(diǎn)都包括兩部分：一部分為用戶需要的實(shí)際數(shù)據(jù)，另一部分為下一結(jié)點(diǎn)的地址。鏈表有一個(gè)“頭指針(PHead)”變量，存放著一個(gè)地址，該地址指向第一個(gè)結(jié)點(diǎn)，第一個(gè)結(jié)點(diǎn)里面存放著第二個(gè)結(jié)點(diǎn)的地址，第二個(gè)結(jié)點(diǎn)又存放著第三個(gè)結(jié)點(diǎn)地址。就這樣頭指針指向第一個(gè)結(jié)點(diǎn)，第一個(gè)結(jié)點(diǎn)又指向第二個(gè)......直到最后一個(gè)結(jié)點(diǎn)。最后一個(gè)結(jié)點(diǎn)不再指向其他結(jié)點(diǎn)，地址部分存放一個(gè)“NULL”。 見(jiàn)下圖：（表中有一個(gè)尾指針（PEnd）其作用后面會(huì)解釋?zhuān)?/p>
c語(yǔ)言單項(xiàng)鏈表尾添加整體代碼如下：（詳解附后）
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
//函數(shù)聲明
//尾添加
void wei_tian_jia(struct NODE** PHEAD, struct NODE** PEND, int shu_ju);
//尾添加(沒(méi)有尾指針)
void wei_tian_jia_(struct NODE** PHEAD, int shu_ju);
//釋放鏈表
void shi_fang_lian_biao(struct NODE* PHEAD);
//釋放鏈表(并是頭指針(PHead)尾指針(PEnd)指向空)
void shi_fang_lian_biao_free(struct NODE** PHEAD, struct NODE** PEnd);
//輸出鏈表
void shu_chu(struct NODE* PHEAD);
//定義一個(gè)鏈表結(jié)構(gòu)體
struct NODE
{
int shu_ju; //用戶需要的實(shí)際數(shù)據(jù)
struct NODE* PNext; //下一結(jié)點(diǎn)的地址
};
int main(void)
{
//創(chuàng)建頭尾指針
struct NODE* PHead = NULL;
struct NODE* PEnd = NULL;
//尾添加
wei_tian_jia(&PHead, &PEnd, 17);
wei_tian_jia(&PHead, &PEnd, 21);
wei_tian_jia(&PHead, &PEnd, 34);
wei_tian_jia(&PHead, &PEnd, 8);
wei_tian_jia(&PHead, &PEnd, 24);
//尾添加(沒(méi)有尾指針)
//wei_tian_jia_(&PHead, 23);
//wei_tian_jia_(&PHead, 17);
//wei_tian_jia_(&PHead, 11);
//輸出鏈表
shu_chu(PHead);
//釋放鏈表
//shi_fang_lian_biao(PHead);
//釋放鏈表(并是頭指針(PHead)尾指針(PEnd)指向空)
shi_fang_lian_biao_free(&PHead, &PEnd);
system("pause");
return 0;
}
//尾添加
void wei_tian_jia(struct NODE** PHEAD, struct NODE** PEND, int SHU_JU)
{
//創(chuàng)建結(jié)點(diǎn)
struct NODE* PTEMP = (struct NODE*)malloc(sizeof(struct NODE));
if (PTEMP != NULL)
{
//節(jié)點(diǎn)賦值
PTEMP->shu_ju = SHU_JU;
PTEMP->PNext = NULL;
//把結(jié)點(diǎn)連起來(lái)
if (NULL == *PHEAD) // 因?yàn)镻HEAD如果是NULL的話 PEND也就是NULL 所以條件里面不必要寫(xiě)
{
*PHEAD = PTEMP;
*PEND = PTEMP;
}
else
{
(*PEND)->PNext = PTEMP;
*PEND = PTEMP;
}
}
}
//尾添加(沒(méi)有尾指針)
void wei_tian_jia_(struct NODE** PHEAD1, int SHU_JU)
{
//創(chuàng)建結(jié)點(diǎn)
struct NODE* PTEMP = (struct NODE*)malloc(sizeof(struct NODE));
if (PTEMP != NULL)
{
//結(jié)點(diǎn)成員賦值
PTEMP->shu_ju = SHU_JU;
PTEMP->PNext = NULL;
//把結(jié)點(diǎn)連一起
if (NULL == *PHEAD1)
{
*PHEAD1 = PTEMP;
}
else
{
struct NODE* PTEMP2 = *PHEAD1;
while (PTEMP2->PNext != NULL)
{
PTEMP2 = PTEMP2->PNext;
}
PTEMP2->PNext = PTEMP;
}
}
}
//輸出鏈表
void shu_chu(struct NODE* PHEAD)
{
while (PHEAD != NULL)
{
printf("%d\n", PHEAD->shu_ju);
PHEAD = PHEAD->PNext;
}
}
//釋放鏈表
void shi_fang_lian_biao(struct NODE* PHEAD)
{
struct NODE* P = PHEAD;
while (PHEAD != NULL)
{
struct NODE* PTEMP = P;
P = P->PNext;
free(PTEMP);
}
free(PHEAD);
}
//釋放鏈表(并是頭指針(PHead)尾指針(PEnd)指向空)
void shi_fang_lian_biao_free(struct NODE** PHEAD, struct NODE** PEnd)
{
while (*PHEAD != NULL)
{
struct NODE* PTEMP = *PHEAD;
*PHEAD = (*PHEAD)->PNext;
free(PTEMP);
}
*PHEAD = NULL;
*PHEAD = NULL;
}
部分代碼詳解：(再次申明：由于作者水平有限，所以有的變量名用的拼音。見(jiàn)笑，莫怪?。?！為了簡(jiǎn)單明了，方便起見(jiàn)，我定義了一個(gè)實(shí)際數(shù)據(jù)。)
“頭指針”(PHead)以及“尾指針”(PEnd)：
頭指針很好理解指向首結(jié)點(diǎn)用于遍歷整個(gè)數(shù)組，而尾指針呢？我們先看下面兩段代碼一段是有尾指針的一段是沒(méi)有尾指針的：
//尾添加
void wei_tian_jia(struct NODE** PHEAD, struct NODE** PEND, int SHU_JU)
{
//創(chuàng)建一個(gè)結(jié)點(diǎn)
struct NODE* PTEMP = (struct NODE*)malloc(sizeof(struct NODE));
if (PTEMP != NULL)
{
//節(jié)點(diǎn)成員賦值（一定要每個(gè)成員都要賦值）
PTEMP->shu_ju = SHU_JU;
PTEMP->PNext = NULL;
//把結(jié)點(diǎn)連起來(lái)
if (NULL == *PHEAD) // 因?yàn)镻HEAD如果是NULL的話 PEND也就是NULL 所以條件里面不必要寫(xiě)
{
*PHEAD = PTEMP;
*PEND = PTEMP;
}
else
{
//把尾指針向后移
(*PEND)->PNext = PTEMP;
*PEND = PTEMP;
}
}
}
那么下面這段代碼是沒(méi)有尾指針的。它的思想就是頭指針一直指向第一個(gè)結(jié)點(diǎn)，然后通過(guò)遍歷來(lái)找到最后一個(gè)結(jié)點(diǎn)，從而使最后一個(gè)結(jié)點(diǎn)里面的指針指向所要插入的元素。
//尾添加(沒(méi)有尾指針)
void wei_tian_jia_(struct NODE** PHEAD1, int SHU_JU)
{
//創(chuàng)建結(jié)點(diǎn)
struct NODE* PTEMP = (struct NODE*)malloc(sizeof(struct NODE));
if (PTEMP != NULL)
{
//結(jié)點(diǎn)成員賦值
PTEMP->shu_ju = SHU_JU;
PTEMP->PNext = NULL;
//把結(jié)點(diǎn)連一起
if (NULL == *PHEAD1)
{
*PHEAD1 = PTEMP;
}
else
{
struct NODE* PTEMP2 = *PHEAD1;
while (PTEMP2->PNext != NULL)
{
PTEMP2 = PTEMP2->PNext;
}
PTEMP2->PNext = PTEMP;
}
}
}
我把上面代碼里面的一段摘出來(lái)說(shuō)明一下。
這段代碼里面可以看到我又定義了一個(gè)PTEMP2指針變量，為什么呢？前面我提到過(guò)沒(méi)有尾指針的時(shí)候添加結(jié)點(diǎn)的思想就是要遍歷數(shù)組，從而找到最后一個(gè)結(jié)點(diǎn)然后讓它指向我們要插入的結(jié)點(diǎn)，如果沒(méi)有這個(gè)PHEAD2，我們遍歷完鏈表以后我們的頭指針PHEAD1就已經(jīng)指向了最后一個(gè)結(jié)點(diǎn)了，單項(xiàng)鏈表如果頭指針移動(dòng)了，數(shù)據(jù)就會(huì)找不到了。所以我定義了一個(gè)中間變量裝著頭指針然后去遍歷鏈表，讓頭指針永遠(yuǎn)指向鏈表的頭。
else
{
struct NODE* PTEMP2 = *PHEAD1;
while (PTEMP2->PNext != NULL)
{
PTEMP2 = PTEMP2->PNext;
}
PTEMP2->PNext = PTEMP;
}
可以看到有尾指針的代碼和沒(méi)有尾指針的代碼里面，有尾指針的鏈表里面我每次添加完數(shù)據(jù)都讓尾指針指向最后一個(gè)結(jié)點(diǎn)，然后通過(guò)尾指針來(lái)添加數(shù)據(jù)。而沒(méi)有尾指針的鏈表里面每次添加數(shù)據(jù)都要通過(guò)循環(huán)來(lái)遍歷鏈表找到最后一個(gè)結(jié)點(diǎn)然后指向所添加的結(jié)點(diǎn)。如果一個(gè)鏈表里面有幾萬(wàn)個(gè)結(jié)點(diǎn)，每次都通過(guò)循環(huán)遍歷鏈表來(lái)添加數(shù)據(jù)，那么速度就相對(duì)于有尾指針的鏈表慢很多?？偠灾€是看個(gè)人愛(ài)好吧。不管黑貓還是白貓能抓到耗子都是好貓。
總結(jié)
到此這篇關(guān)于c語(yǔ)言單鏈表尾添加的文章就介紹到這了,更多相關(guān)c語(yǔ)言單鏈表尾添加內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
閉包有很多種定義，一種說(shuō)法是，閉包是帶有上下文的函數(shù)。說(shuō)白了，就是有狀態(tài)的函數(shù)。更直接一些，不就是個(gè)類(lèi)嗎？換了個(gè)名字而已。本文將介紹c++11閉包的實(shí)現(xiàn)，感興趣的同學(xué)，可以參考下。2021-06-06
C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的推箱子小游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的推箱子小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-07-07
C語(yǔ)言16進(jìn)制與ASCII字符相互轉(zhuǎn)換
大家好，本篇文章主要講的是C語(yǔ)言16進(jìn)制與ASCII字符相互轉(zhuǎn)換，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下2022-01-01
c++中cin/cout與scanf/printf的區(qū)別比較
這篇文章主要介紹了c++中cin/cout與scanf/printf的區(qū)別比較,需要的朋友可以參考下2017-06-06
解決Qt設(shè)置QTextEdit行高的問(wèn)題
這篇文章介紹了Qt設(shè)置QTextEdit行高的方法，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-04-04
C語(yǔ)言實(shí)現(xiàn)簡(jiǎn)單的通訊錄管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)通訊錄管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
C語(yǔ)言實(shí)現(xiàn)單鏈表逆序與逆序輸出實(shí)例
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)單鏈表逆序與逆序輸出,是數(shù)據(jù)結(jié)構(gòu)與算法中比較基礎(chǔ)的重要內(nèi)容,有必要加以牢固掌握,需要的朋友可以參考下2014-08-08
這篇文章主要介紹了C++泛型編程函(數(shù)模板+類(lèi)模板),類(lèi)模板與函數(shù)模板一樣也會(huì)經(jīng)過(guò)兩次編譯,在此文中重點(diǎn)區(qū)分一下類(lèi)模板與模板類(lèi),函數(shù)模板與模板函數(shù)的概念,泛型編程是C++開(kāi)發(fā)的一大精髓,靈活地運(yùn)用泛型編程,需要的朋友可以參考一下2022-02-02
這篇文章主要介紹了C語(yǔ)言 聯(lián)合(union)用法案例詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
通過(guò)“回文字算法”復(fù)習(xí)C++語(yǔ)言
這篇文章主要介紹了通過(guò)“回文字算法”復(fù)習(xí)C++語(yǔ)言的相關(guān)資料,非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友可以參考下2016-10-10