当前位置: 首页 > news >正文

【数据结构】顺序表和链表——顺序表(包含丰富算法题)

文章目录

  • 1. 线性表
  • 2. 顺序表
    • 2.1 概念与结构
    • 2.2 分类
      • 2.2.1 静态顺序表
      • 2.2.2 动态顺序表
    • 2.3 动态顺序表的实现
    • 2.4 顺序表算法题
      • 2.4.1 移除元素
      • 2.4.2 删除有序数组中的重复项
      • 2.4.3 合并两个有序数组
    • 2.5 顺序表问题与思考

1. 线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表有:顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构,也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的, 线性表在物理上存储时,通常以数组和链式结构的形式存储。

2. 顺序表

2.1 概念与结构

概念:顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。

在这里插入图片描述

顺序表和数组的区别?

顺序表的底层结构是数组,对数组的封装,实现了常用的增删改查等接口

在这里插入图片描述

2.2 分类

2.2.1 静态顺序表

概念:使用定长数组存储元素

在这里插入图片描述

静态顺序表缺陷:空间给少了不够用,给多了造成空间浪费

2.2.2 动态顺序表

概念:使用动态开辟的连续空间存储元素

在这里插入图片描述

2.3 动态顺序表的实现

SeqList.h

#define INIT_CAPACITY 4
typedef int SLDataType;
// 动态顺序表 -- 按需申请
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);

[!NOTE]

💡 代码小提示

编写代码过程中要勤测试,写一部分测试一部分,避免写出大量代码后再测试而导致出现问题,问题定位无从下手。

2.4 顺序表算法题

2.4.1 移除元素

https://leetcode.cn/problems/remove-element/description/

2.4.2 删除有序数组中的重复项

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

2.4.3 合并两个有序数组

https://leetcode.cn/problems/merge-sorted-array/description/

2.5 顺序表问题与思考

  • 中间/头部的插入删除,时间复杂度为 O ( N ) O(N) O(N)

  • 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。

  • 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200。

我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。

思考:如何解决以上问题呢?
❤️❤️❤️之后的博客内容将会进行讲解❤️❤️❤️

相关文章:

【数据结构】顺序表和链表——顺序表(包含丰富算法题)

文章目录 1. 线性表2. 顺序表2.1 概念与结构2.2 分类2.2.1 静态顺序表2.2.2 动态顺序表 2.3 动态顺序表的实现2.4 顺序表算法题2.4.1 移除元素2.4.2 删除有序数组中的重复项2.4.3 合并两个有序数组 2.5 顺序表问题与思考 1. 线性表 线性表(linear list)…...

pod基础和镜像拉取策略

目录 pod概念 pod的分类 1.基础容器 pause 2.初始化容器 init 实验:定义初始化容器 init容器的作用 实验:如何在容器内部进行挂载 镜像拉取策略 pod概念 pod是k8s里面的最小单位,pod也是最小化运行容器的资源对象。容器是基于pod在k…...

53 mysql pid 文件的创建

前言 接上一篇文章 mysql 启动过程中常见的相关报错信息 在 mysql 中文我们在 “service mysql start”, “service mysql stop” 经常会碰到 mysql.pid 相关的错误信息 比如 “The server quit without updating PID file” 我们这里来看一下 mysql 中 mysql.pid 文件的…...

前端---对MVC MVP MVVM的理解

就需要从前端这些年的从无到有、从有到优的变迁过程讲一下。 1. Web1.0时代 在web1.0时代并没有前端的概念,开发一个web应用多数采用ASP.NET/Java/PHP编写,项目通常用多个aspx/jsp/php文件构成,每个文件中同时包含了HTML、CSS、JavaScript、…...

深度学习 --- VGG16能让某个指定的feature map激活值最大化图片的可视化(JupyterNotebook实战)

VGG16能让某个指定的feature map激活值最大化图片的可视化 在前面的文章中,我用jupyter notebook分别实现了,预训练好的VGG16模型各层filter权重的可视化和给VGG16输入了一张图像,可视化VGG16各层的feature map。深度学习 --- VGG16卷积核的可…...

