数据结构与算法.md

算法

质数算法

public boolean isPrime(int n) {
    if (n == 2) {
        return true;
    }
    for (int i = 2; i*i <= n; i++) {
        if (n%i==0){
            return true;
        }
    }
    return false;
}

线性结构和非线性结构

线性结构

线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。

线性结构有两种不同的存储结构，即顺序存储结构（数组）和链式存储结构（链表）。顺序存储的线性表称为顺序表，顺序表中的存储元素是连续的链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息。线性结构常见的有：数组、队列、链表和栈。

非线性结构

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

稀疏数组（sparse array）

二维数组记录了很多无意义的值（默认0），稀疏数组记录数组一共有几行几列，有多少不同的值。

把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。

demo

public class SparseArray {

    public static void main(String[] args) {

        // 定义棋盘 1是白子，2是黑子
        int[][] chessArr = new int[11][11];
        // record
        int num = 0;
        // initial chess
        chessArr[2][3] = 1;
        chessArr[4][2] = 2;

        System.out.println("棋盘");
        for (int[] row : chessArr) {
            for (int data : row) {
                System.out.print(data + "\t");
                if (data != 0) {
                    num++;
                }
            }
            System.out.println();
        }

        // 转化成稀疏数组
        int[][] sparseArr = new int[num + 1][3];
        sparseArr[0][0] = chessArr.length;
        sparseArr[0][1] = chessArr.length;
        sparseArr[0][2] = num;
        int temp = 0;
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr.length; j++) {
                if (chessArr[i][j] != 0) {
                    temp++;
                    sparseArr[temp][0] = i;
                    sparseArr[temp][1] = j;
                    sparseArr[temp][2] = chessArr[i][j];
                }
            }
        }

        // 打印稀疏数组
        System.out.println("稀疏数组");
        for (int[] row : sparseArr) {
            for (int data : row) {
                System.out.print(data + "\t");
                if (data != 0) {
                    num++;
                }
            }
            System.out.println();
        }

        //由稀疏数组还原棋盘
        int[][] reduceChessArr = new int[sparseArr[0][0]][sparseArr[0][1]];
        for (int i = 0; i < sparseArr.length - 1; i++) {
            reduceChessArr[sparseArr[i + 1][0]][sparseArr[i + 1][1]] = sparseArr[i + 1][2];
        }

        // 打印还原棋盘
        System.out.println("还原棋盘");
        for (int[] row : reduceChessArr) {
            for (int data : row) {
                System.out.print(data + "\t");
                if (data != 0) {
                    num++;
                }
            }
            System.out.println();
        }

    }


}

队列

介绍

• 队列是一个有序列表，可以用数组或链表来实现。
• 遵循先入先出的原则。即：现存入队列的数据，要先取出。后存入队列的数据要后取出。
• 示意图（数组模拟）

环形队列

预留一个位置做计算

front：0

rear：0

maxSize：n

队列满：（rear+1）%maxSize == front

队列空：front == rear

链表（linked list）

栈（stake）

介绍

• 先入后出（First-In-Last-Out）的有序列表
• 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶（Top），另一端为固定的一段，称为栈底（Bottom）。
• 根据栈的定义可知，最先放入栈中元素在栈底，最后放入元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。

应用

• 子程序的调用：在跳往子程序前，会先将下一个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
• 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
• 表达式的转换【中缀表达式转后缀表达式】与求值（实际解决）
• 二叉树的遍历
• 图形的深度优先（depth-first）搜索法