二.线性表之顺序表
文章目录
- 前言
- 一.顺序表的概念及结构
- 二.顺序表的接口实现
- 1.顺序表的动态存储
- 2.顺序表的初始化
- 3.顺序表尾插
- #封装:扩容函数
- 4.顺序表尾删
- 5.顺序表头插
- 6.顺序表头删
- 7.顺序表查找
- 8.顺序表在pos位置插入x
- 9.顺序表删除pos位置的值
- 10.顺序表销毁
- 11.顺序表打印
- 三.源
- 1.Seqlist.h
- 2.Seqlist.c
- 四.顺序表的问题及思考
前言
线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储:
一.顺序表的概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为:
- 静态顺序表:使用定长数组存储元素。
#define N 7
typedef int SlDataType;
typedef struct Seqlist
{SlDataType array[N]; //定长数组size_t size; //有效数据个数
}Seqlist;
2. 动态顺序表:使用动态开辟的数组存储。
二.顺序表的接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小,下面我们来实现动态顺序表:
1.顺序表的动态存储
typedef int SLDataType; //可以是int,double,结构体,按照要求来
#define INIT_CAPACITY 4 //初始化大小为4typedef struct Seqlist
{SLDataType* a; //指向存放数据的每一个内存空间int size; //有效数据个数int capacity; //空间容量
}SL;
顺序表的长度是不固定的,可增容的,所以要用指针指向每一块信息空间。
2.顺序表的初始化
void SLInit(SL* pc)
{assert(pc);//1.强制转化类型 2.分配的是字节:sizeof(SLDataType) * INIT_CAPACITYpc->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY); //刚开始分配4个if (pc->a == NULL){perror("malloc");return;}pc->size = 0;pc->capacity = INIT_CAPACITY;
}
采用动态分配内存的方式,进行初始化
3.顺序表尾插
void SLPushBack(SL* pc, SLDataType x)
{assert(pc);//检查是否扩容if (pc->size == pc->capacity){SLDataType* tmp = (SLDataType*)realloc(pc->a, sizeof(SLDataType) * pc->capacity * 2);if (tmp == NULL){printf("realloc");return;}pc->a = tmp;pc->capacity *= 2;}//pc->size记录的是当前表中数据的下一位,直接赋值给该位赋值即可pc->a[pc->size++] = x;
}
注意:
- realloc函数是按照字节调整大小,所以一定要记得用sizeof 计算类型的字节大小。
- pc->a[pc->size++] = x的具体含义如下:
改进:上面尾插数据时我们需要检查是否扩容,不如就把扩容函数单独封装,后面再需要检查扩容的时候直接调用该函数即可:
#封装:扩容函数
void SLCheckCapacity(SL* pc)
{assert(pc);//检查是否扩容if (pc->size == pc->capacity){//有可能异地扩容,再新定义一个指针SLDataType* tmp = (SLDataType*)realloc(pc->a, sizeof(SLDataType) * pc->capacity * 2);if (tmp == NULL){printf("relloc");return;}pc->a = tmp;pc->capacity *= 2;}
}
这样尾插函数就可以简化为:
void SLPushBack(SL* pc, SLDataType x)
{//assert(pc);检查是否扩容//if (pc->size == pc->capacity)//{// //有可能异地扩容,再新定义一个指针// SLDataType* tmp = (SLDataType*)realloc(pc->a, sizeof(SLDataType) * pc->capacity * 2);// if (tmp == NULL)// {// printf("relloc");// return;// }// pc->a = tmp; // pc->capacity *= 2;//}SLCheckCapacity(pc);pc->a[pc->size++] = x;
}
4.顺序表尾删
void SLPopBakc(SL* pc)
{//暴力的检查//assert(pc->size > 0);//温柔的检查if (pc->size == 0)return;pc->size--;
}
注意:
- 当size删到0的时候,我们就没法再删除元素了,否则会出问题,所以在删除元素的时候需要特判一下size的大小,可以用断言assert,也可以用if语句。
- **pc->size- -;**的意思是顺序表中元素数量减一,也就是删掉了尾部元素。
5.顺序表头插
//头插
void SLPushFront(SL* pc,SLDataType x)
{assert(pc);SLCheckCapacity(pc);int end = pc->size - 1; while (end >= 0){//从最后一位开始,整体把数据后移一位pc->a[end + 1] = pc->a[end];--end;}pc->a[0] = x;pc->size++;
}
为了给开头腾出位置,需要将数据整体先向后移动一位:
从最后一位开始移动,防止数据被覆盖
6.顺序表头删
//头删
void SLPopFront(SL* pc)
{assert(pc);assert(pc->size > 0); //保证有数据int begin = 1;while (begin < pc->size){pc->a[begin - 1] = pc->a[begin];}pc -> size--;
}
删除头部数据前先判断表中是否有数据,表里没东西固然不能硬删。删头元素时是把头元素后面的数据全部往前挪一位,整体覆盖前一个数据,相当于删除了头部元素:
从第二个开始往前挪,防止提前被覆盖。
7.顺序表查找
//查找
int SLFind(SL* pc, SLDataType x)
{assert(pc);for (int i = 0; i < pc->size; i++){if (pc->a[i] == x){return i;}}return -1;
}
直接遍历一遍查找即可
8.顺序表在pos位置插入x
//任意位置插入
void SLInsert(SL* pc, int pos, SLDataType x)
{assert(pc);assert(pos >= 0 && pos <= pc->size);SLCheckCapacity(pc);int end = pc->size - 1;while (end >= pos){pc->a[end + 1] = pc->a[end];end--;}pc->a[pos] = x;pc->size++;
}
与头插法想法类似,把pos后面的数据整体向后挪动一位,给pos腾出位置来,放入新的值x:
改进:当pos=0的时候其实就是头插,当pos=pc->size的时候就是尾插
所以我们可以只用一个在任意位置插入的SLInsert函数实现所有位置的数据插入:
①尾插:
void SLPushBack(SL* pc, SLDataType x)
{//assert(pc);检查是否扩容//if (pc->size == pc->capacity)//{// //有可能异地扩容,再新定义一个指针// SLDataType* tmp = (SLDataType*)realloc(pc->a, sizeof(SLDataType) * pc->capacity * 2);// if (tmp == NULL)// {// printf("relloc");// return;// }// pc->a = tmp; // pc->capacity *= 2;//}/*SLCheckCapacity(pc);pc->a[pc->size++] = x;*/SLInsert(pc, pc->size, x);
}
②头插
void SLPushFront(SL* pc, SLDataType x)
{//assert(pc);//SLCheckCapacity(pc);//int end = pc->size - 1; //while (end >= 0)//{// //从最后一位开始,整体把数据后移一位// pc->a[end + 1] = pc->a[end];// --end;//}//pc->a[0] = x;//pc->size++;SLInsert(pc, 0, x);
}
这又能进一步使代码变得简洁
9.顺序表删除pos位置的值
//任意位置删除
void SLErase(SL* pc, int pos)
{assert(pc);assert(pc >= 0 && pos < pc->size); //size指向当前数据的下一位,还没有存放数据,所以没东西可删,要注意与任意位置插入的代码区分int begin = pos + 1;while (begin < pc->size){pc->a[begin - 1] = pc->a[begin];begin++;}pc->size--;
}
与头删法类似,采用从pos后往前覆盖的思想,把pos存的数据覆盖住:
改进:当pos=0时就是头删,当pos=pc->size-1时就是尾删,这样我们可以只用该函数实现任意位置的删除
①尾删:
void SLPopBakc(SL* pc)
{//assert(pc);暴力的检查//assert(pc->size > 0);//温柔的检查//if (pc->size == 0)// return;//pc->size--;SLErase(pc, pc->size - 1);
}
②头删
//头删
void SLPopFront(SL* pc)
{//assert(pc);//assert(pc->size > 0); //保证有数据//int begin = 1;//while (begin < pc->size)//{// pc->a[begin - 1] = pc->a[begin];//}//pc -> size--;SLErase(pc, 0);
}
使代码更简洁。
10.顺序表销毁
void SLDestory(SL* pc)
{free(pc->a);pc->a = NULL;pc->capacity = pc->size = 0;
}
由于空间都是动态分配的,所以销毁的时候直接free掉,free后的指针记得置空。
11.顺序表打印
void SLPrint(SL* pc)
{for (int i = 0; i < pc->size; i++){printf("%d", pc->a[i]);}printf("\n");
}
三.源
1.Seqlist.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//typedef int SLDataType;
//#define N 100000
//
静态顺序表 -- 开少了不够用 开多了浪费
//struct SeqList
//{
// SLDataType a[N];
// int size;
//};typedef int SLDataType;
#define INIT_CAPACITY 4// 动态顺序表 -- 按需申请
typedef struct SeqList
{SLDataType* a;int size; // 有效数据个数int capacity; // 空间容量
}SL;// 增删查改
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
void SLCheckCapacity(SL* ps);void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);
2.Seqlist.c
#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 SLDestroy(SL* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}
//打印数据
void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; ++i){printf("%d ", ps->a[i]);}printf("\n");
}
//检查扩容
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}//尾插
void SLPushBack(SL* ps, SLDataType x)
{//assert(ps); 扩容//SLCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;//ps->a[ps->size++] = x;SLInsert(ps, ps->size, x);
}
//尾删
void SLPopBack(SL* ps)
{//assert(ps); 暴力检查//assert(ps->size > 0); 温柔的检查if (ps->size == 0)// //return;ps->a[ps->size - 1] = 0;//ps->size--;SLErase(ps, ps->size-1);
}
//头插
void SLPushFront(SL* ps, SLDataType x)
{/*assert(ps);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->a[end + 1] = ps->a[end];--end;}ps->a[0] = x;ps->size++;*/SLInsert(ps, 0, x);
}
//头删
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--;SLErase(ps, 0);
}
//任意位置插入
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheckCapacity(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--;
}
//查找
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;
}
四.顺序表的问题及思考
- 中间或头部的插入删除,时间复杂度为O(N)
- 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。
要解决上述问题,就要用到链表的知识了,我们下一篇再见!!
码文不易,还请多多支持哦!!
相关文章:

