开发网站 公司/关注公众号一单一结兼职
目录
- 前言
- 一、线性表的链式表示和实现
- 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…...

创建github个人博客
文章目录 安装Hexo安装git安装Node.js安装 Hexo git配置SSH key配置ssh 搭建个人博客新建博客生成静态网页 本文主要参考 【保姆级】利用Github搭建自己的个人博客,看完就会 安装Hexo 参考官方文档:https://hexo.io/zh-cn/docs/ Hexo 是一个快速、简洁且…...

【五子棋game】
编写一个五子棋游戏程序可以分为几个步骤:设计棋盘、定义规则、实现人机交互、判断胜负。下面是一个简化的五子棋游戏程序示例,使用Python语言编写。 首先,我们需要一个棋盘。可以使用一个二维数组来表示棋盘,其中0表示空位&#…...

从入门到精通:使用Python的Watchdog库监控文件系统的全面指南
从入门到精通:使用Python的Watchdog库监控文件系统的全面指南 引言Watchdog库概述核心组件工作原理 快速开始:设置Watchdog安装Watchdog创建一个简单的监控脚本设置和启动Observer 事件处理:如何响应文件系统的变化基本事件处理处理复杂的场景…...

Linux 进程管理指令
Linux 进程管理是系统管理的重要部分,通过各种工具和命令,你可以查看、控制、调试和管理进程。以下是一些常用的 Linux 进程管理命令和工具。 查看进程 1. ps ps 命令用于列出当前系统的进程。 查看当前用户的所有进程: ps -u $USER查看…...

Java OA系统通知公告模块
### 使用Spring Boot实现OA通知公告模块 使用Spring Boot框架实现一个支持多种形式公告发布、设置发布时间和有效期,以及公告发布后推送通知的模块。 #### 项目结构 结构组织项目: OA_Notification_Module/ ├── src/ │ ├── main/ │ │ …...

简约的服务器监控工具Ward
什么是 Ward ? Ward 是一个简单简约的服务器监控工具。 Ward 支持自适应设计系统。此外,它还支持深色主题。它仅显示主要信息,如果您想查看漂亮的仪表板而不是查看一堆数字和图表,则可以使用它。 Ward 在所有流行的操作系统上都能…...

新能源发电乙级资质所需办理标准
企业资历与信誉: 必须具有独立企业法人资格。社会信誉良好,注册资本不少于100万元人民币。 技术条件: 专业技术人员配置齐全、合理,数量需满足资质标准要求。主要技术负责人或总工程师应具有大学本科以上学历、10年以上设计经历&a…...

Elasticsearch:使用 Llamaindex 的 RAG 与 Elastic 和 Llama3
这篇文章是对之前的文章 “使用 Llama 3 开源和 Elastic 构建 RAG” 的一个补充。我们可以在本地部署 Elasticsearch,并进行展示。我们将一步一步地来进行配置并展示。你还可以参考我之前的另外一篇文章 “Elasticsearch:使用在本地计算机上运行的 LLM 以…...

AcWing算法基础课笔记——高斯消元
高斯消元 用来求解方程组 a 11 x 1 a 12 x 2 ⋯ a 1 n x n b 1 a 21 x 1 a 22 x 2 ⋯ a 2 n x n b 2 … a n 1 x 1 a n 2 x 2 ⋯ a n n x n b n a_{11} x_1 a_{12} x_2 \dots a_{1n} x_n b_1\\ a_{21} x_1 a_{22} x_2 \dots a_{2n} x_n b_2\\ \dots \\ a…...

【JavaScript脚本宇宙】图形魔术:探索领先的图像处理库及其独特功能
深入了解HTML5视频:最受欢迎的库及其功能 前言 图像处理是现代数字媒体开发中不可或缺的一部分,从调整图像大小到创建复杂的图形场景。有许多库可用,每个库都有其特定的优点和适用场景。在本文中,我们将探讨六种流行的图像处理库…...