【数据结构】链表（1）：单向链表和单向循环链表

链表

链表是一种经典的数据结构，它通过节点的指针将数据元素有序地链接在一起，在链表中，每个节点存储数据以及指向其他节点的指针（或引用）。链表具有动态性和灵活性的特点，适用于频繁插入、删除操作的场景。

定义

概念
  1. 将线性表 L = (a0，a1，...,an-1) 中各元素分布在存储器的不同存储块，称为结点。
    通过指针或地址建立起它们之间的联系，所得到的存储结构就是链表。
  2. 链表都有一个头结点(一般不保存数据，不做遍历)，是链表的入口。
  3. 链表呈现一对一关系，且有一个前驱结点和一个后继结点。
  4. 每一个结点都往堆申请了地址，由多个堆组成。
分类
  1. 单向链表（重点）
  2. 单向循环链表
  3. 双向链表
  4. 双向循环链表（重点）
  5. 内核链表（重点）

我们这里将链表分成三篇文章来写，分别是 1：单向链表（重点）和单向循环链表；2：双向链表和双向循环链表（重点）；3：内核链表（重点）。因为代码片如若过多可能会导致思维混乱，所以分开来写，将单向链表和循环链表放在一篇文章之中是因为二者的理念相同，只是首位相连接，代码逻辑接近，方便理解和对比。

链表的优缺点（想要具体了解链表和顺序表之间的区别详细，请查阅这篇文章：<链接：【数据结构】顺序表和链表优劣的对比分析>）

  • 优点：插入和删除非常方便。
  • 缺点：查找和替换比较麻烦。
  • 操作：对链表中数据的增删改查 —> 大原则：先连后断
单向链表（Singly Linked List）

定义：

  • 每个节点包含两部分：
    • 数据域（存储数据）。
    • 指针域（存储指向下一个节点的指针）。
  • 只有一个方向，从头节点开始依次访问每个节点。

特点：

  • 插入和删除操作高效，不需要移动其他节点。
  • 无法直接访问某个特定位置的元素，需要从头节点开始遍历。
#define datatype int
typedef struct link{datatype data;           //数据域  struct link *next;  //指向后继结点的指针域
}link_t;// 缺点：只能从头结点一直往后走// 头插：头结点(最前面的结点)后面插入
// 尾插：尾结点(最后面的结点)后面插入
1> 初始化link_init
link_t *link_init(void)  //造头结点
{//1>向堆申请link_t *p = (link_t *)malloc(sizeof(link_t));if(NULL == p){perror("malloc");return NULL;}//将指针赋值 ,为了安全指向NULLp->next = NULL;return p;
}
2> 创建结点create_node(static)
static link_t *create_node(datatype d)
{//1>向堆空间申请link_t *p = (link_t *)malloc(sizeof(link_t));if(NULL == p){perror("malloc");return NULL;}//2>赋值p->data = d;p->next = NULL;return p;
}

在这里插入图片描述

3> 插入函数insert_behind(static)
//将一个结点(a)插到另一个结点(b)的后面
static void insert_behind(link_t *a,link_t *b)
{//遵循先连后断 a->next = b->next;  //避免b指向的地址丢失b->next = a;
}
4> 头插函数insert_head
void insert_head(link_t *p,datatype d)
{//利用传进来的数据，调用创建结点函数link_t *node = create_node(d);//将创建出来的node结点插到头结点后面insert_behind(node,p);  
}

在这里插入图片描述

5> 遍历展示display
void display(link_t *head)
{//遍历整个链表while(head->next != NULL){//将head指针变量往右移head = head->next;printf("%d ",head->data); } printf("\n");
}
6> 尾插函数insert_tail
//每插入一个结点进来，将其插入到尾结点后面
void insert_tail(link_t *p,datatype data)
{link_t *node = create_node(data);if(NULL == node)return;//找到尾结点 while(p->next != NULL){p = p->next;}insert_behind(node,p);  
}

在这里插入图片描述

