本文共 5300 字，大约阅读时间需要 17 分钟。

?????????

????

1.1 ????

???????????????????????????????????????????????????????12x12???????????????????????0?????????????????

1.2 ?????????

?????????????????????????????????????????????????????????????????????????????

1.3 ?????????

1.4 ?????????

package cn.klb.datastructures.sparsearray;public class SparseArray {    /**      * ???????????     * @param chessArray ?????     * @return ????     */    public static int[][] chessToSparse(int[][] chessArray) {        int valueNums = 0;        for (int[] ints : chessArray) {            for (int i : ints) {                if (i != 0) {                    valueNums++;                }            }        }        int row = chessArray.length;        int col = chessArray[0].length;        int[][] sparseArray = new int[valueNums + 1][3];        sparseArray[0][0] = row;        sparseArray[0][1] = col;        sparseArray[0][2] = valueNums;        int index = 1;        for (int i = 1; i < row; i++) {            for (int j = 1; j < col; j++) {                if (chessArray[i][j] != 0) {                    sparseArray[index][0] = i;                    sparseArray[index][1] = j;                    sparseArray[index][2] = chessArray[i][j];                    index++;                }            }        }        return sparseArray;    }    /**      * ??????????????     * @param sparseArray ????     * @return ??????     */    public static int[][] sparseToChess(int[][] sparseArray) {        int row = sparseArray[0][0];        int col = sparseArray[0][1];        int[][] cheeseArray = new int[row][col];        for (int i = 1; i < sparseArray.length; i++) {            cheeseArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];        }        return cheeseArray;    }    /**      * ????     * @param array ??     */    public static void showArray(int[][] array) {        for (int[] ints : array) {            for (int i : ints) {                System.out.print(i + " ");            }            System.out.println();        }    }}### 1.5 ????```javapackage cn.klb.test.datastructurestest;import cn.klb.datastructures.sparsearray.SparseArray;import org.junit.Test;public class SparseArrayTest {    @Test    public void testSparseArray() {        int[][] chessArr1 = new int[12][12];        chessArr1[1][2] = 1;        chessArr1[2][3] = 2;        System.out.println("-----????1--------");        SparseArray.showArray(chessArr1);        System.out.println("-----????-------");        int[][] sparseArr = SparseArray.chessToSparse(chessArr1);        SparseArray.showArray(sparseArr);        System.out.println("-----????2--------");        int[][] chessArr2 = SparseArray.sparseToChess(sparseArr);        SparseArray.showArray(chessArr2);    }}

??

2.1 ????

????????????????????????????????????????????????????

2.2 ???????

????????????????????????????????????????????????

• ??????Enqueue?
• ??????Dequeue?
• ??????????

2.3 ???????????

2.4 ???????

package cn.klb.datastructures.queue;public class ArrayQueue {    private int maxSize; // ??????    private int front;  // ??????    private int rear;   // ??????    private int[] arr; // ????????    public ArrayQueue(int arrMaxSize) {        maxSize = arrMaxSize;        arr = new int[maxSize];    }    /**      * ???????     * @return ???     */    public boolean isFull() {        return (rear + 1) % maxSize == front;    }    /**      * ????????     * @return ????     */    public boolean isEmpty() {        return rear == front;    }    /**      * ???????     * @param n ??????     */    public void add(int n) {        if (isFull()) {            System.out.println("???????????~");            return;        }        arr[rear] = n;        rear = (rear + 1) % maxSize;    }    /**      * ??????     * @return ?????     */    public int getQueue() {        if (isEmpty()) {            throw new RuntimeException("??????????");        }        int value = arr[front];        front = (front + 1) % maxSize;        return value;    }    /**      * ????????     * */    public void showQueue() {        if (isEmpty()) {            System.out.println("????? ????~~");            return;        }        for (int i = front; i < front + size(); i++) {            System.out.print(arr[i % maxSize] + " ");        }        System.out.println();    }    /**      * ?????????????     * @return ????     */    public int size() {        return (rear + maxSize - front) % maxSize;    }}

2.5 ??????

package cn.klb.test.datastructurestest;import cn.klb.datastructures.queue.ArrayQueue;import org.junit.Test;public class ArrayQueueTest {    @Test    public void arrayQueueTest() {        ArrayQueue arrayQueue = new ArrayQueue(5);        System.out.println("-----???0 1 2-----");        arrayQueue.add(0);        arrayQueue.add(1);        arrayQueue.add(2);        arrayQueue.showQueue();        System.out.println("-----????-----");        System.out.println("?????" + arrayQueue.getQueue());        arrayQueue.showQueue();        System.out.println("-----???7 8-----");        arrayQueue.add(7);        arrayQueue.add(8);        arrayQueue.showQueue();    }}

转载地址：http://zbv.baihongyu.com/