【数据结构入门】顺序表详解（增删查改）

顺序表的基本概念

动态顺序表的实现

初始化

插入

尾插法

头插法

指定位置之前插入

删除

尾删法

头删法

指定位置删除

查找

销毁

顺序表的基本概念

什么是顺序表？

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

简单来讲，顺序表的底层结构就是数组，只不过在数组的基础上，实现的增删改查等接口。

顺序表的分类：

静态顺序表
动态顺序表

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

typedef struct Seqlist {
SLdatatye arr[N];//定长数组
int size;//有效数据个数
}SL;

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

因此我们在日常主要使用动态顺序表；

动态顺序表：按需申请空间；

typedef struct Seqlist {
   SLdatatye* arr;//存储数据的底层结构
   int capacity;//记录顺序表空间大小
   int size;//记录顺序表当前有效的数据个数
}SL;

动态顺序表的实现

首先创建一个工程：

SeqList.h：定义顺序表的结构，顺序表要实现的接口/方法；
SeqList.c:具体实现顺序表定义的接口/方法；
test.c：测试顺序表；

初始化

SeqList.h:

void SLinit(SL* s);

SeqList.c:

void SLinit(SL* s)
{
s->arr = NULL;
s->size = s->capacity = 0;
}

插入

数据的插入有多种方法：

头插法；
尾插法；
指定位置插入；

尾插法

对于空间足够的情况我们选择直接插入即可；

如果空间不够，我们就需要扩容；

SeqList.h:

void SLinsertback(SL* s, SLdatatye x);

void SLcheakcapacity(SL* s);//扩容

SeqList.c:

void SLinsertback(SL* s, SLdatatye x)
{
   assert(s != NULL);
   //空间不够，扩容
   SLcheakcapacity(s);

   //空间足够
   s->arr[s->size++] = x;
}

void SLcheakcapacity(SL* s)
{
   if (s->size == s->capacity)
   {
       //三目表达式：
       int newcapacity = s->capacity == 0 ? 4 : 2 * s->capacity;
       SLdatatye* tmp = (SLdatatye*)realloc(s->arr, 2 * newcapacity * sizeof(SLdatatye));
       if (tmp == NULL)
       {
           perror("realloc fail!");
           exit(1);
       }
       //扩容成功
       s->arr = tmp;
       s->capacity = newcapacity;
   }
}

从图中我们可以看到当capacity ==size时说明空间已满，此时如若再添加数据就需要进行扩容，增大空间，这里使用的是realloc；因为在头插法，指定位置插入都需要扩容，为了方便，我们将扩容单独写成一个函数；

头插法

先将数据全部往后平移；
再在首位插入；

SeqList.h:

void SLinsertfront(SL* s, SLdatatye x);

SeqList.c:

void SLinsertfront(SL* s, SLdatatye x)
{
   assert(s != NULL);
   SLcheakcapacity(s);
   for (int i = s->size; i >= 0; i--)//平移
   {
       s->arr[i] = s->arr[i-1];
   }
   s->arr[0] = x;//插入
   s->size++;
}

指定位置之前插入

先平移，后插入，注意size要变化

SeqList.h:

void SLinsert(SL* s, int pos, SLdatatye x);

SeqList.c:

void SLinsert(SL* s, int pos, SLdatatye x)
{
   assert(s);
   SLcheakcapacity(s);
   for (int i = s->size; i >pos; i--)//平移
   {
       s->arr[i] = s->arr[i - 1];
   }
   s->arr[pos] = x;//插入
   s->size++;
}

删除

头删法；
尾删法；
指定位置删除；

尾删法

SeqList.h:

void SLdeleteback(SL* s);

SeqList.c:
void SLdeleteback(SL* s)
{
s->size--;
}

头删法

SeqList.h:

void SLdeletefront(SL* s);

SeqList.c:

void SLdeletefront(SL* s)
{
   for (int i = 0; i < s->size-1; i++)
   {
       s->arr[i] = s->arr[i + 1];
   }
   s->size--;
}

指定位置删除

SeqList.h:

void SLdelete(SL* s, int pos);

SeqList.c:

void SLdelete(SL* s, int pos)
{
   assert(pos < s->size);
   assert(s);
   for (int i = pos; i < s->size; i++)
   {
       s->arr[i] = s->arr[i + 1];
   }
   s->size--;
}

查找

插入本质就是变量；找到就返回其下标，未找到就返回-1

SeqList.h:

int SLfind(SL* s, SLdatatye x);

SeqList.c:

int SLfind(SL* s, SLdatatye x)
{
   assert(s);
   for (int i = 0; i < s->size; i++)
   {
       if (s->arr[i] == x)
           return i;
   }
   return -1;
}

销毁

SeqList.h:

void SLdestroy(SL* s);

SeqList.h:

void SLdestroy(SL* s)
{
   if(s->arr!=NULL)
   {
       free(s->arr);
       s->arr = NULL;
   }

   s->capacity = s->size = 0;
}