链表C语言实现--单向链表

article/2025/10/5 22:19:32

        线性结构的链式存储也称为链表，相比于顺序表，链表能够解决顺序表中空间资源浪费问题以及空间不足的问题。链表的每一个结点包含数据域和指针域，而每一个结点在内存中的地址是不连续的，且能适应动态变化。在数据插入和数据删除操作效率比顺序表高，但在数据查找和修改效率较低，需要遍历链表。

  链表又分为：

  • 有头链表，头节点不存数据，所以数据操作都从头节点所指的下一节点开始，就不会误操作到头节点。故更加常用。

  • 无头链表，第一个节点就存数据，但数据操作就要判断是否是头节点，不能对头节点操作，特别像删除操作就不能对头节点进行。

 本文采用有头链表，链表的每个结点的都用一个结构体表示，唯一特殊的就是头结点不存数据，只存指向下一个结点的指针。结构体定义如下：

typedef int data_t;
typedef struct linklist
{data_t data;//数据域struct linklist *next;//指针域
}LinkList;

首先编写头文件，将链表所涉及的增删改查操作都分别封装成模块

/*===============================================
*   文件名称：linklist.h
*   创 建 者： x m    
*   创建日期：2022年07月28日
*   描    述：
================================================*/
#ifndef _LINKLIST_
#define _LINKLIST_
#include <stdio.h>
#include <stdlib.h>typedef int data_t;
typedef struct linklist
{data_t data;//数据域struct linklist *next;//指针域
}LinkList;//创建头节点
LinkList *Creat_Linklist();
//判空
int Linklist_Is_Empty(LinkList *h_node);
//求表长
int Linklist_length(LinkList *h_node);
//从表头插入数据
void Linklist_Insert_head(LinkList *h_node,data_t data);
//打印
void Linklist_Show(LinkList *h_node);
//按位置插入数据
void Linklist_Insert_Pos(LinkList *h_node,int pos,data_t data);//按位置删除
void Linklist_Delete_Pos(LinkList *h_node,int pos);
//按数据值删除
void Linklist_Delete_Data(LinkList *h_node,data_t data);
//按位置查找
data_t Linklist_Search_Pos(LinkList *h_node,int pos);
//按数据值查找
int Linklist_Search_Data(LinkList *h_node,data_t data);
//按位置修改
void Linklist_Change_Pos(LinkList *h_node,int pos,data_t data);
//按值修改
void Linklist_Change_data(LinkList *h_node,data_t data,data_t newdata);
//清空链表
void Linklist_Empty(LinkList *h_node);
//销毁链表
void Linklist_Delete(LinkList **h_node);
//循环头插10次
void Test_Insert(LinkList *h_node);#endif

在模块文件内实现各个功能

1.创建头结点

头结点申请到空间后，因为其数据域不使用，默认-1就行，应为当前没有下一节点，所以指针域初始化为空NULL，然后返回头结点地址给其他模块和主函数使用。

LinkList *Creat_Linklist()
{LinkList *head=(LinkList*)malloc(sizeof(LinkList));if(NULL==head){printf("malloc error!\n");return NULL;}head->data=-1;head->next=NULL;return head;
}

2.判空

即判断链表当前是否为空表，没有存储数据的结点。那就是判断头结点的下一节点是否为空

int Linklist_Is_Empty(LinkList *h_node)
{if(h_node->next==NULL)return 0;//表空返回0else return 1;
}

3.求表长

表长指的是链表存储数据的结点个数，头结点不算。所以需要从第一个结点开始遍历链表，链表结点的偏移和顺序表不同，要想找到下一个结点，就得通过当前结点的指针域（next）指向下一个结点，直到下一个结点地址为NULL，结束遍历。

int Linklist_length(LinkList *h_node)
{int len=0;LinkList *p=h_node->next;//p指向头节点后的第一个节点while(p!=NULL){len++;// printf("%d,",p->data);//打印数据p=p->next;}return len;
}

4.头插法添加数据

从头结点后添加结点存储数据

 第一步是将新申请的结点的next指针指向原来头结点后的第一个结点，

第二步则是将头结点的next指针指向新节点

两步先后顺序不能反，如果反过来的话，会丢失原来第一个结点的地址，因为头结点next保存的地址被新节点地址所覆盖。

void Linklist_Insert_head(LinkList *h_node,data_t data)
{LinkList *p=(LinkList *)malloc(sizeof(LinkList));if(NULL==p){printf("malloc new node error!\n");return ;}p->data=data;//存数据p->next=h_node->next;//新节点拿到下一节点的地址h_node->next=p; //上一节点刷新得到新节点的地址
}

5.打印

即遍历链表，打印每个结点存的数据

void Linklist_Show(LinkList *h_node)
{if(Linklist_Is_Empty(h_node)==0){printf("表为空，无法打印\n");return ;}LinkList *p=h_node->next;//p指向头节点后的第一个节点while(p!=NULL){printf("%d,",p->data);//打印数据p=p->next;}
}

6.按位置插入数据

这里的位置是从第一个存储数据的结点开始，我是从0开始计算位置，也就是第一个数据结点的位置为0，第二个数据结点的位置为1....这和数组存储数据的下标相似，所以我就按这种方式表达位置。

按位置插入和头插法有些区别，头插法是首先知道头结点的地址的，即函数参数传进来。而按位置插要根据传入的位置来找到要插入的结点的前一结点地址，

void Linklist_Insert_Pos(LinkList *h_node,int pos,data_t data)
{LinkList * new=(LinkList*)malloc(sizeof(LinkList));if(NULL==new){printf("malloc new node error!\n");return ;}LinkList *p=h_node;if(pos<0 || pos>Linklist_length(p)){printf("pos errror!\n");return ;}while(pos--){p=p->next;}new->data=data;new->next=p->next;p->next=new;}

 7.按位置删除

删除结点首先要找到其前一结点的位置并将其next指针指向要删除结点的下一结点地址，并释放删除结点的空间。

 例如上图，删除位置1的结点，则位置0结点的next指针指向位置2结点，但是这样为丢失位置1结点的地址，无法释放其空间。所以需要定义一个临时变量用来保存位置1的地址，在链表完成删除结点后，释放该结点空间。

void Linklist_Delete_Pos(LinkList *h_node,int pos)
{if(Linklist_Is_Empty(h_node)==0){printf("表为空，无法删除");return ;}LinkList *p=h_node;LinkList *q=NULL;if(pos<0 || pos>=Linklist_length(p)){printf("pos errror!\n");return ;}while(pos--){p=p->next;}q=p->next;//q指向pos这个位置上的节点，用于后续删除// p->next=p->next->next;//等价于下面这个语句p->next=q->next;free(q);q=NULL;
}

8.按数据删除结点

首先遍历链表，找到存储该数据的结点，然后删除该结点。删除结点的思路和按位置删除一样，找到要删除结点的前一结点地址即可。

