顺序表（C 语言）

一、线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

二、顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表分为静态顺序表和动态顺序表，静态顺序表是数组大小固定，只能存储定量的数组，超出了就不能存储；动态顺序表使用一个指针管理动态数组，当数组不够存储时可以使用 realloc() 函数进行动态增容。

而一般情况下我们都是使用动态顺序表，因为静态顺序表大小固定，多了不够用，少了浪费空间。

1. 静态顺序表

这里这给出静态顺序表的大体框架，并不实现。

// 静态顺序表// 容量
#define CAPACITY 100// 数据类型
typedef int SSL_DataType;// 静态顺序表结构声明
typedef struct Static_SeqList
{SSL_DataType datas[CAPACITY];  // 数据size_t size;  // 当前数据个数
}SSeqList;// 操作// 初始化
void InitSSeqList(SSeqList* pssl);// 尾插
void SSeqListPushBack(SSeqList* pssl, SSL_DataType data);// 尾删
void SSeqListPopBack(SSeqList* pss1);// 头插
void SSeqListPushFront(SSeqList* pssl, SSL_DataType data);// 头删
void SSeqListPopFront(SSeqList* pssl, SSL_DataType data);// 查找
void SSeqListFind(SSeqList* pssl, SSL_DataType data);// 在 pos 位置插入
void SSeqListInsert(SSeqList* pssl, size_t pos, SSL_DataType data);// 删除 pos 位置的数据
void SSeqListErase(SSeqList* pssl, size_t pos, SSL_DataType data);// 打印
void SSeqListPrint(SSeqList* pssl);

如果需要使用静态顺序表，那么就在另一个 .c 文件中实现其操作功能，然后在主函数中调用即可。

2. 动态顺序表

相比于静态顺序表，动态顺序表增加了一个 capacity 成员表示容量，因为需要比较判断是否增容。还增加了几个操作功能，容量检查和销毁顺序表，销毁顺序表也就是释放动态内存。

2.1 动态顺序表的实现分析

（1）成员：动态申请数据 datas 的初始空间，当前数据的个数 size，容量的大小 capacity
（2）操作：
a. 初始化：申请数据空间，当前数据个数 size 归零，容量 capacity 设置为初始值
b. 检查容量：当执行插入操作的时候，需要检查当前顺序表是否需要增容
c. 头插：在表头插入数据
d. 头删：在表头删除数据
e. 尾插：在表尾插入数据
f. 尾删：在表尾删除数据
g. 查找：在表中查找指定数据，找到了返回下标，没找到返回 -1
h. 插入：在给定下标处插入数据，下标范围 0-size
i. 删除：在给定下标处删除数据，下标范围 0-size-1
j. 打印：打印顺序表的所有数据
k. 销毁：释放申请空间，size 和 capacity 归零

2.2 动态顺序表的实现

下面是顺序表的三个文件：

头文件：SeqList.h

// 动态顺序表// 数据类型
typedef int SL_DataType;// 初始容量
#define INIT_CAPACITY 2// 动态顺序表结构声明
typedef struct SeqList
{SL_DataType* datas;  // 数据size_t size;  // 当前数据个数size_t capacity;  // 当前容量
}SeqList;// 操作声明// 初始化
void SeqListInit(SeqList* psl);// 检查容量
void CheckCapacity(SeqList* psl);// 尾插
void SeqListPushBack(SeqList* psl, SL_DataType data);// 尾删
void SeqListPopBack(SeqList* psl);// 头插
void SeqListPushFront(SeqList* psl, SL_DataType data);// 头删
void SeqListPopFront(SeqList* psl);// 查找
int SeqListFind(SeqList* psl, SL_DataType data);// 在 pos 位置插入数据
void SeqListInsert(SeqList* psl, size_t pos, SL_DataType data);// 删除 pos 位置数据
void SeqListErase(SeqList* psl, size_t pos);// 打印顺序表
void SeqListPrint(SeqList* psl);// 销毁顺序表
void SeqListDestory(SeqList* psl);

操作实现文件：SeqList.c

