数据结构——单向链表

目录

前言

一、单向链表

二、单向链表基本操作

1、链表单创建

2.节点插入

(1)尾部插入

 (2)任意位置插入

3、单向链表节点删除

4、链表打印

5、释放链表

6、链表逆序

 ......

三、链表测试

总结



前言

        链表(Linked List)是一种常见的数据结构,它属于线性表的一种链式存储结构,其逻辑上相邻的元素在物理存储位置并不相邻。它由一系列节点(Node)组成,每个节点包含数据部分和指向列表中下一个节点(或者上一个节点)的指针(链接)。链表中的节点通过指针相互连接,从而形成一个序列。链表可以分为几种不同的类型,但最常见的是单向链表和双向链表。


一、单向链表

        在单向链表中,每个节点包含两个部分:

        1、数据部分:存储节点的数据,数据类型可以是整型、浮点型、字符型或自定义的数据结构(如结构体)等。

        2、指针部分(也称为链接或“next”指针):指向链表中下一个节点的指针。链表的最后一个节点的指针部分通常设置为NULL,表示链表的结束。

         链表就如同一群人手拉着手站在一起,最开始的一个人要拉着一根杆,防止链子丢失了。每个人都带着属于自己的数据(如姓名、性别、年龄等),但他们都手拉着手,随意找到上一个人,便可以自然而然的知到下一个人,他们的手就是next指针。

         链表特性:

         1、动态数据结构:链表的节点可以动态地分配和释放,因此链表是一种动态数据结构。链表的大小可以在运行时动态地增加或减少,不需要像数组那样在创建时指定大小。

        2、非连续存储:链表中的节点可以存储在内存中的任何位置,不像数组那样要求所有元素连续存储。但每个节点都需要额外的内存来存储指针,这增加了链表的内存开销。

        3、灵活:通过指针,可以很容易地在链表中的任何位置插入或删除节点,而不需要移动其他节点,通常只需要修改节点的指针,因此效率较高,尤其是在链表中间或末尾进行这些操作时。。

        4、访问方式:单链表不支持快速随机访问,因为从链表的头节点到任意节点的访问都需要从头开始遍历。

        5、常见运用:在实际应用中,链表常用于实现栈、队列等数据结构,或者在需要频繁插入和删除操作而不太需要随机访问的场景中。

二、单向链表基本操作

1、单向链表创建

        首先声明链表节点。

typedef int data_t;typedef struct node {data_t data;struct node * next;
}listnode, * linklist;

         然后进行链表创建,一般只需要创建一个头节点即可,因为在刚创建时,没有数据要放在链表上,即没有新节点插入。

#include <stdio.h>
#include <stdlib.h>linklist list_create() //创建链表,即头节点
{linklist H;H = (linklist)malloc(sizeof(listnode));//给节点动态分配内存if (H == NULL)//判断是否申请内存成功 {printf("malloc failed\n");return H;}	//如果成功了,则进行赋初值H->data = 0; //一般存放节点个数H->next = NULL;//刚开始时没有节点插入链表,所以该头节点即是尾节点return H; //返回头节点指针
}int main(void)
{linklist H;	H = list_create();//外部调用函数进行创建if (H == NULL)return -1;return 0;
}

2.节点插入

(1)尾部插入

        将链表创建完成后,就可以向链表插入数据了,其中最简单的插入方式为,尾部插入。基本步骤为:

        1、创建新的节点,用以存放将插入的数据;

        2、找到当前链表的尾部,即next指针指向NULL的节点;

        3、将新创建的节点放在尾部,原来尾部节点的next指针指向自己,自己的next指针指向NULL即可。

int list_tailinsert(linklist H, data_t data) //传入待插入的链表地址和待插入的数据
{linklist p;//定义临时指针变量linklist q;if (H == NULL) //检验传入的链表是否有效{printf("H is NULL\n");return -1;}//创建新节点并检查有效性,存放待插入数据if ((p = (linklist)malloc(sizeof(listnode))) == NULL){printf("malloc failed\n");return -1;}p->data = data;p->next = NULL;q = H;while (q->next != NULL) //遍历链表找尾部{q = q->next;}q->next = p;//插入链表,尾部的next指针指向新节点H->data++;//插入数据后,数据个数加一 return 0;
}

 (2)任意位置插入

        在这里,我们用-1表示链表的头节点位置,存放数据的第一个节点用0表示,后面的位置依次即可,可以自定义。其插入基本步骤:

        1、对插入位置的有效性进行判断;

        2、查找待插入位置的前一个节点,如下查找某一位置的节点的操作;

