网站排名第一/google play下载官方版
梳理几个名词:
逻辑地址:就是说是第几个元素。
物理地址:也就是存储地址,在计算机里具体存放的位置。
线性表的存储结构分为:
(1)顺序存储结构:将数据依次存储在连续的整块物理空间中。简称顺序表。
特点:通过计算地址,能直接访问任何数据元素,即随机访问。适合查找,不适合插入删除操作。
(2)链式存储结构:数据分散的存储在物理空间中,通过一根线保存着它们之间的逻辑关系。简称链表、线性链表。
特点:在逻辑上相邻的结点在物理上不必相邻。不能随机存取,只能顺序存储。适合插入删除,不适合访问。
一、线性结构 与 线性表
1、线性结构是最简单、最常用的一种数据结构。
2、线性结构特点
在数据元素的非空有限集合中,除了第一个元素无直接前驱、最后一个元素无直接后继外,集合中其余的每个数据元素都有唯一的直接前驱和唯一的直接后继。可以想象成:把所有结点用一根直线穿起来。
3、线性表
含义:是由
个类型相同的数据元素组成的有限序列。 即:具有相同数据类型的n个数据元素的有限序列,其中n为表长,n=0 是一个空表。
记作: 。
当n >0,除第一个元素无直接前驱、最后一个元素无直接后继外,其余的元素都只有一个前驱和一个直接后继。即:数据元素之间具有一对一的关系。
例如:英文字母表(A,B,C...Z),就是一个简单的线性表。表中的每一个英文字母就是一个数据元素,每个元素之间存在唯一的顺序关系,比如:B前面就是A,B后面就是C,以此类推。
4、线性表的逻辑结构
如下图所示:
5、线性表的长度
线性表中元素的个数 ,被定义为线性表的长度,
时被称为空表。
6、线性表的特点
(1)同一性。线性表中所有数据元素都具有相同的数据类型。
(2)有穷性。线性表由有限个数据元素组成,表的长度就是表中数据元素的个数。
(3)有序性。线性表中相邻数据元素之间存在着顺序关系,。
7、线性表的存储
在计算机中主要有两种存储结构用来存放线性表:顺序存储结构和链式存储结构。
二、线性表的顺序存储结构——顺序表
1、含义
用一组地址连续的存储单元,依次存储线性表中的各个元素。使得线性表中在逻辑结构上相邻的数据元素存储在连续的物理存储单元中,即:通过数据元素物理存储的连续性,来反映数据元素之间逻辑上的相邻关系。就是说,拿一块内存,把数据挨个存进去,这样就能保证表里元素的逻辑顺序和物理顺序相同。
2、顺序表
采用顺序存储结构的线性表简称为顺序表。
可将顺序表归纳为:关系线性化,结点顺序存。
3、线性表顺序存储结构示意图
从图中可以看出,在顺序表中,每个结点 的存储地址是该结点在表中的逻辑位置 i 的线性函数,只要知道线性表中第一个元素的存储地址(基地址)和表中每个元素所占存储单元的多少,就可以计算出线性表中任意一个数据元素的存储地址,从而实现对顺序表中数据元素的随机存取。
4、地址的计算
假设线性表中有 n 个元素,每个元素占 k 个单元,第一个元素的地址为: (也叫基地址) ,则可以公式计算出第 i 个元素的地址:
:
5、顺序表上的操作
(1)查找。可以通过元素所在的序号查找它,也可以通过元素内容来查找。
(2)增加和删除。都会涉及到对元素进行移动。
(3)合并多个顺序表。
例如:有如下顺序表,现在要在第三个元素前面插入6,此时就要把第三个元素一直到最后一个元素,全部向后移动一个位置。
同理,删除也一样,只是把元素像前移动。
6、顺序表优缺点
方便存取,不适合插入和删除。
三、线性表的链式存储
一种动态存储方法。通常将采用链式存储结构的线性表称为线性链表。
分类 | |
从链接方式的角度看 | 单链表 |
双链表 | |
循环链表 | |
从实现角度看 | 动态链表 |
静态链表 |
1、单链表
在顺序表中,用一组地址连续的存储单元
链表:由一系列结点组成的元素集合。
每个节点包含两部分:
1、数据域item :存储数据的地方。
2、next:指向下一个节点的指针。
通过结点之间的相互连接,最终串联成一个链表。
列表:顺序存储
链表:链式存储
链表的方法:
输出当前节点的数据域:节点名.item
输出当前节点的下个节点的数据域:节点名.next.item
举例1:手动创建一个链表:
现有三个节点分别是a,b,c,各节点对应的数据域的值分别是1,2,3
class Node:def __init__(self, item):self.item = itemself.next = Nonea = Node(1) # 实例化一个对象a,即:创建一个新节点a
b = Node(2) # 创建一个新节点b
c = Node(3)
a.next = b # a的下一个值指向b
b.next = c # b的下一个值指向c
print(a.item) # 输出节点a的数据域的值
print(a.next.item) # 输出a 的下一个节点的值
# 结果:
1
2print(a.next.next.item) # 输出a 的下一个节点的下一个节点的值,即a下下个节点的值
# 结果:
3
效果图如下:
2、头插法、尾插法
链表的头节点:head
尾节点:tail
头插法:新节点先连上原来的头节点,然后head指向新节点。(先连上再改头)
node.next=head
head=node
尾插法:不光要知道头在哪,也要知道尾在哪。只有一个头节点时,该节点既是头节点,又是尾节点(即:head tail都指向这个节点),接着再把新节点先连上原来的尾节点 ,tail指向新节点:(先连上再改尾)
tail.next = node
tail = node
举例、分别利用头插法、尾插法,来创建一个链表
举例1:头插法
用头插法分别把1,2,3插到链表里。
class Node:def __init__(self, item):self.item = itemself.next = Nonedef creat_linklist_head(li): # 传入一个列表,列表里面的值作为各个节点的值head = Node(li[0]) # 根据列表的第一个元素创建头节点for i in li[1:]: # 列表除第一个元素外,剩下的元素都将作为节点的值传进去node = Node(i) # 创建一个新节点nodenode.next = head # 头插法: 新节点要先连上原来的头节点head = node # head指向新节点return heada1 = creat_linklist_head([1, 2, 3])
print(a1)
# 结果:
<__main__.Node object at 0x000002EA5BB59128>进程已结束,退出代码 0
结果返回的是一个内存地址,说明,你创建了一个Node对象,并打印了它的内存地址,如果想打印出Node对象的属性,可以在Node类中定义一个__str__方法来返回一个可读的字符串表示形式。
即:加如下代码:
def __str__(self):return str(self.item)
完整代码如下:
class Node:def __init__(self, item):self.item = itemself.next = Nonedef __str__(self): # !!!return str(self.item)def creat_linklist_head(li): # 传入一个列表,列表里面的值作为各个节点的值head = Node(li[0]) # 根据列表的第一个元素创建头节点for i in li[1:]: # 列表除第一个元素外,剩下的元素都将作为节点的值传进去node = Node(i) # 创建一个新节点node.next = head # 头插法: 新节点要先连上原来的头节点head = node # head指向新节点return heada1 = creat_linklist_head([1, 2, 3])
print(a1)
# 结果:
3
为什么结果为3 ?
因为,创建一个单链表函数,返回值是head,也就是头节点,而我们把1,2,3,按头插法插进去之后,头节点的数据域就变成的3,所以返回3 。
或者上面的写法中,把print(a1)改下:改成:
print(a.item) # 输出头节点的数据域
print(a.next.item) # 输出头节点的下一个节点的数据域
结果:
3
2
延申:怎么遍历链表?也就是说,怎么从头到尾查看所有节点的数据域。
class Node:def __init__(self, item):self.item = itemself.next = Nonedef __str__(self):return str(self.item)def creat_linklist_head(li): # 传入一个列表,列表里面的值作为各个节点的值head = Node(li[0]) # 根据列表的第一个元素创建头节点for i in li[1:]: # 列表除第一个元素外,剩下的元素都将作为节点的值传进去node = Node(i) # 创建一个新节点node.next = head # 头插法: 新节点要先连上原来的头节点head = node # head指向新节点return headdef print_linklist(a): # 链表的遍历while a: # 只要链表不是空的就会一直打印print(a.item, end=",") # 打印节点的值a = a.next # 类似i+=1,打印完当前节点,指针指向下个节点,这样才能循环遍历a1 = creat_linklist_head([1, 2, 3]) # 返回头节点
print_linklist(a1)
# 结果:
3,2,1,
注意:
def print_linklist(a):while a: # 只要链表不是空的就会一直打印print(a.item, end=",") # 打印节点的值a = a.next
a=a.next是循环变量,类似i+=1的作用,打印完当前节点的数据域的值后,就要把指针指向下一个节点,否则就一直打印当前这一个节点的数据域,程序就会进入死循环,这里就会一直打印3 。
可以看到,头插法得到的是倒叙的(因为插入的是123,结果确实321,),下面的尾插法得到的是正序的。
举例2:尾插法
class Node:def __init__(self, item):self.item = itemself.next = Nonedef __str__(self):return str(self.item)# 尾插法
def creat_linklist_tail(li): # 传入一个列表,列表里面的值作为各个节点的值head = Node(li[0]) # !!将列表的第一个元素作为头节点tail = head #!因为此时只有一个头节点,所以它既是头节点,又是尾节点(即:head tail都指向这个节点)for i in li[1:]: # 列表除第一个元素外,剩下的元素都将作为节点的值传进去node = Node(i) # 创建一个新节点tail.next = node # 尾插法: 新节点先连上原来的尾节点tail = node # tail指向新节点return head # 返回头节点,因为只有头节点有next方法def print_linklist(a): # 链表的遍历while a: # 只要链表不是空的就会一直打印print(a.item, end=",") # 打印节点的值a = a.next # 类似i+=1,打印完当前节点,指针指向下个节点,这样才能循环遍历a1 = creat_linklist_tail([1, 2, 3])
print_linklist(a1)
# 结果:
1,2,3,
注意:尾插法:
第一步:头节点创建之后,head、tail都指向头节点。
第二步:新节点要先连上原来的尾节点 : tail.next = node
第三步:tail指向新节点:tail = node
举例3:中间插入或删除一个节点
1、插入:新节点插到链表除了首尾之外的任意位置。
假设新节点名字为 p,当前节点叫 curNode,
第一步:先把新节点跟当前节点的下个节点相连:p.next=curNode.next
第二步:当前节点的下一个节点指向p:curNode.next=p
2、删除
直接curNode.next=curNode.next.next即可。
如果要删除的节点设为p话,p=curNode.next,那么,上句改成curNode.next=p.next也一样。
相关文章:

线性结构、线性表、顺序表、链表、头插法、尾插法、中间插入或删除一个节点
梳理几个名词: 逻辑地址:就是说是第几个元素。 物理地址:也就是存储地址,在计算机里具体存放的位置。 线性表的存储结构分为: (1)顺序存储结构:将数据依次存储在连续的整块物理空…...

C# Task.WaitAll 的用法
目录 简介 1.WaitAll(Task[], Int32, CancellationToken) 2.WaitAll(Task[]) 3.WaitAll(Task[], Int32) 4.WaitAll(Task[], CancellationToken) 5.WaitAll(Task[], TimeSpan) 结束 简介 Task.WaitAll 是 C# 中用于并行编程的一个的方法,它属于 System.Threa…...

vue2 前端实现pdf在线预览(无插件版)
toFielDetail()是点击预览的方法,getOfficialFile是获取文件流的接口正常定义即可: export function getOfficialFile(query) {return request({url: /dataAsset/projectassess/getOfficialFile,method: get,params: query,}); } 调用接口的页面需要引用…...

排序XXXXXXXXX
信息学奥赛|常见排序算法总结(C+) - 腾讯云开发者社区-腾讯云 (tencent.com) https://cloud.tencent.com/developer/news/975232 常用序号层级排序 一、序号 序号Sequence Number,有顺序的号码,如数字序号…...