void Linklist_Delete_Data(LinkList *h_node,data_t data)
{if(Linklist_Is_Empty(h_node)==0){printf("表为空，无法删除");return ;}LinkList *p=h_node;//p用来指目标值节点的前一节点LinkList *q=h_node->next;//q用来指向目标值所在节点while(q!=NULL){if(q->data==data){p->next=q->next;free(q);q=NULL;return ;}p=q;q=q->next;}printf("未找到与该值相等的节点，无法删除\n");return ;}

9.按位置查找

从第一个结点遍历到目标结点位置，输出其数据即可

data_t Linklist_Search_Pos(LinkList *h_node,int pos)
{if(Linklist_Is_Empty(h_node)==0){printf("表为空");return -1;}LinkList *p=h_node;if(pos<0 || pos>=Linklist_length(p)){printf("pos errror!\n");return -1;}while(pos--){p=p->next;}return p->next->data;}

10.按数据值查找

int Linklist_Search_Data(LinkList *h_node,data_t data)
{if(Linklist_Is_Empty(h_node)==0){printf("表为空\n");return -1;}LinkList *p=h_node->next;int pos=0;while(p!=NULL){if(p->data==data){return pos;}p=p->next;pos++;}printf("未找到与该值相等的节点\n");return -1;
}

11.按位置修改

思路和按位置查找一样，找到目标结点修改其数据值就行

void Linklist_Change_Pos(LinkList *h_node,int pos,data_t data)
{if(Linklist_Is_Empty(h_node)==0){printf("表为空");return ;}LinkList *p=h_node->next;if(pos<0 || pos>=Linklist_length(p)){printf("pos errror!\n");return ;}while(pos--){p=p->next;}p->data=data;
}

12.按值修改

void Linklist_Change_data(LinkList *h_node,data_t data,data_t newdata)
{if(Linklist_Is_Empty(h_node)==0){printf("表为空\n");return ;}LinkList *p=h_node->next;while(p!=NULL){if(p->data==data){p->data=newdata;}p=p->next;}printf("未找到与该值相等的节点\n");return ;
}

13.清空链表

清空链表指删除所有存储数据的结点，最后只剩下头结点

void Linklist_Empty(LinkList *h_node)
{LinkList *p=h_node->next;int pos=Linklist_length(h_node)-1;for(;pos>=0;pos--){Linklist_Delete_Pos(h_node,pos);}printf("清空完成\n");}

14.销毁链表

即删除头结点，这里要注意除了释放头结点的空间，还要将指向头结点的指针置为NULL，不然其他函数调用该指针仍然会指向头结点空间，但此时头结点已经释放，再访问就会造成非法访问，程序可能出错。

所以传进函数的指向头结点的指针应当是该指针的地址，这样才能在函数能修改该指针的指向。

该指针本身就是指针变量，再取它的地址作为实参，则传入函数内的形参为二级指针。

void Linklist_Delete(LinkList **h_node)//要想让对头节点地址进行操作，就得传其地址的地址
{if(Linklist_Is_Empty(*h_node)==0){free(*h_node);*h_node=NULL;printf("销毁成功\n");return;}printf("表不为空，无法销毁\n");}

15.循环头插十次

主要是方便调试，每次都一个一个输入数据麻烦

void Test_Insert(LinkList *h_node)
{int n=10;while(n--){Linklist_Insert_head(h_node,n);}}

主函数做了一个简易的功能选择界面，便于学习和调试

/*===============================================
*   文件名称：main.c
*   创 建 者：xm     
*   创建日期：2022年07月28日
*   描    述：
================================================*/
#include "linklist.h"
int main(int argc, char *argv[])
{//构建交互界面int mode;LinkList *h_node;int ret,pos,data;while(1){printf("--------------功能选择----------------\n");printf("1.创建头节点 2.判断是否为空表 3.求表长（数据节点个数）4.从表头插入数据\n5.打印表 6.按位置插入数据 7.按位置删除 8.按值删除 9.按位置查找\n10.按值查找 11.按位置修改 12.按值修改\n13.清空链表 14.销毁链表 15.自动头插10个元素\n");printf("请输入功能选项\n");scanf("%d",&mode);getchar();switch(mode){case 1:h_node=Creat_Linklist();break;case 2:ret=Linklist_Is_Empty(h_node);if(ret==0)puts("空表");else puts("非空表");break;case 3:ret= Linklist_length(h_node);printf("表长%d\n",ret);break;case 4:printf("输入数据\n");scanf("%d",&data);Linklist_Insert_head(h_node,data);break;case 5:Linklist_Show(h_node);break;case 6:printf("输入位置和数据\n");scanf("%d%d",&pos,&data);Linklist_Insert_Pos(h_node,pos,data);break;case 7:printf("输入位置\n");scanf("%d",&pos);Linklist_Delete_Pos(h_node,pos);break;case 8:printf("输入值\n");scanf("%d",&data);Linklist_Delete_Data(h_node,data);break;case 9:printf("输入位置\n");scanf("%d",&pos);Linklist_Search_Pos(h_node,pos);break;case 10:printf("输入值\n");scanf("%d",&data);Linklist_Search_Data(h_node,data);break;case 11:printf("输入位置和数据\n");scanf("%d%d",&pos,&data);Linklist_Change_Pos(h_node,pos,data);break;case 12:printf("输入要改数据和新数据\n");scanf("%d%d",&data,&ret);Linklist_Change_data(h_node,data,ret);break;case 13:Linklist_Empty(h_node);break;case 14:Linklist_Delete(&h_node);break;case 15:Test_Insert(h_node);break;default:puts("输入错误\n");}puts("");}return 0;
}

http://chatgpt.dhexx.cn/article/eb8g7t4P.shtml

相关文章

循环链表C语言实现

循环链表C语言实现

本文介绍循环链表中的单向循环链表&#xff0c;双向循环链表两种 第一种&#xff1a;单向循环链表&#xff0c;是在单向链表的基础上&#xff0c;尾结点不再指向NULL&#xff0c;而是指向头结点从而构成循环。如下图&#xff1a; 所以相比单向链表最大的特点就是可以从尾快速循…
阅读更多...
C语言基础入门：链表详解篇

C语言基础入门：链表详解篇

链表概述 链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量&#xff0c;以head表示&#xff0c;它存放一个地址。该地址指向一个元素。链表中每一个元素称为“结点”&#xff0c;每个结点都应包括两个…
阅读更多...
C语言——基础链表详解

C语言——基础链表详解

敢于向黑暗宣战的人&#xff0c;心里必须充满光明。 一、链表的构成 1.构成 链表是由一连串的结构&#xff08;称为结点&#xff09;组成的。 (1)结点的构成&#xff1a; 数据&#xff08;要储存的数据&#xff09;指针&#xff08;指向下一个结点的指针&#xff09; (2)关…
阅读更多...
C语言数据结构——链表

C语言数据结构——链表

目录 前言 一、什么是链表 1.1链表的结构和概念 1.2 链表的分类 二、无头单向非循环链表 2.1 创建结构体 2.2 动态申请一个节点 2.3 单链表打印 2.4 单链表尾插/尾删 2.4.1 单链表尾插 2.4.2 单链表尾删 2.5 单链表头插/头删 2.5.1 头插 2.5.2 头删 2.6 单链表查…
阅读更多...
C语言链表详解（通俗易懂）

C语言链表详解（通俗易懂）

文章目录 前言一、什么是线性表&#xff1f;二、顺序表&#xff1a;三、链表&#xff1a;四、顺序表和链表对比&#xff1a;总结 前言 线性表是实际中广泛应用的重要数据结构&#xff0c;本文用通俗易懂的方法讲解它。 一、什么是线性表&#xff1f; 首先&#xff0c;我们了解…
阅读更多...
C语言——链表

C语言——链表

C语言——链表 链表是一种基础的数据结构类型&#xff0c;一种能够动态维护数据的线性数据表。链表的数据以结点形式存储信息&#xff0c;并通过结点之间的指针实现结点之间的衔接。 为什么要用链表&#xff1f; 链表和数组类似&#xff0c;但是功能比数组强大得多&#xff0c…
阅读更多...
在？您的rsyslog日志管理手册到了，请查收

在？您的rsyslog日志管理手册到了，请查收

rsyslog日志管理和logrotate日志存储轮转 前言&#xff1a; 系统日志是记录服务器系统运行和软件运行状况的记录程序&#xff0c;如果系统和软件在运行中出错&#xff0c;我们就可以在日志中获取到问题发生时的记录&#xff0c;并以此寻求解决问题的方法。 一.rsyslog 系统日…
阅读更多...
日志审计与分析实验三（rsyslog服务器端和客户端配置）（Linux日志收集）

日志审计与分析实验三（rsyslog服务器端和客户端配置）（Linux日志收集）

文章目录 Linux日志收集一、实验目的&#xff1a;1、掌握rsyslog配置方法2、配置rsyslog服务收集其他Linux服务器日志: 二、实验步骤&#xff1a;1、前期配置2. rsyslog的三种传输协议1、udp传输方式2、tcp传输方式3、relp传输方式 Linux日志收集 一、实验目的&#xff1a; 1…
阅读更多...
Linux系统之rsyslog配置

Linux系统之rsyslog配置

目录 Rsyslog简介 Linux配置rsyslog 配置实验&#xff1a; 实验环境&#xff1a; 实验步骤&#xff1a; 实验准备&#xff1a; 针对UDP&#xff1a; 针对TCP&#xff1a; 针对RELP&#xff1a; 结果验证&#xff1a; 1、UDP&#xff1a; 2、TCP&#xff1a; 3、RE…
阅读更多...
rSyslog日志

rSyslog日志

日志服务管理 系统日志管理 系统日志介绍 日志的作用&#xff1a; 软件的运行记录软件运行排错运行分析 日志记录的内容包括&#xff1a; 历史事件&#xff1a;时间&#xff0c;地点&#xff0c;人物&#xff0c;事件日志级别&#xff1a;事件的关键性程度&#xff0c;Lo…
阅读更多...
Linux rsyslog详细介绍

Linux rsyslog详细介绍

转自&#xff1a;http://llei623.blog.163.com/blog/static/852075042010111482731766/ 作者&#xff1a;llei WEB服务器多的时候检查日志是一件痛苦的事情&#xff0c;用 perl 脚本登录到服务器上grep一些错误信息两次之后就觉得是纯体力活&#xff0c;想办法偷懒。 准备弄…
阅读更多...
Linux系统日志rsyslogd

Linux系统日志rsyslogd

Linux系统日志rsyslogd Linux系统日志 Linux上使用rsyslogd守护进程接收用户进程输出的日志和接收内核日志。 用户进程是通过syslogd函数生成系统日志。该函数将日志输出到一个UNIX本地域socket类型(AF_UNIX&#xff09;的文件/dev/log中&#xff0c;rsyslogd则监听该文件以…
阅读更多...
Linux之 rsyslog、日志轮转

Linux之 rsyslog、日志轮转

1.rsyslog 1.1rsyslog介绍 Rsyslog的全称是 rocket-fast system for log&#xff0c;它提供了高性能&#xff0c;高安全功能和模块化设计。rsyslog能够接受从各种各样的来源&#xff0c;将其输入&#xff0c;输出的结果到不同的目的地。rsyslog可以提供超过每秒一百万条消息给…
阅读更多...
rsyslog日志服务简介

rsyslog日志服务简介

1、简介 rsyslog是一个linux系统日志服务的工具&#xff0c;主要用来监控收集系统从开机运行之后所发生的所有日志&#xff0c;包括内核日志&#xff0c;服务日志&#xff0c;应用日志等等&#xff1b;记录的日志全部都写到/var/log下面&#xff0c;常用的有dmsg&#xff08;内…
阅读更多...
Linux 日志管理 Rsyslog Loganalyzer

Linux 日志管理 Rsyslog Loganalyzer

Syslog常被称为系统日志或系统记录&#xff0c;是一种用来在互联网协议&#xff08;TCP/IP&#xff09;的网上中传递记录档消息的标准。这个词汇常用来指涉实际的syslog 协议&#xff0c;或者那些提交syslog消息的应用程序或数据库。 syslog协议属于一种主从式协议&#xff1a…
阅读更多...
建立 rsyslog 日志服务器

建立 rsyslog 日志服务器

文章目录 1. rsyslog 介绍2. 实验目的3. 实验环境4. 配置服务端5. 配置客户端6. 在服务端验证效果 1. rsyslog 介绍 rsyslog 是一个快速处理收集系统日志的开源程序&#xff0c;提供了高性能、安全功能和模块化设计。rsyslog 是 syslog 的升级版&#xff0c;它将多种来源输入输…
阅读更多...
rsyslog配置

rsyslog配置

rsyslog配置文件详解&#xff1a; #### MODULES #### #定义日志的模块。 $ModLoad imuxsock #imuxsock为模块名&#xff0c;支持本地系统日志的模块。 $ModLoad imjournal #imjournal为模块名&#xff0c;支持对系统日志的访问。 #$ModLo…
阅读更多...
syslog 和 rsyslog

syslog 和 rsyslog

1. 介绍 rsyslog可以简单的理解为syslog的超集&#xff0c;在老版本的Linux系统中&#xff0c;Red Hat Enterprise Linux 3/4/5默认是使用的syslog作为系统的日志工具&#xff0c;从RHEL 6 开始系统默认使用了rsyslog。 其特性包括&#xff1a; 支持输出日志到各种数据库&…
阅读更多...
rsyslog日志服务详解

rsyslog日志服务详解

rsyslog日志服务详解 原文出处&#xff1a;http://blog.51cto.com/6638225/1862902 内容&#xff1a; 1、rsyslog日志服务简介 2、rsyslog的配置详解 3、实现日志服务器收集日志及last、lastb、dmseg命令的使用 4、实现日志存储在mysql中 一、rsyslog日志服务简介 ​ 日…
阅读更多...
【Linux】rsyslog日志服务（配置，测试、日志转储）

【Linux】rsyslog日志服务（配置，测试、日志转储）

一、rsyslog简介 Rsyslog的全称是 rocket-fast system for log ,可用于接受来自各种来源的输入&#xff0c;转换 它们&#xff0c;并将结果输出到不同的目的地。 它提供了高性能、强大的安全功能和模块化设计。虽然rsyslog最初是一个常规的系 统日志&#xff0c;但它已经发展…
阅读更多...
推荐文章

Copyright @ 2022~2023