二.线性表之顺序表
文章目录前言一.顺序表的概念及结构二.顺序表的接口实现1.顺序表的动态存储2.顺序表的初始化3.顺序表尾插#封装:扩容函数4.顺序表尾删5.顺序表头插6.顺序表头删7.顺序表查找8.顺序表在pos位置插入x9.顺序表删除pos位置的值10.顺序表销毁11.顺序表打印三.源1.Seqlist…...
ElasticSearch - SpringBoot整合ElasticSearch实现文档的增删改
文章目录1. ElasticSearch和kibana的安装和配置2. SpringBoot 项目环境搭建3. 创建索引4. 索引文档5. 更新文档6. 删除文档https://www.elastic.co/guide/en/elasticsearch/reference/current/search-your-data.htmlhttps://www.elastic.co/guide/cn/elasticsearch/guide/curre…...

JavaScript 库
文章目录JavaScript 库JavaScript 框架(库)jQueryPrototypeMooTools其他框架CDN -内容分发网络引用 jQuery使用框架JavaScript 库 JavaScript 库 - jQuery、Prototype、MooTools。 JavaScript 框架(库) JavaScript 高级程序设计…...
云解析DNS为什么要配置默认线路?
传统解析技术不会判断访客IP,而是会随机选择一个IP返回给访问者,这样就有可能造成移动用户访问电信服务器IP,北京用户访问深圳服务器IP这种跨域跨网访问的情况,产生非常大的延迟,带来很不好的访问体验。 而云解析DNS会…...

