数据结构之顺序表的增删查改

别丢了你的勇敢

前言：

自今日起，我们正式越过C语言的大山，走向了数据结构的深山，现如今摆在我们面前的第一个坎就是顺序表，我们需要了解顺序表的定义，并且知道，如何对其进行增删查改，之后我们需要在此处基础上写出一份通讯录代码，ok，顺序表，启动！

1.什么是顺序表

1.1线性表

线性表（
linear list
）是n个具有相同特性的数据元素的有限序列。线性表是?种在实际中?泛使

?的数据结构，常?的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的?条直线。但是在物理结构上并不?定是连续的，

线性表在物理上存储时，通常以数组和链式结构的形式存储。

线性表指的是具有部分相同特性的?类数据结构的集合

1.2顺序表

顺序表是一种线性表的数据结构，它是由一组具有相同特性的数据元素按照一定的顺序排列而成的。顺序表的底层结构是数组，对数组的封装，实现了常?的增删改查等接口。顺序表可以使用数组来实现，也可以使用动态数组来实现。

顺序表分为静态顺序表和动态顺序表

静态顺序表是使用固定长度的数组来存储元素，数组的长度在创建时就确定了，无法改变。静态顺序表的优点是访问元素的时间复杂度为O(1)，缺点是插入和删除元素的时间复杂度较高。

图片来自比特就业课官网链接：https://www.bitejiuyeke.com

动态顺序表是使用可以动态开辟的数组来存储元素，数组的长度可以根据需要进行动态调整。动态顺序表的优点是可以灵活地插入和删除元素，缺点是访问元素的时间复杂度为O(1)。

顺序表是一种常见的数据结构，它在实际中被广泛使用，常见的应用场景包括数组、字符串等。

图片来自比特就业课官网链接：https://www.bitejiuyeke.com

动态顺序表和静态顺序表的使用是极其相似的，只是静态的顺序表建立在栈区，动态顺序表通过动态内存分配建立于堆区，由于动态涉及了动态内存分配，难度会稍稍高一些，所以我们今天的增删查改直接是以动态顺序表为对象，如果你能明白了这个，那静态顺序表也是同样的原理，也是可以写出来的。

2、动态顺序表的实现

2.1头文件

?? ??我先把头文件列出来，让各位先知道我们要实现的内容有什么

#
define
INIT_CAPACITY 4

typedef
int
SLDataType;

//
动态顺序表
--
按需申请

typedef struct
SeqList

{

SLDataType* a;

int
size;
//
有效数据个数

int
capacity;
//
空间容量

}SL;

//初始化顺序表

void
SLInit
(SL* ps);

//
销毁顺序表

void
SLDestroy
(SL* ps);

//
打印顺序表内容

void
SLPrint
(SL* ps);

//
扩容

void
SLCheckCapacity
(SL* ps);

//尾
部插?
数据

void
SLPushBack
(SL* ps, SLDataType x);

//尾
部删除
数据

void
SLPopBack
(SL* ps);

//
头部插?
数据

void
SLPushFront
(SL* ps, SLDataType x);

//
头部删除
数据

void
SLPopFront
(SL* ps);

//
指定位置插?
数据

void
SLInsert
(SL* ps,
int
pos, SLDataType x);

//
指定位置
删除数据

void SLDelete(SL* ps, int pos);

//
指定位置修改
数据

void SLModify(SL* ps, int pos,SLDataType x);

//
指定位置查找
数据

void SLSearch(SL* ps, int pos, SLDataType x);

2.2具体分析

ok，然后咱们，从上到下，挨个分析

??2.2.1

#define INIT_CAPACITY 4

这是一个宏定义，也是我们初始化默认通讯录的初始容量，即四个单位空间

??2.2.2

typedef int SLDataType;

这是用typedef给int换了个名字，这时候肯定有人会问了，为啥不直接用int，

?? 原因如下：

我们的顺序表是对数组的封装，但我们不能确实是什么类型的数组，如果我直接用int，那后面代码里也都是int，可假如我后来想给这个数组换成char类型呢，那我就要把所有int都改为char，于是乎我们直接用typedef创建一个类型名，之后代码也都用这个类型名，这样我之后想修改就只需要把

typedef int SLDataType改为typedef char SLDataType就ok了

这点在我们之后写通讯录时会体现出来

?? 2.2.3

typedef struct
SeqList

{

SLDataType* a;

int
size;
//
有效数据个数

int
capacity;
//
空间容量

}SL;

这是一个结构体，SLDataType*是顺序表中存储的元素类型，size是当前顺序表的存储数据数量，

capacity是顺序表的存储数据数量最大值。

?? 2.2.4

void
SLInit
(SL* ps);

这是对顺序表的初始化，我们传一个顺序表变量进去，该函数对其进行初始化，具体如下

给ps->a开辟了4个单位空间

将通讯录目前数据数量设置为0

容量设置为4

void SLInit(SL* ps)
{
       ps->a = (SLDataType*)malloc(CAPACITY * sizeof(SLDataType));
       ps->size = 0;
       ps->capacity = 4;
}

??2.2.5

void
SLDestroy
(SL* ps);

有初始化就有销毁，当我们要退出程序时要对顺序表的内容进行销毁，这时候有人要问了：程序退出不是会自动销毁吗，为什么还要再写一个函数呢？

?答：我们使用了动态内存开辟，有开辟就要有释放，当你不用它时就释放它是一个好的代码习惯，不然如果一直想着靠结束代码时释放空间以后当你写项目时就容易忘记及时释放空间导致内存泄漏。

?具体如下：

把之前的空间释放掉

把通讯录目前的数据数量设置为0