【文件解析漏洞】实战详解!
漏洞描述: 文件解析漏洞是由于中间件错误的将任意格式的文件解析成网页可执行文件,配合文件上传漏洞进行GetShell的漏洞! IIS解析漏洞: IIS6.X: 方式一:目录解析 在网站下建立文件夹的名字为.asp/.asa 的文件夹,其目…...

【杂谈】学会让你节省三秒钟——Dev-c++的缺省源
【杂谈】学会让你节省三秒钟——Dev-c的缺省源 1.前言2.缺省源的介绍3.注意 1.前言 你是否在为每次写程序都要自己手打一遍框架而感到苦恼?为什么大佬的Dev-C一新建文件就会自动出现程序框架?看完这篇文章,让你也能成为大佬,不用再…...

推荐一款前端滑动验证码插件(Vue、uniapp)
uniapp版本:滑块拼图验证码,有后端,简单几步即可实现,小程序、h5都可以用 - DCloud 插件市场 Vue版本及cdn版本可以查阅文档: 行为验证 | Poster 文档 示例代码: <template><view id"app&…...

【Git】git stash
目录 基本概念参数详解listshowsavepushpop|applydropclearbranch 参考文章 Git的stash命令是一个非常实用的功能,它允许开发者临时保存工作目录和暂存区的更改,以便能够切换到其他分支或进行其他操作,而不会丢失当前的修改。以下是git stash…...