7> 删除函数link_del
void link_del(link_t *p,datatype d)
{link_t *node = NULL;//遍历while(p->next != NULL){//进行数据对比if(p->next->data == d) //从头结点后第一个有数据的结点开始判断{//先保存要删除结点的地址node = p->next;// 将p的next指向node的nextp->next = node->next;//为了安全，在释放前，令它的指针域指向NULLnode->next = NULL;//释放free(node);continue;}//往后继续遍历，找相同数据的结点p = p->next; }}

在这里插入图片描述

8> 修改函数link_replace
void link_replace(link_t *p,int old,int new)
{//遍历找到旧数据所在的地址while(p->next != NULL){if(p->next->data == old){p->next->data = new;continue; } p = p->next;}
}
完整代码（共三个文件：头文件、链表函数和主函数）

头文件： link.h

#ifndef __LINK_H__
#define __LINK_H__#include <stdio.h>
#include <stdlib.h>#define datatype inttypedef struct link{datatype data;           //数据域  struct link *next;  //指向后继结点的指针域
}link_t;extern link_t *link_init(void);
extern void insert_head(link_t *p,datatype d);
extern void display(link_t *head);
extern void insert_tail(link_t *p,datatype data);
extern void link_del(link_t *p,datatype d);
extern void link_replace(link_t *p,int old,int new);#endif

链表函数：link.c

#include "link.h"
//初始化
link_t *link_init(void)  //造头结点
{//1>向堆申请link_t *p = (link_t *)malloc(sizeof(link_t));if(NULL == p){perror("malloc");return NULL;}//将指针赋值 ,为了安全指向NULLp->next = NULL;return p;
}//创建结点
static link_t *create_node(datatype d)
{//1>向堆空间申请link_t *p = (link_t *)malloc(sizeof(link_t));if(NULL == p){perror("malloc");return NULL;}//2>赋值p->data = d;p->next = NULL;return p;
}//插入函数insert_behind
//将一个结点(a)插到另一个结点(b)的后面
static void insert_behind(link_t *a,link_t *b)
{//遵循先连后断 a->next = b->next;  //避免b指向的地址丢失b->next = a;
}//头插函数insert_head
void insert_head(link_t *p,datatype d)
{//利用传进来的数据，调用创建结点函数link_t *node = create_node(d);//将创建出来的node结点插到头结点后面insert_behind(node,p); 
}//遍历操作
void display(link_t *head)
{//遍历整个链表while(head->next != NULL){//将head指针变量往右移head = head->next;printf("%d ",head->data); } printf("\n");
}//每插入一个结点进来，将其插入到尾结点后面
void insert_tail(link_t *p,datatype data)
{link_t *node = create_node(data);if(NULL == node)return;//找到尾结点 while(p->next != NULL){p = p->next;}insert_behind(node,p);  
}//删除
void link_del(link_t *p,datatype d)
{link_t *node = NULL;//遍历while(p->next != NULL){//进行数据对比if(p->next->data == d) //从头结点后第一个有数据的结点开始判断{//先保存要删除结点的地址node = p->next;// 将p的next指向node的nextp->next = node->next;//为了安全，在释放前，令它的指针域指向NULLnode->next = NULL;//释放free(node);continue;}//往后继续遍历，找相同数据的结点p = p->next; }
}//替换
void link_replace(link_t *p,int old,int new)
{//遍历找到旧数据所在的地址while(p->next != NULL){if(p->next->data == old){p->next->data = new;continue; } p = p->next;}
}

主函数：main.c

#include "link.h"int main(void)
{link_t *head = link_init();if(NULL == head)return -1;printf("%p\n",head);int data,ret;while(1){printf("请开始头插\n");ret = scanf("%d",&data);if(ret == 0)break;insert_head(head,data); display(head);}getchar();while(1){printf("请开始尾插\n");ret = scanf("%d",&data);if(ret == 0)break;insert_tail(head,data); display(head);}getchar();while(1){printf("请开始删除\n");ret = scanf("%d",&data);if(ret == 0)break;link_del(head,data); display(head);}getchar();int old,new;while(1){printf("请开始替换\n");ret = scanf("%d%d",&old,&new);if(ret == 0)break;link_replace(head,old,new); display(head);}return 0;
}
单向循环链表（Singly Circular Linked List）

