【数据结构】详解顺序表

引言

经过一段时间的学习，博主也是学到了数据结构和算法这块，那么在接下来的时间里，我也将继续分享我在数据结构这块的学习心得和重点内容。那么第一个我将分享的是动态顺序表的实现，这一块内容将对大家c语言动态内存管理有一定的要求，之前博主也有介绍，如有问题还请前往: 【c语言】详解动态内存管理

一、顺序表的介绍

当谈及顺序表结构式时，我们便会引入线性表的概念，如下：

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

我们今天介绍的顺序表就是以类似数组结构的形式存储的

二、顺序表的两种分类

1. 静态顺序表
   一般使用定长数组存储数据，如下这般申请静态顺序表：

//静态顺序表
typedef int SLDataType;
#define N 10
typedef struct SeqList
{
    SLDataType arr[N];//定长数组
    int size;//有效数据个数
}SList;

静态顺序表缺陷：空间给少了不够用，给多了造成空间浪费。

2. 动态顺序表
   为了解决静态顺序表的问题，便有了动态顺序表，一般如下定义：

//动态顺序表--按需申请空间
typedef int SLDataType;
typedef struct SeqList
{
    SLDataType* head;
    int size;//有效数据个数
    int capacity;//空间容量
}SL;

在初次动态申请内存空间时，我们便可用capacity记录空间容量，size记录已存的有效数字个数，用realloc()函数来动态开辟内存，用head来指向动态开辟的空间的起始地址，这样便可通过下表来访问顺序表元素。例如，我们想访问第三个元素：head[2]。

三、动态顺序表的一些常用接口

我们定义如下结构体，表示动态顺序表：

typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{
 SLDataType* a;
 int size; // 有效数据个数
 int capacity; // 空间容量
}SL;

下面各接口函数都是基于此动态顺序表。

3.1空间容量检测

每当我们插入数据时都要检测空间剩余容量，即ps->capacity == ps->size与否，不足便要增容，如果每次写插入数据函数时都写这一段代码那就太麻烦了，所以我们封装一个这样的函数。

在此函数中要先判读ps->capacity大小，如果为0，便要赋值为4；有值时，便翻倍。

还要一点要注意的是，realloc()开辟新空间时，如果原空间后面内存不够，便会释放此空间，在其他地方重新开辟，并拷贝原始数据，所以在这我们重新定义一个指针new_p。

//空间检测
void SLcapacity_check(SL* ps)
{
  assert(ps);
  if (ps->capacity == ps->size)
  {
      //判断新开辟的空间容量mewcapacity
    int newcapacity = (ps->capacity == 0) ? 4 : (ps->capacity) * 2;
    SLDataType* new_p = (SLDataType*)realloc(ps->p, sizeof(SLDataType) * newcapacity);
    //检测开辟成功与否
    if (new_p == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    //赋值新空间地址，空间容量
    ps->p = new_p;
    ps->capacity = newcapacity;
  }
}

3.2尾插数据

在检测空间后，便可直接插入数据，相对简单就不多介绍了。

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
  assert(ps);
  SLcapacity_check(ps);
  ps->p[ps->size] = x;
  ps->size++;
}

3.3头插数据

在检测剩余空间后，要实现头插，便要将原始数据都后移一位，需要注意的是，要从尾节点开始后移，然后再插到下标为0的位置。

//头插
void SLPushFront(SL* ps, SLDataType x)
{
  assert(ps);
  SLcapacity_check(ps);
  //原数据后移
  for (int i = ps->size; i > 0; i--)
    ps->p[i] = ps->p[i - 1];
  ps->p[0] = x;
  ps->size++;
}

3.4尾删数据

事实上尾删数据后，我们的有效数据个数就会减少一个，那么直接ps->size--，便可在逻辑上实现尾删。

//尾删
void SLPopBack(SL* ps)
{
  assert(ps->size > 0);
  ps->size--;

3.5头删数据

对于头删数据，其实和头插极其相似。头插是从后向前拷贝数据，头删则是从前向后拷贝数据，即将第i个拷贝到第i-1个的位置，最后再将ps->size--。如果有效数据已经为0了，那么在函数内部不会进行任何操作。

//头删
void SLPopFront(SL* ps)
{
  assert(ps);
  if (ps->size > 0)
  {
    for (int i = 0; i < ps->size - 1; i++)
    {
      ps->p[i] = ps->p[i + 1];
    }
    ps->p[ps->size - 1] = 0;
    ps->size--;
  }
}

3.6寻找某个数

通过遍历顺序表，便可实现此函数，另外只需要注意一点：找到返回下标，未找到返回-1，返回值类型为int。

此函数主要为下面要介绍的两个函数服务。

//顺序表查找--返回下标
int SListFind(SL* ps, SLDateType x)
{
  for (int i = 0; i < ps->size; ++i)
  {
    if (ps->a[i] == x)
    {
      return i;
    }
  }
  return -1;
}

3.7指定位置插入数据

在执行插入操作前就要判断，给定的位置是否超过有效数据个数。插入部分代码就是与头插类似的版本，只不过SListPushFront()函数是从下标ps->size-1到0的数据向后拷贝；而SListInsert()函数是从ps->size-1到pos的数据向后拷贝。

// 顺序表在pos位置插入x
void SListInsert(SL* ps, size_t pos, SLDateType x)
{
  assert(ps);
  assert(pos <= ps->size);//指定位置不能超过有效数据个数
  SLcapacity_check(ps);
    //此操作与头插相似，拷贝数据，再插入
  int end = ps->size ;
  while (end > pos)
  {
    ps->a[end] = ps->a[end - 1];
    --end;
  }
  ps->a[pos] = x;
  ps->size++;
}

3.8指定位置删除数据

与头删类似，从下标为pos+1的位置向前拷贝，最后ps->size--，其他就不多解释了。

// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos)
{
  assert(ps && pos < ps->size);
    //与头删相似，从下标为pos+1的位置向前拷贝
  int start = pos+1;
  while (start < ps->size)
  {
    ps->a[start-1] = ps->a[start];
    ++start;
  }
  ps->size--;
}

四、小结

通过上面对动态顺序表的实现的讲解后，我们不难发现其实动态顺序表也是有很多缺点的：

1. 当空间不够时需要增容，而增容是有代价的；
2. 为了避免频繁扩容，我本每次扩2倍，这样可能导致空间的浪费；

3. 顺序表要求从开始位置连续存储，那么我们在头部和中部位置插入/删除数据就需要挪动数据，这样的效率并不高

但除了一些缺点外，顺序表当然也是有优点的：

1. 顺序表支持随机访问（下标）；
2. cpu高速缓存命中率更高