(一)稀疏数组、数组队列

2019-07-13 本文已影响0人 guideEmotion

一线性结构

数据元素之间存在一对一的线性关系

顺序存储结构

顺序表中的存储元素是连续的

链式存储结构

链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息

二非线性结构

非线性结构包括：二维数组，多维数组，广义表，树结构，图结构

三稀疏数组

当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是:

记录数组一共有几行几列，有多少个不同的值
把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模
image.png
image.png

实战

使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
把稀疏数组存盘，并且可以从新恢复原来的二维数组数
整体思路分析

image.png

思路

二维数组转稀疏数组

遍历原始数组，得到有效数据的个数sum
创建一个稀疏数组int[sum+1][3]（如果值只有0，1；则可以省略第三列。第一行可以放默认值,规则自定义）。这里放第一行二维数组的行列数以及sum
将二维数组的有效数据依次记录

稀疏数组还原二维数组

根据第一行创建一个默认值的二维数组
从第二行开始遍历，还原有效数值

代码

    /**
     * 获得一个原始二维数组
     * @return
     */
    public int[][] getOriginArray(){
        int[][] origin = new int[10][12];
        origin[2][8] = 1;
        origin[9][11] = 90;
        origin[8][5] = 123;
        origin[6][6] = 99;
        origin[7][4] = 6;
        origin[3][1] = 618;
        origin[5][9] = 111;
        return origin;

    }

    /**
     * 转换成稀疏数组
     * @param origin
     * @return
     */
    public int[][] tranSparseArray(int[][] origin){
        int sum = 0;
        int rows = origin.length;
        int columns = origin[0].length;
        for(int i=0;i<rows;i++){
            int[] row= origin[i];
            for(int j=0;j<columns;j++){
                if(row[j]!=0){
                    sum++;
                }
            }
        }
        int[][] sparseArray = new int[sum+1][3];
        sparseArray[0][0] = sum;
        sparseArray[0][1] = rows;
        sparseArray[0][2] = columns;
        int index = 1;
        for(int i=0;i<rows;i++){
            int[] row= origin[i];
            for(int j=0;j<columns;j++){
                if(row[j]!=0){
                    sparseArray[index][0] = i;
                    sparseArray[index][1] = j;
                    sparseArray[index][2] = row[j];
                    index ++;
                }
            }
        }
        return sparseArray;

    }

    /**
     * 稀疏数组还原
     * @param sparseArray
     * @return
     */
    public int[][] recovery(int[][] sparseArray){
        int rows = sparseArray[0][1];
        int columns = sparseArray[0][2];
        int[][] orgins = new int[rows][columns];
        for(int index=1;index<sparseArray.length;index++){
            int row = sparseArray[index][0];
            int column = sparseArray[index][1];
            int value = sparseArray[index][2];
            orgins[row][column] = value;

        }
        return orgins;
    }

工具方法

    /**
     * 打印二维数组
     * @param array
     */
    public static void printTwoDimArray(int[][] array){
        for(int i = 0;i<array.length;i++){
            System.out.print("[");
            for(int j=0;j<array[i].length;j++){
                System.out.print("\t"+array[i][j]);
            }
            System.out.println("\t"+"]");

        }
    }

测试

    @Test
    public void test() {
        int[][] origin = getOriginArray();
        ArrayUtils.printTwoDimArray(origin);

        System.out.println("-----------");

        int[][] sparseArray = tranSparseArray(origin);
        ArrayUtils.printTwoDimArray(sparseArray);

        System.out.println("-----------");

        int[][] recoverys = recovery(sparseArray);
        ArrayUtils.printTwoDimArray(recoverys);


    }

四队列

队列是一个有序列表，可以用数组或是链表来实现
遵循先入先出的原则

数组实现

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示:

我的定义和图不同，front（rear）指向下一个要取（加）得元素得前一个下标

image.png

思路

取数据后，front+1；加数据后，rear+1（rear总是大于等于front）
封装一个数据机构
当front=maxSize-1时，队列满了

代码

package com.zyc;

import org.junit.Test;

/**
 * @author zhuyc
 * @create 2019-07-13 16:25
 */
public class ArrayQueue {

    private int front;//下一个坐标就是要取得元素坐标
    private int rear;//下一个坐标就是增加元素得坐标
    private int maxSize;
    private int[] array;

    public ArrayQueue(int maxSize){
        front = -1;
        rear = -1;
        this.maxSize = maxSize;
        array = new int[maxSize];

    }

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

    public boolean isEmpty(){
        return front==rear;//一样表示放的都取出来了
    }

    public void push(int value){
        if(isFull()){
            throw new RuntimeException("队列已满");
        }
        array[++rear] = value;
    }

    public int pop(){
        if(isEmpty()){
            throw new RuntimeException("空队列");
        }

        return array[++front];
    }


    public void showValidQueue(){
        if(isEmpty()){
            System.out.println("空队列");
        }else{
            for(int i = front;i<rear;i++){
                System.out.printf("数组[%d]=%d",i+1,array[i+1]);
            }
            System.out.println();
        }

    }

