**
** 线性表是具有n个相同类型元素的有序序列,线性表是最基本、最简单、也是最常用的一种数据结构。线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部。比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储,但是把最后一个数据元素的尾指针指向了首位结点)。
线性结构
常见的线性表有:数组,链表,栈,队列,哈希表
a1是首节点 an是尾节点 a1是a2的前驱 a2是a1的后继
前驱后继与直接前驱直接后继的区别
如用(a1,…,ai-1,ai,ai+1,…,an)表示一个顺序表,则表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素。当i=1,2,…,n-1时,ai有且仅有一个直接后继,当i=2,3,…,n时,ai有且仅有一个直接前驱 [1] 。
在线性表中,无论数据本身由多少种数据类型(每一种被称为一个“数据项”)组成,每一条数据被称为“数据元素”。
如果数据元素本身包含的数据项非常多,就可以称这个数据元素为一个“记录”,多条记录组成一个“文件”。
之前讲过,逻辑结构上相邻的数据在实际的物理存储中有两种形式:分散存储和集中存储。 考虑到这两种情况,线性表分为两种,分别解决两种情况下数据的存储问题: 数据元素在内存中集中存储,采用顺序表示结构,简称“顺序存储”; 数据元素在内存中分散存储,采用链式表示结构,简称“链式存储”。
上面这些都是有相同特征的“有序列”