数据结构-线性表.md

简介

线性表是对多种数据结构的一种统称。

定义

线性表

一个线性表是 n 个具有相同特性的数据元素的有限序列。

线性表的长度

线性表中的个数 n 定义为线性表的长度，n=0 时称为空表。

在非空表中每个数据元素都有一个确定的位置，如用 ai 表示数据元素，则i称为数据元素 ai 在线性表中的位序。

前驱与后继

线性表的相邻元素之间存在着序偶关系。

如用（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. 集合中必存在唯一的一个“第一元素”。
2. 集合中必存在唯一的一个“最后元素”。
3. 除最后一个元素之外，均有唯一的后继。
4. 除第一个元素之外，均有唯一的前驱。

思维导图