顺序表——重置版
本期我们来实现数据结构的顺序表(这个之前写过一次,不过本期和之前可能会略有不同,但大体相同),大家可以看一下我们之前完成的顺序表
(6条消息) 顺序表及其多种接口的实现_顺序表类中实现接口方法_KLZUQ的博客-CSDN博客
目录
顺序表的结构
顺序表的初始化
顺序表的销毁
尾插
尾删
打印顺序表的元素
扩容
头插
头删
任意位置插入
任意位置删除
查找
realloc相关知识
完整代码
我们继续用工程化的写法来保证好的代码习惯
顺序表的结构
我们仍然是先写出顺序表的结构
typedef int SLDataType;
#define INIT_CAPACITY 10 //初始容量
typedef struct SeqList {SLDataType* a;int size;//有效数据个数 int capacity;//空间容量
}SL;
因为顺序表大小的原因,开多了浪费,开少了不够用,所以我们需要定义一些变量来帮助我们对顺序表的大小进行调整
顺序表的初始化
void SLInit(SL* ps) {//初始化assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps->a == NULL) {perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}
初始化参数我们需要传顺序表这个结构体的指针,然后使用malloc开辟空间给顺序表,这个空间就是我们用来存储数据的,同时我们要判断是否开辟成功,失败时我们用perror来返回错误信息即可,开辟成功后,我们将有效数据个数置0,容量置为我们设置的初始容量
第一行的断言是因为我们传入的是顺序表这个结构体的指针,是不可能为空的,所以需要断言,而顺序表里的内容是否为空是由size来进行决定的
顺序表的销毁
void SLDestory(SL* ps) {//销毁assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}
顺序表的销毁我们free的是ps->a,而不是直接free掉ps,然后我们将ps置为空即可
尾插
void SLPushBack(SL* ps, SLDataType x)//尾插
{assert(ps);if (ps->size == ps->capacity) {//扩容SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2*sizeof(SLDataType));if (tmp == NULL) {perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->size++] = x;
}
尾插前我们需要对容量进行判断,如果不够就需要先扩容,我们这里扩容扩二倍,接着把数据放入数组里即可(我们的size是从0开始的,也就是说size的位置是我们当前存放数据最后一个的下一个位置)
尾删
void SLPopBack(SL* ps)//尾删
{assert(ps);//严格的判断//assert(ps->size>0);//温柔的判断if (ps->size == 0) {return;}ps->size--;
}
因为是顺序表,我们使用size来控制当前数据个数,所以直接size-1即可,我们不需要将这里的数据置为0,因为没有必要,而且我们也不能释放空间,因为这是数组,是连续的空间,当然在删除数据前,我们要先判断数组是否为空,这里我们有两种方法,一种是用assert直接断言,另一种是当作无事发生(更推荐assert一些)
打印顺序表的元素
有了尾插尾删,我们需要对程序进行测试,所以我们对顺序表的元素进行打印
void SLPrint(SL* ps) {//打印assert(ps);for (int i = 0; i < ps->size; i++) {printf("%d->", ps->a[i]);}printf("NULL\n");
}
扩容
我们在写头插时,发现插入都需要先判断是否需要扩容,所以我们把扩容代码提取出来封装为一个函数方便后续使用
void SLCheckCapaicty(SL* ps)//扩容
{assert(ps);if (ps->size == ps->capacity) {//扩容SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(SLDataType));if (tmp == NULL) {perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}
头插
void SLPushFront(SL* ps, SLDataType x)//头插
{assert(ps);SLCheckCapaicty(ps);int end = ps->size - 1;while (end>=0) {ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;
}
头插的效率不高,需要挪动后续所有元素,如果有n个元素,我们要插入n个元素,时间复杂度就是n^2了,而尾插n个数据的数据复杂度是n,这是非常恐怖的,比如我们要插入1w个数据,那么头插就是1w*1w了,而尾插是1w,所以我们要避免使用头插
头删
void SLPopFront(SL* ps)//头删
{assert(ps);assert(ps->size > 0);int begin = 1;while (begin < ps->size) {ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}
如果size为0,那么顺序表为空,不能进行删除,删除时我们只需将a[0]之后的元素向前挪动即可,接着size-1,同样的,头删的效率也很低,时间复杂度也是n^2,所以我们也要少用头删
任意位置插入
void SLInsert(SL* ps, int pos, SLDataType x)//任意位置插入
{assert(ps);assert(pos>=0 && pos<=ps->size);SLCheckCapaicty(ps);int end = ps->size - 1;while (end>=pos) {ps->a[end + 1] = ps->a[end];--end;}ps->a[pos] = x;ps->size++;
}
如果我们想在顺序表中间某个位置插入,就可以使用该函数,因为是插入,所以也需要先判断是否需要扩容,另外,我们传入的pos是位置,所以要符合顺序表元素的个数,所以要断言一下,下面的插入代码和头插几乎一样
任意位置删除
void SLErase(SL* ps, int pos)//任意位置删除
{assert(ps);assert(pos >= 0 && pos < ps->size);int begin = pos + 1;while (begin < ps->size) {ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}
这里的断言和任意位置插入稍有不同,我们发现pos<ps->szie,而不能等于,而且我们不需要检查size是否大于0,因为pos会间接检查,因为size不可能为负数,而pos要大于等于0
查找
int SLFind(SL* ps, SLDataType x)//查找
{assert(ps);for (int i = 0; i < ps->size; i++) {if (ps->a[i] == x) {return i;}}return -1;
}
任意位置的插入和删除,一般是配合查找来使用的,查找返回的是下标,找不到时返回-1
realloc相关知识
最后我们在补充一点其他的只是,我们的顺序表扩容时使用了realloc函数,而realloc函数分配空间扩容会分为两种,一种是原地扩容,另一种是异地扩容,原地扩容就是将当前位置的后续空间使用权也分配给我们,而异地扩容则是新找了一块空间将使用权分配给我们,然后把原来的空间使用权归还给操作系统,当我们扩容小的时候,一般是原地扩容,但是当扩容次数较多时,后续空间会不足,就会进行异地扩容,找一块更大的空间给我们,异地扩容的效率是比原地扩容低很多的,异地扩容不仅要找一块新的空间,还要把原空间里的数据给拷贝过来,再释放原空间
完整代码
最后,在这里附上全部代码
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDataType;
#define INIT_CAPACITY 10 //初始容量
typedef struct SeqList {SLDataType* a;int size;//有效数据个数 int capacity;//空间容量
}SL;void SLInit(SL* ps);//初始化
void SLDestory(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 SLCheckCapaicty(SL* ps);//扩容
void SLInsert(SL* ps, int pos, SLDataType x);//任意位置插入
void SLErase(SL* ps, int pos);//任意位置删除
int SLFind(SL* ps, SLDataType x);//查找
#include "SeqList.h"void SLInit(SL* ps) {//初始化assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);if (ps->a == NULL) {perror("malloc fail");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;
}void SLCheckCapaicty(SL* ps)//扩容
{assert(ps);if (ps->size == ps->capacity) {//扩容SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(SLDataType));if (tmp == NULL) {perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}void SLPrint(SL* ps) {//打印assert(ps);for (int i = 0; i < ps->size; i++) {printf("%d->", ps->a[i]);}printf("NULL\n");
}void SLDestory(SL* ps) {//销毁assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}void SLPushBack(SL* ps, SLDataType x)//尾插
{assert(ps);SLCheckCapaicty(ps);ps->a[ps->size++] = x;
}
void SLPushFront(SL* ps, SLDataType x)//头插
{assert(ps);SLCheckCapaicty(ps);int end = ps->size - 1;while (end>=0) {ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;
}
void SLPopBack(SL* ps)//尾删
{assert(ps);//严格的判断assert(ps->size>0);//温柔的判断/*if (ps->size == 0) {return;}*/ps->size--;
}
void SLPopFront(SL* ps)//头删
{assert(ps);assert(ps->size > 0);int begin = 1;while (begin < ps->size) {ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}int SLFind(SL* ps, SLDataType x)//查找
{assert(ps);for (int i = 0; i < ps->size; i++) {if (ps->a[i] == x) {return i;}}return -1;
}void SLInsert(SL* ps, int pos, SLDataType x)//任意位置插入
{assert(ps);assert(pos>=0 && pos<=ps->size);SLCheckCapaicty(ps);int end = ps->size - 1;while (end>=pos) {ps->a[end + 1] = ps->a[end];--end;}ps->a[pos] = x;ps->size++;
}
void SLErase(SL* ps, int pos)//任意位置删除
{assert(ps);assert(pos >= 0 && pos < ps->size);int begin = pos + 1;while (begin < ps->size) {ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}
以上就是本期全部内容,希望大家可以有所收获
如有错误,还请指正
相关文章:

顺序表——重置版
本期我们来实现数据结构的顺序表(这个之前写过一次,不过本期和之前可能会略有不同,但大体相同),大家可以看一下我们之前完成的顺序表 (6条消息) 顺序表及其多种接口的实现_顺序表类中实现接口方法_KLZUQ的博客-CSDN博客…...
PyQt5自然语言处理入门案例笔记
前言 最近想将自然语言处理的项目进行可视化,尽量还是使用回Python语言,因此打算用PyQt来实现相应的功能。 入门案例 一个简单的自然语言处理的demo,使用PyQt框架,该demo可以读取文本文件,对文件中的文本进行情感分…...
使用 CSS 替换表行颜色?
跳到主内容 我正在使用一个带有交替行颜色的表格。 tr.d0 td {background-color: #CC9999;color: black; } tr.d1 td {background-color: #9999CC;color: black; }<table><tr class"d0"><td>One</td><td>one</td></tr>&…...

智能家居控制系统
🥁作者: 华丞臧. 📕专栏:【项目经验】 各位读者老爷如果觉得博主写的不错,请诸位多多支持(点赞收藏关注)。如果有错误的地方,欢迎在评论区指出。 推荐一款刷题网站 👉 LeetCode刷题网站…...

Linux 进程:fork()与vfork()的对比
目录一、fork函数二、vfork函数1.函数的原理2.函数的隐患3.解决函数隐患的方法在Linux的进程学习中,常使用fork函数来创建子进程,但其实还有一个vfork函数也可以创建子进程。但是这两个函数的实现机制不同,fork函数使用了写实拷贝技术&#x…...

环境搭建02-Ubuntu16.04 安装CUDA和CUDNN、CUDA多版本替换
1、CUDA安装 (1)下载需要的CUDA版本 https://developer.nvidia.com/cuda-toolkit-archive (2)安装 sudo sh cuda_8.0.61_375.26_linux.run(3)添加环境 gedit ~/.bashrc在文件末尾添加: ex…...

HOT100--(3)无重复字符的最长子串
点击查看题目详情 大思路: 创建哈希表,元素类型为<char, int>,分别是字符与其对应下标 用哈希表来存储未重复的子串,若有重复则记录下当前子串最大值maxhashsize 并且开始以相同方法记录下一子串 遍历完成以后,…...

vue keep-alive多层级路由支持
keep-alive使用 属性值 1.include - 字符串或正则表达式。只有名称匹配的组件会被缓存。 2.exclude - 字符串或正则表达式。任何名称匹配的组件都不会被缓存。 3.max - 数字。最多可以缓存多少组件实例。 注:匹配首先检查组件自身的 name 选项,如果 nam…...

从源码角度看React-Hydrate原理
React 渲染过程,即ReactDOM.render执行过程分为两个大的阶段:render 阶段以及 commit 阶段。React.hydrate渲染过程和ReactDOM.render差不多,两者之间最大的区别就是,ReactDOM.hydrate 在 render 阶段,会尝试复用(hydr…...
ARM基础 -- 2
文章目录一、可编程器件的编程原理1.1 电子器件的发展方向1.2 可编程器件的特点1.3 整个编程及运行过程二、指令集对CPU的意义2.1 汇编语言与C等高级语言的差异2.2 汇编语言的本质2.2.1 编程语言的发展过程2.2.2 汇编语言的特点和用途三、RISC和CISC的区别3.1 复杂指令集CPU --…...
Java 类型转换
Java 类型转换 int转Integer int int0 1; Integer integer1 int0; // 自动装箱 Integer integer2 new Integer(int0); Integer integer3 Integer.valueOf(int0);Integer转int Integer integer0 2; int int1 integer0; // 自动拆箱 int int2 integer0.intValue(); // …...

【Java开发】JUC基础 05:线程通信/协作
1 生产者消费者问题📌 线程通信应用的场景可以简单地描述为生产者和消费者问题假设仓库中只能存放一件产品,生产者将生产出来的产品放入仓库,消费者将仓库中产品取走消费;如果仓库中没有产品,则生产者将产品放入仓库&a…...

哪些工具可以实现在线ps的需求
在线Photoshop有哪些工具可以选择?在 Adobe 的官网上就能够实现,很惊讶吧,其实 Adobe 官方推出了在线版本的 Photoshop 的,尽管目前还是 Beta版本,但其实也开放了蛮久了。编辑切换为居中添加图片注释,不超过…...

如何使用C2concealer生成随机化的C2 Malleable配置文件
关于C2concealer C2concealer是一款功能强大的命令行工具,在该工具的帮助下,广大研究人员可以轻松生成随机化的C2 Malleable配置文件,以便在Cobalt Strike中使用。 工具运行机制 开发人员对Cobalt Strike文档进行了详细的研究,…...

网络基础之IP地址和子网掩码
一、IP地址IP地址是IP协议提供的一种统一的地址格式,它为互联网上的每一个网络和每一台主机分配一个逻辑地址,以此来屏蔽物理地址的差异。习惯上,我们用分成四段的十进制数表示IP地址,从0.0.0.0 一直到255.255.255.255。互联网上的…...

G1D54-CRF
一、CRF的输入X是什么?是构造的特征吗? 如此,CRF的x只用于状态函数吗? CRF的例子解释调用代码 机器之心 知乎忆榛 此处线性链条件随机场的特征函数形式被统一了? BilstmCRF,强烈推荐!&#x…...
vue3 使用defineAsyncComponent与component标签实现动态渲染组件
内容有些啰嗦,内容记载了当时遇到了bug以及解决问题的思路。 业务场景简述: 前端做配置化组件,通过url内的唯一标识,请求后端sql 哪取页面配置信息,前端通过配置信息动态渲染查询表单,导出、表格ÿ…...

Linux下 C/C++ NTP网络时间协议详解
NTP(Network Time Protocol,网络时间协议)是由RFC 1305定义的时间同步协议。它是通过网络在计算机系统之间进行时钟同步的网络协议。NTP 在公共互联网上通常能够保持时间延迟在几十毫秒以内的精度,并在理想条件下,它能…...

Pytest自动化框架-权威教程02-Pytest 使用及调用方法
Pytest 使用及调用方法使用python -m pytest调用pytest2.0版本新增你可以在命令行中通过Python编译器来调用Pytest执行测试:Copypython -m pytest [...]通过python调用会将当前目录也添加到sys.path中,除此之外,这几乎等同于命令行直接调用pytest [...]。可能出现的执行退出cod…...

大数据技术——概述
根据IBM前首席执行官郭士纳的观点,IT领域每隔十五年就会迎来一次重大变革三次信息化浪潮1.存储设备容量不断增加2.CPU处理能力大幅提升3.网络带宽不断增加运营式系统阶段数据库的出现使得数据管理的复杂度大大降低,数据往往伴随着一定的运营活动而产生并记录在数据库…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...

针对药品仓库的效期管理问题,如何利用WMS系统“破局”
案例: 某医药分销企业,主要经营各类药品的批发与零售。由于药品的特殊性,效期管理至关重要,但该企业一直面临效期问题的困扰。在未使用WMS系统之前,其药品入库、存储、出库等环节的效期管理主要依赖人工记录与检查。库…...
算法250609 高精度
加法 #include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; char input1[205]; char input2[205]; int main(){while(scanf("%s%s",input1,input2)!EOF){int a[205]…...
FTXUI::Dom 模块
DOM 模块定义了分层的 FTXUI::Element 树,可用于构建复杂的终端界面,支持响应终端尺寸变化。 namespace ftxui {...// 定义文档 定义布局盒子 Element document vbox({// 设置文本 设置加粗 设置文本颜色text("The window") | bold | color(…...

云原生时代的系统设计:架构转型的战略支点
📝个人主页🌹:一ge科研小菜鸡-CSDN博客 🌹🌹期待您的关注 🌹🌹 一、云原生的崛起:技术趋势与现实需求的交汇 随着企业业务的互联网化、全球化、智能化持续加深,传统的 I…...

NineData数据库DevOps功能全面支持百度智能云向量数据库 VectorDB,助力企业 AI 应用高效落地
NineData 的数据库 DevOps 解决方案已完成对百度智能云向量数据库 VectorDB 的全链路适配,成为国内首批提供 VectorDB 原生操作能力的服务商。此次合作聚焦 AI 开发核心场景,通过标准化 SQL 工作台与细粒度权限管控两大能力,助力企业安全高效…...