引入
在前面我們學(xué)習(xí)了順序表，順序表在數(shù)組的基礎(chǔ)上提供了很多現(xiàn)成的方法，方便了我們對(duì)數(shù)據(jù)的管理，但是我們也發(fā)現(xiàn)順序表有著許多不足：
在處理大型的數(shù)據(jù)時(shí)，需要頻繁的增容且在中間刪除或插入數(shù)據(jù)時(shí)需要遍歷順序表，這些性質(zhì)導(dǎo)致了順序表的效率較低。這時(shí)我們就可以使用另一種數(shù)據(jù)結(jié)構(gòu)--鏈表。
和順序表一樣，鏈表也是一種線性表。和順序表不同的是，雖然鏈表在邏輯上是連續(xù)的，鏈表在物理上并不是連續(xù)的。
既然物理上不是連續(xù)的，那么鏈表是怎么把一個(gè)個(gè)數(shù)據(jù)聯(lián)系到一起的呢？鏈表分為一個(gè)個(gè)節(jié)點(diǎn)，
每個(gè)節(jié)點(diǎn)通常由兩部分組成：數(shù)據(jù)域和指針域。
-
數(shù)據(jù)域（Data Field）：數(shù)據(jù)域存儲(chǔ)節(jié)點(diǎn)所需要的數(shù)據(jù)，可以是任意類(lèi)型的數(shù)據(jù)，如整數(shù)、字符串等。
-
指針域（Pointer Field）：指針域存儲(chǔ)指向下一個(gè)節(jié)點(diǎn)的指針，這個(gè)指針通常稱(chēng)為“后繼指針”或“next 指針”。
-
鏈表中的節(jié)點(diǎn)通過(guò)指針域相互連接起來(lái)，形成一個(gè)鏈?zhǔn)浇Y(jié)構(gòu)。當(dāng)我們創(chuàng)建一個(gè)新的節(jié)點(diǎn)時(shí)，我們將前一個(gè)節(jié)點(diǎn)的指針域指向新節(jié)點(diǎn)，從而將新節(jié)點(diǎn)連接到鏈表中。具體來(lái)說(shuō)，當(dāng)我們?cè)阪湵砦膊刻砑右粋€(gè)新節(jié)點(diǎn)時(shí)，我們將原來(lái)鏈表中最后一個(gè)節(jié)點(diǎn)的指針域指向這個(gè)新節(jié)點(diǎn)，從而將新節(jié)點(diǎn)連接到鏈表尾部。
鏈表的頭節(jié)點(diǎn)通常用來(lái)標(biāo)識(shí)整個(gè)鏈表的起始位置，而鏈表的最后一個(gè)節(jié)點(diǎn)的指針域通常指向一個(gè)特殊的值（如空值NULL），表示這是鏈表的末尾。鏈表中的節(jié)點(diǎn)通過(guò)指針域相互連接，形成一個(gè)動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu)，可以方便地進(jìn)行插入、刪除等操作，而不需要像數(shù)組一樣需要連續(xù)的內(nèi)存空間。
?單鏈表的實(shí)現(xiàn)
模塊劃分
和實(shí)現(xiàn)順序表一樣，分為三個(gè)文件來(lái)實(shí)現(xiàn)，SList..c用來(lái)實(shí)現(xiàn)順序表的各種方法，SList.h用來(lái)包含實(shí)現(xiàn)方法所需的頭文件和所需方法的初始化。test.c用來(lái)測(cè)試寫(xiě)的方法是否有問(wèn)題。
節(jié)點(diǎn)
實(shí)現(xiàn)鏈表的節(jié)點(diǎn)需要?jiǎng)?chuàng)建兩個(gè)變量，數(shù)據(jù)域用來(lái)儲(chǔ)存數(shù)據(jù)，指針域用來(lái)存放下一個(gè)節(jié)點(diǎn)的地址。我們用結(jié)構(gòu)體來(lái)實(shí)現(xiàn)。
typedef int SLTDatatype;//方便后面調(diào)整數(shù)據(jù)類(lèi)型
typedef struct SListNode
{
SLTDatatype data;
struct SListNode* next;
}SListNode;方法聲明
在SList.h中將需要實(shí)現(xiàn)的方法進(jìn)行聲明，同時(shí)包含需要的頭文件。
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//定義節(jié)點(diǎn)的結(jié)構(gòu)
//數(shù)據(jù) + 指向下一個(gè)節(jié)點(diǎn)的指針
typedef int SLTDataType;
typedef struct SListNode
{
SLTDataType data;
struct SListNode* next;
}SLTNode;
//鏈表的打印
void SLTPrint(SLTNode* phead);
//鏈表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾刪
void SLTPopBack(SLTNode** pphead);
//頭刪
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插入數(shù)據(jù)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType);
//在指定位置之后插入數(shù)據(jù)
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//刪除pos節(jié)點(diǎn)
void SLTErase(SLTNode** pphead,SLTNode* pos);
//刪除pos之后的節(jié)點(diǎn)
void SLTEraseAfter(SLTNode* pos);
//銷(xiāo)毀鏈表
void SListDesTroy(SLTNode** pphead)；方法實(shí)現(xiàn)
在SList.c中對(duì)需要的方法進(jìn)行實(shí)現(xiàn)。順序表的實(shí)現(xiàn)需要初始化，開(kāi)始就為順序表申請(qǐng)一塊內(nèi)存，而鏈表卻不需要。這是為什么呢？順序表需要初始化的主要原因是因?yàn)樗鼈冊(cè)趦?nèi)存中需要一段連續(xù)的存儲(chǔ)空間來(lái)存儲(chǔ)數(shù)據(jù)，而鏈表則不需要。
-
順序表：
- 順序表通常使用數(shù)組來(lái)實(shí)現(xiàn)，數(shù)組需要一塊連續(xù)的內(nèi)存空間來(lái)存儲(chǔ)元素。
- 在使用順序表之前，需要明確指定表的長(zhǎng)度（即數(shù)組的大小），以便系統(tǒng)為其分配一段連續(xù)的內(nèi)存空間。
- 初始化順序表時(shí)，需要為其分配內(nèi)存空間，并且要進(jìn)行一些必要的初始化操作，如將元素個(gè)數(shù)設(shè)置為0，以及初始化其他相關(guān)的變量。
- 如果不進(jìn)行初始化，順序表中的元素將會(huì)包含一些未知的隨機(jī)值，這可能導(dǎo)致程序出現(xiàn)錯(cuò)誤或者不可預(yù)測(cè)的行為。
-
鏈表：
- 鏈表由節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)可以在內(nèi)存中分散存儲(chǔ)，它們通過(guò)指針相互連接起來(lái)。
- 在使用鏈表時(shí)，不需要一開(kāi)始就為整個(gè)鏈表分配一段連續(xù)的內(nèi)存空間，節(jié)點(diǎn)可以動(dòng)態(tài)地在內(nèi)存中創(chuàng)建和刪除。
- 因此，鏈表在使用之前不需要像順序表那樣進(jìn)行顯式的初始化，只需要在插入第一個(gè)節(jié)點(diǎn)時(shí)，將鏈表的頭指針設(shè)置為該節(jié)點(diǎn)即可。
鏈表的打印
//鏈表的打印
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
//創(chuàng)建一個(gè)新的指針來(lái)遍歷，這樣不會(huì)改變phead
while (pcur)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("NULL\n");
}鏈表是由一個(gè)一個(gè)節(jié)點(diǎn)構(gòu)成的，我們可以手動(dòng)地創(chuàng)建幾個(gè)幾點(diǎn)并把它們連接起來(lái)，
//鏈表是由一個(gè)一個(gè)的節(jié)點(diǎn)組成
//創(chuàng)建幾個(gè)節(jié)點(diǎn)
SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
node1->data = 1;
SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
node2->data = 2;
SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
node3->data = 3;
SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
node4->data = 4;
//將四個(gè)節(jié)點(diǎn)連接起來(lái)
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = NULL;
//打印鏈表
SLTNode* plist = node1;
SLTPrint(plist);?我們來(lái)測(cè)試一下
鏈表插入的一般步驟(刪除類(lèi)似)
鏈表插入一般需要：
- 首先，需要找到插入位置，即要將新節(jié)點(diǎn)插入到哪個(gè)節(jié)點(diǎn)之后或之前。
- 然后，創(chuàng)建新節(jié)點(diǎn)，并將其插入到鏈表中。
- 最后，調(diào)整相鄰節(jié)點(diǎn)的指針，使得鏈表的結(jié)構(gòu)得以維護(hù)。
在鏈表的插入操作中，我們需要修改的是當(dāng)前節(jié)點(diǎn)的指針，以將其指向新節(jié)點(diǎn)。如果我們只傳遞指向當(dāng)前節(jié)點(diǎn)的指針，那么在函數(shù)內(nèi)部修改指針的值只會(huì)影響函數(shù)內(nèi)部的副本（傳值調(diào)用），而不會(huì)影響調(diào)用者傳遞給函數(shù)的原始指針。為了能夠修改調(diào)用者傳遞的指針的值，我們需要傳遞指針的地址，也就是二級(jí)指針（傳址調(diào)用）。這樣，在函數(shù)內(nèi)部就可以通過(guò)二級(jí)指針來(lái)修改調(diào)用者傳遞的指針的值，從而實(shí)現(xiàn)鏈表的插入操作。（傳值調(diào)用和傳址調(diào)用CSDNhttps://mp.csdn.net/mp_blog/creation/editor/136962591）簡(jiǎn)單的說(shuō)就是，如果要對(duì)鏈表進(jìn)行遍歷來(lái)找到需要插入的位置，在插入時(shí)我們不能直接傳入要改變的地址，這是一個(gè)一級(jí)指針，一級(jí)指針作為形參改變不了實(shí)參的一級(jí)指針，如果傳入的是一級(jí)指針，形參就是一個(gè)新創(chuàng)建的臨時(shí)地址，并不能通過(guò)解引用找到需要改變的位置，當(dāng)然就不能對(duì)鏈表進(jìn)行插入刪除操作了。我們要使用二級(jí)指針，對(duì)它解引用一次才能得到我們傳入的指針，對(duì)其進(jìn)行遍歷就能找到我們需要插入數(shù)據(jù)的位置。
要對(duì)鏈表進(jìn)行遍歷來(lái)找到需要插入的位置才需要傳入二級(jí)指針，這是不是意味著不通過(guò)頭節(jié)點(diǎn)來(lái)遍歷鏈表就不需要傳入二級(jí)指針了。這個(gè)猜想是正確的，不需要通過(guò)頭節(jié)點(diǎn)來(lái)遍歷，我們可以直接傳入要操作的地址。所以，是否需要傳入二級(jí)指針取決于你的插入操作需要定位的位置以及你如何確定這個(gè)位置。如果通過(guò)遍歷鏈表來(lái)確定插入位置，那么可能需要傳入二級(jí)指針；如果已經(jīng)明確了插入位置，那么只需要傳入指向該位置的指針即可。
鏈表的尾插
在尾插中我們需要對(duì)鏈表的遍歷來(lái)找到要進(jìn)行插入的位置，所以需要傳入二級(jí)指針。
//創(chuàng)建一個(gè)新節(jié)點(diǎn)
SLTNode* SLTBuyNode(SLTDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
//鏈表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
//空鏈表和非空鏈表
SLTNode* newnode = SLTBuyNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾
SLTNode* ptail = *pphead;
while (ptail->next)
{
ptail = ptail->next;
}
//ptail指向的就尾節(jié)點(diǎn)
ptail->next = newnode;
}
}
讓我們一起來(lái)測(cè)試一下吧
頭插
在頭插中我們也需要遍歷鏈表來(lái)找到要要操作的位置，故傳入二級(jí)指針。
//頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);//申請(qǐng)一個(gè)新節(jié)點(diǎn)
//newnode *pphead
newnode->next = *pphead;
*pphead = newnode;
}?測(cè)試
?尾刪
如果只有一個(gè)節(jié)點(diǎn)直接釋放并置空，若有多個(gè)節(jié)點(diǎn)，找到尾節(jié)點(diǎn)之前的節(jié)點(diǎn)和尾節(jié)點(diǎn)，釋放尾節(jié)點(diǎn)并置空，把尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的指針域指向NULL。
//尾刪
void SLTPopBack(SLTNode** pphead)
{
assert(pphead && *pphead);
//鏈表也不能為空
//鏈表只有一個(gè)節(jié)點(diǎn)
if ((*pphead)->next == NULL)//->優(yōu)先級(jí)高于*
{
free(*pphead);
*pphead = NULL;
}
else
{
SLTNode* prev = *pphead;
SLTNode* ptail = *pphead;
while (ptail->next) //要找兩個(gè)節(jié)點(diǎn)
{
prev = ptail;
ptail = ptail->next;
}
//此時(shí)ptail指向尾節(jié)點(diǎn)
free(ptail);
ptail = NULL;
prev->next = NULL;
}
}
測(cè)試
?頭刪
//頭刪
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);
//鏈表也不能為空
SLTNode* next = (*pphead)->next;//->優(yōu)先級(jí)高于*
free(*pphead);
*pphead = next;
}測(cè)試
查找
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
//只有一個(gè)節(jié)點(diǎn)時(shí)
//有多個(gè)節(jié)點(diǎn)時(shí)
SLTNode* pcur = phead;
while (pcur)
{
if ((pcur)->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
創(chuàng)建一個(gè)find變量，用來(lái)接收SLTFind()的返回值，如果返回的不是空指針則找到了，反之則沒(méi)有找到。
//測(cè)試查找
SLTNode* find = SLTFind(plist, 2);
if (find != NULL)
{
printf("找到了\n");
}
else
{
printf("沒(méi)找到\n");
}
SLTNode* find2 = SLTFind(plist, 10);
if (find2 != NULL)
{
printf("找到了\n");
}
else
{
printf("沒(méi)找到\n");
}
在指定位置前插入數(shù)據(jù)
雖然我們知道了指定位置的數(shù)據(jù)，但是單鏈表無(wú)法通過(guò)通過(guò)一個(gè)節(jié)點(diǎn)訪問(wèn)上一個(gè)節(jié)點(diǎn)。所以我們?nèi)匀恍枰闅v鏈表來(lái)找到指定位置之前的節(jié)點(diǎn)。
//在指定位置之前插入數(shù)據(jù)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead && *pphead);
assert(pos);
//找pos的前一個(gè)節(jié)點(diǎn)
SLTNode* newnode = SLTBuyNode(x);
//如果pos == *pphead;說(shuō)明頭插
if (pos == *pphead)
{
SLTPushFront(pphead, x);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//此時(shí)prev已經(jīng)指向pos的前一個(gè)節(jié)點(diǎn)
newnode->next = pos;
prev->next = newnode;
}
}
測(cè)試
在指定位置后插入數(shù)據(jù)?
單鏈表可以通過(guò)一個(gè)節(jié)點(diǎn)訪問(wèn)上一個(gè)節(jié)點(diǎn)，這時(shí)候就不用遍歷鏈表了。
//在指定位置之后插入數(shù)據(jù)
void SLTInsertAfter(SLTNode* pos, SLTDataType x)//不需要頭節(jié)點(diǎn)，自己就能找到下一個(gè)節(jié)點(diǎn)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
測(cè)試
刪除指定節(jié)點(diǎn)
//刪除pos節(jié)點(diǎn)
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && *pphead);
assert(pos);
//當(dāng)*pphead == pos時(shí)
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev指向pos的前一個(gè)節(jié)點(diǎn)
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
?不能先釋放pos節(jié)點(diǎn)再改變prev的指向，釋放后pos是一個(gè)野指針，置為空之后為空指針。不能再找到原來(lái)pos之后的位置
測(cè)試
如果用prev->next = prev->next->next不使用pos指針的話，就可以對(duì)pos節(jié)點(diǎn)提前釋放并置空
//刪除pos節(jié)點(diǎn)
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && *pphead);
assert(pos);
//當(dāng)*pphead == pos時(shí)
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else
{
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev指向pos的前一個(gè)節(jié)點(diǎn)
prev->next = prev->next->next;
free(pos);
pos = NULL;
}
}
刪除指定節(jié)點(diǎn)之后的節(jié)點(diǎn)?
/刪除pos之后的節(jié)點(diǎn)
void SLTEraseAfter(SLTNode* pos)
{
assert(pos && pos->next);
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}測(cè)試
銷(xiāo)毀鏈表?
如果鏈表創(chuàng)建后不進(jìn)行銷(xiāo)毀或釋放，可能會(huì)導(dǎo)致內(nèi)存泄漏和資源浪費(fèi)的問(wèn)題。內(nèi)存泄漏是指程序分配了內(nèi)存空間但未釋放，導(dǎo)致該內(nèi)存空間無(wú)法再被程序使用，最終導(dǎo)致系統(tǒng)資源耗盡或程序性能下降。
實(shí)現(xiàn)時(shí)需要兩個(gè)指針，一個(gè)用來(lái)儲(chǔ)存當(dāng)前節(jié)點(diǎn)的next指針；一個(gè)用來(lái)儲(chǔ)存當(dāng)前節(jié)點(diǎn)的指針；釋放當(dāng)前節(jié)點(diǎn)并使當(dāng)前節(jié)點(diǎn)指向next。
//銷(xiāo)毀鏈表
void SListDesTroy(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}調(diào)試?
?
總結(jié)?
仔細(xì)觀察，凡是不需要遍歷鏈表的操作，我們就不需要傳二級(jí)指針做形參。例如刪除指定位置之后的數(shù)據(jù)和在指定位置后插入數(shù)據(jù)就不需要傳二級(jí)指針。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-859418.html
在對(duì)某一個(gè)節(jié)點(diǎn)進(jìn)行操作時(shí)，要考慮兩個(gè)方面，一要對(duì)指定的節(jié)點(diǎn)進(jìn)行操作，二要調(diào)整相鄰節(jié)點(diǎn)的指針，使得鏈表的結(jié)構(gòu)得以維護(hù)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-859418.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】-- 單鏈表的實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[C語(yǔ)言][數(shù)據(jù)結(jié)構(gòu)][鏈表] 單鏈表的從零實(shí)現(xiàn)!](https://imgs.yssmx.com/Uploads/2024/04/847183-1.png)
