【数据结构】顺序表和链表1-阿里云开发者社区

线性表

数据的逻辑结构分为线性结构和非线性结构，这里的线性结构就是我们所说的线性表(linear list)，那么线性表的定义是什么呢？

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

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

一.线性表的数组结构——顺序表

顺序表我们可以理解成一个结构体的数组，它在内存中的存储的物理地址是连续的，存储数据时依次存储。一般可分为静态顺序表（使用定长数组）和动态顺序表（使用动态开辟数组）。

1.静态顺序表结构

//静态顺序表
typedef int SLDataType;
#define N 10//容量
typedef struct SeqListStatic
{
  SLDataType data[N];//保存数据
  size_t size;//存入的数据个数
}SListS;

2.动态顺序表结构

//动态顺序表
typedef struct SeqList
{
  SLDataType* a;//指向动态开辟的的数组
  size_t size;//顺序表内存放数据的个数
  size_t capacity; //顺序表容量
}SeqList;

3.接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。下面实现的接口大多数都是要对结构进行修改，所以我们传参的时候，都传结构体指针

（1）初始化

初始状态时，表内没有数据，我们把动态开辟的数组类型a置空，此时容量与数据个数都为0。

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

（2）销毁

有初始化就会有销毁，顺序表的空间是动态开辟来的，那么不用的时候我们要释放这些空间，，首先将空间free，然后将指针置空，最后将容量与数据个数置为0。

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

（3）打印

为了便于我们观察顺序表内存放的内容，我们实现一个打印接口，将顺序表内的内容打印出来。由于顺序表内存放书数据的形式是数组，因此我们定义一个遍历的变量i，表示数组下标，该表内共存放size个数据。

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

（4）插入数据

插入数据的时候，会有一个风险，当容量不够时，直接插入会导致越界，因此，在插入数据之前，应该先检查顺序表容量，如果不够，我们应该动态增容

void SLCheckCapacity(SeqList* ps)
{
  if (ps->capacity == ps->size)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//判断表内容量是否为空
    SLDataType* tmp = (SLDataType*)realloc(ps->a, 
              newCapacity * sizeof(SLDataType));//增加容量
    if (tmp == NULL)
    {
      perror("realloc fail:");
      return;
    }
    ps->a = tmp;
    ps->capacity = newCapacity;
  }
}

我们检查capacity与size是否相等，由于capacity只能大于或者等于size，所以当size==capacity的时候，就证明顺序表已经满了，我们需要增容了。增容的大小可以随意，但是二倍是最合适的，增容过多会导致空间浪费，过少会导致增容次数变多，使效率下降。但是在初始化的时候，我们将capacity内的值置为0，所以直接*2显然是不合适的，因此，需要加一个判断，这里我们使用三目操作符" ? :"，如果capacity为0，那么首先开辟4个元素大小的空间，否则将空间扩大到原来的二倍。

1.尾插

首先使用assert判断指针的有效性，然后检查容量，不够则扩容，然后将数据放在size下标的位置，然后size自增1。

void SeqListPushBack(SeqList* ps, SLDataType x)
{
  assert(ps);
  SLCheckCapacity(ps);
  ps->a[ps->size] = x;
  ps->size++;
}

2.头插

尾插的时候，是在数据的最后面插入，因此不需要挪动数据，但是头插我们需要将前面的所有数组向后挪动一位，然后在最开始的位置插入一个数据。挪动数据的方式也是有讲究的，对于当前这种情况，我们应该让数据从后往前挪动，否则其他数据会被覆盖，导致数据丢失。

void SeqListPushFront(SeqList* ps, SLDataType x)
{
  assert(ps);
  SLCheckCapacity(ps);
  int end = ps->size - 1;
  while (end >= 0)//挪动数据
  {
    ps->a[end + 1] = ps->a[end];
    end--;
  }
  ps->a[0] = x;
  ps->size++;
}

3.在任意位置插入

在任意位置插入时，我们不仅要考虑传入的指针ps是否有效，对于传入的位置pos也是需要判断是否合法的，pos只能在有数据的位置或者是最后一个数据的下一个位置，所以pos <= ps->size；要在顺序表内随机的地方插入数据，那么就要把该位置之后的所有数据向后挪动一位，挪动完成之后，在pos位置存入数据。

void SeqListInsert(SeqList* ps, size_t pos, SLDataType x)
{
  assert(ps);
  assert(pos <= ps->size);
  SLCheckCapacity(ps);
  size_t end = ps->size;
  while (end > pos)//挪动数据
  {
    ps->a[end] = ps->a[end - 1];
    end--;
  }
  ps->a[pos] = x;
  ps->size++;
}

（5）删除数据

1.尾删

尾删数据的时候，会导致有位置被空出来，这时候，我们要考虑的问题就是，是否要缩容，首先结论是不需要。缩容是有代价的，会使效率变低，并且以后要插入数据的时候，还需要重新扩容，现在的硬件技术发达，对于空间的需求没有那么紧张，因此，综合考虑我们不进行缩容操作。由于我们访问顺序表内元素的方式是通过数组下标，即size，所以直接对size自减就可以啦。

void SeqListPopBack(SeqList* ps)
{
  assert(ps);
  if (ps->size > 0)
    ps->size--;
  else
    return;
}

2.头删

在顺序表的头的位置删除数据，需要保持结构不变，所以需要将后面的数据向前挪动，由于第一个数据是需要被删除的，不需要保留，所以从前向后挪动就行，当数据挪动完成，将size自减，即可完成头删操作。

void SeqListPopFront(SeqList* ps)
{
  assert(ps);
  assert(ps->size > 0);
  int begin = 0;
  while (begin < ps->size - 1)//挪动数据
  {
    ps->a[begin] = ps->a[begin + 1];
    begin++;
  }
  ps->size--;
}

3.在任意位置删除

在任意位置删除时，我们不仅要考虑传入的指针ps是否有效，对于传入的位置pos也是需要判断是否合法的，pos只能在有数据的位置，所以pos < ps->size；要在顺序表内随机的地方删除数据，那么就要把该位置之后的所有数据向前挪动一位，挪动完成之后，size自减。

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

注：对于增删数据，我们实现的6个接口，其实是可以复用的，对于插入数据，我们使用SeqListInsert函数，传入pos为0的时候就是头插，传入pos为ps->size的时候就是尾插，同样的对于删除数据，使用SeqListErase，传入pos为0就是头删，为ps->size-1就是尾删。

（6）查找数据

查找数据，首先要检验传入指针的有效性，然后检查表内是否存在数据，如果传入空表，继续执行查找操作是不合适的，然后我们要遍历顺序表，并判断每个元素存放的值是否与我们要查找的值相同。找到了就返回下标位置，否则就返回-1。

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

（7）修改数据

增删查改是所有数据结构需要实现的接口，但是对于修改数据这个接口，它和查找数据是类似的，这里就不进行过多赘述。

【数据结构】顺序表和链表1

线性表