开篇 数据结构包括：线性结构和非线性结构
文章目录
- 开篇
- 一、稀疏数组
- （1）稀疏数组的处理方法是：
- （2）思路分析
- （3）代码实现
- 二、队列
- （2）代码实现
- 三、数组模拟环型队列
- （1）问题分析及优化
- （2）代码实现
线性结构
- 线性结构作为最常用的数据结构，其特点是数据元素之间存在一对有的线性关系
- 线性结构有两种不同的存储结构，及顺序存储结构（数组）和链式存储结构（链表）。顺序存储结构的线性表称为顺序表，顺序表中的元素是连续的；如数组；
- 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放元素以及相邻元素的地址信息；
- 线性结构常见的有：数组，队列，表，链表和栈
非线性结构包括：二维数组，多为数组，广义表，树结构，图结构
一、稀疏数组 当一个数组中大部分元素为0，或者同一个值的数组时，可以使用稀疏数组来保存该数组。
（1）稀疏数组的处理方法是：
- 记录数组有几行几列，有多少个不同的值
- 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模；
文章图片
二维数组转稀疏数组的思路：
- 遍历原始的二维数组，得到有效的个数sum
- 根据sum就可以创建稀疏数组sparseArr int[sum+1][3]
- 将二维数组的有效数据存入到稀疏数组中
- 先读取稀疏数组的第一行，根据第一行的数据创建原始的二维数组
- 读取稀疏数组后几行的数据，并赋值给原始的二维数组
首先创建原始的二维数组
//创建一个原始的二维数组，11*11
//0:表示没有妻棋子，1：表示黑子，2：表示蓝子int chessArr[][]=new int[11][11];
chessArr[1][2]=1;
chessArr[2][3]=2;
System.out.println("输出原始的二维数组");
//输出原始的二维数组
for (int[] row : chessArr) {
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 (chessArr[i][j]!=0){
sum++;
}}}//2.创建对应的稀疏数组
int sparseArr[][]=new int[sum+1][3];
//给稀疏数组赋值
//第一行
sparseArr[0][0]=11;
sparseArr[0][1]=11;
sparseArr[0][2]=sum;
//第二行
//遍历二维数组，将非零的值放到sparseArr中
int count=0;
//用于给sparseArr计数：
for (int i = 0;
i < 11;
i++) {
for (int j = 0;
j < 11;
j++) {
if (chessArr[i][j]!=0){
count++;
sparseArr[count][0]=i;
sparseArr[count][1]=j;
sparseArr[count][2]=chessArr[i][j];
}}}//输出稀疏数组的形式
System.out.println();
System.out.println("得到的稀疏数组为------");
for (int i = 0;
i .length;
i++) {
System.out.printf("%d\t%d\t%d\t\n",sparseArr[i][0],sparseArr[i][1],sparseArr[i][2]);
//输出所在行的第一个数据，第二个数据，第三个数据}
System.out.println();
运行结果：
文章图片
将稀疏数组转换为原来的二维数组：
//将原始的稀疏数组-》恢复成原来的二维数组
//1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
int chessArry2[][]=new int[sparseArr[0][0]][sparseArr[0][1]];
//2.读取稀疏数组后几行的数据—（从第二行开始），并赋值给原始的二维数组
for (int i = 1;
i < sparseArr.length;
i++) {
chessArry2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];
}//输出恢复后的二维数组
for (int[] row : chessArry2) {
for (int data : row) {
System.out.printf("%d\t",data);
}
System.out.println();
}
}
文章图片
二、队列
- 队列是一个有序列表，可以使用数组或者链表来实现
- 遵循先入先出的原则，即：先存入队列的数据，要先取出，后存入的要后取出
- 示意图：front随着数据输出而改变，rear随着数据输入而改变
文章图片
- 将尾指针往后移。rear+1，当front=rear则表明队列为空
- 若尾指针rear小于队列最大下标maxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据，rear==maxSize-1表明队列满
//编写一个叫做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++;
//front后移
return arr[front];
}//显示所有队列数据
publicvoid 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];
}
文章图片
三、数组模拟环型队列 （1）问题分析及优化
- 目前数组使用一次就不能用，没有达到复用效果
- 将这个数组使用算法，改进成一个环型队列
- front变量的含义做一个调整：front指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素，front初始值=0
- rear变量的含义做一个调整：rear指向队列最后一个元素的后一个位置，因为希望空出一个空间作为约定；rear初始值=0
- 当队列满时：（rear+1）%maxSize=front【满】
- 当队列为空的条件：rear=front【空】
5.队列中有效的数据的个数：（rear+maxSize-front）%maxSize
public class CircleArrayQueueDemo {
public static void main(String[] args) {
//数组模拟环型队列
System.out.println("测试数组模拟环型队列的案例~~~~~");
//创建一个环型队列
CircleArrray queue = new CircleArrray(4);
//设置为4，其实有效使用空间为3
char key=' ';
//接受用户输入
Scanner scanner = new Scanner(System.in);
boolean loop=true;
while (loop) {
System.out.println("s(show):显示队列");
System.out.println("e(excit):退出程序");
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 = https://www.it610.com/article/scanner.nextInt();
queue.addQueue(value);
break;
case'g':
try {
int res = queue.getQueue();
System.out.printf("取出的数据是%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int res = queue.headQueue();
System.out.printf("队列头的数据是%d\n", res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e'://退出
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出~~~~~~~~");
}}class CircleArrray{
private int maxSize;
//表示最大容量
private int front;
//队列头
private int rear;
//队列尾
private int[] arr;
//该数组用于存放数据，模拟队列//构造器
public CircleArrray(int arrMaxSize){
maxSize=arrMaxSize;
arr=newint[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是指向队列的第一个元素//先将front对应的值保存到一个临时变量
int value=https://www.it610.com/article/arr[front];
//将front后移
front= (front+1)%maxSize;
//将临时保存的变量返回
returnvalue;
}//显示所有队列数据
publicvoid showQueue(){
//遍历
if (isEmpty()){
System.out.println("队列时空的，没有数据");
return;
}
//从front开始遍历，遍历多少个元素for (int i = front;
i < front+size();
i++) {
System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
}
}//显示队列的头数据，注意不是取数据
public int headQueue(){
//判断
if (isEmpty()){
throw new RuntimeException("队列是空的，没有数据");
}
return arr[front];
}//求出当前队列有效数据个数：
publicint size(){
return (rear+maxSize-front) % maxSize;
}}运行结果展示：
文章图片
【数据结构和算法|【大厂必会的数据结构和算法】01-稀疏数组和队列】如果感觉内容写的还不错的话，一键三连不迷路！！！！
后面将会更新更多学习内容，一起学习吧！！！！！！
文章图片
推荐阅读
- 算法/数据结构|数据结构与算法_01_时间复杂度和空间复杂度
- 数据结构初阶|【C语言 - 数据结构】树、二叉树（下篇）
- c++|C++八种排序算法万字详解
- 算法/数据结构|数据结构与算法_合集导航
- 如何在Java中向左或向右旋转数组（）
- 如何在Binary Search Tree中实现减小键或更改键（）
- 如何识别一种语言是否正常（）
- 如何处理二叉搜索树中的重复项（）
- 如何从PHP中的路径获取文件名（）