线性表(2)顺序表

定义

顺序表是一种存储结构，指的是线性表中逻辑相邻的元素在物理内存上也相邻，其用一块连续的地址空间存放表中的数据元素。也就是说，对于表\(A(a_1, a_2, a_3, \dots, a_n)\)，设表中元素的大小为\(size\)，其物理地址如下：

顺序表的最大的特点就是支持随机访问，随机访问指的是，只要知道了表中第一个元素的位置以及表中元素的大小，就可以在\(O(1)\)的时间内查找到某一个位置的元素。如果我们想要查找第\(i\)个元素，只需要计算一次公式\(Loc(A)+(i-1)size\)，就可以找到相应的的元素。

实现

对于一个数据结构，我们肯定需要存放其数据元素的空间，对于线性表，我们在定义里说了，它是用一块连续的地址空间存放数据元素，这种情况下，我们必须保证有一块连续的空间用来存放我们的所有数据元素，那么如何保证其连续呢？我们知道在C语言里，数组就是这样的连续空间，这样我们就可以静态地分配一块固定大小的地址空间，存放所有的数据元素，而我们知道，数组的大小在其被声明的时候就已经确定，因此无可更改，也就是静态的。

代码如下：

const int MaxSize = 10;

typedef struct {
    ElemType data[MaxSize];
    int len;
}SqList;

typedef struct

在这里，我们用到了typedef这样的语法，相较于直接用struct xxx这样的定义，在声明这种类型的变量的时候，无需加上struct，也就是说，用typedef定义的结构体，申明变量的时候只需要SqList s;就可以，而不适用typedef的则需要struct SqList s;来申明。

静态分配看起来已经够用了，但是考虑到在某些情况下，需要我们精确地控制使用的内存或者我们事先分配的空间不够用，这就需要我们能够动态地分配空间。注意到C语言中的malloc()/free()函数就能够实现堆上空间的动态分配，只要我们适当使用这两个函数，就可以完成顺序表的动态分配。

代码如下：

typedef struct {
    ElemType *data;
    int MaxSize;
    int len;
}SqList;

我们在结构体里申明了一个指针，用这个指针代替了原来的数组，这样子，我们只需要将指针指向我们动态申请的空间的起始位置，就可以通过这个指针访问所要访问的元素了。而新加入的MaxSize数据项，则是记录表的最大长度，类比一下静态分配的MaxSize，我们动态分配改变的其实就是这个MaxSize。

我们在更新顺序表的长度的时候，先开辟一块更大的空间，然后将原来的数据拷贝到新的空间，再用free()回收原来的空间，就完成了一个顺序表表长的更新，代码如下：

//将表增长len
void IncreaseSize(SqList &L, int len) {
    ElemType *p = L.data;
    L.data = (ElemType *)malloc(sizeof(ElemType) * (L.MaxSize + len));
    for (int i = 0; i < L.MaxSize; ++i) {
    	L.data[i] = p[i];   
    }
    L.MaxSize += len;
    free(p);
}

这其实就相当于，我们有一个箱子，箱子里装着衣服，随着时间过去，箱子终于有一天放不下新衣服了，这时候我们就需要先买一个更大的箱子，把箱子里的衣服放进新的箱子，再处理掉就的箱子。

另外注意到，一开始我们的表中的指针并不是指向有效的地址的，这就需要一个初始化过程，避免我们解引用的时候访问了奇奇怪怪的地址：

void InitList(SqList &L, int InitSize) {
    L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize);
    L.len = 0;
    L.MaxSize = InitSize;
}

结构体的更新

假设我们要对一个结构体更新，如果这个结构体的数据项很少，当然很难出问题，但是如果结构体的数据项多了，我们很容易忘记更新某些需要更新的数据，所以最好的更新方法就是对着结构体中的数据项逐个检查，看是否需要更新，避免有遗漏。

操作

根据我们在线性表(1)中的讨论，线性表最基本的操作有增删改查。其中的增就代表了插入元素，对于顺序表，要插入一个元素到某个位置，需要分情况讨论。

插入

在插入后大小不超过表的最大长度的情况下：

