柚子快報邀請碼778899分享：數(shù)據(jù)結(jié)構(gòu)————單鏈表

http://yzkb.51969.com/

1.單鏈表的概念及結(jié)構(gòu)

1.1單鏈表的概念

概念：鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表 中的指針鏈接次序?qū)崿F(xiàn)的 。

1.2單鏈表的結(jié)構(gòu)

單鏈表是由一個個結(jié)點，通過指針連接在一起形成的。那么單個結(jié)點的結(jié)構(gòu)是這樣的：??

注意：鏈表中最后一個結(jié)點的next指針為空，不指向任何結(jié)點。

那么多個結(jié)點連接起來，形成的鏈式結(jié)構(gòu)就是鏈表：

可能在這里你會有疑惑：鏈表不是邏輯結(jié)構(gòu)上連續(xù)，順序上非連續(xù)嗎？那么圖中為什么一個個結(jié)點都是挨在一起的呢？沒錯，鏈表在結(jié)構(gòu)上并不是連續(xù)的，上圖也只是為了方便大家理解，所以用了指針的“形象化”表達。實際上在存儲時，是沒有箭頭指向的，各個結(jié)點之間也是分散的。

在了解了鏈表的基本結(jié)構(gòu)和概念后，我們來試著實現(xiàn)一個單鏈表。

2.單鏈表的實現(xiàn)

2.1結(jié)點的創(chuàng)建

從上邊結(jié)點的示意圖中我們就可以想到：每個結(jié)點都要存儲數(shù)據(jù)，也要有指向下一個結(jié)點的地址的next指針，那么鏈表結(jié)點是不是應該包含這兩個元素呢？是的！在創(chuàng)建鏈表結(jié)點時，這兩部分是十分重要的。

typedef int SLTDataType;

typedef struct SListNode

{

SLTDataType data;

struct SListNode* next;

}SLTNode;

在這里，我們同時把int類型重命名為SLTDataType，那這一步有什么用呢？其實這一步可以說是一勞永逸，當我們后續(xù)想要修改鏈表中結(jié)點存儲的數(shù)據(jù)的數(shù)據(jù)類型時，我們不需要一個個去修改函數(shù)定義中傳參的類型，只需要將這里的int改成我們想要的類型即可。

在定義結(jié)點時，有一個坑：那就是next指針的指針類型。在我一開始寫的時候，總是會把他寫成int* next，然而我們需要清楚，next是指向結(jié)點的指針，所以它的類型應該是結(jié)構(gòu)體類型（因為我們把結(jié)點定義成了一個結(jié)構(gòu)體）。

2.2單鏈表的功能

我們創(chuàng)建一個鏈表并不單單是為了看看他的結(jié)構(gòu)啦，定義之類的，我沒還要用鏈表實現(xiàn)一些功能，比如說插入、刪除、查找等。

//打印鏈表

void PrintfSList(SLTNode* phead);

//創(chuàng)建新結(jié)點

SLTNode* BuySListNode(SLTDataType x);

//頭插

void SLTPushFront(SLTNode** pphead,SLTDataType x);

//尾插

void SLTPushBack(SLTNode** pphead,SLTDataType x);

//頭刪

void SLTPopFront(SLTNode** pphead);

//尾刪

void SLTPopBack(SLTNode** pphead);

//找到某個結(jié)點

SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//在pos之前插入x

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//在pos之后插入x

void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//刪除pos位置

void SLTErase(SLTNode** pphead, SLTNode* pos);

需要注意的是：鏈表是不需要進行初始化的??！

2.3鏈表功能的實現(xiàn)

2.3.1鏈表的打印

需要注意的是：鏈表與順序表不同，順序表的頭指針不可能為空，但是鏈表卻有可能為空，此時該鏈表就是一個空鏈表。所以在代碼的開頭，不需要加入斷言。

在打印時，cur指針不斷向后訪問，直到cur指針為空時，說明訪問完整個鏈表，循環(huán)結(jié)束。

