单向链表

目录

思维导图：

学习内容：

1. 链表的引入

1.1 顺序表的优缺点

1.1.1 优点

1.1.2 不足

1.1.3 缺点

1.2 链表的概念

1.2.1 链式存储的线性表叫做链表

1.2.2 链表的基础概念

1.3 链表的分类

2. 单向链表

2.1 节点结构体类型

2.2 创建链表 

2.3 申请节点封装数据 

2.4 链表判空 

2.5 头插 

2.6 链表遍历 

2.7 通过位置查找节点 

2.8 任意位置插入元素

2.9 头删 

 2.10 任意位置删除函数

2.11 按值查找返回位置 

2.12 按位置修改 

2.13 按值进行修改函数 

2.14 链表的反转 

2.15 链表的释放

课外作业：

思维导图：

学习内容：

1. 链表的引入

1.1 顺序表的优缺点

1.1.1 优点

        能够直接通过下标进行定位元素，访问效率高，对元素进行查找和修改比较快

1.1.2 不足

        插入和删除元素需要移动大量的元素，效率较低

1.1.3 缺点

        存储数据元素有上限，当达到MAX后，就不能再添加元素了

1.2 链表的概念

1.2.1 链式存储的线性表叫做链表

        链式存储：表示数据元素的存储地址不一定连续

        线性表：数据元素之间存在一对一的关系

1.2.2 链表的基础概念

        1、节点：节点是链表的基本单位，由数据域和指针域组成

        2、数据域：存放数据元素的部分

        3、指针域：存放下一个节点地址的部分

        4、前驱节点：当前节点的上一个节点

        5、后继节点：当前节点的下一个节点

        6、头节点：虚设的一个节点，数据域不存放数据元素，可以存放链表的长度

        7、头指针：指向第一个节点的指针称为头指针

        8、第一个节点：实际存储数据元素的链表上的第一个节点

        注意：头节点的指针域其实就是头指针，也可以单独定义一个指针，指向第一个节点

1.3 链表的分类

        1、单向链表：只能从头节点或第一个节点出发，单向访问其后继节点的链表称为单向链表

        2、双向链表：从头部出发，既可以访问前驱节点，也可以访问后继节点

        3、循环链表：首尾相接的链表称为循环链表

2. 单向链表

2.1 节点结构体类型

        1> 头节点和普通节点数据域可以合到一起，使用一格共用体表示

        2> 指针域都是指向普通节点的地址

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

2.2 创建链表 

        1> 在堆区申请一格头节点的空间，就创建了一个链表

        2> 需要对头节点的数据域初始化链表长度，指针域初始化NULL

//创建链表
NodePtr list_create()
{//只需要在堆区申请一个头结点NodePtr L = (NodePtr)malloc(sizeof(Node));if(NULL == L){printf("创建失败\n");return NULL;}//程序执行至此，说明头结点创建结束L->len = 0;    //表示链表长度为0L->next = NULL;      ///防止野指针printf("链表创建成功\n");return L;
}

2.3 申请节点封装数据 

        1> 需要将要封装的数据当做函数的参数进行传递

        2> 同样在堆区申请节点，就传入的数据放入数据域

//申请结点封装数据函数
NodePtr apply_node(datatype e)
{//在堆区申请一个结点的大小NodePtr p = (NodePtr)malloc(sizeof(Node));if(NULL == p){printf("结点申请失败\n");return NULL;}//给结点内容赋值p->data = e;          //数据域赋值p->next = NULL;        //指针域return p;
}

2.4 链表判空 

        只需要判断头节点的指针域中是否为空即可

//链表判空
int list_empty(NodePtr L)
{return L->next == NULL;
}

2.5 头插 

        1> 表示将新插入的节点放入第一个节点中

        2> 插入数据时，不能先将前面节点与后面节点先断开。一定要从新节点出发，指向后面的节点，然后将前驱节点指向字节

//头插
int list_insert_head(NodePtr L, datatype e)
{//判断逻辑if(NULL==L){printf("链表不合法\n");return -1;}//申请结点封装数据NodePtr p = apply_node(e);if(NULL==p){return -1;}//头插逻辑p->next = L->next;L->next = p;//表的变化L->len ++;printf("头插成功\n");return 0;
}