• 如果是插入到某个已有元素的位置，我们需要移动该位置以及该位置之后的元素一个位置，空出来的位置留给新的元素。
• 如果是插入到表尾，只需要将表尾的位置给新元素就可以了，不需要改动其他元素的位置。
• 如果是插入到表尾之后的位置，这将造成新的表尾和旧的表尾之间有空隙，操作不合法。

其实第一种和第二种情况可以归约为同一种情况，也就是，将插入位置及其后面的元素向后移动，第二种情况下，后面没有元素，也就是移动0个元素。

根据上面的分析，代码如下：

void ListInsert(SqList &L, int i, ElemType e) {
    for (int idx = L.len - 1; idx >= i; --idx) {
        L.data[idx + 1] = L.data[idx];
    }
    L.data[i] = e;
}

注意到，这里并没有考虑到操作不合法的情况，对于操作不合法的情况，也分开考虑：

• 插入位置超过表尾
• 插入后大小超过表最大大小

这里只需要用if语句对传入的参数进行特判就行了，代码如下：

bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 0 || i > L.len)
    	return false;
    if (L.len >= L.MaxSize)
        return false;
    for (int idx = L.len - 1; idx >= i; --idx) {
        L.data[idx + 1] = L.data[idx];
    }
    L.data[i] = e;
    L.len++;
    return true;
}

这样我们就得到了完整的插入操作。接下来要考虑的就是删除操作。

关于插入操作的复杂度，分析如下：

• 对于最好的情况，新插入的元素在表尾，不用移动任何元素，其复杂度是\(O(1)\)。
• 对于最坏情况，需要把所有的元素都移动一遍，其复杂度是\(O(n)\)。
• 对于平均情况，假设元素插入的位置是均匀随机分布的，也就是，新元素插入某一个位置的概率是\(p=\frac{1}{n + 1}\)，这个情况下，需要移动的平均次数就是\(\sum_{i = 0}^n\frac{i}{n+1}\)，是一个简单的等差数列求和，求和的结果是一次的，因此复杂度是\(O(n)\).

删除

删除是插入的逆过程，在代码上的体现也是如此，对于删除后的位置，会造成空隙，需要把删除位置后面的元素提前。而合法的删除操作只需要保证被删除的位置小于表长就行了。代码如下：

bool ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 0 || i >= L.len)
        return false;
    e = L.data[i];
    for (int idx = i; i < L.len - 1; ++i) {
        L.data[idx] = L.data[idx + 1];
    }
    L.len--;
    return true;
}

这里大体上和插入操作是很相似的，但是也有几处不同：

• 参数e用的是引用，这是为了把被删除的元素传给调用者
• 删除操作的元素移动是从前往后遍历

关于删除操作的时间复杂度，分析如下：

• 对于最好的情况，删除的是表尾元素，不需要移动其他元素，复杂度是\(O(1)\)。
• 对于最坏情况，需要移动剩下所有元素，复杂度是\(O(n)\)。
• 对于平均情况，分析过程与插入操作类似，复杂度是\(O(n)\)。

注意每次删除和插入操作以后都要对长度进行更新，我自己写博客的过程也差点忘记写

另外要注意的，按照王道课程上的说法，顺序表的表项从1开始编号，数组下标从0开始编号，我这里按照我的习惯写了，顺序表表项也从0开始编号

查找

查找有按位查找和按值查找两种，我们说过，顺序表的最大特性就是支持随机访问，这是很好的性质，这使得按位查找的实现变得非常简单。

ElemType GetElem(SqList L, int i) {
    return L.data[i];
}

在这一段代码中，由于随机访问的特性，我们直接按下标取值返回即可。但是对于按值查找，则复杂一点：

int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.len; i++) {
        if (L.data[i] == e)
            return i;
    }
    return -1;
}

在上面的代码中，需要遍历表中的元素，知道找到某一个和给定元素相等的元素，返回其下标即可，而如果遍历完了表都没找到相应的元素，则需要返回-1表示查找失败。

关于两种查找方式的时间复杂度：

按位查找只做了一次操作，复杂度是\(O(1)\)的。

对于按值查找有：

• 最好情况下，第一个元素即使所查找的元素，时间复杂度是\(O(1)\)。
• 最坏情况下，所查找的元素在表的最后，时间复杂度是\(O(n)\)。
• 平均情况下，假设所查找的元素所在的位置是等概率的，按照类似于插入操作的分析可得，时间复杂度是\(O(n)\).