//打印鏈表

void PrintfSList(SLTNode* phead)

{

SLTNode* cur = phead;

while (cur != NULL)

{

printf("%d->", cur->data);

cur = cur->next;

}

printf("NULL\n");//輸出結(jié)果為1->2->3->4->NULL

}

2.3.2創(chuàng)建新結(jié)點

在這里我們就要用malloc函數(shù)動態(tài)開辟一塊空間，作為我們申請的新結(jié)點。因為每插入一個數(shù)據(jù)我們都需要申請新的空間作為結(jié)點，為了減少代碼的重復性和復雜性，我們另寫一個函數(shù)來專門創(chuàng)建結(jié)點。

//創(chuàng)建新節(jié)點

SLTNode* BuySListNode(SLTDataType x)

{

SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));

if (newnode == NULL)

{

perror("BuySListNode malloc");

exit(-1);

}

newnode->data = x;

newnode->next = NULL;

return newnode;

}

2.3.3鏈表的尾插

我們先來看尾插的代碼：

//尾插

void SLTPushBack(SLTNode** pphead,SLTDataType x)

{

assert(pphead);

SLTNode* newnode = BuySListNode(x);

if (*pphead == NULL)

{

*pphead = newnode;

}

else

{

SLTNode* tail = *pphead;

while(tail->next != NULL)

{

tail = tail->next;

}

tail->next = newnode;

}

}

在這段代碼中，有人可能會有很多疑惑：為什么要使用二級指針呢？為什么打印鏈表的時候不需要斷言，這里卻需要斷言呢？這是很多初學者都會存在的問題（作者也一樣哈哈哈）。

首先對于第一個問題：為什么要使用二級指針呢？因為我們在進行鏈表的尾插操作時，很可能出現(xiàn)一種特殊情況：這個鏈表是空鏈表，里邊沒有任何節(jié)點。此時我們的尾插就變成了頭插。

此時，我們就改變了頭指針的指向，但是我們要注意的是，這一操作是在函數(shù)里進行的，所以函數(shù)傳參時的phead看似是plist，實則是他的拷貝，也就是我們說的形參。那么我們知道，形參的改變是不會影響實參的，也就是說，如果只是簡單的使用一級指針來接收頭指針，是不會對他造成任何改變的，也就造成我們的插入失敗。為了解決這一問題，我們才動用了二級指針這尊“大佛”，二級指針表示的就不只是簡單的頭指針plist的指向，而是他自己的地址，只有真正改變了他的地址，才能真正改變他的指向。

接下來看第二個問題，關(guān)于斷言。在尾插時，我們對pphead進行了斷言，要清楚的是，pphead表示的是頭指針plist的地址，不是頭指針plist！！！所以一切都變得合理起來，我們必須確保頭指針實實在在存在，即他的地址不為空，才能進行后邊的操作。

2.3.4鏈表的尾刪

在尾刪時，我們需要注意的是，這個鏈表中可能只有一個節(jié)點，或者有多個節(jié)點。

當只有一個節(jié)點時，頭指針正好指向這一結(jié)點，我們直接將它釋放，然后將頭指針置空就可以了。是不是很easy~

但是當鏈表中有多個結(jié)點，我們就需要一次次地循環(huán)遍歷找到尾結(jié)點的前一個結(jié)點，用tail指針指向他，然后釋放掉tail->next（尾結(jié)點）。

那么有人可能會有疑問：為什么要找尾結(jié)點的前一個節(jié)點，而不是真正的尾結(jié)點呢？因為我們在尾刪時，要將最后一個結(jié)點釋放刪除掉，并將前一個結(jié)點的next置空。又因為這是單鏈表，刪除掉尾結(jié)點后無法再找到他的前一個結(jié)點，所以我們不能直接指向尾結(jié)點。

//尾刪

void SLTPopBack(SLTNode** pphead)

