深入浅出:手把手教你实现顺序表

一、什么是顺序表

顺序表是一种数据结构,或者说,是数据在内存中存储和管理的一种方式。顺序表要求每个数据要从第一个位置开始,依次挨着放。这就很适合使用C语言中的数组来实现。

很多朋友可能会觉得,那有啥可以讲的?我们创建一个数组,在里面存储数据不就得了?其实没这么简单。这个数组要创建多大?如果创建太小,万一数据太多,不够存咋办?万一创建太大,却没这么多数据,那很多空间不就浪费了?所以,我们需要进行动态的内存管理。比如说,一开始就给4个空间,之后每次放满了就扩容,依次类推。

C语言里提供了动态内存管理的函数,分别是malloc,calloc,realloc和free。这些函数能够帮助我们很好地进行动态内存的管理。以上的这几个函数有一个特点,需要使用一个指针来指向这块动态管理的空间。除此之外,我们还需要两个变量,分别用来记录这块空间的大小,以及存储的有效数据的个数。综上,我们需要声明一个结构体来描述顺序表。


struct SeqList
{int* a;int size;int capacity;
};

其中,我们假设要存储的数据类型是int,所以需要一个int*的指针来管理这块空间。如果需要存储其他类型的数据,并且随时修改存储类型,可以使用typedef,用SLDateType来代替此处和下文中出现的int,这样方便以后修改存储类型。


typedef int SLDataType;

以上结构体中的size代表目前存储的有效数据的个数,一开始是0。而capacity则代表容量,也就是目前最多可以存储的数据个数。当size和capacity相等时,代表顺序表已满,此时就需要扩容。

需要说明的是,如果你嫌每次写struct SeqList很麻烦,也可以typedef一下。


typedef struct SeqList
{int* a;int size;int capacity;
}SL;

以下叙述中,我们假设已经创建了一个顺序表,并且拿到了它的地址psl。


SL sl;
SL* psl = &sl;

由于后面的操作都要对psl解引用,所以我们假设每次解引用前都断言了psl!=NULL。


assert(psl);

二、初始化

顺序表一开始没有存储任何数据,所以可以把先把结构体的内容都初始化成0。


psl->a = psl->size = psl->capacity = 0;

三、插入、删除

数组的下标是从0开始的,所以我们假定顺序表的下标也是从0开始。那么,我们如何在下标为pos的位置插入一个数据呢?其实很简单,只需要把pos及pos之后的位置向后挪动一格,此时pos位置就空出来了,就可以插入数据了。所以核心代码就一行,即如何挪动数据。我们需要知道起始位置是pos,往后挪动一格就到了pos+1。一共要挪动几个数据呢?举个例子,假设一共有10个数据,也就是size=10,假设pos是3,下标是从0开始的,pos前面的数据有0,1,2,总共3个数据,也就是说,pos前面的数据有pos个,那么pos及pos之后的数据就有size-pos个,这也是要挪动的数据的个数。我们使用memmove函数来挪动数据,注意不能使用memcpy,因为挪动前后的内存空间是有重叠的。


memmove(psl->a+pos+1, psl->a+pos, (psl->size-pos)*sizeof(int));

接着插入数据。


psl->a[pos] = x;
psl->size++;

这就完了吗?No!你忽略了一个重要的问题。一开始初始化时,psl为空,能直接解引用吗?还有万一size=capacity,能直接插入吗?所以每次插入前,都要检查一下容量是否充足,如果满了,要扩容!

检查容量是否充足很好办,如果size==capacity就满了,这包括两种情况,一种是capacity=size=0,另一种是随着size逐渐增长,size==capacity时就满了。

那如何扩容呢?这就可以使用realloc。注意当传给realloc的指针为NULL时,realloc的表现和malloc是一样的。所以我们可以把上面两种情况当做一种情况来处理。为了叙述方便,我们假设一开始给4个空间,后面每次都扩2倍,也就是说新的容量是:


int newCapacity = psl->capacity==0 ? 4 : 2*psl->capacity;

接着调用realloc函数:


int* tmp = (int*)realloc(psl->a, newCapacity*sizeof(int));

若tmp经过检查不为NULL,说明扩容成功。


psl->a = tmp;
psl->capacity = newCapacity;

知道了如何插入数据,删除数据也是同样的道理。只需要把pos位置之后的数据向前挪一格,就覆盖掉了pos位置的数据,相当于把pos位置的数据删除了。目标位置是pos,起始位置是pos+1,要挪动的数据个数是多少呢?在上面插入数据的讲解中,pos及pos之后的数据个数是size-pos,那么不包括pos的数据个数就是size-pos-1。


memmove(psl->a+pos, psl->a+pos+1, (size-pos-1)*sizeof(int));

最后不要忘了psl->size--。但是有个问题,如果一开始就没有数据,那就不能继续删了呀!所以删除之前要断言一下psl->size>0,才可以删除(但有了后面的讲解,其实不用断言这一点,具体原因后面说)。