定义：

  • 单向链表的变体，最后一个节点的指针指向头节点，形成一个环。
  • 从链表的任何节点出发，都可以遍历整个链表。

特点：

  • 无需额外存储头尾信息，适合循环任务。
  • 需要注意防止死循环。
#define datatype int
typedef struct link{datatype data;           //数据域  struct link *next;      //指向后继结点的指针域
}link_t;// 头插：头结点(最前面的结点)后面插入
// 尾插：尾结点(最后面的结点)后面插入
1> 初始化link_init
link_t *link_init(void)  //造头结点
{//1>向堆申请link_t *p = (link_t *)malloc(sizeof(link_t));if(NULL == p){perror("malloc");return NULL;}//将指针赋值 ,为了安全指向NULL  //修改处p->next = p; //自己指向自己return p;
}
2> 创建结点create_node
static link_t *create_node(datatype d)
{//1>向堆空间申请link_t *p = (link_t *)malloc(sizeof(link_t));if(NULL == p){perror("malloc");return NULL;}//2>赋值  //修改处p->data = d;p->next = p;   //指向自己return p;
}
3> 插入函数insert_behind(static)
//将一个结点(a)插到另一个结点(b)的后面
static void insert_behind(link_t *a,link_t *b)
{//遵循先连后断 a->next = b->next;  //避免b指向的地址丢失b->next = a;
}
4> 头插函数insert_head
void insert_head(link_t *p,datatype d)
{//利用传进来的数据，调用创建结点函数link_t *node = create_node(d);//将创建出来的node结点插到头结点后面insert_behind(node,p); 
}
5> 遍历展示display
void display(link_t *head)
{//修改处link_t *p = head;//遍历整个链表  //修改处while(head->next != p)  //最后一个结点指向的是头结点{//将head指针变量往右移head = head->next;printf("%d ",head->data); } printf("\n");
}
6> 尾插函数insert_tail
//每插入一个结点进来，将其插入到尾结点后面
void insert_tail(link_t *p,datatype data)
{//修改处link_t *head = p; link_t *node = create_node(data);if(NULL == node)return;//找到尾结点  //修改处while(p->next != head)  //尾结点指向头结点{p = p->next;}insert_behind(node,p);  
}
7> 删除函数link_del
void link_del(link_t *p,datatype d)
{//修改处，保存头结点的地址link_t *head = p;link_t *node = NULL;//遍历   //修改处while(p->next != head){//进行数据对比if(p->next->data == d) //从头结点后第一个有数据的结点开始判断{//先保存要删除结点的地址node = p->next;// 将p的next指向node的nextp->next = node->next;//为了安全，在释放前，令它的指针域指向自己  //修改处node->next = node;//释放free(node);continue;}//往后继续遍历，找相同数据的结点p = p->next; }}
8> 修改函数link_replace
void link_replace(link_t *p,int old,int new)
{//修改处，保存头结点地址link_t *head = p;//遍历找到旧数据所在的地址  修改处while(p->next != head){if(p->next->data == old){p->next->data = new;continue; } p = p->next;}
}
完整代码（共三个文件：头文件、链表函数和主函数）

头文件： cyclelink.h

#ifndef __CYCLELINK_H__ 
#define __CYCLELINK_H__#include <stdio.h>
#include <stdlib.h>#define datatype int
typedef struct link{datatype data;           //数据域  struct link *next;  //指向后继结点的指针域
}link_t;extern link_t *link_init(void);
extern void insert_head(link_t *p,datatype d);
extern void display(link_t *head);
extern void insert_tail(link_t *p,datatype data);
extern void link_del(link_t *p,datatype d);
extern void link_replace(link_t *p,int old,int new);#endif

链表函数： cyclelink.c

#include "cyclelink.h"link_t *link_init(void)  //造头结点
{//1>向堆申请link_t *p = (link_t *)malloc(sizeof(link_t));if(NULL == p){perror("malloc");return NULL;}//将指针赋值 ,为了安全指向NULL  //修改处**p->next = p; //自己指向自己return p;
}static link_t *create_node(datatype d)
{//1>向堆空间申请link_t *p = (link_t *)malloc(sizeof(link_t));if(NULL == p){perror("malloc");return NULL;}//2>赋值  //修改处p->data = d;p->next = p;   //指向自己return p;
}//将一个结点(a)插到另一个结点(b)的后面
static void insert_behind(link_t *a,link_t *b)
{//遵循先连后断 a->next = b->next;  //避免b指向的地址丢失b->next = a;
}void insert_head(link_t *p,datatype d)
{//利用传进来的数据，调用创建结点函数link_t *node = create_node(d);//将创建出来的node结点插到头结点后面insert_behind(node,p); 
}void display(link_t *head)
{//修改处link_t *p = head;//遍历整个链表  //修改处while(head->next != p)  //最后一个结点指向的是头结点{//将head指针变量往右移head = head->next;printf("%d ",head->data); } printf("\n");
}//每插入一个结点进来，将其插入到尾结点后面
void insert_tail(link_t *p,datatype data)
{//修改处link_t *head = p;link_t *node = create_node(data);if(NULL == node)return;//找到尾结点  //修改处while(p->next != head)  //尾结点指向头结点{p = p->next;}insert_behind(node,p);  
}void link_del(link_t *p,datatype d)
{//修改处，保存头结点的地址link_t *head = p;link_t *node = NULL;//遍历   //修改处while(p->next != head){//进行数据对比if(p->next->data == d) //从头结点后第一个有数据的结点开始判断{//先保存要删除结点的地址node = p->next;// 将p的next指向node的nextp->next = node->next;//为了安全，在释放前，令它的指针域指向自己  //修改处node->next = node;//释放free(node);continue;}//往后继续遍历，找相同数据的结点p = p->next; }}void link_replace(link_t *p,int old,int new)
{//修改处，保存头结点地址link_t *head = p;//遍历找到旧数据所在的地址  修改处while(p->next != head){if(p->next->data == old){p->next->data = new;continue; } p = p->next;}
}

主函数：main.c

#include "cyclelink.h"int main(void)
{link_t *head = link_init();if(NULL == head)return -1;printf("%p\n",head);int data,ret;while(1){printf("请开始头插\n");ret = scanf("%d",&data);if(ret == 0)break;insert_head(head,data); display(head);}getchar();while(1){printf("请开始尾插\n");ret = scanf("%d",&data);if(ret == 0)break;insert_tail(head,data); display(head);}getchar();while(1){printf("请开始删除\n");ret = scanf("%d",&data);if(ret == 0)break;link_del(head,data); display(head);}getchar();int old,new;while(1){printf("请开始替换\n");ret = scanf("%d%d",&old,&new);if(ret == 0)break;link_replace(head,old,new); display(head);}return 0;
}

综上。希望该内容能对你有帮助，感谢！

以上。仅供学习与分享交流，请勿用于商业用途！转载需提前说明。

我是一个十分热爱技术的程序员，希望这篇文章能够对您有帮助，也希望认识更多热爱程序开发的小伙伴。
感谢！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/498177.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

开源电子书转有声书整合包ebook2audiobookV2.0.0

开源电子书转有声书整合包ebook2audiobookV2.0.0

ebook2audiobook&#xff1a;将电子书转换为有声书的开源项目 项目地址 GitHub - DrewThomasson/ebook2audiobook 整合包下载 更新至v2.0.0 https://pan.quark.cn/s/22956c5559d6 修改:页面已转为中文 项目简介 ebook2audiobook 是一个开源项目&#xff0c;它能够将电子…
阅读更多...
NSSCTFpwn刷题

NSSCTFpwn刷题

[SWPUCTF 2021 新生赛]nc签到 打开附件里面内容 import osart (( "####!!$$ ))#####!$$ ))(( ####!!$:(( ,####!!$: )).###!!$:##!$:#!!$!# #!$: #$#$ #!$: !!!$:\ "!$: /\ !: /"\ : /"-."-/\\\-."//.-"…
阅读更多...
java里classpath都包含哪些范围？

java里classpath都包含哪些范围？

什么是 classpath &#xff1f; classpath 等价于 main/java main/resources 第三方jar包的根目录 「引」SpringBoot中的classpath都包含啥
阅读更多...
Docker+Portainer 离线安装

Docker+Portainer 离线安装

1. Docker安装 步骤一&#xff1a;官网下载 docker 安装包 步骤二&#xff1a;解压安装包; tar -zxvf docker-24.0.6.tgz 步骤三&#xff1a;将解压之后的docker文件移到 /usr/bin目录下; cp docker/* /usr/bin/ 步骤四&#xff1a;将docker注册成系统服务; vim /etc/sy…
阅读更多...
#渗透测试#红蓝攻防#红队打点web服务突破口总结01

#渗透测试#红蓝攻防#红队打点web服务突破口总结01

免责声明 本教程仅为合法的教学目的而准备&#xff0c;严禁用于任何形式的违法犯罪活动及其他商业行为&#xff0c;在使用本教程前&#xff0c;您应确保该行为符合当地的法律法规&#xff0c;继续阅读即表示您需自行承担所有操作的后果&#xff0c;如有异议&#xff0c;请立即停…
阅读更多...
Java：190 基于SSM的药品管理系统

Java：190 基于SSM的药品管理系统

作者主页&#xff1a;舒克日记 简介&#xff1a;Java领域优质创作者、Java项目、学习资料、技术互助 文中获取源码 项目介绍 系统的用户分管理员和销售两个角色的权限子模块。 管理员统计药品销售量&#xff0c;可以导出药品出入库记录&#xff0c;管理药品以及报损信息。 销…
阅读更多...
Quo Vadis, Anomaly Detection? LLMs and VLMs in the Spotlight 论文阅读

Quo Vadis, Anomaly Detection? LLMs and VLMs in the Spotlight 论文阅读

文章信息&#xff1a; 原文链接&#xff1a;https://arxiv.org/abs/2412.18298 Abstract 视频异常检测&#xff08;VAD&#xff09;通过整合大语言模型&#xff08;LLMs&#xff09;和视觉语言模型&#xff08;VLMs&#xff09;取得了显著进展&#xff0c;解决了动态开放世界…
阅读更多...
VUE echarts 教程二 折线堆叠图

VUE echarts 教程二 折线堆叠图

VUE echarts 教程一 折线图 import * as echarts from echarts;var chartDom document.getElementById(main); var myChart echarts.init(chartDom); var option {title: {text: Stacked Line},tooltip: {trigger: axis},legend: {data: [Email, Union Ads, Video Ads, Dir…
阅读更多...
001__VMware软件和ubuntu系统安装(镜像)

001__VMware软件和ubuntu系统安装(镜像)

[ 基本难度系数 ]:★☆☆☆☆ 一、Vmware软件和Ubuntu系统说明&#xff1a; a、Vmware软件的说明&#xff1a; 官网&#xff1a; 历史版本&#xff1a; 如何下载&#xff1f; b、Ubuntu系统的说明&#xff1a; 4、linux系统的其他版本&#xff1a;红旗(redhat)、dibian、cent…
阅读更多...
Flutter中添加全局防护水印的实现

Flutter中添加全局防护水印的实现

随着版权意识的加强&#xff0c;越来越多的应用开始在应用内部增加各种各样的水印信息&#xff0c;防止核心信息泄露&#xff0c;便于朔源。 效果如下&#xff1a; 在Flutter中增加全局水印的方式&#xff0c;目前有两种实现。 方案一&#xff0c;在native层添加一个遮罩层&a…
阅读更多...
FOC控制原理-ADC采样时机

FOC控制原理-ADC采样时机

0、文章推荐 SimpleFOC移植STM32&#xff08;五&#xff09;—— 电流采样及其变换_极对数对电流采样的影响-CSDN博客 FOC 电流采样方案对比&#xff08;单电阻/双电阻/三电阻&#xff09; - 知乎 (zhihu.com) FOC中的三种电流采样方式&#xff0c;你真的会选择吗&#xff1f;…
阅读更多...
git clone 和 conda 换源

git clone 和 conda 换源

文章目录 git clone 通过 sshconda 创建虚拟环境通过 env.yml 文件conda 换源 git clone 通过 ssh git clone ssh://用户名IP地址:/仓库名字.gitconda 创建虚拟环境通过 env.yml 文件 conda env create -f environment.ymlconda 换源 Step 1 生成 .bashrc 文件在家目录下。…
阅读更多...
联邦协作训练大模型的一些研究进展

联邦协作训练大模型的一些研究进展

联邦协作训练大模型的一些研究进展： 架构与框架创新 凝聚联邦学习框架：中科院计算所等团队提出的凝聚联邦学习框架，借助端边云协同，通过桥接样本在线蒸馏协议，组织树状拓扑的算力网，实现不同层级节点间模型无关的协同训练，使各层级可依本地算力训练合适模型，云端最终集…
阅读更多...
深度学习blog- 数学基础（全是数学）

深度学习blog- 数学基础（全是数学）

矩阵‌&#xff1a;矩阵是一个二维数组&#xff0c;通常由行和列组成&#xff0c;每个元素可以通过行索引和列索引进行访问。 张量‌&#xff1a;张量是一个多维数组的抽象概念&#xff0c;可以具有任意数量的维度。除了标量&#xff08;0D张量&#xff09;、向量&#xff08;…
阅读更多...
ARM200~500部署

ARM200~500部署

前提&#xff1a;数据库已经安装好&#xff0c;并且正常运行 1.修改hostname,将里面的AR-A 改为hzx vi /etc/hostname 2.重启网络服务 sudo systemctl restart NetworkManager 3.修改community-admin.service 文件&#xff0c;更改小区名称和IP&#xff0c;并将文件上传到/…
阅读更多...
在实际开发中，如何权衡选择使用哪种数据结构和算法？

在实际开发中，如何权衡选择使用哪种数据结构和算法？

学习数据结构与算法有一段时间了&#xff0c;听音频、看视频、看专栏、看书、抄书&#xff0c;尝试了很多种方法&#xff0c;今天在 专栏 中看到一篇文章&#xff0c;觉得很不错&#xff0c;摘抄如下。 学习数据结构和算法&#xff0c;不要停留在学院派的思维中&#xff0c;只把…
阅读更多...
基于Hadoop的物品租赁系统的设计与实现-springboot+vue

基于Hadoop的物品租赁系统的设计与实现-springboot+vue

开发语言&#xff1a;Java框架&#xff1a;springbootJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;…
阅读更多...
深入浅出：从入门到精通大模型Prompt、SFT、RAG、Infer、Deploy、Agent

深入浅出：从入门到精通大模型Prompt、SFT、RAG、Infer、Deploy、Agent

阅读原文 渐入佳境 我们都知道&#xff0c;通过编写一个提示词&#xff08;prompt&#xff09;&#xff0c;我们可以引导大模型生成回答&#xff0c;从而开启愉快的人工智能对话&#xff0c;比如让模型介绍一下卡皮巴拉。上边简图描述了这个过程&#xff0c;我们拆成两部分 pr…
阅读更多...
【YOLOv3】源码（train.py）

【YOLOv3】源码（train.py）

概述 主要模块分析 参数解析与初始化 功能&#xff1a;解析命令行参数&#xff0c;设置训练配置项目经理制定详细的施工计划和资源分配日志记录与监控 功能&#xff1a;初始化日志记录器&#xff0c;配置监控系统项目经理使用监控和记录工具&#xff0c;实时跟踪施工进度和质量…
阅读更多...
vue封装弹窗元素拖动指令

vue封装弹窗元素拖动指令

项目开发过程中我们通常会遇到需要到一些弹窗鼠标可以随意拖动位置去放置&#xff0c;vue里面直接通过封装对应的指令即可&#xff0c;于是封装了一个出来&#xff0c;希望可以用到。 Vue.directive(draggable-dom, draggableDom); 组件节点添加对应指令就可以 v-draggable-…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023