数据结构-线性表的链式表示
目录
- 前言
- 一、线性表的链式表示和实现
- 1.1 线性表的表示
- 1.2 基本操作的实现
- 1.3 线性表的链式表示的优缺点
- 总结
前言
本篇文章主要介绍线性表的链式表示
一、线性表的链式表示和实现
1.1 线性表的表示
线性表的链式表示又称为链式存储结构或链式映像
链式存储定义:逻辑上相邻的数据元素在物理存储结构中不一定相邻
线性表的链式表示是用一组物理位置任意的存储单元来存放线性表的数据元素,这组存储单元可能是连续,也可能是不连续的,取决于操作系统的分配策略。
线性表的逻辑关系使用指针表示
线性表
( a , b , c , d ) (a,b,c,d) (a,b,c,d)
链式存储结构

一个结点由数据域和指针域组成
数据域:数据元素本身本身信息,
指针域:存储其后继结点的存储地址
一般,称指向第一个结点的指针称为链表的头指针
一般,可以将链式存储结构简化如下图表示:

单链表是由头指针唯一确定,因此单链表可以用头指针的名字来命令。
与链式存储结构有关的术语
假设有一个线性表 ( a 1 , a 2 , ⋯ , a n ) (a_1,a_2,\cdots,a_n) (a1,a2,⋯,an),其链式存储结构如下:

头指针:指向链表的第一个结点的指针
首元结点:指链表中存储第一个数据元素 a 1 a_1 a1的结点
头结点:为了便于对链表的处理,在链表的首元结点之前附加的一个结点
假设一个线性表为 ( a , b , c , d ) (a,b,c,d) (a,b,c,d)
不带头结点的链式存储结构

带头结点的链式存储结构

讨论
- 如何表示空表?
无头结点时,头指针为空时表示空表
有头结点时,当头结点的指针域为空时表示空表 - 在链表设置头结点的好处?
便于首元结点的处理
便于空表和非空表的处理
1.2 基本操作的实现
单链表的定义和表示
//定义返回值常量
#define SUCCESS 1
#define ERROR 0//假设数据元素类型为char
typedef char ElemType;//定义结点类型
struct Node;
typedef struct Node* PNode; //假设作为结点指针类型
struct Node {ElemType data; //数据域PNode next; //指针域
};typedef struct Node* LinkList; //假设作为单链表类型
为了处理方便,这是使用带头结点的链式存储结构。
下面介绍如何实现线性表的基本操作。
-
创建空链表
step1 使用malloc()函数创建一个sizeof(struct Node)大小的空间作为头结点
step2 将头结点的指针域置为NULL,表示一个空表//3.1 创建一个空链表 LinkList createNullList_link(void) {LinkList llist = (LinkList)malloc(sizeof(struct Node));if (NULL == llist){printf("malloc fail!\n");return NULL;}llist->next = NULL;return llist; } -
销毁链表
step1 首先销毁链表的数据元素结点
step2 最后销毁链表的头结点//3.2 销毁一个单链表 void destroyList_link(LinkList* linkList) {assert(linkList && *linkList);PNode p = (*linkList)->next;//1. 销毁数据元素结点while (p){PNode pnext = p->next;free(p);p = pnext;}//2. 销毁头结点free(*linkList);*linkList = NULL; } -
链表的查找
step1 判断链表是否为空表
step2 从首元结点开始查找
step3 查找失败,返回ERROR;查找成功,返回数据元素的位置序号//3.7 根据指定数据元素e获取数据元素的对应序号 int locateElem_link(LinkList linkList, ElemType e) {assert(linkList);PNode p = linkList->next; //首元结点int j = 1;while (p && p->data != e){p = p->next;j++;}if (p)return j;elsereturn ERROR; } -
链表的插入
step1 首先找到 a i − 1 的存储位置 p a_{i-1}的存储位置p ai−1的存储位置p
step2 生成一个数据域为e的新结点newNode
step3 插入新结点,即newNode的指针域指向 a i a_i ai,结点 a i − 1 a_{i-1} ai−1的指针域指向newNode

//3.8 在第i个元素之前插入数据元素e int insertElem_link(LinkList linkList, int i, ElemType e) {assert(linkList);PNode p = linkList; //考虑插入位置可能在第1个之前int j = 0;while (p && j < i - 1){p = p->next;++j;}if (!p || j > i - 1) //当 p == NULL成立时,说明i-1大于表长; j > i-1 为了应对i <= 0情况 return ERROR;//新建结点PNode newNode = (PNode)malloc(sizeof(struct Node));if (NULL == newNode){printf("malloc fail!\n");return ERROR;}newNode->data = e;newNode->next = p->next;p->next = newNode;return SUCCESS; } -
链表的删除
step1 首先找到 a i − 1 a_{i-1} ai−1的存储位置p
step2 使结点 a i − 1 a_{i-1} ai−1的指针域指向 a i + 1 a_{i+1} ai+1

//3.9 将链表第i个数据元素删除 int deleteElem_link(LinkList linkList, int i) {assert(linkList);PNode p = linkList;int j = 0;while (p->next && j < i - 1){p = p->next;j++;}if (!(p->next) || j > i - 1) //p->next,因为删除的是p->next,而不是p所指的结点return ERROR;PNode q = p->next;p->next = q->next;free(q);q = NULL;return SUCCESS; }
1.3 线性表的链式表示的优缺点
-
优点
在线性表的链式存储结构中,数据元素之间的逻辑关系靠结点的指针域来指示,结点的空间是动态申请和动态释放的,所以不需要预先按最大的需要分配连续空间;
线性表的插入和删除只需要修改指针域,而不需要移动其他数据元素 -
缺点
存储密度小,每个结点的指针域需要额外占用存储空间;
链式存储结构是一种非随机存储结构,查找任一个结点都要从头指针开始,沿着指针链一个一个地搜索,增加算法的时间代价。
总结
完整代码:https://gitee.com/PYSpring/data-structure/tree/master
相关文章:
数据结构-线性表的链式表示
目录 前言一、线性表的链式表示和实现1.1 线性表的表示1.2 基本操作的实现1.3 线性表的链式表示的优缺点 总结 前言 本篇文章主要介绍线性表的链式表示 一、线性表的链式表示和实现 1.1 线性表的表示 线性表的链式表示又称为链式存储结构或链式映像 链式存储定义࿱…...
DDL-表操作-数据类型
一.DDL-表操作-数据类型 MySQL中的数据类型有很多,主要分为三类:数值类型,字符串类型,日期类型。 二.关系表 注意: 无符号和有符号的取值范围不是一样的,无符号需要加上UNSIGNED范围。 BLOB:用来描述二进制数据 TEXT:用来描述字符串 三.定长字符串和变长字符串 c…...
python实例代码 - 多层感知机预测销售情况
多层感知器预测销售情况 将一种广告投放到TV、newspaper、radio上时不同组合的情况会对应不同的销售量。 # -*- coding:utf-8 -*- # PredicateAdvertise.py # 多层感知器预测销售情况 # 将一种广告投放到TV、newspaper、radio上时不同组合的情况会对应不同的销售量。 import …...
JVM专题十:JVM中的垃圾回收机制
在JVM专题九:JVM分代知识点梳理中,我们主要介绍了JVM为什么采用分代算法,以及相关的概念,本篇我们将详细拆分各个算法。 垃圾回收的概念 垃圾回收(Garbage Collection,GC)确实是计算机编程中的…...
MySQL入门学习-索引.创建索引
索引是 MySQL 中用于加速查询的一种数据结构。它通过在表的列上创建索引来加快数据的检索速度。 一、索引的概念 索引类似于书的目录,可以快速定位到表中的数据。当在表中的列上创建索引后,MySQL 会根据索引列的值对数据进行排序,并建立一个…...
ChatGPT智能对话绘画系统 带完整的安装源代码包以及搭建教程
系统概述 ChatGPT 智能对话绘画系统是一款集智能语言处理和绘画创作于一体的综合性系统。它利用了深度学习和自然语言处理技术,能够理解用户的意图和需求,并通过与用户的交互,生成富有创意的绘画作品。该系统的核心是一个强大的人工智能模型…...
巴中市红色旅游地管理系统
摘 要 随着红色旅游的兴起,越来越多的人开始对巴中市的红色旅游地产生兴趣。巴中市作为中国革命的重要发源地之一,具有丰富的红色旅游资源。然而,目前巴中市红色旅游地的管理仍然存在许多问题,如信息不对称、资源利用效率低等。为…...
ROS2从入门到精通2-2:详解机器人3D可视化工具Rviz2与案例分析
目录 0 专栏介绍1 什么是Rviz2?2 Rviz2基本界面3 Rviz2基本数据类型4 数据可视化案例4.1 实例1:显示USB摄像头数据4.2 实例2:显示球体 0 专栏介绍 本专栏旨在通过对ROS2的系统学习,掌握ROS2底层基本分布式原理,并具有…...
国企:2024年6月中国铁路相关招聘信息,6.27截止
中国铁路济南局集团有限公司2024年度 招聘普通高校本科及以上学历毕业生公告(三) 中国铁路济南局集团有限公司根据企业发展需要,拟招聘普通高等院校本科及以上学历毕业生,现将有关事项公告如下: 一、招聘计划 本次招聘岗位均为生产一线操作技能岗位,具体岗位、专业要求…...
React+TS前台项目实战(十九)-- 全局常用组件封装:带加载状态和清除等功能的Input组件实现
文章目录 前言Input组件1. 功能分析2. 代码详细注释3. 使用方式4. 效果展示 总结 前言 今天我们来封装一个input输入框组件,并提供一些常用的功能,你可以选择不同的 尺寸、添加前缀、显示加载状态、触发回调函数、自定义样式 等等。这些功能在这个项目中…...
php composer 报错
引用文章: Composer设置国内镜像_composer 国内源-CSDN博客 php composer.phar require --prefer-dist yiidoc/yii2-redactor "*" A connection timeout was encountered. If you intend to run Composer without connecting to the internet, run the …...
数据安全如何防护?迅软加密软件保护企业数据资产
前言:加密软件是一种重要的工具,可以帮助企业保护其数据资产的安全。通过使用加密算法,加密软件可以将敏感数据转化为无法理解的密文,只有授权的用户才能解密并访问这些数据。 一、迅软加密软件保护企业数据资产的关键方面 1、数…...
Android 11 ,默认授予预置应用/APK 需要的权限,解决permission denied for window type 2003 问题。
写这篇文章的原因是解决了一个APP闪退的问题,闪退的原因是插拔U盘时,注册的广播接收者接收到广播需要弹出一个Dialog询问是否需要打开U盘,这个Dialog设置的是系统级别悬浮窗,没有这个权限,报错导致闪退,下面…...
RabbitMQ(消息队列)
RabbitMQ 它是消息中间件,是在消息的传输过程中保存消息的容器,实现应用程序和应用程序之间通信的中间产品。目前主流消息队列通讯协议是AMQP(二进制传输,支持多种语言)、JMS(HTTP传输,只支持J…...
LeetCode-数组/回溯-No40组合总和II
题目: 给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次 。 注意:解集不能包含重复的组合。 示例 1: 输入: ca…...
直接调用 Java 线程的 run() 方法会发生什么?
文章目录 前言回顾run() 方法 vs start() 方法run()方法start()方法 直接调用 run() 方法的影响直接调用 run() 方法调用 start() 方法 示例解析结论个人简介 前言 在Java中,多线程编程是一个重要的概念,尤其是在处理并发任务时。线程是Java中实现多线程…...
计算机毕业设计Thinkphp/Laravel学生考勤管理系统zyoqy
管理员登录学生考勤管理系统后,可以对首页、个人中心、公告信息管理、年级管理、专业管理、班级管理、学生管理、教师管理、课程信息管理、学生选课管理、课程签到管理、请假申请管理、销假申请管理等功能进行相应操作,如图5-2所示。学生登录进入学生考勤…...
3浏览器安全
上一篇👉: 浏览器渲染原理 浏览器安全涉及多方面的威胁与防护,其中XSS(跨站脚本攻击)与CSRF(跨站请求伪造)是最常见的两类安全问题,而中间人攻击与网络劫持也是不容忽视的安全隐患。下面是对这…...
昇思25天学习打卡Day01
实验结果 心得体会 趁着假期,跟谁官方实战营开始系统学习MindSpore深度学习框架。昇思MindSpore是一个全场景深度学习框架,旨在实现易开发、高效执行、全场景统一部署三大目标。其中易开发表现为API友好,调试难度低;高效执行包括…...
Python-爬虫 下载天涯论坛帖子
为了爬取的高效性,实现的过程中我利用了python的threading模块,下面是threads.py模块,定义了下载解析页面的线程,下载图片的线程以及线程池 import threading import urllib2 import Queue import re thread_lock threading.RL…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案
一、TRS收益互换的本质与业务逻辑 (一)概念解析 TRS(Total Return Swap)收益互换是一种金融衍生工具,指交易双方约定在未来一定期限内,基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
Qt 事件处理中 return 的深入解析
Qt 事件处理中 return 的深入解析 在 Qt 事件处理中,return 语句的使用是另一个关键概念,它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别:不同层级的事件处理 方…...
