程序猿必修课之数据结构（三）线性表1
原文出自：http://www.jianshu.com/p/5980a6755ab2
线性表的定义
线性表(List)：零个或多个数据元素的有限序列。
首先它是一个序列。也就是说，元素之间是有顺序的，若存在多个元素，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。
其次，线性表强调是有限的。
线性表元素的个数 n (n >= 0) 定义为线性表的长度，当 n = 0 时，称为空表。
线性表的抽象数据类型
ADT 线性表(List)
Data
线性表的数据对象集合为{a1, a2, ……, an}，每个元素的类型均为DataType。其中，除第一个元素 a1 外，每一个元素有且只有一个直接前驱元素，除了最后一个元素 an 外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
InitList （*L）：初始化操作，建立一个空的线性表 L。
ListEmpty （L）：若线性表为空，返回 true，否则返回 false。
ClearList （*L）：将线性表清空。
GetElem（L, i, *e）：将线性表 L 中的第 i 个位置元素值返回给 e。
LocateElem （L, e）：在线性表 L 中查找与给定值 e 相等的元素，如果查找成功，返回该元素在表中序号；否则返回 0。
ListInsert (*L, i, e) ）：在线性表 L 中的第 i 个位置插入新元素 e。
ListDelete (*L, i, *e) ）：删除线性表 L 中第 i 个位置元素，并用 e 返回其值。
ListLength (L) ：返回线性表 L 的元素个数。
endADT
线性表的顺序存储结构
线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
线性表的顺序存储结构，是在内存中开辟一块连续的区域，然后把相同数据类型的数据元素依次存放在这块内存中。
线性表的顺序存储结构代码
# define MAXSIZE 20
typedef int ElemType; /* ElemType 类型根据实际情况而定，这里假设为 int */
typedef struct {
ElemType data [MAXSIZE];
int length;
}SqList;
顺序存储结构需要的三个属性：
- 存储空间的起始位置，也就是数组 data。
- 线性表的最大存储容量，也就是数组的长度 MaxSize。
- 线性表的当前长度，也就是 length。
数组长度与线性表长度区别
数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。
线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。
在任意时刻，线性表的长度应该小于等于数组的长度。
地址计算法
存储器中的每个存储单元都有自己的编号，这个编号称为地址。
由于每个数据元素，不管它是整型、实型还是字符型，它都是需要占用一定的存储单元空间的。假设占用的是 c 个存储单元，那么线性表中第 i + 1 个数据元素的存储位置和第 i 个数据元素的存储位置满足下列关系 (LOC 表示获取存储位置的函数)。
LOC(A(i+1)) = LOC(A(i)) + c
所以对于第 i 个数据元素 A(i) 在存储位置可以由 A(1) 推算得出：
LOC(A(i)) = LOC(A(1)) + (i - 1) * c
通过这个公式，我们可以发现，计算线性表中任意位置的地址所用的时间是相同的。那么我们对每个线性表位置的存入或者取出数据，对于计算机来说都是相等的时间，也就是一个常数，因此用时间复杂度的概念来说，它的存取时间性能为 O(1)。我们把具有这一性能的存储结构称为随机存取结构。
顺序存储结构的操作
顺序存储结构的操作主要包括：数据查找、插入、删除等。
数据查找
查找的实现方法非常简单，只要将线性表中的第 i 个位置元素返回就可以了。
代码实现如下：
ElemType GetElem (SqList L, int i) {
if (L.length ==0 || i < 1 || i > L.length)
// 抛出异常
return L.data[i - 1];
};
插入操作
插入算法的思路：
- 如果插入位置不合理，抛出异常
- 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量
- 从最后一个元素开始向前遍历到第 i 个位置，分别将它们都向后移动一个位置
- 将要插入的元素填入位置 i 处
- 表长加 1。
代码实现如下：
bool ListInsert (SqList *L, int i, ElemType e) {
/* 如果插入位置不正确 */
if (i < 1 || i > L->length + 1)
return false;
/* 如果顺序线性表已经满了 */
if (L->length >= MAXSIZE)
return false;
/* 如果插入位置不在表尾 */
if (i <= L->length) {
int k = L->length - 1;
for (k; k >= i - 1; k--)
L->data[k + 1] = L->data[k];
}
/* 将新元素插入 */
L->data[i - 1] = e;
L->length++;
return true;
};
删除操作
删除算法的思路：
- 如果删除位置不合理，抛出异常
- 取出删除元素
- 从删除位置开始遍历到最后一个元素位置，分别将它们向前移动一个位置
- 表长减 1 。
代码实现如下：
bool ListDelete (SqList *L, int i, ElemType *e) {
/* 线性表为空 */
if (L->length == 0)
return false;
/* 删除位置不正确 */
if (i < 1 || i > L->length)
return false;
*e = L->data[i - 1];
/* 如果删除位置不是最后一个 */
if (i < L->length) {
int k = i;
for (k; k < L->length; k++)
/* 将删除位置后继元素前移 */
L->data[k - 1] = L->data[k];
}
L->length--;
return true;
}
下面我们分析一下插入和删除操作的时间复杂度
如果元素要插入到最后一个位置，或者要删除最后一个元素，此时时间复杂度为 O(1)，这是最好的情况。
如果元素要插入到第 1 个位置或者删除第 1 个元素，此时时间复杂度为 O(n)。
平均情况，由于每个位置插入或者删除的可能性是相同的，所以平均移动次数和最中间的那个元素的移动次数是相等的，为 (n -1) / 2，经推导，可以得出复杂度为 O(n)。
线性表的顺序存储结构，在存储和读取数据时，不管是哪个位置，时间复杂度都是 O(1）;而插入或删除时，时间复杂度都是 O(n)。这说明，线性表比较适合元素个数变化小的情况，适合数据的存储与读取，不适合频繁插入删除操作。
线性表顺序存储结构的优缺点
优点：
- 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
- 可以快速地存取表中任一位置的元素
缺点：
- 插入和删除操作需要移动大量元素
- 当线性表长度变化较大时，难以确定存储空间的容量
- 造成存储空间的 “碎片”
