【數據結構】--- 單鏈表的增刪查改

前言：

經過了幾個月的漫長歲月，回頭時年邁的小編發現，數據結構的內容還沒有寫博客，于是小編趕緊停下手頭的活動，補上博客以洗清身上的罪孽

前言

? ? ? ? ? ?概念：

單鏈表的結構

我們設定一個哨兵位頭節點給鏈表

單鏈表的基本操作

插入：

單鏈表的頭插：

單鏈表的尾插：

單鏈表的遍歷打印：從頭節點開始，逐個訪問鏈表中的每個節點，直到達到鏈表的末尾。

單鏈表的刪除：刪除鏈表中的指定節點，需要修改前一個節點的指針域以繞過被刪除的節點。

單鏈表的頭刪：

單鏈表的尾刪：

單鏈表元素的查找：根據給定的值或位置查找鏈表中的節點。

單鏈表的鏈表銷毀：

驗證：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

完整代碼：

slist.h

slist.c

test.c

總結：

概念：

? ? ? ?單鏈表是一種鏈式存取的數據結構，用一組地址任意的存儲單元存放線性表中的數據元素。鏈表中的數據是以結點來表示的，每個結點的構成：元素 (數據元素的映象) + 指針 (指示后繼元素存儲位置)，元素就是存儲數據的存儲單元，指針就是連接每個結點的地址數據。單鏈表不要求邏輯上相鄰的兩個元素在物理位置上也相鄰，因此不需要連續的存儲空間。單鏈表是非隨機的存儲結構，即不能直接找到表中某個特定的結點。查找某個特定的結點時，需要從表頭開始遍歷，依次查找。?

單鏈表的結構

? ? ? ?在單鏈表中，每個節點由一個數據元素和一個指針構成。數據元素可以是任何類型，而指針則指向鏈表中的下一個節點。如果一個節點的指針為空（NULL），則表示它是鏈表的最后一個節點。單鏈表通常通過一個頭指針來訪問，頭指針指向鏈表的第一個節點。

一個典型的單鏈表節點的結構可以用以下C語言代碼表示：

typedef struct SListNode
{SLTDateType data;//數據域struct SListNode* next;// 指針域，指向下一個節點
}SListNode;

我們設定一個哨兵位頭節點給鏈表

 SListNode* head = NULL;

單鏈表的基本操作

單鏈表的基本操作包括初始化、遍歷、插入、刪除和查找等。

單鏈表的初始化：創建一個空鏈表，通常是通過創建一個頭節點，其指針域為空。

插入：

在鏈表的指定位置插入一個新節點，需要修改前一個節點的指針域。

單鏈表的頭插：

? ? ? ? 斷言確保頭指針地址有效，先去動態申請一個新節點，然后將新節點的下一個節點指向頭節點，將該新節點變為頭節點，（不需要判斷是否為空）


// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x) {assert(pplist);SListNode* newnode = BuySListNode(x);//SListNode* start = *pplist;newnode->next = *pplist;*pplist = newnode;}

單鏈表的尾插：

? ? ? 斷言確保頭指針地址有效，再申請一個新節點，分兩種情況，當鏈表為空時，直接新節點就是頭節點，鏈表不為空時，從頭節點遍歷到最后一個節點，將新節點設為最后一個節點的下一個節點

// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x) {assert(pplist);SListNode* newnode = BuySListNode(x);SListNode* end = *pplist;if (*pplist != NULL) //鏈表非空{while (end->next != NULL)end = end->next;end->next = newnode;}else //鏈表為空{*pplist = newnode;}
}

? ? ?動態創建一個SListNode大小的節點，然后看看是否創建成功，成功后將數據放入該節點，并將該節點的下一個位置，置為空；


// 動態申請一個節點
SListNode* BuySListNode(SLTDateType x) {SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL) {perror("malloc fail");return NULL;}// 初始化數據域和指針域newnode->data = x;newnode->next = NULL;return newnode;
}

單鏈表在pos位置前插入

// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x) {assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos)SListPushFront(pphead, x);else {SListNode* ne = pos;SListNode* newnode = BuySListNode(x);SListNode* start = *pphead;while (start->next != pos) {start = start->next;if (start == NULL) {assert(0);return;}}start->next = newnode;newnode->next = ne;}}

單鏈表在pos位置后插入

// 單鏈表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x) {assert(pos);/*SListNode* pre = pos;*/SListNode* newnode = BuySListNode(x);SListNode* ne = pos->next;pos->next = newnode;newnode->next = ne;}

單鏈表的遍歷打印：從頭節點開始，逐個訪問鏈表中的每個節點，直到達到鏈表的末尾。

? 創建一個頭指針，遍歷一遍鏈表，每遍歷一個節點，將這個節點的數據打印出來；

// 單鏈表打印
void SListPrint(SListNode* plist) {SListNode* head = plist;while (head != NULL) // 遍歷鏈表直到NULL{printf("%d->", head->data);head = head->next;}printf("NULL\n");}

單鏈表的刪除：刪除鏈表中的指定節點，需要修改前一個節點的指針域以繞過被刪除的節點。

單鏈表的頭刪：

? ? ? 斷言確保頭指針地址有效，以及頭指針不為空，將頭指針保存好，然后將頭指針置為頭指針的下一個位置，再將保存的指針釋放，并置為空

// 單鏈表頭刪
void SListPopFront(SListNode** pplist) {assert(pplist);assert(*pplist);SListNode* start = *pplist;*pplist = (*pplist)->next;free(start);start = NULL;}

單鏈表的尾刪：

斷言確保頭指針地址有效，以及頭指針不為空，分兩種情況，

一種是頭指針下一個節點為空，直接將其釋放并置為空；

另外一種情況呢，就是設兩個指針，找尾和尾的前驅節點，然后將尾節點釋放并置為空，再將尾的前驅節點的下一個置為空

// 單鏈表的尾刪
void SListPopBack(SListNode** pplist) {assert(pplist);assert(*pplist);//暴力檢查是否為空鏈表，空鏈表不能刪數據SListNode* end = *pplist;if ((*pplist)->next== NULL) {free(*pplist);*pplist = NULL;}else{//找尾SListNode* prev = *pplist;SListNode* tail = *pplist;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;//假如只有一個節點這里就會非法訪問}}

刪除pos位置

// 刪除pos位置
void SLTErase(SListNode** pphead, SListNode* pos) {assert(pphead);assert(*pphead);assert(pos);if (pos == *pphead)SListPopFront(pphead);else {SListNode* start = *pphead;while (start->next != pos) {start = start->next;if (start == NULL) {assert(0);return;}}start->next = pos ->next;free(pos);pos = NULL;}
}

單鏈表元素的查找：根據給定的值或位置查找鏈表中的節點。

? ? ? ? 創建一個節點start將頭節點指針復制一個副本，然后再指針不為空時不斷將其指向下一個的同時，看看該節點的值與所要查找的值是否相等，相等返回該節點的結構體指針，當遍歷完鏈表還沒有找到，返回NULL；

// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDateType x) {SListNode* start = plist;while (start != NULL) {if (start->data == x)return start;start = start->next;}return NULL;
}

單鏈表的鏈表銷毀：

? ? ? ?先判斷頭指針是否為空，為空直接返回，不為空時創建一個start頭指針儲存頭節點，再通過start遍歷整個鏈表，在遍歷過程中，將每一個節點釋放掉，最后再將頭節點釋放，置為空；

//銷毀鏈表
void SLTDestroy(SListNode** pphead) {if (*pphead == NULL) {return;}else {SListNode* start = *pphead;while (start != NULL) {SListNode* ne = start->next;free(start);start = ne;}free(*pphead);*pphead = NULL;}
}

驗證：

我們再創建一個main的測試函數測試一下我們實現的單鏈表的各個功能有沒有問題：

完整代碼：

slist.h

#pragma once
// slist.h
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;// 動態申請一個節點
SListNode* BuySListNode(SLTDateType x);
// 單鏈表打印
void SListPrint(SListNode* plist);
// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 單鏈表的尾刪
void SListPopBack(SListNode** pplist);
// 單鏈表頭刪
void SListPopFront(SListNode** pplist);
// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 單鏈表在pos位置之后插入x
// 分析思考為什么不在pos位置之前插入
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 單鏈表刪除pos位置之后的值
// 分析思考為什么不刪除pos位置？
void SListEraseAfter(SListNode* pos);// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x);
// 刪除pos位置
void SLTErase(SListNode** pphead, SListNode* pos);
void SLTDestroy(SListNode** pphead);

slist.c

#include "slist.h"
// 動態申請一個節點
SListNode* BuySListNode(SLTDateType x) {SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL) {perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;
}
// 單鏈表打印
void SListPrint(SListNode* plist) {SListNode* head = plist;while (head != NULL) {printf("%d->", head->data);head = head->next;}printf("NULL\n");}
// 單鏈表尾插
void SListPushBack(SListNode** pplist, SLTDateType x) {assert(pplist);SListNode* newnode = BuySListNode(x);SListNode* end = *pplist;if (*pplist != NULL) {while (end->next != NULL)end = end->next;end->next = newnode;}else {*pplist = newnode;}
}
// 單鏈表的頭插
void SListPushFront(SListNode** pplist, SLTDateType x) {assert(pplist);SListNode* newnode = BuySListNode(x);//SListNode* start = *pplist;newnode->next = *pplist;*pplist = newnode;}
// 單鏈表的尾刪
void SListPopBack(SListNode** pplist) {assert(pplist);assert(*pplist);//暴力檢查是否為空鏈表，空鏈表不能刪數據SListNode* end = *pplist;if ((*pplist)->next== NULL) {free(*pplist);*pplist = NULL;}else{//找尾SListNode* prev = *pplist;SListNode* tail = *pplist;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;//假如只有一個節點這里就會非法訪問}}
// 單鏈表頭刪
void SListPopFront(SListNode** pplist) {assert(pplist);assert(*pplist);SListNode* start = *pplist;*pplist = (*pplist)->next;free(start);start = NULL;}
// 單鏈表查找
SListNode* SListFind(SListNode* plist, SLTDateType x) {SListNode* start = plist;while (start != NULL) {if (start->data == x)return start;start = start->next;}return NULL;
}
// 單鏈表在pos位置之后插入xvoid SListInsertAfter(SListNode* pos, SLTDateType x) {assert(pos);/*SListNode* pre = pos;*/SListNode* newnode = BuySListNode(x);SListNode* ne = pos->next;pos->next = newnode;newnode->next = ne;}
// 單鏈表刪除pos位置之后的值void SListEraseAfter(SListNode* pos) {assert(pos);assert(pos->next);SListNode* pre = pos;SListNode* ne = pos->next->next;free(pos->next);pos->next = ne;
}// 在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x) {assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos)SListPushFront(pphead, x);else {SListNode* ne = pos;SListNode* newnode = BuySListNode(x);SListNode* start = *pphead;while (start->next != pos) {start = start->next;if (start == NULL) {assert(0);return;}}start->next = newnode;newnode->next = ne;}}
// 刪除pos位置
void SLTErase(SListNode** pphead, SListNode* pos) {assert(pphead);assert(*pphead);assert(pos);if (pos == *pphead)SListPopFront(pphead);else {SListNode* start = *pphead;while (start->next != pos) {start = start->next;if (start == NULL) {assert(0);return;}}start->next = pos ->next;free(pos);pos = NULL;}
}
void SLTDestroy(SListNode** pphead) {if (*pphead == NULL) {free(pphead); pphead = NULL;}else {SListNode* start = *pphead;while (start != NULL) {SListNode* ne = start->next;free(start);start = ne;}*pphead = NULL;}
}

test.c

#include "slist.h"int main() {SListNode* head = NULL; // 尾插SListPushBack(&head, 1);SListPushBack(&head, 2);SListPushBack(&head, 3);printf("鏈表內容（尾插入后）：");SListPrint(head);// 頭插SListPushFront(&head, 0);printf("鏈表內容（頭插入后）：");SListPrint(head);// 查找SListNode* found = SListFind(head, 2);if (found) {printf("找到節點：%d\n", found->data);}else {printf("未找到節點\n");}// 頭刪SListPopFront(&head);printf("鏈表內容（頭刪后）：");SListPrint(head);// 尾刪SListPopBack(&head);printf("鏈表內容（尾刪后）：");SListPrint(head);// pos插入SListInsertAfter(head, 4); printf("鏈表內容（插入4后）：");SListPrint(head);// pos刪除SLTErase(&head, head->next);printf("鏈表內容（刪除第二個節點后）：");SListPrint(head);// 銷毀SLTDestroy(&head);//destroy后不能再訪問// printf("鏈表內容（銷毀后）：");//SListPrint(head); return 0;
}