1. 线性表

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

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

2. 顺序表

2.1 概念及结构

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

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

顺序表一般可以分为：

静态顺序表：使用定长数组存储。
动态顺序表：使用动态开辟的数组存储。

// 顺序表的静态存储
#define N 100
typedef 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. 动态顺序表的实现

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

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

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

3.1 定义结构

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

指向动态开辟空间的data指针
记录当前有效数据个数的size变量
记录当前容量的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 检查增容

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

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

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

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

当顺序表空间足够，不进行任何操作，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 主动报错只有两种情况

free 释放的为野指针。

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);
}

【数据结构】动态顺序表(C语言实现)