数据结构之——(手撕)顺序表

本章会介绍的知识点如下图:

 

 1: 顺序表的概念:顺序表是用一段物理地址连续的存储单元依次存储数据的线性结构,通常我们使用数组来表示,对数组进行增删查改。

                 顺序表的结构:逻辑结构与物理结构都是内存中一块连续开辟的空间,都是11对应的线性结构。

2: 顺序表的两种定义方式:静态的顺序表与动态的顺序表,一般情况下我们很少会用静态的顺序表,因为静态的顺序表会将空间固定,导致如果我们使用顺序表的时候可能会浪费很多的空间,也可能在我们增容的时候会出现空间不够的情况,这种情况下如果我们还是在继续使用的话那么数组将会越界这种情况是error的。

两种定义顺序表的方式代码如下

        静态的顺序表        

typedef int SqListDataType;//这里是给我们的顺序表元素的类型起个名字
//							 假设元素是其他类型我们就可以修改这里
//静态的
struct SqList1
{SqListDataType arr1[1000];//开辟了一个整形的数组int size;//用来记录顺序表当前使用了多少的空间
};

动态的顺序表:

        

struct SqList2
{SqListDataType* arr2;int size;int Capacity;//用来记录当前数组开辟了多少个空间
};

在这两种结构中通常我们是会选择动态的顺序表来管理数据的。

3:顺序表的接口实现:

我们最终选择这个定义的顺序表 

        1:这个接口的定义是应为当我们在增加元素的时候我们所存储的元素会变多,总有一种情况下我们空间会慢,所以这时候我们就需要扩容,使用了realloc这个函数扩容有两种情况,一种是原地扩,一种是换个空间扩。不管怎么样我们都定义一个空间,用来存储新开辟的地址,让后在给ps

