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

别丢了你的勇敢

前言：

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

1.什么是顺序表

1.1线性表

1.2顺序表

图片来自比特就业课官网链接：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;

🍊 2.2.4

void SLInit (SL* ps);

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

🍋2.2.5

void SLDestroy (SL* ps);

void SLDestroy(SL* ps)
{
?? ?free(ps->a);
?? ?ps->a = NULL;
?? ?ps->size = 0;
?? ?ps->capacity = 0;
｝

🍌 2.2.6

void SLPrint (SL* ps);

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

🍉 2.2.7

void SLCheckCapacity (SL* ps);

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;
}

🍇 2.2.8

void SLPushBack(SL* ps, SLDataType x); ?

??这个是尾插

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

void SLPushBack(SL* ps, SLDataType x)
{
?? ?if (ps->size + 1 > ps->capacity)
?? ??? ?SLCheckCapacity(ps);
?? ?ps->a[ps->size] = x;
?? ?(ps->size)++;
}

🍓 ?2.2.9

1. 第一步检查是否需要扩容
2. 第二步通过循环让下标pos及pos之后的元素集体后移一个单位，
3. 第三步把数据放入下标为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);

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

void SLDelete(SL* ps, int pos)
{
?? ?if (ps->size - 1 < 0)
?? ?{
?? ??? ?printf("顺序表空了\n");
?? ??? ?//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("要修改的元素不存在\n");
?? ?else
?? ??? ?ps->a[pos] = x;
}

🍍 2.2.15

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

{
?? ?if (pos >= ps->size)
?? ??? ?printf("要查找的元素不存在\n");
?? ?else
?? ??? ?printf("%d\n",ps->a[pos]);
}