线性表的定义
线性结构的特点:
在数据元素的非空有限集中:
- 存在唯一的一个被称作"第一个"的数据元素;
- 存在唯一的一个被称做"最后一个"的数据元素;
- 除第一个之外,集合中的每个数据元素均只有一个前驱;
- 除最后一个之外,集合中每个数据元素均只有一个后继.
线性结构的数据元素之间的关系如下图:
线性表,栈,队列,串和数组都属于线性结构.而线性表是最基本也是最常用的一种线性结构.
线性表(List):零个或多个数据元素的有限序列.
序列,顾名思义,元素之间是有顺序的,就像上图中那样,八个小朋友都是按顺序排好的,第二个在第一个后面,第三个在第二个后面......
其次,线性表强调是有限的,即数据元素的个数是有限的.事实上,在计算机中处理的对象都是有限的,无限的数列,只存在于数学的概念中.
如果我们像高数那样定义线性表的概念,则:
若将线性表记为(
,...,
,
,
,...,
),
则表中
领先于
,
领先于
,
称
是
的直接前驱元素,
是
的直接后继元素.
当i=1,2,...,n-1时,
有且仅有一个直接后继,
当i=2,3,...,n时,
有且仅有一个直接前驱.
其对应关系如下图所示:
所以,将线性表元素的个数n(n>=0)定义为线性表的长度,当n=0时,称为空表.
在非空表中的每个数据元素都有一个确定的位置,如
是第一个数据元素,
是最后一个数据元素,
是第i个数据元素,称i为数据元素
在线性表中的位序.
生活中常见的线性表
我们生活中有很多东西都有线性表的身影,如一年中的星座列表:
班上同学的点名册,因为每个同学的信息是按顺序排的,因此虽然每个数据元素有很多数据项,但组合起来仍然是一个线性表:
还有我们天天都在用的手机通讯录,和点名册类似,同样是一种线性表:
还有一点要注意,如果我现在要将我的猫和张三家的狗也加入通讯录中,可行吗?
答案是不可以,因为根据线性表的定义,必须是相同类型的数据才可以.猫和狗显然和人不是一种类型,想要记录的话,还是重新建立一个"宠物档案册"吧~
结语
当我们搞清楚什么是线性表后,在数据结构线性表篇我们还将一起学习线性表的抽象数据类型,线性表的顺序存储结构(顺序表的实现),线性表的链式存储结构(链表的实现)等相关知识.希望这些内容能对大家有所帮助,一起学习,一起进步!
数据结构线性表篇思维导图:
