数据结构

链表

约瑟夫问题

// 约瑟夫问题 n个小孩围城一圈，从第k个小孩开始报数，当数到m的小孩出列，下个小孩继续开始从1报数到m，直到小孩全部出列


// 环形链表
public class CircleNode {
    public int id;
    public CircleNode next;
}


public class JosephusCase {
    //记录头节点
    static CircleNode head = new CircleNode();
	//记录当前节点
    static CircleNode currentNode = head;
	//临时节点
    static CircleNode tempNode = head;
	//主函数
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入有多少个人参加游戏：");
        int n = scanner.nextInt();
        head.id = 1;
        currentNode = head;
        tempNode = head;
		// 创建出n个节点
        for (int i=2;i<=n;i++){
            tempNode = new CircleNode();
            tempNode.id = i;
            currentNode.next = tempNode;
            currentNode = tempNode;
        }
		// 尾节点指向头节点，形成环形结构
        tempNode.next = head;
        currentNode = head;
        System.out.println("请输入从第几个人开机计数：");
        int k = scanner.nextInt();
        for (int i=1;i<k;i++){
            currentNode = currentNode.next;
        }
        System.out.println("请输入数到多少出列：");
        int m = scanner.nextInt();
        System.out.print("结果为：");
        rank(m);
    }
	//出列方法
    public static void rank(int m){
		//判断队列中是否为只剩下一个节点
        if (currentNode.next == currentNode){
            System.out.print(currentNode.id + " ");
            return;
        }
		//开始计数
        for (int i=1;i<m;i++){
            tempNode = currentNode;
            currentNode = currentNode.next;
        }
        System.out.print(currentNode.id + " ");
		//去除当前节点，并开始下一次数数
        tempNode.next = currentNode.next;
        currentNode = tempNode.next;
        rank(m);
    }
}

栈

计算器

// 自定义栈
public class MyStack<E> {
        private int index = 0;

        private E[] myStack;

        public MyStack(Class<E> clz){
            myStack = (E[]) Array.newInstance(clz,10);
        }

        public MyStack(Class<E> clz,Integer size){
            myStack = (E[]) Array.newInstance(clz,size);
        }

        public void push(E e) throws Exception {
            if (index == myStack.length){
                throw new Exception("栈已满");
            }
            myStack[index++] = e;
        }

        public E pop() throws  Exception{
            if (index == 0){
                throw new Exception("栈中没有数据");
            }
            return myStack[--index];
        }

        public E peek(){
            if (index == 0){
                return null;
            }
            return myStack[index-1];
        }
}


public class CalculatorCase {

    static MyStack<Integer> numStack = new MyStack<>(Integer.class);

    static MyStack<String> optStack = new MyStack<>(String.class);

    public static void main(String[] args) throws Exception {
        Scanner scanner = new Scanner(System.in);

        System.out.print("请输入表达式：");

        String origin = scanner.nextLine();

        String[] strs = origin.split("");
		//将数字和操作符分别加入到不同的栈中
        for (String str : strs) {
            if (str.equals("+")|str.equals("-")|str.equals("*")|str.equals("/")){
                addOpt(str);
            }else {
                addNum(str);
            }
        }
        int result = getResult();
        System.out.println("结果为：" + result);
    }
	//栈添加操作符
    public static void addOpt(String s) throws Exception {
        String opt;
        switch (s){
            case "+" :
                opt = optStack.peek();
                //如果栈为空添加
                if (opt == null) {optStack.push(s);break;}
				//如果栈中之前的操作符运算级别更大，先消费掉栈中的数据
                if (opt.equals("*")|opt.equals("/")){
                    int num1 = numStack.pop();
                    int num2 = numStack.pop();
                    if (opt.equals("*")) numStack.push(num1*num2);
                    if (opt.equals("/")) numStack.push(num1/num2);
                    optStack.pop();
                    optStack.push(s);
                }
                else optStack.push(s);
                break;
            case "-" :
                opt = optStack.peek();
                if (opt == null) optStack.push(s);
                if (opt.equals("*")|opt.equals("/")){
                    int num1 = numStack.pop();
                    int num2 = numStack.pop();
                    if (opt.equals("*")) numStack.push(num1*num2);
                    if (opt.equals("/")) numStack.push(num1/num2);
                    optStack.pop();
                    optStack.push(s);
                }
                else optStack.push(s);
                break;
            case "*" :
                optStack.push(s);
                break;
            case "/" :
                optStack.push(s);
                break;
        }

    }

