php模板建站/视频营销模式有哪些
顺序表的模拟实现
文章目录
- 顺序表的模拟实现
- 1.线性表
- 2.顺序表
- 2.1概念结构
- 2.2顺序表的模拟实现
- 2.2.1顺序表的初始化
- 2.2.2顺序表的销毁
- 2.2.3尾插数据
- 2.2.4尾删数据
- 2.2.5头插数据
- 2.2.6头删数据
- 2.2.7中间插入数据
- 2.2.8中间删除数据
- 2.2.9打印顺序表
- 2.2.10查找数据
- 2.2.11复用Insert和Erase实现尾部操作和头部操作
- 2.3顺序表的优缺点
- 3.顺序表OJ题目训练
1.线性表
线性表 (linear list) 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…
线性表在逻辑结构是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,
💡ps:
逻辑结构:想象的该数据结构在内存中的存储方式,逻辑结构便于我们的思考。
物理结构:实际的该数据结构在内存中的存储方式。
例如,C语言中的二维数组
int arr[M][N]
:逻辑结构:M行,N列的元素集合,不是连续存放的
物理结构:1行,M*N列的元素集合,是连续存放的
线性表在物理上存储时,通常以数组和链式结构的形式存储。
2.顺序表
2.1概念结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为:
-
静态顺序表:使用定长数组存储元素。(静态数组)
-
动态顺序表:使用动态开辟的数组存储。(malloc动态开辟空间)
2.2顺序表的模拟实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小,所以下面我们实现动态顺序表。
SeqList.h
中的声明(因为需要通过函数来修改顺序表,所以要传址)
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDateType;//顺序表的成员
typedef struct SeqList
{SLDateType* a;//顺序表的首元素地址size_t size;//顺序表的数据个数size_t capacity;//顺序表的容量
}SL;void SLInit(SL* ps);//顺序表的初始化void SLDestroy(SL* ps);//顺序表的销毁//尾部操作
void SLPushBack(SL* ps, SLDateType x);//尾插
void SLPopBack(SL* ps);//尾删//头部操作
void SLPushFront(SL* ps, SLDateType x);//头插
void SLPopFront(SL* ps);//头删//中间
size_t SLFind(SL* ps, SLDateType x);//查找(返回下标)
void SLInsert(SL* ps, size_t pos, SLDateType x);//在pos前插入数据x
void SLErase(SL* ps, size_t pos);//删除pos处的数据void SLPrint(SL* ps);//打印顺序表
SeqList.c
结构功能实现:
包含头文件#include"SeqList.h"
2.2.1顺序表的初始化
void SLInit(SL* ps)//顺序表的初始化
{assert(ps);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}
2.2.2顺序表的销毁
💡ps:由于是动态开辟的空间,使用完要还给操作系统,不然会造成内存泄漏。
void SLDestroy(SL* ps)//顺序表的销毁
{assert(ps);free(ps->a);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}
2.2.3尾插数据
void Enhance(SL* ps)
{size_t newcapacity = (ps->capacity == 0) ? 4 : ps->capacity * 2;//如果容量为0,开辟4,否则两倍开辟SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType)*newcapacity);//这里要考虑异地增容的情况if (tmp == NULL)//增容失败{perror("realloc fail\n");return;}else{ps->a = tmp;ps->capacity = newcapacity;}
}void SLPushBack(SL* ps, SLDateType x)//尾插
{assert(ps);//防止ps为空,进行断言//考虑增容if (ps->size == ps->capacity)//空间不足时需要增容{Enhance(ps);}ps->a[ps->size++] = x;
}
💡ps:顺序表插入操作都要检查是否需要增容
时间复杂度:O(1)
2.2.4尾删数据
void SLPopBack(SL* ps)//尾删
{assert(ps);assert(ps->size > 0);//顺序表为空,则不可继续再删除--(ps->size);
}
💡ps:顺序表的删除操作都要检查是是否为空顺序表
时间复杂度:O(1)
2.2.5头插数据
void SLPushFront(SL* ps, SLDateType x)//头插
{assert(ps);//考虑增容if (ps->size == ps->capacity){Enhance(ps);}//挪动数据size_t end = ps->size;while (end > 0){ps->a[end] = ps->a[end - 1];--end;}//插入数据ps->a[end] = x;++(ps->size);
}
💡ps:由于顺序表是连续存储的,在头部插入数据时,需要将整体数据向后挪动一次,再将数据插入到头部
时间复杂度:O(N)
2.2.6头删数据
void SLPopFront(SL* ps)//头删
{assert(ps);assert(ps->size > 0);//挪动数据--(ps->size);size_t begin = 0;while (begin < ps->size){ps->a[begin] = ps->a[begin + 1];++begin;}}
💡ps:头删数据,将后面的数据向前移动,将第一个数据覆盖即可
时间复杂度:O(N)
2.2.7中间插入数据
void SLInsert(SL* ps, size_t pos, SLDateType x)//中间插
{assert(ps);assert(pos >= 0 && pos <= ps->size);//==0是头插,等于ps->size是尾插//考虑增容if (ps->size == ps->capacity){Enhance(ps);}//挪动数据size_t cur = ps->size;while (cur > pos){ps->a[cur] = ps->a[cur - 1];--cur;}//插入ps->a[cur] = x;++(ps->size);}
💡ps:中间插入数据,同样也需要向后挪动数据
时间复杂度:O(N)
2.2.8中间删除数据
void SLErase(SL* ps, size_t pos)//中间删
{assert(ps);assert(pos >= 0 && pos < ps->size);//等于0相等于头删,等于ps->size-1等于尾删//assert(ps->size > 0);//对pos的检查,间接检查了size要大于0--(ps->size);size_t cur = pos;while (cur < ps->size){ps->a[cur] = ps->a[cur + 1];++cur;}
}
💡ps:中间删除数据,同样也需要向前挪动数据
时间复杂度:O(N)
2.2.9打印顺序表
void SLPrint(const SL* ps)//打印顺序表
{assert(ps);for (size_t i = 0; i < ps->size; ++i){printf("%d ", ps->a[i]);}printf("\n");
}
2.2.10查找数据
size_t SLFind(const SL* ps, SLDateType x)//查找(返回下标)
{assert(ps);for (size_t i = 0; i < ps->size; ++i){if (ps->a[i] == x){return i;}}return EOF;//找不到
}
2.2.11复用Insert和Erase实现尾部操作和头部操作
Insert
和Erase
功能中是包含了尾部操作和头部操作的,所以尾部操作和头部操作可以使用Insert
和Erase
来复用
void SLPushBack(SL* ps, SLDateType x)//尾插
{SLInsert(ps, ps->size, x);
}void SLPopBack(SL* ps)//尾删
{SLErase(ps, ps->size - 1);
}void SLPushFront(SL* ps, SLDateType x)//头插
{SLInsert(ps, 0, x);
}void SLPopFront(SL* ps)//头删
{SLErase(ps, 0);
}
2.3顺序表的优缺点
优点:
1. 尾插和尾删的效率很高,时间复杂度为:O(1)
2. 支持随机访问,知道了一个元素的下标,就可以直接访问和修改
缺点:
1. 头部操作和中间操作中,需要挪动数据,时间复杂度为:O(N),效率较低
2. 增容会带来一定的性能消耗,特别是异地增容,代价是极大的
3. 2倍增容方式,会有一部分的空间浪费
3.顺序表OJ题目训练
- 原地移除数组中所有的元素val,要求时间复杂度为O(N),空间复杂度为O(1)。OJ链接
- 删除排序数组中的重复项。OJ链接
- 合并两个有序数组。OJ链接
相关文章:

【数据结构】顺序表:尾部操作我很行,随机访问我超快!!!
顺序表的模拟实现 文章目录顺序表的模拟实现1.线性表2.顺序表2.1概念结构2.2顺序表的模拟实现2.2.1顺序表的初始化2.2.2顺序表的销毁2.2.3尾插数据2.2.4尾删数据2.2.5头插数据2.2.6头删数据2.2.7中间插入数据2.2.8中间删除数据2.2.9打印顺序表2.2.10查找数据2.2.11复用Insert和…...

SQL优化
SQL优化 SQL优化的方法: sql查询语句尽不使用select * ,而是具体的字段。 节约资源,减少网络开销。减少回表,提高查询效率。 避免在where子句中使用or来连接条件。 or可能会使索引失效,从而进行全表查询。 尽量使用…...

Java ArrayList 和 LinkList 原理对比
Java 中的 ArrayList 和 LinkedList 都是实现了 List 接口的集合类它们都允许添加、删除和修改元素。但是它们的底层实现原理不同导致它们在不同的场景下拥有不同的优劣势。 ArrayListArrayList 的底层是通过数组实现的因此它具有数组的特性。它允许快速随机访问元素但是在插入…...

【Spring】入门概述(一)
🚗Spring学习第一站~ 🚩本文已收录至专栏:Spring家族学习之旅 👍希望您能有所收获 一.初识 Spring并不是单一的一个技术,而是一个大家族,发展到今天已经形成了一种开发的生态圈,Spring提供了若…...

十二、面向切面编程AOP
IoC使软件组件松耦合。AOP让你能够捕捉系统中经常使用的功能,把它转化成组件。 AOP(Aspect Oriented Programming):面向切面编程,面向方面编程。(AOP是一种编程技术) AOP是对OOP的补充延伸。 …...

Mybatis 处理 CLOB/BLOB 类型数据
Mybatis 处理 CLOB/BLOB 类型数据 BLOB 和 CLOB 都是大型字段类型。 BLOB通过二进制存储,而CLOB可以直接存储文本。 通常,图片、文件、音乐等信息存储在 BLOB 字段中。首先,文件是转换为二进制,然后存储在。文章或较长的文本存…...

【NLP经典论文阅读】Efficient Estimation of Word Representations in Vector Space(附代码)
❤️觉得内容不错的话,欢迎点赞收藏加关注😊😊😊,后续会继续输入更多优质内容❤️👉有问题欢迎大家加关注私戳或者评论(包括但不限于NLP算法相关,linux学习相关,读研读博…...

Spring bean生命周期分为几个阶段?
bean 的生命周期从调用 beanFactory 的 getBean 开始,到这个 bean 被销毁,可以总结为以下七个阶段:处理名称,检查缓存→处理父子容器→处理 dependsOn→选择 scope 策略→创建 bean→类型转换处理→销毁 bean划分的阶段和名称并不…...

【基础算法】单链表的OJ练习(4) # 分割链表 # 回文链表 #
文章目录前言分割链表回文链表写在最后前言 本章的OJ练习相对前面的难度加大了,但是换汤不换药,还是围绕单链表的性质来出题的。我相信,能够过了前面的OJ练习,本章的OJ也是轻轻松松。 对于OJ练习(3):-> 传送门 <…...

SpringBoot整合定时任务和邮件发送(邮箱 信息轰炸 整蛊)
SpringBoot整合定时任务和邮件发送(邮箱 信息轰炸 整蛊) 目录SpringBoot整合定时任务和邮件发送(邮箱 信息轰炸 整蛊)1.概述2.最佳实践2.1创建项目引入依赖(mail)2.2 修改yml配置文件2.3 启动类添加EnableScheduling注解2.4 执行的…...

Arduino添加ESP32开发板
【2023年3月4日】 最近要在新电脑上安装Arduino,需要进行一些配置,正好记录一下! Arduino2.0.1 下的开发板添加操作。 ESP32开发板GitHub链接: GitHub - espressif/arduino-esp32: Arduino core for the ESP32Arduino core for…...

Mysql通配符的使用
LIKE操作符 通配符:用来匹配值的一部分的特殊字符。 搜索模式:由字面值,通配符或两者组合构成的搜索条件。 百分号(%)通配符 搜索模式使用例如下 SELECT prod_id, prod_name FROM products WHERE prod_name Like jet%; 这条子句表示&…...

RocketMQ-02
1. 案例介绍 1.1 业务分析 模拟电商网站购物场景中的【下单】和【支付】业务 ###1)下单 用户请求订单系统下单订单系统通过RPC调用订单服务下单订单服务调用优惠券服务,扣减优惠券订单服务调用调用库存服务,校验并扣减库存订单服务调用用户…...

深度学习卷积神经网络CNN之 VGGNet模型主vgg16和vgg19网络模型详解说明(理论篇)
1.VGG背景 2. VGGNet模型结构 3. 特点(创新、优缺点及新知识点) 一、VGG背景 VGGNet是2014年ILSVRC(ImageNet Large Scale Visual Recognition Challenge大规模视觉识别挑战赛)竞赛的第二名,解决ImageNet中的1000类图…...

三:BLE协议架构简介
低功耗蓝牙体系整体架构说明1. PHY(物理层)2. LL(链路层)3. HCI(主机与控制器通信接口)4. L2CAP(逻辑链路控制及适配协议)5. ATT(属性协议)6. GATT(通用属性规范)7. GAP(通用访问规范)8. SM(安全管理)整体架构说明 架构层说明PHY1. 物理层2. 控制射频的发送和接收LL1. 链路层2.…...

小型双轮差速底盘双灰度循迹功能的实现
1. 功能说明 在机器人车体上安装2个 灰度传感器 ,实现机器人按照下图所指定的路线进行导航运动,来模拟仓库物流机器人按指定路线行进的工作过程。 2. 使用样机 本实验使用的样机为R023e样机。 3. 功能实现 3.1 电子硬件 在这个示例中,我们采…...

电子签名?玩具罢了!
需要的前置知识:简单的canvas绘制线路过程 let canvas document.getElementById(id); //id为canvas标签元素的id,或通过其它方法获取标签 let ctx canvas.getContext(2d); //规定为2d绘制图片,即确定为2d画笔 ctx.strokeStyle "whit…...

【Spring Boot读取配置文件的方式】
Spring Boot 支持多种读取配置文件的方式,常用的方式有以下三种: application.properties: Spring Boot 默认会读取该文件作为应用的配置文件。可以在 src/main/resources 目录下创建该文件,并在其中配置应用的属性。 applicat…...

java学习路线规划
java学习路线规划 一、写在前面 兄弟,我整理了一下关于自己之前学习java的一些方向,给你归纳在这里,有空就来看看,希望对你有帮助。 二、java基础篇 1、认识java 了解java历史,大概看看发展史,安装…...

格密码学习笔记(二):连续极小、覆盖半径和平滑参数
文章目录最短距离和连续极小值距离函数和覆盖半径格的平滑参数致谢最短距离和连续极小值 除了行列式,格的另一个基本量是格上最短非零向量的长度,即格中最短距离,其定义为 λ1minx,y∈L,x≠y∥x−y∥minz∈L,z≠0∥z∥.\begin{aligned} …...

ios 通过搜索设备MAC地址绑定
最近做了一个物联网项目,涉及到了设备绑定配网这块,需要了解一下iOS BLE与设备绑定的相关知识点,第一次接触蓝牙相关的项目,所以开始熟悉蓝牙的相关信息。没有去深入研究BabyTooth库,只是感觉CoreBluetooth已经让我更好的理解整个流程这个物联网项目的设备绑定流程是…...

Python实现人脸识别,进行视频跟踪打码,羞羞的画面统统打上马赛克
哈喽兄弟们,我是轻松~ 今天我们来实现用Python自动对视频打马赛克前言准备工作代码实战效果展示最后前言 事情是这样的,昨天去表弟家,用了下他的电脑,不小心点到了他硬盘里隐藏的秘密,本来我只需要用几分钟电脑的&…...

vcf bed起始位置是0还是1
VCF 起始位置为1, POS - position: The reference position, with the 1st base having position 1. Positions are sorted numerically, in increasing order, within each reference sequence CHROM. It is permitted to have multiple records with the same POS. Telome…...

Hexo+live2d | 如何把live2d老婆放进自己的博客
参考:Hexo添加Live2D看板娘最新教程live2d-widgetlive2d-widget-models网页/博客Hexo添加live2d游戏角色看板娘,简易添加,碧蓝航线等live2d新型游戏角色模型(moc3)live2d-moc3jsdelivr方法1可以直接去看参考文章的第一部分的第一篇…...

【微信小程序】-- 页面导航 -- 导航传参(二十四)
💌 所属专栏:【微信小程序开发教程】 😀 作 者:我是夜阑的狗🐶 🚀 个人简介:一个正在努力学技术的CV工程师,专注基础和实战分享 ,欢迎咨询! &…...

Pytorch学习笔记#2: 搭建神经网络训练MNIST手写数字数据集
学习自https://pytorch.org/tutorials/beginner/basics/quickstart_tutorial.html 导入并预处理数据集 pytorch中数据导入和预处理主要用torch.utils.data.DataLoader 和 torch.utils.data.Dataset Dataset 存储样本及其相应的标签,DataLoader在数据上生成一个可迭…...

C语言 猜名次、猜凶手、杨辉三角题目详解
猜名次题目:5位运动员参加了10米台跳水比赛,有人让他们预测比赛结果:A选手说:B第二,我第三;B选手说:我第二,E第四;C选手说:我第一,D第二ÿ…...

蚁群算法负荷预测
%% 清空环境变量 clc clear close all format compact %% 网络结构建立 %% 清空环境变量 clc clear close all format compact %% 网络结构建立 %读取数据 dataxlsread(天气_电量_数据.xlsx,C12:J70);%前7列为每个时刻的发电量 最后列为天气 for i1:58 input(i,:)[data…...

ubuntu添加系统服务实现开机root权限运行
需求 开机自动运行程序(或脚本),需要以root权限运行但不输入密码,也不能将密码写入文件。 环境 Ubuntu 20.04 解决方案 添加系统服务,然后通过systemctl控制。 操作步骤 假设目标程序为/home/xxx/test 1、创建service配置文件 [Unit…...

【阅读笔记】你不知道的Javascript--类与类型委托3
目录类一些常见原理混入行为委托委托理论类与对象更妙的设计与语法类型冷门关键词typeof 防范机制值原生函数访问内部属性类 一些常见原理 在继承或者实例化时,JavaScript 的对象机制并不会自动执行复制行为; 多态:JS 中的多态,…...