1990-2022年各地级市gdp、一二三产业gdp及人均gdp数据

1990-2022年各地级市gdp、一二三产业gdp及人均gdp数据 1、时间:1990-2022年 2、来源:城市统计年鉴 3、指标:年度、城市名称、城市代码、城市类别、省份标识、省份名称、国内生产总值/亿元、第一产业占GDP比重(%)、第二产业占GDP比重(%)、第…...

c++ 原型模式

文章目录 什么是原型模式为什么要使用原型模式使用场景示例 什么是原型模式 用原型实例指定创建对象的种类,并通过拷贝这些原型创建新的对象,简单理解就是“克隆指定对象” 为什么要使用原型模式 原型模式(Prototype Pattern)是…...

论tomcat线程池和spring封装的线程池

Tomcat 中的线程池是什么? 内部线程池:Tomcat 确实有一个内部的线程池,用于处理 HTTP 请求,通常是org.apache.tomcat.util.threads.ThreadPoolExecutor 类的实例。这个线程池专门用于处理进入的 HTTP 请求和发送响应。可以通过 T…...

阿里P7大牛整理自动化测试高频面试题

最近好多粉丝咨询我,有没有软件测试方面的面试题,尤其是Python自动化测试相关的最新面试题,所以今天给大家整理了一份,希望能帮助到你们。 接口测试基础 1、公司接口测试流程是什么? 从开发那边获取接口设计文档、分…...

vue如何实现路由缓存

&#xff08;以下示例皆是以vue3vitets项目为例&#xff09; 场景一&#xff1a;所有路由都可以进行缓存 在渲染路由视图对应的页面进行缓存设置&#xff0c;代码如下&#xff1a; <template><router-view v-slot"{ Component, route }"><transiti…...

基于Openjdk容器打包运行jar程序

文章目录 应用场景基于Openjdk容器打包运行jar程序1.编译项目成jar包2.构建Dockerfile文件精简版-含jar包精简版-不含jar包带注释版-含jar包 3.编译Dockerfile成镜像。4.运行镜像&#xff1a; 应用场景 部署多版本jdk的应用程序。 基于Openjdk容器打包运行jar程序 1.编译项目…...

DNN学习平台(GoogleNet、SSD、FastRCNN、Yolov3)

DNN学习平台&#xff08;GoogleNet、SSD、FastRCNN、Yolov3&#xff09; 前言相关介绍1&#xff0c;登录界面&#xff1a;2&#xff0c;主界面&#xff1a;3&#xff0c;部分功能演示如下&#xff08;1&#xff09;识别网络图片&#xff08;2&#xff09;GoogleNet分类&#xf…...

HTTP协议(超文本传输协议)

HTTP请求消息 http请求消息组成&#xff1a; 请求行 &#xff1a;包含请求的方法 操作资源的地址 协议的版本号 http请求方法&#xff1a; GET&#xff1a;从服务器获取资源 POST&#xff1a;添加资源信息 PUT&#xff1a;请求服务器更新资源信息 DELETE&#xff1a;请…...

FFmpeg的日志系统(ubuntu 环境)

1. 新建.c文件 vim ffmpeg_log.c2. 输入文本 #include<stdio.h> #include<libavutil/log.h> int main() {av_log_set_level(AV_LOG_DEBUG);av_log(NULL,AV_LOG_INFO,"hello world");return 0; }当log level < AV_LOG_DEBUG 都可以印出来 #define A…...

浅析VO、DTO、DO、PO

一、概念介绍 POJO&#xff08;plain ordinary java object&#xff09; &#xff1a; 简单java对象&#xff0c;个人感觉POJO是最常见最多变的对象&#xff0c;是一个中间对象&#xff0c;也是我们最常打交道的对象。一个POJO持久化以后就是PO&#xff0c;直接用它传递、传递…...

android kotlin基础复习 enum

