顺序表专题
文章目录
- 目录
- 1. 数据结构相关概念
- 1.1 什么是数据结构
- 1.2 为什么需要数据结构
- 2. 顺序表的概念及结构
- 3. 顺序表分类
- 4. 实现动态顺序表
- 4.1 初始化
- 4.2 顺序表的尾部插入
- 4.3 打印顺序表
- 4.4 顺序表的头部插入
- 4.5 顺序表的尾部删除
- 4.6 顺序表的头部删除
- 4.7 指定位置之前插入数据
- 4.8 删除指定位置数据
- 4.9 在顺序表中查找x
- 4.10 顺序表的销毁
目录
- 数据结构相关概念
- 顺序表概念及结构
- 顺序表分类
- 实现动态顺序表
1. 数据结构相关概念
1.1 什么是数据结构
数据结构是由“数据”和“结构”两词组合而来。
什么是数据?
常见的数值1、2、3、4…、教务系统里保存的用户信息(姓名、性别、年龄、学历等等)、网页里肉眼可以看到的信息(文字、图片、视频等等),这些都是数据。
什么是结构?
当我们想要大量使用同⼀类型的数据时,通过手动定义大量的独立的变量对于程序来说,可读性非常差,我们可以借助数组这样的数据结构将⼤量的数据组织在⼀起,结构也可以理解为组织数据的方式。
概念: 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成,即数据由哪部分构成,以什么方式构成,以及数据元素之间呈现的结构。
总结:
1)能够存储数据(如顺序表、链表等结构)
2)存储的数据能够方便查找
1.2 为什么需要数据结构
程序中如果不对数据进行管理,可能会导致数据丢失、操作数据困难、野指针等情况。通过数据结构,能够有效将数据组织和管理在⼀起。按照我们的方式任意对数据进行增删改查等操作。
最基础的数据结构:数组。
【思考】有了数组,为什么还要学习其他的数据结构?
假定数组有10个空间,已经使用了5个,向数组中插入数据的步骤:
- 求数组的长度,求数组的有效数据个数
- 向下标为数据有效个数的位置插入数据(注意:这里是否要判断数组是否满了,满了还能继续插入吗)
- 假设数据量非常庞大,频繁的获取数组有效数据个数会影响程序执行效率。
结论: 最基础的数据结构能够提供的操作已经不能完全满足复杂算法实现。
2. 顺序表的概念及结构
线性表:
线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就说是连续的⼀条直线;但是在物理结构上并不⼀定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。
顺序表:
逻辑结构是线性的、物理结构是连续的。
顺序表和数组的区别:
顺序表的底层结构是数组,对数组的封装,实现了常用的增删改查等接口。
3. 顺序表分类
- 静态顺序表
概念:使用定长数组存储元素
//静态顺序表#define N 100typedef int SLDataType;//顺序表中数组类型不一定是整型,如果要变为字符类型,就可以在这里直接改;如果不这样定义,就要在代码中改很多次struct SeqList
{SLDataType a[N];//定长数组int size;//有效数据个数
};
静态顺序表缺陷:空间给少了不够⽤,给多了造成空间浪费
- 动态顺序表
//动态顺序表typedef int SLDataType;typedef struct SeqList
{SLDataType* arr;//存储数据的底层结构int capacity;//记录顺序表的空间大小int size;//记录顺序表当前有效的数据个数
}SL;//typedef struct SeqList SL;
4. 实现动态顺序表
4.1 初始化
void SLInit(SL* ps)
{assert(ps);ps->arr = NULL;ps->size = ps->capacity = 0;
}
4.2 顺序表的尾部插入
void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newCapacity = 0 == ps->capacity ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));if (NULL == tmp){perror("realloc fail!");exit(1);}//扩容成功ps->arr = tmp;ps->capacity = newCapacity;}
}void SLPushBack(SL* ps, SLDataType x)
{//断言 -- 粗暴的解决方式//assert(ps != NULL);assert(ps);//if判断 -- 温柔的解决方式//if (NULL == ps)//{// return;//}//空间不够,扩容SLCheckCapacity(ps);//空间足够,直接插入ps->arr[ps->size++] = x;//ps->size++;
}
注:
扩容的原则:成倍数的增加(1.5倍、2倍)
4.3 打印顺序表
void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}
4.4 顺序表的头部插入
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//判断是否扩容SLCheckCapacity(ps);//旧数据往后挪动一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}
4.5 顺序表的尾部删除
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//顺序表不为空ps->size--;
}
4.6 顺序表的头部删除
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];}ps->size--;
}
4.7 指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//pos及之后的数据往后挪动一位,pos空出来for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}
4.8 删除指定位置数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//pos以后的数据往前挪动一位for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
4.9 在顺序表中查找x
int SLFind(SL* ps, SLDataType x)
{//加上断言对代码的健壮性更好assert(ps);for (int i = 0; i < ps->size; i++){if (x == ps->arr[i]){return i;}}return -1;
}
4.10 顺序表的销毁
void SLDestroy(SL* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}
完整代码:
//SeqList.h#include <stdio.h>
#include <stdlib.h>
#include <assert.h>静态顺序表
//
//#define N 100
//
//typedef int SLDataType;
//
//struct SeqList
//{
// SLDataType a[N];
// int size;
//};//动态顺序表typedef int SLDataType;typedef struct SeqList
{SLDataType* arr;//存储数据的底层结构int capacity;//记录顺序表的空间大小int size;//记录顺序表当前有效的数据个数
}SL;//typedef struct SeqList SL;//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);//保持接口一致性//顺序表的头部/尾部插入
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);//顺序表的头部/尾部删除
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);//指定位置之前插入数据
//删除指定位置数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);int SLFind(SL* ps, SLDataType x);
//SeqList.c#include "SeqList.h"//初始化和销毁
void SLInit(SL* ps)
{assert(ps);ps->arr = NULL;ps->size = ps->capacity = 0;
}void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newCapacity = 0 == ps->capacity ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));if (NULL == tmp){perror("realloc fail!");exit(1);}//扩容成功ps->arr = tmp;ps->capacity = newCapacity;}
}//顺序表的头部/尾部插入
void SLPushBack(SL* ps, SLDataType x)
{//断言 -- 粗暴的解决方式//assert(ps != NULL);assert(ps);//if判断 -- 温柔的解决方式//if (NULL == ps)//{// return;//}//空间不够,扩容SLCheckCapacity(ps);//空间足够,直接插入ps->arr[ps->size++] = x;//ps->size++;
}void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//判断是否扩容SLCheckCapacity(ps);//旧数据往后挪动一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}//顺序表的头部/尾部删除
void SLPopBack(SL* ps)
{assert(ps);assert(ps->size);//顺序表不为空ps->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];}ps->size--;
}//指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(ps);//pos及之后的数据往后挪动一位,pos空出来for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}//删除指定位置数据
void SLErase(SL* ps, int pos)
{assert(ps);assert(pos >= 0 && pos < ps->size);//pos以后的数据往前挪动一位for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}//在顺序表中查找x
int SLFind(SL* ps, SLDataType x)
{//加上断言对代码的健壮性更好assert(ps);for (int i = 0; i < ps->size; i++){if (x == ps->arr[i]){return i;}}return -1;
}void SLDestroy(SL* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}
//test.c#include "SeqList.h"void slTest01()
{SL sl;SLInit(&sl);//测试尾插SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(&sl);//SLPushBack(&sl, 5);//SLPrint(&sl);//SLPushBack(NULL, 6);//头插//SLPushFront(&sl, 5);//SLPushFront(&sl, 6);//SLPushFront(&sl, 7);//SLPrint(&sl);//尾删//SLPopBack(&sl);//SLPopBack(&sl);//SLPopBack(&sl);//SLPopBack(&sl);//SLPrint(&sl);//头删//SLPopFront(&sl);//SLPopFront(&sl);//SLPopFront(&sl);//SLPopFront(&sl);//SLPrint(&sl);//指定位置插入//SLInsert(&sl, 0, 100);//SLPrint(&sl);//SLInsert(&sl, sl.size, 200);//SLPrint(&sl);//SLInsert(&sl, 100, 300);//SLPrint(&sl);//删除指定位置的数据//SLErase(&sl, 0);//SLPrint(&sl);//SLErase(&sl, sl.size - 1);//SLPrint(&sl);SLErase(&sl, 1);SLPrint(&sl);
}void slTest02()
{SL sl;SLInit(&sl);//测试尾插SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(&sl);//测试查找//int ret = SLFind(&sl, 3);int ret = SLFind(&sl, 30);if (ret < 0){printf("数据不存在,查找失败!");}else{printf("数据找到了,在下标为%d位置\n", ret);}
}int main()
{//slTest01();slTest02();return 0;
}
相关文章:
顺序表专题
文章目录 目录1. 数据结构相关概念1.1 什么是数据结构1.2 为什么需要数据结构 2. 顺序表的概念及结构3. 顺序表分类4. 实现动态顺序表4.1 初始化4.2 顺序表的尾部插入4.3 打印顺序表4.4 顺序表的头部插入4.5 顺序表的尾部删除4.6 顺序表的头部删除4.7 指定位置之前插入数据4.8 …...
手写SpringBoot(三)之自动配置
系列文章目录 手写SpringBoot(一)之简易版SpringBoot 手写SpringBoot(二)之动态切换Servlet容器 手写SpringBoot(三)之自动配置 手写SpringBoot(四)之bean动态加载 手写SpringBoot…...
vitepress builld报错
问题:build时报错:document/window is not defined。 背景:使用vitepress展示自定义的组件,之前build是没有问题了,由于新增了qr-code以及quill富文本组件,导致打包时报错。 原因:vitepress官…...
redis分布式锁-----基于Redis的SETNX命令的简单分布式锁实现
Redis的SETNX命令的简单分布式锁实现的Java示例 首先,确保你已经引入了Jedis这个Java Redis客户端库。你可以通过Maven或Gradle来添加依赖。 1、Maven依赖 <dependency><groupId>redis.clients</groupId><artifactId>jedis</artifact…...
HTTP请求头中的Host表示是什么?
表示处理请求的服务器地址,由于一台服务器可能部署多个网站,如果通过域名访问,host就是域名...
apk被play protect blocked的解决方案(ADB+Appium+webdriverio)
起因:公司有海外项目,需要推广apk ,数量多,但是由于被play protect阻止安装,初版解决方案 apk加固、换签名、垃圾代码、修改资源文件的MD5,但是由于原生代码标记过于严重,推广成本高,又换了一种…...
【BlossomRPC】手把手教你写一个RPC协议
文章目录 新的开始什么是RPC?设计一个RPC需要些什么? 新的开始 经常会遇到一些项目,看着看着就发现看不懂文档了,也就是会出现一些跳过讲解的文章,使得自己很难了解某种中间件的开发全貌,所以想着自己先设计一个比较…...
算法之美:堆排序原理剖析及应用案例分解实现
这段时间持续更新关于“二叉树”的专栏文章,关心的小伙伴们对于二叉树的基本原理已经有了初步的了解。接下来,我将会更深入地探究二叉树的原理,并且展示如何将这些原理应用到更广泛的场景中去。文章将延续前面文章的风格,尽量精炼…...
Net8 ABP VNext完美集成FreeSql、SqlSugar,实现聚合根增删改查,完全去掉EFCore
没有基础的,请参考上一篇 彩蛋到最后一张图里找 参考链接 结果直接上图,没有任何业务代码 启动后,已经有了基本的CRUD功能,还扩展了批量删除,与动态查询 动态查询截图,支持分页,排序 实现原理…...
yolov8直接调用zed相机实现三维测距(python)
yolov8直接调用zed相机实现三维测距(python) 1. 相关配置2. 版本一2.1 相关代码2.2 实验结果 3. 版本二3.1 相关代码3.2 实验结果 相关链接 此项目直接调用zed相机实现三维测距,无需标定,相关内容如下: 1.yolov5直接调…...
element跑马灯/轮播图,第一页隐藏左边按钮,最后一页隐藏右边按钮(vue 开箱即用)
图示: 第一步: <el-carousel :class"changeIndex0?leftBtnNone:changeIndeximgDataList.length-1? rightBtnNone:" height"546px" :autoplay"false" change"changeNext"><el-carousel-item v-for…...
下载及安装PHP,composer,phpstudy,thinkPHP6.0框架
文章目录 目录 文章目录 前言 一、下载PHP 二、下载composer 三、下载PHPstudy 四、下载think PHP 1.下载 2.多应用开发 前言 thinkPHP是一款开源的PHP框架,它是基于MVC(Model-View-Controller)设计模式构建的。thinkPHP提供了丰富的…...
volatile使用场景总结
volatile关键字在Java中用于确保变量的可见性以及防止指令重排序,特别是在没有使用锁定机制时对变量进行读写的多线程环境中。以下是需要使用volatile修饰的一些场景: 确保变量的可见性 当一个变量被多个线程访问,且至少有一个线程在写&…...
AcWing 1413. 矩形牛棚(每日一题)
原题链接:1413. 矩形牛棚 - AcWing题库 作为一个资本家,农夫约翰希望通过购买更多的奶牛来扩大他的牛奶业务。 因此,他需要找地方建立一个新的牛棚。 约翰购买了一大块土地,这个土地可以看作是一个 R 行(编号 1∼R&…...
macOS Sonoma 14.4.1 (23E224) 正式版发布,ISO、IPSW、PKG 下载
macOS Sonoma 14.4.1 (23E224) 正式版发布,ISO、IPSW、PKG 下载 2024 年 3 月 26 日凌晨,macOS Sonoma 14.4.1 更新修复了一个可能导致连接到外部显示器的 USB 集线器无法被识别的问题。它还解决了可能导致 Java 应用程序意外退出的问题,并修…...
WPF使用外部字体,思源黑体,为例子
1.在工程中新建文件夹,命名为“Font"。 2.将下载好的字体文件复制到Font文件夹。 3.在工程中,加入静态资源 <Window.Resources><FontFamily x:Key"SYBold">/AnalyzeImage;Component/Font/#思源黑体 CN Bold</FontFamily…...
9、jenkins微服务持续集成(一)
文章目录 一、流程说明二、源码概述三、本地部署3.1 SpringCloud微服务部署本地运行微服务本地部署微服务3.2 静态Web前端部署四、Docker快速入门一、流程说明 Jenkins+Docker+SpringCloud持续集成流程说明 大致流程说明: 开发人员每天把代码提交到Gitlab代码仓库Jenkins从G…...
VOC(客户之声)赋能智能家居:打造个性化、交互式的未来生活体验
随着科技的飞速发展,智能家居已成为现代家庭不可或缺的一部分。然而,如何让智能家居更好地满足用户需求,提供更贴心、更智能的服务,一直是行业关注的焦点。在这个背景下,VOC(客户之声)作为一种用…...
时序预测 | Matlab实现GWO-BP灰狼算法优化BP神经网络时间序列预测
时序预测 | Matlab实现GWO-BP灰狼算法优化BP神经网络时间序列预测 目录 时序预测 | Matlab实现GWO-BP灰狼算法优化BP神经网络时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.Matlab实现GWO-BP灰狼算法优化BP神经网络时间序列预测(完整源码和数据…...
node.js学习(2)
版权声明 以下文章为尚硅谷PDF资料,B站视频链接:【尚硅谷Node.js零基础视频教程,nodejs新手到高手】仅供个人学习交流使用。如涉及侵权问题,请立即与本人联系,本人将积极配合删除相关内容。感谢理解和支持,…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
Golang——9、反射和文件操作
反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一:使用Read()读取文件2.3、方式二:bufio读取文件2.4、方式三:os.ReadFile读取2.5、写…...
人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent
安全大模型训练计划:基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标:为安全大模型创建高质量、去偏、符合伦理的训练数据集,涵盖安全相关任务(如有害内容检测、隐私保护、道德推理等)。 1.1 数据收集 描…...
什么是VR全景技术
VR全景技术,全称为虚拟现实全景技术,是通过计算机图像模拟生成三维空间中的虚拟世界,使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验,结合图文、3D、音视频等多媒体元素…...
UE5 音效系统
一.音效管理 音乐一般都是WAV,创建一个背景音乐类SoudClass,一个音效类SoundClass。所有的音乐都分为这两个类。再创建一个总音乐类,将上述两个作为它的子类。 接着我们创建一个音乐混合类SoundMix,将上述三个类翻入其中,通过它管理每个音乐…...