    public static void addNum(String s) throws Exception {
        numStack.push(Integer.parseInt(s));
    }
	//处理栈，进行运算
    public static int getResult() throws Exception {
        String opt;
        while(optStack.peek()!=null){
             opt = optStack.pop();
             int num1 = numStack.pop();
             int num2 = numStack.pop();
             switch (opt){
                 case "+" : numStack.push(num1+num2);break;
                 case "-" : numStack.push(num1-num2);break;
                 case "*" : numStack.push(num1*num2);break;
                 case "/" : numStack.push(num1/num2);break;
             }
        }
        return numStack.peek();
    }
}

后缀计算（逆波兰）

1 初始化两个栈：运算符栈1和存储中间结果的栈2
2 从左至右扫描中缀表达式
3 遇到操作数，将其压入中间栈2

4 遇到运算符，比较宇栈1栈顶运算符的优先级
4.1 如果栈1为空，或者栈顶运算符为"("，直接将此运算符压入栈1
4.2 否则，如果优先级高于栈1栈顶优先级，压入栈1
4.3 否则，将栈1栈顶运算符转移到栈2中，继续进行操作4，与栈1新的栈顶进行比较

5 遇到括号
5.1 如果左括号"("，直接压入栈1
5.2 如果为右括号")"，依次将栈1操作数转移到栈2中，知道与一个左括号抵消

6 重复步骤2至5，知道表达式最右边
7 将s1剩余操作数依次转移到s2中
8 依次弹出s2中的元素，其逆序

递归

迷宫问题

//设置一个二维数组，其中 0代表未走过，1代表墙，2为路径，3为死路
public class MazeCase {
    public static void main(String[] args) {
        int [][] maze = initMaze();
        findWay(maze,1,1);
        printMaze(maze);
    }
    //初始化迷宫
    public static int[][] initMaze(){
        int[][] maze = new int[8][8];
        for (int i =0;i<8;i++){
            maze[0][i] = 1;
            maze[7][i] = 1;
        }
        for (int j =0;j<8;j++){
            maze[j][0] = 1;
            maze[j][7] = 1;
        }
        maze[4][4] = 1;
        maze[3][2] = 1;
        maze[6][5] = 1;
        printMaze(maze);
        return maze;
    }
    //打印迷宫状态
    public static void printMaze(int[][] maze){
        System.out.println("迷宫形状为：");
        for (int i=0;i<8;i++){
            for (int j=0;j<8;j++){
                System.out.print(maze[i][j] + " ");
            }
            System.out.println("");
        }
    }
    //递归寻找路径
    public static boolean findWay(int[][] maze,int i,int j){
        //如果到达终点，返回成功
        if (i==6&j==6) {maze[i][j] = 2;return true;}
        //如果路径未走过就开始判断
        else if (maze[i][j] == 0){
            maze[i][j] = 2;
            if (findWay(maze,i+1,j)) return true;
            else if (findWay(maze,i,j+1)) return true;
            else if (findWay(maze,i-1,j)) return true;
            else if (findWay(maze,i,j-1)) return true;
            else {maze[i][j] = 3;return false;}
        }
        //其他情况都返回错误
        else {
            return false;
        }
    }
}

八皇后

