作者主页：

2. 顺序表

2.1 概念及结构

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

注：顺序表本质上就是数组，但是在数组的基础上，它还要求数据是连续存储，不能跳跃间隔。

顺序表一般可以分为：

  1. 静态顺序表：使用定长数组存储。
  2. 动态顺序表：使用动态开辟的数组存储。
// 顺序表的静态存储#define N 100typedef int SLDataType;// 让数据存储多种类型typedef struct SeqList{    SLDataType a[N]; // 定长数组    int size; // 有效数据个数}SeqList;// 顺序表的动态存储typedef struct SeqList{    SLDataType* array; // 指向动态开辟的数组    int size ; // 表示数组中存储了多少个数据    int capicity ; // 数组实际能存数据的空间容量是多大}SeqList

注：

  • 静态顺序表使用#define定义长度，让大小修改起来更方便。
  • 为存储多种类型的数据，将数据类型typedef重命名为SLDataType，这样更加直观。当存储类型想改变时，直接更改数据类型即可。
  • 顺序表的类型很繁琐，可以用typedef重命名为SL，更加简洁。

两种顺序表的对比：

静态顺序表的最大的缺陷就是空间问题，它只适用于确定知道要存多少数据的场景。静态顺序表的特点是如果顺序表满了，就不让插入元素。静态顺序表的缺点也很直观：空间开辟多了，浪费空间。空间开辟少了，空间不足。到底给多大的空间？这个很难确定。

所以现实中静态顺序表很少使用，我们基本都是使用动态顺序表，根据需要动态的分配空间大小。下面我们使用C语言实现动态顺序表。

3. 动态顺序表的实现

我们实现一个动态顺序表，分为三部分：

  1. SeqList.h：头文件，结构、常量的定义，接口函数的声明…
  2. test.c：用于顺序表功能的测试
  3. SeqList.c：接口函数的实现

接下来我们的功能主要在SeqList.c中实现~

3.1 定义结构

相比较于静态顺序表，动态顺序表的结构由三个成员组成：

  1. 指向动态开辟空间的data指针
  2. 记录当前有效数据个数的size变量
  3. 记录当前容量的capacity变量
