目錄
- 0. 引
- 1. 鏈表的概念和結構
- 2. 鏈表的分類
- 3. 鏈表的實作
- 3.1 列印、申請新節點、銷毀
- 3.1.1 列印
- 3.1.2 申請新節點
- 3.1.3 銷毀
- 3.2 尾插、尾刪
- 3.2.1 尾插
- 3.2.2 尾刪
- 3.3 頭插、頭刪
- 3.3.1 頭插
- 3.3.2 頭刪
- 3.4 查找、任意位置插入、任意位置洗掉
- 3.4.1 查找
- 3.4.2 任意位置插入
- 3.4.3 任意位置洗掉
- 4. 關于單鏈表的思考
- 4.1 鏈表優點
- 4.1 鏈表缺點
- 附錄
- `SingleList.h`
- `SingleList.c`
- `test.c`
小邊碎碎念:上次實作單鏈表已經是兩個月之前的事兒了,今兒拿出來再寫,思路還是在,但確實忘掉了一些細節,一上午出現了各種小問題,全都是自己一個個調出來的,這種快感不是別的什么事情可以代替的,同時也發現,當初覺得想不到的東西,現在看也就是理所當然,這就是螺旋式上升吧🐏!
0. 引
上文說到順序表缺陷 ——
??1. 空間不夠需要增容,增容是要付出代價的,
??2. 為了避免頻繁擴容,我們基本都是按倍數去擴(比如擴2倍),這又可能會造成一定的空間浪費,
??3. 順序表要求資料從開始位置保持連續,那么中間和頭部的插入和洗掉,都需要挪動資料,時間復雜度為O(N),效率不高,
為此,我們引入了鏈表,
1. 鏈表的概念和結構
鏈表是一種物理存盤結構上非連續、非順序的存盤結構,資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的 ,
- 邏輯圖 —— 想象出來的形象方式表示

- 物理圖 —— 記憶體中的真實存盤 —— 通過指標來存盤下一個節點的地址,并不連續

2. 鏈表的分類
實際中鏈表的結構非常多樣,以下情況組合起來就有8種鏈表結構:
- 單向或雙向

- 帶頭不帶頭

- 回圈非回圈

當然我們最常用的還是這兩種 ——
- 無頭單向非回圈鏈表

- 結構簡單,但缺陷還是很多(一會兒實作的時候你就知道啦),單純單鏈表的增刪查改意義不大,
- 但是還是要寫,可能正因為它的缺陷,很多oj題考察的都是單鏈表
- 更多的是做更復雜資料結構的子結構,比如哈希桶、鄰接表,
- 帶頭雙向回圈鏈表

- 結構最復雜,一般用在單獨存盤資料,實際中使用的鏈表資料結構,都是帶頭雙向回圈鏈表,
- 另外這個結構雖然復雜,卻也是無死角的結構,用代碼實作時會發現結構會帶來很多優勢,非常爽,后面我們代碼實作了就知道了,
3. 鏈表的實作
文末領取頭檔案大家自己寫,自己寫自己調時候思路是最清晰的,具體實作中每個思路和要注意的小點我都會寫好(尤其是它第一次出現的時候)(這鏈表電腦畫圖老累了,主要是這個破箭頭,ipad上寫字還丑,我把我草紙的圖弄進來了哦吼吼)紅筆寫的是邊界,耦合色寫的是變化程序哈哈,
3.1 列印、申請新節點、銷毀
3.1.1 列印

