柚子快報(bào)邀請(qǐng)碼778899分享:數(shù)據(jù)結(jié)構(gòu)之單鏈表(C語言)
柚子快報(bào)邀請(qǐng)碼778899分享:數(shù)據(jù)結(jié)構(gòu)之單鏈表(C語言)
數(shù)據(jù)結(jié)構(gòu)之單鏈表(C語言)
1 鏈表的概念2 節(jié)點(diǎn)創(chuàng)建函數(shù)與鏈表打印函數(shù)2.1 節(jié)點(diǎn)創(chuàng)建函數(shù)2.2 鏈表打印函數(shù)
3 單鏈表尾插法與頭插法3.1 尾插函數(shù)3.2 頭插函數(shù)
4 單鏈表尾刪法與頭刪法4.1 尾刪函數(shù)4.2 頭刪函數(shù)
5 指定位置的插入與刪除5.1 在指定位置之前插入數(shù)據(jù)5.2 在指定位置之后插入數(shù)據(jù)5.3 刪除指定位置節(jié)點(diǎn)5.4 刪除指定位置之后節(jié)點(diǎn)
6 鏈表數(shù)據(jù)的查找與鏈表的銷毀6.1 鏈表數(shù)據(jù)的查找6.2 鏈表的銷毀
7 單鏈表全程序及演示結(jié)果7.1 SList.h 文件7.2 SList.c 文件7.3 SList_test.c 文件
1 鏈表的概念
鏈表是線性表的一種,其物理存儲(chǔ)結(jié)構(gòu)上是非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)元素的邏輯存儲(chǔ)結(jié)構(gòu)是通過鏈表中指針鏈接次序?qū)崿F(xiàn)的。即鏈表中: (1)物理結(jié)構(gòu):不是線性的 (2)邏輯結(jié)構(gòu):一定是線性的 鏈表是由一個(gè)一個(gè)節(jié)點(diǎn)(結(jié)點(diǎn))構(gòu)成的,可以類比春運(yùn)前與春運(yùn)后火車的車廂數(shù)量,每一個(gè)車廂都可看作是一個(gè)節(jié)點(diǎn),春運(yùn)時(shí)就增加車廂數(shù)(節(jié)點(diǎn)數(shù))來運(yùn)送更多乘客(存儲(chǔ)更多數(shù)據(jù)),非春運(yùn)時(shí)就減少車廂數(shù),可保證基本運(yùn)作即可。 單鏈表中每一個(gè)節(jié)點(diǎn)是由兩部分組成,第一是該節(jié)點(diǎn)所要存儲(chǔ)的數(shù)據(jù),第二是該節(jié)點(diǎn)所指向的下一個(gè)節(jié)點(diǎn)的指針(地址)。 具體代碼如下:
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;//指向下一節(jié)點(diǎn)指針
//在指向下一節(jié)點(diǎn)指針這里,它的類型要用重命名前的結(jié)構(gòu)體類型
}SLTNode;
注意,在指向下一節(jié)點(diǎn)指針這里,它的類型之所以不能使用重命名后的結(jié)構(gòu)體類型SLTNode是因?yàn)樵谙到y(tǒng)讀取到該行時(shí)還沒完成重命名的操作,故只能使用重命名前的名稱struct SListNode來定義類型。
2 節(jié)點(diǎn)創(chuàng)建函數(shù)與鏈表打印函數(shù)
2.1 節(jié)點(diǎn)創(chuàng)建函數(shù)
在上面我們只是定義了節(jié)點(diǎn)的結(jié)構(gòu),但并沒有真正創(chuàng)建節(jié)點(diǎn)。故我們自定義一個(gè)函數(shù)來完成這部分操作。既然要?jiǎng)?chuàng)建節(jié)點(diǎn),那么就需要申請(qǐng)空間,因?yàn)榇藭r(shí)不同于數(shù)組擴(kuò)容,鏈表的物理結(jié)構(gòu)并不是連續(xù)的,而是可以通過指針將每一個(gè)碎片化的節(jié)點(diǎn)連接起來,所以直接使用malloc來進(jìn)行空間申請(qǐng)即可。這一部分與順序表中的空間檢查函數(shù)很相似。
//節(jié)點(diǎn)創(chuàng)建函數(shù)
SLTNode* SLTBuyNode(SLTDataType x)//形參部分為data要初始化的值
//下一節(jié)點(diǎn)部分也不知道指向哪里,先置為NULL即可
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//malloc申請(qǐng)單鏈表節(jié)點(diǎn)空間
if (newnode == NULL)//如果申請(qǐng)失敗,跳出函數(shù)
{
perror("malloc fail !");
exit(1);
}
//申請(qǐng)成功則進(jìn)行對(duì)應(yīng)的初始化
newnode->data = x;
newnode->next = NULL;//指向下一節(jié)點(diǎn)部分置為空
return newnode;//將創(chuàng)建的節(jié)點(diǎn)作為返回值返回到調(diào)用處
}
2.2 鏈表打印函數(shù)
在上文中我們已知,鏈表是靠指針來完成次序的連接,其無法做到任意訪問,而是必須先訪問前一個(gè)節(jié)點(diǎn)后再去訪問后一個(gè)節(jié)點(diǎn)。比如,我們將第一個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的節(jié)點(diǎn)地址設(shè)為phead,那么下一個(gè)節(jié)點(diǎn)就是phead->next,再后面一個(gè)節(jié)點(diǎn)為phead->next->next,以此類推。 在上面的那種訪問方式中,當(dāng)我們要訪問第n個(gè)節(jié)點(diǎn)時(shí),phead后面會(huì)跟(n-1)個(gè)next。如此就顯得非常冗余,所以我們可以另辟蹊徑,用一個(gè)臨時(shí)節(jié)點(diǎn)來做為過度節(jié)點(diǎn)(我們?cè)O(shè)為pcur),將鏈表的頭節(jié)點(diǎn)賦值給pcur,然后通過循環(huán)讓pcur不斷指向后面的next完成對(duì)鏈表的遍歷。實(shí)現(xiàn)如下:
SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
//通過一個(gè)過渡節(jié)點(diǎn)的嫁接轉(zhuǎn)換完成對(duì)鏈表的遍歷訪問
while (pcur)//等價(jià)于pcur != NULL
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
//如果傳過來的本來就是空節(jié)點(diǎn),那么就無法進(jìn)入循環(huán),打印為空
printf("NULL\n");
}
3 單鏈表尾插法與頭插法
3.1 尾插函數(shù)
在原鏈表之尾插入一個(gè)新的節(jié)點(diǎn),首先我們要調(diào)用節(jié)點(diǎn)創(chuàng)建函數(shù)建立一個(gè)新的節(jié)點(diǎn),然后對(duì)原鏈表進(jìn)行遍歷找尾,最后將尾節(jié)點(diǎn)的next指向新創(chuàng)建的節(jié)點(diǎn)即可。 請(qǐng)審讀下面尾插函數(shù),分析其是否存在問題。
SLTNode* PushBack(SLTNode* phead, SLTDataType x)
{
//判斷傳參是否為空
assert(phead);
//創(chuàng)建要尾插的節(jié)點(diǎn)
SLTNode* newnode = SLTBuyNode(x);
//找尾
SLTNode* ptail = phead;
//思考此處循環(huán)判斷條件應(yīng)該是什么
while (ptail->next)
//若將ptail != NULL 設(shè)置為條件,當(dāng)循環(huán)到尾節(jié)點(diǎn)時(shí),此時(shí)不為空,會(huì)繼續(xù)到后面的空節(jié)點(diǎn),而此時(shí)這個(gè)空節(jié)點(diǎn)就不是鏈表的尾節(jié)點(diǎn)了。
//故應(yīng)設(shè)置為ptail->next != NULL,當(dāng)循環(huán)到尾節(jié)點(diǎn)時(shí),ptail->next == NULL 跳出循環(huán),然后再將ptail->next賦值為newnode即完成尾插。
{
ptail = ptail->next;//沒找到尾節(jié)點(diǎn)就不斷向后遍歷
}
ptail->next = newnode;
}
上面尾插程序看似十分完美,其實(shí)存在兩點(diǎn)嚴(yán)重的問題:
當(dāng)鏈表為空鏈表時(shí),phead與ptail都會(huì)成為空指針NULL,那么在while中的條件判斷就成為了對(duì)空指針解引用的非法訪問。在尾插函數(shù)中,我們想通過修改形參中的鏈表來完成實(shí)參中鏈表的修改,那么在形參中可以用一級(jí)指針接收傳參嗎?用一級(jí)指針接收傳參可以保證實(shí)參改變嗎?
我們先來解決第一個(gè)問題,既然有空鏈表的這種情況,那么就使用一個(gè)條件分支來區(qū)別二者(空鏈表與非空鏈表)。
void PushBack(SLTNode* phead, SLTDataType x)
{
//判斷傳參是否為空
assert(phead);
//創(chuàng)建要尾插的節(jié)點(diǎn)
SLTNode* newnode = SLTBuyNode(x);
//空鏈表與非空鏈表區(qū)分
if (phead == NULL)
{
phead = newnode;
}
else
{
//找尾
SLTNode* ptail = phead;
//思考此處循環(huán)判斷條件應(yīng)該是什么
while (ptail->next)
//若將ptail != NULL 設(shè)置為條件,當(dāng)循環(huán)到尾節(jié)點(diǎn)時(shí),此時(shí)不為空,會(huì)繼續(xù)到后面的空節(jié)點(diǎn),而此時(shí)這個(gè)空節(jié)點(diǎn)就不是鏈表的尾節(jié)點(diǎn)了。
//故應(yīng)設(shè)置為ptail->next != NULL,當(dāng)循環(huán)到尾節(jié)點(diǎn)時(shí),ptail->next == NULL 跳出循環(huán),然后再將ptail->next賦值為newnode即完成尾插。
{
ptail = ptail->next;//沒找到尾節(jié)點(diǎn)就不斷向后遍歷
}
ptail->next = newnode;
}
}
然后我們?cè)賮斫鉀Q第二個(gè)問題,形參如果想要影響實(shí)參的內(nèi)容,我們傳參時(shí)就要傳地址而不是傳數(shù)值(即使用傳址調(diào)用)。測(cè)試文件中內(nèi)容如下:
void Test01()
{
SLTNode* plist = NULL;
SLTDataType x = 1;
PushBack(plist, x);
SLTPrint(plist);
}
int main()
{
Test01();
return 0;
}
在傳參時(shí)我們是將plist作為實(shí)參,而plist是一個(gè)一級(jí)指針,其存儲(chǔ)的是后面的空地址NULL。所以在傳參時(shí)phead所接收的是plist所指向的NULL,屬于傳值調(diào)用。在前面函數(shù)已經(jīng)講過,傳值調(diào)用時(shí)函數(shù)會(huì)在棧區(qū)開創(chuàng)棧幀空間來存儲(chǔ)形參及函數(shù)內(nèi)參數(shù),也就是在棧幀空間內(nèi)某一塊空間被置為NULL,然后再由phead來存儲(chǔ)。此時(shí)無論phead怎么改變,都與原來的plist毫無關(guān)系了,形參也就無法影響實(shí)參了。 所以在傳參時(shí)我們不能傳plist(等于傳值),而是要傳plist的地址(&plist)。相應(yīng)的,因?yàn)閭鬟f的是一級(jí)指針的地址,所以在形參部分接收頭節(jié)點(diǎn)的形參要使用二級(jí)指針(我們將其命名為pphead)。 最終尾插函數(shù)如下:
void PushBack(SLTNode** pphead, SLTDataType x)
{
//判斷傳參是否為空
assert(pphead);
//創(chuàng)建要尾插的節(jié)點(diǎn)
SLTNode* newnode = SLTBuyNode(x);
//空鏈表與非空鏈表區(qū)分
if (*pphead == NULL)//等同于原來 phead == NULL。也等同于plist == NULL
{
*pphead = newnode;//等同于原來的phead == newnode。也等同于plist == newnode
}
else
{
//找尾
SLTNode* ptail = *pphead;
//思考此處循環(huán)判斷條件應(yīng)該是什么
while (ptail->next)
//若將ptail != NULL 設(shè)置為條件,當(dāng)循環(huán)到尾節(jié)點(diǎn)時(shí),此時(shí)不為空,會(huì)繼續(xù)到后面的空節(jié)點(diǎn),而此時(shí)這個(gè)空節(jié)點(diǎn)就不是鏈表的尾節(jié)點(diǎn)了。
//故應(yīng)設(shè)置為ptail->next != NULL,當(dāng)循環(huán)到尾節(jié)點(diǎn)時(shí),ptail->next == NULL 跳出循環(huán),然后再將ptail->next賦值為newnode即完成尾插。
{
ptail = ptail->next;//沒找到尾節(jié)點(diǎn)就不斷向后遍歷
}
ptail->next = newnode;
}
}
在經(jīng)過上面修改后,傳參時(shí)一級(jí)指針的地址&plist作為實(shí)參,形參處的二級(jí)指針pphead來接收實(shí)參,形參實(shí)例化后開創(chuàng)棧幀來存儲(chǔ)一級(jí)指針地址&plist,后續(xù)我們對(duì)pphead解引用操作時(shí)(*pphead),操作的就是測(cè)試文件中的一級(jí)指針plist,完成形參改變實(shí)參的操作。
3.2 頭插函數(shù)
在原鏈表之頭插入一個(gè)節(jié)點(diǎn),我們?cè)谡{(diào)用節(jié)點(diǎn)創(chuàng)建函數(shù)后只需要將新節(jié)點(diǎn)newnode->next賦值為存儲(chǔ)鏈表頭節(jié)點(diǎn)地址的一級(jí)指針plist,然后再將一級(jí)指針newnode賦值給plist就完成了頭節(jié)點(diǎn)的轉(zhuǎn)換。 具體如下:
void PushFront(SLTNode** pphead, SLTDataType x)
{
//判斷傳參是否為空
assert(pphead);
//創(chuàng)建要尾插的節(jié)點(diǎn)
SLTNode* newnode = SLTBuyNode(x);
//進(jìn)行頭插
newnode->next = *pphead;//將新節(jié)點(diǎn)next指向原頭節(jié)點(diǎn)的地址
*pphead = newnode;//將原頭節(jié)點(diǎn)的地址更改為新節(jié)點(diǎn)的地址
}
4 單鏈表尾刪法與頭刪法
4.1 尾刪函數(shù)
我們先來思考一下,能否從頭遍歷鏈表后直接free掉尾節(jié)點(diǎn)? 答案肯定是不能的。鏈表的每一節(jié)點(diǎn)間都通過next指針相連,若直接free掉尾節(jié)點(diǎn),那么尾節(jié)點(diǎn)前面一個(gè)節(jié)點(diǎn)的next指針就會(huì)指向一塊未初始化的空間,成為野指針。所以我們需要定義兩個(gè)指針,一個(gè)是尾節(jié)點(diǎn)ptail,另一個(gè)是尾節(jié)點(diǎn)前面一個(gè)節(jié)點(diǎn)prev,free掉尾節(jié)點(diǎn)后,將ptail置為NULL,再將prev->next置為NULL。
void PopBack(SLTNode** pphead)
{
//不僅要判斷參數(shù)是否為空,還要判斷是否為空鏈表。
assert(pphead && *pphead);
//定義需要使用的兩個(gè)節(jié)點(diǎn)指針
SLTNode* prev = *pphead;
SLTNode* ptail = *pphead;
//遍歷單鏈表找尾
while (ptail->next)
{
//尋找尾節(jié)點(diǎn)和其前一個(gè)節(jié)點(diǎn)
prev = ptail;
ptail = ptail->next;
}
free(ptail);
//釋放空間后將兩處置為NULL
ptail = NULL;
prev->next = NULL;
}
在上面的邏輯中,情況是否全面不妨和前面一樣,使用極端情況來檢驗(yàn)??真湵淼那闆r下會(huì)被assert斷言發(fā)現(xiàn),故被排除。那在只有一個(gè)節(jié)點(diǎn)時(shí)呢?因?yàn)閜tail->next為空,故不進(jìn)入循環(huán)。直接free并置為NULL,所以ptail與prev都為NULL。但是后面prev->next卻又對(duì)空指針進(jìn)行了非法訪問,造成出錯(cuò)。故應(yīng)在邏輯中分為鏈表只有一個(gè)節(jié)點(diǎn)和有多個(gè)節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)時(shí)直接free并置空,多個(gè)節(jié)點(diǎn)使在執(zhí)行上面程序。 最終程序如下:
void PopBack(SLTNode** pphead)//與前面一樣,為了形參能改變實(shí)參,使用二級(jí)指針來接收頭節(jié)點(diǎn)指針地址
{
//不僅要判斷參數(shù)是否為空,還要判斷是否為空鏈表。
assert(pphead && *pphead);
//定義需要使用的兩個(gè)節(jié)點(diǎn)指針
SLTNode* prev = *pphead;
SLTNode* ptail = *pphead;
//鏈表有一個(gè)節(jié)點(diǎn)
if ((*pphead)->next == NULL)// -> 優(yōu)先級(jí)高于 *
{
free(*pphead);
*pphead = NULL;
}
//鏈表有多個(gè)節(jié)點(diǎn)
else
{
//遍歷單鏈表找尾
while (ptail->next)
{
//尋找尾節(jié)點(diǎn)和其前一個(gè)節(jié)點(diǎn)
prev = ptail;
ptail = ptail->next;
}
free(ptail);
//釋放空間后將兩處置為NULL
ptail = NULL;
prev->next = NULL;
}
}
4.2 頭刪函數(shù)
刪掉單鏈表頭節(jié)點(diǎn)只需要將頭節(jié)點(diǎn)的next指針指向地址保留下來,釋放頭節(jié)點(diǎn)空間,然后將方才保留的地址轉(zhuǎn)換為頭節(jié)點(diǎn)地址即可。
void PopFront(SLTNode** pphead)
{
//不僅要判斷參數(shù)是否為空,還要判斷是否為空鏈表。
assert(pphead && *pphead);
//保留頭節(jié)點(diǎn)next節(jié)點(diǎn)指針
SLTNode* next = (*pphead)->next;
free(*pphead);
//將保留的節(jié)點(diǎn)指針作為頭節(jié)點(diǎn)指針,完成頭節(jié)點(diǎn)轉(zhuǎn)換
*pphead = next;
}
5 指定位置的插入與刪除
5.1 在指定位置之前插入數(shù)據(jù)
在指定位置之前插入數(shù)據(jù),首先我們思考一下,指定位置若是頭節(jié)點(diǎn),此時(shí)其就是頭插法插入(特殊情況)。除此之外,我們?nèi)粼谥付ㄎ恢弥爸苯硬迦胄鹿?jié)點(diǎn),那么指定位置之前原來的節(jié)點(diǎn)就會(huì)與pos節(jié)點(diǎn)斷開。所以我們需要找到前一個(gè)節(jié)點(diǎn)地址,將前一個(gè)節(jié)點(diǎn)next指針指向newnode,newnode->next指向pos節(jié)點(diǎn),如此完成連接。 具體見下:
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
//雙判空
assert(pphead && *pphead);
//插入值判空
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
//若 pos == *pphead ,說明是頭插
if (pos == *pphead)
{
PushFront(pphead, x);
}
else
//非頭插,將前一個(gè)節(jié)點(diǎn)prev與newnode連接,newnode與pos連接
{
SLTNode* prev = *pphead;
//尋找pos前一個(gè)節(jié)點(diǎn)
while (prev->next != pos)
{
prev = prev->next;
}
//節(jié)點(diǎn)連接
newnode->next = pos;
prev->next = newnode;
}
}
5.2 在指定位置之后插入數(shù)據(jù)
在指定位置之后插入數(shù)據(jù)我們通過前文的講述,自然會(huì)先考慮到尾插的情況,在pos 在尾節(jié)點(diǎn)時(shí),pos->next == NULL,我們將pos->next直接賦值給newnode->next,然后將pos與newnode連接即可(pos->next==newnode)。在尾插情況之外,通過上面的連接操作同樣可以完成插入數(shù)據(jù),故不需要使用條件分支。 具體見下:
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
//雙重判空
assert(pphead && *pphead);
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
//進(jìn)行插入操作
//將pos節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)地址賦值給新節(jié)點(diǎn) newnode 的 next 指針
newnode->next = pos->next;
//將pos節(jié)點(diǎn)的next指針指向新節(jié)點(diǎn)newnode
pos->next = newnode;
}
5.3 刪除指定位置節(jié)點(diǎn)
在pos節(jié)點(diǎn)為頭結(jié)點(diǎn),此時(shí)刪除操作符合頭刪法,即調(diào)用頭刪函數(shù)即可。除此情況之外,我們需要將pos前一個(gè)節(jié)點(diǎn)與后一個(gè)節(jié)點(diǎn)連接后再釋放pos節(jié)點(diǎn)。 具體見下:
//刪除指定位置pos節(jié)點(diǎn)
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && *pphead);
assert(pos);
//若 pos == *pphead,此時(shí)就是頭刪法刪除
if (pos == *pphead)
{
PopFront(pos);
}
else
//刪除指定位置節(jié)點(diǎn)需要我們將pos之前與pos之后的節(jié)點(diǎn)連接起來
{
SLTNode* prev = *pphead;
//尋找pos前一個(gè)節(jié)點(diǎn)
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
5.4 刪除指定位置之后節(jié)點(diǎn)
與前面操作如出一轍,我們將pos與其后兩個(gè)節(jié)點(diǎn)連接,最后再釋放pos后一個(gè)節(jié)點(diǎn)置空即可。但在此處我們需要考慮pos是不是尾節(jié)點(diǎn),即pos->next是否等于NULL。 具體見下:
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && *pphead);
//判斷傳參 pos 是否為空以及 pos 是不是最后一個(gè)節(jié)點(diǎn)
assert(pos && pos->next);
//先將pos之后的節(jié)點(diǎn)用del存儲(chǔ)下來
SLTNode* del = pos->next;
//將pos與pos后第二個(gè)節(jié)點(diǎn)連接起來
pos->next = del->next;//pos->next = pos->next->next
free(del);
del = NULL;
}
6 鏈表數(shù)據(jù)的查找與鏈表的銷毀
6.1 鏈表數(shù)據(jù)的查找
與順序表的查找如出一轍,對(duì)整個(gè)鏈表遍歷即可。找到就返回該節(jié)點(diǎn),沒找到就返回NULL。
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* pcur = phead;
//查找節(jié)點(diǎn)
while (pcur)
{
//找到節(jié)點(diǎn)直接返回
if (pcur->data == x)
{
return pcur;
}
//沒找到向后遍歷
pcur = pcur->next;
}
//遍歷后不存在,返回空表示沒找到
return NULL;
}
6.2 鏈表的銷毀
在對(duì)鏈表每個(gè)節(jié)點(diǎn)釋放之前,我們需要先保留該節(jié)點(diǎn)的next指針的指向,從而能夠銷毀后續(xù)節(jié)點(diǎn)。
void SLTDestroy(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
//定義 next節(jié)點(diǎn)以保留pcur->next的指向
SLTNode* next = pcur->next;
free(pcur);
//將保留的next節(jié)點(diǎn)賦值給pcur,進(jìn)而下一循環(huán)銷毀后續(xù)節(jié)點(diǎn)
pcur = next;
}
//全部銷毀后將鏈表置為空
*pphead = NULL;
}
7 單鏈表全程序及演示結(jié)果
7.1 SList.h 文件
#pragma once
#include
#include
#include
//類型重命名
typedef int SLTDataType;
//定義節(jié)點(diǎn)結(jié)構(gòu)
//數(shù)據(jù) + 指向下一節(jié)點(diǎn)指針
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;//指向下一節(jié)點(diǎn)指針
//在指向下一節(jié)點(diǎn)指針這里,它的類型要用重命名前的結(jié)構(gòu)體類型
}SLTNode;
//節(jié)點(diǎn)創(chuàng)建函數(shù)
SLTNode* SLTBuyNode(SLTDataType x);
//鏈表打印函數(shù)
void SLTPrint(SLTNode* phead);
//尾插函數(shù)
void PushBack(SLTNode** pphead, SLTDataType x);
//頭插函數(shù)
void PushFront(SLTNode** pphead, SLTDataType x);
//尾刪函數(shù)
void PopBack(SLTNode** pphead);
//頭刪函數(shù)
void PopFront(SLTNode** pphead);
//在指定位置之前插入數(shù)據(jù)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入數(shù)據(jù)
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//刪除pos節(jié)點(diǎn)
void SLTErase(SLTNode** pphead, SLTNode* pos);
//刪除pos之后節(jié)點(diǎn)
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos);
//鏈表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//銷毀鏈表
void SLTDestroy(SLTNode** pphead);
7.2 SList.c 文件
#include"SList.h"
//節(jié)點(diǎn)創(chuàng)建函數(shù)
SLTNode* SLTBuyNode(SLTDataType x)//形參部分為data要初始化的值
//下一節(jié)點(diǎn)部分也不知道指向哪里,先置為NULL即可
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//malloc申請(qǐng)單鏈表節(jié)點(diǎn)空間
if (newnode == NULL)//如果申請(qǐng)失敗,跳出函數(shù)
{
perror("malloc fail !");
exit(1);
}
//申請(qǐng)成功則進(jìn)行對(duì)應(yīng)的初始化
newnode->data = x;
newnode->next = NULL;//指向下一節(jié)點(diǎn)部分置為空
return newnode;//將創(chuàng)建的節(jié)點(diǎn)作為返回值返回到調(diào)用處
}
//鏈表的打印
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
//通過一個(gè)過渡節(jié)點(diǎn)的嫁接轉(zhuǎn)換完成對(duì)鏈表的遍歷訪問
while (pcur)//等價(jià)于pcur != NULL
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
//如果傳過來的本來就是空節(jié)點(diǎn),那么就無法進(jìn)入循環(huán),打印為空
printf("NULL\n");
}
//鏈表的尾插法
void PushBack(SLTNode** pphead, SLTDataType x)
{
//判斷傳參是否為空
assert(pphead);
//創(chuàng)建要尾插的節(jié)點(diǎn)
SLTNode* newnode = SLTBuyNode(x);
//空鏈表與非空鏈表區(qū)分
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾
SLTNode* ptail = *pphead;
//思考此處循環(huán)判斷條件應(yīng)該是什么
while (ptail->next)
//若將ptail != NULL 設(shè)置為條件,當(dāng)循環(huán)到尾節(jié)點(diǎn)時(shí),此時(shí)不為空,會(huì)繼續(xù)到后面的空節(jié)點(diǎn),而此時(shí)這個(gè)空節(jié)點(diǎn)就不是鏈表的尾節(jié)點(diǎn)了。
//故應(yīng)設(shè)置為ptail->next != NULL,當(dāng)循環(huán)到尾節(jié)點(diǎn)時(shí),ptail->next == NULL 跳出循環(huán),然后再將ptail->next賦值為newnode即完成尾插。
{
ptail = ptail->next;//沒找到尾節(jié)點(diǎn)就不斷向后遍歷
}
ptail->next = newnode;
}
}
//鏈表的頭插法
void PushFront(SLTNode** pphead, SLTDataType x)
{
//判斷傳參是否為空
assert(pphead);
//創(chuàng)建要尾插的節(jié)點(diǎn)
SLTNode* newnode = SLTBuyNode(x);
//進(jìn)行頭插
newnode->next = *pphead;//將新節(jié)點(diǎn)next指向原頭節(jié)點(diǎn)的地址
*pphead = newnode;//將原頭節(jié)點(diǎn)的地址更改為新節(jié)點(diǎn)的地址
}
//鏈表的尾刪法
void PopBack(SLTNode** pphead)
{
//不僅要判斷參數(shù)是否為空,還要判斷是否為空鏈表。
assert(pphead && *pphead);
//定義需要使用的兩個(gè)節(jié)點(diǎn)指針
SLTNode* prev = *pphead;
SLTNode* ptail = *pphead;
//鏈表有一個(gè)節(jié)點(diǎn)
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
//鏈表有多個(gè)節(jié)點(diǎn)
else
{
//遍歷單鏈表找尾
while (ptail->next)
{
//尋找尾節(jié)點(diǎn)和其前一個(gè)節(jié)點(diǎn)
prev = ptail;
ptail = ptail->next;
}
free(ptail);
//釋放空間后將兩處置為NULL
ptail = NULL;
prev->next = NULL;
}
}
//鏈表的頭刪法
void PopFront(SLTNode** pphead)
{
//不僅要判斷參數(shù)是否為空,還要判斷是否為空鏈表。
assert(pphead && *pphead);
//保留頭節(jié)點(diǎn)next節(jié)點(diǎn)指針
SLTNode* next = (*pphead)->next;
free(*pphead);
//將保留的節(jié)點(diǎn)指針作為頭節(jié)點(diǎn)指針,完成頭節(jié)點(diǎn)轉(zhuǎn)換
*pphead = next;
}
//在指定位置之前插入數(shù)據(jù)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
//雙判空
assert(pphead && *pphead);
//插入值判空
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
//若 pos == *pphead ,說明是頭插
if (pos == *pphead)
{
PushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
}
//在指定位置之后插入數(shù)據(jù)
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
//雙重判空
assert(pphead && *pphead);
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
//進(jìn)行插入操作
//將pos節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)地址賦值給新節(jié)點(diǎn) newnode 的 next 指針
newnode->next = pos->next;
//將pos節(jié)點(diǎn)的next指針指向新節(jié)點(diǎn)newnode
pos->next = newnode;
}
//刪除指定位置pos節(jié)點(diǎn)
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && *pphead);
assert(pos);
//若 pos == *pphead,此時(shí)就是頭刪法刪除
if (pos == *pphead)
{
PopFront(pos);
}
else
//刪除指定位置節(jié)點(diǎn)需要我們將pos之前與pos之后的節(jié)點(diǎn)連接起來
{
SLTNode* prev = *pphead;
//尋找pos前一個(gè)節(jié)點(diǎn)
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
//刪除指定位置之后的節(jié)點(diǎn)
void SLTEraseAfter(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && *pphead);
//判斷傳參 pos 是否為空以及 pos 是不是最后一個(gè)節(jié)點(diǎn)
assert(pos && pos->next);
//先將pos之后的節(jié)點(diǎn)用del存儲(chǔ)下來
SLTNode* del = pos->next;
//將pos與pos后第二個(gè)節(jié)點(diǎn)連接起來
pos->next = del->next;//pos->next = pos->next->next
free(del);
del = NULL;
}
//銷毀鏈表
void SLTDestroy(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
//定義 next節(jié)點(diǎn)以保留pcur->next的指向
SLTNode* next = pcur->next;
free(pcur);
//將保留的next節(jié)點(diǎn)賦值給pcur,進(jìn)而下一循環(huán)銷毀后續(xù)節(jié)點(diǎn)
pcur = next;
}
//全部銷毀后將鏈表置為空
*pphead = NULL;
}
//鏈表的查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* pcur = phead;
//查找節(jié)點(diǎn)
while (pcur)
{
//找到節(jié)點(diǎn)直接返回
if (pcur->data == x)
{
return pcur;
}
//沒找到向后遍歷
pcur = pcur->next;
}
//遍歷后不存在,返回空表示沒找到
return NULL;
}
7.3 SList_test.c 文件
#include"SList.h"
void Test01()
{
SLTNode* plist = NULL;
SLTDataType x = 1;
PushBack(&plist, x);
PushBack(&plist, 2);
PushBack(&plist, 3);
PushBack(&plist, 4);
PushBack(&plist, 5);
SLTPrint(plist);
SLTNode* find = SLTFind(plist, 3);
if (find == NULL)
{
printf("沒有找到!\n");
}
else
{
printf("找到了!\n");
}
}
int main()
{
Test01();
return 0;
}
運(yùn)行結(jié)果: 全文至此結(jié)束!?。?寫作不易,不知各位老板能否給個(gè)一鍵三連或是一個(gè)免費(fèi)的贊呢(▽)(▽),這將是對(duì)我最大的肯定與支持?。?!謝謝!??!(▽)(▽)
柚子快報(bào)邀請(qǐng)碼778899分享:數(shù)據(jù)結(jié)構(gòu)之單鏈表(C語言)
推薦鏈接
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理,出于傳遞更多信息之目的,不代表金鑰匙跨境贊同其觀點(diǎn)和立場(chǎng)。
轉(zhuǎn)載請(qǐng)注明,如有侵權(quán),聯(lián)系刪除。