数据结构之手搓顺序表（顺序表的增删查改）
目录
文章目录
前言
一、什么是顺序表？
二、动态顺序表的实现
1.头文件定义
2.实现顺序表的初始化
3.检查顺序表空间容量是否足够，不够就增容
4.顺序表的销毁
5.顺序表的打印
6.顺序表的尾插
7.顺序表的头插
8.顺序表的头删
9.顺序表的尾删
10.顺序表的查找
11.在顺序表指定位置插入数据
12.顺序表删除指定位置数据
定义汇总代码：
1. .c文件
2.建议
前言
在我们学习初阶顺序结构的时候，首当其冲学习的就是顺序表，下边我将边讲解边手搓一个顺序表并实现他的增删改查功能
一、什么是顺序表？
概念：顺序表是用⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采用数组存储。其实顺序表的底层结构就是数组，我们对数组进行封装，实现了增删改查等常用的接口。
顺序表有静态顺序表和动态顺序表。
我们这里主要实现动态顺序表，因为静态顺序表有缺陷，空间给少了不够用，给多了又浪费。
二、动态顺序表的实现
1.头文件定义
代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int DateType;
typedef struct seqlist
{
DateType* arr;
int size;//有效的数据个数
int capacity;//空间容量
}seqlist;
//顺序表的初始化
void SeqListInit(seqlist* ps);
//检查顺序表空间容量是否足够，不够就增容
void SLCheckCapacity(seqlist* ps);
//顺序表的销毁
void SeqListDestroy(seqlist* ps);
//顺序表的打印
void SeqListPrint(seqlist* ps);
//顺序表的尾插
void SeqListPushBack(seqlist* ps, DateType x);
//顺序表的头插
void SeqListPushFront(seqlist* ps, DateType x);
//顺序表的头删
void SeqListPopFront(seqlist* ps);
//顺序表的尾删
void SeqListPopBack(seqlist* ps);
// 顺序表查找
int SeqListFind(seqlist* ps, DateType x);
// 顺序表在pos位置插入x
void SeqListInsert(seqlist* ps, int pos, DateType x);
// 顺序表删除pos位置的值
void SeqListErase(seqlist* ps, int pos);2.实现顺序表的初始化
代码如下：
//顺序表的初始化
void SeqListInit(seqlist* ps)
{
ps->arr = NULL;
ps->capacity = ps->size = 0;
}初始化就很简单，就是把指针指向空，有效数据个数和空间容量设为0。因为我们还没有开空间放数据。
3.检查顺序表空间容量是否足够，不够就增容
代码如下：
因为在顺序表的增删查改中要频繁用到这个操作，索性我们就把他封装成一个函数，到时候直接调用会更方便，不用一遍又一遍的去实现。
//检查顺序表空间容量是否足够，不够就增容
void SLCheckCapacity(seqlist* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
DateType* new = (DateType*)realloc(ps->arr, newcapacity * sizeof(DateType));
if (new == NULL)
{
perror("realloc");
return 1;
}
ps->arr = new;
ps->capacity = newcapacity;
}
}这里的思路呢就是先判断如果有效数据个数等于空间容量，那就说明顺序表满了，我们如果要再插入数据的话，就需要扩容，这也是动态顺序表的精髓所在。这里用到了三目操作符和realloc开辟空间。
4.顺序表的销毁
代码如下：
//顺序表的销毁
void SeqListDestroy(seqlist* ps)
{
assert(ps);
if (ps->arr)
{
free(ps->arr);
}
ps->arr = NULL;
ps->capacity = ps->size = 0;
}这里的思路也很简单，因为我们要销毁顺序表，free就是释放malloc,realloc,calloc开辟的空间，然后再将ps->arr这个指针设为空，避免它成为野指针，既然空间释放了，那么有效数据个数和空间容量就顺手变成0。
5.顺序表的打印
代码如下：
//顺序表的打印
void SeqListPrint(seqlist* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d->", ps->arr[i]);
}
printf("\n");
}这个其实没什么好说的，就是简单的循环打印数组中的内容。
6.顺序表的尾插
代码如下：
//顺序表的尾插
void SeqListPushBack(seqlist* ps, DateType x)
{
assert(ps);
SLCheckCapacity(ps);
ps->arr[ps->size] = x;
ps->size++;
}前边我们说了size就是有效数据个数，并且顺序表的底层就是数组，比如说顺序表中有1，2，3，4，那就是四个有效数据，而在数组中，他们的下标就是0，1，2，3，那么我们要插入5，我们用size这个数做下标就刚好是在顺序表末尾插入一个数据。然后再让size++，也就是下标++。
7.顺序表的头插
代码如下：
//顺序表的头插
void SeqListPushFront(seqlist* ps, DateType x)
{
assert(ps);
SLCheckCapacity(ps);
for (int i = ps->size; i >0; i--)
{
ps->arr[i] = ps->arr[i-1];
}
ps->arr[0] = x;
ps->size++;
}头插比尾插复杂一点点，因为头插需要把顺序表里边的数据整体向后挪一个位置，但是其实就是数组里边的数据整体向后挪一个下标，把0下标让出来插入。
8.顺序表的头删
代码如下：
//顺序表的头删
void SeqListPopFront(seqlist* ps)
{
assert(ps);
assert(ps->size);
for (int i = 1; i < ps->size; i++)
{
ps->arr[i-1] = ps->arr[i];
}
ps->size-- ;
}这里其实就是也不算真的删除，就是把0下标之后的数据依次往前挪一位，把0下标的数据覆盖了。
然后size--。
9.顺序表的尾删
代码如下：
//顺序表的尾删
void SeqListPopBack(seqlist* ps)
{
assert(ps);
assert(ps->size);
ps->size--;
}尾删就更简单了，就是把有效数据size--，这样就取不到最后一个数据了，等以后写入数据的话直接就把他覆盖了。
10.顺序表的查找
代码如下：
//顺序表的查找
int SeqListFind(seqlist* ps, DateType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}简单粗暴，直接for循环再顺序表中找，找到一样的，就返回他的下标，找不到就返回-1；
11.在顺序表指定位置插入数据
代码如下：
// 顺序表在pos位置插入x
void SeqListInsert(seqlist* ps, int pos, DateType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
ps->size++;
}很简单，pos就是下标，把下标和之后的数据全部向后挪一位，但是在这之前需要判断空间容量是否充足。
12.顺序表删除指定位置数据
代码如下：
// 顺序表删除pos位置的值
void SeqListErase(seqlist* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
assert(ps->size);
for (int i = pos; i < ps->size-1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}这里的思路就是把pos位置之后的值依次往前挪，并且覆盖了pos位置，然后size--。
定义汇总代码：
1. .c文件
#include"seqlistt.h"
//顺序表的初始化
void SeqListInit(seqlist* ps)
{
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
//检查顺序表空间容量是否足够，不够就增容
void SLCheckCapacity(seqlist* ps)
{
assert(ps);
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
DateType* new = (DateType*)realloc(ps->arr, newcapacity * sizeof(DateType));
if (new == NULL)
{
perror("realloc");
return 1;
}
ps->arr = new;
ps->capacity = newcapacity;
}
}
//顺序表的销毁
void SeqListDestroy(seqlist* ps)
{
assert(ps);
if (ps->arr)
{
free(ps->arr);
}
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
//顺序表的打印
void SeqListPrint(seqlist* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d->", ps->arr[i]);
}
printf("\n");
}
//顺序表的尾插
void SeqListPushBack(seqlist* ps, DateType x)
{
assert(ps);
SLCheckCapacity(ps);
ps->arr[ps->size] = x;
ps->size++;
}
//顺序表的头插
void SeqListPushFront(seqlist* ps, DateType x)
{
assert(ps);
SLCheckCapacity(ps);
for (int i = ps->size; i >0; i--)
{
ps->arr[i] = ps->arr[i-1];
}
ps->arr[0] = x;
ps->size++;
}
//顺序表的头删
void SeqListPopFront(seqlist* ps)
{
assert(ps);
assert(ps->size);
for (int i = 1; i < ps->size; i++)
{
ps->arr[i-1] = ps->arr[i];
}
ps->size-- ;
}
//顺序表的尾删
void SeqListPopBack(seqlist* ps)
{
assert(ps);
assert(ps->size);
ps->size--;
}
//顺序表的查找
int SeqListFind(seqlist* ps, DateType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}
// 顺序表在pos位置插入x
void SeqListInsert(seqlist* ps, int pos, DateType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
ps->size++;
}
// 顺序表删除pos位置的值
void SeqListErase(seqlist* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
assert(ps->size);
for (int i = pos; i < ps->size-1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}2.建议
可以将顺序表手搓一边，然后测试一下功能是否完整。如有助益，谓之我幸。