实现顺序表的增删查改

news/2024/4/21 0:21:23/

现在让我们探索数据结构这个美妙的世界吧!

概念介绍

线性表是具有相同特性的数据元素的有限序列。线性表是一种在实际运用中广泛运用的线性结构,如线性表,栈,队列,字符串等。

顺序表的本质是数组,实现了对数组的封装,例如增删查改等功能。

顺序表分为静态顺序表和动态顺序表:

静态顺序表:

#define N 100
struct SeqList
{int arr[N];int size;//有效数据个数
};

动态顺序表:

struct SeqList
{int* arr;//动态数组int size;//有效数据个数int capacity;//空间大小
};

但是目前这个结构体只能存储int类型的数据,所以我们给数据类型起一个别名,让其更好存储其他类型的数据。

我们当前顺序表存储的类型进行替换:

typedef int SLDataType;

当前顺序表被我们修改成这样:

struct SeqList
{SLDataType* arr;//动态数组int size;//有效数据个数int capacity;//空间大小
};

但是每次引用我们的顺序表时,我们都要写SeqList,这样未免太麻烦了,于是我们想到用typedef一下来缩减我们的工作量。

typedef struct SeqList SL;

或者我们还可以采用另一种方式:

typedef struct SeqList
{SLDataType* arr;//动态数组int size;//有效数据个数int capacity;//空间大小
}SL;

初始化

void SLInit(SL* ps);
void SLInit(SL s)
{s.arr=NULL;s.size=s.capcity=0;
}

我们测试一下顺序表初始化的一些方法:

void SLTest01()
{SL s1;SLInit(s1);
}int main()
{SLTest01();return 0;
}

这个程序初始化的结果竟然是错误的,那么问题出现在哪里呢?问题在于我们没有传地址,仅仅是传值调用了。那就让我们修改一下我们的代码吧。

void SLInit(SL* ps);
void SLInit(SL* ps)
{s.arr=NULL;s.size=s.capcity=0;
}
void SLTest01()
{SL s1;SLInit(&s1);
}int main()
{SLTest01();return 0;
}

销毁

void SLDestroy(SL* ps);
void SLDestroy(SL* ps)
{if(ps->arr){free(ps->arr);}ps->arr=NULL;ps->size=ps->capcity=0;
}

尾部插入

void SLPushBack(SL* ps, SLDataType x);//往哪儿插入未知,所以要传入结构体

如图所示,size从4变成了5。

void SLPushBack(SL* ps, SLDataType x)
{//我们要往size里面插入xps->arr[size++]=x;//size后置加加,完成这个式子以后,size的空间被扩展
}

插入完成之后,让我们测试一下这个函数吧。

void SLTest01()
{SL s1;SLPushBack(&s1,1);
}

 但是测试的结果竟然是错误的,这是为啥呢?

空间为0,不能往数组里插入数据。在插入数据之前,我们应该先检查空间够不够。

void SLPushBack(SL* ps, SLDataType x)
{//我们要往size里面插入xif(ps->capacity=ps->size){//申请空间,增容通常是成倍地增加//如果malloc失败,会返回空指针int newCapacity=ps->capacity==0?4:2*ps->capacity;//我们再把申请来的空间给临时的tmpSLDataType*tmp=(SLDataType*)realloc(ps->arr,newCapacity*sizeof(SLDataTpye);if(tmp==NULL){perror("realloc fail");exit(1);//直接退出程序,不再执行}ps->arr=tmp;//如果开辟成功,就把realloc出的新空间给arrps->capacity=newCapacity;ps->arr[size++]=x;//size后置加加,完成这个式子以后,size的空间被扩展
}

如果我们插入空(NULL),这个程序就崩了。说明这个代码还不具备健壮性

那么我们可以如何解决呢?

if(ps==NULL)
{return;
}

这样遇到空,程序就会结束。我们也可以换一种方式:

assert(ps);

等价于assert(ps!=NULL);   这时如果为空,就直接一个弹窗出来报错了。

头部插入

void SLPushFront(SL* ps, SLDataType x);

插入数据我们就想到空间是否够用呢?

void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//检查ps是否为空SLCheckCapacity(ps);//先让顺序表向后挪动一位for(int i=ps->size;i>0;i--)//要判断函数的终止条件,就要看最后一个移动的条件是什么?这个程序是从后往前挪动,那么最后一次挪动就是arr[0]挪动到arr[1],那么i等于1,i大于0{ps->arr[i]=ps->arr[i-1];}ps->arr[0]=x;ps->size++;
}

在我们检查函数空间大小是否够用时,我们可以单独封装一个函数。

