栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

数据结构与算法(一)——线性结构和非线性结构(稀疏数组和队列)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数据结构与算法(一)——线性结构和非线性结构(稀疏数组和队列)

线性结构和非线性结构(稀疏数组和队列)

目录
    • 线性结构和非线性结构(稀疏数组和队列)
  • 一、线性结构
    • 1、稀疏数组
      • (1)简介
      • (2)稀疏数组的处理方法:
      • (3)应用场景
      • (4)应用实例
        • 1)、使用稀疏数组,来保留类似前面的二维数组(棋盘、地图等)
        • 2)、 把稀疏数组存盘,并且可以重新恢复原来的二维数组
        • 3)、代码实现
    • 2、队列
      • (1)简介
      • (2)数组模拟普通队列
        • 1)数据存入队列
        • 2)代码实现
      • (3)数组模拟环形队列
        • 1)思路分析
        • 2)代码实现

一、线性结构
  • 线性结构作为最常用的数据结构,其特点是数据元素之间存在一对一的线性关系
  • 线性结构有两种不同的存储结构,即顺序存储结构和链式存储结构。顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的
  • 链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素及相邻元素的地址信息。
  • 线性结构常见的有:数组、队列、链表和栈。
1、稀疏数组 (1)简介

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

(2)稀疏数组的处理方法:
  1. 记录数组一种有几行几列,有多少个不同的值。
  2. 把具有不同值的元素的行列及值记录在一个小规模的数组中,从而缩小程序的规模。

    第一行记录原数组有6行,7列,存储8个非0的值
(3)应用场景

比如五子棋程序中,有存盘退出和续上盘的功能。

分析问题:
因为该二维数组的很多值都是默认值0,因此记录了很多没有意义的数据,因此可以采用稀疏数组来存储。

(4)应用实例

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

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

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

稀疏数组转二维数组的思路:
1、读取稀疏数组第一行,根据第一行的数据创建原始二维数组,比如:chessArr2 = int[11][11]。
2、读取稀疏数组后几行的数据,并且赋值给原始的二维数组。

3)、代码实现
public class SparseArray {

    public static void main(String[] args) {
        //创建一个原始的二维数组11*11
        //0 表示没有子 1表示黑子 2表示篮子
        int chessArr[][]  = new int[11][11];
        chessArr[1][2] = 1;
        chessArr[2][4] = 2;
        chessArr[5][7] = 2;
        chessArr[4][8] = 1;
        int index = 1;
        System.out.println("原始二维数组");
        for (int[] row : chessArr){
            for (int data :row){
                System.out.printf("%dt",data);
            }
            System.out.println("读取输出第行"+index);
            index+=1;

        }

        //二维
        System.out.println("二维数组转稀疏数组");
        int[][] sparseArr = SparseArray.convertToSparseArray(chessArr);
        int[][] oldArray =  SparseArray.convertToOldArray(sparseArr);

        int oldArrayIndex = 1;
        System.out.println("转稀疏数组还原原始二维数组");
        for (int[] row : oldArray){
            for (int data :row){
                System.out.printf("%dt",data);
            }
            System.out.println("读取输出第行"+oldArrayIndex);
            oldArrayIndex+=1;

        }


    }

    
    private static int[][]  convertToSparseArray(int[][] oldArray){
        int sum = 0;
        for (int[] ints : oldArray) {
            for (int anInt : ints) {
                if (anInt!=0){
                    sum++;
                }
            }
        }
        System.out.println("稀疏数组总长度"+sum);
        //行
        int rowLen = oldArray.length;
        //列
        int colLen = oldArray[0].length;
        int sparseArr[][] = new int[sum+1][3];
        sparseArr[0][0] = rowLen;
        sparseArr[0][1] = colLen;
        sparseArr[0][2] = sum;

        int sparseArrDataIndex = 1;
        for (int i = 0; i < oldArray.length; i++) {
            for (int j = 0; j < oldArray[i].length; j++) {
                if (oldArray[i][j]!=0){

                    sparseArr[sparseArrDataIndex][0] = i;
                    sparseArr[sparseArrDataIndex][1] = j;
                    sparseArr[sparseArrDataIndex][2] = oldArray[i][j];
                    sparseArrDataIndex++;
                }
            }
        }
        System.out.println("稀疏数组转换完成");
        System.out.println("输出稀疏数组");
        for (int[] ints : sparseArr) {
            for (int anInt : ints) {
                System.out.printf("%dt",anInt);
            }
            System.out.println("输出行");
        }

        return sparseArr;
    }

    
    private static int[][] convertToOldArray(int[][] sparseArr){
        int[][] oldArray = new int[sparseArr[0][0]][sparseArr[0][1]];
        for (int i = 1; i < sparseArr.length; i++) {
            oldArray[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];
        }
        return oldArray;
    }
}

2、队列 (1)简介
  • 队列是一个有序列表,医用数组或者是链表来实现
  • 遵循先入先出原则。即:先存入队列的数据,要先取出。后存入的要后取出。

    front 表示队列头的指针,rear 表示队列尾部的指针
    左侧为初始队列,中间为对列新加,右侧为队列取出元素。
    可以看到添加数据,是从队列尾部插入,移出数据是从对列首部移出。
(2)数组模拟普通队列 1)数据存入队列