//寻找链表上某一位置的节点的地址,返回该节点地址
linklist list_getpos(linklist H, int pos) //传入链表指针和待寻找节点的位置
{linklist p;int i;if (H == NULL) {printf("H is NULL\n");return NULL;}if (pos == -1) return H;//如果是-1,则返回链表头节点,因为用0表示第一个节点的位置p = H;i = -1;while (i < pos) //遍历寻找{p = p->next;if (p == NULL) //没有到达指定位置,链表已经结尾了,位置错误,返回NULL{printf("pos is invalid\n");return NULL;}i++;}return p;
}

        3、创建新节点,存放待插入数据;

        4、重新连接节点,即插入新节点,先将上一个节点的next指针内容赋给新节点的next指针,再将新节点的地址赋给上一个节点的next指针(切勿将顺序搞反)。

//任意位置插入,传入链表地址,待插入数据,待插入位置
int list_insert(linklist H, data_t data, int pos) 
{linklist p;linklist new;if (H == NULL) {printf("H is NULL\n");return -1;}p = list_getpos(H, pos-1);//找到待插入位置的上一个节点Pif (p == NULL) return -1;//没有找到则返回if ((new = (linklist)malloc(sizeof(listnode))) == NULL)//创建待插入的新节点{printf("malloc failed\n");return -1;}new->data = data;//存放数据new->next = NULL;
//插入链表,注意先后次序,以免节点丢失new->next = p->next;p->next = new;H->data++;//插入数据后,数据个数加一 return 0;
}

3、单向链表节点删除

        删除节点也可以像插入一样,可进行尾部删除和任意位置删除的操作,尾部删除可对照插入进行,不再赘述。下面进行任意位置节点的删除操作,其基本步骤为:

        1、查找待删除节点的上一个节点;

        2、将待删除的next指针赋给上一个节点的next指针,这样便可以从链表上去掉待删除节点;

        3、然后将删除的节点释放掉内存即可。

int list_delete(linklist H, int pos) 
{linklist p;linklist deletenode;if (H == NULL) return -1;p = list_getpos(H, pos-1);//寻找待删除节点的上一个节点if (p == NULL) return -1;//没有找到则返回if (p->next == NULL) //如果要删除的节点不存在,则返回{printf("delete pos is invalid\n");return -1;}deletenode = p->next;//找到要删除的节点//将待删除的next指针赋给上一个节点的next指针p->next = deletenode->next;//也可以用p->next = p->next->next;//printf("free:%d\n", deletenode->data);//释放删除节点的内存free(deletenode);deletenode = NULL;H->data--;//删除节点后,数据个数减一 return 0;
}

4、链表打印

        我们需要查看链表时,就需要遍历打印出来,如下操作。

int list_show(linklist H) //链表打印显示
{linklist p;if (H == NULL){printf("H is NULL\n");return -1;}p = H;while (p->next != NULL)//遍历打印{printf("%d ", p->next->data);p = p->next;}puts("");return 0;
}

5、释放链表

        当链表使用完成之后,需要释放其占用的内存。

int list_free(linklist H) 
{linklist p;if (H == NULL) return 0;//没有头节点(即链表),则不用释放p = H;//printf("free:");//头节点依次往后移动,然后将前面的删掉while (H != NULL) {p = H;//printf("%d ", p->data);free(p);H = H->next;}puts("");return 0;
}

6、链表逆序

        链表反序主要有以下步骤:

        1、对当前链表的节点数进行判断(头节点不算),如果没有节点或者只有一个节点,则不需要逆序;

        2、将待逆序的链表的第二个及以后的部分分离,这样,待逆序链表只有头节点和第一个节点了,然后依次取出分离部分的头节点在待逆序链表的头部进行插入,便实现了逆序操作。

int list_reverse(linklist H) 
{linklist p;linklist q;if (H == NULL) {printf("H is NULL\n");return -1;}//如果是空链表,或者是只有一个节点,则没有逆序的必要,返回if (H->next == NULL || H->next->next == NULL) return 0;//开始时将链表分为两段p = H->next->next;//p第二个节点及之后的节点H->next->next = NULL;//H只有第一个节点while (p != NULL) {q = p;p = p->next;//p继续往后移q->next = H->next;//在H链表的头部进行插入H->next = q;}return 0;
}

 ......

三、链表测试

        通过以上链表的基本操作,已基本可以使用链表了,如下简单测试:

