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

JAVA与数据结构-线性表

目录

一.线性表的概念

二.线性表的关系及分类

三.数组与顺序表

四.链表

1.静态链表(链表的的数组底层实现)

2.循环链表

3.双向链表

五.栈

1.栈的概念

2.栈的底层实现

3.共享空间栈

4.逆波兰表达式(后缀表达式)

5.栈与递归 

六.队列

1.队列概念

2.队列的底层实现

3.循环队列

七.链式储存与顺序储存


一.线性表的概念

线性表是0个或n个相同数据类型的有限序列

构成线性表的条件:除了头尾外每个结点有且仅有一个前驱和后继。

二.线性表的关系及分类

线性表按物理存储结构可分为顺序存储结构和链式存储结构。

基本顺序存储结构为数组,基本链式存储结构为链表。

以数组为底层可实现顺序表和栈及队列。

以链表为底层可实现栈和队列。

其关系图大致如下:

三.数组与顺序表

封装顺序表的使用:

定义

List<类型参数>  顺序表名 = new ArrayList<>();

ArrayList<类型参数> 顺序表名 = new ArrayList<>();

【ArrayList实现了List接口】

顺序表的底层实现:

底层是对数组的处理较简单

顺序表底层需要实现的一般方法:

(其余可自行到库中查看)

四.链表

链表的一般底层实现:

通过内部类定义结点与C语言中结构体类似

要实现的一般方法有: 

1.静态链表(链表的的数组底层实现)

静态链表的实现的每一个结点需要值域和游标(游标用来存储下一节点的下标) 

2.循环链表

链表的尾部指针域指向头结点

3.双向链表

 在单向链表的属性中多了一个指向前一个结点的“指针”.

五.栈

1.栈的概念

只在表首进行删除和插入操作的线性表

2.栈的底层实现

数组实现:

需要一top变量指示栈顶下标(栈空为-1,栈满为n)

大致框架如下,方法(push,pop,peek,empty等可参考库函数尝试实现)

链表实现:

以“头指针”指示栈顶,对头指针及其前一个结点进行操作即可实现栈的基本方法

基本结构如下:

3.共享空间栈

用于底层为数组实现的栈节省空间,两栈合并。

结构大致如下:

可定义top1,top2分别表示两栈顶当两栈顶相遇(top1+1=top2)时栈满。

当top1 = -1且top2 = n时栈空(n为栈大小)。

4.逆波兰表达式(后缀表达式)

中缀转后缀:

一种较容易推导方法为加括号,通过栈推导可自行查资料

5.栈与递归 

递归的底层可以理解为一个栈,每次递归时所得数据存储在栈中直到递归出口再将数据依次弹出

六.队列

1.队列概念

只在头部进行删除尾部进行插入的线性表 (先进先出)

2.队列的底层实现

数组实现:

与栈相似多出一个属性指示队尾,对队首队尾进行操作

链表实现:

单向链表实现时与栈相似都是对头指针进行操作,只是加入删除元素的方式有所不同

双向链表实现队列较为快捷可同时对头尾指针进行操作。 

3.循环队列

以数组为底层实现循环队列时防止假满状态(队尾元素删除后其空间无法利用,头指针一直向前走无法回头)实现空间重复利用。定义front rear指示队列首尾部

循环队列大小计算公式:

ret = (front - rear + maxSize) % maxSize 

循环队列循环的实现:

添加删除元素时分别对尾头指针进行操作;

添加移动尾的下标:

(rear + 1) % maxSize

删除移动头的下标:

(front + 1) % maxSize

循环队列满空的判断:

空时front = rear

满时判断:

1.标记法

flag=false 时为空

flag=true时为满

2.留空法

留下一个位置不放元素

当(rear + 1) % maxSize = front 时为满

通过以上操作我们可以发现下标只在(0 ~ maxSize - 1)范围内变化,从而实现循环

4.双向队列

可在两边同时进出的队列

七.链式储存与顺序储存

顺序存储结构如数组及以其为底层实现的结构:

1.空间大小确定

2.如需查找,时间复杂度仅为O(1)较易进行