2.6 链表遍历 

        需要使用一个遍历指针，将每一个节点进行遍历一遍，如果该指针指向的节点不为空，就访问其数据域，向后偏移

//链表遍历函数
int list_show(NodePtr L)
{//判断逻辑if(NULL==L || list_empty(L)){printf("遍历失败\n");return -1;}printf("链表中的元素分别是：");//遍历逻辑NodePtr q = L->next;   //定义遍历指针从第一个结点出发while(q != NULL){//输出数据域printf("%d\t", q->data);q = q->next;    //指针向后偏移一个}
}

2.7 通过位置查找节点 

        1> 参数：链表、位置

        2> 返回值：对应节点的地址

//通过位置查找结点
NodePtr list_search_pos(NodePtr L, int pos)
{//判断逻辑if(NULL==L || list_empty(L) || pos<0 || pos>L->len){printf("查找失败\n");return NULL;}//查找逻辑//定义遍历指针从头结点出发NodePtr q = L;for(int i=0; i<pos; i++){q = q->next;}return q;     //将找到的结点地址返回
}

2.8 任意位置插入元素

        1> 参数：链表、位置、要插入的元素

        2> 返回值：int

        3> 注意：必须找到要插入位置的节点的前驱节点，将前驱节点当作头节点，进行头插操作

//任意位置插入
int list_insert_pos(NodePtr L, int pos, datatype e)
{//判断逻辑if(NULL==L || pos<1 || pos>L->len+1){printf("插入失败\n");return -1;}//申请结点封装数据NodePtr p = apply_node(e);if(NULL==p){return -1;}//调用函数查找前驱结点NodePtr q = list_search_pos(L, pos-1);//插入逻辑p->next = q->next;q->next = p;//表的变化L->len++;printf("插入成功\n");return 0;
}

2.9 头删 

        1> 参数：链表

        2> 返回值：int

        3> 注意：需要将要删除的节点先标记一下，头节点的指针，指向第二个节点后，将标记的节点释放

//链表头删
int list_delete_head(NodePtr L)
{//判断逻辑if(NULL==L || list_empty(L)){printf("删除失败\n");return -1;}//删除三部曲NodePtr p = L->next;    //标记L->next = p->next;  //L->next->next  孤立free(p);            //释放p = NULL;//表长变化L->len--;printf("头删成功\n");return 0;
}

 2.10 任意位置删除函数

        1> 参数：链表、要删除的位置

        2> 返回值:int

        3> 注意：需要找到要删除的节点的前驱节点，将其当作头节点，进行头删逻辑

//链表任意位置删除
int list_delete_pos(NodePtr L, int pos)
{//判断逻辑if(NULL==L || list_empty(L) || pos<1 || pos>L->len){printf("删除失败\n");return -1;}//找到前驱结点NodePtr q = list_search_pos(L, pos-1);//删除逻辑NodePtr p = q->next;           //标记q->next = q->next->next;   //p->next 孤立free(p);                   //释放p = NULL;//表的变化L->len--;printf("删除成功\n");return 0;
}

2.11 按值查找返回位置 

        1> 参数：链表、要查找的值

        2> 返回值：元素在链表中的位置

//链表按值查找返回位置
int list_search_value(NodePtr L, datatype e)
{//判断逻辑if(NULL==L || list_empty(L)){printf("查找失败\n");return -1;}//查找逻辑//定义遍历指针从第一个结点出发NodePtr q = L->next;for(int index=1; index<=L->len; index++){//判断当前结点的值是否为要找的数据if(q->data == e){return index;}q = q->next;     //继续向后遍历}//程序执行至此，表示没找到printf("没找到\n");return -1;
}

2.12 按位置修改 

        1> 参数：链表、要修改的元素位置、要被更新的值

        2> 返回值：int

        3> 注意：先通过位置，找到对应的元素，更改该元素中的内容即可

