[數據結構] -- 單鏈表

🌈 個人主頁：白子寰
🔥 分類專欄：C++打怪之路，python從入門到精通，數據結構，C語言，C語言題集👈 希望得到您的訂閱和支持~
💡 堅持創作博文(平均質量分82+)，分享更多關于深度學習、C/C++，python領域的優質內容！（希望得到您的關注~）

鏈表

概念

結構

鏈表的分類

單向鏈表和雙向鏈表

?帶頭(哨兵位)?或不帶頭(哨兵位) 鏈表

順序表和鏈表的優缺點

在SList.h文件中

定義單鏈表的結構

實現單鏈表的接口/方法

在SList.c文件中?

打印單鏈表(遍歷鏈表)

開辟空間

開辟空間molloc返回值問題

尾部插入元素

傳參的時候為什么要傳二級指針??

測試尾插?

頭部插入元素?

測試?

尾部刪除元素?

測試?

頭部刪除元素?

測試?

查找元素?

?在指定位置之前插入數據

測試?

刪除pos節點?

測試?

在指定位置之后插入數據

刪除pos之后的節點?

測試?

銷毀鏈表?

鏈表

概念

鏈表是一種物理存儲結構上非連續、非順序的存儲結構，

數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的，

單鏈表一般不會單獨使用，
只有頭插和頭刪實現簡單且效率高

結構

鏈表也屬于線性表，線性表在物理上存儲時，
通常以數組（順序表）和鏈式結構（鏈表）的形式存儲，
鏈式結構在邏輯上是連續的，但在物理上不一定連續
? ? ? ? ? ? ? ? ?
現實中的結點一般是從堆上申請出來的
? ? ? ? ? ? ??
從堆上申請的空間，是按照一定的策略來分配的，
兩次申請的空間可能連續，也可能不連續

鏈表的分類

單向鏈表和雙向鏈表

單向鏈表(常用)

雙向鏈表?

?帶頭(哨兵位)?或不帶頭(哨兵位) 鏈表

?帶頭(哨兵位) 鏈表

不帶頭(哨兵位) 鏈表

循環鏈表

帶頭雙向循環鏈表(常用)

順序表和鏈表的優缺點

	順序表	鏈表
存儲空間	物理上一定連續	邏輯上連續,物理上不一定連續
訪問	隨機訪問	不支持隨機訪問
任意位置插入或刪除元素	效率低	修改指針指向
應用	空間不夠擴容,元素高效存儲,隨機訪問	分節點,開節點,可以在任意位置插入或刪除

在SList.h文件中

定義單鏈表的結構

typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;		//數據struct SListNode* next; //指針域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);
//在指定位置之前插入數據
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//刪除pos節點
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插入數據
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//刪除pos之后的節點
void SLTEraseAfter(SLTNode* pos);
//銷毀鏈表
void SListDesTroy(SLTNode** pphead);

在SList.c文件中?

打印單鏈表(遍歷鏈表)

//SLTNode*，表示 phead 是一個指向 SLTNode 類型的指針。
void SLTPrint(SLTNode* phead)		//接收一個指向鏈表頭節點的指針 phead 作為參數
{//一級指針SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL");printf("\n");
}

開辟空間

//開辟空間
SLTNode* SLTBuyNode(SLTDataType x)
{//為一個 SLTNode 類型的結構體分配內存,以便訪問和操作這個新分配的 SLTNode 結構體//所以返回值為SLTNnode*SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

開辟空間molloc返回值問題

函數原型:

尾部插入元素

//尾部插入元素
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);//頭結點為空if (*pphead == NULL){*pphead = newnode;return;}//頭結點不為空SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;
}

傳參的時候為什么要傳二級指針??

二級指針，在函數內部修改頭指針本身的值

一級指針，用于遍歷和訪問鏈表

以下的 打印鏈表和銷毀鏈表函數 說明一級和二級指針的意思?

測試尾插?

頭部插入元素?

//頭部插入元素?
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;	// *pphead表示頭結點*pphead = newnode;
}

測試?

尾部刪除元素?

free作用:

①free(ptail);之后，ptail指針本身的值并未改變，但它所指向的內存已經被釋放，因此不應該再使? 用這個指針訪問已經被釋放的內存。

②我們只需要確保不要再使用這個指針來訪問內存，而不必將其置為NULL

//尾部刪除元素?
void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);	//保證頭結點不為空if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}//有多個結點SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}//單鏈表最后一個結點,只有數據域data且指針域的值是NULL// 釋放尾節點的內存free(ptail);// 將尾節點的前驅節點的next置為NULL，實現刪除尾節點 prev->next = NULL;
}

測試?