int main(void)
{linklist H;int value;H = list_create();//创建链表if (H == NULL)return -1;printf("input:");while (1) {scanf("%d", &value);//输入要插入的值if (value  < 0)//输入负数退出尾部插入的操作break;list_tailinsert(H, value);//在链表尾部进行插入printf("input:");}list_show(H);//打印显示当前链表内容list_insert(H, 100, 1);//在1位置处插入数据为100的节点,位置从0开始算list_show(H);list_delete(H, 2);//删除位置2所在的节点list_show(H);printf("H=%p\n", H);//打印链表头节点地址H = list_free(H);//释放链表printf("H=%p\n", H);return 0;
}

总结

        链表作为一种灵活且高效的数据结构,在计算机科学的各个领域都有着广泛的应用,更多操作需要自己灵活展现。

有误之处望指正!!

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

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

相关文章

万字长文讲透数字化转型

温馨提醒&#xff1a;1.6w字详细拆解&#xff0c;内容篇幅较长&#xff0c;建议先收藏~ 数字化浪潮正在席卷全球&#xff0c;践行数字化转型和提升企业的运营水平与竞争力&#xff0c;已经成为各国企业角力全球市场的重要议题。为此&#xff0c;很多国家政府都推出了鼓励和推动…

(el-Time-Picker)操作(不使用 ts):Element-plus 中 TimePicker 组件的使用及输出想要时间格式需求的解决过程

Ⅰ、Element-plus 提供的 TimePicker 时间选择器组件与想要目标情况的对比&#xff1a; 1、Element-plus 提供 TimePicker 组件情况&#xff1a; 其一、Element-ui 自提供的 TimePicker 代码情况为(示例的代码)&#xff1a; // Element-plus 提供的组件代码: <template>…

Go - 10. * 值类型和指针类型的差异

目录 一.引言 二.接收者类型 三.代码示例 1.指针接收者 2.值接收者 3.运行结果对比 4.代码修改 5.刨根问底 四.总结 一.引言 go 语言中 func (c *Title) 和 func (c Title) 两个方法的传参差一个 * 号&#xff0c;二者的区别是一个是指针类型&#xff0c;一个是值类型…

MATLAB中的imshow函数的使用方法及实例应用

一、imshow函数 imshow是MATLAB工具软件中用于显示图像的函数&#xff0c;它支持多种图像类型&#xff0c;包括灰度图像、真彩色图像、索引图像等。以下是对imshow常用用法: imshow(I) 在图窗中显示灰度图像 I。imshow 使用图像数据类型的默认显示范围&#xff0c;并优化图窗、…

React(三):PDF文件在线预览(简易版)

效果 依赖下载 https://mozilla.github.io/pdf.js/getting_started/ 引入依赖 源码 注意&#xff1a;pdf文件的预览地址需要配置代理后才能显示出来 import ./index.scss;function PreviewPDF() {const PDF_VIEWER_URL new URL(./libs/pdfjs-4.5.136-dist/web/viewer.html, im…

软硬链接和动静态库

为什么一定要提供路径呢&#xff1f; 因为要根据路径找到文件 一切与路径相关的问题都是方便用户去访问文件 软硬链接 给我康康 软链接是这样的&#xff1a; ln -s file_target1.txt file_soft.link 软链接有独特的innode 这是硬链接&#xff1a; ln file_target2.txt …

【Redis】缓存三大问题与缓存一致性问题

缓存三大问题 缓存穿透 缓存穿透是指用户查询的数据在缓存和数据库中都不存在&#xff0c;导致每次请求都会直接落到数据库上&#xff0c;增加数据库负载。 解决方案 1&#xff09;参数校验 一些不合法的参数请求直接抛出异常信息返回给客户端。比如查询的数据库 id 不能小于…

python3.10安装geopandans实战笔记

1.geopandans安装所需软件库版本 python3.10 GDAL-3.4.3-cp310-cp310-win_amd64.whl【手动下载】 Fiona-1.8.21-cp310-cp310-win_amd64.whl【手动下载】 shapely-2.0.2-cp310-cp310-win_amd64.whl【手动下载】 pyproj 手动下载地址&#xff1a;https://download.csdn.net/down…

Unity入门5——材质

创建材质 点击Assets → Create → Material&#xff0c;得到一个默认材质球的副本。 使用材质 直接把材质球拖拽到物体上&#xff0c;或设置mesh renderer组件下的Materials 数组中第一个元素

html+css网页设计公司网站模版3个页面 无js 静态页面

