当前位置: 首页 > news >正文

数据结构-线性表的链式表示

目录

  • 前言
  • 一、线性表的链式表示和实现
    • 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. 在链表设置头结点的好处?
    便于首元结点的处理
    便于空表和非空表的处理

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;  //假设作为单链表类型

为了处理方便,这是使用带头结点的链式存储结构。
下面介绍如何实现线性表的基本操作。

  1. 创建空链表
    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;
    }
  2. 销毁链表
    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;
    }
    
  3. 链表的查找
    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;
    }
    
  4. 链表的插入
    step1 首先找到 a i − 1 的存储位置 p a_{i-1}的存储位置p ai1的存储位置p
    step2 生成一个数据域为e的新结点newNode
    step3 插入新结点,即newNode的指针域指向 a i a_i ai,结点 a i − 1 a_{i-1} ai1的指针域指向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;
    }
    
  5. 链表的删除
    step1 首先找到 a i − 1 a_{i-1} ai1的存储位置p
    step2 使结点 a i − 1 a_{i-1} ai1的指针域指向 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 线性表的表示 线性表的链式表示又称为链式存储结构或链式映像 链式存储定义&#xff1…...

DDL-表操作-数据类型

一.DDL-表操作-数据类型 MySQL中的数据类型有很多,主要分为三类:数值类型,字符串类型,日期类型。 二.关系表 注意: 无符号和有符号的取值范围不是一样的,无符号需要加上UNSIGNED范围。 BLOB&#xff1a;用来描述二进制数据 TEXT:用来描述字符串 三.定长字符串和变长字符串 c…...

python实例代码 - 多层感知机预测销售情况

多层感知器预测销售情况 将一种广告投放到TV、newspaper、radio上时不同组合的情况会对应不同的销售量。 # -*- coding:utf-8 -*- # PredicateAdvertise.py # 多层感知器预测销售情况 # 将一种广告投放到TV、newspaper、radio上时不同组合的情况会对应不同的销售量。 import …...

JVM专题十:JVM中的垃圾回收机制

在JVM专题九&#xff1a;JVM分代知识点梳理中&#xff0c;我们主要介绍了JVM为什么采用分代算法&#xff0c;以及相关的概念&#xff0c;本篇我们将详细拆分各个算法。 垃圾回收的概念 垃圾回收&#xff08;Garbage Collection&#xff0c;GC&#xff09;确实是计算机编程中的…...

MySQL入门学习-索引.创建索引

索引是 MySQL 中用于加速查询的一种数据结构。它通过在表的列上创建索引来加快数据的检索速度。 一、索引的概念 索引类似于书的目录&#xff0c;可以快速定位到表中的数据。当在表中的列上创建索引后&#xff0c;MySQL 会根据索引列的值对数据进行排序&#xff0c;并建立一个…...

ChatGPT智能对话绘画系统 带完整的安装源代码包以及搭建教程

系统概述 ChatGPT 智能对话绘画系统是一款集智能语言处理和绘画创作于一体的综合性系统。它利用了深度学习和自然语言处理技术&#xff0c;能够理解用户的意图和需求&#xff0c;并通过与用户的交互&#xff0c;生成富有创意的绘画作品。该系统的核心是一个强大的人工智能模型…...

巴中市红色旅游地管理系统

摘 要 随着红色旅游的兴起&#xff0c;越来越多的人开始对巴中市的红色旅游地产生兴趣。巴中市作为中国革命的重要发源地之一&#xff0c;具有丰富的红色旅游资源。然而&#xff0c;目前巴中市红色旅游地的管理仍然存在许多问题&#xff0c;如信息不对称、资源利用效率低等。为…...

ROS2从入门到精通2-2:详解机器人3D可视化工具Rviz2与案例分析

目录 0 专栏介绍1 什么是Rviz2&#xff1f;2 Rviz2基本界面3 Rviz2基本数据类型4 数据可视化案例4.1 实例1&#xff1a;显示USB摄像头数据4.2 实例2&#xff1a;显示球体 0 专栏介绍 本专栏旨在通过对ROS2的系统学习&#xff0c;掌握ROS2底层基本分布式原理&#xff0c;并具有…...

国企:2024年6月中国铁路相关招聘信息,6.27截止

