資料結構與算法内容介紹與概述

話不多說，懂得都懂，不想被時代遺忘？不想一再錯過機會，算法還不會？兩個月後你會感謝現在的選擇，跟着部落客一起學算法吧。

一、 資料結構和算法内容介紹

1. 字元串比對問題

最快的速度進行比對

str=”查德常你好查德你常查德你好”

str= “查德你常查德”

如果讓你做，你是不是會用

• 暴力比對法

  但是如果你會算法你會用

• KMP 部分比對表

2. 漢諾塔遊戲

将A 塔的所有圓盤移動到 C 塔，小圓盤上不能放大圓盤，在三根柱子之間一次隻能移動一個圓盤

如果你會算法，你用以下算法會很好解決

• 分治算法

3. 八皇後問題

古老而著名的問題

8*8的棋盤上擺放八個皇後，使其不能互相攻擊，即：任意兩個皇後不能再同一行，同一列或者統一斜線上，問有多少種擺法

如果你會算法，你用以下算法會很好解決

• 回溯算法

4. 馬踏棋盤算法也稱騎士周遊問題

國際象棋8*8的棋盤，馬按照日字走，每個方格隻走一次，走遍整個棋盤的方格

如果你會算法，你用以下算法會很好解決

深度優化周遊算法（DFS）+貪心算法優化算法是程式的靈魂，優秀的程式在海量資料計算時，依然保持告訴計算。一般情況下記憶體計算架構（Spark）和緩存技術（比如Rides）來優化程式，思考一下，計算架構和緩存技術，他的核心也是算法。資料結構和算法是公司篩選人才的依據。 程式員門檻越來越高了，不學算法會落伍。

二、資料結構和算法的概述

資料結構是一門研究研究組織資料方式的學科，有了程式設計語言就有了算法。 資料結構是算法的基礎。 程式 = 資料結構 + 算法

實際程式設計中遇到的問題

1. 五子棋替換問題

如何判斷遊戲的輸赢，并可以完成存盤推出和繼續上局的功能

1）棋盤 二維數組=》（稀疏數組）=》寫入檔案【存檔】

2）讀取檔案=》稀疏數組=》二維數組=》棋盤【接上局】

資料結構包括：線性結構+非線性結構

線性結構：

存儲元素是連續的指的是位址是連續的。

非線性結構：

2. 應用場景

從 6 * 7 = 42 個資料

轉換為稀疏數組變為 9 * 3 = 27 個資料

起到了使原始數組變小的作用。

3. 應用執行個體(重點)

1）使用稀疏數組，來保留類似前面的二維數組（棋盤）

2）把稀疏數組存盤，并可以重新回複原來的二維數組

3）整體思路分析

轉為稀疏數組的思路

1.周遊原始的二維數組，得到有效資料的個數sum

2.根據個數就可以建立稀疏數組的spareArr int[sum+1][3]

3.将二維數組的有效資料存入到稀疏數組中

恢複的思路

1.先讀取第一行根據第一行的資料建立原始的二維數組chessArr2=int[11][11]

2.再其他資料指派給原始的二維數組即可

代碼實作：

建立原始的棋盤，二維數組

public class sparseArr {
    public static void main(String[] args) {
        int chessArr1[][] = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        System.out.println("原始的二維數組");
        for (int[] row: chessArr1) {
            for (int data: row) {
                System.out.printf("%d\t",data);
            }
            System.out.println();
        }
    }
}
           

結果：

求sum,一共有多少非零個數

int sum = 0;
for (int i = 0; i < chessArr1.length; i++){
    for (int j = 0; j < chessArr1.length; j++) {
        if(chessArr1[i][j]!=0){sum++;}
    }
}
System.out.println(sum);
           

得出結果2

建立稀疏數組并指派

int sparseArr[][] = new int[sum+1][3];
//給稀疏數組指派
sparseArr[0][0] = 11;
sparseArr[0][1] = 11;
sparseArr[0][2] = sum;

int count = 0;
for (int i = 0; i < chessArr1.length; i++){
    for (int j = 0; j < chessArr1.length; j++) {
        if(chessArr1[i][j]!=0){
            count++;
            sparseArr[count][0] = i;
            sparseArr[count][1] = j;
            sparseArr[count][2] = chessArr1[i][j];
        }
    }
}

for(int[] row: sparseArr){
    for (int data : row){
        System.out.printf("%d\t",data);
    }
    System.out.println();
}
           

得到稀疏數組

将稀疏數組恢複成原始的數組（棋盤）

重新建立二維數組（棋盤）chessArr2

int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
int rowNum = 0;
//已知稀疏數組有3列
for (int[] row: sparseArr) {
    rowNum++;
}
for(int i = 1; i < rowNum; i++){
    chessArr2[sparseArr[i][0]][sparseArr[i][1]]=sparseArr[i][2];
}

for (int[] row: chessArr2){
    for (int data: row){
        System.out.printf("%d\t",data);
    }
    System.out.println();
}
           

運作結果

可以看出二維數組可以極大的節省我們的存儲空間