public class EightQueenCase {
	//主函数
    public static void main(String[] args) {
        int[][] chess = initChess(8);
        printChess(chess);
        layoutQueen(chess,0);
    }
	//初始化棋盘
    public static int[][] initChess(int num){
        return new int[num][num];
    }
    //打印棋盘状态
    public static void printChess(int[][] chess){
        count++;
        System.out.println("棋盘形状为：");
        for (int i=0;i<chess.length;i++){
            for (int j=0;j<chess[0].length;j++){
                System.out.print(chess[i][j] + " ");
            }
            System.out.println("");
        }
    }
    //判断当前位置是否可以落棋
    //n：第n个棋子（第n行）
    //k：第n列
    //i：第i个棋子
    //k：第j个棋子的位置
    public static boolean check(int[][] chess,int n,int k){
        if (n==0) {
            return true;
        }
        else{
            for (int i=0;i<n;i++){
                int j = findIndex(chess[i]);
                //向量
                if (j==k|Math.abs(n-i)==Math.abs(j-k)) {
                    return false;}
            }
            return true;
        }
    }
    //招出当前棋子位置（第多少列）
    public static int findIndex(int[] chessLine){
        int index = 0;
        for (int i=0;i<chessLine.length;i++){
            if (chessLine[i] == 1){
                index = i;
                break;
            }
        }
        return index;
    }
    //放置棋子
    public static boolean layoutQueen(int[][] chess,int n){
        if (n == chess.length){
            //n个棋子已经全部放置，返回true
            return true;
        }
        for (int i=0;i<chess.length;i++){
            if (check(chess,n,i)){
                //如果可以放置该棋子，就改变放置当前棋子
                chess[n][i] = 1;
                if (layoutQueen(chess,n+1)){
                    //放置下一颗棋子
                    printChess(chess);
                }
                //改变回原来状态，进行循环
                chess[n][i] = 0;
            }
        }
        return false;
    }
}

排序

工具类

