数据结构 day4

目录

思维导图：

学习内容：

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/382217.html

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

相关文章

【手撕数据结构】拿捏单链表

【手撕数据结构】拿捏单链表

目录 单链表介绍链表的初始化打印链表增加节点尾插头插再给定位置之后插入在给定位置之前插入 删除节点尾删头删删除给定位置的节点删除给定位置之后的节点 查找节点 单链表介绍 单链表也叫做无头单向非循环链表&#xff0c;链表也是一种线性结构。他在逻辑结构上一定连续&…
阅读更多...
展望未来：利用【Python】结合【机器学习】强化数据处理能力

展望未来：利用【Python】结合【机器学习】强化数据处理能力

欢迎来到 破晓的历程的 博客 ⛺️不负时光&#xff0c;不负己✈️ 文章目录 一、引言二、数据清洗与预处理三、特征工程四、数据可视化五、模型训练与评估六、模型部署与优化七、总结 在数据驱动的时代&#xff0c;数据处理与机器学习技术的结合已成为推动业务增长和创新的关键…
阅读更多...
Redis 7.x 系列【25】集群部署

Redis 7.x 系列【25】集群部署

有道无术&#xff0c;术尚可求&#xff0c;有术无道&#xff0c;止于术。 本系列Redis 版本 7.2.5 源码地址&#xff1a;https://gitee.com/pearl-organization/study-redis-demo 文章目录 1. 概述2. 配置文件2.1 cluster-enabled2.2 cluster-config-file2.3 cluster-node-tim…
阅读更多...
HAL库源码移植与使用之RTC时钟

HAL库源码移植与使用之RTC时钟