3.插入操作需移动插入位置后所有元素,时间复杂度为O(n),不便

链式存储结构如链表及以其为底层实现的结构:

1.大小不固定

2.只可按一定顺序进行查找O(n)不便

3.插入时找指定元素时O(n)插入时O(1),插入愈多其优势越明显

故选用结构时需据实际情况。

相关文章:

JAVA与数据结构-线性表

目录 一.线性表的概念 二.线性表的关系及分类 三.数组与顺序表 四.链表 1.静态链表(链表的的数组底层实现&#xff09; 2.循环链表 3.双向链表 五.栈 1.栈的概念 2.栈的底层实现 3.共享空间栈 4.逆波兰表达式&#xff08;后缀表达式&#xff09; 5.栈与递归 六.…...

C++|开源日志库log4cpp和glog

文章目录 log4cpp 和 glog对比1. **功能对比**2. **易用性和配置**3. **性能**4. **线程安全**5. **日志输出**6. **功能扩展**7. **适用场景**8. **总结** 其它开源C日志库1. **spdlog**2. **easylogging**3. **Boost.Log**4. **loguru**5. **Poco Logging**6. **Qt Logging (…...

React Context 实现全局组件注册

来源于GPT4o&#xff1a;https://ai.openaicloud.cn/?inVitecodeEJSTWFZMQE 第一步&#xff1a;创建全局组件上下文 (GlobalComponentProvider) 我们将创建一个 React Context 和 Provider&#xff0c;用于存储和提供全局组件。 // src/context/GlobalComponentProvider.tsx…...

基于AutoDL云计算平台+LLaMA-Factory训练平台微调本地大模型

1. 注册与认证 访问AutoDL官网&#xff1a;前往 AutoDL官网。 注册账号&#xff1a;完成注册流程。 实名认证&#xff1a;按照要求完成实名认证&#xff0c;以确保账号的合规性。 2. 选择GPU资源 进入算力市场&#xff1a;在官网首页点击“算力市场”菜单。 挑选GPU&#x…...

strdup 函数

strdup 函数是 C 标准库中的一个函数&#xff0c;用于复制一个字符串。它的全称是 "string duplicate"。这个函数在 <string.h> 头文件中声明。strdup 函数会分配足够的内存来存储源字符串的副本&#xff0c;并将源字符串的内容复制到新分配的内存中。然后返回…...

2.9/Q2,Charls最新文章解读!

文章题目&#xff1a;The causal effect of Internet use on rural middle-aged and older adults depression: A propensity score matching analysis DOI&#xff1a;10.1177/20552076241310041 中文标题&#xff1a;互联网使用对农村中老年人抑郁症的因果影响&#xff1a…...

【未完成】springboot项目实现扫码登录相关逻辑

准备工作 配置redis 引入redis依赖 <dependencies><!-- Spring Data Redis 依赖 --><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId></dependency><…...

html、js、css实现爱心效果

好的&#xff01;我们可以进一步美化这个爱心效果&#xff0c;增加更多动态和视觉吸引力。以下是改进后的代码&#xff0c;包括以下功能&#xff1a; 1. 背景渐变&#xff1a;添加动态背景渐变效果。 2. 爱心阴影&#xff1a;为爱心添加阴影&#xff0c;使其更具立体感。 3. 随…...

【前端】Hexo 建站指南

文章目录 前言生成站点本地测试部署云端参考 前言 更好的阅读体验&#xff1a;https://blog.dwj601.cn/FrontEnd/Hexo/build-your-own-website-with-hexo/ 笔记记多了&#xff0c;想要分享给同学们一起交流进步&#xff0c;该怎么办&#xff1f;想要搭建一个属于自己的知识库…...

OpenStack基础架构

openstack是一套IaaS云的解决方案&#xff0c;是一个开源的云计算管理平台 每一台物理机上都会有一个nova服务器 虚拟化其实是在nova主机里启用的 COW技术&#xff1a; 这么来看&#xff0c;3个物理机上产生10个虚拟机&#xff0c;所以把服务分散到10个虚拟机上和分散到4个虚拟…...

1905电影网中国地区电影数据分析(一) - 数据采集、清洗与存储

文章目录 前言一、数据采集步骤及python库使用版本1. python库使用版本2. 数据采集步骤 二、数据采集网页分析1. 分析采集的字段和URL1.1 分析要爬取的数据字段1.2 分析每部电影的URL1.2 分析每页的URL 2. 字段元素标签定位 三、数据采集代码实现1. 爬取1905电影网分类信息2. 爬…...

IPhone16 Plus 设备详情

目录 产品宣传图内部图——前内部图——后设备详细信息 产品宣传图 内部图——前 内部图——后 设备详细信息 信息收集于HubWeb.cn...

埃氏算法C++实现: 快速输出质数( 素数 )

目录 1.简介 算法原理 算法特点 应用场景 2.一般求素数方法 3.埃氏算法求素数 3.1.无动态分配 3.2.有动态分配 1.简介 ‌埃氏算法&#xff08;Eratosthenes Sieve&#xff09;‌&#xff0c;全称为埃拉托斯特尼筛法&#xff0c;是一种由古希腊数学家埃拉托斯特尼在公元…...

后端的config包中的常用配置

文章目录 一. CorsConfig二. Knife4jConfig三. MyBatisPlusConfig四. RedisTemplateConfig五. RedissonConfig 一. CorsConfig 全局跨域配置 Configuration public class CorsConfig implements WebMvcConfigurer {Overridepublic void addCorsMappings(CorsRegistry registr…...

基于亿坊PHP框架构建物联网解决方案的优势分析!

在物联网 (IoT) 领域&#xff0c;选到合适的框架对于整个项目的开展也尤为重要。通常情况下&#xff0c;基于PHP的一些主流框架被用户常选择&#xff0c;今天就带大家了解下基于亿坊PHP框架构建物联网解决方案的优势有哪些&#xff1f; 1、开发效率高 在物联网项目中&#xf…...

IoTDB结合Mybatis使用示例(增删查改自定义sql等)

IoTDB时序库是当前越来越流行以及基于其优势各大厂商越来越易接受的国产开源时序数据库&#xff0c;针对IoTDB的内容不做过多介绍&#xff0c;在使用该时序库时&#xff0c;往往有一定入门门槛&#xff0c;不同于关系型数据库或文档型数据库那般方便维护和接入开发&#xff0c;…...

skynet 源码阅读 -- 启动主流程

Skynet 启动主流程分析 Skynet 是一个轻量级、高并发的服务器框架。它在启动时会进行一系列初始化操作&#xff0c;并启动多个不同功能的线程&#xff08;Monitor、Timer、Worker、Socket&#xff09;&#xff0c;从而实现消息分发、定时器、网络I/O等核心功能。本文主要从 ma…...

OpenCV:高通滤波之索贝尔、沙尔和拉普拉斯

目录 简述 什么是高通滤波&#xff1f; 高通滤波的概念 应用场景 索贝尔算子 算子公式 实现代码 特点 沙尔算子 算子公式 实现代码 特点 拉普拉斯算子 算子公式 实现代码 特点 高通滤波器的对比与应用场景 相关阅读 OpenCV&#xff1a;图像滤波、卷积与卷积核…...

UDP 广播组播点播的区别及联系

1、网络IP地址的分类 组播地址是分类编址的IPv4地址中的D类地址&#xff0c;又叫多播地址&#xff0c;他的前四位必须是1110&#xff0c;所以网络地址的二进制取值范围是11100000~11101111对应的十进制为 224~~239。所以以224~239开头的网络地址都是组播地址。 组播地址的功能…...

STM32补充——IAP

0 前置知识&#xff1a; FLASH相关内容&#xff1a;前往STM32补充——FLASH STM32三种烧录方式&#xff08;看看就行&#xff09;&#xff1a; 1.ISP&#xff1a;In System Programming&#xff08;在系统编程&#xff09; 执行芯片厂商的 Bootloader 程序进入 ISP 模式&…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...

ubuntu22.04 安装docker 和docker-compose

首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...