public class ArrayUtil {
    public static int[] getOriginArray(){
        Random random = new Random();
        int[] array = new int[random.nextInt(30)];
        for (int i=0;i<array.length;i++){
            array[i] = random.nextInt(100);
        }
        return array;
    }
    public static void printArray(int[] array){
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println("");
    }
    public static void exchangeNums(int[] array,int i,int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

插入排序

public class InsertSort {
    public static int[] insertSort(int[] array){
        for (int i=1;i<array.length;i++){
            for (int j=i-1;j>=0;j--){
                if (array[j+1]<array[j]){
                    ArrayUtil.exchangeNums(array,j,j+1);
                }else{
                    break;
                }
            }
        }
        return array;
    }
}

希尔排序

public class ShellSort {
    public static int[] shellSort(int[] array){
        int h = 1;
        while (h<array.length/2){
            h=2*h+1;
        }
        while (h>=1){
            for (int i=0;i<h;i++){
                //根据h进行局部排序
                partSort(array,i,h);
            }
            h=h/2;
        }
        return array;
    }
    //插入排序
    public static void partSort(int[] array,int index,int h){
        for (int i = index+h;i<array.length;i=i+h){
            for (int j = i-h;j>=index;j=j-h){
                if (array[j+h]<array[j]){
                    ArrayUtil.exchangeNums(array,j,j+h);
                }else{
                    break;
                }
            }
        }
    }
}

快速排序

public class FastSort {
    public static int[] fastsort(int[] array){
        array = partSort(array,0,array.length-1);
        return array;
    }
	//部分排序
    public static int[] partSort(int[] array,int start,int end){
        int mid = start + (end-start)/2;
        int tempstart = start;
        int tempend = end;
        boolean preFlag = false;
        boolean forFlag = false;
        //如果分片的大小等于1直接返回
        if (start == end) return array;
        //分片大小等于2，两个树排序返回
        if ((end-start)==1){
            if (array[start]>array[end]){
                ArrayUtil.exchangeNums(array,start,end);
            }
            return array;
        }
        //选择中间的数进行排序，小于中间数的数在左边，大于中间数的数在邮编
        while (start<end){
            //判断左边是否出现了大于中间数
            while(array[start]<=array[mid] & start<mid){
                start++;
            }
            if (array[start]>array[mid]){
                preFlag = true;
            }
			//判断右边是否出现了小于中间数
            while(array[end]>=array[mid] & end>mid){
                end--;
            }
            if (array[end]<array[mid]){
                forFlag = true;
            }
			//同时出现，交换两个数
            if (preFlag & forFlag){
                ArrayUtil.exchangeNums(array,start,end);
                preFlag = false;
                forFlag = false;
            }
            //左边有大于中间数的数，而右边已经判断完成
            if (preFlag & end==mid){
                int temp = start;
                int tempNum = array[start];
                while (temp<mid){
                    array[temp] = array[temp+1];
                    temp++;
                }
                array[temp] = tempNum;
                mid = mid-1;
                end = end -1;
                preFlag = false;
            }
            //右边有小于中间数的数，而左边已经判断完成
            if (forFlag & start==mid){
                int temp = end;
                int tempNum = array[end];
                while (temp>mid){
                    array[temp] = array[temp-1];
                    temp--;
                }
                array[temp] = tempNum;
                mid = mid+1;
                start = start+1;
                forFlag=false;
            }
        }
        //进行细分
        if (start!=tempstart){partSort(array,tempstart,mid-1);}
        if (end != tempend){partSort(array,mid+1,tempend);}
        return array;
    }
}

分治排序

public class MergeSort {
    public static int[] mergeSort(int[] array){
        int[] temp = array.clone();
        divide(array,temp,0,array.length-1);
        return array;
    }
    //递归调用
    private static int[] divide(int[] array,int[] temp,int start,int end){
        if (start == end) return array;
        if ((end-start)==1) {
            if (array[start]>array[end]){
                ArrayUtil.exchangeNums(array,start,end);
                ArrayUtil.exchangeNums(temp,start,end);
                return array;
            }
        }
        int mid = start+(end-start)/2;
        //左边递归
        divide(array,temp,start,mid);
        //右边递归
        divide(array,temp,mid+1,end);
        //合并
        merge(array,temp,start,mid,end);
        return array;
    }
    private static int[] merge(int[] array, int[] temp,int start, int mid, int end) {
        int preindex = start;
        int forindex = mid+1;
        int index = start;
        while (preindex<=mid & forindex<=end){
            if (array[preindex] < array[forindex]){
                temp[index++] = array[preindex++];
            }else if (array[forindex] < array[preindex]){
                temp[index++] = array[forindex++];
            }
            else if (array[preindex] == array[forindex]){
                temp[index++] = array[preindex++];
                temp[index++] = array[forindex++];
            }
        }
        if (preindex>mid && forindex<=end){
            while(forindex<=end){
                temp[index++] = array[forindex++];
            }
        }
        if (forindex>end && preindex<=mid){
            while (preindex<=mid){
                temp[index++] = array[preindex++];
            }
        }
        for (int i=start;i<=end;i++){
            array[i] = temp[i];
        }
        return array;
    }
}

基数排序

public class RadixSort {
    public static int[] radixSort(int[] array){
		//最大数为几位
        int maxBit = getMaxBit(array);
        //位值
        int bitValue;
        int index = 0;
        int n = 1;
        //有多少位循环多少次
        for (int i=0;i<maxBit;i++,n=n*10){
            //按位存放值
            int[][] container = new int[10][array.length];
            //记录每位有多少值
            int[] containerBit = new int[10];
            for (int j=0;j<array.length;j++){
                bitValue = array[j] / n % 10;
                containerBit[bitValue] = containerBit[bitValue] + 1;
                container[bitValue][containerBit[bitValue]-1] = array[j];
            }
            index = 0;
            for (int j=0;j<container.length;j++){
                for (int k=0;k<containerBit[j];k++){
                    array[index++] = container[j][k];
                }
            }
        }
        return array;
    }
    public static int getMaxBit(int[] array){
        int maxBig = 1;
        int max = array[0];
        for (int i=0;i<array.length;i++){
            if (array[i] > max) {
                max = array[i];
            }
        }
        while(max/10 != 0){
            maxBig++;
            max = max/10;
        }
        return maxBig;
    }
}

查找

线性查找

public class LineSearch {
    public static int lineSearch(int[] array,int value){
        for (int i=0;i<array.length;i++){
            if (array[i] == value){
                return i;
            }
        }
        return -1;
    }
}

二分查找

public class BinarySearch {
    public static int binarySearch(int[] array,int value){

        return halfSearch(array,value,0,array.length-1);
    }
    public static int halfSearch(int[] array,int value,int start,int end){
        int mid = start + (end -start)/2;
        if ((end-start)<=1){
            for (int i=start;i<=end;i++){
                if (array[i] == value){
                    return i;
                }
            }
            return -1;
        }
        if (array[mid] == value){
            return mid;
        }else if (array[mid]>value){
            return halfSearch(array,value,start,mid-1);
        }else if (array[mid]<value){
            return halfSearch(array,value,mid+1,end);
        }
        return -1;
    }
}

插值查找

//二分查找
int mid = start + (end -start)/2;
//插值查找 自适应调整mid位置
int mid = start + (end -start)*(value - array[start])/(array[end]-array[start]);

树

顺序存储二叉树

//顺序二叉树通常只考虑完全二叉树
//第n个元素的左子节点为2*n+1
//第n个元素的右子节点为2*n+2
//第n个元素的父节点为（n-1）/2

public class ArrayBinaryTree {
    private int[] array;

    public void setArray(int[] array){
        this.array = array;
    }
    //前序输出
    public void preOrder(){
        this.preOrder(0);
    }
    public void preOrder(int index){
        if (array == null | array.length==0){
            System.out.println("数组为空");
        }
        System.out.println(array[index]);
        if ((index*2+1)<array.length){
            System.out.println(2*index+1);
        }
        if ((index*2+2)<array.length){
            System.out.println(2*index+2);
        }
    }
}

线索化二叉树

//n个节点的二叉链表中含有n+1【公式2n-(n-1)=n+1】个空指针域，利用二叉链表中的空指针域，存放指向 该节点 在某种遍历次序下的前驱和后驱节点的指针（这种附加的指针成为“线索”）
//这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。根据线索的性质不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后续线索二叉树
//一个节点的前一个节点，称为前驱节点
//一个节点的后一个节点，称为后驱节点

堆排序

public class HeapSort {

    public static int[] heapSort(int[] array){
        //将数组转换为大顶堆
        for (int i = array.length/2-1;i>=0;i--){
            partAdjust(array,i,array.length);
        }
        return  partChange(array,array.length);
    }
    /*
        int[] array : 需要排序的数组
        int i ：需要排序的节点
        int length: 数组需要排序的长度
     */
    public static int[] partAdjust(int[] array,int i,int length){
        int temp = array[i];
        for (int k = (i*2)+1;k<length;k=k*2+1){
            if ((k+1)<length && array[k]<array[k+1]){
                k++;
            }
            if (array[k] > temp){
                array[i] = array[k];
                i = k;
            }else {
                break;
            }
        }
        array[i] = temp;
        return array;
    }
    /*
        length : 数组需要排序的长度
     */
    public static int[] partChange(int[] array,int length){
        if (length==1) return array;
        int temp = array[0];
        array[0] = array[length-1];
        array[length-1] = temp;
        //重新将堆调整为大顶堆,因为只交换了头尾节点，其他数据是排过序的，所以只需对头节点排序即可
        partAdjust(array,0,length-1);
        partChange(array,length-1);
        return array;
    }
}

赫夫曼树

public class HaffmanTree {
    public static HaffmanNode createHaffmanTree(int[] array){
        List<HaffmanNode> list = new ArrayList<>();
        for (int i : array) {
            list.add(new HaffmanNode(i));
        }
        while (list.size()>1){
            //对集合进行排序
            Collections.sort(list);
            //获取最小的两个节点
            HaffmanNode left = list.get(0);
            HaffmanNode right = list.get(1);
            //创建最小节点的父节点
            HaffmanNode parent = new HaffmanNode(left.value+right.value);
            parent.left = left;
            parent.right = right;
            //移除两个小节点添加大节点
            list.remove(left);
            list.remove(right);
            list.add(parent);
        }
        //返回树的头节点
        return list.get(0);
    }
    //前序输出
    public static void preOrder(HaffmanNode node){
        if (node.left != null){
            preOrder(node.left);
        }
        System.out.print(node.value + " ");
        if (node.right != null){
            preOrder(node.right);
        }
    }
}
class HaffmanNode implements Comparable<HaffmanNode>{
    int value;
    HaffmanNode left;
    HaffmanNode right;
    public HaffmanNode(int value){
        this.value = value;
    }
    @Override
    public String toString() {
        return "HaffmanNode{" +
                "value=" + value +
                '}';
    }
    @Override
    public int compareTo(HaffmanNode o) {
        //从小到大
        return this.value - o.value;
    }
}

赫夫曼编码