void SLCheckCapacity(SL*ps)
{//我们要往size里面插入xif(ps->capacity=ps->size){//申请空间,增容通常是成倍地增加//如果malloc失败,会返回空指针int newCapacity=ps->capacity==0?4:2*ps->capacity;//我们再把申请来的空间给临时的tmpSLDataType*tmp=(SLDataType*)realloc(ps->arr,newCapacity*sizeof(SLDataTpye));if(tmp==NULL){perror("realloc fail");exit(1);//直接退出程序,不再执行}ps->arr=tmp;//如果开辟成功,就把realloc出的新空间给arrps->capacity=newCapacity;
}

当我们运行完一个程序时,打印一下查看结果是否正确。

void Print(SL s)
{for(int i=0;i<s.size;i++){printf("%d",s.arr[i]);}printf("\n");
}

出乎意料的是,打印的结果不是我们想要的:

 好吧,增加一个数据,我们的size忘了++了。

尾部删除

void SLPopBack(SL*PS)
{
//ps不能为空,所以要先判断一下assert(ps);assert(ps->size);//数据个数也不能为空ps->arr[size-1]=-1;--ps->size;
}

直接把size--,不影响增删查改数据。

头部删除

void SLPopFront(SL*ps)
{assert(ps);assert(ps->size);for(int i=0;i<ps->size-1;i++){ps->arr[i]=ps->arr[i+1];//arr[size-1]=arr[size-2]}ps->size--;
}

在指定位置之前插入数据

void SLInsert(SL*ps,int pos,SLDataType x)
{assert(pos);assert(pos>=0&&pos<=ps->size);//可以等于,可以在size之前插入数据,在这里也就是尾插


http://www.ppmy.cn/news/1405571.html

相关文章

Docker 笔记

1.Ubuntu安装Docker 安装Docker看这篇文章 http://t.csdnimg.cn/IsSsJ 2.在docker中运行python代码 2.1搭建python环境 docker部署python环境看这篇文章 http://t.csdnimg.cn/TYz0G 2.2在python shell中运行python代码 2.2.1查看镜像 2.2.1启动python&#xff0c;厦门这个…

java实现小程序授权登录以及获取手机号

1、引入依赖 <dependency><groupId>com.github.binarywang</groupId><artifactId>weixin-java-miniapp</artifactId><version>4.1.0</version></dependency>2、引入封装好的工具类 import cn.binarywang.wx.miniapp.api.WxMaS…

28.ReentrantLock-多条件变量

synchronized中也有条件变量&#xff0c;当条件不满足时进入WaitSet等待。 ReentrantLock的条件变量比Synchronized强大之处在于它支持多个条件变量。 await和signal方法 多条件变量的使用流程 1.await需要获得锁。 2.await执行后会释放锁&#xff0c;进入ConditionObject…

Windows Edge浏览器兼容性问题诊断与修复策略详解

随着Microsoft Edge浏览器的持续迭代与更新&#xff0c;其性能与兼容性已得到了显著提升。然而&#xff0c;在面对互联网上纷繁复杂的网页内容时&#xff0c;仍有可能遇到兼容性问题。本文旨在探讨Edge浏览器在处理网页兼容性问题时的常见场景、原因分析及相应的解决方案&#…

秒验:让APP验证和登录远不只是便捷

在互联网时代&#xff0c;手机号码已成为用户在App应用中的身份标识&#xff0c;用于登录和身份核验。目前&#xff0c;大多数App应用采用短信验证码的方式进行登录&#xff0c;但这种方式存在一些缺点&#xff0c;如操作繁琐、验证码接收不及时或被截取等。随着5G时代的到来&a…

大数据设计为何要分层,行业常规设计会有几层数据

大数据设计通常采用分层结构的原因是为了提高数据管理的效率、降低系统复杂度、增强数据质量和可维护性。这种分层结构能够将数据按照不同的处理和应用需求进行分类和管理&#xff0c;从而更好地满足不同层次的数据处理和分析需求。行业常规设计中&#xff0c;数据通常按照以下…

docker导出导入镜像

docker导出镜像 查看要导出的镜像 docker images主要有两列 REPOSITORY TAG 导出命令 导出公式 docker save -o xxxx.tar REPOSITORY:TAG例子 docker save -o minio.tar minio/minio:latestminio/minio:latest可以使用image id代替&#xff0c;但是使用image id会导致导…

常州SAP实施公司有哪些值得推荐

随着信息技术的不断发展和企业管理的日益复杂&#xff0c;SAP系统在各行各业中扮演着越来越重要的角色。常州作为中国制造业的重要基地之一&#xff0c;其企业在数字化转型的道路上也越来越多地采用SAP系统&#xff0c;以提高管理效率、降低成本、优化资源配置&#xff0c;从而…

Excel中文显示问号

直接上操作步骤&#xff1a; 1&#xff09;打开Excel -> 文件 -> 选项 -> 语言 2&#xff09;Office 显示语言&#xff0c;“中文(简体)”设置为首选。 3&#xff09;Office创作语言和校对&#xff0c;“中文(简体)”设置为首选。 网上用记事本转换的方法&#xff0c;…

基于单片机20v数字电压表仿真系统设计

**单片机设计介绍&#xff0c;基于单片机20v数字电压表仿真系统设计 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机20V数字电压表仿真系统设计的主要目标是实现一个能够准确测量和显示20V直流电压的仿真系统。以下是该设计的主…

专升本-物联网

物联网&#xff08;IOT&#xff0c;Internet of things&#xff09; 体系结构&#xff1a; 感知层&#xff08;感知执行层&#xff09; 网络层 应用层 基本特征&#xff1a; 全面感知 可靠传输 智能处理 作用&#xff1a; 信息采集、转换、收集 信息传递和处理 数据…

网关冗余技术

1.第一跳冗余协议&#xff1a;FHRP HSRP、VRRP、GLBP 2.HSRP 热备份路由协议&#xff0c;思科私有协议&#xff0c;组播地址224.0.0.2&#xff0c;默认hello time3s&#xff0c;hold time 10s &#xff08;1&#xff09;原理&#xff1a; 1&#xff09;①将多台设备逻辑的…

C++中的string类模拟实现

目录 string类的模拟实现 string类的构造函数 string类拷贝构造函数 string类析构函数 string类c_str()函数 string类中的[]运算符重载函数 string类中的赋值运算符重载 string类中获取字符串有效字符个数 string类中获取字符串存储空间大小&#xff08;不包括\0&…

人工智能(pytorch)搭建模型25-基于pytorch搭建FPN特征金字塔网络的应用场景,模型结构介绍

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下人工智能(pytorch)搭建模型25-基于pytorch搭建FPN特征金字塔网络的应用场景&#xff0c;模型结构介绍。特征金字塔网络&#xff08;FPN&#xff09;是一种深度学习模型结构&#xff0c;主要应用于目标检测任务中&am…

scRNA+bulk+MR:动脉粥样硬化五个GEO数据集+GWAS,工作量十分到位

今天给大家分享一篇JCR一区&#xff0c;单细胞bulkMR的文章&#xff1a;An integrative analysis of single-cell and bulk transcriptome and bidirectional mendelian randomization analysis identified C1Q as a novel stimulated risk gene for Atherosclerosis 标题&…

Transformer的代码实现 day03(Positional Encoding)

Positional Encoding的理论部分 注意力机制是不含有位置信息&#xff0c;这也就表明&#xff1a;“我爱你”&#xff0c;“你爱我”这两者没有区别&#xff0c;而在现实世界中&#xff0c;这两者有区别。所以位置编码是在进行注意力计算之前&#xff0c;给输入加上一个位置信息…

FFMPEG对于处理rtp流出现马赛克问题处理

背景 本项目是基于FFMPEG 3.3版本进行的开发。 近期5G发展迅速&#xff0c;无线集群中的带宽不再是瓶颈&#xff0c;对于视频质量的要求也越来越高&#xff0c;现在使用720P、1080P、2K、4K进行视频通话成为了日常。 问题描述 本项目之前对于CIF和VGA格式的视频进行录…

论文笔记:基于多粒度信息融合的社交媒体多模态假新闻检测

整理了ICMR2023 Multi-modal Fake News Detection on Social Media via Multi-grained Information Fusion&#xff09;论文的阅读笔记 背景模型实验 背景 在假新闻检测领域&#xff0c;目前的方法主要集中在文本和视觉特征的集成上&#xff0c;但不能有效地利用细粒度和粗粒度…

2024年github之node排行榜top50

如果有帮助到您还请动动手帮忙点赞&#xff0c;关注&#xff0c;评论转发&#xff0c;感谢啦&#xff01;&#x1f495;&#x1f495;&#x1f495;&#x1f618;&#x1f618;&#x1f618; 本文由Butterfly一键发布工具发布 2024年github之node排行榜top50 语言star项目名称…

spring-boot集成websocket

引入Maven依赖包 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId><version>跟随spingboot版本</version> </dependency>后端代码 /*** 开启WebSocket支持*…