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

【Java数据结构】初识线性表之一:顺序表

使用Java简单实现一个顺序表

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。

线性表大致包含如下的一些方法:

public class MyArrayList {
    private int[] array;
    private int size;
    // 默认构造方法默认分配空间
    SeqList(){   }
    // 将顺序表的底层容量设置指定容量
    SeqList(int initcapacity){   }

     // 新增元素,默认在数组最后新增
    public void add(int data) { }
    // 在 pos 位置新增元素
    public void add(int pos, int data) { }
    // 判定是否包含某个元素
    public boolean contains(int toFind) { return true; }
    // 查找某个元素对应的位置
    public int indexOf(int toFind) { return -1; }
    // 获取 pos 位置的元素
    public int get(int pos) { return -1; }
    // 给 pos 位置的元素设为 value
    public void set(int pos, int value) {   }
    //删除第一次出现的关键字key
    public void remove(int toRemove) {   }
    // 获取顺序表长度
    public int size() { return 0; }
    // 清空顺序表
    public void clear() {   }
   
    // 打印顺序表
    public void display() {   }
}

 接下来根据上面的方法实现一个 int 类型的顺序表:

import java.util.Arrays;
public class MyArrayList {private int[] elem;private int usedSize;private static final int DEFAULT_SIZE = 10;public MyArrayList(){elem = new int[DEFAULT_SIZE];}public MyArrayList(int initCapacity){elem = new int[initCapacity];}private boolean checkCapacity(){if(this.usedSize == elem.length){return true;}return false;}public void display(){for (int i = 0; i < this.usedSize; i++) {System.out.print(this.elem[i] + " ");}}public void add(int data){if(checkCapacity()){this.elem = Arrays.copyOf(this.elem,2*elem.length);}this.elem[this.usedSize] = data;this.usedSize++;return;}public void add(int pos,int data){if(pos > this.usedSize || pos < 0){throw new PosOutOfBoundsException("插入位置错误!");}if(checkCapacity()){this.elem = Arrays.copyOf(this.elem,2*elem.length);}for (int i = this.usedSize - 1; i >=pos ; i--) {elem[i+1] = elem[i];}this.elem[pos] = data;this.usedSize++;return;}public boolean contains(int data){for (int i = 0; i < this.usedSize; i++) {if(this.elem[i] == data){return true;}}return false;}public int indexof(int data){for (int i = 0; i < this.usedSize; i++) {if(this.elem[i] == data){return i;}}return -1;}public int get(int pos){if(pos >= this.usedSize || pos < 0){throw new PosOutOfBoundsException("输入的位置错误!");}return this.elem[pos];}public void set(int pos,int data){if(pos >= this.usedSize || pos < 0){throw new PosOutOfBoundsException("输入的位置错误!");}this.elem[pos] = data;}public int size(){return this.usedSize;}public void remove(int data){if(this.contains(data)){int pos = this.indexof(data);for (int i = pos; i < this.usedSize - 1; i++) {this.elem[pos] = this.elem[pos+1];}this.usedSize--;}else{throw new PosOutOfBoundsException("没有该元素");}}public void clear(){this.usedSize = 0;return;}
}

ArrayList简介

在集合框架中,ArrayList是一个普通的类,实现了List接口,具体框架图如下:

  • ArrayList是以泛型方式实现的,使用时必须要先实例化
  • ArrayList实现了RandomAccess接口,表明ArrayList支持随机访问
  • ArrayList实现了Cloneable接口,表明ArrayList是可以clone的
  • ArrayList实现了Serializable接口,表明ArrayList是支持序列化的
  • 和Vector不同,ArrayList不是线程安全的,在单线程下可以使用,在多线程中可以选择Vector或者
  • CopyOnWriteArrayList
  • ArrayList底层是一段连续的空间,并且可以动态扩容,是一个动态类型的顺序表

ArrayList如何使用

ArrayList的构造方法

ArrayList中的构造方法:

ArrayList();//无参构造

ArrayList(Collection<? extends E> c);//利用其他 Collection 构建 ArrayList

ArrayList(int initialCapacity);//指定顺序表初始容量

 代码示例:

public class Test {public static void main(String[] args) {List<Integer> list1 = new ArrayList<>();//无参构造List<Integer> list2 = new ArrayList<>(10);//指定容量list2.add(1);list2.add(2);list2.add(3);List<Integer> list3 = new ArrayList<>(list2);//利用其他 Collection 构建 ArrayList}
}

ArrayList常见操作

尾插

public class Test {public static void main(String[] args) {List<Integer> list = new ArrayList<>();//无参构造list.add(1);list.add(2);list.add(3);System.out.println(list);}
}

将元素插入到指定位置

public class Test {public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(1,4);System.out.println(list);}
}

尾插另一个顺序表中的元素

public class Test {public static void main(String[] args) {List<Integer>  list1 = new ArrayList<>();list1.add(4);list1.add(5);list1.add(6);List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.addAll(list1);System.out.println(list);}
}

删除指定位置元素

public class Test {public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.remove(1);System.out.println(list);}
}

删除指定数据

public class Test {public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.remove(new Integer(2));System.out.println(list);}
}

获取指定位置元素

public class Test {public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);System.out.println(list.get(1));}
}

将指定位置元素设置为新数据

public class Test {public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.set(1,4);System.out.println(list);}
}

清空顺序表

public class Test {public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.clear();System.out.println(list);}
}

判断一个元素是否在顺序表中

public class Test {public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);System.out.println(list.contains(2));System.out.println(list.contains(4));}
}

返回第一个指定元素所在下标

public class Test {public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(1);System.out.println(list.indexOf(1));}
}

返回最后一个指定元素所在下标

public class Test {public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);list.add(1);System.out.println(list.lastIndexOf(1));}
}

截取部分list

public class Test {public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);System.out.println(list.subList(0,2));}
}

遍历 ArrayList 的三种方法

ArrayList 可以使用三方方式遍历:for循环+下标、foreach增强循环、使用迭代器

public class Test {public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);//使用fori遍历for (int i = 0; i < list.size(); i++) {System.out.print(list.get(i));}System.out.println();//使用foreach遍历for(Integer integer:list){System.out.print(integer);}System.out.println();//使用迭代器遍历Iterator<Integer> it = list.listIterator();while(it.hasNext()){System.out.print(it.next());}}
}

运行结果:

 ArrayList的场景使用

洗牌算法

将一副扑克牌随机打乱,并分配给三个人,每人五张牌

算法原码所在位置:

shufflecards · 一直淡水鱼/Java经典例题 - 码云 - 开源中国 (gitee.com)

杨辉三角

题目描述:

代码实现:

public class Test {public static List<List<Integer>> generate(int numRows) {List<List<Integer>> list = new LinkedList<>();for (int i = 0; i < numRows; i++) {List<Integer> row = new LinkedList<>();for (int j = 0; j < i + 1; j++) {if (j == 0 || i == j) {row.add(1);} else {row.add(list.get(i - 1).get(j - 1) + list.get(i - 1).get(j));}}list.add(row);}return list;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int numRows = scanner.nextInt();List<List<Integer>> list = generate(numRows);for (int i = 0; i < numRows; i++) {for (int j = 0; j < i + 1; j++) {System.out.print(list.get(i).get(j) + " ");}System.out.println();}}
}

 运行结果图:

相关文章:

【Java数据结构】初识线性表之一:顺序表

使用Java简单实现一个顺序表 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构&#xff0c;一般情况下采用数组存储。在数组上完成数据的增删查改。 线性表大致包含如下的一些方法&#xff1a; public class MyArrayList { private int[] array; pri…...

对接高德开放平台API

高德开放平台API&#xff1a; https://lbs.amap.com/ 一、天气查询 天气查询: https://lbs.amap.com/api/webservice/guide/api/weatherinfo adcode城市码表下载: https://lbs.amap.com/api/webservice/download Component public class WeatherUtil {Resourceprivate GdCon…...

Linux 初识

目录 ​编辑 1.Linux发展史 1.1UNIX发展历史 1.2Linux发展历史 2.Linux的开源属性 2.1 开源软件的定义 2.2 Linux的开源许可证 2.3 开源社区与协作 3.Linux的企业应用现状 3.1 服务器 3.1.1 Web服务器 3.1.2 数据库服务器 3.1.3 文件服务器 3.1.4 电子邮件服务器 …...

CSS技巧专栏:一日一例 4.纯CSS实现两款流光溢彩的酷炫按钮特效

大家好&#xff0c;今天是 CSS技巧专栏&#xff1a;一日一例 第三篇《纯CSS实现两款流光溢彩的酷炫按钮特效》 先看图&#xff1a; 特此说明&#xff1a; 本专题专注于讲解如何使用CSS制作按钮特效。前置的准备工作和按钮的基本样式&#xff0c;都在本专栏第一篇文章中又详细…...

int类型变量表示范围的计算原理

文章目录 1. 了解2. 为什么通常情况下int类型整数的取值范围是-2147483648 ~ 21474836473. int类型究竟占几个字节4. 推荐 1. 了解 通常情况下int类型变量占4个字节&#xff0c;1个字节有8位&#xff0c;每位都有0和1两种状态&#xff0c;所以int类型变量一共可以表示 2^32 种状…...

STM32崩溃问题排查

文章目录 前言1. 问题说明2. STM32&#xff08;Cortex M4内核&#xff09;的寄存器3. 崩溃问题分析3.1 崩溃信息的来源是哪里&#xff1f;3.2 崩溃信息中的每个关键字代表的含义3.3 利用崩溃信息去查找造成崩溃的点3.4 keil5中怎么根据地址找到问题点3.5 keil5上编译时怎么输出…...

CSS 【详解】样式选择器(含ID、类、标签、通配、属性、伪类、伪元素、Content属性、子代、后代、兄弟、相邻兄弟、交集、并集等选择器)

CSS 样式选择器&#xff0c;用于选中页面中的 html 元素&#xff0c;以便添加 CSS 样式。 按渲染性能由高到低 依次是&#xff1a; ID 选择器 #id 通过元素的 id 属性选中元素&#xff0c;区分大小写 <p id"p1" >第一段</p>#p1{color: red; }但不推荐使…...

CMakeLists.txt编写思路

近期在linux编写CMakeLists.txt文件&#xff0c;整理了一些思路。 一、编写CMakeLists.txt的基本步骤和思路&#xff1a; 初始化CMake&#xff1a; 使用cmake_minimum_required指令指定CMake的最小版本要求&#xff0c;以确保兼容性。使用project指令定义项目名称和可选的语言…...

红日靶场----(三)2.漏洞利用

上期的通过一句话木马实现对目标主机的持久后门 我使用的是蚁剑&#xff0c;蚁剑安装及使用参考&#xff1a; 下载地址&#xff1a; GitHub - AntSwordProject/AntSword-Loader: AntSword 加载器 安装即使用&#xff1a; 1. 快速入门 语雀 通过YXCMS的后台GETSHELL 利用…...

LeetCode HOT100(三)滑动窗口

子数组最大平均数 I &#xff08;非hot100&#xff0c;但是滑动窗口的思想可以很好的体现&#xff0c;入门滑动窗口很好的题&#xff09; 给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。 请你找出平均数最大且 长度为 k 的连续子数组&#xff0c;并输出该最大平均数…...

数学系C++ 排序算法简述(八)

目录 排序 选择排序 O(n2) 不稳定&#xff1a;48429 归并排序 O(n log n) 稳定 插入排序 O(n2) 堆排序 O(n log n) 希尔排序 O(n log2 n) 图书馆排序 O(n log n) 冒泡排序 O(n2) 优化&#xff1a; 基数排序 O(n k) 快速排序 O(n log n)【分治】 不稳定 桶排序 O(n…...

记一下blender曲线阵列

先说一下如何正常使用这个 这一次我是用来贴瓷砖 随便创建一个mesh 然后添加一个阵列修改器&#xff0c;然后再给他添加一个curve修改器&#xff0c;使用constant offset去偏移他 这里有个小细节 我第一次创建的curve 我选取之后&#xff0c;死活无法沿着曲线阵列&#xff…...

Windows电脑安装Python结合内网穿透轻松搭建可公网访问私有网盘

文章目录 前言1.本地文件服务器搭建1.1.Python的安装和设置1.2.cpolar的安装和注册 2.本地文件服务器的发布2.1.Cpolar云端设置2.2.Cpolar本地设置 3.公网访问测试4.结语 前言 本文主要介绍如何在Windows系统电脑上使用python这样的简单程序语言&#xff0c;在自己的电脑上搭建…...

react hooks antd 父组件取子组件form表单的值

在React中&#xff0c;父组件可以使用ref来访问子组件的方法或属性。子组件包含一个表单&#xff0c; 使用forwardRef、useImperativeHandle&#xff1a;forwardRef允许组件使用ref将 DOM 节点暴露给父组件&#xff0c;使用useImperativeHandle暴露方法给父组件。 子组件&#…...

【ARMv8/v9 GIC 系列 1.7 -- GIC PPI | SPI | SGI | LPI 中断使能配置概述】

请阅读【ARM GICv3/v4 实战学习 】 文章目录 GIC 各种中断使能配置PPIs(每个处理器私有中断)SPIs(共享外设中断)SGIs(软件生成的中断)LPIs(局部中断)GIC 各种中断使能配置 在ARM GICv3和GICv4架构中,不同类型的中断(如PPIs、SPIs、SGIs和LPIs)可以通过不同的方式进…...

大数据如何推动工业数字化发展?

随着工业领域的深刻变革&#xff0c;数字化成为了驱动行业前行的核心力量。在这一转变中&#xff0c;大数据扮演着不可或缺的角色。它不仅为企业提供了洞察市场趋势、消费者行为等关键信息的窗口&#xff0c;还为企业优化生产流程、提升产品质量以及推动创新提供了强有力的支持…...

计算机网络浅谈—什么是 OSI 模型?

开放系统通信&#xff08;OSI&#xff09;模型是一个代表网络通信工作方式的概念模型。 思维导图 什么是 OSI 模型&#xff1f; 开放系统互连 (OSI) 模型是由国际标准化组织创建的概念模型&#xff0c;支持各种通信系统使用标准协议进行通信。简单而言&#xff0c;OSI 为保证…...

浪潮服务器内存物理插槽位置

浪潮服务器内存物理插槽位置 如下图所示...

windows node降级到指定版本

要在Windows上将Node.js降级到指定版本&#xff0c;你可以使用nvm&#xff08;Node Version Manager&#xff09;来管理和切换不同的Node.js版本。以下是使用nvm降级Node.js的步骤&#xff1a; 如果尚未安装nvm&#xff0c;请访问https://github.com/coreybutler/nvm-windows …...

EXSI 实用指南 2024 -编译环境 Mac OS 安装篇(一)

1. 引言 在现代虚拟化技术的快速发展中&#xff0c;VMware ESXi 作为领先的虚拟化平台&#xff0c;凭借其高性能、稳定性和丰富的功能&#xff0c;广泛应用于企业和个人用户。ESXi 能有效地提高硬件资源利用率&#xff0c;并简化 IT 基础设施的管理。然而&#xff0c;如何在 V…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...