Lesson02 - 顺序表C语言实现（没有伪代码）
文章目录
数据结构与算法前言1 什么是顺序表
1.1 基本概念1.2 顺序表的类型 二、顺序表上的基本操作实现（c语言版）
2.1 初始化2.2 销毁2.3 打印2.4 增容2.5 尾插2.6 尾删2.7 在 pos 位置插入元素2.8 删除 pos 位置的元素2.9 头插2.10 头删2.11 查找（按位查找）2.12 查找（按值查找）2.13 修改 pos 位置的值 3 顺序表的特点
先来谈优点：再来谈优点： //后记
前言
Lesson02 主要讲解数据结构中的 - 顺序表，以及顺序表的C语言实现。
本篇文章没有伪代码，帮助大家在理解顺序表的前提下，自己动手用C语言实现动态增长的顺序表
1 什么是顺序表 1.1 基本概念 线性表的顺序存储又称为顺序表
通俗而言，就是用一组地址连续的存储单元，依次来存储线性表中的数据元素
再简单来说，极其类似我们C语言中定义的数组
但是，区别于数组的是：
1.2 顺序表的类型 在数组中，我们的数据可以有间隔
比如在 int arr [10] 这个数组中，我们可以通过访问下标将1和2存在数组中的任意位置
但是在顺序表中，我们必须将元素依次存放，也就是在逻辑上相邻的元素，在物理位置上（存储单元内）也相邻，不可随意存放
由于我们可以用一维数组模拟实现顺序表
而一维数组的空间分配可以直接静态分配定长的数组（比如直接 inta[100]，就是静态分配100个int型的空间）；
也可以动态分配空间（比如 int* a = (int*)malloc(sizeof(int)*100 ,就是动态分配100个空间）；
因此顺序表也可以分为两类：
第一类：静态数据表
#define MAX_SIZE 100 //定义静态数组的最大容量
typedef int SLDataType; //定义顺序表中数据的类型
//定义一个静态顺序表
typedef struct SeqList
{
SLDataType a[MAX_SIZE]; //固定大小的数组
int size; //顺序表中有效数据的个数,方便我们寻找最后一个元素的位置
}SeqList;
数组的大小和空间固定，一旦空间占满，新的数据就是溢出，程序就会崩溃
而且如果静态开辟的数组很大，但是需要存储的数据很少的话，会造成空间的浪费
因此，静态顺序表有其局限性
第二类：动态顺序表
typedef int SLDataType; //定义顺序表中数据的类型
//定义一个动态顺序表
typedef struct SeqList
{
SLDataType* a; //定义一个指向动态数组的指针
int size; //顺序表中有效元素的个数
int capacity; //顺序表此时的容量，方便扩容
}SeqList;
二、顺序表上的基本操作实现（c语言版） 存储的空间是在程序执行过程中动态分配的
一旦分配的空间用满，我们可以另外开辟一块更大的空间（比如用 realloc 函数），用来替换之前的空间
这样带来的好处就是我们需要存储的数据就不会出现溢出，空间利用率较高
ps：由于静态顺序表局限性很大，我们这里用C语言实现一个动态顺序表~
2.1 初始化 在初始化接口中，会给顺序表动态分配一个数组，并且将 size 和 capacity 的值初始化
#include
//顺序表初始化
//定义默认容量
#define DEFAULT_CAPACITY 10
void SeqListInit(SeqList* ps)//这里切记要传创建的顺序表的地址
{
assert(ps); //断言一下，如果是空指针，无法解引用操作
ps->capacity = DEFAULT_CAPACITY; //容量初始化为默认容量
ps->size = 0; //有效数据为 0
//动态申请一个大小为capacity的数组
ps->a = (int*)malloc(sizeof(SLDataType) * ps->capacity);
if (ps->a == NULL) //使用 malloc 函数一定要注意检查申请失败的情况
{
perror("SeqList::malloc");
}
}
2.2 销毁
将顺序表清空
malloc 申请的空间还给系统，capacity 与 size 的值清 0
//顺序表的销毁
void SeqListDestroy(SeqList* ps)
{
assert(ps);
free(ps->a); //释放申请的空间
ps->a = NULL;
ps->capacity = 0;
ps->size = 0;
}
2.3 打印
类似于数组元素的打印，也就是遍历整个顺序表，依次将元素打印出来
#include2.4 增容//顺序表的打印 void SeqListPrint(SeqList* ps) { assert(ps); int i = 0; for (i = 0; i < ps->size; i++) { printf("%d ", ps->a[i]); } printf("n"); }
在插入操作中要重复判断顺序表是否已满，所以这里单独定义一个接口函数
//检查是否已满
void CheckSeqListFull(SeqList* ps)
{
//顺序表已满的条件
if (ps->capacity == ps->size)
{
//每次扩容选择扩大为原来的二倍
SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);
if (tmp == NULL)
{
perror("CheckFull::realloc");
}
ps->a = tmp;
ps->capacity *= 2;//切记一定要修改扩容后的容量
}
}
2.5 尾插
尾插 - 在顺序表的最后面插入一个元素
插入前一定要注意顺序表是否已满，不然会造成越界访问
并且在插入后，记得修改顺序表的 size
//顺序表的尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
assert(ps);
CheckSeqListFull(ps); //一定要检查是否已满
ps->a[ps->size++] = x; //插入数据后记得size++
}
2.6 尾删
尾删 - 删除顺序表的最后一个元素
在这里我们不在物理上删除这个元素，而是在逻辑上将其删除即可
也就是只需修改顺序表中有效元素的个数即可
//顺序表的尾删
void SeqListPopBack(SeqList* ps)
{
assert(ps);
//如果没有元素，不必删除
if (ps->size == 0)
return;
//逻辑上删除，物理上这个元素还是存在的,但是我们已经访问不到它了
ps->size--;
}
2.7 在 pos 位置插入元素
思路：将 pos 位置之后的元素从后往前以此向后移动一位
再将待插入元素放入 pos 位置上即可
//在 pos 位置上插入元素x
void SeqListInsert(SeqList* ps, int pos ,SLDataType x)
{
assert(ps);
assert(pos >= 0); //检查插入位置的合法性
CheckSeqListFull(ps); //检查顺序表是否已满
int i = 0;
//从后往前，依次后移一位
for (i = ps->size - 1; i >= pos; i--)
{
ps->a[i + 1] = ps->a[i];
}
//插入x
ps->a[pos] = x;
ps->size++;
}
2.8 删除 pos 位置的元素
思路：将 pos 位置之后的元素从前往后依次向前移动一位，覆盖之前的元素
//删除顺序表 pos 位置的元素
void SeqListErase(SeqList* ps, int pos)
{
assert(ps);
assert(pos >= 0);
int i = 0;
// 将pos ~ size-1位置的元素依次前移一位
for (i = pos; i < ps->size - 1; i++)
//这里注意i的最大值不能超过size-1，否则i+1就会越界
{
ps->a[i] = ps->a[i + 1];
}
//删除元素记得size--
ps->size--;
}
2.9 头插
这里可以复用 2.7 在顺序表的 pos 位置插入元素 的代码
即在 0 位置插入元素
//顺序表的头插
void SeqListPushFront(SeqList* ps, SLDataType x)
{
//复用代码-在0位置插入元素x
SeqListInsert(ps, 0, x);
}
2.10 头删
这里依旧可以复用 2.8 删除顺序表 pos 位置的元素 的代码
即删除 0 位置的元素
//顺序表头删
void SeqListPopFront(SeqList* ps)
{
//复用代码-删除0位置的元素
SeqListErase(ps, 0);
}
2.11 查找（按位查找）
按位查找很简单，直接访问下标即可
//顺序表的查找（按位查找）
SLDataType SeqListFindByPos(SeqList* ps, int pos)
{
assert(ps);
//检查位置的合法性
assert(pos >= 0 && pos < ps->size);
return ps->a[pos];
}
2.12 查找（按值查找）
只需遍历整个顺序表，找到此值返回下标
找不到就返回 -1
//顺序表的查找（按值查找）
int SeqListFindByVal(SeqList* ps, SLDataType x)
{
assert(ps);
int i = 0;
for (i = 0; i < ps->size; i++)
{
if (ps->a[i] == x)
return i;
}
return -1;
}
2.13 修改 pos 位置的值
判断位置合法性，然后修改即可
//修改 pos 位置的值
void SeqListModify(SeqList* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
ps->a[pos] = x;
}
3 顺序表的特点
先来谈优点：
再来谈优点： 支持随机访问，即通过下标直接访问 pos 位置的元素，时间复杂度为o（1）
存储密度高，每个结点只存储数据
在数据中间插入或删除元素时，需要移动大量数据
数据量过大时，增容操作也会消耗一定的性能
综上就是关于顺序表最核心的知识，对您有帮助的老铁，还望关注、点赞、收藏一键三连哦~~~
//后记 以后每周会更新一到两篇学习数据结构的笔记，用来记录自己的学习历程，复习巩固所学的知识。
文中概念或者代码有任何错误的地方，希望大佬们在评论区指出，本人会虚心接受并且改正。