不得不安利的程序员开发神器,太赞了!!
作为一名程序员,你是否常常为繁琐的后端服务而感到头疼?是否希望有一种工具可以帮你简化开发流程,让你专注于创意和功能开发?今天,我要向大家隆重推荐一款绝佳的开发神器——MemFire Cloud。它专为懒人开发者准备&…...

吴恩达机器学习C1W2Lab06-使用Scikit-Learn进行线性回归
前言 有一个开源的、商业上可用的机器学习工具包,叫做scikit-learn。这个工具包包含了你将在本课程中使用的许多算法的实现。 目标 在本实验室你可以: 利用scikit-learn实现基于正态方程的近似解线性回归 工具 您将使用scikit-learn中的函数以及ma…...

CSS实现表格无限轮播
<div className{styles.tableTh}><div className{styles.thItem} style{{ width: 40% }}>报警名称</div><div className{styles.thItem} style{{ width: 35% }}>开始时间</div><div className{styles.thItem} style{{ width: 25% }}>状态&…...

编程小白如何从迷茫走出
针对新生们常常感到的迷茫,以下是如何选择适合自己的编程语言、如何制定有效的学习计划以及如何避免常见的学习陷阱的详细建议: 一、如何选择适合自己的编程语言 明确需求和目标:不同的编程语言有不同的特点和适用场景。例如,Py…...

14 B端产品的运营管理
通过运营找到需求并通过交换价值提供供给,再逐步扩大规模、站稳脚跟,辅助产品在商业竞争中获胜。 B端产品运营框架 1. 打通渠道 目的:触达客户。 环节:文案策划、活动策划→广告渠道推广→线下BD。 线下BD:通过见面…...

STM32_RTOS学习笔记——1(列表与列表项)
总体RTOS笔记目录 一,列表与列表项(本文) 二,待定 视频参考:B站野火 一,C语言列表概念 列表就是C语言中的链表,链表就如同下面的衣架一样,需要的各种内容可以参考 C语言链表可…...

子网划分案例
划分子网是将一个较大的网络划分为多个较小的子网,以提高网络管理和安全性 子网划分可以更有效地利用 IP 地址空间,并且有助于控制网络流量、提高网络性能和安全性。 子网划分的主要步骤如下: 确定需要划分的子网数量以及每个子网所需的主…...

javaweb_02:Maven
一、引入 在javaweb的开发中,需要使用大量的jar包,我们得手动去导入,而Maven可以自动帮我们导入和配置这个jar包。 二、Maven项目框架管理工具 核心思想:约定大于配置(有约束不违反):Maven会…...

19.延迟队列优化
问题 前面所讲的延迟队列有一个不足之处,比如现在有一个需求需要延迟半个小时的消息,那么就只有添加一个新的队列。那就意味着,每新增一个不同时间需求,就会新创建一个队列。 解决方案 应该讲消息的时间不要跟队列绑定…...

P10477 Subway tree systems 题解,c++ 树相关题目
题目 poj 链接 洛谷链接 n n n 组数据,每组数据给定两个 01 01 01 串(长度不超过 3000 3000 3000),意思如下: 对于每一个 0 0 0,代表该节点有一个子节点,并前往该子节点。对于每一个 1 1 …...

18.jdk源码阅读之CopyOnWriteArrayList
1. 写在前面 CopyOnWriteArrayList 是 Java 中的一种线程安全的 List 实现,基于“写时复制”(Copy-On-Write)机制。下面几个问题大家可以先思考下,在阅读源码的过程中都会解答: CopyOnWriteArrayList 适用于哪些场景…...

美股:AMD展现乐观前景,挑战AI加速器市场霸主
在科技行业的激烈竞争中,AMD公司近期发布了对当前季度收入的乐观预测,显示出其新推出 一、AMD第三季度营收预期超越分析师平均预期 AMD在周二的声明中预计,第三季度营收将达到约67亿美元,这一数字超出了分析师此前平均预期的66.…...

如何提高计算机视觉技术在复杂环境和低光照条件下的物体识别准确率?
要在复杂环境和低光照条件下提高计算机视觉技术的物体识别准确率,可以采取以下几个方法: 数据增强:在训练集中添加各种复杂环境和低光照条件下的图片,通过增加数据的多样性,使算法能够更好地适应各种场景。 预处理&am…...

ubuntu cmake使用自己版本的qt
给一篇文章参考 https://blog.csdn.net/bank_dreamer/article/details/138678909 自己使用的范例 set(Qt5_DIR "/home/peak/Qt5.14.0/5.14.0/gcc_64/lib/cmake/Qt5")# 设置Qt5的安装目录 #set(CMAKE_PREFIX_PATH "/home/peak/Qt5.14.0")find_package(Qt5…...

Python基础知识笔记---保留字
保留字,也称关键字,是指被编程语言内部定义并保留使用的标识符。 一、保留字概览 二、保留字用途 1. False:表示布尔值假。 2. None:表示空值或无值。 3. True:表示布尔值真。 4. not:布尔逻辑操作符…...

Python面试整理-Web开发
在Python中,Web开发可以利用多种强大的框架和库来构建从简单的静态网页到复杂的动态Web应用。以下是几种流行的Python Web开发框架和相关技术的概述: 1. Flask Flask 是一个轻量级的Web应用框架,它非常灵活,适用于小型到中型项目,或作为构建微服务的基础。Flask的核心非常…...

民大食堂用餐小程序的设计
管理员账户功能包括:系统首页,个人中心,用户管理,商家管理,档口号管理,商家餐品管理,餐品种类管理,购物车管理,订单信息管理 微信端账号功能包括:系统首页&a…...

Linux系统编程(4):消息队列
Linux下的进程通信手段基本上是从Unix平台上的进程通信手段继承而来的。 而对Unix发展做出重大贡献的两大主力AT&T的贝尔实验室 以及 BSD(加州大学伯克利分校的伯克利软件发布中心), 他们在进程间通信方面的侧重点有所不同; 前…...

【初阶数据结构篇】单链表的实现(赋源码)
文章目录 单链表的实现代码位置概念与结构概念:结构: 链表的性质链表的分类单链表的实现单链表的创建和打印及销毁单链表的创建单链表的打印单链表的销毁 单链表的插入单链表头插单链表尾插单链表在指定位置之前插入数据单链表在指定位置之后插入数据 单…...

LeetCode 2844.生成特殊数字的最少操作(哈希表 + 贪心)
给你一个下标从 0 开始的字符串 num ,表示一个非负整数。 在一次操作中,您可以选择 num 的任意一位数字并将其删除。请注意,如果你删除 num 中的所有数字,则 num 变为 0。 返回最少需要多少次操作可以使 num 变成特殊数字。 如…...

昇思MindSpore 应用学习-基于 MindSpore 实现 BERT 对话情绪识别
基于 MindSpore 实现 BERT 对话情绪识别 模型简介 BERT全称是来自变换器的双向编码器表征量(Bidirectional Encoder Representations from Transformers),它是Google于2018年末开发并发布的一种新型语言模型。与BERT模型相似的预训练语言模…...

【初阶数据结构篇】顺序表和链表算法题
文章目录 顺序表算法题移除元素删除有序数组中的重复项合并两个有序数组 链表算法题移除链表元素反转链表链表的中间结点合并两个有序链表链表分割链表的回文结构 顺序表算法题 不熟悉顺序表的可以先了解一下 顺序表实现方法 移除元素 给你一个数组 nums 和一个值 val&#x…...