//检查容量的代码
void check_capacity(SqList* ps)
{assert(ps);//空间不够,扩容,一次扩两倍if (ps->Capacity == ps->size){SqListDataType* tmp=(SqListDataType*)realloc(ps->arr, (ps->Capacity)* 2*sizeof(SqListDataType));if (tmp == NULL){perror("realloc fail");exit(-1);}else{printf("扩容成功\n");ps->arr = tmp;ps->Capacity *= 2;}}}

2:头插思路:先检查空间是否足够,在从后往前移动元素,将第一个位置出来,最后在添加元素即可。

void PushFrontSqList(SqList* ps, SqListDataType x)
{//先检查空间够不够,空间不够扩容check_capacity(ps);//先判断空间是否满了//先移动元素int end = ps->size - 1;while (end >= 0){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[0] = x;ps->size++;
}

上述代码的意思如下图:

        

 3:尾插思路:这个挺简单的,我们只要在size位置插入即可,size在++即可,这里要注意的就是我们插入要以数组的下标。

代码:

void PushBackSqList(SqList* ps, SqListDataType x)
{assert(ps);check_capacity(ps);ps->arr[ps->size] = x;ps->size++;//SqListInsert(ps, ps->size, x);
}

 4:头删思路:我们首先得判断顺序表是否有元素,如果有的话才能进行删除,我们只需要遍历数组从前往后将后一个元素移动到前一个就行,这里需要注意的就是我们移动时位置的不同可能导致代码的不一样,而我的代码是从第一个开始所以我最后的位置因该是size-2处,然后size--就可以了。

代码:

void PopFrontSqList(SqList* ps)
{assert(ps);assert(ps->size > 0);int i = 0;for (i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

5:尾删思路:这个挺简单的,首先还是得判断顺序表是否存在元素,如果有将size--就行了。

代码:

void PopBackSqList(SqList* ps)
{assert(ps);assert(ps->size > 0);ps->size--;
}

6:顺序表得查找思路:遍历数组就行了,如果存在则返回下标,如果不存在我们返回-1.

代码:

int FindSqList(SqList* ps, SqListDataType x)
{assert(ps);//防止ps没有意义//思路:遍历顺序表找int i = 0;for (i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}//未找到printf("未找到\n");return -1;
}

7:顺序表插入思路:在pos位置处插入一个元素,pos为下标,首先先我们得判断pos是否存在,如果存在我们先从前往后将元素向后移动,然后在pos位置处插入即可。

代码:

void SqListInsert(SqList* ps, int pos, SqListDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);check_capacity(ps);int end = ps->size - 1;while (end >= pos){ps->arr[end + 1] = ps->arr[end];end--;}ps->arr[pos] = x;ps->size++;
}

图:

 8:顺序表的删除思路:先判断,pos是否在顺序表中,我们只要从前完后移动pos后面的元素即可,然后我们在把size--;

代码:

void SqListErase(SqList* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);int i = pos;for (i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

9:顺序表的修改思路:先判断,pos是否在顺序表中,然后在根据数组随机访问的特点修改即可。

代码:

void ModifySqlist(SqList* ps, int pos, SqListDataType x)
{assert(ps);assert(pos >= 0 && pos < ps->size);ps->arr[pos] = x;}

10:打印:遍历数组即可

代码:

void SqListPrint(SqList* ps)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}

11:销毁顺序表这一步也不能省略,防止内存泄漏。

代码:

//销毁
void DestorySqList(SqList* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->Capacity = ps->size = 0;
}

以上就是顺序表的大致结构了。

通过上面我们可以发现:顺序表适合尾插,尾删,修改,这是因为顺序表随机访问的特点造成的。

        本章完,感谢大家的观看。

        

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

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

相关文章

⛳ Docker 安装 MySQL

&#x1f38d;目录 ⛳ Docker 安装 MySQL&#x1f69c; 一、搜索 mysql , 查看版本&#x1f3a8; 二、拉取mysql镜像&#x1f463; 三、建立容器的挂载文件&#x1f9f0; 四、创建mysql配置文件&#xff0c;my.conf&#x1f3ed; 五、根据镜像产生容器&#x1f381; 六、远程连…

node_modules.cache是什么东西

一开始没明白这是啥玩意&#xff0c;还以为是npm的属性&#xff0c;网上也没说过具体的来源出处 .cache文件的产生是由webpack4的插件cache-loader生成的&#xff0c;node_modules里下载了cache-loader插件&#xff0c;很多朋友都是vuecli工具生成的项目&#xff0c;内置了这部…

elelementui组件

一、按钮 1、按钮样式 使用type、plain、round和circle属性来定义 Button 的样式。 2、主要代码 <el-row><el-button>默认按钮</el-button><el-button type"primary">主要按钮</el-button><el-button type"success">…

【计算机网络】日志与守护进程

文章目录 日志日志的创建logmessage 函数日志左边部分实现日志右边部分实现 完整代码log.hpp(整体实现)err.hpp (错误信息枚举&#xff09; 守护进程PGID SID TTY 的介绍shell中控制进程组的方式结论 为什么要有守护进程存在&#xff1f;守护进程的创建使用守护进程的条件守护进…

2023国赛数学建模A题B题C题D题资料思路汇总 高教社杯

本次比赛我们将会全程更新思路模型及代码&#xff0c;大家查看文末名片获取 之前国赛相关的资料和助攻可以查看 2022数学建模国赛C题思路分析_2022年数学建模c题思路_UST数模社_的博客-CSDN博客 2022国赛数学建模A题B题C题D题资料思路汇总 高教社杯_2022国赛a题题目_UST数模…

前端通信(渲染、http、缓存、异步、跨域)自用笔记

SSR/CSR&#xff1a;HTML拼接&#xff1f;网页源码&#xff1f;SEO/交互性 SSR &#xff08;server side render&#xff09;服务端渲染&#xff0c;是指由服务侧&#xff08;server side&#xff09;完成页面的DOM结构拼接&#xff0c;然后发送到浏览器&#xff0c;为其绑定状…

浅谈泛在电力物联网发展形态与技术挑战

安科瑞 华楠 摘 要&#xff1a;泛在电力物联网是当前智能电网发展的一个方向。首先&#xff0c;总结了泛在电力物联网的主要作用和价值体现&#xff1b;其次&#xff0c;从智能电网各个环节概述了物联网技术在电力领域的已有研究和应用基础&#xff1b;进而&#xff0c;构思并…

手机无人直播软件,有哪些优势?

近年来&#xff0c;随着手机直播的流行和直播带货的市场越来越大&#xff0c;手机无人直播软件成为许多商家开播带货的首选。在这个领域里&#xff0c;声音人无人直播系统以其独特的优势&#xff0c;成为市场上备受瞩目的产品。接下来&#xff0c;我们将探讨手机无人直播软件给…

基于jeecg-boot的flowable流程加签功能实现

更多nbcio-boot功能请看演示系统 gitee源代码地址 后端代码&#xff1a; https://gitee.com/nbacheng/nbcio-boot 前端代码&#xff1a;https://gitee.com/nbacheng/nbcio-vue.git 在线演示&#xff08;包括H5&#xff09; &#xff1a; http://122.227.135.243:9888 今天我…

uni-app打包后安卓不显示地图及相关操作详解

新公司最近用uni-app写app&#xff0c;之前的代码有很多问题&#xff0c;正好趁着改bug的时间学习下uni-app。 问题现象&#xff1a; 使用uni-app在浏览器调试的时候&#xff0c;地图是展示的&#xff0c;但是打包完成后&#xff0c;在app端是空白的。咱第一次写app&#xff…

视频云存储/安防监控EasyCVR视频汇聚平台分发rtsp流时,出现“用户已过期”提示该如何解决?

视频云存储/安防监控EasyCVR视频汇聚平台基于云边端智能协同&#xff0c;支持海量视频的轻量化接入与汇聚、转码与处理、全网智能分发、视频集中存储等。音视频流媒体视频平台EasyCVR拓展性强&#xff0c;视频能力丰富&#xff0c;具体可实现视频监控直播、视频轮播、视频录像、…

2023企业Hyper-V备份解决方案!

虚拟技术已成为IT基础设施的核心元素&#xff0c;企业长期依赖虚拟机&#xff08;VM&#xff09;为应用程序提供工作负载。Hyper-V是一款广受欢迎的虚拟化平台&#xff0c;多年来已日臻完善&#xff0c;并在各类规模的公司中得到广泛应用。 随着虚拟机使用的普及&…

FPGA使用MIG调用SODIMM内存条接口教程,提供vivado工程源码和技术支持

目录 1、前言免责声明 2、SODIMM内存条简介3、设计思路框架视频输入视频缓存MIG配置调用SODIMM内存条VGA时序视频输出 4、vivado工程详解5、上板调试验证6、福利&#xff1a;工程代码的获取 1、前言 FPGA应用中&#xff0c;数据缓存是一大重点&#xff0c;不管是图像处理还是A…

搭建开发环境-操作系统篇(一键搭建开发环境)

概述 所谓工欲善其事必先利其器&#xff0c;搭环境往往是开发过程中卡出很多初学者的拦路虎。 对于很多老鸟来说&#xff0c;很多东西都已经习惯成自然&#xff0c;也就没有刻意和初学者说。但对于很多初学者&#xff0c;却是受益良多。 这个系列&#xff0c;先从操作系统开始…

ES基础操作

1.创建索引 在 Postman 中&#xff0c;向 ES 服务器发 PUT 请求 &#xff1a; http://127.0.0.1:9200/shopping 后台日志 重复发送 PUT 请求添加索引 &#xff1a; http://127.0.0.1:9200/shopping &#xff0c;会返回错误信息 : 2.获取单个索引相关信息 在 Postman 中&#…

IDC发布《亚太决策支持型分析数据平台评估》报告,亚马逊云科技位列“领导者”类别

日前&#xff0c;领先的IT市场研究和咨询公司IDC发布《2023年亚太地区&#xff08;不含日本&#xff09;决策支持型分析数据平台供应商评估》1报告&#xff0c;亚马逊云科技位列“领导者”类别。IDC认为&#xff0c;亚马逊云科技在解决方案的协同性、敏捷性、完整性、及时性、经…

[C++] string类常用接口的模拟实现

文章目录 1、前言2、遍历2.1 operator[ ]下标方式2.2 迭代器2.3 范围for2.4 c_str 3、容量相关3.1 size&#xff08;大小&#xff09;3.2 capacity&#xff08;容量&#xff09;3.3 empty&#xff08;判空&#xff09;3.4 clear&#xff08;清理&#xff09;3.5 reserve3.6 res…

idea连接linux远程docker详细教程操作

1&#xff1a;修改docker配置文件docker.service vi /usr/lib/systemd/system/docker.service2&#xff1a;找到 ExecStart&#xff0c;在最后面添加 -H tcp://0.0.0.0:2375 # for containers run by docker ExecStart/usr/bin/dockerd -H fd:// --containerd/run/containerd/…

Android动态添加和删除控件/布局

一、引言 最近在研究RecyclerView二级列表的使用方法&#xff0c;需要实现的效果如下。 然后查了一些博客&#xff0c;觉得实现方式太过复杂&#xff0c;而且这种方式也不是特别受推荐&#xff0c;所以请教了别人&#xff0c;得到了一种感觉还不错的实现方式。实现的思路为&…

航空电子设备中的TSN通讯架构—直升机

前言 以太网正在迅速取代传统网络&#xff0c;成为航空电子设备和任务系统的核心高速网络。本文提出了以太网时间敏感网络(TSN)在航空电子设备上应用的技术优势问题。在实际应用中&#xff0c;TSN已成为一个具有丰富的机制和协议的工具箱&#xff0c;可满足与时间和可靠性相关…