📖线性表

在了解线性表之前先让我们来了解一下什么是线性表。线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表i、栈、队列、字符串等。

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

📖顺序表

定义：

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

顺序表一般可分为以下两类：

• 静态顺序表：使用定长数组存储元素（缺陷：开少了不够用、开多了浪费）
• 动态顺序表：使用动态开辟的数组存储（按需申请）

📖动态顺序表

上面说动态顺序表就是动态开辟数组来存储嘛，那这里我们为什么不直接去开辟数组，而是要先定义一个结构体呢？因为一个顺序表它不只是简单的去动态申请一块空间就结束了，我们还需要在这个顺序表上执行一系列操作，比如说插入数据、删除数据、修改数据、查找数据等等。插入数据时如果当顺序表满了就不能再插了，因此我们需要知道顺序表中有效元素的个数以及顺序表的容量，当有效个数等于容量时我们就该对顺序表进行扩容，所以有效元素个数和容量是每一个顺序表都应该具备的属性，还记得我们之前学的嘛？当一个事物具有多个属性的时候，我们就可用结构体将事物的所有属性放在一起。这就是为什么在创建一个顺序表的时候需要先定义一个结构体，这个结构体就是用来表示一个顺序表的，它们的关系如下图所示：

🔖结构

#define INIT_CAPACITY 4
typedef int SLDataType;
//动态顺序表，按需申请
typedef struct SeqList
{
  SLDataType* arr;//使当前的顺序表具有普适性
  int size;     //有效数据个数
  int capacity; //空间容量
}SL;

顺序表只是一种数据存储结构，这就意味任何类型的数据都应该可以按照顺序表的结构进行存储，所以为了使我们的顺序表更加具有普适性，结构体里arr指向的数组类型是我们重定义的SLDataType，这样当我们想创建其它类型的顺序表时只需要对typedef后面的类型进行需改即可；size是用来计数的，统计当前顺序表一共有多少个有效元素；capacity是用来表示当前顺序表的容量，当size==capacity时说明当前顺序表已经“装满了”，需要扩容。

🔖初始化

void SLInit(SL* ps)
{
  assert(ps);
  ps->arr = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);//开一定大小的空间
  if (ps->arr == NULL)
  {
    perror("malloc");
    return;
  }
  ps->size = 0;
  ps->capacity = INIT_CAPACITY;
}

 需要注意：形参是结构体类型的指针，千万不能是结构体类型的变量，因为如果只是单纯的进行值传递那么形参的改变不会影响实参，因此这里我们需要传递地址，形参就需要用一个指针来接受。

🔖销毁

void SLDestory(SL* ps)
{
  assert(ps);
  free(ps->arr);
  ps->arr = NULL;
  ps->capacity = ps->size = 0;
}

为什么要销毁？根据上面说的顺序表本质上不就是一个结构体变量嘛，结构体变量和其他基本数据类型一样都是数据类型用来定义变量，我们平时在使用基本数据类型定义的变量时，用完之后也没有专门对其进行销毁，那为什么到了线性表这里就需要专门去销毁呢？不要忘了！！！我们这里是动态顺序表，arr是通过动态申请空间得到的，只要是动态申请的内存在使用结束的时候都需要进行释放，将空间使用权限归还给操作系统，否则就会导致内存泄漏。所以我们需要写一个销毁函数在顺序表使用结束的时候主动将其动态申请的空间释放。在释放前我们可以先对传过来的地址用assert进行断言检查，判断其是否为空，为空就无需进行释放。

🔖尾插

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
  assert(ps);
  SLCheckCapacity(ps);//进行容量检查
  //ps->a[ps->size] = x;
  //ps->size++;
  ps->arr[ps->size++] = x;
}

尾插时需要先判断顺序表是否满了，满了要先进行扩容才能继续进行扩容。size表示有效元素个数，同时也是顺序表中最后一个元素后一个位置的下标。成功插入后要对有效数据个数size加一。这里因为扩容逻辑不仅在尾插中会用到，在头插和随即插入中也可能用上，因此可以把扩容逻辑单独写成一个函数，这是程序设计的一种思路，可以降低代码的的冗余。扩容函数将在下面展示。

🔖扩容

//检查容量
void SLCheckCapacity(SL* ps)
{
  assert(ps);
  if (ps->size == ps->capacity)
  {
    SLDataType* tmp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * ps->capacity * 2);//一次扩大二倍比较合适，你也可以按照你的需求进行扩容
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    ps->arr = tmp;
    ps->capacity *= 2;
  }
}

扩容时需要调用realloc函数进行扩容，在使用realloc函数的时候需要注意他的第一个参数指向待扩容的空间，第二个参数是待扩容的大小单位是字节，其次就是扩容的两种形式：原地扩容和异地扩容。关于realloc的具体用法忘了的小伙伴可以去看看我之前分享的一篇文章：【C语言进阶】动态内存管理