1、kotlin中&#xff0c;关键字enum来定义枚举类型。枚举类型可以包含多个枚举常量&#xff0c;并且每个枚举常量可以有自己的属性和方法。 2、测试代码&#xff1a; enum class Color{RED,YELLOW,BLACK,GOLD,BLUE,GREEN,WHITE }inline fun <reified T : Enum<T>>…...

个股场外期权怎么交易?场外期权交易流程是怎样的?

今天带你了解个股场外期权怎么交易&#xff1f;场外期权交易流程是怎样的&#xff1f;个股场外期权是一种非标准化的期权合约&#xff0c;通常在场外市场&#xff08;OTC市场&#xff09;由金融机构和投资者之间进行交易。 场外个股期权主要功能 风险管理&#xff1a; 帮助投…...

企业选ETL还是ELT架构?

作为数据处理的重要工具&#xff0c;ETL工具被广泛使用&#xff0c;同时ETL也是数据仓库中的重要环节。本文将从解释ETL工具是怎么处理数据&#xff0c;同时介绍ELT和ETL工具在企业搭建数据仓库的重要优势。 一、什么是ETL? ETL是Extract-Transform-Load的缩写&#xff0c;将…...

【Spring Boot 3】【Web】同时启用 HTTP 和 HTTPS

【Spring Boot 3】【Web】同时启用 HTTP 和 HTTPS 背景介绍开发环境开发步骤及源码工程目录结构背景 软件开发是一门实践性科学,对大多数人来说,学习一种新技术不是一开始就去深究其原理,而是先从做出一个可工作的DEMO入手。但在我个人学习和工作经历中,每次学习新技术总是…...

【Android】最好用的网络库:Retrofit

最好用的网络库&#xff1a;Retrofit 文章目录 最好用的网络库&#xff1a;RetrofitRetrofit的基本用法Retrofit的使用逻辑Retrofit的基本操作处理复杂的接口地址类型进阶删除提交header中指定参数 Retrofit构建器的最佳写法Retrofit的使用封装 用户网络请求的接口配置繁琐&…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

用递归算法解锁「子集」问题 —— LeetCode 78题解析

文章目录 一、题目介绍二、递归思路详解&#xff1a;从决策树开始理解三、解法一&#xff1a;二叉决策树 DFS四、解法二&#xff1a;组合式回溯写法&#xff08;推荐&#xff09;五、解法对比 递归算法是编程中一种非常强大且常见的思想&#xff0c;它能够优雅地解决很多复杂的…...

GeoServer发布PostgreSQL图层后WFS查询无主键字段

在使用 GeoServer&#xff08;版本 2.22.2&#xff09; 发布 PostgreSQL&#xff08;PostGIS&#xff09;中的表为地图服务时&#xff0c;常常会遇到一个小问题&#xff1a; WFS 查询中&#xff0c;主键字段&#xff08;如 id&#xff09;莫名其妙地消失了&#xff01; 即使你在…...

RabbitMQ 各类交换机

为什么要用交换机&#xff1f; 交换机用来路由消息。如果直发队列&#xff0c;这个消息就被处理消失了&#xff0c;那别的队列也需要这个消息怎么办&#xff1f;那就要用到交换机 交换机类型 1&#xff0c;fanout&#xff1a;广播 特点 广播所有消息​​&#xff1a;将消息…...

[QMT量化交易小白入门]-六十二、ETF轮动中简单的评分算法如何获取历史年化收益32.7%

本专栏主要是介绍QMT的基础用法,常见函数,写策略的方法,也会分享一些量化交易的思路,大概会写100篇左右。 QMT的相关资料较少,在使用过程中不断的摸索,遇到了一些问题,记录下来和大家一起沟通,共同进步。 文章目录 相关阅读1. 策略概述2. 趋势评分模块3 代码解析4 木头…...

视觉slam--框架

视觉里程计的框架 传感器 VO--front end VO的缺点 后端--back end 后端对什么数据进行优化 利用什么数据进行优化的 后端是怎么进行优化的 回环检测 建图 建图是指构建地图的过程。 构建的地图是点云地图还是什么信息的地图&#xff1f; 建图并没有一个固定的形式和算法…...