    public void showQueue(){
        if(isEmpty()){
            System.out.println("空队列");
        }else{
            for(int i = 0;i<maxSize;i++){
                System.out.printf("数组[%d]=%d",i,array[i]);
            }
            System.out.println();
        }

    }

    public int head(){
        if(isEmpty()){
            throw new RuntimeException("空队列");
        }
        int index = front +1;
        return array[index];
    }
}

测试

    @org.junit.Test
    public void test(){
        ArrayQueue queue = new ArrayQueue(10);
        queue.push(23);
        queue.push(28);
        queue.push(1);
        queue.push(3);
        System.out.println("-------");
        queue.showQueue();
        queue.showValidQueue();
        System.out.println("-------");
        System.out.println(queue.pop());
        System.out.println(queue.head());
        System.out.println(queue.pop());
        System.out.println("-------");
        queue.showQueue();
        queue.showValidQueue();




    }

数组模拟环形队列

上面的队列的空间是不可复用，下面我们要进行优化

思路分析

front和rear对maxSize取模后的值范围[0,maxSize-1]正好是数组的有效下标范围
rear-front<maxSize,否则就超出了容量(这样就处理了覆盖的问题)
取下标时我们需要对front(rear)取模
当front和rear同时超过maxSize时，作一次重置操作(两者都等于取模后的值，这样可以避免无限增长)
当maxSize=2的n次方时，可以用&maxSize-1操作代替取模

代码

package com.zyc;

import org.junit.Test;

/**
 * @author zhuyc
 * @create 2019-07-13 16:25
 */
public class ArrayQueue {

    private int front;//下一个坐标就是要取得元素坐标
    private int rear;//下一个坐标就是增加元素得坐标
    private int maxSize;
    private int[] array;

    public ArrayQueue(int maxSize){
        front = -1;
        rear = -1;
        this.maxSize = maxSize;
        array = new int[maxSize];

    }

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

    public boolean isEmpty(){
        return front==rear;//一样表示放的都取出来了
    }

    public void push(int value){
        if(isFull()){
            throw new RuntimeException("队列已满");
        }


        int index = ++rear%maxSize;
        array[index] = value;
    }

    public int pop(){
        if(isEmpty()){
            throw new RuntimeException("空队列");
        }
        if(front==maxSize){//重置
            front = front%maxSize;
            rear = rear%maxSize;
        }
        int index = ++front%maxSize;
        return array[index];
    }


    public void showValidQueue(){
        if(isEmpty()){
            System.out.println("空队列");
        }else{
            for(int i = front;i<rear;i++){
                int index = (i+1)%maxSize;
                System.out.printf("数组[%d]=%d",index,array[index]);
            }
            System.out.println();
        }

    }

    public void showQueue(){
        if(isEmpty()){
            System.out.println("空队列");
        }else{
            for(int i = 0;i<maxSize;i++){
                System.out.printf("数组[%d]=%d",i,array[i]);
            }
            System.out.println();
        }

    }

    public int head(){
        if(isEmpty()){
            throw new RuntimeException("空队列");
        }
        int index = (front +1)%maxSize;
        return array[index];
    }





}

测试

    @Test
    public void testArrayQueue2(){
        ArrayQueue queue = new ArrayQueue(4);
        queue.push(1);
        queue.push(2);
        queue.push(3);
        queue.push(4);
        System.out.println("-------");
        queue.showQueue();
        queue.showValidQueue();
        System.out.println("-------");
        System.out.println(queue.pop());
        System.out.println(queue.head());
        System.out.println(queue.pop());
        System.out.println("-------");
        queue.showQueue();
        queue.showValidQueue();
        System.out.println("-------");
        queue.push(5);
        queue.push(6);
        queue.showQueue();
        queue.showValidQueue();
        System.out.println("-------");
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        queue.push(7);
        queue.push(8);
        queue.push(9);
        queue.push(10);
        System.out.println("-------");
        queue.showQueue();
        queue.showValidQueue();
        System.out.println("-------");
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println(queue.pop());
        System.out.println("-------");
        queue.showQueue();
        queue.showValidQueue();
        System.out.println("-------");
        queue.push(11);
        System.out.println(queue.pop());
        System.out.println("end");


    }

(一)稀疏数组、数组队列

一线性结构

顺序存储结构

链式存储结构

二非线性结构

三稀疏数组

实战

思路

代码

四队列

数组实现

思路

代码

测试

数组模拟环形队列

思路分析

代码

测试

猜你喜欢

热点阅读

(一)稀疏数组、数组队列

一 线性结构

顺序存储结构

链式存储结构

二 非线性结构

三 稀疏数组

实战

思路

代码

四 队列

数组实现

思路

代码

测试

数组模拟环形队列

思路分析

代码

测试

猜你喜欢

热点阅读

一线性结构

二非线性结构

三稀疏数组

四队列