顺序表

本质上是数组，但是在数组的基础上，还要求数据是从头开始连续存储的，不能跳跃间隔。

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

顺序表分为静态顺序表和动态顺序表两种

静态顺序表

使用定长数组存储元素

#define N 100
typedef int SLDateType;
//静态顺序表
typedef struct SeqList
{
  SLDateType a[N];
  int size;  //表示数组中存储了多少个数据
}SL;

静态顺序表有一个缺点：

如果满了就不让插，并且难以确定长度，N小了不够用，N大了浪费

所以我们通常不使用静态顺序表，限制太多，我们使用动态顺序表

动态顺序表

使用动态开辟的数组存储

typedef int SLDateType;
//动态顺序表
typedef struct SeqList
{
  SLDateType* a;
  int size; //表示数组中存储了多少个数据
  int capacity;  //数组实际能存数据空间容量是多大
}SL;

这里有一个问题：不管是静态顺序表还是动态顺序表，为什么都要定义成结构体呢？

以动态顺序表为例，size和capacity是必须定义的，如果不设计成结构体的形式，在使用时，就要定义三个变量：SLDateType* a，int size,int capacity，在后面的每个函数中都需要传这三个参数，十分不方便，如果把这三个变量定义成一个结构体，那么在接口函数中就传一个结构体就可以了

接口函数的实现

如果在主函数里定义了一个结构体变量，想要通过函数改变这个顺序表，就需要传结构体指针，所以在下面的函数中，我们传的都是结构体指针

这里我们要思考一个问题：我们在函数中传的参数是结构体的指针，而这个结构体指针一定不会是空的，如果这个指针为空就表示出问题了

所以在每个函数的开始都要用assert断言一下所传的指针是否为空

初始化函数

void SLInit(SL* ps)
{
  assert(ps);
  SLDataType* new = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
  if (new == NULL)
  {
  perror("malloc fail");
  return;
  }
  ps->a = new;
  ps->size = 0;
  ps->capacity = INIT_CAPACITY;
}

在初始化函数中，我们可以先开辟一部分空间，所以使用malloc语句，这个动态开辟的空间大小为INIT_CAPACITY，INIT_CAPACITY是我们在前面用#define定义的标识符

将开辟的空间赋给ps->a，此时因为顺序表中没有数据,ps->size为0，ps->capacity为INIT_CAPACITY

销毁函数

因为结构体中的a指向的空间是动态开辟出来的，我们必须对这块空间进行销毁操作，否则会发生内存泄漏

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

ps->a指向的空间是动态开辟出来的，所以要free(ps->a)，并且要把ps->a这个指针赋为NULL，而size和capacity的值自然而然就是0了

打印函数

这个函数是将顺序表中的值遍历打印出来，没什么好说的

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

增容函数

因为在前面初始化函数中已经开辟了4个空间，所以在使用其他插入函数时，不知道此时的空间是否是满的，所以我们需要检查空间是否为满，如果满了就需要再开辟空间

判断空间满的条件就是p s->size==capacity

如果空间已满，就需要使用realloc函数进行扩容，这里我们每次扩容都扩原空间长度的二倍

这里每次扩容二倍，势必会有一定的空间浪费

例如当前容量为100，再插入就会扩容到200容量，如果我只插入10个数据，那么最后就有90个空间被浪费。

这也是顺序表的一大缺陷

void CheckCapacity(SL* ps)
{
  assert(ps);
  if (ps->size == ps->capacity)
  {
  SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);
  if (tmp == NULL)
  {
    perror("realloc");
    return;
  }
  ps->a = tmp;
  ps->capacity = ps->capacity * 2;
  }
}

尾插函数

这是一个插入函数，所以在插入前需要调用CheckCapacity函数判断是否空间已满

尾插就是在最后插入，也就是下标为size的位置

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

头插函数

这也是一个插入函数，所以在插入前需要调用CheckCapacity函数

因为是头插，所以要把所有元素以从后向前的顺序向后挪动一位

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

尾删函数

尾删，如果表中没有元素就无法删除，所以要判断一下顺序表是否为空，如果size==0就表示顺序表为空，这里我使用assert断言，顺便与ps是否为空一起断言assert(ps && ps->size)

尾删，其实就是把size减一， size减一后最后一个元素就访问不到了，也就达到了尾删的效果，所以没必要去真正得将最后一个元素删除

void SLPopBack(SL* ps)
{
  assert(ps && ps->size);
  ps->size--;
}

头删函数

头删，也是需要判断一下顺序表是否为空

然后从第二个元素开始，把每个元素都向前挪动一位，将第一个元素进行覆盖，也就达到的头删的效果

void SLPopFront(SL* ps)
{
  assert(ps && ps->size);
  int begin = 1;
  while (begin < ps->size)
  {
  ps->a[begin - 1] = ps->a[begin];
  begin++;
  }
  ps->size--;
}

查找函数

查找目标值元素，如果找到返回下标值，如果没有找到则返回-1

int SLFind(SL* ps, SLDataType x)
{
  assert(ps);
  for (int i = 0; i < ps->size; i++)
  {
  if (ps->a[i] == x)
  {
    return i;
  }
  }
  return -1;
}

插入函数

在下标pos处进行插入操作

因为是插入函数，仍需要调用CheckCapacity函数判满

同时还需要判断pos的值，pos应该大于等于0，小于等于size，否则就出问题了

然后以从后向前的顺序，将pos后面位置的元素(包括pos位置的元素)向后挪动，然后再将新的值放到pos位置处

void SLInsert(SL* ps, int pos, SLDataType x)
{
  assert(ps);
  assert(pos >= 0 && pos <= ps->size);
  CheckCapacity(ps);
  int end = ps->size - 1;
  while (end >= pos)
  {
  ps->a[end + 1] = ps->a[end];
  end--;
  }
  ps->a[pos] = x;
  ps->size++;
}

我们可以使用这个函数去事项头插和尾插的操作

SLInsert(ps,0,x);//用SLInsert实现头插
SLInsert(ps,ps->size,x);//用SLInsert实现尾插

1

2

删除函数

这是一个删除函数，就需要判断顺序表是否为空

仍然需要判断pos的值是否合适

删除的操作就是将pos位置后面的元素都向前挪动一位，达到删除的效果

void SLEraze(SL* ps, int pos)
{
  assert(ps&&ps->size);
  assert(pos >= 0 && pos < ps->size);
  int begin = pos + 1;
  while (begin < ps->size)
  {
  ps->a[begin - 1] = ps->a[begin];
  begin++;
  }
  ps->size--;
}

同样，我们也可以使用这个函数实现头删和尾删函数

SLEraze(ps,0);//用SLEraze实现头删
SLEraze(ps,ps->size-1);//用SLEraze实现尾删

1

2

顺序表的优缺点

优点：支持随机访问，可以通过下标访问

缺点：

空间不够需要增容，增容是要付出代价的，会造成空间的浪费

顺序表在头部和中部进行插入和删除都要挪动数据，时间复杂度为O(N)，比较浪费时间，效率不高

如果想解决这些问题，我们可以使用链表