其实,前面的讲述中漏掉了一点,那就是pos并不是任何值都可以的。在插入数据的时候,必须保证pos>=0 && pos<=psl->size,而在删除的时候,必须保证pos>=0 && pos<psl->size。pos>=0很好理解,因为下标从0开始。pos<size也很好理解,因为size表示有效数据个数。假设有6个数据,即size是6,下标就是0~5,pos就只能从这之间取。但是插入时为啥允许pos==size呢?还是假设有6个数据,size是6,已经有的数据下标是0~5,那如果是否允许在下标为6的位置插入呢?当然允许呀!因为在已经有的最后一个数据后面紧接着插入一个数据,并没有违反顺序表数据挨着挨着存储的原则。

由于删除顺序表的元素时有pos>=0,size>pos,故有size>0,所以不用断言这一点。

四、打印

只需要遍历这个数组然后打印即可。


for (int i = 0; i<psl->size; ++i)
{printf("%d ", psl->a[i]);
}
printf("\n");

五、查找、修改

查找也是遍历数组即可,非常简单。需要注意的是,pos必须要满足pos>=0 && pos<psl->size。具体原因,讲解插入删除时已经讲过。

如查找x:


for (int i = 0; i<psl->size; ++i)
{if (psl->a[i] == x)return i;
}return -1; // 找不到就返回负数

修改也很简单,访问下标为pos的数据并且改掉即可。


psl->a[pos] = x;

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/114111.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Qt网络通信——获取本机网络信息

查询一个主机的MAC地址或者IP地址是网络应用中常用到的功能&#xff0c;Qt提供了QHostInfo和QNetworkInterface 类可以用于此类信息的查询 1.QHostInfo 类&#xff08;显示和查找本地的信息&#xff09;是的主要函数 类别 函数原型作用公共函数QList <QHostAdress> addr…

SpringBoot项目配置文件数据库用户名密码加密

1、需求 在使用SpringBoot开发过程中&#xff0c;会将一些敏感信息配置到SpringBoot项目的配置文件中(不考虑使用配置中心的情况 )&#xff0c;例如数据库的用户名和密码、Redis的密码等。为了保证敏感信息的安全&#xff0c;我们需要将此类数据进行加密配置。 2、操作步骤 …

docker 部署springboot(成功、截图)

1.新建sringboot工程并打包 2.编写Dockerfile文件 # 基础镜像使用java FROM openjdk:8 # 作者 MAINTAINER feng # VOLUME 指定了临时文件目录为/tmp。 # 其效果是在主机 /var/lib/docker 目录下创建了一个临时文件&#xff0c;并链接到容器的/tmp VOLUME /tmp # 将jar包添加…

探秘二叉树后序遍历:从叶子到根的深度之旅

本篇博客会讲解力扣“145. 二叉树的后序遍历”的解题思路&#xff0c;这是题目链接。 本题的思路是&#xff1a; 先创建一个数组&#xff0c;用来存储二叉树后序遍历的结果。数组的大小跟树的结点个数有关。树的结点个数可以使用递归实现&#xff0c;即总个数左子树结点个数右…

Ansible

目录 Ansible简介 ansible 环境安装部署 #管理端安装 ansible //ansible 目录结构 //配置主机清单 //配置密钥对验证 ansible 命令行模块 1&#xff0e;command 模块 2&#xff0e;shell 模块 3&#xff0e;cron 模块 4&#xff0e;user 模块 5&#xff0e;group 模块 6&am…

人生的回忆

回忆是人类宝贵的精神财富&#xff0c;它们像一串串珍珠&#xff0c;串联起我们生活中的每一个片段。 回忆是时间的见证者&#xff0c;它们承载着我们成长、经历、悲欢离合的点点滴滴。 回忆让我们重温过去的欢笑与眼泪&#xff0c;感受那些已经逝去的时光。它们就像一本翻开的…

Caffine和Guava的refreshAfterWrite的异同

背景: guava和caffine的refreshAfterWrite方法在用于本地缓存的场景是非常常用的&#xff0c;本文通过例子列举下caffine的refreshAfterWrite方法和guava的refreshAfterWrite的相同点和不同点 相同点/不同点&#xff1a; 以下都是使用keyXYZ作为例子 场景1&#xff1a;一开…

时序预测 | MATLAB实现基于QPSO-BiGRU、PSO-BiGRU、BiGRU时间序列预测

时序预测 | MATLAB实现基于QPSO-BiGRU、PSO-BiGRU、BiGRU时间序列预测 目录 时序预测 | MATLAB实现基于QPSO-BiGRU、PSO-BiGRU、BiGRU时间序列预测效果一览基本描述程序设计参考资料 效果一览 基本描述 1.时序预测 | MATLAB实现基于QPSO-BiGRU、PSO-BiGRU、BiGRU时间序列预测&a…

基于沙猫群算法优化的BP神经网络(预测应用) - 附代码