把通讯录容量设置为0

void SLDestroy(SL* ps)

{

   free(ps->a);

   ps->a = NULL;

   ps->size = 0;

   ps->capacity = 0;

｝

?? 2.2.6

void
SLPrint
(SL* ps);

这个是打印顺序表的信息，直接遍历数组挨个打印就可以

循环控制条件依靠顺序表中的ps->size就可以

void SLPrint(SL* ps)

{

for (int i = 0; i < ps->size; i++)

printf("%d ", ps->a[i]);

}

?? 2.2.7

void
SLCheckCapacity
(SL* ps);

要知道我们给顺序表设置的初始容量只有4个单位，在你不断输入数据的情况下，他很快就会满，于是我们就需要设置一个函数用来给顺序表扩容

直接调用realloc函数就可以

这里我们的扩容方式是直接将容量扩大到现在容量的2倍

??????
为什么不是扩大一个固定的数呢？??????

假如我们每次扩2个或3个，那很容易就会不够，扩容很频繁，导致性能消耗，如果一次扩1000个，2000个又很容易空间浪费，但如果我们以倍数扩容，随着空间越来越大每次增加的空间也会越来越大，这样扩容就不会很频繁，浪费空间也不会很多，我们通常是采用2倍扩容或1.5倍扩容，至于为什么是这俩数字就涉及到数学原理了，我能力有限，无法作答。（去找你数分的朋友吧）

void SLCheckCapacity(SL* ps)

{

   SLDataType* p = (SLDataType*)realloc(ps->a, 2 * ps->capacity * sizeof(SLDataType));

   if (p == NULL)

   {

       perror("realloc fail");

       exit(1);

   }

   ps->a = p;

   ps->capacity *= 2;

}

??这里有个小知识点别忘了，realloc会自动释放之前的空间，所以不用free了

?? 2.2.8

void SLPushBack(SL* ps, SLDataType x);

??这个是尾插

在增加之前判断一下顺序表是不是满了，如果满了就调用扩容函数
再来一个尾插，也就是在数组最后面加入元素
之后直接在末尾加上该元素即可

void SLPushBack(SL* ps, SLDataType x)

{

   if (ps->size + 1 > ps->capacity)

       SLCheckCapacity(ps);

   ps->a[ps->size] = x;

   (ps->size)++;

}

?? 2.2.9

void
SLPopBack
(SL* ps);

??
这个是尾删

尾删之前要判断一下顺序表是不是空的，
如果是就打印提示信息，若不是就把最后一个元素设置其值为0，
然后把顺序表的当前数据数量减一

void SLPopBack(SL* ps)

{

   if (ps->size - 1 < 0)

   {

       printf("顺序表空了，无法删除
");

       //perror("SLPopFront Fail");

       return ;

   }

   ps->a[ps->size - 1]=0;

   (ps->size)--;

}

??2.2.10

void
SLPushFront
(SL* ps, SLDataType x);

??这个是头插，比尾插麻烦一些，

第一步还是检验顺序表是不是满了
第二步我们要通过循环把所有元素集体向后移动一个单位，然后在空出来的第一个位置插入我们要插的值。
记得ps->size++

void SLPushFront(SL* ps, SLDataType a)

{

   if (ps->size + 1 > ps->capacity)

       SLCheckCapacity(ps);

   for (int i = 1; i <= ps->size; i++)

   {

       ps->a[i] = ps->a[i - 1];

   }

   (ps->size)++;

   ps->a[0] = a;

}

?? 2.2.11

void
SLPopFront
(SL* ps);

??
这个是头删

第一步检验顺序表是不是为空
第二步通过循环把元素集体向前移动一个单位，从而覆盖掉第一个元素
第三步ps->size--

void SLPopFront(SL* ps)

{

   if (ps->size - 1 < 0)

       perror("SLPopFront Fail");

   for (int i = 0; i < ps->size - 1; i++)

   {

       ps->a[i] = ps->a[i + 1];

   }

   ps->a[ps->size - 1] = 0;

   (ps->size)--;

}

??2.2.12

void
SLInsert
(SL* ps,
int
pos, SLDataType x);

??
指定位置之前插?数据

第一步检查是否需要扩容
第二步通过循环让下标pos及pos之后的元素集体后移一个单位，
第三步把数据放入下标为pos的地方

void SLInsert(SL* ps, int pos, SLDataType x)

{

   if (ps->size + 1 < ps->capacity)

       SLCheckCapacity(ps);

   for (int i = ps->size; i > pos; i--)

       ps->a[i] = ps->a[i - 1];

   ps->a[pos] = x;

ps->size++;

}

??2.2.13

void SLDelete(SL* ps, int pos);

??
指定位置删除数据

第一步检查顺序表是否为空
第二步通过循环把下标pos之后的元素向前移动一个单位，从而覆盖掉pos对位空间的值
第三步ps->size--

void SLDelete(SL* ps, int pos)

{

   if (ps->size - 1 < 0)

   {

       printf("顺序表空了
");

       //perror("SLPopFront Fail");

       return;

   }

   for (int i = pos; i < ps->size - 1; i++)

       ps->a[i] = ps->a[i + 1];

   ps->size--;

}

?? 2.2.14

void SLModify(SL* ps, int pos,SLDataType x);

??这个是修改数据：

先判断下标是否有效

若有效则修改数据

void SLModify(SL* ps, int pos,SLDataType x)

{

   if (pos >= ps->size)

       printf("要修改的元素不存在
");

   else

       ps->a[pos] = x;

}

?? 2.2.15

void SLSearch(SL* ps, int pos, SLDataType x);

??查找数据：