数据结构——顺序表（C语言）

1.线性表

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

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

2.顺序表

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

在这里，我将给大家讲动态顺序表是怎么实现的。

（1）.我先定义了一个结构体，因为顺序表是具有相同特性的数据元素的有限列表。所以我用SeqListDateType来typedef 了，这样我们如果是double 或者float这样的类型的话，我们就只用改变宏这里一处。

（2）.因为是动态的，所以我就用指针，size就代表了顺序表中有多少个元素，capacity代表了是有多少的空间。

#define SeqListDateType int
typedef struct SeqList
{
  SeqListDateType* arr;
  int size;
  int capacity;
}SeqList;

顺序表的初始化：

第一个函数就是度顺序表的初始化，这里我是直接把ps->arr置位了NULL，size和capacity一开始是0。

void SeqListInit(SeqList* ps)
{
  ps->arr = NULL;
  ps->size = ps->capacity = 0;
}

顺序表的扩容：

因为我们是实现动态的顺序表，所以我们要处理一下，当size和capacity相等的时候，有2种情况，一种情况：一开始为0的时候，第二种情况：当空间不够的时候

这里，我用三目来实现了，如果是一开始我就给了4个int大小的空间，如果是第二种情况的话我就用扩二倍的思想来处理.

void SeqListCheckCapacity(SeqList* ps)
{
  if (ps->size == ps->capacity)
  {
    int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    SeqListDateType* tmp = (SeqListDateType*)realloc(ps->arr, newcapacity*sizeof(SeqListDateType)*2);
    if (tmp == NULL)
    {
      perror("realloc fail\n");
      exit(-1);
    }
    ps->capacity = newcapacity;
    ps->arr = tmp;
  }
}

顺序表的尾插：

一开始，我们开辟了4个int大小的空间，所以size一开始是0，然后就插入，然后size++就可以实现了，不过在我们插入的时候我们要考虑扩容的问题，如果空间满了，是要扩容的。

void SeqListPushBack(SeqList* ps, int x)
{
  assert(ps);
  SeqListCheckCapacity(ps);
  ps->arr[ps->size] = x;
  ps->size++;
  //SeqListInsert(ps, ps->size,x);
}

顺序表的头插：

思路：可以用迭代的思路走，但我们想一想，如果是从前面迭代的话，就会形成对数据的覆盖，所以要从后面迭代走。

我定义了end指向了4的位置，然后4要到后面的位置去，然后end--，这样当我们迭代完，顺序表0的位置就空了出来，直接把数据插入进去就可以了。

void SeqListPushFront(SeqList* ps,int x)
{
  assert(ps);
  SeqListCheckCapacity(ps);
  int end = ps->size - 1;
  while (end >=0)
  {
    ps->arr[end + 1] = ps->arr[end];
    end--;
  }
  ps->arr[0] = x;
  ps->size++;
  //SeqListInsert(ps,0,x);
}

顺序表的尾删：

顺序表尾删更简单，直接让size--就可以实现了。因为，我们打印的数据就是size范围内的数据，size减了过后就没有这个数据了。

void SeqListPopBack(SeqList* ps)
{
  assert(ps);
  ps->size--;
  //SeqListErqse(ps, ps->size-1);
}

顺序表的头删：

思路：先定义一个begin来指向第一个位置，我们迭代让后面的数据覆盖掉前面的数据就可以了。最后size--就实现了顺序表的头删。

void SeqListPopFront(SeqList* ps)
{
  assert(ps);
  int begin = 0;
  while (begin < ps->size - 1)
  {
    ps->arr[begin] = ps->arr[begin+1];
    ++begin;
  }
  ps->size--;
  //SeqListErqse(ps, 0);
}

顺序表的最后处理：

我们直接free掉动态开辟的空间就可以了，然后把size和capacity置为0.

void SeqListDestory(SeqList* ps)
{
  free(ps->arr);
  ps->arr = NULL;
  ps->size = ps->capacity = 0;
}

我们想一个问题，如果是在面试中，给了我们10分钟来实现顺序表，如果这样处理时间是不是可能不够呢？？所以，我给大家带来另外2个函数，这样我们就可以复用这2个函数对顺序表的头插、尾插..就可以直接复用，大大节约了时间。话不多说，直接放码！！！

顺序表的指定位置插入：

思路：假设pos=2，我定义了end来指向最后一个元素，只需要将最后一个元素往后移动一位，然后end--，这样就迭代了起来，最终就可以把pos的位置空出来，然后在pos位置插入想要的元素。

void SeqListInsert(SeqList* ps, int pos, int x)
{
  assert(pos <= ps->size && pos>=0);
  SeqListCheckCapacity(ps);
  int end = ps->size - 1;
  while (end >= pos)
  {
    ps->arr[end+1] = ps->arr[end];
    end--;
  }
  ps->arr[pos] = x;
  ps->size++;
}

顺序表的指定位置删除：

思路：删除的话，其实也是一个覆盖的过程，将pos+1的位置覆盖掉pos的位置，然后迭代，临界位置就是size-1的时候，最后size--就实现了对指定位置的删除。

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

这样，就可以用这两个元素来复用了！

尾插：尾插其实就是对顺序表最后的位置插入元素（注意，在最后一个位置插入的时候size已经++了，所以是ps->size）

SeqListInsert(ps, ps->size,x);

头插：头插就是对0的位置插入元素

SeqListInsert(ps,0,x);

尾删：尾删也是和尾插一样的，对最后的位置删除

SeqListErase(ps, ps->size-1);

头删：头删是对0的位置开始删除

SeqListErase(ps, 0);