基于沙猫群算法优化的BP神经网络&#xff08;预测应用&#xff09; - 附代码 文章目录 基于沙猫群算法优化的BP神经网络&#xff08;预测应用&#xff09; - 附代码1.数据介绍2.沙猫群优化BP神经网络2.1 BP神经网络参数设置2.2 沙猫群算法应用 4.测试结果&#xff1a;5.Matlab代…

NFTScan | 08.21~08.27 NFT 市场热点汇总

欢迎来到由 NFT 基础设施 NFTScan 出品的 NFT 生态热点事件每周汇总。周期&#xff1a;2023.08.21~ 2023.08.27 NFT Hot News 01/ NFT 品牌体验平台 Recur 将于 11 月 16 日彻底关闭&#xff0c;此前曾获 5000 万美元融资 8 月 21 日&#xff0c;NFT 品牌体验平台 Recur 在 X…

mall :rabbit项目源码解析

文章目录 一、mall开源项目1.1 来源1.2 项目转移1.3 项目克隆 二、RabbitMQ 消息中间件2.1 rabbit简介2.2 分布式后端项目的使用流程2.3 分布式后端项目的使用场景 三、安装RabbitMQ(Win10)3.1安装erLang语言&#xff0c;配置环境变量3.2 安装RabbitMQ服务端3.3 测试安装效果 四…

海康机器人工业相机SDK MVS安装教程

文章目录 一. 海康机器人介绍二. 工业相机客户端安装教程 一. 海康机器人介绍 海康机器人是面向全球的机器视觉和移动机器人产品及解决方案提供商&#xff0c;业务聚焦于工业物联网、智慧物流和智能制造&#xff0c;构建开放合作生态&#xff0c;为工业和物流领域用户提供服务…

美国纽约10日游

一、前言 我有两周断更了&#xff0c;原因是去纽约只顾着玩&#xff0c;没时间写&#xff0c;今天有时间正好和大家分享一下去纽约的攻略 二、以下是一个10天去美国纽约旅游的攻略&#xff0c;十万以内&#xff0c;包括机票、酒店、交通、餐饮和景点门票等费用&#xff1a; 第…

js、PHP连接外卖小票机打印机方案(调用佳博、芯烨等)

前言&#xff1a; 目前开发需要用到电脑直接连接外卖小票机打印小票&#xff0c;查阅各种资料&#xff0c;使用 6612345浏览器 终于解决了这个问题。 效果&#xff1a; PHP、js直接连接小票机并且自动出票。 支持的小票机&#xff1a; 目前测试可以的有&#xff1a;电脑A4打印…

学乐多光屏 P90:打开儿童学习新视界

随着科技迅猛发展&#xff0c;儿童教育正在迎来一场前所未有的革命。在这个数字化时代的浪潮中&#xff0c;学乐多光屏P90凭借其卓越的特性和深远的教育理念&#xff0c;成为智能儿童学习领域的引领者&#xff0c;为孩子们创造了崭新的学习体验。 创新科技&#xff0c;引领学习…

亚马逊云科技GenAI菁英创造营,致力于大模型时代高校AI人才培养

大语言模型&#xff08;LLM&#xff09;产业的蓬勃发展将改变数字产业生态&#xff0c;助力AI工业化进程、变革海量应用交互方式、创造数字产业新的增长空间。 “GenAI Talent Program”由亚马逊云科技特别打造&#xff0c;该计划致力于大模型时代高校AI人才培养&#xff0c;通…

dubbo项目traceId链路传递(MDC方案及重复traceId处理)

1.traceId用途 主要用于项目dubbo接口调用链日志追踪使用&#xff0c;可以获取完整的链路日志&#xff0c;协助排查问题。 2.traceId传递及代码实现 本方案是基于 org.slf4j.MDC 进行实现&#xff0c;会出现线程池中线程复用导致traceId重复问题&#xff0c;后面会说解决方案。…

头歌MYSQL——课后作业1 数据库和数据表的建立、修改和删除

第1关&#xff1a;建立数据库 任务描述 本关任务&#xff1a;建立数据库 为了完成本关任务&#xff0c;你需要掌握&#xff1a; 如何创建数据库&#xff0c;显示已经建立的数据库 相关知识 创建数据库 创建数据库是在系统磁盘上划分一块区域用于数据的存储和管理。 命令格…

应用TortoiseSVN的SubWCRev管理VisualStudio C#项目编译版本号

首先要安装 TortoiseSVN, 并确保TortoiseSVN的bin目录被加入到系统环境变量Path中。 1、拷贝Porperties目录下的文件AssemblyInfo.cs生成副本AssemblyInfo.template, 作为版本管理的模板文件。 2、修改模板文件中的想要管理的版本号信息 // [assembly: AssemblyVersion(&quo…

使用spring自带的发布订阅来实现发布订阅

背景 公司的项目以前代码里面有存在使用spring自带发布订阅的代码&#xff0c;因此稍微学习一下如何使用&#xff0c;并了解一下这种实现方式的优缺点。 优点 实现方便&#xff0c;代码方面基本只需要定义消息体和消费者&#xff0c;适用于小型应用程序。不依赖外部中间件&a…