{

//空

assert(pphead);

//一個節(jié)點

if ((*pphead)->next == NULL)

{

free(*pphead);

*pphead = NULL;

}

//多個節(jié)點

else

{

SLTNode* tail = *pphead;

while (tail->next->next != NULL)

{

tail = tail->next;

}

free(tail->next);

tail->next = NULL;

}

}

2.3.5鏈表的頭插

在有了上邊的基礎之后，我們來實現(xiàn)頭插就變的易如反掌了~

//頭插

void SLTPushFront(SLTNode** pphead, SLTDataType x)

{

assert(pphead);

SLTNode* newnode = BuySListNode(x);

newnode->next = *pphead;

*pphead = newnode;

}

2.3.6鏈表的頭刪

//頭刪

void SLTPopFront(SLTNode** pphead)

{

//空

assert(pphead);

//非空

SLTNode* newhead = (*pphead)->next;

free(*pphead);

*pphead = newhead;

}

頭刪時仍要注意加入斷言來檢查，并且要先定義新的頭指針，再進行釋放，否則會導致鏈表的丟失。

2.3.7找到某個結(jié)點

//找到某個節(jié)點

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)

{

SLTNode* cur = phead;

while (cur!=NULL)

{

if (x == cur->data)

{

return cur;

}

else

{

cur = cur->next;

}

}

return NULL;

}

這里的返回值不再是void而是SLTNode*，返回的是找到的結(jié)點。當我們遍歷整個鏈表也沒有找到這一結(jié)點時，就只能返回空啦。

2.3.8在pos位置之前插入數(shù)據(jù)

//在pos之前插入x

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)

{

assert(pphead);

assert(pos);

if (pos == *pphead)//頭插

{

SLTPushFront(pphead, x);

}

else

{

SLTNode* prev = *pphead;

while (prev->next != pos)

{

prev = prev->next;

assert(prev->next);

}

SLTNode* newnode = BuySListNode(x);

newnode->next = pos;

prev->next = newnode;

}

}

注意：

1、在這里，我們不僅需要斷言pphead，還需要斷言pos！因為我們要在pos位置前面插入x，pos絕對絕對不可以是空呀！

2、pos的位置也需要檢查！因為當pos的位置超出整個單鏈表的范圍，那是絕對無法正確插入的??！

接下來就很簡單了，當pos恰巧就是頭指針的位置時，這一操作就進化成了頭插，直接引用頭插函數(shù)即可。如果pos的位置沒那么湊巧，我們就找到pos的前驅(qū)結(jié)點，然后把新結(jié)點鏈接在pos和他的前驅(qū)結(jié)點之間。

2.3.9在pos位置之后插入數(shù)據(jù)

//在pos之后插入x

void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)

{

assert(pphead);

assert(pos);

SLTNode* cur = *pphead;

while (cur != pos)

{

cur = cur->next;

assert(cur != NULL);

}

if (pos->next == NULL)//尾插

{

SLTPushBack(pphead, x);

}

else

{

SLTNode* newnode = BuySListNode(x);

newnode->next = pos->next;

pos->next = newnode;

}

}

這里也需要對pos進行檢查，防止要插入的位置超出范圍。

2.3.10刪除pos位置

//刪除pos位置

void SLTErase(SLTNode** pphead, SLTNode* pos)

{

assert(pphead);

assert(pos);

if (pos == *pphead)//頭刪

{

SLTPopFront(pphead);

}

else

{

SLTNode* prev = *pphead;

while (prev->next != pos)

{

prev = prev->next;

assert(prev->next);

}

prev->next = pos->next;

free(pos);

pos = NULL;

}

}

3.總結(jié)

1.Slist.h

#pragma once

#include

#include

#include

typedef int SLTDataType;

typedef struct SListNode

{

SLTDataType data;

struct SListNode* next;

}SLTNode;

//打印鏈表

void PrintfSList(SLTNode* phead);

