【数据结构】带头结点的单链表

article/2025/11/9 8:32:58

文章目录

    • 一、单链表的概念
    • 二、结构体声明:
    • 三、函数
      • 1.购买节点
      • 2.释放节点
      • 3.单链表的初始化
      • 4.判空函数
      • 5.获取单链表有效值个数
      • 6.按数据查询(返回含有此数据节点的前驱)
      • 7.按数据查询(返回含有当前数据的节点)
      • 8.按pos位置查节点的前驱
      • 9.按pos位置查节点
      • 10.按照节点插入数据
      • 11.头插法
      • 12.尾插法
      • 13.按pos位置插入
      • 14.删除ptr指针后续节点
      • 15.删除第一个节点
      • 16.删除最后一个节点
      • 17.删除数据域和val相等的元素
      • 18.删除数据域和val相等的所有元素
      • 19.清空链表
      • 20.销毁链表
    • 四.完整代码
      • 1. My_LinkList.h
      • 2. My_LinkList.cpp

一、单链表的概念

单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:数据域(数据元素的映象) + 指针域(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。
单链表逻辑上相邻,物理上不一定相邻
在这里插入图片描述

二、结构体声明:

typedef int ELEM_TYPE;//有效数据节点结构体设计:
typedef struct ListNode
{ElemType data;//数据域struct ListNode* next;//指针域
}ListNode,*LinkList;

三、函数

1.购买节点

从堆区申请一个节点大小的内存,并将申请好内存的地址返回。
代码如下:

//购买节点
ListNode* Buynode()
{ListNode* s = (ListNode*)malloc(sizeof(ListNode));if (s == NULL) exit(1);memset(s, 0, sizeof(ListNode));//将节点内数据全部填充为0return s;//返回申请成功的节点地址
}

2.释放节点

每次删除节点之后都需要用 free()来释放,否则会造成严重的内存泄漏
代码如下:

//释放节点
void Freenode(ListNode*p)
{free(p);p = NULL;//防止野指针
}

3.单链表的初始化

将头节点的数据域浪费掉,头节点的指针域2指为NULL,等待插入数据。

单链表设计头节点的目的

  • 防止单链表是空的而设的。当链表为空的时候,带头结点的头指针就指向头结点,如果当链表为空的时候,头结点的指针域的数值为NULL。

  • 为了方便单链表的特殊操作,插入在表头或者删除第一个结点。这样就保持了单链表操作的统一性。

  • 单链表加上头结点之后,无论单链表是否为空,头指针始终指向头结点,因此空表和非空表的处理统一,方便了单链表的操作,也减少了程序的复杂性和出现bug的机会。
    代码实现:

//初始化 //对头结点进行初始化
ListNode* InitList()  
{ListNode* s = Buynode();//申请一个头节点s->next = NULL;//将头节点的next域置为空return s;
}

4.判空函数

判断一个单链表是否是空链,只需要判断头节点的指针域是否为NULL

(如果不是一个空链,那么必定存在一个有效值节点,只要存在有效值节点,那么头结点的指针域必不可能指向空,而是指向第一个有效值节点)
代码如下:

//判空
bool IsEmpty(LinkList head)
{assert(head != NULL);return head->next == NULL;
}

5.获取单链表有效值个数

用for循环遍历单链表,使用一个变量充当计数器,每次循环+1,当 p->next == NULL 的时候,返回计数器的值。
代码如下:

//获取单链表有效值个数
int GetSize(LinkList head)
{assert(head != NULL);int size = 0;//计数器LinkList p = head->next;//从头结点的下一个开始while (p != NULL){size++;p = p->next;}return size;
}

6.按数据查询(返回含有此数据节点的前驱)

通过两个指针 prev 和 p 进行遍历,prev从头节点开始,p从 头节点的next域开始,两个指针同步前进同步停止。
当 p->data == val(传进来的值)时,循环结束返回 prev的值
否则当p ==NULL 时说明将链表遍历完成都没有找到。返回NULL;

在这里插入图片描述
当要查询 3 的时候,返回的是 2 的地址,此时prev->next->data == 3
在这里插入图片描述
代码如下:

ListNode* FindValue_Prev(LinkList head, ElemType val)
{assert(head != NULL);ListNode* prev = head;//headListNode* p = head->next;//head->nextwhile (p != NULL && p->data != val)//循环结束条件{prev = p;//先将prev向后走一步p = p->next;//然后p向后走一步}if (p == NULL)//当p ==NULL 说明没有找到 返回NULL{prev = NULL;}return prev;
}

7.按数据查询(返回含有当前数据的节点)

通过调用查找前驱的函数找到它的前驱,那么前驱的后继就是当前查询的节点。
如果p 是NULL 的话,说明没有找到
代码如下:

ListNode* FindValue(LinkList head, ElemType val)
{assert(head != NULL);ListNode* p = FindPos_Prev(head, val);//调用查找前驱的函数if (p != NULL){p = p->next;}return p;
}

8.按pos位置查节点的前驱

通过两个指针 prev 和 p 和一个计数器 i 进行遍历,prev从头节点开始,p从 头节点的next域开始,两个指针同步前进同步停止。
但是在循环之前需要判断 pos位置是否合法。当pos<1 时 返回NULL

当 p == NULL 的时候说明没有找到退出循环返回 NULL
当 i==pos 时 说明找到了这个数据的节点,此时返回prev

代码如下:

ListNode* FindPos_Prev(LinkList head, int pos)
{assert(head != NULL);int i = 1;ListNode* prev = head;ListNode* p = head->next;if (pos < 1){return NULL;}while (p != NULL && i < pos){prev = p;p = p->next;i = i + 1;}if (p == NULL){prev = NULL;}return prev;
}

9.按pos位置查节点

通过调用查找前驱的函数找到它的前驱,那么前驱的后继就是当前查询的节点。
如果p 是NULL 的话,说明没有找到
代码如下:

ListNode* FindPos(LinkList head, int pos)
{assert(head != NULL);ListNode* p = FindPos_Prev(head,pos);if (p != NULL){p = p->next;}return p;
}

10.按照节点插入数据

我们认为,形参中传入进来的节点地址就是存在的(通过其他函数嵌套使用,并不可单独使用)
直接插入即可。
在这里插入图片描述

首先通过 **Buynode()**函数申请一个节点,保存val值
然后把ptr->next赋值给s->next 此时s和ptr都指向 300 这个地址
然后将 s 的地址赋值给 ptr->next ,完成插入
在这里插入图片描述
代码如下:

bool Insert_Next(LinkList head, ListNode* ptr, ElemType val)
{assert(head != NULL);if (NULL == ptr){return false;}ListNode* s = Buynode();s->data = val;s->next = ptr->next;ptr->next = s;return true;
}

11.头插法

首先通过 **Buynode()**函数申请一个节点,保存val值
然后把头节点指向的next的地址赋值给 s->next
在这里插入图片描述
最后 把s 的地址赋值给头节点的next域
在这里插入图片描述
代码如下:

void Push_Front(LinkList head, ElemType val)
{assert(head != NULL);ListNode* s = Buynode();s->data = val;s->next = head->next;head->next = s;
}

12.尾插法

先使用一个p指针遍历链表到 p->next == NULL 说明此时p指针所指向的节点就是尾节点
使用**Buynode()**申请一个节点,将val值赋值给s 并且将s->next置为空
在这里插入图片描述
最后将 s 的地址赋值给 p->next ,完成尾插
在这里插入图片描述
代码如下:

void Push_Back(LinkList head, ElemType val)
{assert(head != NULL);ListNode* p = head;ListNode* s = Buynode();while (p->next != NULL){p = p->next;}//退出循环后p指向尾节点s->data = val;s->next = p->next;p->next = s;
}

13.按pos位置插入

首先判断pos的合法性,如果pos<1则退出
然后用while循环判断链表是否结束以及 计数链表的位置
此时while循环有两种情况结束

  • 当 s->next == NULL 时,说明 s指向的链表的尾部,此处退出循环,判断pos和i的关系如果pos>i 说明pos位置远远大于链表有效长度,无法插入。
  • 当 i>pos 退出循环时,说明已经找到了pos位置,并且s->next就是待插入位置,此时调用**Insert_Next()**函数,传入s的地址,完成插入
    代码如下:
bool InsertPos(LinkList head, int pos, ElemType val)
{assert(head != NULL);if (pos < 1){return false;}//判断p的合法性ListNode* s = head;int i = 1;//计数链表位置while (s->next != NULL && i < pos){s = s->next;i++;}if (pos > i){return false;}return Insert_Next(head, s, val);

14.删除ptr指针后续节点

我们认为,形参中传入进来的节点地址就是存在的(通过其他函数嵌套使用,并不可单独使用)
直接删除即可。
首先 用一个指针保存ptr ->next 的值(也就是待删除结点的地址)
在这里插入图片描述
然后将 p->next 的值赋值给 ptr->next
在这里插入图片描述
最后使用 Freenode()函数释放p节点
在这里插入图片描述
完成删除
代码如下:

bool Earse_Next(LinkList head, ListNode* ptr)
{assert(head != NULL);if (ptr == NULL||ptr->next==NULL)//判断ptr和ptr->next是一个有效值{return false;}ListNode* p = ptr->next;ptr->next = p->next;Freenode(p);//释放节点return true;
}

15.删除第一个节点

直接调用 **Earse_Next()**函数,传入头节点
头节点的后续节点就是第一个节点。
代码如下:

void Pop_Front(LinkList head)
{assert(head != NULL);Earse_Next(head, head);
}

16.删除最后一个节点

通过两个指针 pre和 p分别指向头节点和头节点的下一个节点
使用while循环找到 最后一个节点的前驱
然后调用 **Earse_Next()**函数,完成删除
代码如下:

void Pop_Back(LinkList head)
{assert(head != NULL);ListNode* pre = head;ListNode* p = head->next;while (p != NULL && p->next != NULL){pre = p;p = p->next;}Earse_Next(head, pre);
}

17.删除数据域和val相等的元素

通过 **FindPos_Prev()函数查到val数据的节点地址
然后通过
Earse_Next()**函数,完成删除
代码如下:

bool Remove(LinkList head, ElemType val)
{assert(head != NULL);return Earse_Next(head, FindPos_Prev(head, val));
}

18.删除数据域和val相等的所有元素

通过while循环 不断调用**FindValue_Prev()函数返回地址
然后通过通过
Earse_Next()函数,完成删除一个数据
直到
FindValue_Prev()**函数返回地址为NULL的时候,说明链表里没有这个数据退出循环,完成删除。
代码如下:

void Remove_ALL(LinkList head, ElemType val)
{assert(head != NULL);ListNode* s = NULL;while ((s = FindValue_Prev(head, val)) != NULL){Earse_Next(head, s);}
}

19.清空链表

不断调用头删函数,直到除了头节点以外没有任何节点(判空函数)
代码如下:

void ClearList(LinkList head)
{assert(head != NULL);while (!IsEmpty(head)){Pop_Front(head);}
}

20.销毁链表

清空链表并且释放头节点
代码如下:

void DestroyList(LinkList head)
{assert(head != NULL);ClearList(head);Freenode(head);
}

四.完整代码

1. My_LinkList.h

#ifndef MY_LINKLIST_S
#define MY_LINKLIST_S
typedef int ElemType;
typedef struct ListNode
{ElemType data;//数据元素struct ListNode* next;//指针域
}ListNode,*LinkList;//初始化函数 head
ListNode* InitList();//清空链表
void ClearList(LinkList head);//销毁链表
void DestroyList(LinkList head);//判空函数 
bool IsEmpty(LinkList head);//返回数据节点的个数
int GetSize(LinkList head);//传入头节点打印函数
void PrintList(LinkList head);//按数据查询返回含有此数据节点的前驱
ListNode* FindValue_Prev(LinkList head, ElemType val);//按数据查询 返回含有当前数据的节点
ListNode* FindValue(LinkList head, ElemType val);//按pos位置查节点
ListNode* FindPos(LinkList head, int pos);//按pos位置查节点的前驱
ListNode* FindPos_Prev(LinkList head, int pos);//按节点插入
bool Insert_Next(LinkList head, ListNode* ptr, ElemType val);//从头插入
void Push_Front(LinkList head, ElemType val);//尾插法
void Push_Back(LinkList head, ElemType val);//按pos位置插入
bool InsertPos(LinkList head, int pos, ElemType val);//删除ptr指针后续节点
bool Earse_Next(LinkList head, ListNode* ptr);//删除第一个节点
void Pop_Front(LinkList head);//删除最后一个节点
void Pop_Back(LinkList head);//删除数据域和val相等的元素
bool Remove(LinkList head, ElemType val);//删除数据域和val相等的所有元素
void Remove_ALL(LinkList head, ElemType val);

2. My_LinkList.cpp

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include"My_LinkList.h"ListNode* Buynode()//购买节点
{ListNode* s = (ListNode*)malloc(sizeof(ListNode));if (s == NULL) exit(1);memset(s, 0, sizeof(ListNode));//将节点内数据全部填充为0return s;//返回申请成功的节点地址
}void Freenode(ListNode*p)
{free(p);p = NULL;//防止野指针
}bool IsEmpty(LinkList head)
{assert(head != NULL);return head->next == NULL;
}int GetSize(LinkList head)
{assert(head != NULL);int size = 0;LinkList p = head->next;while (p != NULL){size++;p = p->next;}return size;
}ListNode* InitList()  
{ListNode* s = Buynode();s->next = NULL;return s;
}void PrintList(LinkList head)
{assert(head != NULL);ListNode* p = head->next;while (p != NULL){printf("%d ", p->data);p = p->next;}printf("\n");
}ListNode* FindValue(LinkList head, ElemType val)
{assert(head != NULL);ListNode* p = FindPos_Prev(head, val);if (p != NULL){p = p->next;}return p;
}ListNode* FindValue_Prev(LinkList head, ElemType val)
{assert(head != NULL);ListNode* prev = head;//headListNode* p = head->next;//head->nextwhile (p != NULL && p->data != val){prev = p;p = p->next;}if (p == NULL){prev = NULL;}return prev;
}ListNode* FindPos(LinkList head, int pos)
{assert(head != NULL);ListNode* p = FindPos_Prev(head,pos);if (p != NULL){p = p->next;}return p;
}ListNode* FindPos_Prev(LinkList head, int pos)
{assert(head != NULL);int i = 1;ListNode* pre = head;ListNode* p = head->next;if (pos < 1){return NULL;}while (p != NULL && i < pos){pre = p;p = p->next;i = i + 1;}if (p == NULL){pre = NULL;}return pre;
}bool Insert_Next(LinkList head, ListNode* ptr, ElemType val)
{assert(head != NULL);if (NULL == ptr){return false;}ListNode* s = Buynode();s->data = val;s->next = ptr->next;ptr->next = s;return true;
}void Push_Front(LinkList head, ElemType val)
{assert(head != NULL);ListNode* s = Buynode();s->data = val;s->next = head->next;head->next = s;
}void Push_Back(LinkList head, ElemType val)
{assert(head != NULL);ListNode* p = head;ListNode* s = Buynode();while (p->next != NULL){p = p->next;}s->data = val;s->next = p->next;p->next = s;
}bool InsertPos(LinkList head, int pos, ElemType val)
{assert(head != NULL);if (pos < 1){return false;}ListNode* s = head;int i = 1;while (s->next != NULL && i < pos){s = s->next;i++;}if (pos > i){return false;}return Insert_Next(head, s, val);/*p->data = val;p->next = s->next;s->next = p; */
}bool Earse_Next(LinkList head, ListNode* ptr)
{assert(head != NULL);if (ptr == NULL||ptr->next==NULL){return false;}ListNode* p = ptr->next;ptr->next = p->next;Freenode(p);return true;
}
void Pop_Front(LinkList head)
{assert(head != NULL);Earse_Next(head, head);
}
void Pop_Back(LinkList head)
{assert(head != NULL);ListNode* pre = head;ListNode* p = head->next;while (p != NULL && p->next != NULL){pre = p;p = p->next;}Earse_Next(head, pre);
}
bool Remove(LinkList head, ElemType val)
{assert(head != NULL);return Earse_Next(head, FindPos_Prev(head, val));/*ListNode* pre = head;ListNode* p = head->next;while (p != NULL && p->data != val){pre = p;p = p->next;}if (p != NULL){Earse_Next(head, pre);}*/
}
void Remove_ALL(LinkList head, ElemType val)
{assert(head != NULL);ListNode* s = NULL;while ((s = FindValue_Prev(head, val)) != NULL){Earse_Next(head, s);}
}
void ClearList(LinkList head)
{assert(head != NULL);while (!IsEmpty(head)){Pop_Front(head);}
}
void DestroyList(LinkList head)
{assert(head != NULL);ClearList(head);Freenode(head);
}

http://chatgpt.dhexx.cn/article/2F7GvwtJ.shtml

相关文章

【考研】分清带头结点和不带头结点的单链表

CSDN话题挑战赛第2期 参赛话题&#xff1a;学习笔记 前言 为分清带结点与不带头结点的单链表操作&#xff0c;本文以图文和表格形式描述了两者之间的区别。考研中&#xff0c;数据结构的单链表操作是重要考点&#xff0c;其中&#xff0c;比较常考带头结点的链表操作。 所以&…

【带头结点的单链表】

带头结点的单链表 前言一、带头结点的单链表结构体设计1. 带头结点的单链表2. 结构体声明 二、函数实现1. 初始化2. 申请新节点3. 头插4. 尾插5. 按位置插入6. 头删7. 尾删8. 销毁 总结 前言 单链表的概念&#xff1a; 单链表是一种链式存取的数据结构&#xff0c;用一组地址…

带头结点单链表 (详解)

单链表结构体 结构体后的*List是一个指向结构体的指针类型&#xff0c;我们通过它来定义该类型的指针。 如&#xff1a;List p ;  则这个p就是指向LinkedList结构体的一个指针&#xff0c;也就是单链表的头指针。&#xff08;所以说头指针是必然存在的&#xff0c;但单链表不…

数据结构-带头节点的单链表(C语言)超详细讲解

前面我们学到线性表的顺序存储结构&#xff08;顺序表&#xff09;&#xff0c;发现它有着明显的缺点&#xff1a;插入和删除元素时需要频繁的移动元素&#xff0c;运算效率低。必须按事先估计的最大元素个数申请连续的存储空间。存储空间估计大了&#xff0c;造成浪费空间&…

Windows配置端口转发绕过samba 445端口限制共享linux磁盘

概述 Samba是在Linux和UNIX系统上实现SMB协议的一个免费软件。SMB&#xff08;Server Messages Block&#xff0c;信息服务块&#xff09;是一种在局域网上共享文件和打印机的一种通信协议&#xff0c;它为局域网内的不同计算机之间提供文件及打印机等资源的共享服务。SMB协议…

Linux安装samba服务

个人推荐: &#x1f4e2;&#x1f4e2;&#x1f4e2; 前些天发现了一个蛮有意思的人工智能学习网站,8个字形容一下 "通俗易懂&#xff0c;风趣幽默"&#xff0c;感觉非常有意思,忍不住分享一下给大家。点击跳转到教程。 一&#xff1a;使用到的Linux指令 1:检查是否…

samba服务

目录 一&#xff1a;samba概述 1.1samba简介 1.2samba的监听端口 1.3samba的进程 1.4samba安全级别 二&#xff1a;samba服务的特点 三&#xff1a;samba的主要作用 四&#xff1a;常见文件服务器软件的对比 五&#xff1a;samba配置文件 5.1samba主配置文件 5.2常用…

Samba配置详解

一、简介 Samba是一个能让Linux系统应用Microsoft网络通讯协议的软件&#xff0c;而SMB是Server Message Block的缩写&#xff0c;即为服务器消息块 &#xff0c;SMB主要是作为Microsoft的网络通讯协议&#xff0c;后来Samba将SMB通信协议应用到了Linux系统上&#xff0c;就形成…

Windows 10 下修改 smb 连接的默认端口(445)

服务器&#xff08;samba 共享文件夹所在服务器&#xff09;上已经frp外网映射445 端口转接4455 windows10 右键开始–powershell&#xff08;管理员&#xff09; netsh interface portproxy add v4tov4 listenport445 listenaddress127.0.0.1 connectport4455 connectaddress …

Samba配置与使用

1.安装Samba Centos7系统 yum -y install samba2. 查看安装情况(可选) rpm -qa |grep samba3.设置开机自启 systemctl enable smb.service systemctl enable nmb.service4.启动服务 //启动服务 systemctl start smb.service //查看启动服务的状态 systemctl status smb.se…

Linux——samba服务器配置

实验目的&#xff1a;实现Linux的主机与windows系列主机进行文件的传输 实验环境&#xff08;保证两台主机能够相互访问&#xff09;&#xff1a; 1、Windows7&#xff1a;客户端 2、centos7&#xff1a; 服务端&#xff08;文件共享&#xff09; 实验案例&#xff1a; J…

samba服务2---安装与端口

具体说明 一、安装二、samba的守护进程三、启动samba服务 一、安装 安装简单&#xff0c;centos 8 &#xff1a;dnf -y install samba samba-client就可以了 主要安装的包是这些&#xff0c;我们一一来说。 samba # 主服务包 samba-common # 通用工具包 samba-common-libs # …

在windows系统中映射网络驱动器时,如何通过非455端口远程访问Linux服务器的Samba服务

声明 通常情况下&#xff0c;在windows中通过Linux服务器的Samba服务去映射网络驱动器时候&#xff0c;一般默认就是直接填入内网Linux服务器ip即可&#xff0c;它会默认445端口。若是我的windows并不和Linux服务器在一个网段时&#xff0c;该如何操作呢&#xff1f; 1 用管理…

Winows通过非445端口远程访问公网Samba

一、用管理员账号打开CMD&#xff0c;以下命令查询445端口占用情况 输入命令&#xff1a; netstat -ano | findstr 445可以看出是pid为4的进程进行监听&#xff0c;从任务管理器上看是名叫System&#xff0c;备注"NT Kernel&System"。 二、禁用该服务 本地 …

Samba服务的介绍,安装和使用

一、samba概述 Samba是在Linux和UNIX系统上实现SMB协议的一个免费软件&#xff0c;由服务器及客户端程序构成。SMB&#xff08;Server Messages Block&#xff0c;信息服务块&#xff09;是一种在局域网上共享文件和打印机的一种通信协议。SMB协议是客户机/服务器型协议&#…

samba更改其他端口,如何与windows共享文件夹

这个需求来自于腾讯云之类的运营商将445 139之类的端口封禁&#xff0c;samba不能使用455端口 网上的解决办法是几乎都是进行端口转发将445端口的进出都转发到其他端口 我自己想出了一种新的办法&#xff0c;就是有点慢&#xff0c;但是不需要去对到本地计算机的445端口进行…

Samba 服务详解

文章目录 一、Samba 概述1. samba 简介2. samba 监听端口3. samba 进程4. samba 用户5. samba 安全级别6. samba 配置文件7. 常用配置文件参数 二、搭建匿名用户共享服务器&#xff08;Linux - Linux&#xff09;1. 环境准备2. 服务端3. 客户端4. 服务端上验证 三、Windows 访问…

samba使用指定端口windows访问linux

samba使用指定端口 背景 公司因为感染病毒&#xff0c;所以直接把共享文件的端口给封了&#xff01;&#xff01;&#xff01;然后造成写代码特别特别不方便&#xff0c;这几天用ftp想吐&#xff0c;跟公司相关人员理论了半天&#xff0c;居然还跟我说用git同步更好&#xff…

SMB服务搭建及各端非标端口连接配置

写在前面 目前有个pc&#xff08;win10&#xff09;同步文件到ipad的需求&#xff0c;代替使用微信带来的数据空间占用问题。 初始阶段的方案是pc端共享文件夹&#xff0c;ipad使用“文件”app接入&#xff0c;每到次日这个同步就会失效ipad无法连接到共享目录。起初以为是重启…

samba更改端口后用windows访问

前言 有时候我们需要在服务器上使用samba服务&#xff0c;然后在windows端访问共享目录。但是samba使用的是139和455端口&#xff0c;这两个端口由于勒索病毒之类的安全问题可能被运营商直接封了&#xff0c;所以没办法&#xff0c;只能使用更改端口&#xff0c;但是更改端口后…