Linux命令之awk
awk是一个有强大的文本格式化能力的linux命令,早期是在Unix上实现的,linux后来也可以使用了,我们在Linux上使用的awk是gawk(GNU awk的意思) 语法 awk [option] 模式{动作} file option表示awk的可选参数,可…...

实战-缓存数据一致+binlog初始+cannel监听+数据迁移,数据一致性架构设计
前言 一. 解决缓存不命中(高并发操作击穿打挂DB的风险) 当并发量打的时候,当我们的缓存过期时,就算到数据库的比例偏小的时候,我们的请求时比较大的。那也会存在数据库崩掉的情况。解决方案想法如下(总体…...
nginx配置中proxy_pass反向代理502的bug
记录一个坑人的bug, 我今天在一台新的liunx上运行nginx来进行反向代理时候,发现怎么测都是502 我把配置全部删了从头开始配置,发现80端口正常,80端口index.html正常,反向代理转向http://127.0.0.1/也正常,…...

JavaScript 两种方案打开文件对话框
JavaScript 两种方案打开文件对话框 文章目录JavaScript 两种方案打开文件对话框一、文件对话框二、传统方案表单元素🌈三、文件系统访问API💦四、更进一步使用六、代码仓库🌐七、参考资料💘七、推荐博文🍗一、文件对话…...

Pycharm远程服务器常见问题
2023年02月23日 问题描述:Pycharm远程服务器跑代码时,不小心把Pycharm关掉了,但服务器代码还在运行? 解决办法:kill进程 先用watch -n 0.5 nvidia_smi查看进程,然后kill -9 <进程> 1、nvidia-smi…...

内容团队如何快速出稿
对于内容团队而言,每个内容选题就相当于一个小项目,它们并非简单的线性工作流,相反其复杂程度不亚于一个小型工厂。一个内容选题会涉及内容形式,选题类型等多个变量,这些变量因素组合起来就是十几种不同类型的工作流。…...
es-08索引的批量操作
索引的批量操作 批量查询和批量增删改 批量查询 GET /_mget#批量查询 GET product/_search GET /_mget {"docs": [{"_index": "product","_id": 2},{"_index": "product","_id": 3}] }GET product/_mge…...

诈金花的概率
游戏使用一副除去大小王的扑克牌,共4个花色52张牌。 1、豹子(AAA最大,222最小)。2、同花顺(AKQ最大,A23最小)。3、同花(AKQ最大,352最小)。4、顺子ÿ…...

ESP32设备驱动-MLX90393磁场传感器驱动
MLX90393磁场传感器驱动 文章目录 MLX90393磁场传感器驱动1、MLX90393介绍2、硬件准备3、软件准备4、驱动实现1、MLX90393介绍 MLX90393 磁场传感器可以在运行时重新编程为不同的模式和不同的设置。 该传感器使用 Melexis 专有的 Triaxis 技术提供与沿 XYZ 轴感应的磁通密度成…...

Java面试题-Spring框架
Spring框架 1. BeanFactory和ApplicationContext有何区别 BeanFactory是Spring最底层的接口,是IoC的核心,定义IoC的基本功能。 BeanFactory具有:延迟实例化的特性。在启动的时候,不会实例化Bean,只有有需要从容器…...
【计算机物理模拟】-力矩、转动惯量和角速度之间的关系
力矩和角速度之间的关系可以通过牛顿第二定律和角动量定理来描述。 牛顿第二定律表明,物体的加速度与作用在物体上的合力成正比,加速度的方向与合力的方向相同。而对于旋转运动的物体,其加速度可以表示为半径 rrr 乘以角加速度 α\alphaα&a…...

async和await用法理解和快速上手 , 同步任务和异步任务顺序安排和轻松理解 , js代码执行顺序表面知道
学习关键语句 : async , await 用法 await 怎么使用 同步任务和异步任务 微任务和宏任务 js中代码执行顺序 写在前面 虽然说 async 和 await 是 Promise 的语法糖 , 但是用惯了Promise 的人(我) , 还真不能超快速使用上这个语法糖 , 所以赶紧写一篇文章出来让各位了解了解这个…...

Linux下java服务占用cpu过高如何处理
Linux下java服务占用cpu过高如何处理 top命令查看进程信息 top按下shiftp,按cpu使用率排行,可见进程1932占用最高,并且是一个java服务 使用jps命令确认java服务 [rootVM-16-16-centos ~]# jps 1011 Jps 9462 yuan_back-0.0.1-SNAPSHOT.jar 1932 spigot-1.18.jar查找异常进程中…...

ros下用kinectv2运行orbslam2
目录 前提 创建工作空间 orbslam2源码配置、测试: 配置usb_cam ROS功能包 配置kinect 前提 vim 、 cmake 、 git 、 gcc 、 g 这些一般都装了 主要是Pangolin 、 OpenCV 、 Eigen的安装 18.04建议Pangolin0.5 创建工作空间 我们在主目录下创建一个catkin_…...

MVP简单模型搭建【架构】
MVP简介 MVP是一种项目架构设计模式(说白了就是我们产品的一种设计方案) 其实MVP本质 就是将View和Model完全隔离,通过Presenter统一调度管理(Presenter扮演着中介的角色)传统的设计思路是我们直接跟房东谈࿰…...

若依ruoyi框架实现目录树与查询页面联动
目录1、业务场景2、前端api.js修改index.vue修改template修改script修改3、后端controllerserviceimpldomainentitytreeselect1、业务场景 后管页面实现目录数与查询页面的联动,类似若依框架用户管理页面。 2、前端 api.js修改 在原有的js文件里配置目录树的查…...

基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...