//創(chuàng)建新結(jié)點

SLTNode* BuySListNode(SLTDataType x);

//頭插

void SLTPushFront(SLTNode** pphead,SLTDataType x);

//尾插

void SLTPushBack(SLTNode** pphead,SLTDataType x);

//頭刪

void SLTPopFront(SLTNode** pphead);

//尾刪

void SLTPopBack(SLTNode** pphead);

//找到某個結(jié)點

SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//在pos之前插入x

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//在pos之后插入x

void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//刪除pos位置

void SLTErase(SLTNode** pphead, SLTNode* pos);

2.Slist.c

#include"SList.h"

//打印鏈表

void PrintfSList(SLTNode* phead)

{

SLTNode* cur = phead;

while (cur != NULL)

{

printf("%d->", cur->data);

cur = cur->next;

}

printf("NULL\n");

}

//創(chuàng)建新節(jié)點

SLTNode* BuySListNode(SLTDataType x)

{

SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));

if (newnode == NULL)

{

perror("BuySListNode malloc");

exit(-1);

}

newnode->data = x;

newnode->next = NULL;

return newnode;

}

//頭插

void SLTPushFront(SLTNode** pphead, SLTDataType x)

{

SLTNode* newnode = BuySListNode(x);

newnode->next = *pphead;

*pphead = newnode;

}

//尾插

void SLTPushBack(SLTNode** pphead,SLTDataType x)

{

assert(pphead);

SLTNode* newnode = BuySListNode(x);

if (*pphead == NULL)

{

*pphead = newnode;

}

else

{

SLTNode* tail = *pphead;

while(tail->next != NULL)

{

tail = tail->next;

}

tail->next = newnode;

}

}

//頭刪

void SLTPopFront(SLTNode** pphead)

{

//空

assert(*pphead);

//非空

SLTNode* newhead = (*pphead)->next;

free(*pphead);

*pphead = newhead;

}

//尾刪

void SLTPopBack(SLTNode** pphead)

{

//空

assert(pphead);

//一個節(jié)點

if ((*pphead)->next == NULL)

{

free(*pphead);

*pphead = NULL;

}

//多個節(jié)點

else

{

SLTNode* tail = *pphead;

while (tail->next->next != NULL)

{

tail = tail->next;

}

free(tail->next);

tail->next = NULL;

}

}

//找到某個節(jié)點

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)

{

SLTNode* cur = phead;

while (cur!=NULL)

{

if (x == cur->data)

{

return cur;

}

else

{

cur = cur->next;

}

}

return NULL;

}

//在pos之前插入x

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)

{

assert(pphead);

assert(pos);

if (pos == *pphead)//頭插

{

SLTPushFront(pphead, x);

}

else

{

SLTNode* prev = *pphead;

while (prev->next != pos)

{

prev = prev->next;

}

SLTNode* newnode = BuySListNode(x);

newnode->next = pos;

prev->next = newnode;

}

}

//在pos之后插入x

void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)

{

assert(pphead);

assert(pos);

SLTNode* cur = *pphead;

while (cur != pos)

{

cur = cur->next;

assert(cur != NULL);

}

if (pos->next == NULL)//尾插

{

SLTPushBack(pphead, x);

}

else

{

SLTNode* newnode = BuySListNode(x);

newnode->next = pos->next;

pos->next = newnode;

}

}

//刪除pos位置

void SLTErase(SLTNode** pphead, SLTNode* pos)

{

assert(pphead);

assert(pos);

if (pos == *pphead)//頭刪

{

SLTPopFront(pphead);

}

else

{

SLTNode* prev = *pphead;

while (prev->next != pos)

{

prev = prev->next;

}

prev->next = pos->next;

free(pos);

pos = NULL;

}

}

柚子快報邀請碼778899分享：數(shù)據(jù)結(jié)構(gòu)————單鏈表

http://yzkb.51969.com/

推薦文章