线性表的定义和基本操作
标签: 数据结构
学习人数: 39.3k


高清播放
赞赏支持

线性表的定义

提到线性这个词,并不陌生,在 数据结构的基本概念 中学过线性的逻辑结构。线性逻辑结构是一对一关系,结点之间排成了一列或者一行,所以说线性表也是一种逻辑关系

 

有了对线性表的认知,那么来看一下它的概念:

线性表是具有相同类型的 n (n>=0) 个元素的有限序列,其中 n 为表长,当 n=0 时,该表为空表。

 

为什么要相同类型?计算机在处理大量数据的时候,把相同的数据元素称作为数据对象。往往要处理相同的数据元素,也就处理一种数据对象。不会把音频和图片杂糅到一起进行处理。也不会把抽象事物,比如说人和汽车组合到一起进行处理。因为这样没有意义,也没有高的效率。

 

对于相同类型,在接下来所学到的所有的数据结构中都有这样的要求。因为具有相同类型的数据结构,它在解决实际问题,实现算法时,才更加的有意义。其次,对于这个类型的范围,它的定义其实并不狭隘,并不仅仅局限于我们常见的类型,比如说整型、浮点型这样的类型。对于从实际生活中抽象出来的类型,比如说一本书、一个人也是可以作为一个元素的。它与 C++ 中的面向对象的类比较相似。

 

除了相同类型,定义中还有一个比较重要的点,那就是是有限序列。什么是有限?就是说明该线性表的长度是有限的,因为计算机无法处理无限多的数据。第二个是序列,根据下面的表示方法可以发现,线性表中每一个元素都是有序号的,序列的意思就是有序号的一种排列。这就是在线性表定义中比较重要的两个点。

 

若 L 命名为线性表,则一般表示为:

在 L 当中,线性表的每一个元素都具有相同类型,都是属于同一个数据对象的数据元素,分别是 a1、a2 一直到 an 。可以发现,对于所有的元素它都是有序号的。

 

那么在表中,第一个元素,称它为表头元素,最后一个元素称它为表尾元素。除了这样,该线性表还有一些其他的逻辑关系。

 

在线性表中,每一个元素除了表头元素,它都有一个前驱结点。也就是 ai+1 的前驱结点,即是 ai 。同样在表中,每一个元素除了表尾元素,它都有一个后继结点。也就是 ai 的后继结点 ai+1 ,这就是线性表在定义上的所有知识点。根据定义,总结一下线性表的特点

1、表中元素个数有限
2、表中元素具有逻辑上的顺序性,在序列中各个元素排序有其先后次序
3、表中元素都是数据元素,每个元素都是单个元素
4、表中元素的数据类型都相同,这意味着每个元素占有相同大小的存储空间
5、表中元素具有抽象性,即讨论元素间一对一的逻辑关系,而不考虑元素究竟表示的内容
6、线性表是一种逻辑结构,表示元素之间一对一相邻的关系

 

 

线性表的基本操作

线性表的九种基本操作:

首先对于任何一种数据结构,都有一个创建它的方法,也有一个销毁它的方法。在线性表中创建它的方法叫做 InitList,传入的参数是一个线性表,它的作用是初始化这个线性表,构造一个空的线性表。注意传入的参数是引用类型。第二个就是销毁的操作,叫 DestroyList,传入的参数依旧是一个引用类型的线性表。它是销毁这个线性表,并释放线性表所占用的内存空间。注意针对不同的存储结构而言,它们具体的实现方式可能有非常大的差异。

 

接下来有两种查找操作,一种是按值查找,另一种是按位查找。首先...

登录查看完整内容


课后作业

掌握线性表的定义和基本操作


登录后开始许愿

2 条上岸许愿
sheir
2024年7月1日 09:38

线性表用法

分析 时间复杂度?

空间复杂度?

 

如何评估一个算法?

赞(0)
Charisma
2021年7月9日 00:16

视频为啥不能看

 

赞(0)