数据结构线性表知识点

一、线性表的概念

1. 基本概念

线性表是一种由相同类型的数据元素构成的有限序列。所有的数据元素类型相同，而且线性表由有限个数据元素组成。线性表中的每个数据元素与其位置相关，即每个数据元素都有一个唯一的序号。通常，我们将逻辑序号和存储序号统一，假设从0开始，这样包含n个元素的线性表的元素序号i满足0≤i≤n-1。

2. 线性表的抽象数据类型描述

3. 线性表的顺序存储结构

（1）顺序存储结构——顺序表

顺序表是通过data数组来存放线性表元素的。其中，data数组的容量（即可以存放最多元素的数量）称为capacity。而线性表中实际数据元素的个数用size表示。

（2）线性表基本运算算法在顺序表中的实现

在动态分配顺序表的空间时，初始容量设置为initcapacity。当添加或插入元素时，可能需要扩大容量；删除元素时，可能需要减少容量。整体建立顺序表时，可以由含若干个元素的数组a的全部元素整体创建，即依次将a中的元素添加到data数组的末尾。当出现上溢出时，按照实际元素个数size的两倍扩大容量。

顺序表的基本运算算法包括：将元素e添加到线性表的末尾（Add(e)），求线性表的长度（getsize()），求线性表中序号为i的元素（GetElem(i)），设置线性表中序号为i的元素（SetElem(i, e)），求线性表中第一个值为e的元素的逻辑序号（GetNo(e)），在线性表中插入e作为第i个元素（Insert(i, e)），以及删除线性表中的第i个数据元素（Delete(i)）等。其中，扩容运算resize()在n次插入中仅调用一次，其平摊时间为O(1)，在算法时间分析中可忽略。

4. 顺序表的应用算法设计示例

（1）基于顺序表基本操作的算法设计

练习1：对于含有n个整数元素的顺序表L，设计一个算法将其所有元素逆置。例如，L=(1，2，3，4，5)被逆置后变为L=(5，4，3，2，1)。分析该算法的时间复杂度和空间复杂度。

练习2：假设有一个整数顺序表L，设计一个算法用于删除从序号i开始的k个元素。例如，L=（1，2，3，4，5），删除i=1开始的k=2个元素后L=（1，4，5）。

（2）基于整体建立顺序表的算法设计

练习3：对于含有n个整数元素的顺序表L，设计一个算法用于删除其中所有值为x的元素。例如，L=(1，2，1，5，1)，当x=1时，删除后L=(2，5)。分析该算法的时间复杂度和空间复杂度。

（3）有序顺序表的算法设计