线性表】1.线性表的定义和基本操作"/>
【Ⅱ线性表】1.线性表的定义和基本操作
本篇文章我们将学习第一个数据结构——线性表。
每当学习新的数据结构时,大家一定要清楚地认识每个数据结构的三要素,在头脑里有一个良好的框架。
逻辑结构 首先需要知道该数据结构的逻辑关系(比如线性还是非线性)以及逻辑之间的数学特性(比如栈的先进先出、完全二叉树的父子关系计算等) 存储(物理)结构 选择一个好的存储结构(顺序存储、链式存储等)将数据存储到计算机中,对每一种存储方式熟练掌握并深刻体会该存储方式的优缺点(比如是否支持随机存取,增删是否需要大量挪动元素等) 数据运算 熟练掌握每种存储方式的运算代码实现(比如初始化,销毁,增删查改等)
一、线性表的定义
1、引例
引例1:英文字母(A,B,……,Z) 引例2:排队
2、定义
线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列
3、非空的线性表或线性结构的特点
<1>存在唯一的一个被称作“第一个”的数据元素
<2>存在唯一的一个被称作“最后一个”的数据元素
<3>除第一个之外,结构中的每个数据元素均只有一个前驱
<4>除最后一个之外,结构中的每个数据元素均只有一个后继
4、注解
①线性表的表示: 若用L命名,表示为L=(,,,……,,,,……,an) ②元素: 这里的元素是抽象的,在具体实现时可以具体确定下来;可以是整数、学生信息等 ③线性表的逻辑特性: :唯一的表头元素
:唯一的表尾元素
除去:每个元素有且仅有一个直接前驱
除去:每个元素有且仅有一个直接后继
①线性表的表示:若用L命名,表示为L=(a1,a2,a3,a4,a5,···,a(i-1),ai,a(i+1),···,an)
②元素:这里的元素是抽象的,在具体实现时可以具体确定下来;可以是整数、学生信息等
③线性表的逻辑特性:
a1:唯一的表头元素
an:唯一的表尾元素
除去a1:每个元素ai有且仅有一个直接前驱a(i-1)
除去an:每个元素ai有且仅有一个直接后继a(i+1)
④线性表的长度:线性表中所含元素的个数;n=0表示元素个数为0,是空表
⑤线性表的特点:
表中元素是有限个
表中元素具有逻辑上的顺序性,各个元素有先后次序
表中元素的数据类型都相同(表中每个元素占用相同大小的存储空间;表中元素都是数据元素,每一个元素都是单个元素)
表中元素具有抽象性。线性表仅讨论元素间的逻辑关系,不讨论元素的具体内容
⑥位序:ai是第i个数据元素,称i为数据元素ai在线性表中的位序;数组下标是从0开始的,位序是从1开始的
⑦线性表、顺序表、链表:
线性表是逻辑结构,表示一对一的相邻关系
顺序表是采用顺序存储对线性表的实现,是指存储结构
链表是采用链式存储对线性表的实现,是指存储结构
⑧判断给定的某个例子是不是线性表:一对一?类型相同?有限序列?逻辑结构?
5.例子
例子1:班级同学之间的友谊
不是线性表,不是一对一线性关系
例子2:点名册
是线性表,满足一对一、类型相同、有限序列、逻辑结构
同学的姓名、性别、出生年月什么的,这其实是数据项;一个数据元素可以由若干个数据项组成
例子3: 一群人线性排队,中间用了个洋娃娃占位
不是线性表,类型不相同
二、线性表的存储结构
这里只是简单的引入一下,不用太纠结,后面文章会具体深入下去学习线性表的存储结构
线性表的存储结构:顺序存储结构(顺序表)、链式存储结构(链表)
1.顺序表、链表
顺序表
定义:把线性表中所有元素按照逻辑顺序,依次存储到从指定位置开始的一块连续存储空间
特点:第一个元素的存储位置就是指定的存储位置;第i+1个元素的存储位置紧接在第i个元素的存储位置后面
例子:
链表
每个节点内容:所存储的元素的信息;元素之间的逻辑关系信息(指针)
例子:
2.顺序存储与链式存储的比较
顺序表
可以随机访问
占用存储空间连续
顺序表的插删,需要移动多个元素
链表
只能顺序访问
占用额外的存储空间存储元素间关系,空间利用率更低
存储空间不一定要连续
链表的插删不需要移动多个元素
三、线性表的基本操作
1.基本操作
InitList(&L):初始化表。构造一个空的线性表
Length(L):求表长。返回线性表L的长度,即L中数据元素的个数
LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值e的元素
GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值
ListInsert(&L,i,e):插入操作。在表L中第i个位置上插入指定元素e
ListDelete(&L,i,&e):删除操作。删除表L中第i个位置上的元素,并用e返回删除元素的值
Printlist(L):输出操作。按前后顺序输出线性表的所有元素值
Empty(L):判空操作。若L为空表,则返回true,否则返回false
DestroyList(&L):销毁操作。销毁线性表一并释放线性表L所占用的内存空间
2.注解
(1)对这些基本操作的具体实现要依赖于具体的存储结构
(2)基本操作的使用:在我们做代码题的时候,某道题里涉及到线性表的基本操作时可以直接使用,不必去实现完整函数
(3)这里的&是引用
注:引用&只出现在C++中,C中无【使用时不必考虑,C++兼容C】;使用指针也可以达到相同效果,但更麻烦【不推荐使用】
引用&使用场景:
①当需要对传入值本身修改时,可选择使用
②当数据本身较大时,为避免复制开销,可使用(普通方式为值的复制,把实参内存中的内容复制到形参内存中去,但时间消耗很大,下面运行例子可以证明)
更多推荐
【Ⅱ线性表】1.线性表的定义和基本操作
发布评论