稀疏數組與環形數組_ZenDei技術網路在線

數據結構與演算法的關係數據結構(data structure)是一門研究組織數據方式的學科，有了編程語言也就有了數據結構。學好數據結構可以編寫出跟家漂亮，更加有效率的代碼要學好數據結構就要多多考慮如何將生活中遇到的問題，用程式去實現解決程式=數據結構+演算法數據結構是演算法的基礎，換言之，想要學好 ...

數據結構與演算法的關係

數據結構(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];
    }
}