实时时钟(Real Time Clock&#xff0c;RTC)&#xff0c;本质是一个计数器&#xff0c;计数频率常为秒&#xff0c;专门用来记录时间。 普通定时器无法掉电运行&#xff01;但RTC可由VBAT备用电源供电&#xff0c;断电不断时 这里讲F1系列的RTC 可以产生三个中断信号&#xff…
阅读更多...
TYPE-C接口PD取电快充协议芯片ECP5701：支持PD 2.0和PD 3.0(5V,9V,12V,15V,20V)

TYPE-C接口PD取电快充协议芯片ECP5701：支持PD 2.0和PD 3.0(5V,9V,12V,15V,20V)

随着智能设备的普及&#xff0c;快充技术成为了越来越多用户的刚需。而TYPE-C接口作为新一代的USB接口&#xff0c;具有正反插、传输速度快、充电体验好等优点&#xff0c;已经成为了快充技术的主要接口形式。而TYPE-C接口的PD&#xff08;Power Delivery&#xff09;取电快充协…
阅读更多...
poi库简单使用（java如何实现动态替换模板Word内容）

poi库简单使用（java如何实现动态替换模板Word内容）

目录 Blue留言&#xff1a; Blue的推荐&#xff1a; 什么是poi库&#xff1f; 实现动态替换 第一步&#xff1a;依赖 第二步&#xff1a;实现word模板中替换文字 模板word&#xff1a; 通过以下代码&#xff1a;&#xff08;自己建一个类&#xff0c;随意取名&#xf…
阅读更多...
[排序]hoare快速排序

[排序]hoare快速排序

今天我们继续来讲排序部分&#xff0c;顾名思义&#xff0c;快速排序是一种特别高效的排序方法&#xff0c;在C语言中qsort函数&#xff0c;底层便是用快排所实现的&#xff0c;快排适用于各个项目中&#xff0c;特别的实用&#xff0c;下面我们就由浅入深的全面刨析快速排序。…
阅读更多...
JVM监控及诊断工具-命令行篇--jcmd命令介绍

JVM监控及诊断工具-命令行篇--jcmd命令介绍

JVM监控及诊断工具-命令行篇5-jcmd&#xff1a;多功能命令行 一 基本情况二 基本语法jcmd -ljcmd pid helpjcmd pid 具体命令 一 基本情况 在JDK 1.7以后&#xff0c;新增了一个命令行工具jcmd。它是一个多功能的工具&#xff0c;可以用来实现前面除了jstat之外所有命令的功能…
阅读更多...
简历网站分享

简历网站分享

作者本人自己编写了一个简历站点&#xff0c;分享给大家。在线链接 &#xff0c; github仓库
阅读更多...
从PyTorch官方的一篇教程说开去（3.3 - 贪心法）

从PyTorch官方的一篇教程说开去（3.3 - 贪心法）

您的进步和反馈是我最大的动力&#xff0c;小伙伴来个三连呗&#xff01;共勉。 贪心法&#xff0c;可能是大家在处理陌生问题时候&#xff0c;最容易想到的办法了吧&#xff1f; 还记得小时候&#xff0c;国足请了位洋教练发表了一句到现在还被当成段子的话&#xff1a;“如…
阅读更多...
【深入C++】map和set的使用

【深入C++】map和set的使用

文章目录 C 中的容器分类1. 顺序容器2. 关联容器3. 无序容器4. 容器适配器5. 字符串容器6. 特殊容器 set1.构造函数2.迭代器3.容量相关的成员函数4.修改器类的成员函数5.容器相关操作的成员函数 multiset1.equal_range map1.初始化相关的函数2.迭代器3.容量相关的成员函数4.访问…
阅读更多...
58. 不理解竞态问题

58. 不理解竞态问题

内容 竞态问题可能程序员面临的最困难和最隐蔽的错误之一。作为 Go 开发者&#xff0c;必须理解数据竞争和竞态条件等关键方面&#xff0c;包括它们可能产生的影响以及如何避免。接下来将首先讨论数据竞争与竞态条件的区别&#xff0c;然后研究 Go 内存模型及其重要性。 数据…
阅读更多...
SpringBoot常用功能实现

SpringBoot常用功能实现

1. 配置文件多环境配置 1.1 创建不同环境配置文件 文件名前缀和后缀为标准固定格式&#xff0c;不可以改变。 1.2 pom中加入文件配置 可以使用<activation>标签设置默认环境。 <profiles><profile><id>dev</id><activation><active…
阅读更多...
Typora 1.5.8 版本安装下载教程 (轻量级 Markdown 编辑器)，图文步骤详解，免费领取（软件可激活使用）

Typora 1.5.8 版本安装下载教程 (轻量级 Markdown 编辑器)，图文步骤详解，免费领取（软件可激活使用）

文章目录 软件介绍软件下载安装步骤激活步骤 软件介绍 Typora是一款基于Markdown语法的轻量级文本编辑器&#xff0c;它的主要目标是为用户提供一个简洁、高效的写作环境。以下是Typora的一些主要特点和功能&#xff1a; 实时预览&#xff1a;Typora支持实时预览功能&#xff0…
阅读更多...
在 CentOS 7 上安装 Docker 并安装和部署 .NET Core 3.1

在 CentOS 7 上安装 Docker 并安装和部署 .NET Core 3.1

1. 安装 Docker 步骤 1.1&#xff1a;更新包索引并安装依赖包 先安装yum的扩展&#xff0c;yum-utils提供了一些额外的工具&#xff0c;这些工具可以执行比基本yum命令更复杂的任务 sudo yum install -y yum-utils sudo yum update -y #更新系统上已安装的所有软件包到最新…
阅读更多...
【spring boot】初学者项目快速练手

【spring boot】初学者项目快速练手

项目视频&#xff1a;一小时带你从0到1实现一个SpringBoot项目开发_哔哩哔哩_bilibili 注解视频&#xff1a;10、Java高级技术&#xff1a;注解&#xff1a;认识注解_哔哩哔哩_bilibili 一、基础知识 1.注解Annotation &#xff08;1&#xff09;定义 注解是Java代码里的特…
阅读更多...
Golang | Leetcode Golang题解之第257题二叉树的所有路径

Golang | Leetcode Golang题解之第257题二叉树的所有路径

题目&#xff1a; 题解&#xff1a; func binaryTreePaths(root *TreeNode) []string {paths : []string{}if root nil {return paths}nodeQueue : []*TreeNode{}pathQueue : []string{}nodeQueue append(nodeQueue, root)pathQueue append(pathQueue, strconv.Itoa(root.V…
阅读更多...
干货-并发编程提高——线程切换基础（一）

干货-并发编程提高——线程切换基础（一）

现在的时分&#xff08;time-sharing&#xff09;多任务&#xff08;multi-task&#xff09;操作系统架构通常都是用所谓的“时间分片&#xff08;time quantum or time slice&#xff09;”方式进行抢占式&#xff08;preemptive&#xff09;轮转调度&#xff08;round-robin式…
阅读更多...
HydraRPC: RPC in the CXL Era——论文阅读

HydraRPC: RPC in the CXL Era——论文阅读

ATC 2024 Paper CXL论文阅读笔记整理 问题 远程过程调用&#xff08;RPC&#xff09;是分布式系统中的一项基本技术&#xff0c;它允许函数在远程服务器上通过本地调用执行来促进网络通信&#xff0c;隐藏底层通信过程的复杂性简化了客户端/服务器交互[15]。RPC已成为数据中心…
阅读更多...
【iOS】内存五大分区

【iOS】内存五大分区

目录 堆&#xff08;Heap&#xff09;是什么五大分区栈区堆区全局/静态区常量区&#xff08;即.rodata&#xff09;代码区&#xff08;.text&#xff09; 函数栈堆和栈的区别和联系图解 OC语言是C语言的超集&#xff0c;所以先了解C语言的内存模型的内存管理会有很大帮助。C语言…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023