中国铁路济南局集团有限公司2024年度 招聘普通高校本科及以上学历毕业生公告(三) 中国铁路济南局集团有限公司根据企业发展需要,拟招聘普通高等院校本科及以上学历毕业生,现将有关事项公告如下: 一、招聘计划 本次招聘岗位均为生产一线操作技能岗位,具体岗位、专业要求…...

React+TS前台项目实战(十九)-- 全局常用组件封装:带加载状态和清除等功能的Input组件实现

文章目录 前言Input组件1. 功能分析2. 代码详细注释3. 使用方式4. 效果展示 总结 前言 今天我们来封装一个input输入框组件&#xff0c;并提供一些常用的功能&#xff0c;你可以选择不同的 尺寸、添加前缀、显示加载状态、触发回调函数、自定义样式 等等。这些功能在这个项目中…...

php composer 报错

引用文章&#xff1a; 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 …...

数据安全如何防护?迅软加密软件保护企业数据资产

前言&#xff1a;加密软件是一种重要的工具&#xff0c;可以帮助企业保护其数据资产的安全。通过使用加密算法&#xff0c;加密软件可以将敏感数据转化为无法理解的密文&#xff0c;只有授权的用户才能解密并访问这些数据。 一、迅软加密软件保护企业数据资产的关键方面 1、数…...

Android 11 ,默认授予预置应用/APK 需要的权限,解决permission denied for window type 2003 问题。

写这篇文章的原因是解决了一个APP闪退的问题&#xff0c;闪退的原因是插拔U盘时&#xff0c;注册的广播接收者接收到广播需要弹出一个Dialog询问是否需要打开U盘&#xff0c;这个Dialog设置的是系统级别悬浮窗&#xff0c;没有这个权限&#xff0c;报错导致闪退&#xff0c;下面…...

RabbitMQ(消息队列)

RabbitMQ 它是消息中间件&#xff0c;是在消息的传输过程中保存消息的容器&#xff0c;实现应用程序和应用程序之间通信的中间产品。目前主流消息队列通讯协议是AMQP&#xff08;二进制传输&#xff0c;支持多种语言&#xff09;、JMS&#xff08;HTTP传输&#xff0c;只支持J…...

LeetCode-数组/回溯-No40组合总和II

题目&#xff1a; 给定一个候选人编号的集合 candidates 和一个目标数 target &#xff0c;找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次 。 注意&#xff1a;解集不能包含重复的组合。 示例 1: 输入: ca…...

直接调用 Java 线程的 run() 方法会发生什么?

文章目录 前言回顾run() 方法 vs start() 方法run()方法start()方法 直接调用 run() 方法的影响直接调用 run() 方法调用 start() 方法 示例解析结论个人简介 前言 在Java中&#xff0c;多线程编程是一个重要的概念&#xff0c;尤其是在处理并发任务时。线程是Java中实现多线程…...

计算机毕业设计Thinkphp/Laravel学生考勤管理系统zyoqy

管理员登录学生考勤管理系统后&#xff0c;可以对首页、个人中心、公告信息管理、年级管理、专业管理、班级管理、学生管理、教师管理、课程信息管理、学生选课管理、课程签到管理、请假申请管理、销假申请管理等功能进行相应操作&#xff0c;如图5-2所示。学生登录进入学生考勤…...

3浏览器安全

上一篇&#x1f449;: 浏览器渲染原理 浏览器安全涉及多方面的威胁与防护&#xff0c;其中XSS&#xff08;跨站脚本攻击&#xff09;与CSRF&#xff08;跨站请求伪造&#xff09;是最常见的两类安全问题&#xff0c;而中间人攻击与网络劫持也是不容忽视的安全隐患。下面是对这…...

昇思25天学习打卡Day01

实验结果 心得体会 趁着假期&#xff0c;跟谁官方实战营开始系统学习MindSpore深度学习框架。昇思MindSpore是一个全场景深度学习框架&#xff0c;旨在实现易开发、高效执行、全场景统一部署三大目标。其中易开发表现为API友好&#xff0c;调试难度低&#xff1b;高效执行包括…...

Python-爬虫 下载天涯论坛帖子

为了爬取的高效性&#xff0c;实现的过程中我利用了python的threading模块&#xff0c;下面是threads.py模块&#xff0c;定义了下载解析页面的线程&#xff0c;下载图片的线程以及线程池 import threading import urllib2 import Queue import re thread_lock threading.RL…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...