typedef struct SeqList{SLDataType* a;int sz;// 表示数组中存储了多少个数据int capacity;// 数组实际能存数据的空间容量是多大}SL;

我们比静态顺序表多了一个capacity成员。我们用这个成员记录当前顺序表的最大容量，当有效数据个数size和capacity相等时。说明当前顺序表空间已满，需要进行扩容。

3.2 接口函数总览

我们实现动态顺序表，就要实现对应的功能，例如增删查改等等…

这些功能我们会封装成函数，而当我们调用时，就会对接到对应函数，所以我们称这些函数为接口函数。

动态顺序表的实现需要如下接口：

void SeqListInit(SL* ps);// 初始化void SeqListCheckCapacity(SL* ps);// 检查增容void SeqListPushBack(SL* ps, SLDataType x);// 尾插void SeqListPopBack(SL* ps);// 尾删void SeqListPushFront(SL* ps, SLDataType x);// 头插void SeqListPopFront(SL* ps);// 头删void SeqListPrint(SL* ps);// 打印void SeqListDestory(SL* ps);// 销毁int SeqListFind(SL* ps, SLDataType x);// 查找void SeqListInsert(SL* ps, int pos, SLDataType x);// 指定下标位置插入void SeqListErase(SL* ps, int pos);// 指定下标位置删除void SeqListModify(SL* ps, int pos, int x);// 修改

这里需要提一下，为什么我函数接口的名称起的这么繁杂：

这其实是C++中STL的命名风格，STL库中，也有数据结构的相关函数。为了以后学习STL更加轻松。所以提前适应起来，方便以后学习。

3.3 初始化

顺序表在进行操作之前，需要先将其内容进行初始化，防止之后操作时出错。

void SeqListInit(SL* ps);

在实现这个接口之前，我们思考一下，参数可不可以为结构体？比如这样:

void SeqListInit(SL ps){ps.a = NULL;ps.sz = ps.capacity = 0;}

这时绝对不行的！要知道实参在传参时，会形成一份临时拷贝，叫做形参。当我们在函数中对形参的内容进行修改时，不会影响到实参，所以，不可行！

想要正确的初始化结构体，我们需要传sl的地址，通过指针对结构体内容进行修改：

void SeqListInit(SL* ps){assert(ps);ps->a = NULL;// 置空ps->sz = ps->capacity = 0;// 初始大小和容量设定为0}

3.4 检查增容

当顺序表需要插入数据时，可能会遇到三种情况：

  1. 整个顺序表没有空间。
  2. 空间不够，需要扩容。
  3. 空间足够，直接插入数据。

如果顺序表空间足够，那么不需要扩容，通过相关操作插入数据；如果空间不足或者根本没有空间，那么就得扩容。

当顺序表没有空间时，我们开辟四个空间；当顺序表空间不足，我们将当前空间扩大为两倍(扩两倍是为了防止扩容过度，或扩小了频繁扩容，消耗过大)。

当顺序表空间足够，不进行任何操作，if语句判断后，直接返回。

void SeqListCheckCapacity(SL* ps){assert(ps);// 顺序表没有空间or顺序表空间不足if (ps->sz == ps->capacity){// 没扩容，扩四个整形；空间不足，扩两倍int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;// realloc在起始地址为空指针时，和malloc一样效果SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));if (tmp == NULL){printf("realloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}}

3.5 尾插

在顺序表尾部插入数据：

void SeqListPushBack(SL* ps, SLDataType x);

在插入数据前，需要检查空间情况，所以要先调用SeqListCheckCapacity函数，对异常状况进行操作。

void SeqListPushBack(SL* ps, SLDataType x){assert(ps);SeqListCheckCapacity(ps);// 检查增容ps->a[ps->sz] = x;// 在尾部插入ps->sz++;}

3.6 尾删

在顺序表尾部插入数据：

void SeqListPopBack(SL* ps);

要实现尾删，那么我们只需要让sz--即可，因为sz标识了顺序表存了多少个有效数据。直接减少sz，那么之后的元素想操作也没办法了。

但是请注意，当顺序表没有元素，也就是sz为0时，不可删除。

为什么这么说，举个例子：

假如顺序表已有五个数据，我尾删六个数据，那么这时，我的顺序表sz = -1。这时候调用打印的接口，由于 sz = -1 并不会进行打印，所以不会出错。

如果我继续尾插数据，这时就会出现问题，我们就会访问到-1下标，也就是会在-1下标插入数据，这就越界访问了，进行了越界写。这时程序仍然不会报错。

但是当我们销毁顺序表时，程序会奔溃。因为程序在平时是几乎不对内存进行检查的，当销毁时，会对空间进行检查是否越界。

这也是为什么数组越界总在 free 处报错的原因。

所以我们需要谨记：free 主动报错只有两种情况

  1. free 释放的为野指针。
  2. free 释放的内存不是动态开辟的内存，或者释放的空间不完整。
    如果这两个都没有错误，那一定是越界访问，但是 free 不一定报错。
void SeqListPopBack(SL* ps){assert(ps);// 温柔处理//if (ps->sz > 0)// 不做出反应//{////ps->a[ps->sz - 1] = 0 ;// 不需要，sz标识顺序表的元素个数//ps->sz--;//} // 暴力处理assert(ps->sz > 0);// 直接终止程序，报错ps->sz--;}

3.7 头插

在顺序表头部插入数据：

void SeqListPushFront(SL* ps, SLDataType x);

要实现这一功能，需要保证原来的数据不能被覆盖。因此，我们将数据从后往前依次后挪，使用一个end下标来实现。

但是这里也要考虑增容的问题，否则会越界访问，在销毁顺序表时，程序会奔溃。

void SeqListPushFront(SL* ps, SLDataType x){assert(ps);    SeqListCheckCapacity(ps);// 检查增容    // 挪动数据    int end = ps->sz - 1;while (end >= 0)// 一直挪到0下标{ps->a[end + 1] = ps->a[end];end--;}ps->a[0] = x;ps->sz++;}

3.8 头删

从顺序表头部删除数据：

void SeqListPopFront(SL* ps);

要实现头删，那么我们可以给定一个begin下标，让数据从前往后依次前挪，保证原来的数据不被覆盖。

void SeqListPopFront(SL* ps){assert(ps);assert(ps->sz > 0);// 暴力处理，sz为0时，不能头删// 挪动数据int begin = 1;while (begin <= ps->sz - 1){ps->a[begin - 1] = ps->a[begin];begin++;}    // memmove(ps->a, ps->a + 1, (ps->sz - 1) * sizeof(SLDataType));    // 这样也可以，将1下标开始的元素，向前移动sz-1个单位    // 但是并不推荐，还是自己动手实现比较好ps->sz--;}

3.9 查找

查找一个元素在顺序表中的位置，返回下标：

int SeqListFind(SL* ps, SLDataType x);

这个就非常简单了，使用循环遍历顺序表，找到数据返回对应下标，找不到数据返回-1。

int SeqListFind(SL* ps, SLDataType x){assert(ps);// 找到了就返回元素出现的第一个位置for (int i = 0; i < ps->sz; i++){if (ps->a[i] == x){return i;}}return -1;}

3.10 指定下标位置插入

在指定pos下标处插入元素：

void SeqListInsert(SL* ps, int pos, SLDataType x);

要实现这一功能，我们依然需要一个end下标，数据从后往前依次后挪，直到pos下标移动完毕。另外，别忘了检查容量。

void SeqListInsert(SL* ps, int pos, SLDataType x){assert(ps);// 温柔处理//if (pos > ps->sz || pos < 0)//{//printf("pos invaild\n");//return;//}// 暴力处理// 断言表达式为真，相安无事// 为假，直接报错// 这两个表达式只要有一个不满足条件，便报错assert(pos >= 0 && pos <= ps->sz);// 包含头插和尾插SeqListCheckCapacity(ps);// 检查增容int end = ps->sz - 1;// 从后往前依次向后挪while (end >= pos){ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->sz++;}

该功能其实也可以实现头插和尾插，所以我们可以在头插和尾插中复用该功能：

// 头插void SeqListPushFront(SL* ps, SLDataType x){SeqListInsert(ps, 0, x);}// 尾插void SeqListPushBack(SL* ps, SLDataType x){SeqListInsert(ps, ps->sz, x);}

3.11 指定下标位置删除

在指定pos下标处删除元素：

void SeqListErase(SL* ps, int pos);

要实现这一功能，我们需要一个begin下标，数据从前往后依次前挪，直到sz-1下标移动完毕。

同样的，该接口也可复用于头删和尾删：

// 头删void SeqListPopFront(SL* ps){SeqListErase(ps, 0);}// 尾删void SeqListPopBack(SL* ps){SeqListErase(ps, ps->sz - 1);}

3.12 修改

顺序表指定pos下标进行修改：

void SeqListModify(SL* ps, int pos, int x);

要实现这个功能非常简单，只需要判断修改位置是否合法后，直接修改即可。

void SeqListModify(SL* ps, int pos, int x){assert(ps);assert(pos >= 0 || pos <= ps->sz - 1);ps->a[pos] = x;}

3.13 打印

在每次操作后，可以打印出顺序表，观察操作情况：

void SeqListPrint(SL* ps);// 打印

void SeqListPrint(SL* ps){assert(ps);for (int i = 0; i < ps->sz; i++){printf("%d ", ps->a[i]);}}

3.14 销毁

当操作执行完毕后，需要销毁顺序表：

void SeqListDestory(SL* ps);

销毁顺序表，只需要把动态开辟的空间释放，指针置空，其他变量置0。

void SeqListDestory(SL* ps){assert(ps);free(ps->a);ps->a = NULL;ps->sz = ps->capacity = 0;}

4. 完整代码

SeqList.h

#pragma once#include #include #include #include #define N 1000typedef int SLDataType;// 动态顺序表typedef struct SeqList{SLDataType* a;int sz;// 表示数组中存储了多少个数据int capacity;// 数组实际能存数据的空间容量是多大}SL;/* * 为什么使用这种命名风格？  * 为了对应C++ STL中的命名风格 * 方便后续学习STL */// 接口函数// 接口，就是和别人对接的void SeqListInit(SL* ps);// 初始化void SeqListCheckCapacity(SL* ps);// 检查增容void SeqListPushBack(SL* ps, SLDataType x);// 尾插void SeqListPopBack(SL* ps);// 尾删void SeqListPushFront(SL* ps, SLDataType x);// 头插void SeqListPopFront(SL* ps);// 头删void SeqListPrint(SL* ps);// 打印void SeqListDestory(SL* ps);// 销毁// ...// 找到了返回x位置下标，没有没到返回-1int SeqListFind(SL* ps, SLDataType x);// 查找void SeqListInsert(SL* ps, int pos, SLDataType x);// 指定下标位置插入void SeqListErase(SL* ps, int pos);// 删除pos位置的数据void SeqListModify(SL* ps, int pos, int x);// 修改pos位置的数据

SeqList.c

#define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h"// 初始化void SeqListInit(SL* ps){assert(ps);ps->a = NULL;ps->sz = ps->capacity = 0;}// 检查增容void SeqListCheckCapacity(SL* ps){assert(ps);// 顺序表没有空间or顺序表空间不足if (ps->sz == ps->capacity){// 没扩容，扩四个整形；空间不足，扩两倍int newcapacity = ps->capacity == 0 " />