稀疏数组与环形数组
2019-08-16 09:17:25来源：博客园 阅读 ()
稀疏数组与环形数组
数据结构与算法的关系
数据结构(data structure)是一门研究组织数据方式的学科，有了编程语言也就有了数据结构。学好数据结构可以编写出跟家漂亮，更加有效率的代码
要学好数据结构就要多多考虑如何将生活中遇到的问题，用程序去实现解决
程序=数据结构+算法
数据结构是算法的基础，换言之，想要学好算法，需要把数据结构学到位
数据结构包括：线性结构和非线性结构
线性结构：
- 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系(a[0]=30)
- 线性结构有两种不同的存储结构，即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的
- 链式存储的线性表称为链表，链表中的存储元素不一定连续，元素节点中存放数据元素以及相邻元素的地址信息
- 线性结构常见的有：数组，队列，链表和栈
非线性结构
非线性结构包括：二维数组，多维数组，广义表，树结构，图结构
稀疏数组
当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组
稀疏数组的处理方法是：
- 记录数组一共有几行几列，有多少个不同的值
- 把具有不同的值得元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
二维数组转稀疏数组
- 遍历 原始的二维数组，得到有效数据的个数sum
- 根据sum就可以创建稀疏数组sparseArr 行数为sum+1,列数固定为3
- 将二维数组的有效数据存入到稀疏数组
稀疏数组转原始的二维数据
1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，
2.在读取稀疏数组后几行的数据，并赋给原始的二维数据
package demo1;
public class SparseArray {
public static void main(String[] args) {
//二维数组，数组里面装了数组
//定义一个行列为11的二维数组，第一个[]代表行，第二个代表列
int chessArr1[][] = new int[11][11];
//0:表示没有棋子，1表示黑子，2表示蓝子
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
chessArr1[3][4] = 2;
// System.out.println(chessArr1[1][2]);
//遍历数组,原始二维数组
for(int i=0;i<chessArr1.length;i++) {
for(int j=0; j<chessArr1[i].length;j++) {
System.out.print(chessArr1[i][j]+" ");
}
System.out.println();
}
//将二维数组转为稀疏数组的思路
//1.先遍历二维数组 得到非0数据的个数
int sum = 0 ;
for(int i=0;i<chessArr1.length;i++) {
for(int j=0; j<chessArr1[i].length;j++) {
if(chessArr1[i][j]!=0) {
sum=sum+1;
}
}
}
//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;
for(int i=0;i<chessArr1.length;i++) {
for(int j=0; j<chessArr1[i].length;j++) {
if(chessArr1[i][j]!=0) {
count++;
//给sparseArr数组赋值
//第一个稀疏数组的值放在第一行
//所以需要递增
sparseArr[count][0]=i;//稀疏数组的第一列存储的是行数
sparseArr[count][1]=j;//稀疏数组的第二列存储的是列数
sparseArr[count][2]=chessArr1[i][j];//稀疏数组的第三列存储的是值
}
}
}
System.out.println("稀疏数组--------");
for(int i=0;i<sparseArr.length;i++) {
for(int j=0; j<sparseArr[i].length;j++) {
System.out.print(sparseArr[i][j]+" ");
}
System.out.println();
}
//把稀疏数组转换成二维数组
//定义新的二维数组,行数应该为稀疏数组的第一列，列数为第二列
int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
//定义好的二维数组，把稀疏数组转换为二维数组
//稀疏数组sparseArr[i][0]对应是chessArr2的行
//稀疏数组sparseArr[i][1]对应的是chessArr2的列
//sparseArr[i][2];对应的是稀疏数组的值
for(int i=1;i<sparseArr.length;i++) {
chessArr2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];
}
//遍历二维数组
System.out.println("稀疏数组转二维数组");
for(int i=0;i<chessArr2.length;i++) {
for(int j=0; j<chessArr2[i].length;j++) {
System.out.print(chessArr2[i][j]+" ");
}
System.out.println();
}
}
}
队列
队列是一个有序列表，可以用数组或是链表来实现
遵循先入先出的原则，先存入队列的数据，要先取出，后存入的数据，后取出。
数组模拟环形队列实现
队列满条件是 (rear + 1) % maxSize == front 【满】
队列中有效的数据的个数 (rear + maxSize - front) % maxSize
package demo1;
import java.util.Scanner;
public class CircleArrayQueueDemo {
public static void main(String[] args) {
CircleArray queue = new CircleArray(4);
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):查看队列头的数据");
System.out.println("请输入您的操作");
key = scanner.next().charAt(0);
switch(key) {
case 's':
queue.showQueue();
break;
case 'e':
scanner.close();
loop=false;
break;
case 'a':
System.out.println("请输入你要添加的数据");
int i = scanner.nextInt();
queue.addQueue(i);
break;
case 'g':
try {
int res = queue.getQueue();
System.out.println("取出的数据是"+res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int res = queue.getQueue();
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
default:
break;
}
}
System.out.println("程序退出");
}
}
class CircleArray{
private int maxSize;//数组最大的容量
private int front;//front指向队列的第一个元素初始值为0
private int rear;//rear 指向队列的最后一个元素的后一个位置，rear初始值为0
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 front == rear;
}
//添加数据到队列
public void addQueue(int n) {
//判断队列是否满
if(isFull()) {
System.out.println("队列满，不能加入数据");
}
arr[rear]=n;//rear指针在最后元素的后一位
rear=(rear+1)%maxSize;
}
//获取队列的数据，出队列
public int getQueue() {
//取出队列，先判断是否为空，为空，不能取
if(isEmpty()) {
throw new RuntimeException("队列空，不能取");
}
int value = arr[front];
front=(front+1)%maxSize;//front后移
return value;
}
//显示队列的所有数据
public void showQueue() {
if(isEmpty()) {
System.out.println("队列空的，没有数据");
return;
}
for(int i = front; i< front +size();i++) {
System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
}
}
public int size() {
return(rear + maxSize - front) % maxSize;
}
//显示队列的头数据
public int headQueue() {
if(isEmpty()) {
System.out.println("队列空的，没有数据");
throw new RuntimeException("队列空的，没有数据");
}
return arr[front];
}
}
原文链接:https://www.cnblogs.com/train99999/p/11094469.html
如有疑问请与原作者联系
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
- Java笔记：数组，异常，泛型 2020-06-08
- 数组小Demo 2020-05-25
- 从零开始的数组，这么设计么是为什呢？ 2020-05-24
- LeetCode 面试题53 - I. 在排序数组中查找数字 I 2020-05-22
- LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置 2020-05-22
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
