动态顺序表的详解（上）

顺序表的详细介绍

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

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

顺序表是一种使用数组实现的线性表结构，相邻元素在数组中连续存储。在 C 语言中，可以使用数组和指针来实现顺序表。通常情况下，我们会在代码中定义结构体来实现顺序表，其中包括以下信息：

存储数据的数组

当前顺序表中元素的数量

顺序表的最大容量

而顺序表有静态顺序表和动态顺序表，其中静态顺序表是使用定长数组存储元素的。动态顺序表使用动态开辟的数组存储。

动态顺序表的实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

结构体的定义

typedef int SLDataType;
typedef struct SeqList
{
  SLDataType* a;//存储元素的指针
  int size;//记录有效数据
  int capacity;//记录空间容量
}SL;

在这里将int重定义为SLDataType的原因是这样我们需要改变存储元素的类型仅改一个int就可以了，十分的方便。

顺序表的初始化

首先顺序表已经创建好了，那么开始用之前也要初始化一下，直接看代码。

void SLInit(SL* psl)
{
  assert(psl);
  psl->a=NULL;
  psl->size=0;
  psl->capacity=0;
}

首先在使用之前，有效数据个数当然是0个，那么存放元素所指向的指针也就是空指针了，空间容量也自然是0个了，在这里我们每个函数都用assert来断言一下，保证传入指针非空。

顺序表的销毁

有初始化就会有销毁，在程序结束时我们需要释放掉动态开辟的数组，并将一切都赋值为0，那么我们直接看代码。

void SLDestroy(SL* psl)
{
  assert(psl);
  if(psl->a!=NULL)
  {
    free(psl->a);
    psl->a=NULL;
    psl->size=0;
    psl->capacity=0;
  }
}

销毁的过程，首先要先判断传入指针是否为空，之后通过传入指针psl找到a判断该指针是否为空指针，不为空指针说明有元素存储，那么就需要释放掉这块动态开辟的空间，并将其赋值为空指针，最后将有效数据和空间容量赋值为0即可。

顺序表的扩容

接下来我们需要对顺序表进行头部插入元素或者尾部插入元素或者是任意位置差入元素，但如果顺序表的容量不够，就无法插入，所以我们对顺序表的扩容单独封装一个函数，对其进行调用即可。

void SLCheckCapacity(SL* psl)
{
  assert(psl);
  if(psl->size==psl->capacity)
  {
    int newcapacity=psl->capacity==0?4:psl->capacity*2;
    SLDataType* tmp=(SLDataType*)realloc(psl->a,sizeof(SLDataType)*newcapacity);
    if(tmp==NULL)
    {
      perror("realloc fail");
      return;
    }
    psl->a=tmp;
    psl->capacity=newcapacity;
}

首先，我们依然先来断言保证传入指针非空，之后查看通过传入指针psl找到的有效数据个数是否等于空间容量，如果相等则说明需要进行扩容，那么我们首先第一次一定是要进行扩容的，因为我们并没有给他开辟空间，所以用三目运算符来敲定如果通过psl指针找到的空间容量capacity等于0，则赋值为4个空间大小，之后在扩容很明显不是0，就扩容为上一次capacity的两倍（倍数根据实际情况选定）。做完这些事情我们只是把空间容量改了，真正能够存储元素的空间还没有开辟，所以接下来，我们定义一个临时变量tmp来接受动态开辟的空间，为什么不直接通过psl指针找到的a，因为如果我们在某一次扩容出现问题，直接赋给psl所指向的a，那么会导致之前psl所指向的a的元素数据丢失，造成不必要的麻烦，为了检查tmp是否正确开辟，我们用一个if语句来提醒，如果if语句没有生效就说明成功开辟，那么我们再把临时变量tmp赋值给通过psl所找到的a指针即可，最后扩容成功，也要newcapacity赋值给capacity即可。

顺序表的尾插

我们已经实现了顺序表的扩容，那么就可以来插入元素了，直接看代码。

void SLPushBack(SL* psl,SLDataType x)
{
  assert(psl);
  SLCheckCapacity(&psl);
  psl->a[psl->size]=x;
  psl->size++;
}

首先依然是先来断言保证传入指针非空，之后通过扩容函数判断是否需要扩容，之后将x值赋给通过psl找到的a的第psl->size个下标赋给这个位置的a，也就是最后一个位置。最后有效数据个数psl->size++即可。

顺序表的头插

实现了尾插之后我们来看一下实现头插，也是直接看代码。

void SLPushFront(SL* psl,SLDataType x)
{
  assert(psl);
  SLCheckCapacity(&psl);
  int end=psl->size-1;
  while(end>=0)
  {
    psl->a[end+1]=psl->a[end];
    end--;
  }
  psl->a[0]=x;
  psl->size++;
}

首先，我们实现数据头插，就需要将所有数据向后移动一位，从而达到首地址无元素的情况，所以我们先定义一个end变量为有效数据个数-1，之后通过while循环倒着将所有的元素向后移动一位，end–即可。循环结束后首地址就没有元素存放，这时我们将，x存放到psl指向a的首地址即可，最后size++。

顺序表的打印

为了防止我们插入元素无法显示出来，所以我们，先封装一个打印函数，能够将顺序表给打印出来。

void SLPrint(SL* psl)
{
  assert(psl);
  for(int i=0;i<psl->size;i++)
  {
    printf("%d ",psl->a[i]);
  }
  printf("\n");
}

这个函数实现十分的简单就不再过多赘述。