顺序表前言
顺序表作为数据结构的入门知识,整体知识较为简单,主要对动态内存开辟 结构体 指针有要求,其余难度较低
顺序表要实现的功能
顺序表主要需要实现的有顺序表的增删查改和定向搜索销毁等,具体实现函数如下
// 对数据的管理:增删查改
void SeqListInit(SeqList* ps);
void SeqListDestroy(SeqList* ps);
void SeqListPrint(SeqList* ps);
void SeqListPushBack(SeqList* ps, SLDateType x);
void SeqListPushFront(SeqList* ps, SLDateType x);
void SeqListPopFront(SeqList* ps);
void SeqListPopBack(SeqList* ps);
// 顺序表查找
int SeqListFind(SeqList* ps, SLDateType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* ps, int pos, SLDateType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* ps, int pos);
定义顺序表
要实现顺序表,就需要对顺序表进行定义,在c语言中通常使用结构体进行写入,包括顺序表的容量,顺序表中存在元素的个数,顺序表的主体
在对顺序表的定义中存在两种,如果不使用动态内存开辟,可以直接定义一个数组实现顺序表,但由于数组容量是固定的,会把整个顺序表固定大小,于是在这里采用动态内存开辟的方法实现顺序表
首先对顺序表进行定义
typedef int SLDateType;
typedef struct SeqList
{
SLDateType* a;
int size;
int capacity;
}SeqList;
接下来我们就对顺序表的各项功能进行依次实现
顺序表初始化
把顺序表的结构体定义完成后就可以创建一个顺序表了,创建好初始值后就要对顺序表进行一定的初始化内容
代码实现如下
void SeqListInit(SeqList* ps)
{
assert(ps);
ps->a = (SLDateType*)malloc(sizeof(SLDateType) * 4);
if (ps->a == NULL)
{
perror("malloc fail");
return;
}
ps->size = 0;
ps->capacity = 4;
}
关于assert函数
assert的作用是断言,主要是用来进行条件判断,例如这里检测ps,意思就是检测ps是否为空指针,如果ps是空指针后续的操作就不必而行了,这样有利于检查错误信息,当运行到该语句结论为假时,会直接终止代码,算是暴力检查的一种方法
顺序表的销毁
创建完顺序表后就要对顺序表进行销毁,销毁的就是把它对应的空间释放,置空指针,返回初始值
代码实现如下
void SeqListDestroy(SeqList* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}
关于置空指针
一般来说,把相关空间释放后为了避免出现野指针的情况要把指针置空,但不进行指针的置空在一些情况下也是可以的,一般释放空间后都会紧跟置空指针
打印顺序表
将顺序表里的信息打印到屏幕上,进行可视化观察有无错误信息
代码实现如下
void SeqListPrint(SeqList* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}
顺序表的尾插
将一个数据插入到顺序表中就涉及到了顺序表的尾插
思路也很简单,首先看原来顺序表的容量是否满足要求,如果不满足就进行一定的扩容,再把要插入的数据放到顺序表的尾部即可
如何实现检查容量?
如果顺序表的size和capacity是一致的,说明已经满了,到达上限了
因此函数实现如下
void SLCheckCapacity(SeqList* ps)
{
assert(ps);
SLDateType* tmp = NULL;
if (ps->capacity == ps->size)
{
tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->capacity * 2);
if (tmp == NULL)
{
perror("realloc fail");
return;
}
ps->a = tmp;
ps->capacity *= 2;
printf("扩容成功 当前容量%d\n", ps->capacity);
}
}
但是由于后续还有再规定位置插入元素的情况,我们可以直接先写在x位置插入元素的情况
因此函数实现就变成了实现在x位置插入元素
函数实现如下
void SeqListInsert(SeqList* ps, int pos, SLDateType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
int end = ps->size - 1;
while (pos <= end)
{
ps->a[end + 1] = ps->a[end];
end--;
}
ps->a[pos] = x;
ps->size ++ ;
}
有了在x位置插入元素函数的实现,对于在尾部插入函数只需要将x换成size即可
void SeqListPushBack(SeqList* ps, SLDateType x)
{
assert(ps);
SeqListInsert(ps,ps->size,x);
}
顺序表的头插
和顺序表的尾插相似,当我们有了在x位置插入元素的函数时,这些需求就很好写了
void SeqListPushFront(SeqList* ps, SLDateType x)
{
assert(ps);
SeqListInsert(ps, 0, x);
}
顺序表的头删
有了前面的想法,我们也把在x位置的元素进行删除封装成一个函数
函数实现如下
void SeqListErase(SeqList* ps, int pos)
{
assert(pos >= 0 && pos < ps->size);
int end = ps->size-1;
while (pos <= end)
{
ps->a[pos] = ps->a[pos + 1];
pos++;
}
ps->size--;
}
那么头删就是把标号为0的元素删除
具体函数实现如下
void SeqListPopFront(SeqList* ps)
{
assert(ps);
SeqListErase(ps, 0);
}
顺序表的尾删
有了头删的想法,尾删和头删基本一致
void SeqListPopBack(SeqList* ps)
{
assert(ps);
int end = ps->size - 1;
SeqListErase(ps, end);
}
顺序表定向位置查找
最简单的功能,只需要遍历顺序表即可文章来源:https://www.toymoban.com/news/detail-565632.html
int SeqListFind(SeqList* ps, SLDateType x)
{
assert(ps);
for(int i=0;i<ps->size;i++)
{
if (ps->a[i] == x)
return i;
}
return -1;
}
整体来说顺序表是数据结构入门的部分,难度偏低文章来源地址https://www.toymoban.com/news/detail-565632.html
到了这里,关于数据结构---手撕顺序表---顺序表增删查改寻找功能的实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!