数据结构线性表(一)

一、什么是线性表

1、基本概念

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

所有数据元素类型相同。

线性表是有限个数据元素构成的。

线性表中数据元素与位置相关，即每个数据元素有唯一的序号。

线性表中每个元素ai的唯一位置通过序号或者索引i表示，为了算法设计方便，将逻辑序号和存储序号统一，均假设从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)

扩容运算resize()在n次插入中仅仅调用一次，其平摊时间为O(1)，上述算法时间分析中可以忽略它。

在线性表中删除第i个数据元素Delete(i)

输出线性表所有元素display()

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）有序顺序表的算法设计

有序表是指按元素值或者某属性值递增或者递减排列的线性表，有序表是线性表的一个子集。

有序顺序表是有序表的顺序存储结构。

对于有序表可以利用其元素的有序性提高相关算法的效率，二路归并就是有序表的一种经典算法。

练习：有两个按元素值递增有序的整数顺序表A和B，设计一个算法将顺序表A和B的全部元素合并到一个递增有序顺序表C中。并给出算法的时间复杂度和空间复杂度。

二路归并：

算法中尽管有多个while循环语句，但恰好对顺序表A、B中每个元素均访问一次，所以时间复杂度为O(n+m) 。

算法中需要在临时顺序表C中添加n+m个元素，所以算法的空间复杂度也是O(n+m)。

二路归并中，若两个有序表的长度分别为n、m，算法的主要时间花费在元素比较上，那么比较次数是多少呢？

最好的情况下，整个归并中仅仅是较长表的第一个元素与较短表每个元素比较一次，此时元素比较次数为MIN(n，m)（为最少元素比较次数），如A=(1，2，3)，B=(4，5，6，7，8)，只需比较3次。

最坏的情况下，这n+m个元素均两两比较一次，比较次数为n+m-1（为最多元素比较次数），如A=(1，3，5，7)，B=(2，4，6)，需要比较6次。