当前位置：首页 > news >正文

数据结构---单链表的增删查改

news 来源：原创 2025/5/20 1:05:26

前言：

经过了几个月的漫长岁月，回头时年迈的小编发现，数据结构的内容还没有写博客，于是小编赶紧停下手头的活动，补上博客以洗清身上的罪孽

前言

概念：

单链表的结构

我们设定一个哨兵位头节点给链表

单链表的基本操作

插入：

单链表的头插：

单链表的尾插：

单链表的遍历打印：从头节点开始，逐个访问链表中的每个节点，直到达到链表的末尾。

单链表的删除：删除链表中的指定节点，需要修改前一个节点的指针域以绕过被删除的节点。

单链表的头删：

单链表的尾删：

单链表元素的查找：根据给定的值或位置查找链表中的节点。

单链表的链表销毁：

验证：

完整代码：

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;
}

单链表的遍历打印：从头节点开始，逐个访问链表中的每个节点，直到达到链表的末尾。

创建一个头指针，遍历一遍链表，每遍历一个节点，将这个节点的数据打印出来；

// 单链表打印
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;//假如只有一个节点这里就会非法访问}}

单链表元素的查找：根据给定的值或位置查找链表中的节点。

创建一个节点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;
}

总结：

本篇关于单链表的讲解到这里就结束啦，后续小编会带来更多精彩实用的内容，对你有帮助的可以点个赞，欢迎各位队列交流学习

前言：

概念：

单链表的结构

我们设定一个哨兵位头节点给链表

单链表的基本操作

插入：

单链表的头插：

单链表的尾插：

单链表的遍历打印：从头节点开始，逐个访问链表中的每个节点，直到达到链表的末尾。

单链表的删除：删除链表中的指定节点，需要修改前一个节点的指针域以绕过被删除的节点。

单链表的头删：

单链表的尾删：

单链表元素的查找：根据给定的值或位置查找链表中的节点。

单链表的链表销毁：

验证：

完整代码：

slist.h

slist.c

test.c

总结：

相关文章：