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

day19 链表

news 2025/7/23 15:56:04

定义

链式存储的线性表

头文件相关定义 

typedef int datatype;//定义数据域类型
typedef struct Node
{union{int len;  //头结点数据域datatype data; //普通节点数据域};struct Node *next;   //节点指针域
}Node,*Node_ptr;

链表的函数 

注意事项 

1.创建节点时，需要初始化节点的数据域和指针域

2.创建节点后需要判断地址来查看是否创建成功

3.无论是声明何种函数都需要判断头节点是否为空

    如果长度发生改变需要添加长度逻辑

        //判断逻辑

        //功能逻辑

        （长度逻辑）

        //返回逻辑

4.任意位置的增删改查都需要判断插入位置是否合理

5.释放节点后，需要将指针置空，防止野指针

6.遍历下一个节点的操作为p=p->next;

7.理解链表反转

8.头节点不允许增删改查

创建单向链表

Node_ptr linklist_create();

函数功能：从堆区空间申请一个头结点并初始化，并检查链表是否创建成功

参数：void

返回值：成功返回头结点地址，失败返回NULL

 主要代码

Node_ptr l=(Node_ptr)malloc(sizeof(Node));
if(l==NULL)
{printf("创建链表失败\n");return NULL;		
}
//头结点初始化
l->len=0;//初始化长度为0
l->next=NULL;//初始化指针为空，防止野指针

链表判空操作

int link_empty(Node_ptr );

函数功能：判断链表是否为空

参数：链表头结点地址

返回值：为空返回1，否则返回0

 主要代码

//通过判断头结点的后继节点指针是否为空
return l->next==NULL;

创建节点

Node_ptr Node_apply(datatype );

函数功能：从堆区申请一个新节点并判断是否申请成功，并初始化数据域

参数：节点数据域的值

返回值：成功返回节点地址，失败返回NULL

 主要代码

//堆区申请空间
Node_ptr p=(Node_ptr)malloc(sizeof(Node));
if(p==NULL)
{printf("节点空间申请失败\n");return NULL;
}
printf("节点申请成功\n");
p->data=e; //初始化数据域
p->next=NULL; //初始化指针为空
return p; //封装好的节点地址

单向链表头插

int link_insert_head(Node_ptr ,datatype );

函数功能：通过创建节点函数申请节点，并在链表头部插入新节点

参数：链表头结点地址、待插入数据

返回值：成功返回0，失败返回-1

//创建节点
//pa指针接收节点的地址
Node_ptr pa=Node_apply(e);
if(pa==NULL)
{printf("插入失败\n");return -1;
}
//头插逻辑
pa->next=L->next;//先继承头节点的指向
L->next=pa;  //再将头节点指针指向插入的节点
//长度自增
L->len++;

单向链表按位置查找

Node_ptr link_find_post(Node_ptr ,int );

函数功能：先判断位置是否合理，根据位置查找节点地址

参数：链表头结点地址、位置索引（从0开始）

返回值：成功返回节点地址，失败返回NULL

主要代码 

//判断逻辑
if(L==NULL||post<0||post>L->len)
{printf("查找失败\n");return NULL;
}
//查找逻辑
Node_ptr q=L; //定义一个遍历指针
for(int i=0;i<post;i++) //先移动再自加，所有不需要等于post
{q=q->next;//指向下一个节点
}
//返回节点
return q;

链表遍历

void show(Node_ptr );

函数功能：先判断是否为空，再打印链表中所有节点的数据

参数：链表头结点地址

返回值：void

 主要代码

//判断逻辑
if(link_empty(L))
{printf("遍历失败\n");
}
Node_ptr q=L->next; //遍历指针指向第一个节点
while(q)  //如果遍历为空，结束遍历
{printf("%-4d",q->data);//遍历数据q=q->next;//指向下一个节点
}

链表任意位置插入

int link_insert_post(Node_ptr ,int ,datatype);

函数功能：先判断位置是否合理，再在指定位置插入新节点

参数：链表头结点地址、位置索引、待插入数据

返回值：成功返回0，失败返回-1 

//创建节点
Node_ptr p=Node_apply(e);
if(p==NULL)
{printf("插入失败2\n");return -1;
}
//调用函数找到post-1的地址，用q接收
Node_ptr q=link_find_post(L,post-1);
//利用头插
p->next=q->next; //插入节点继承post-1节点的指针指向
q->next=p;    //psost-1节点指向插入节点
//长度自增
L->len++;

链表头删

int link_delete_head(Node_ptr );

函数功能：判断是否为空，删除链表首节点（非头结点）

参数：链表头结点地址

返回值：成功返回0，失败返回-1

//p记录节点地址
Node_ptr p=L->next;
//删除逻辑，头节点指向下一个节点
L->next=p->next;
//释放节点
free(p);
p=NULL;//防止野指针
//长度自减
L->len--;

任意位置删除

int link_delete_post(Node_ptr ,int );

函数功能：先判断位置是否合理，删除指定位置的节点

参数：链表头结点地址、位置索引

返回值：成功返回0，失败返回-1

//遍历到post前驱节点,p接收post-1地址
Node_ptr p=link_find_post(L,post-1);
//删除逻辑
//本质是p->next=(p->next)->next 
Node_ptr q=p->next; 
p->next=q->next;  //q被孤立
//释放节点，置空
free(q);
q=NULL;
//长度自减
L->len--;

按值查找位置

int link_find_value(Node_ptr ,datatype );

函数功能：查找数据值首次出现的位置

参数：链表头结点地址、待查找数据

返回值：成功返回位置索引（从1开始），失败返回-1

//查找逻辑
Node_ptr p=L->next; //p指向第一个节点
for(int i=1;i<=L->len;i++) //遍历查找
{	if(p->data==e)return i;p=p->next; //不匹配p往后移动
}
return -1;

按位置修改

int link_updata_post(Node_ptr ,int ,datatype);

函数功能：修改链表中指定位置节点的数据

参数：链表头结点地址、位置索引、新数据

返回值：成功返回0，失败返回-1

//查找逻辑,用p接收post地址
Node_ptr p=link_find_post(L,post);
//修改逻辑
p->data=e;

按值修改

int link_updata_value(Node_ptr,datatype,datatype);

函数功能：修改链表中值的节点数据

参数：链表头结点地址、旧数据、新数据

返回值：成功返回0，失败返回-1

int link_updata_value(Node_ptr L,datatype old,datatype new)
{//查找逻辑int post=link_find_value(L,old);//判断逻辑if(post==-1){return -1;}//修改逻辑link_updata_post(L,post,new);return 0;
}

单向链表反转

int link_reverse(Node_ptr );

函数功能：反转链表（头结点除外）

参数：链表头结点地址

返回值：成功返回0，失败返回-1

Node_ptr H=L->next;   //H记录第一个节点地址
L->next=NULL;      //清空头节点
while(H!=NULL)   //遍历
{Node_ptr q=H; //记录H的指向，搬运作用H=H->next;//头插形式插入q->next=L->next;L->next=q;
}

链表释放

void link_free(Node_ptr);

函数功能：释放链表所有节点（包括头结点）

参数：链表头结点地址

返回值：void

//释放逻辑
while(!link_empty(L))
{//调用头参函数link_delete_head(L);
}
//释放头节点，置空
free(L);
L=NULL;

完整代码

linklist.h 

#ifndef LINKLIST_H
#define LINKLIST_H
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef int datatype;//定义数据域类型
typedef struct Node
{union{int len;  //头结点数据域datatype data; //普通节点数据域};struct Node *next;   //节点指针域
}Node,*Node_ptr;
//创建单向链表
Node_ptr linklist_create();
//链表判空操作
int link_empty(Node_ptr );
//创建节点
Node_ptr Node_apply(datatype ); 
//单向链表头插
int link_insert_head(Node_ptr ,datatype );
//单向链表按位置查找返回地址
Node_ptr link_find_post(Node_ptr ,int );
//链表的遍历
void show(Node_ptr );
//链表任意位置插入
int link_insert_post(Node_ptr ,int ,datatype);
//链表头删
int link_delete_head(Node_ptr );
//任意位置删除
int link_delete_post(Node_ptr ,int );
//按值查找返回位置
int link_find_value(Node_ptr ,datatype );
//按位置修改
int link_updata_post(Node_ptr ,int ,datatype);
//按值修改
int link_updata_value(Node_ptr,datatype,datatype);
//单向链表反转
int link_reverse(Node_ptr );
//
//链表的释放 
void link_free(Node_ptr);#endif

linklist.c

#include"linklist.h"
//此处头结点的地址都用l表示
//其他节点用p/pa表示//创建单向链表
Node_ptr linklist_create()
{   //申请一个头结点的空间Node_ptr l=(Node_ptr)malloc(sizeof(Node));if(l==NULL){printf("创建链表失败\n");return NULL;		}//头结点初始化l->len=0;//初始化长度为0l->next=NULL;//初始化指针为空，防止野指针printf("创建链表成功\n");return l;
}
//链表判空操作
//链表为空返回1，非空返回0
int link_empty(Node_ptr l)
{   //判断链表传入地址是否为空if(l==NULL){printf("链表不合法\n");return -1;}//通过判断头结点的后继节点指针是否为空return l->next==NULL;
}
//创建节点
//成功返回节点地址，失败返回空
Node_ptr Node_apply(datatype e)
{//堆区申请空间Node_ptr p=(Node_ptr)malloc(sizeof(Node));if(p==NULL){printf("节点空间申请失败\n");return NULL;}printf("节点申请成功\n");p->data=e; //初始化数据域p->next=NULL; //初始化指针为空return p; //封装好的节点地址
}
//单向链表头插
//成功返回0失败返回-1
//插入的数据是逆序，先进的在后面
int link_insert_head(Node_ptr L ,datatype e )
{//判断逻辑if(L==NULL){printf("插入失败\n");return -1;}//创建节点//pa指针接收节点的地址Node_ptr pa=Node_apply(e);if(pa==NULL){printf("插入失败\n");return -1;}//头插逻辑pa->next=L->next;//先继承头节点的指向L->next=pa;  //再将头节点指针指向插入的节点//长度自增L->len++;printf("头插成功\n");return 0;
}
//单向链表查找
//成功返回地址，失败返回空
Node_ptr link_find_post(Node_ptr L,int post)
{//判断逻辑if(L==NULL||post<0||post>L->len){printf("查找失败\n");return NULL;}//查找逻辑Node_ptr q=L; //定义一个遍历指针for(int i=0;i<post;i++) //先移动再自加，所有不需要等于post{q=q->next;//指向下一个节点}//返回节点return q;
}
//链表的遍历
void show(Node_ptr L)
{//判断逻辑if(link_empty(L)){printf("遍历失败\n");}Node_ptr q=L->next; //遍历指针指向第一个节点while(q)  //如果遍历为空，结束遍历{printf("%-4d",q->data);//遍历数据q=q->next;//指向下一个节点}putchar(10);
}
//链表任意位置插入
//成功插入返回0，失败返回-1
int link_insert_post(Node_ptr L ,int post,datatype e)
{//判断逻辑if(L==NULL||post<1||post>L->len+1) //判断地址和插入逻辑的合理性{printf("插入失败1\n");return -1;}//创建节点Node_ptr p=Node_apply(e);if(p==NULL){printf("插入失败2\n");return -1;}//调用函数找到post-1的地址，用q接收Node_ptr q=link_find_post(L,post-1);//插入逻辑p->next=q->next; //插入节点继承post-1节点的指针指向q->next=p;    //psost-1节点指向插入节点//长度自增L->len++;printf("插入数据成功\n");return 0;
}
//链表头删
//成功返回0，失败返回-1
int link_delete_head(Node_ptr L)
{//判断逻辑if(link_empty(L)){printf("删除失败\n");return -1;}//p记录节点地址Node_ptr p=L->next;//删除逻辑，头节点指向下一个节点L->next=p->next;//释放节点free(p);p=NULL;//防止野指针//长度自减L->len--;printf("链表头删成功\n");return 0;
}
//任意位置删除
//成功返回0，失败返回-1
int link_delete_post(Node_ptr L,int post)
{//判断逻辑if(L==NULL||post<1||post>L->len){printf("按位置删除失败\n");return -1;}//遍历到post前驱节点,p接收post-1地址Node_ptr p=link_find_post(L,post-1);//删除逻辑//本质是p->next=(p->next)->next Node_ptr q=p->next; p->next=q->next;  //q被孤立//释放节点，置空free(q);q=NULL;//长度自减L->len--;printf("删除成功\n");return 0;
}
//按值查找返回位置
int link_find_value(Node_ptr L ,datatype e)
{//判断逻辑if(L==NULL||link_empty(L)){printf("查找失败\n");return -1;}//查找逻辑Node_ptr p=L->next; //p指向第一个节点for(int i=1;i<=L->len;i++) //遍历查找{	if(p->data==e)return i;p=p->next; //不匹配p往后移动}printf("未找到，查询失败\n");return -1;
}
//按位置修改
int link_updata_post(Node_ptr L,int post,datatype e)
{//判断逻辑if(L==NULL||link_empty(L)||post<0||post>L->len+1){printf("修改失败\n");return -1;}//查找逻辑,用p接收post地址Node_ptr p=link_find_post(L,post);//修改逻辑p->data=e;return 0;
}
//按值修改
int link_updata_value(Node_ptr L,datatype old,datatype new)
{//查找逻辑int post=link_find_value(L,old);//判断逻辑if(post==-1){return -1;}//修改逻辑link_updata_post(L,post,new);return 0;
}
//单向链表反转
int link_reverse(Node_ptr L)
{if(L==NULL||L->len<=1){printf("翻转失败\n");return -1;}Node_ptr H=L->next;   //H记录第一个节点地址L->next=NULL;      //清空头节点while(H!=NULL)   //遍历{Node_ptr q=H; //记录H的指向，搬运作用H=H->next;//头插形式插入q->next=L->next;L->next=q;}return 0;
}
//链表的释放
void link_free(Node_ptr L)
{//判断逻辑if (L=NULL){printf("释放失败\n");return;}//释放逻辑while(!link_empty(L)){//调用头参函数link_delete_head(L);}//释放头节点，置空free(L);L=NULL;printf("释放成功\n");
}

main.c

#include"linklist.h"
int main(int argc, const char *argv[])
{	//定义指针x接收申请空间的首地址	Node_ptr x=linklist_create();	if(x==NULL){printf("创建失败\n");}printf("创建链表成功\n");printf("%d\n",link_empty(x));//Node_apply(e);//头插link_insert_head(x,1);link_insert_head(x,2);link_insert_head(x,3);link_insert_head(x,4);printf("%d\n",x->len);//链表查找//指针q接收地址Node_ptr q=link_find_post(x,2);printf("%d\n",q->data);printf("11111\n");show(x);link_insert_post(x,2,99);show(x);link_delete_head(x);show(x);link_delete_post(x,3);show(x);printf("%d\n",link_find_value(x,3));link_updata_post(x,3,88);show(x);link_updata_value(x,3,77);show(x);link_reverse(x);show(x);link_free(x);return 0;
}

http://www.lryc.cn/news/596682.html

相关文章：

  • 程序是如何生成的-以c语言为例
  • 信息学奥赛一本通 1553：【例 2】暗的连锁
  • 前端_CSS复习
  • 【React 入门系列】React 组件通讯与生命周期详解
  • 高可用架构模式——数据集群和数据分区
  • 单细胞转录组学+空间转录组的整合及思路
  • OneCode3.0 UI组件注解详解手册
  • 【vscode】vscode中python虚拟环境的创建
  • 回调地狱及解决方法
  • error C++17 or later compatible compiler is required to use ATen.
  • 【coze扣子】第1篇：coze快速入门
  • 威胁情报：Solana 开源机器人盗币分析
  • 以Java程序员角度理解MCP
  • 学习游戏制作记录（战斗系统简述以及击中效果）7.22
  • [c++11]std::function/bind
  • 基于SpringBoot+Vue的班级管理系统（Echarts图形化分析）
  • 101.对称二叉树
  • ubuntu 20.04 安装 cmake 3.26
  • VS Code 美化插件
  • 3ds Max 云端渲染插件 - 完整 Python 解决方案
  • Mysql-场景篇-2-线上高频访问的Mysql表，如何在线修改表结构影响最小？-1--Mysql8.0版本后的INSTANT DDL方案（推荐）
  • 基于mysql云数据库创建和美化表格，对比分析Power BI和Quick BI的功能优劣
  • 基于eBPF的Kubernetes网络故障自愈系统设计与实现
  • AI一周事件（2025年7月15日-7月21日）
  • 【Spring AI 0基础教程】1、基础篇 环境搭建 - 智能天气预报助手
  • 数据资产——解读数据资产全过程管理手册2025【附全文阅读】
  • 【时时三省】(C语言基础)指向函数的指针
  • 发票识别在费控系统应用剖析
  • Dify-13: 文本生成API端点
  • uniapp打开导航软件并定位到目标位置的实现