【2.1】线性表

一、线性表的概念

线性表简称表，是零个或多个元素的有穷序列，通常可 以表示成 k0，k1, …，kn-1(n ≥ 1)

• 表目:线性表中的元素(可包含多个数据项，记录)
• 索引(下标):i 称为表目 ki 的“索引”或“下标”
• 表的长度:线性表中所含元素的个数 n
• 空表:长度为零的线性表 ( n = 0 )

线性表特点:

• 操作灵活，其长度可以增长、缩短

二、线性结构

二元组𝐵 = （𝐾,𝑅） 𝐾 = {𝑎0,𝑎1,…,𝑎𝑛−1} 𝑅 = {𝑟}

• 有一个唯一的开始结点，它没有前驱，有一个唯一的直接后继

• 一个唯一的终止结点，它有一个唯一的直接前驱，而没有后继

• 其它的结点皆称为 内部结点，每一个内部结点都有且仅有一个唯一的直 接有前驱，也有一个唯一的直接后继

  < 𝑎𝑖, 𝑎𝑖+1 > 𝑎𝑖是𝑎𝑖+1的前驱，𝑎𝑖+1是𝑎𝑖的后继

• 前驱/后继关系r，具有 反对称性 和 传递性

特点：

• 均匀性:虽然不同线性表的数据元素可以是各种各样 的，但对于同一线性表的各数据元素必定具有相同的 数据类型和长度
• 有序性:各数据元素在线性表中都有自己的位置，且 数据元素之间的相对位置是线性的

按复杂程度划分：

• 简单的:线性表、栈、队列、散列表
• 高级的:广义表、多维数组、文件……

按访问方式划分

• 直接访问型 (direct access)
• 顺序访问型 (sequential access)
• 目录索引型 (directory access)

按操作划分(详见后)L

• 线性表
• 所有表目都是同一类型结点的线性表
• 不限制操作形式
• 根据存储的不同分为:顺序表，链表
• 栈 (LIFO, Last In First Out)
• 插入和删除操作都限制在表的同一端进行
• 队列 (FIFO, First In First Out)
• 插入操作在表的一端， 删除操作在另一端

三、线性表的逻辑结构

主要属性包括

• 线性表的长度
• 表头 (head)
• 表尾 (tail)
• 当前位置 (current position)

四、线性表分类

4.1 线性表分类(按存储)

线性表

• 所有表目都是同一类型结点的线性表
• 不限制操作形式
• 根据存储的不同分为:顺序表，链表

4.2 线性表分类(按操作)

• 线性表 – 不限制操作
• 栈 – 在同一端操作
• 队列 – 在两端操作

栈 (LIFO, Last In First Out) – 插入和删除操作都限制在表的同一端进行

队列 (FIFO, First In First Out) – 插入操作在表的一端， 删除操作在另一端

五、线性表的运算

• 建立线性表
• 清除线性表
• 插入一个新元素
• 删除某个元素
• 修改某个元素
• 排序
• 检索

线性表类模板：

六、讨论

• 线性表有哪些分类方式?
• 各种线性表名称中，哪些跟存储结构相关?哪些跟运算相关?

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾蛟