01、数据结构——数组

news/2023/5/28 6:52:57

一、数据结构与算法

  • 数据结构是一门研究组织数据方式的学科,有了编程语言也就有了数据结构。学好数据结构可以编写出更加漂亮、更加有效率的代码。
  • 程序=数据结构+算法
  • 数据结构是算法的基础

二、稀疏数组:

1、基本介绍:

当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组

2、稀疏数组的处理方法是

(1)记录数组一共有几行几列,有多少个不同的值

(2)把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模

 3、应用实例

(1)使用稀疏数组来保留类似前面的二维数组(棋盘、地图等等)

(2)把稀疏数组存盘,并且可以重新恢复原来的二维数组数

(3)整体思路分析

二级数据转稀疏数组的思路:

  • 遍历原始的二维数组,得到有效数据的个数sum
  • 根据sum就可以创建稀疏数组sparseArr int[sum + 1][3]
  • 将二维数组的有效数据存入到稀疏数组

稀疏数组转原始二维数组的思路:

  • 先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组
  • 在读取稀疏数组后几行的数据,并赋给原始的二维数组即可

(4)代码实现

package com.atguigu.sparse.array;public class SparseArray {public static void main(String[] args) {//创建一个原始的二维数组11*11//0:表示没有棋子,1:表示黑子,2:表示蓝子int chessArr1[][]=new int[11][11];chessArr1[1][2]=1;chessArr1[2][3]=2;//输出原始的二维数组System.out.println("原始的二维数组:");for(int[] row:chessArr1){for(int data:row){System.out.printf("%d\t",data);}System.out.println();}//将二维数组转稀疏数组的思路://1、先遍历二维数组,得到非0数据的个数int sum=0;for(int i=0;i<11;i++){for(int j=0;j<11;j++){if (chessArr1[i][j] != 0) {sum++;}}}//2、创建对应的稀疏数组int sparseArr[][]=new int[sum+1][3];//给稀疏数组赋值sparseArr[0][0]=11;sparseArr[0][1]=11;sparseArr[0][2]=sum;//遍历二维数组,将非0的值存放到sparseArr中int count=0;//count用于记录是第几个非0数据for(int i=0;i<11;i++){for(int j=0;j<11;j++){if (chessArr1[i][j] != 0) {count++;sparseArr[count][0]=i;sparseArr[count][1]=j;sparseArr[count][2]=chessArr1[i][j];}}}//输出稀疏数组的形式System.out.println();System.out.println("得到的稀疏数组:");for(int i=0;i<sparseArr.length;i++){System.out.printf("%d\t%d\t%d\t",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);}System.out.println();//将稀疏数组---》恢复成原始的二维数组//1、先读取稀疏数组的第一行,根据第一行的数据,创建原始的二维数组int chessArr2[][]=new int[sparseArr[0][0]][sparseArr[0][1]];//2、输出恢复后的二维数组for(int i=1;i<sparseArr.length;i++){chessArr2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];}System.out.println();System.out.println("恢复后的二维数组:");for(int[] row:chessArr1){for(int data:row){System.out.printf("%d\t",data);}System.out.println();}}
}
//"C:\Program Files\Java\jdk-19\bin\java.exe" "-javaagent:D:\IntelliJ IDEA 2022.2.3\lib\idea_rt.jar=56110:D:\IntelliJ IDEA 2022.2.3\bin" -Dfile.encoding=UTF-8 -Dsun.stdout.encoding=UTF-8 -Dsun.stderr.encoding=UTF-8 -classpath D:\java-idea-2022.10.26\DataStructure\out\production\DataStructure com.atguigu.sparse.array.SparseArray
//原始的二维数组:
//0	0	0	0	0	0	0	0	0	0	0	
//0	0	1	0	0	0	0	0	0	0	0	
//0	0	0	2	0	0	0	0	0	0	0	
//0	0	0	0	0	0	0	0	0	0	0	
//0	0	0	0	0	0	0	0	0	0	0	
//0	0	0	0	0	0	0	0	0	0	0	
//0	0	0	0	0	0	0	0	0	0	0	
//0	0	0	0	0	0	0	0	0	0	0	
//0	0	0	0	0	0	0	0	0	0	0	
//0	0	0	0	0	0	0	0	0	0	0	
//0	0	0	0	0	0	0	0	0	0	0	
//
//得到的稀疏数组:
//11	11	2	1	2	1	2	3	2	
//======================
//
//恢复后的二维数组:
//0	0	0	0	0	0	0	0	0	0	0	
//0	0	1	0	0	0	0	0	0	0	0	
//0	0	0	2	0	0	0	0	0	0	0	
//0	0	0	0	0	0	0	0	0	0	0	
//0	0	0	0	0	0	0	0	0	0	0	
//0	0	0	0	0	0	0	0	0	0	0	
//0	0	0	0	0	0	0	0	0	0	0	
//0	0	0	0	0	0	0	0	0	0	0	
//0	0	0	0	0	0	0	0	0	0	0	
//0	0	0	0	0	0	0	0	0	0	0	
//0	0	0	0	0	0	0	0	0	0	0	
//
//进程已结束,退出代码0

4、练习

 三、数组模拟队列

1、基本介绍:

(1)队列是一个有序列表,可以用数组或是链表来实现

(2)遵循先入先出的原则

2、数组模拟队列

(1)队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的声明如下图,其中 maxSize是该队列的最大容量

(2)因为队列的输出、输入是分别从前后端来处理,因此需要两个变量front及rear分别记录队列前后端的下标,front会随着数据输出而改变,而rear则是随着数据输入而改变

 (3)addQueue:将数据存入队列。思路:

1)将尾指针往后移:rear+1,当front=rear [ 空 ]

2)若尾指针rear小于队列的最大下标maxSize-1,则将数据存入rear所指的数组元素中,否则无法存入数据,rear==maxSize-1 [ 队列满 ]

3)注:

rear是队列最后 [ 含 ]

front是队列最前元素 [不含]

4)代码实现:

package com.atguigu.sparse.queue;import java.util.Scanner;public class ArrayQueueDemo {public static void main(String[] args) {ArrayQueue queue = new ArrayQueue(3);char key=' ';//接收用户输入Scanner scanner = new Scanner(System.in);boolean loop=true;//输出一个菜单while (loop) {System.out.println("s(show): 显示队列");System.out.println("e(exit): 退出队列");System.out.println("a(add): 添加数据到队列");System.out.println("g(get): 从队列中取出数据");System.out.println("h(head): 查看队列头的数据");key=scanner.next().charAt(0);//接收一个字符switch(key){case 's':queue.showQueue();break;case 'a':System.out.println("输出一个数:");int value=scanner.nextInt();queue.addQueue(value);break;case 'g':try {int res=queue.getQueue();System.out.printf("取出的数据:%d\n",res);} catch (Exception e) {//TODO:handle exceptionSystem.out.println(e.getMessage());}break;case 'h':try {int res=queue.headQueue();System.out.printf("队头的数据:%d\n",res);} catch (Exception e) {//TODO:handle exceptionSystem.out.println(e.getMessage());}break;case 'e':scanner.close();loop=false;break;default:break;}}}
}
//使用数组模拟队列-编写一个ArrayQueue类
class ArrayQueue{private int maxSize;//表示数组的最大容量private int front;//队列头private int rear;//队列尾private int[] arr;//存放数据//创建队列的构造器public ArrayQueue(int arrMaxSize){maxSize=arrMaxSize;arr=new int[maxSize];front=-1;//指向队列头的前一个位置rear=-1;//指向队列尾的最后一个数据}//判断队列是否满public boolean isFull(){return rear==maxSize-1;}//判断队列是否为空public boolean isEmpty(){return rear==front;}//添加数据到队列public void addQueue(int n){//判断队列是否满if (isFull()) {System.out.println("队列已满,不能加入数据!");return;}rear++;//让rear后移arr[rear]=n;}public int getQueue(){//判断队列是否为空if (isEmpty()) {//抛出异常throw new RuntimeException("队列空,不能取数据");}front++;return arr[front];}//显示队列的所有数据public void showQueue(){//遍历if (isEmpty()) {System.out.println("队列空的,没有数据");return;}for(int i=0;i<arr.length;i++){System.out.printf("arr[%d]=%d\n",i,arr[i]);}}//显示队列的头数据,注意不是取出数据public int headQueue(){//判断if (isEmpty()) {throw new RuntimeException("队列空的,没有数据");}return arr[front+1];}
}
//"C:\Program Files\Java\jdk-19\bin\java.exe" "-javaagent:D:\IntelliJ IDEA 2022.2.3\lib\idea_rt.jar=55292:D:\IntelliJ IDEA 2022.2.3\bin" -Dfile.encoding=UTF-8 -Dsun.stdout.encoding=UTF-8 -Dsun.stderr.encoding=UTF-8 -classpath D:\java-idea-2022.10.26\DataStructure\out\production\DataStructure com.atguigu.sparse.queue.ArrayQueueDemo
//s(show): 显示队列
//e(exit): 退出队列
//a(add): 添加数据到队列
//g(get): 从队列中取出数据
//h(head): 查看队列头的数据
//s
//队列空的,没有数据
//s(show): 显示队列
//e(exit): 退出队列
//a(add): 添加数据到队列
//g(get): 从队列中取出数据
//h(head): 查看队列头的数据
//a
//输出一个数:
//10
//s(show): 显示队列
//e(exit): 退出队列
//a(add): 添加数据到队列
//g(get): 从队列中取出数据
//h(head): 查看队列头的数据
//h
//队头的数据:10
//s(show): 显示队列
//e(exit): 退出队列
//a(add): 添加数据到队列
//g(get): 从队列中取出数据
//h(head): 查看队列头的数据
//g
//取出的数据:10
//s(show): 显示队列
//e(exit): 退出队列
//a(add): 添加数据到队列
//g(get): 从队列中取出数据
//h(head): 查看队列头的数据
//e
//
//进程已结束,退出代码0

 (4)问题分析并优化

1)目前数组使用一次就不能用,没有达到利用的效果

2)使用算法将这个数组,改进成一个环形的队列

四、数组模拟环形队列

1、思路:

(1)调整front变量的含义:front指向队列的第一个元素

(2)调整rear变量的含义:rear指向队列最后一个元素的后一个位置,因为希望空出一个空间作为约定,rear的初始值=0

(3)队列为满时的条件,(rear+1)%maxSize=front 

尾索引的下一个为头索引时表示队列满,即将队列容量空出一个作为约定

(4)队列为空时的条件,rear=front 

(5)队列中有效的数据的个数 (rear+maxSize-front)%maxSize

package com.atguigu.sparse.queue;import java.util.Scanner;public class CircleArrayQueueDemo {public static void main(String[] args) {System.out.println("测试数组模拟环形队列的案例");CircleArray queue = new CircleArray(4);//队列的有效数据最大是3char key=' ';//接收用户输入Scanner scanner = new Scanner(System.in);boolean loop=true;//输出一个菜单while (loop) {System.out.println("s(show): 显示队列");System.out.println("e(exit): 退出队列");System.out.println("a(add): 添加数据到队列");System.out.println("g(get): 从队列中取出数据");System.out.println("h(head): 查看队列头的数据");key=scanner.next().charAt(0);//接收一个字符switch(key){case 's':queue.showQueue();break;case 'a':System.out.println("输出一个数:");int value=scanner.nextInt();queue.addQueue(value);break;case 'g':try {int res=queue.getQueue();System.out.printf("取出的数据:%d\n",res);} catch (Exception e) {//TODO:handle exceptionSystem.out.println(e.getMessage());}break;case 'h':try {int res=queue.headQueue();System.out.printf("队头的数据:%d\n",res);} catch (Exception e) {//TODO:handle exceptionSystem.out.println(e.getMessage());}break;case 'e':scanner.close();loop=false;break;default:break;}}}
}
class CircleArray{private int maxSize;//表示数组的最大容量private int front;//指向队列的第一个元素private int rear;//指向队列最后一个元素的后一个位置private int[] arr;//存放数据public CircleArray(int arrMaxSize){maxSize=arrMaxSize;arr=new int[maxSize];}//判断队列是否满public boolean isFull(){return (rear+1)%maxSize==front;}//判断队列是否为空public boolean isEmpty(){return rear==front;}//添加数据到队列public void addQueue(int n){//判断队列是否满if (isFull()) {System.out.println("队列已满,不能加入数据");return;}//直接将数据加入arr[rear]=n;//将rear后移,考虑取模rear=(rear+1)%maxSize;}//获取队列的数据public int getQueue(){//判断队列是否为空if (isEmpty()) {//抛出异常throw new RuntimeException("队列空,不能取数据");}//front指向队列的第一个元素//1、先把front对应的值保留到一个临时变量//2、将front后移,考虑取模//3、将临时保存的变量返回int value=arr[front];front=(front+1)%maxSize;return value;}//显示队列的所有数据public void showQueue(){//遍历if (isEmpty()) {System.out.println("队列空的,没有数据");return;}//从front开始遍历for(int i=front;i<front+size();i++){System.out.printf("arr[%d]=%d\n",i,arr[i]);}}//求出当前队列有效数据的个数public int size(){return (rear+maxSize-front)%maxSize;}//显示队列的头数据public int headQueue(){if (isEmpty()) {throw new RuntimeException("队列空的,没有数据");}return arr[front];}}
//"C:\Program Files\Java\jdk-19\bin\java.exe" "-javaagent:D:\IntelliJ IDEA 2022.2.3\lib\idea_rt.jar=56804:D:\IntelliJ IDEA 2022.2.3\bin" -Dfile.encoding=UTF-8 -Dsun.stdout.encoding=UTF-8 -Dsun.stderr.encoding=UTF-8 -classpath D:\java-idea-2022.10.26\DataStructure\out\production\DataStructure com.atguigu.sparse.queue.CircleArrayQueueDemo
//测试数组模拟环形队列的案例
//s(show): 显示队列
//e(exit): 退出队列
//a(add): 添加数据到队列
//g(get): 从队列中取出数据
//h(head): 查看队列头的数据
//s
//队列空的,没有数据
//s(show): 显示队列
//e(exit): 退出队列
//a(add): 添加数据到队列
//g(get): 从队列中取出数据
//h(head): 查看队列头的数据
//a
//输出一个数:
//10
//s(show): 显示队列
//e(exit): 退出队列
//a(add): 添加数据到队列
//g(get): 从队列中取出数据
//h(head): 查看队列头的数据
//a
//输出一个数:
//20
//s(show): 显示队列
//e(exit): 退出队列
//a(add): 添加数据到队列
//g(get): 从队列中取出数据
//h(head): 查看队列头的数据
//a
//输出一个数:
//30
//s(show): 显示队列
//e(exit): 退出队列
//a(add): 添加数据到队列
//g(get): 从队列中取出数据
//h(head): 查看队列头的数据
//a
//输出一个数:
//40
//队列已满,不能加入数据
//s(show): 显示队列
//e(exit): 退出队列
//a(add): 添加数据到队列
//g(get): 从队列中取出数据
//h(head): 查看队列头的数据
//s
//arr[0]=10
//arr[1]=20
//arr[2]=30
//s(show): 显示队列
//e(exit): 退出队列
//a(add): 添加数据到队列
//g(get): 从队列中取出数据
//h(head): 查看队列头的数据
//g
//取出的数据:10
//s(show): 显示队列
//e(exit): 退出队列
//a(add): 添加数据到队列
//g(get): 从队列中取出数据
//h(head): 查看队列头的数据
//g
//取出的数据:20
//s(show): 显示队列
//e(exit): 退出队列
//a(add): 添加数据到队列
//g(get): 从队列中取出数据
//h(head): 查看队列头的数据
//a
//输出一个数:
//10
//s(show): 显示队列
//e(exit): 退出队列
//a(add): 添加数据到队列
//g(get): 从队列中取出数据
//h(head): 查看队列头的数据
//s
//arr[2]=30
//arr[3]=10
//s(show): 显示队列
//e(exit): 退出队列
//a(add): 添加数据到队列
//g(get): 从队列中取出数据
//h(head): 查看队列头的数据

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.exyb.cn/news/show-4562582.html

如若内容造成侵权/违法违规/事实不符,请联系郑州代理记账网进行投诉反馈,一经查实,立即删除!

相关文章

JavaEE3-Spring创建

目录 1.创建一个普通的Maven项目 2.添加Spring框架支持(spring-context&#xff0c;spring-beans) 3.添加启动类 1.创建一个普通的Maven项目 不选择任何模板&#xff0c;直接点Next。 Name&#xff1a;项目名称&#xff1b; Location&#xff1a;项目保存路径&#xff1b; …

微信小程序——【云音乐播放器】

目录 第一章 开发准备 一、项目结构 二、新建微信小程序项目 第二章 标签页切换 一、常用组件介绍 二、编写页面结构和样式 第三章 音乐推荐 一、组件介绍 二、编写音乐推荐页面结构和样式 第四章 播放器 一、任务分析 二、组件介绍 三、实现播放器功能 四、编写…

【音乐小程序项目】

一、学习目标 掌握swiper组件、scroll-view组件的使用掌握image组件的使用掌握音频API的使用掌握slider组件的使用 二、开发前准备 &#xff08;1&#xff09; 项目展示 音乐小程序项目效果展示 &#xff08;2&#xff09; 项目初始化 开发者工具创建空白项目 三、学…

音乐播放器实现的过程

文章目录一、学习目标1.掌握swiper组件、scroll-view组件的使用2.掌握image组件的使用3.掌握slider组件的使用4.掌握音频API的使用二、开发前准备1.标签页切换2.音乐推荐3.播放器4.播放列表三、音乐小程序项目效果展示四、代码实现1.标签页面切换2.音乐推荐2.1.前导知识2.2.轮播…

微信小程序中实现——【音乐播放器】

文章目录一、学习目标1、掌握swiper组件、scroll-view组件的使用2、掌握image组件的使用3、掌握音频API的使用4、掌握slider组件的使用二、开发前的准备1、页面结构图2、项目初始化3、 任务分析4、 前导知识三、标签页切换1、页面和样式&#xff1a;2、音乐小程序基础页面和样式…

音乐学院计算机考试内容,全国艺术院校(音乐类)专业设置及考试内容(8)

天津音乐学院专业考试内容&#xff1a;(一)音乐学1.初试&#xff1a;听写(节奏、音程、和弦、曲调等)&#xff0c;乐理&#xff0c;论文写作2.复试&#xff1a;音乐学常识&#xff0c;音乐风格听辨&#xff0c;视唱(二升二降以下)&#xff0c;和声(到属七和弦)3.面试&#xff1…

文献阅读(45)——使用自监督学习对AMD分类

使用自监督学习对AMD分类 文章目录使用自监督学习对AMD分类一、简介二、先验知识三、文章核心内容四、使用方法1. 非参数化实例歧视&#xff08;中文翻译过来总是奇奇怪怪&#xff0c;其实就是NPID&#xff09;a 挑战b 解决方案c 转化&#xff01;2. 数据集3. 数据预处理五、结…

四川省国家级自然保护区功能区划

四川是全球生物多样性保护热点地区之一&#xff0c;有高等植物近万种&#xff0c;占全国总数的33%&#xff0c;居全国第2位。有野生脊椎动物1247种&#xff0c;超过全国总数的45%&#xff0c;其中国家重点保护野生动物144种&#xff0c;占全国总数的39.6%。四川省自然保护区数量…

扫荡川西大巡游(组图)

丹巴美女 丹巴碉楼 作为大香格里拉旅游环线中的一道亮丽风景&#xff0c;理塘乃至整个川西地区是藏区最值得前往的精华部分。正逢秋季&#xff0c;到深山野岭感受格聂神山和丹巴风情&#xff0c;最合适不过。 推荐行程&#xff1a;成都—康定—理塘—格聂神山—冷谷寺—理塘—长…

女大学生的280块川西环游功略(含帐单)

木格措 作者&#xff1a;hanxue007 梦想是一个实施的过程&#xff0c;当你去做的你的梦想就在一步步的实现&#xff0c;梦想不在于你把所有的条件都具备才开始实施而是在于一个创造的过程&#xff01;不停的出发&#xff0c;不停的行走就是我的梦想&#xff0c;我就行走在梦想的…

10大古镇,你去过几个?

转自&#xff1a;http://travel.sohu.com/20160218/n437799228.shtml 10大古镇&#xff0c;你去过几个&#xff1f; 有人旅行&#xff0c;是为了放松身心&#xff1b;有人旅行&#xff0c;是为了增加阅历&#xff1b;有人旅行&#xff0c;井井只是因为看到那个地方的照片&#…

java基础学习 day36(字符串相关类的底层原理)

字符串存储的内存原理 直接赋值会复用字符串常量池中已有的new出来的不会复用&#xff0c;而是开辟一个新的空间来创建 “”号比较的到底是什么 基本数据类型比较数据值引用数据类型比较地址值 PS. 所以以后对引用数据类型&#xff0c;不要用“”&#xff0c;改用.equals()…

linux快速创建目录

快速创建目录&#xff1a; 1.同级目录下快速创建多个目录&#xff1a; mkdir 800{1,2,3,4,5} make day{1,2,3,4,5,6} 2.多级目录下同时创建目录&#xff1a;mkdir -p project/a/src mkdir -p project/{a,b,c,d}/src

linux 创建目录命令

命令行提示符 [rootlocalhost ~]# [当前用户名主机名 当前所在目录]$linux 超级用户 rootwindow 超级用户 administartor # 超级用户$ 普通用户当前所在目录 ~用户的家目录管理员超级用户 /root普通用户    /home/用户名/所在目录 linux 命令格式命令 空格 [选项] 空格 …

linux 创建目录命令_如何使用一个Linux命令创建多个子目录

linux 创建目录命令If you want to create a directory containing several subdirectories, or a directory tree, using the command line in Linux, generally you have to use the mkdir command several times. However, there is a faster way to do this. 如果要使用Lin…

Linux创建目录和文件 mkdir、touch、cp、rm、mv 和 ln命令

目录前言一、mkdir命令二、touch命令三、ln命令3.1 软/硬链接3.2 软链接详解四、cp命令五、rm命令六、mv命令七、rename前言 点击此处查看 ls、cd、alias、du命令 一、mkdir命令 用法&#xff1a;mkdir [选项]... 目录位置及名称...&#xff0c;若指定目录不存在则创建目录。 …

html大作业(含资源)

资源:链接&#xff1a;https://pan.baidu.com/s/1d3oB-KiRR8TFuFkBEQk9tQ 提取码&#xff1a;dbbd 效果图&#xff1a; 注意事项&#xff1a;拿到一个网页不要立马就开始做&#xff0c;应该先仔细的观察网页的结构并分析&#xff0c;把它分成一小块一小块的完成。 这里 我…

致美创意网站练习

致美创意致美创意网站1.首页首页的html首页的css2.关于致美关于致美的html关于致美的css3.案例展示案例展示的html案例展示的css新闻动态新闻动态的html新闻动态的css内容详细——新闻动态&#xff1a;为什么设计logo&#xff1f;内容的html内容的css剩余两个网页同理&#xff…

普通人如何实现财务自由、跨越式发展?

今天在知乎上看一个40岁焦虑的帖子&#xff0c;结果一个前阿里高P在回答中强力凡尔赛了一把&#xff1a; 初看起来虽然凡尔赛&#xff0c;但仔细看看还并不一定是吹牛&#xff0c;这哥们2002年就毕业了&#xff0c;彼时就业市场热捧的是各种外企比如快消和四大&#xff0c;即便…

小白入!!粉底液气垫傻傻搞不清楚??

更多护肤技巧关注工从号&#xff1a;玛丽安保莱MARIANNEBOLLE 作为很多新手小白刚开始学习化妆的时候&#xff0c;时常会将粉底液与气垫搞混&#xff0c;不知道该在什么情况下使用粉底液还是气垫。其实粉底液和气垫都是用做底妆之用&#xff0c;因为两种类型的产品在功效和作用…