void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
3.1.2 申請新節點
//申請新節點
SLTNode* BuyListNode(SListDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
printf("malloc failed\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
3.1.3 銷毀
- 順序表中申請的記憶體是連續的(
realloc),因此一次釋放就行;而鏈表的空間申請時候就不連續,必須遍歷回收, - free時,data和next都會被置成隨機值,因此要記錄next

void SListDestroy(SLTNode** pphead)
{
assert(pphead);
// 鏈表的空間必須遍歷回收,因為申請時候就不連續
SLTNode* cur = *pphead;
SLTNode* next = cur->next;// 記錄下一個節點的位置
while (next)
{
free(cur);
cur = next;
next = cur->next;
}
*pphead = NULL;
}
3.2 尾插、尾刪
3.2.1 尾插
- 為什么要傳二級指標?尾插、包括后面的尾刪頭插頭刪、前面的銷毀都需要傳二級指標,而列印、查找就不需要,
🍓實際上,二級指標就是為了處理首節點的改變(pList是鏈表的地址,型別為SLNode*),后面操縱的都是結構體就不需要,眾所周知形參是實參的一份臨時拷貝,形參的改變不會影響實參,因此必須傳實參地址(在這里型別為SLNode**)以改變實參,
- 解釋一下
assert(pphead);,像這種一定不為空的要斷言一下,方便查錯(傳錯)

void SListPushBack(SLTNode** pphead, SListDataType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
//1.空鏈表 - 尾插頭結點的地址pList發生改變,因此需要傳pList的地址
//單拎出來處理
if (*pphead == NULL)
{
*pphead = newnode;
return;
}
//2.找尾
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
3.2.2 尾刪
- 考慮鏈表為空 —— 斷言結束(STL采取的就是這樣粗暴的方式),畢竟,就是你用錯了
- 其余細節程序都在圖中

void SListPopBack(SLTNode** pphead)
{
assert(pphead);
//1.空鏈表
assert(*pphead);
//2.刪的只剩一個節點時
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
return;
}
//3.
//找尾的上一個
SLTNode* prevtail = *pphead;
SLTNode* tail = prevtail->next;
while (tail->next != NULL)
{
prevtail = tail;
tail = tail->next;
}
free(tail);
prevtail->next = NULL;
}
3.3 頭插、頭刪
3.3.1 頭插

void SListPushFront(SLTNode** pphead, SListDataType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
3.3.2 頭刪

void SListPopFront(SLTNode** pphead)
{
assert(pphead);
//1.刪空
assert(*pphead);
//2.
SLTNode* headnext = (*pphead)->next;
free(*pphead);
*pphead = headnext;
}
3.4 查找、任意位置插入、任意位置洗掉
3.4.1 查找
SLTNode* SListFind(SLTNode* phead, SListDataType x)
{
SLTNode* cur = phead;
if (phead == NULL)
{
//處理空鏈表,不然后面解參考可是又錯了
return NULL;
}
while (cur)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;//走到這兒還沒找到
}
3.4.2 任意位置插入

//在pos位置之前去插入一個節點--pos位置一般是find來的
void SListInsert(SLTNode** pphead, SLTNode* pos, SListDataType x)
{
assert(pphead);
assert(pos);
SLTNode* newnode = BuyListNode(x);
//1. 頭插
if (*pphead == pos)
{
newnode->next = *pphead;
*pphead = newnode;
}
//2.
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = newnode;
newnode->next = pos;
}

//在pos后邊插入--這個更適合也更簡單高效
//STL- insert_after
void SListInsertAfter(SLTNode* pos, SListDataType x)
{
assert(pos);
SLTNode* newnode = BuyListNode(x);
SLTNode* posNext = pos->next;
pos->next = newnode;
newnode->next = posNext;
}
3.4.3 任意位置洗掉

void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
//刪空
assert(*pphead);
//1.頭刪
//帶哨兵位的頭的 -- 可以合并 頭刪與中間刪 -- 邏輯結構一樣,不會刪完
if (*pphead == pos)
{
*pphead = pos->next;
free(pos);
return;//自己調出來的
}
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = pos->next;
free(pos);//注意順序,對于我很簡單啦
//pos不置空也無所謂,畢竟在函式中是形參,形參的改變不會影響實參,處于好習慣,還是置空比較好
}
當然也可以實作洗掉pos后面的節點,這個功能很奇葩哈哈給pos不刪pos
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);//一個節點
SLTNode* posNext = pos->next;
pos->next = posNext->next;
free(posNext);
//next = NULL;//出作用域即銷毀,是野指標,但別人拿不到
}
4. 關于單鏈表的思考
4.1 鏈表優點
鏈表彌補了順序表的缺陷
- 按需申請空間,不用了就釋放(更合理的使用了空間),不存在空間浪費
- 頭部和中間插入洗掉資料,不需要挪動資料
4.1 鏈表缺點
- 每一個資料,都要存一個指標鏈接后面的資料結點
- 不支持隨機訪問(用下標直接訪問第i個元素),而有些演算法,需要隨機訪問,如:二分查找、優化的快排
附錄
SingleList.h
#pragma once
//無頭單向非回圈鏈表
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SListDataType;
typedef struct SListNode
{
SListDataType data;
struct SListNode* next;
}SLTNode;
void SListPrint(SLTNode* phead);
//銷毀
void SListDestroy(SLTNode** pphead);
//尾插
void SListPushBack(SLTNode** pphead, SListDataType x);
//尾刪
void SListPopBack(SLTNode** pphead);
//頭插
void SListPushFront(SLTNode** pphead, SListDataType x);
//頭刪
void SListPopFront(SLTNode** pphead);
//查找
SLTNode* SListFind(SLTNode* phead, SListDataType x);
//在pos位置之前去插入一個節點--pos位置一般是find來的
void SListInsert(SLTNode** pphead, SLTNode* pos, SListDataType x);
//任意位置刪
void SListErase(SLTNode** pphead, SLTNode* pos);
//在pos后邊插入--這個更適合也更簡單高效
void SListInsertAfter(SLTNode* pos, SListDataType x);
void SListEraseAfter(SLTNode* pos);
//void SListInsert(SLTNode* phead, SLTNode* pos,SListDataType x);
//void SListErase(SLTNode* phead, int pos);
SingleList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
void SListDestroy(SLTNode** pphead)
{
// 這個鏈表是
// 鏈表的空間必須遍歷回收,因為申請時候就不連續
SLTNode* cur = *pphead;
SLTNode* next = cur->next;// 記錄下一個節點的位置
while (next)
{
free(cur);
cur = next;
next = cur->next;
}
*pphead = NULL;
}
//申請新節點
SLTNode* BuyListNode(SListDataType x)
{
SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{
printf("malloc failed\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void SListPushBack(SLTNode** pphead, SListDataType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
//1.空鏈表 - 尾插頭結點的地址pList發生改變,因此需要傳pList的地址
// **pphead
if (*pphead == NULL)
{
*pphead = newnode;
return;
}
//找尾
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
void SListPopBack(SLTNode** pphead)
{
assert(pphead);
//1.空鏈表
assert(*pphead);
//2.刪的只剩一個節點時
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
return;
}
//3.普遍情況
//找尾的上一個
SLTNode* prevtail = *pphead;
SLTNode* tail = prevtail->next;
while (tail->next != NULL)
{
prevtail = tail;
tail = tail->next;
}
free(tail);
prevtail->next = NULL;
}
void SListPushFront(SLTNode** pphead, SListDataType x)
{
assert(pphead);
SLTNode* newnode = BuyListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void SListPopFront(SLTNode** pphead)
{
assert(pphead);
//1.刪空
assert(*pphead);
//2.
SLTNode* headnext = (*pphead)->next;
free(*pphead);
*pphead = headnext;
}
SLTNode* SListFind(SLTNode* phead, SListDataType x)
{
SLTNode* cur = phead;
if (phead == NULL)
{
//處理空鏈表,不然后面解參考可是又錯了
return NULL;
}
while (cur)
{
if (cur->data == x)
{
return cur;
}
else
{
cur = cur->next;
}
}
return NULL;//走到這兒還沒找到
}
//在pos位置之前去插入一個節點--pos位置一般是find來的
void SListInsert(SLTNode** pphead, SLTNode* pos, SListDataType x)
{
assert(pphead);
assert(pos);
SLTNode* newnode = BuyListNode(x);
//1. 頭插
if (*pphead == pos)
{
newnode->next = *pphead;
*pphead = newnode;
}
//2.
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = newnode;
newnode->next = pos;
}
//在pos后邊插入--這個更適合也更簡單高效
//STL- insert_after
void SListInsertAfter(SLTNode* pos, SListDataType x)
{
assert(pos);
SLTNode* newnode = BuyListNode(x);
SLTNode* posNext = pos->next;
pos->next = newnode;
newnode->next = posNext;
}
//任意位置刪
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
//刪空
assert(*pphead);
//1.頭刪
//帶哨兵位的頭的 -- 可以合并 頭刪與中間刪 -- 邏輯結構一樣,不會刪完
if (*pphead == pos)
{
*pphead = pos->next;
free(pos);
return;//自己調出來的
}
SLTNode* posPrev = *pphead;
while (posPrev->next != pos)
{
posPrev = posPrev->next;
}
posPrev->next = pos->next;
free(pos);//注意順序,對于我很簡單啦
//pos不置空也無所謂,畢竟在函式中是形參,形參的改變不會影響實參,處于好習慣,還是置空比較好
}
void SListEraseAfter(SLTNode* pos)
{
assert(pos);
assert(pos->next);//一個節點
SLTNode* posNext = pos->next;
pos->next = posNext->next;
free(posNext);
//next = NULL;//出作用域即銷毀,是野指標,但別人拿不到
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
//測驗尾插尾刪
void testSingleList1()
{
//指向單鏈表的指標 - 本質是存盤這個單鏈表頭結點的地址的指標變數
SLTNode* pList;
pList = NULL;//這個錯是我調出來的
SListPushBack(&pList, 1);
SListPushBack(&pList, 2);
SListPushBack(&pList, 3);
SListPushBack(&pList, 4);
SListPrint(pList);
SListPopBack(&pList);
SListPopBack(&pList);
SListPopBack(&pList);
/*SListPopBack(&pList);
SListPopBack(&pList);*/
SListPrint(pList);
SListDestroy(&pList);
}
//測驗頭插頭刪
void testSingleList2()
{
SLTNode* pList;
pList = NULL;
SListPushFront(&pList, 1);
SListPushFront(&pList, 2);
SListPushFront(&pList, 3);
SListPrint(pList);
SListPopFront(&pList);
SListPopFront(&pList);
/*SListPopFront(&pList);
SListPopFront(&pList);*/
SListPrint(pList);
SListDestroy(&pList);
}
//測驗任意位置的插入、查找
void testSingleList3()
{
SLTNode* pList;
pList = NULL;
SListPushBack(&pList, 1);
SListPushBack(&pList, 2);
SListPushBack(&pList, 4);
SListPushBack(&pList, 5);
SLTNode* ret = SListFind(pList, 2);
if (ret == NULL)
{
printf("not found\n");
}
else
{
printf("%d\n", ret->data);
}
//SListInsert(&pList, ret, 0);//測驗頭插
//SListInsert(&pList, ret, 3);
SListInsertAfter(ret, 3);
SListPrint(pList);
SListDestroy(&pList);
}
//測驗任意位置刪
void testSingleList4()
{
SLTNode* pList;
pList = NULL;
SListPushBack(&pList, 1);
SListPushBack(&pList, 2);
SListPushBack(&pList, 4);
SListPushBack(&pList, 5);
SListPrint(pList);
SLTNode* ret = SListFind(pList, 1);
if (ret == NULL)
{
printf("not found\n");
}
else
{
printf("%d\n", ret->data);
}
//SListErase(&pList, ret);
//SListErase(&pList, ret);
SListEraseAfter(ret);
SListPrint(pList);
SListDestroy(&pList);
}
int main()
{
//testSingleList1();
//testSingleList2();
//testSingleList3();
testSingleList4();
return 0;
}
下一篇來帶頭雙向回圈鏈表
本文完@邊通書
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/404352.html
標籤:其他
上一篇:資料結構之前綴樹