//链表按位置进行修改
int list_update_pos(NodePtr L, int pos, datatype e)
{//判断逻辑if(NULL==L || list_empty(L) || pos<1 || pos>L->len){printf("修改失败\n");return -1;}//按位置查找逻辑NodePtr p = list_search_pos(L, pos);//修改逻辑p->data = e;printf("修改成功\n");return 0;
}

2.13 按值进行修改函数 

        1> 参数：链表、旧值、新值

        2> 返回值：int

        3> 思路：先通过旧值找到位置，通过位置进行修改

//按值进行修改
int list_update_value(NodePtr L, datatype old_e, datatype new_e)
{//判断逻辑if(NULL==L || list_empty(L)){printf("修改失败\n");return -1;}//按值查找位置int res = list_search_value(L, old_e);if(res == -1){printf("没有要修改的值\n");return -1;}//按位置修改list_update_pos(L, res, new_e);printf("修改成功\n");return 0;
}

2.14 链表的反转 

        1> 参数：链表

        2> 返回值：int

        3> 注意：在该操作中，没有节点被删除，也没有节点被释放

//将链表进行翻转
void list_reverse(NodePtr L)
{//判断逻辑if(NULL==L || L->len<=1){printf("翻转失败\n");return ;}//翻转逻辑NodePtr H = L->next;   //将链表元素进行托付L->next = NULL;        //自己白手起家NodePtr p = NULL;         //结点的搬运工while(H != NULL){p = H;      //搬运第一个结点H = H->next;     //头指针后移//将p以头插的方式放入L中p->next = L->next;L->next = p;}printf("翻转成功\n");}

2.15 链表的释放

         1> 参数：链表

        2> 返回值：无

        3> 注意：需要先将所有的节点内存全部释放后，再将头节点释放

//释放链表
void list_destroy(NodePtr L)
{//判断逻辑if(NULL == L){return;}//将所有结点进行释放while(!list_empty(L)){//头删list_delete_head(L);}//释放头结点free(L);L = NULL;printf("释放成功\n");
}

课外作业：

1.链表的排序

解析：

//排序
void list_sort(NodePtr L)
{if(NULL == L || list_empty(L)){printf("排序失败\n");return ;}for (int i = 0; i < L->len; i++){NodePtr q=L->next;NodePtr q1 = q->next;while(q1 != NULL){if(q->data > q1->data){datatype temp = q->data;q->data = q1->data;q1->data  =temp;}q=q->next;            //指针向后偏移一个q1= q1->next;}}printf("排序成功\n");list_print(L);
}

2.链表的反转（递归实现）

解析：

3. 链表去重

解析：

void list_rep(NodePtr L)
{if(NULL == L || L->len<=1){printf("去重失败\n");return ;}NodePtr q = L;while(q->next != NULL){if(q->data == q->next->data){NodePtr temp = q->next;q->next = temp->next;free(temp);}else{q=q->next;}}printf("去重成功\n");list_print(L);
}

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

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

相关文章

EXCEL 排名(RANK,COUNTIFS)

EXCEL 排名(RANK,COUNTIFS)

1.单列排序 需求描述&#xff1a;如有下面表格&#xff0c;需要按笔试成绩整体排名。 解决步骤&#xff1a; 我们使用RANK函数即可实现单列整体排名。 Number 选择第一列。 Ref 选择这一整列&#xff08;CtrlShift向下箭头、再按F4&#xff09;。 "确定"即可计算…
阅读更多...
图像分类算法概述：深度学习方法

图像分类算法概述：深度学习方法

图像分类算法概述&#xff1a;深度学习方法 图像分类是计算机视觉中的一个基本任务&#xff0c;近年来随着深度学习的发展&#xff0c;图像分类算法取得了巨大的进步。本文将概述主要的深度学习图像分类算法。 #mermaid-svg-fkTtkPLl9ahuVT6w {font-family:"trebuchet ms…
阅读更多...
BGP选路之Preferred value

BGP选路之Preferred value

原理概述 当一台BGP路由器中存在多条去往同一目标网络的BGP路由时&#xff0c;BGP协议会对这些BGP路由的属性进行比较&#xff0c;以确定去往该目标网络的最优BGP路由&#xff0c;然后将该最优BGP路由与去往同一目标网络的其他协议路由进行比较&#xff0c;从而决定是否将该最优…
阅读更多...
元组(tuple)

元组(tuple)

目录 一、基本介绍 1、元组(tuple)可以存放多个不同数据类型&#xff0c;元组是不可变序列 2、元组也是一种数据类型 二、元组的定义 1、元组的定义 2、代码说明 三、元组的使用 1、元组使用语法 2、举例说明 3、代码演示&#xff0c;访问/获取第三个数据/元素 四、…
阅读更多...
SpringBoot集成Kaptcha验证码

SpringBoot集成Kaptcha验证码

Hi &#x1f44b;, Im shy 有人见尘埃&#xff0c;有人见星辰 1. 什么是Kaptcha验证码? Kaptcha是一个强大的开源Java验证码生成库,由Google开发。它能够生成高度可配置的图片验证码,主要用于防止自动化程序滥用web应用,提高应用的安全性。 2. Kaptcha的主要特性 Kaptch…
阅读更多...
AMEsim液压阀伯德图绘制方法

AMEsim液压阀伯德图绘制方法

之前也在液压圈论坛里面发过类似的贴子&#xff0c;具体可以看这个网址&#x1f6aa;&#x1f449;&#xff1a;如何得出说明书里面的伯德图曲线&#xff1f;&#xff0c;回复的人还是比较少&#xff0c;这个方法重要信息是参考百度文库这篇文章&#x1f6aa;&#x1f449;&…
阅读更多...
相机的内参与外参

相机的内参与外参

目录 一、相机的内参二、相机的外参 一、相机的内参 如下图所示是相机的针孔模型示意图&#xff1a; 光心O所处平面是相机坐标系(O&#xff0c;P)&#xff0c;像素平面所在坐标系为像素坐标系(O’&#xff0c;P’)。 焦距f&#xff1a;O到O’的距离 相机的内参表示的是相机坐标…
阅读更多...
文本编辑三巨头（grep）

文本编辑三巨头（grep）

目录 正则表达式 元字符 grep 案例 我在编写脚本的时候发现&#xff0c;三个文本编辑的命令&#xff08;grep、sed、awk&#xff0c;被称为文本编辑三剑客&#xff0c;我习惯叫它三巨头&#xff09;用的还挺多的&#xff0c;说实话我一开始学的时候也有些懵&#xff0c;主要…
阅读更多...
【实现100个unity特效之8】使用ShaderGraph实现2d贴图中指定部分局部发光效果

【实现100个unity特效之8】使用ShaderGraph实现2d贴图中指定部分局部发光效果

最终效果 寒冰法师 火焰法师 文章目录 最终效果寒冰法师火焰法师 素材一、功能分析实现方法基本思路Unity的Bloom后处理为什么关键部位白色&#xff1f;最终结果 二、 新建URP项目三、合并图片四、使用PS制作黑白图片方法一 手动涂鸦方法二 魔棒工具1. 拖入图片进PS&#xff0…
阅读更多...
环信+亚马逊云科技服务：助力出海AI社交应用扬帆起航

环信+亚马逊云科技服务：助力出海AI社交应用扬帆起航

随着大模型技术的飞速发展&#xff0c;AI智能体的社交体验得到了显著提升&#xff0c;AI社交类应用在全球范围内持续火热。尤其是年轻一代对新技术和新体验的热情&#xff0c;使得AI社交产品在海外市场迅速崛起。作为领先的即时通讯解决方案提供商&#xff0c;环信与亚马逊云科…
阅读更多...
# Redis 入门到精通（九）-- 主从复制（2）

# Redis 入门到精通（九）-- 主从复制（2）

Redis 入门到精通&#xff08;九&#xff09;-- 主从复制&#xff08;2&#xff09; 一、redis 主从复制–数据同步阶段注意事项 1、数据同步阶段 master 说明 1&#xff09;如果 master 数据量巨大&#xff0c;数据同步阶段应避开流量高峰期&#xff0c;避免造成 master 阻…
阅读更多...
掌握Rust：函数、闭包与迭代器的综合运用

掌握Rust：函数、闭包与迭代器的综合运用

掌握Rust&#xff1a;函数、闭包与迭代器的综合运用 引言&#xff1a;解锁 Rust 高效编程的钥匙函数定义与模式匹配&#xff1a;构建逻辑的基石高阶函数与闭包&#xff1a;代码复用的艺术迭代器与 for 循环&#xff1a;高效数据处理的引擎综合应用案例&#xff1a;构建一个简易…
阅读更多...
JavaSE--基础语法--继承和多态(第三期)

JavaSE--基础语法--继承和多态(第三期)

一.继承 1.1我们为什么需要继承? 首先&#xff0c;Java中使用类对现实世界中实体来进行描述&#xff0c;类经过实例化之后的产物对象&#xff0c;则可以用来表示现实中的实体&#xff0c;但是 现实世界错综复杂&#xff0c;事物之间可能会存在一些关联&#xff0c;那在设计程…
阅读更多...
Redis的应用场景及类型

Redis的应用场景及类型

目录 一、Redis的应用场景 1、限流 2、分布式锁 3、点赞 4、消息队列 二、Redis类型的命令及用法 1、String类型 2、Hash类型 3、List类型 4、Set类型 5、Zset类型 6、Redis工具类 Redis使用缓存的目的就是提升读写性能 实际业务场景下&#xff0c;我们就可以把 Mys…
阅读更多...
Mysql数据库第四次作业

Mysql数据库第四次作业

mysql> create table student(sno int primary key auto_increment,sname varchar(30) not null unique,Ssex varchar(2) check (Ssex男 or Ssex女) not null,Sage int not null,Sdept varchar(10) default计算机 not null); mysql> create table Course(Con int primar…
阅读更多...
pytest的安装和介绍和 Exit Code 含义

pytest的安装和介绍和 Exit Code 含义

pytest 准备工作&#xff08;在cmd里&#xff09;&#xff1a; 1安装 pip install -U pytest2验证安装 pytest --version # 会展示当前已安装版本3其他的 显示可用的内置函数参数 pytest --fixtures通过命令行查看帮助信息及配置文件选项 pytest --help一、pytets框架中的…
阅读更多...
Air780EP-AT开发-HTTP应用指南

Air780EP-AT开发-HTTP应用指南

简介 关联文档和使用工具&#xff1a; AT固件获取AT指令手册 概述 4G模块支持HTTP和HTTPS协议&#xff0c; HTTP应用的基本流程如下&#xff1a; 1、激活PDP&#xff08;参考&#xff1a;http://oldask.openluat.com/article/937&#xff09;2、初始化HTTP服务3、设置HTTP会话…
阅读更多...
从0到1使用Docker部署java项目详解

从0到1使用Docker部署java项目详解

Docker部署Java项目相比传统部署方式&#xff0c;在环境一致性、配置管理、可扩展性和安全性等方面具有显著优势。然而&#xff0c;它也带来了学习成本、资源消耗和复杂度增加等挑战。 云服务器 白嫖阿里云服务 通过免费试用方式获取自己的阿里云服务器。当然&#xff0c;如…
阅读更多...
ElasticSearch(四)— 数据检索与查询

ElasticSearch(四)— 数据检索与查询

一、基本查询语法 所有的 REST 搜索请求使用_search 接口&#xff0c;既可以是 GET 请求&#xff0c;也可以是 POST请求&#xff0c;也可以通过在搜索 URL 中指定索引来限制范围。 _search 接口有两种请求方法&#xff0c;一种是基于 URI 的请求方式&#xff0c;另一种是基于…
阅读更多...
S71200 - 笔记

S71200 - 笔记

1 S71200 0 ProfiNet - 2 PLC编程 01.如何零基础快速上手S7-1200_哔哩哔哩_bilibili 西门子S7-1200PLC编程设计学习视频&#xff0c;从入门开始讲解_哔哩哔哩_bilibili
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023