当我们将数据存入队列时比如addQueue,插入处理需要两个步骤:

  1. 判断队列是否为空,即front==rear,判断队列是否已满,即rear == maxSize-1,若rear小于最大下标maxSize-1,则数据正常存入,若rear大于等于最大下标maxSize-1,则无法正常存入。
  2. 若可以存入则将尾部指针后移:rear+1,
2)代码实现
import java.util.Scanner;



public class ArrayQueueExample {
    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue(5);
        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':
                    arrayQueue.showQueue();
                    break;
                case 'a':
                    System.out.println("输入一个数");
                    int val = scanner.nextInt();
                    arrayQueue.addQueue(val);
                    break;
                case 'e':
                    scanner.close();
                    loop=false;
                    break;
                case 'g':
                    try {
                        int queue = arrayQueue.getQueue();
                        System.out.printf("取出的数据是%d",queue);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int queue = arrayQueue.showFrontQueue();
                        System.out.printf("查看队列头的数据是%d",queue);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
            }
        }
        System.out.println("退出程序");
    }
}

class ArrayQueue {
    
    private int maxSize;
    
    private int rear;
    
    private int front;
    
    private int[] data;

    //创建队列构造器
    public ArrayQueue() {
    }

    
    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        data = new int[maxSize];
        rear = -1;//指向队列尾部,即就是队列最后一个数据
        front = -1;//指向队列头部的前一个位置
        this.data = data;
    }

    
    public boolean isFull() {
        return rear == maxSize - 1;
    }

    
    public boolean isEmpty() {
        return rear == front;
    }

    
    public void addQueue(int d) {
        if (isFull()) {
            System.out.println("该队列已满,无法加入队列");
            return;
        }
        rear++;
        data[rear] = d;
    }

    
    public int getQueue() {
        //判断队列是否为空
        if (isEmpty()) {
            throw new RuntimeException("队列为空,无法取出数据");
        }
        //front后移
        front++;
        return data[front];
    }

    
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("队列为空,没有数据~~~");
            return;
        }
        for (int i = 0; i < data.length; i++) {
            System.out.printf("data[%d]=%dn", i, data[i]);
        }
    }

    
    public int showFrontQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空,没有数据~~~");
        }

        return data[front + 1];
    }
}
(3)数组模拟环形队列 1)思路分析
  1. front变量的含义做调整,即front从上例的指向队列头部的前一个位置变更为指向队列的第一个元素。front的初始值为0
  2. rear变量的含义做调整,即rear指向队列最后一个元素的后一个位置,因为希望空出一个空间作为约定。rear的初始值为0
  3. 当队列满时,条件为 (rear+1)% maxSzie = front 为队列满了
  4. 当队列为空的条件,即rear = front 为空
  5. 队列中有效的数据个数:(rear + maxSzie - front) %maxSzie
2)代码实现
import java.util.Scanner;



public class CircularArrayQueueExample {
    public static void main(String[] args) {
        CircularArrayQueue arrayQueue = new CircularArrayQueue(5);
        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':
                    arrayQueue.showQueue();
                    break;
                case 'a':
                    System.out.println("输入一个数");
                    int val = scanner.nextInt();
                    arrayQueue.addQueue(val);
                    break;
                case 'e':
                    scanner.close();
                    loop=false;
                    break;
                case 'g':
                    try {
                        int queue = arrayQueue.getQueue();
                        System.out.printf("取出的数据是%d",queue);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int queue = arrayQueue.showFrontQueue();
                        System.out.printf("查看队列头的数据是%d",queue);
                    }catch (Exception e){
                        System.out.println(e.getMessage());
                    }
                    break;
            }
        }
        System.out.println("退出程序");
    }
}

class CircularArrayQueue {
    
    private int maxSize;
    
    private int rear;
    
    private int front;
    
    private int[] data;

    //创建队列构造器
    public CircularArrayQueue() {
    }

    
    public CircularArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        data = new int[maxSize];
        rear = 0;//指向队列最后一个元素的后一个位置
        front = 0;//指向队列的第一个元素
    }

    
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    
    public boolean isEmpty() {
        return rear == front;
    }

    
    public void addQueue(int d) {
        if (isFull()) {
            System.out.println("该队列已满,无法加入队列");
            return;
        }
        //因为rear指向了最后一个元素的后一个位置,因此直接将数据加入
        data[rear] = d;
        //加入数据后需要将rear后移,必须考虑取模
        rear = (rear+1)%maxSize;
    }

    
    public int getQueue() {
        //判断队列是否为空
        if (isEmpty()) {
            throw new RuntimeException("队列为空,无法取出数据");
        }
        //front指向队列第一个元素
        //1、把第一个值存在临时变量
        int frontData = data[front];
        //2、front后移,考虑取模,当front = maxSzie会数组越界
        front = (front+1)%maxSize;
        return frontData;
    }

    
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("队列为空,没有数据~~~");
            return;
        }
        //从front开始遍历,遍历有效个数
        for (int i = front; i < front+validSize(); i++) {
            System.out.printf("data[%d]=%dn", i%maxSize, data[i%maxSize]);
        }
    }

    
    public int validSize(){
        return (rear + maxSize - front) %maxSize;
    }

    
    public int showFrontQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空,没有数据~~~");
        }

        return data[front];
    }
}


转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/986186.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号