【数据结构】手撕顺序表-阿里云开发者社区

前言

在我们很多时候都要对数据进行增删查改等操作，而这些操作又依赖于线性表。今天就让我们学习顺序表和链表是怎么对数据进行增删查改。

1.线性表

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

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

2.顺序表

2.1概念及结构

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

顺序表一般可以分为：

2.1.1静态顺序表：使用定长数组存储元素

2.1.2 动态顺序表：使用动态开辟的数组存储

2.2 接口实现

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

2.3动态顺序表的实现

2.3.1结构

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
  SLDataType* array;  // 指向动态开辟的数组
  size_t size ;       // 有效数据个数
  size_t capicity ;   // 容量空间的大小
}SeqList;

顺序表只是一种数据存储结构，这就意味任何类型的数据都应该可以按照顺序表的结构进行存储，所以为了使我们的顺序表更加具有普适性，结构体里arr指向的数组类型是我们重定义的SLDataType，这样当我们想创建其它类型的顺序表时只需要对typedef后面的类型进行需改即可；size是用来计数的，统计当前顺序表一共有多少个有效元素；capacity是用来表示当前顺序表的容量，当size==capacity时说明当前顺序表已经“装满了”，需要扩容。

2.3.2初始化

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

需要注意：形参是结构体类型的指针，千万不能是结构体类型的变量，因为如果只是单纯的进行值传递那么形参的改变不会影响实参，因此这里我们需要传递地址，形参就需要用一个指针来接受。

2.3.3销毁

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

为什么要销毁？根据上面说的顺序表本质上不就是一个结构体变量嘛，结构体变量和其他基本数据类型一样都是数据类型用来定义变量，我们平时在使用基本数据类型定义的变量时，用完之后也没有专门对其进行销毁，那为什么到了线性表这里就需要专门去销毁呢？不要忘了！！！我们这里是动态顺序表，arr是通过动态申请空间得到的，只要是动态申请的内存在使用结束的时候都需要进行释放，将空间使用权限归还给操作系统，否则就会导致内存泄漏。所以我们需要写一个销毁函数在顺序表使用结束的时候主动将其动态申请的空间释放。在释放前我们可以先对传过来的地址用assert进行断言检查，判断其是否为空，为空就无需进行释放。

2.3.4扩容

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

扩容时需要调用realloc函数进行扩容，在使用realloc函数的时候需要注意他的第一个参数指向待扩容的空间，第二个参数是待扩容的大小单位是字节，其次就是扩容的两种形式：原地扩容和异地扩容。关于realloc的具体用法忘了的小伙伴可以去看看我之前分享的一篇文章：【C语言进阶】动态内存管理

2.3.5尾插

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

尾插时需要先判断顺序表是否满了，满了要先进行扩容才能继续进行扩容。size表示有效元素个数，同时也是顺序表中最后一个元素后一个位置的下标。成功插入后要对有效数据个数size加一。这里因为扩容逻辑不仅在尾插中会用到，在头插和随即插入中也可能用上，因此可以把扩容逻辑单独写成一个函数，这是程序设计的一种思路，可以降低代码的的冗余。扩容函数将在下面展示。

2.3.6头插

在插入前，我们要先把数据向后挪，再将数据插入表中。在挪动过程中我们要注意增容问题，空间不足时，要及时增容。

void SLPushFront(SL* psl, SLDateType 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++;
}

2.3.7尾删

void SLPopBack(SL* psl)
{
  assert(psl);
  assert(psl->size > 0);
  psl->size--;
}

由于顺序表是用连续的物理空间来进行数据存储的，因此尾删数据只需要把有限数据个数减一就行，这样我们就无法访问到原链表中的最后一个数据，进而实现了顺序表的尾删，删掉后，顺序表中剩下的多余空间不能单独释放，在堆上动态申请的一块连续空间只能同时释放。就类似于你参加团购，购买时是一起购买的，退货时也不允许你一个人退货。

2.3.8头删

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

头删需要从第二个元素开始把后面的所有元素往前挪动一位。

2.3.9在pos位置插入

在插入前，我们要先判断pos位置是否有效。

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

2.3.10删除pos位置元素

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

2.3.11打印顺序表元素

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

3.动态顺序表完整源码

SeqList.h

typedef int SLDateType;
typedef struct SeqList
{
  SLDateType* a;
  int size;//有效数据
  int capacity;//空间容量
}SL;
void SLInit(SL* psl);//初始化
void SLDestroy(SL* psl);//销毁
void SLPrint(SL* psl);
void SLCheckCapacity(SL* psl);//检查容量
void SLPushBack(SL* psl, SLDateType x);//尾插
void SLPushFront(SL* psl, SLDateType x);//头插
void SLPopBack(SL* psl);//尾删
void SLPopFront(SL* psl);//头删
void SLInsert(SL* psl, int pos, SLDateType x);//在下标为pose的位置插入
void SLErase(SL* psl, int pos);//在下标为pose的位置删除

SeqList.c

void SLInit(SL* psl)
{
  assert(psl);
  psl->a = NULL;
  psl->size = 0;
  psl->capacity = 0;
}
void SLDestroy(SL* psl)
{
  assert(psl);
  if (psl->a != NULL)
  {
    free(psl->a);
    psl->a = NULL;
    psl->size = 0;
    psl->capacity = 0;
  }
}
void SLPrint(SL* psl)
{
  assert(psl);
  for (int i = 0; i < psl->size; i++)
  {
    printf("%d ", psl->a[i]);
  }
  printf("\n");
}
void SLCheckCapacity(SL* psl)
{
  assert(psl);
  if (psl->size == psl->capacity)
  {
    int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
    SLDateType* tmp = (SLDateType*)realloc(psl->a, sizeof(SLDateType) * newcapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
    }
    psl->a = tmp;
    psl->capacity = newcapacity;
  }
}
void SLPushBack(SL* psl, SLDateType x)
{
  assert(psl);
  SLCheckCapacity(psl);
  psl->a[psl->size] = x;
  psl->size++;
}
void SLPushFront(SL* psl, SLDateType 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++;
}
void SLPopBack(SL* psl)
{
  assert(psl);
  assert(psl->size > 0);
  psl->size--;
}
void SLPopFront(SL* psl)
{
  assert(psl);
  assert(psl->size > 0);
  int begin = 1;
  while (begin < psl->size)
  {
    psl->a[begin - 1] = psl->a[begin];
    begin++;
  }
  psl->size--;
}
void SLInsert(SL* psl, int pos, SLDateType x)
{
  assert(psl);
  assert(pos >= 0 && pos <= psl->size);
  SLCheckCapacity(psl);
  int end = psl->size - 1;
  while (end > pos)
  {
    psl->a[end + 1] = psl->a[end];
    end--;
  }
  psl->a[pos] = x;
  psl->size++;
}
void SLErase(SL* psl, int pos, SLDateType x)
{
  assert(psl);
  assert(pos >= 0 && pos < psl->size);
  int begin = pos + 1;
  while (begin < psl->size)
  {
    psl->a[begin - 1] = psl->a[begin];
    begin++;
  }
  psl->size--;
}

本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。你们的支持就是博主最大的动力。

【数据结构】手撕顺序表

前言