数据结构---手撕顺序表---顺序表增删查改寻找功能的实现

这篇具有很好参考价值的文章主要介绍了数据结构---手撕顺序表---顺序表增删查改寻找功能的实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


顺序表前言

顺序表作为数据结构的入门知识,整体知识较为简单,主要对动态内存开辟 结构体 指针有要求,其余难度较低


顺序表要实现的功能

顺序表主要需要实现的有顺序表的增删查改和定向搜索销毁等,具体实现函数如下

// 对数据的管理:增删查改 
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);
}

顺序表定向位置查找

最简单的功能,只需要遍历顺序表即可

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构.C】顺序表和单链表的增删查改

    宝子,你不点个赞吗?不评个论吗?不收个藏吗? 最后的最后,关注我,关注我,关注我,你会看到更多有趣的博客哦!!! 喵喵喵,你对我真的很重要。 目录 单链表增删查改 c1.h sqlist.c number.c 单链表的增删查改  c1.h stuscore.c c1.h sqlist.c number.c  c1.h stuscore.c   宝子,你不点

    2024年02月11日
    浏览(109)
  • 详解初阶数据结构之顺序表(SeqList)——单文件文件实现SeqList的增删查改

    目录 一、线性表 二、顺序表 2.1概念及结构 2.2接口实现 2.3动态顺序表的创建 2.3动态顺序表的初始化 2.3.1传值初始化 2.3.2传址初始化 2.4动态顺序表的清空 2.5动态顺序表的扩容 2.6动态顺序表内容的打印 三、动态顺序表的使用 3.1尾插尾删 3.1.1尾插 3.1.2尾删 3.2头插头删 3.2.1头插

    2024年02月09日
    浏览(40)
  • 【数据结构】单链表的增删查改(C实现)

    优势 : 可通过 下标i (数据连续(物理空间连续)) 便捷查询查找顺序表中的信息,也会在后面的 排序算法 和 堆算法 中尽显身手 问题 : 在头部/中间的插入与删除需要 挪动数据 ,时间复杂度为O(N),效率低; 增容需要申请新空间, 可能会拷贝数据 ,释放旧空间,会有

    2024年02月05日
    浏览(54)
  • 【数据结构】链表:带头双向循环链表的增删查改

    本篇要分享的内容是带头双向链表,以下为本片目录 目录 一、链表的所有结构 二、带头双向链表 2.1尾部插入 2.2哨兵位的初始化 2.3头部插入 2.4 打印链表 2.5尾部删除 2.6头部删除  2.7查找结点 2.8任意位置插入 2.9任意位置删除  在刚开始接触链表的时候,我们所学仅仅所学的

    2024年02月05日
    浏览(89)
  • 【数据结构】单链表的增删查改(C语言实现)

    在上一节中我们提到了顺序表有如下缺陷: 在头部/中间的插入与删除需要挪动数据,时间复杂度为O(N),效率低; 增容需要申请新空间,可能会拷贝数据,释放旧空间,会有不小的消耗; 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容

    2024年02月06日
    浏览(56)
  • 【数据结构与算法】单链表的增删查改(附源码)

      这么可爱的猫猫不值得点个赞吗 😽😻 目录 一.链表的概念和结构 二.单链表的逻辑结构和物理结构 1.逻辑结构  2.物理结构 三.结构体的定义 四.增加 1.尾插   SListpushback 2.头插  SListpushfront 五.删除 1.尾删  SListpopback 2.头删  SListpopfront 六.查找  插入  释放   打印 1.查找

    2024年02月02日
    浏览(72)
  • 【数据结构】双向链表的增删查改(C 代码实现)

    引入双向链表:关于单链表的问题与讨论 单链表存在的毛病: 因为单链表 只能单向 遍历链表, 对于 前插 这个操作,单链表必 须得找到所需前插节点位置的前一个 ,那么这时就得 从头指针重新遍历一次 链表,会造成时间复杂度大大增加。 没有头节点(哨兵位)无法删除

    2024年02月08日
    浏览(51)
  • 【数据结构】单向链表的增删查改以及指定pos位置的插入删除

    目录  单向链表的概念及结构  尾插 头插 尾删 ​编辑  头删  查找  在pos位置前插  在pos位置后插  删除pos位置  删除pos的后一个位置 总结 代码  概念:链表是一种 物理存储结构上非连续 、非顺序的存储结构,数据元素的 逻辑顺序 是通过链表中的 指针链接 次序实现的

    2024年02月05日
    浏览(47)
  • 数据结构之——(手撕)顺序表

    本章会介绍的知识点如下图:                    顺序表的结构:逻辑结构与物理结构都是内存中一块连续开辟的空间,都是11对应的线性结构。 两种定义顺序表的方式代码如下         静态的顺序表         动态的顺序表:          在这两种结构中通常我们是会

    2024年02月11日
    浏览(37)
  • 【数据结构】手撕顺序表

    顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储; 在数组上完成数据的增删查改。  1,  静态顺序表 :使用 定长数组 存储元素。 2., 动态顺序表 :使用 动态开辟 的数组存储。   静态顺序表只适用于确定知道需要存多少数

    2024年02月11日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包