【探索數據結構】線性表之單鏈表

🎉🎉🎉歡迎蒞臨我的博客空間，我是池央，一個對C++和數據結構懷有無限熱忱的探索者。🙌

🌸🌸🌸這里是我分享C/C++編程、數據結構應用的樂園?

🎈🎈🎈期待與你一同在編程的海洋中遨游，探索未知的技術奧秘💞

📝專欄指路:

📘【C++】專欄：深入解析C++的奧秘，分享編程技巧與實踐。

📘【數據結構】專欄：探索數據結構的魅力，助你提升編程能力。

前言

回顧：線性表之順序表

順序表的問題及思考

1.中間/頭部的插入刪除，時間復雜度為0(N)

2.增容需要申請新空間，拷貝數據，釋放舊空間。會有不小的消耗。

3.增容一般是呈2倍的增長，勢必會有一定的空間浪費。例如當前容量為100,滿了以后增容到200,我們再繼續插入了5個數據，后面沒有數據插入了，那么就浪費了95個數據空間。

思考：如何解決以上問題呢?

是否存在一種數據結構，能夠解決以上順序表表現出來的問題：

1)中間/頭部的插入刪除，可以一步到位，不需要挪動數據

2)不需要擴容

3)不會造成空間

答案是本篇主角——(單)鏈表

文章重點介紹:不帶頭節點不循環的單鏈表

一、鏈表

鏈表是一種物理存儲單元上非連續、非順序的存儲結構，其數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點組成，每個結點都包含兩個部分：數據域和指針域。數據域用于存儲數據元素的信息，而指針域則存儲著指向下一個結點的地址信息。有單鏈表、雙鏈表、循環鏈表

優點：動態內存分配、插入和刪除高效、空間利用率高

缺點：訪問元素效率低、有額外的空間開銷、緩存不優好

二、單鏈表

1.概念

單鏈表是一種線性數據結構，其中元素在邏輯上按照線性順序排列，但在物理內存中通過指針進行鏈接。每個元素（稱為節點/結點）都包含兩部分信息：數據域和指針域。數據域存儲節點的值或數據，而指針域則包含指向下一個節點的指針。

2.分類

（1）帶頭節點

在單鏈表中，第一個節點之前通常有一個頭指針（或稱為頭節點），它指向鏈表中的第一個數據節點。如果鏈表為空，則頭指針通常指向空（NULL）。鏈表的最后一個節點的指針域被設置為空（NULL），以表示鏈表的結束。

（2）不帶頭節點

不帶頭節點的單鏈表，我們直接通過頭指針指向第一個數據節點，而不需要額外的頭節點作為起始點。

3.代碼示例

創建單鏈表結構

typedef int SLTDataType;
typedef struct SListNode SLTNode;
struct SListNode
{SLTDataType data;//節點存放的數據SLTNode* next;//存放下一個節點的地址
};

三、對單鏈表的操作

（0）打印

//打印
void SLTPrint(SLTNode* phead)
{//創建指向第一個節點的指針的指針，讓phead無需改變SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

（1）創建一個新節點

//創建一個新節點
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");exit(1);//申請空間成功會返回0}newnode->data = x;newnode->next = NULL;return newnode;
}

（2）尾插

有鏈表為空和非空兩種情況

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//*pphead是指向第一個節點的指針， 存放第一個節點的地址//創建一個新節點SLTNode* newnode = SLTBuyNode(x);//空鏈表if (*pphead == NULL){*pphead = newnode;}else{//非空鏈表，找尾//創建指向第一個節點的指針的指針，讓*phead無需改變SLTNode * ptail = *pphead;while (ptail->next){ptail = ptail->next;}//新節點變為鏈表的新尾巴ptail->next = newnode;}
}

思考：為什么要用二級指針來接收實參？

簡單來說，想要改變實參，傳值無法改變，要通過傳實參的地址給形參，形參的改變才會影響實參

（3）頭插

//頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);//*pphead是指向第一個節點的指針， 存放第一個節點的地址//創建一個新節點SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

（4）查找

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);//不改變頭結點，防止要多次遍歷時找不到頭結點SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

（5）頭刪

//頭刪
void SLTDelFront(SLTNode** pphead)
{assert(pphead && *pphead);//鏈表不能為空//無論有幾個節點都適用SLTNode* next = (*pphead)->next;//保存第二個節點的地址free(*pphead);*pphead = NULL;*pphead = next;//原本的第二個節點成為新頭結點
}

（6）尾刪

//尾刪
void SLTDelBack(SLTNode** pphead)
{//可能會修改頭節點地址所以還是使用二級指針assert(pphead && *pphead);//鏈表不能為空//鏈表只有一個節點if ((*pphead)->next == NULL)//->優先級高于*{free(*pphead);*pphead = NULL;}//多個節點SLTNode* ptail = *pphead;SLTNode* prev = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;
}

（7）指定位置之前插入

//指定位置之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && *pphead);//鏈表不能為空assert(pos);//創建一個新節點SLTNode* newnode = SLTBuyNode(x);//相當于頭插if ((*pphead) == pos){//pphead存放指向第一個節點指針的地址SLTPushFront(pphead, x);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev->newnode->posnewnode->next = pos;prev->next = newnode;}
}

（8）指定位置之后插入

//指定位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{//為什么不需要頭結點，因為在指定位置插入是這樣的邏輯//pos-newnode-pos->next,通過pos我們就能找到他的下一個節點assert(pos);//創建一個新節點SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;//思考：上面兩行代碼順序互換可以嗎？
}

不相同，不可以互換位置，第二中代碼pos->next指針先指向了newnode那么原先pos的下一個節點的地址就會找不到

（9）刪除指定節點

//刪除指定節點pos
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);//鏈表不能為空assert(pos);if ((*pphead) == pos){//相當于頭刪SLTDelFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next!=pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

（10）刪除指定節點之后的數據

// 刪除指定節點pos之后的數據
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//如果沒有用del來存放pos->next會怎么樣？SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

（11）銷毀

一個一個銷毀

/銷毀
void SLTDestroy(SLTNode** pphead)
{assert(pphead && *pphead);//鏈表不能為空SLTNode* pcur = *pphead;while (pcur){//如果沒有保存pcur->next的地址// 在pcur釋放掉后，剩余節點找不到了，無法銷毀SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

四、測試（僅供參考）

#include"SList.h"
void STListTest01()
{//創建節點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;//鏈接節點node1->next = node2;node2->next = node3;node3->next = NULL;//創建指向第一個節點的指針，讓node1無需改變SLTNode* plist = node1;//調用打印SLTPrint(plist);}
void STListTest02()
{SLTNode* plist = NULL;SLTNode* p = NULL;//尾插SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&p, 3);plist->next->next = p;SLTPushBack(&p, 4);SLTPrint(plist);//頭插SLTPushFront(&plist, 5);SLTPrint(plist);//尾刪SLTDelBack(&plist);SLTPrint(plist);//頭刪SLTDelFront(&plist);SLTPrint(plist);SLTNode*find=SLTFind(plist, 3);//指定位置之前插入SLTInsert(&plist, find, 5);SLTPrint(plist);//指定位置之后插入SLTInsertAfter(find, 10);SLTPrint(plist);//刪除指定節點/*SLTErase(plist, find);*///刪除指定節點之后數據SLTEraseAfter(find);SLTPrint(plist);//銷毀鏈表SLTDestroy(&plist);SLTPrint(plist);}
int main()
{//STListTest01();STListTest02();
}

下回預告：線性表之雙鏈表

持續更新中...

敬請期待