htmlcss网页设计公司网站模版3个页面 无js 静态页面 网页作品代码简单&#xff0c;可使用任意HTML编辑软件&#xff08;如&#xff1a;Dreamweaver、HBuilder、Vscode 、Sublime 、Webstorm、Text 、Notepad 等任意html编辑软件进行运行及修改编辑等操作&#xff09;。 获取源…

iOS弱引用

背景&#xff1a;在面试过程中被问到如果两个对象已经发生循环引用了&#xff0c;该如何将他们剪断&#xff0c;在运行态的时候。 由于这个场景比较抽象&#xff0c;我理解面试官是希望我通过运行时的方法和方式来解决循环引用。 解决方案一: 重写setter用关联对象来实现wea…

数据库规范化设计 5大基本原则

规范化设计原则是数据库设计的基本原则&#xff0c;有助于减少数据冗余&#xff0c;提高数据一致性和完整性&#xff0c;简化数据管理&#xff0c;增强数据安全性&#xff0c;对整个开发项目至关重要。而缺乏规范化设计会导致数据冗余&#xff0c;增加存储成本&#xff0c;引发…

java 如何查看jar版本冲突,如何查看哪个模块依赖冲突,idea查看jar包冲突

1. idea 下载插件&#xff1a; 2. 如上图所示&#xff0c;下载Maven Helper, 注意是maven helper 不是别的 3.重启idea 4.点击pom文件&#xff0c;然后点击如图所示&#xff1a; 5. 如此即可查到&#xff0c;某个jar包 都有哪个模块依赖&#xff0c;使用的什么版本&#xff0…

【JavaEE】定时器

目录 前言 什么是定时器 如何使用java中的定时器 实现计时器 实现MyTimeTask类 Time类中存储任务的数据结构 实现Timer中的schedule方法 实现MyTimer中的构造方法 处理构造方法中出现的线程安全问题 完整代码 考虑在限时等待wait中能否用sleep替换 能否用PriorityBlo…

RISC-V竞赛|第二届 RISC-V 软件移植及优化锦标赛报名正式开始!

目录 赛事背景 赛道方向 适配夺旗赛 优化竞速赛 比赛赛题&#xff08;总奖金池8万元&#xff01;&#xff09; &#x1f525;竞速赛 - OceanBase 移植与优化 比赛赛程&#xff08;暂定&#xff09; 赛事说明 「赛事背景」 为了推动 RISC-V 软件生态更快地发展&#xff0…

收银系统源码-连锁店版本

千呼新零售2.0系统是零售行业连锁店一体化收银系统&#xff0c;包括线下收银线上商城连锁店管理ERP管理商品管理供应商管理会员营销等功能为一体&#xff0c;线上线下数据全部打通。 私有化独立部署/全开源源码&#xff0c;系统开发语言&#xff1a; 核心开发语言: PHP、HTML…

【vue3】【elementPlus】【黑暗模式】

从创建vue3项目到引入elementPlus组件并设置黑暗模式 1.创建vue3项目&#xff1a; npm init vuelatest1.1 根据需求定制项目插件&#xff1a; 2.引入elementPlus组件&#xff1a; npm install element-plus --save2.1 如图注册全局elementPlus组件&#xff1a; ------------…

SPSS、Python员工满意度问卷调查激励保健理论研究:决策树、随机森林和AdaBoost|附代码数据

全文链接&#xff1a;https://tecdat.cn/?p37293 原文出处&#xff1a;拓端数据部落公众号 在深入了解公司当前的实际情况和员工内心真实想法的基础上&#xff0c;我们旨在从专业视角出发&#xff0c;为企业在组织管理方面的不足进行诊断&#xff0c;并进行全面审视。 为了…

vue实现PC端图片放大缩小可鼠标拖动,鼠标滚轮控制放大缩小完整代码付效果图

vue实现图片放大缩小可鼠标拖动&#xff0c;鼠标滚轮控制放大缩小完整代码付效果图 效果图&#xff1a; 创建一个ImageViewer 组件&#xff0c;并且在当前页面引用完整代码如下&#xff1a; 代码引用&#xff1a; <template><view><image-viewer :imageUrl&q…

2024年必备技能:智联招聘岗位信息采集技巧全解析

随着大数据时代的发展&#xff0c;精准定位职业机会成为程序员求职的关键。本文将深入解析如何利用Python高效采集智联招聘上的岗位信息&#xff0c;助你在2024年的职场竞争中脱颖而出。通过实战代码示例&#xff0c;揭示网络爬虫背后的秘密&#xff0c;让你轻松掌握这一必备技…