// 头文件
#include "SeqList.h"
#include <assert.h>
#include <stdlib.h>// 操作定义// 初始化
void SeqListInit(SeqList* psl)
{// 检查空指针assert(psl);// 容量psl->capacity = INIT_CAPACITY;// 申请空间psl->datas = (SL_DataType*)malloc(sizeof(SL_DataType) * psl->capacity);// 判断是否申请成功if (NULL == psl->datas){perror("SeqListInit::malloc: ");return;}// 当前数据个数psl->size = 0;
}// 检查容量
void CheckCapacity(SeqList* psl)
{assert(psl);// 判断是否需要增容if (psl->size == psl->capacity){// 增容两倍SL_DataType* tmp = (SL_DataType*)realloc(psl->datas, sizeof(SL_DataType) * psl->capacity * 2);// 判断是否增容成功if (NULL == tmp){perror("CheckCapacity::realloc: ");return;}// 成功psl->datas = tmp;psl->capacity *= 2;tmp = NULL;}}// 尾插
void SeqListPushBack(SeqList* psl, SL_DataType data)
{assert(psl);// 检查增容CheckCapacity(psl);// 插入psl->datas[psl->size++] = data;
}// 尾删
void SeqListPopBack(SeqList* psl)
{assert(psl);// 检查当前表中是否有数据if (0 == psl->size){printf("There is no data!\n");return;}// 删除--psl->size;
}// 头插
void SeqListPushFront(SeqList* psl, SL_DataType data)
{assert(psl);// 判断增容CheckCapacity(psl);// 把所有元素往后挪动int i;for (i = (int)psl->size; i > 0; --i)psl->datas[i] = psl->datas[i - 1];// 插入psl->datas[0] = data;++psl->size;
}// 头删
void SeqListPopFront(SeqList* psl)
{assert(psl);// 检查当前表中是否有数据if (0 == psl->size){printf("There is no data!\n");return;}// 把后面 sz-1 个元素往前移int i;for (i = 1; i < psl->size; ++i)psl->datas[i - 1] = psl->datas[i];// 删除--psl->size;}// 查找
int SeqListFind(SeqList* psl, SL_DataType data)
{assert(psl);int i;for (i = 0; i < psl->size; ++i){// 找到了返回下标if (psl->datas[i] == data){return i;}}// 没找到返回 -1return -1;
}// 在 pos 位置插入数据
void SeqListInsert(SeqList* psl, size_t pos, SL_DataType data)
{assert(psl);// 判断下标是否合法if (pos<0 || pos > psl->size){printf("Illegal subscript!\n");return;}// 判断增容CheckCapacity(psl);// 把从该下标开始的元素都往后移一位int i;for (i = (int)psl->size; i > pos; --i){psl->datas[i] = psl->datas[i - 1];}// 插入psl->datas[pos] = data;++psl->size;
}// 删除 pos 位置数据
void SeqListErase(SeqList* psl, size_t pos)
{assert(psl);// 判断坐标是否合法if (pos < 0 || pos >= psl->size){printf("Illegal subscript!\n");return;}// 把从 pos+1 开始的元素都往前移int i;for (i = (int)pos + 1; i < psl->size; ++i)psl->datas[i - 1] = psl->datas[i];// 删除--psl->size;
}// 打印顺序表
void SeqListPrint(SeqList* psl)
{assert(psl);// 判断表中是否有数据if (0 == psl->size){printf("There is no data!\n");return;}// 打印int i;for (i = 0; i < psl->size; ++i)printf("%d ", psl->datas[i]);printf("\n");
}// 销毁顺序表
void SeqListDestory(SeqList* psl)
{assert(psl);// 释放空间free(psl->datas);psl->datas = NULL;psl->capacity = 0;psl->size = 0;
}

测试文件：test.c

// 头文件
#include "SeqList.h"// 头插头删测试
void test1(SeqList* PSL)
{// 头插加打印SeqListPushFront(PSL, 1);SeqListPrint(PSL);SeqListPushFront(PSL, 2);SeqListPrint(PSL);SeqListPushFront(PSL, 3);SeqListPrint(PSL);SeqListPushFront(PSL, 4);SeqListPrint(PSL);SeqListPushFront(PSL, 5);SeqListPrint(PSL);// 头删加打印SeqListPopFront(PSL);SeqListPrint(PSL);SeqListPopFront(PSL);SeqListPrint(PSL);SeqListPopFront(PSL);SeqListPrint(PSL);SeqListPopFront(PSL);SeqListPrint(PSL);SeqListPopFront(PSL);SeqListPrint(PSL);
}// 尾插尾删测试
void test2(SeqList* PSL)
{// 尾插加打印SeqListPushBack(PSL, 1);SeqListPrint(PSL);SeqListPushBack(PSL, 2);SeqListPrint(PSL);SeqListPushBack(PSL, 3);SeqListPrint(PSL);SeqListPushBack(PSL, 4);SeqListPrint(PSL);SeqListPushBack(PSL, 5);SeqListPrint(PSL);// 尾删加打印SeqListPopBack(PSL);SeqListPrint(PSL);SeqListPopBack(PSL);SeqListPrint(PSL);SeqListPopBack(PSL);SeqListPrint(PSL);SeqListPopBack(PSL);SeqListPrint(PSL);SeqListPopBack(PSL);SeqListPrint(PSL);
}// pos 位置插入删除测试
void test3(SeqList* PSL)
{// 在 pos 位置插入加打印SeqListInsert(PSL, 0, 1);SeqListPrint(PSL);SeqListInsert(PSL, 1, 9);SeqListPrint(PSL);SeqListInsert(PSL, 0, 8);SeqListPrint(PSL);SeqListInsert(PSL, 1, 3);SeqListPrint(PSL);SeqListInsert(PSL, 1, 7);SeqListPrint(PSL);SeqListInsert(PSL, 3, 6);SeqListPrint(PSL);// 在 pos 位置删除加打印SeqListErase(PSL, 0);SeqListPrint(PSL);SeqListErase(PSL, PSL->size - 1);SeqListPrint(PSL);SeqListErase(PSL, 1);SeqListPrint(PSL);SeqListErase(PSL, 1);SeqListPrint(PSL);SeqListErase(PSL, 0);SeqListPrint(PSL);SeqListErase(PSL, 0);SeqListPrint(PSL);
}// 查找功能测试
void test4(SeqList* PSL)
{// 插入数据SeqListPushBack(PSL, 1);SeqListPushBack(PSL, 3);SeqListPushBack(PSL, 5);SeqListPushBack(PSL, 7);SeqListPushBack(PSL, 9);SeqListPushBack(PSL, 10);SeqListPushBack(PSL, 8);SeqListPushBack(PSL, 6);SeqListPushBack(PSL, 4);SeqListPushBack(PSL, 2);// 打印SeqListPrint(PSL);// 查找int i;for (i = 1; i <= 10; ++i){printf("元素 %d 的下标为: %d\n", i, SeqListFind(PSL, i));}}int main()
{// 测试顺序表// 创建顺序表SeqList SL;// 初始化顺序表SeqListInit(&SL);// 头插头删测试printf("头插头删测试:\n");test1(&SL);// 尾插尾删测试printf("\n\n尾插尾删测试:\n");test2(&SL);// 在 pos 位置插入删除测试printf("\n\n在 pos 位置插入删除测试:\n");test3(&SL);// 查找功能测试printf("\n\n查找功能测试:\n");test4(&SL);// 销毁顺序表SeqListDestory(&SL);return 0;
}

该顺序表的每个功能作者都测试过，基本上没有问题。但是在调试的时候发现了动态内存的越界访问问题，经过调试发现，是扩容之后的容量 capacity 没有乘以 2。总得来说，顺序表的增删查改基本功能均已实现，如果大家发现了上述代码的错误，欢迎告知。

下面是在 x86 环境下，程序测试的结果：

2.3 动态顺序表存在的问题

通过对上述代码的学习发现动态顺序表存在以下问题：
（1）当进行头插、头删、插入和删除这四个操作的时候，需要挪动数组的数据，时间复杂度为 O(n)
（2）当容量不够的时候需要增容，每次增容后的容量是上一次的两倍，但是这样肯定会有空间的浪费。且增容需要申请新空间，拷贝数据，释放旧空间，这样会产生不小的时间消耗。

三、与数组有关的面试题

既然顺序表是在数组的基础上实现的，那么现在来看几道与数组有关的面试题。

1. 移除元素

题目描述： 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
（1）更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
（2）返回 k。

示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,,]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,,,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

题目OJ链接： 链接: link

题目解析： 这种在数组中原地删除数据的题目一般使用前后指针法，前指针 front，后指针 back。front 和 back 刚开始均指向数组首元素，只要 back 指向的元素的值不为 val，则 *front++ = *back++。要是后指针指向的元素的值为 val，则 front 不动，++back。重复上述步骤，直到 back 指向数组的尾后元素。最后返回 front 与数组首元素地址的差值。

图示过程：

可以发现最后要删除的数不是被后面的数覆盖了，就是跑到后面去了。而其他数都按照原来的顺序跑到前面去了。

代码如下：

// 移除元素
void remove_element(int* arr, int sz, int val)
{// 前后指针int* front = arr;int* back = arr;// 移除while (back < arr + sz){if (*back == val)++back;else*front++ = *back++;}// 返回return front - arr;
}

时间复杂度： O(n)
空间复杂度： O(1)

2. 删除有序数组中的重复项

题目描述： 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

（1）更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
（2）返回 k 。

示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 非严格递增 排列

题目OJ链接： link

题目思路： 本题也是使用前后指针法，前后指针刚开始都是指向数组首元素，若来指针指向的数组元素的值相同，那么 back 指针往后走，直到两个指针指向的值不同，然后先自增 front 指针，然后把 back 指向元素的值赋给 front 指向元素的值。重复上述步骤，直到 back 指向数组的尾后元素。最后返回 front 与数组首元素地址的差值。

图示过程：

代码如下：

// 删除有序数组中的重复项
int removeDuplicates(int* arr, int sz)
{// 前后指针int* front = arr;int* back = arr;// 开始删除while (back < arr + sz){if (*back == *front)++back;else*(++front) = *back;}// 返回return (int)(front - arr);
}

时间复杂度： O(n)
空间复杂度： O(1)