【数据结构】什么是线性表?

2024-07-04 06:30| 来源: 网络整理| 查看: 265

🦄个人主页:修修修也

🎏所属专栏:数据结构

⚙️操作环境:Visual Studio 2022

线性表的定义

生活中常见的线性表

结语

线性表的定义

线性结构的特点:

在数据元素的非空有限集中:

存在唯一的一个被称作"第一个"的数据元素;存在唯一的一个被称做"最后一个"的数据元素;除第一个之外,集合中的每个数据元素均只有一个前驱;除最后一个之外,集合中每个数据元素均只有一个后继.

线性结构的数据元素之间的关系如下图:

线性表,栈,队列,串和数组都属于线性结构.而线性表是最基本也是最常用的一种线性结构.

线性表(List):零个或多个数据元素的有限序列.

序列,顾名思义,元素之间是有顺序的,就像上图中那样,八个小朋友都是按顺序排好的,第二个在第一个后面,第三个在第二个后面......

其次,线性表强调是有限的,即数据元素的个数是有限的.事实上,在计算机中处理的对象都是有限的,无限的数列,只存在于数学的概念中.

如果我们像高数那样定义线性表的概念,则:

若将线性表记为( $a_1{_{}}$ ,..., $a_{i-1}$ , $a_{i}$ , $a_{i+1}$ ,..., $a_{n}$ ),

则表中 $a_{i-1}$ 领先于 $a_{i}$ , $a_{i}$ 领先于 $a_{i+1}$ ,

称 $a_{i-1}$ 是 $a_{i}$ 的直接前驱元素, $a_{i+1}$ 是 $a_{i}$ 的直接后继元素.

当i=1,2,...,n-1时, $a_{i}$ 有且仅有一个直接后继,

当i=2,3,...,n时, $a_{i}$ 有且仅有一个直接前驱.

其对应关系如下图所示:

所以,将线性表元素的个数n(n>=0)定义为线性表的长度,当n=0时,称为空表.

在非空表中的每个数据元素都有一个确定的位置,如 $a_{1}$ 是第一个数据元素, $a_{n}$ 是最后一个数据元素, $a_{i}$ 是第i个数据元素,称i为数据元素 $a_{i}$ 在线性表中的位序.

生活中常见的线性表

我们生活中有很多东西都有线性表的身影,如一年中的星座列表:

班上同学的点名册,因为每个同学的信息是按顺序排的,因此虽然每个数据元素有很多数据项,但组合起来仍然是一个线性表:

还有我们天天都在用的手机通讯录,和点名册类似,同样是一种线性表:

还有一点要注意,如果我现在要将我的猫和张三家的狗也加入通讯录中,可行吗?

答案是不可以,因为根据线性表的定义,必须是相同类型的数据才可以.猫和狗显然和人不是一种类型,想要记录的话,还是重新建立一个"宠物档案册"吧~

结语

当我们搞清楚什么是线性表后,在数据结构线性表篇我们还将一起学习线性表的抽象数据类型,线性表的顺序存储结构(顺序表的实现),线性表的链式存储结构(链表的实现)等相关知识.希望这些内容能对大家有所帮助,一起学习,一起进步!

今日新闻