数据结构(Java版)_java数据结构

数据结构

数据结构和算法的关系

​ 数据（data）结构（structure）是一门研究组织数据方式的学科，

程序 = 数据机构 + 算法

​ 数据结构和算法的基础

线性结构和非线性结构

数据结构包括：线性结构和非线性结构

线性结构

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

线性结构有两种不同的存储结构，即顺序存储和链式存储结构。顺序存储结构的线性表称为顺序结构，顺序表中的存储元素是连续的

​ 链式存储的线性表称为链表，链表中的存储元素不一定是连续的，元素节点中存放数据元素以及相邻元素的地址信息

​ 线程结构常见的有：数组、队列、链表和栈

非线性结构

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

稀疏数组(Array)

稀疏sparse array数组

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zq1P9TRi-1674801911588)(C:\Users\16510\AppData\Local\Temp\msohtmlclip1\01\clip_image001.png)]

稀疏数组的处理方式：

​ [0]记录有几行几列 [1]…[n]记录值的所在坐标

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-COwq72IT-1674801911589)(C:\Users\16510\AppData\Local\Temp\msohtmlclip1\01\clip_image002.jpg)]

二位数组 转 稀疏数组的思路

​ 遍历 原始的二维数组，得到有效数据的个数 sum

​ 根据sum就可以创建稀疏数组 sparseArr int[sum + 1][3]

​ 将二维数组的有效数据存入到稀疏数组中

稀疏数组 转 原始的二维数组

​ 先读取稀疏数组的第一行，根据第一行的数据创建原始的二维数组，比如上面的chessArr2 = int[11][11]

​ 再读取稀疏数组后几行的数据，并赋值给原始的数组即可

public static void main(String[] args) {
   //创建一个 11 * 11的二维数组
   int[][] array = new int[11][11];
   //0表示没有棋子
   //1表示黑子
   //2表示白子
   array[1][2] = 1;
   array[2][3] = 2;
   array[2][2] = 1;
   System.out.println("原始的二维数组");
   for (int[] row : array) {
       for (int data : row) {
           System.out.printf("%d\t", data);
       }
       System.out.println();
   }


   System.out.println("稀疏数组");
   //将二维数组转换为稀疏数组
   //先遍历二维数组 得到非0数据的个数
   //记录非0数据
   int sum = 0;
   for (int i = 0; i < 11; i++) {
       for (int j = 0; j < 11; j++) {
           if (array[i][j] != 0) {
               sum++;
           }
       }
   }
   //创建对应的稀疏数组
   int[][] sparseArr = new int[sum + 1][3];
   //给稀疏数组赋值
   sparseArr[0][0] = 11;
   sparseArr[0][1] = 11;
   sparseArr[0][2] = sum;
   int s = 1;
   //遍历二维数组，将非0的值存放到sparseArr中
   for (int i = 0; i < 11; i++) {
       for (int j = 0; j < 11; j++) {
           if (array[i][j] != 0) {
               sparseArr[s][0] = i;
               sparseArr[s][1] = j;
               sparseArr[s][2] = array[i][j];
               s++;
           }
       }
   }
   for (int[] row : sparseArr) {
       for (int content : row) {
           System.out.printf("%d\t",content);
       }
       System.out.println();
   }

   //将稀疏数组
   System.out.println("稀疏数组转二维数组");
   int[][] ints = new int[sparseArr[0][0]][sparseArr[0][1]];
   for (int i = 1; i < sparseArr.length; i++) {
       ints[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
   }
   for (int[] rows : ints) {
       for (int content : rows) {
           System.out.printf("%d\t",content);
       }
       System.out.println();
   }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

队列(Queue)

队列是一个有序列表，可以用数组或链表来实现

遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出

队列的实现

class ArrayQueue {
   private int maxSize;//最大容量
   private int front;//队列头
   private int rear;//队列尾
   private int[] arr;//数组存放数据

   public ArrayQueue(int maxSize) {
       this.maxSize = maxSize;
       arr = new int[maxSize];
       front = -1;//指向队列头部，分析出front是指向队列头的前一个位置
       rear = -1;//指向队列尾，指向队列尾的具体的数据（即就是队列的最后一个数据)
   }

   //判断队列是否满
   public boolean isFull() {
       return rear == maxSize - 1;
   }

   //判断队列是否为空
   public boolean isEmpty() {
       return rear == front;
   }

   //添加数据到队列
   public void addQueue(int i) {
       //判断队列是否满
       if (isFull()) {
           System.out.println("队列已满");
           return;
       }
       arr[++rear] = i;
   }

   //获取队列数据
   public int findQueue() {
       if (isEmpty()) {
           throw new RuntimeException("队列数据为空");
       }
       return arr[++front];
   }

   //显示队列
   public void selectArr() {
       if (isEmpty()) {
           System.out.println("队列为空");
           return;
       }
       for (int i = 0; i < arr.length; i++) {
           System.out.printf("arr[%d]=%d\n", i, arr[i]);
       }
   }

   //显示队列的头
   public int rearContent() {
       if (isEmpty()) {
           throw new RuntimeException("队列为空");
       }
       return arr[front + 1];
   }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

问题分析

​ 目前数字使用一次就不可以重复使用，没有达到复用的效果

​ 将这个数组使用算法，改进成一个环形的数组 %

处理思路

​ Front变量的含义：front就指向队列的第一个元素，也就是说arr[front]就是队列头 0

​ Rear 变量的含义：rear就指向队列的最后一个元素的后一个位置，空出来的位置最为空间约定 0

​ 判断队列是否满：(rear + 1) % maxSize == front

​ 判断队列是否为空：rear == front

​ 查看有效队列：

class CircleQueue {
   private int maxSize;//最大容量
   private int front;//队列头
   private int rear;//队列尾
   private int[] arr;//数组存放数据

   public CircleQueue(int maxSize) {
       this.maxSize = maxSize;
       arr = new int[maxSize];
       front = 0;//指向队列头部，分析出front是指向队列头的前一个位置
       rear = 0;//指向队列尾，指向队列尾的具体的数据（即就是队列的最后一个数据)
   }

   //判断队列是否满
   public boolean isFull() {
       return (rear + 1) % maxSize == front;
   }

   //判断队列是否为空
   public boolean isEmpty() {
       return rear == front;
   }

   //添加数据到队列
   public void addQueue(int i) {
       //判断队列是否满
       if (isFull()) {
           System.out.println("队列已满");
           return;
       }
       arr[rear] = i;
       rear = (rear + 1) % maxSize;
   }

   //获取队列数据
   public int findQueue() {
       if (isEmpty()) {
           throw new RuntimeException("队列数据为空");
       }
       int s = arr[front];
       front = (front + 1) % maxSize;
       return s;
   }

   //显示队列
   public void selectArr() {
       if (isEmpty()) {
           System.out.println("队列为空");
           return;

       }
       //思路 ：从front开始遍历，遍历多少个元素
       for (int i = front; i < front + size(); i++) {
           System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
       }
   }

   //显示队列的头
   public int rearContent() {
       if (isEmpty()) {
           throw new RuntimeException("队列为空");
       }
       return arr[front];
   }

   //求出当前数组的有效个数
   public int size() {
       return (rear + maxSize - front) % maxSize;
   }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

链表（LinkedList）

链表是以节点的方式来存储：链式存储

每个节点包含data域，next域：指向下一个节点

​ 实际结构

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yrz1skf8-1674801911590)(C:\Users\16510\AppData\Roaming\Typora\typora-user-images\image-20230127143444981.png)]

链表的各个节点比一定是连续存放

链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

​ 逻辑结构

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1EmfDqBD-1674801911590)(C:\Users\16510\AppData\Roaming\Typora\typora-user-images\image-20230127143505089.png)]

单链表实现

​ 先创建一个head头节点，作用就是表示单链表的头

​ 后面我们每添加一个节点，就直接加入到链表的最后 遍历：

​ 通过一个辅助遍历，帮助遍历整个链表

class SingleLinkedList {
    //初始化头节点
    private HearNode heard = new HearNode(0, "", "");
    //添加方法：添加节点到单项列表
    //当不考虑编号的顺序时，找到当前链表的最后节点，将最后这个节点的next域，指向 新 的节点即可
    public void add(HearNode hearNode) {
        //因为head节点不能动，因此我们需要一个赋值变量 temp
        HearNode temp = heard;
        //遍历链表，找到最后
        while (true) {
            //找到链表的最后
            if (temp.next == null) {
                break;
            }
            //如果没有找到最后，就将temp后移
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        temp.next = hearNode;
    }

    //第二中方式在添加，且排序
    //如果有这个排名，则添加失败，并给出提示
    public void addByOrder(HearNode hearNode) {
        //因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置
        //因为这是一个单链表，因此我们找的temp是位于添加位置的前一个节点
        HearNode temp = heard;
        boolean flag = false;//添加的编号是否存在，默认为false
        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no > hearNode.no) {//找到位置
                break;
            } else if (temp.next.no == hearNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;//后移
        }
        //判断flag的值
        if (flag) {
            System.out.printf("编号%d重复\n", hearNode.no);
        } else {
            hearNode.next = temp.next;
            temp.next = hearNode;
        }
    }

    public void list() {
        //判断链表是否为空
        if (heard.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，因此我们需要一个辅助变量来遍历
        HearNode temp = heard.next;
        while (true) {
            if (temp == null) {
                break;
            }
            //输出节点的信息
            System.out.println(temp.toString());
            //将next后移
            temp = temp.next;
        }
    }

    /*
    判断链表是否为空
    判断no，
        如果找到了，对name, nickName进行修改
        如果没有找到，抛出异常
     */
    public void edit(int no,String name, String nickName) {
        if (heard.next == null) {
            System.out.println("链表为空");
            return;
        }
        HearNode temp = heard.next;
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = name;
            temp.nickName = nickName;
            System.out.println("修改成功");
        } else {
            System.out.println("没有找到该节点 ");
        }
    }

//    public void delete(HearNode hearNode) {
    public void delete(int no) {
        if (heard.next == null) {
            System.out.println("链表为空");
            return;
        }
        HearNode temp = heard;
        boolean flag = false;
        /*HearNode content = null;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == hearNode.no) {
                flag = true;
                break;
            }
            content = temp;
            temp = temp.next;
        }*/

        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
//            content.next = hearNode.next;
            temp.next = temp.next.next;
        } else {
            System.out.println("没有这个节点");
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

单项链表

双项链表

单项环形链表

​ 约瑟夫问题

​ 构建一个单项环形链表

​ 先创建一个节点，让first指向该节点，并形成环形

后面当我们每创建一个新的节点，就把该节点添加到该链表，并把下一个节点指向第一个节点

​ 遍历环形链表

​ 先让一个辅助指针（变量）curBody, 指向frist节点

​ 然后通过while循环遍历该环形链表即可curBoy.next == first结束

class CircleSingleLinkedList {
  private Body first = null;

  public void add(int num) {
      Body curBody = null;
      if (num < 1) {
          num = 10;
      }
      Body curBoy = null;//辅助指针
      for (int i = 1; i <= num; i++) {
          Body body = new Body(i);
          if (i == 1) {
              first = body;
              first.next = first;
              curBody = first;
          } else {
              curBody.next = body;
              body.next = first;
              curBody = body;
          }
      }
  }

  public void list() {
      //判断链表是否为空
      if (first.next == null) {
          System.out.println("链表为空");
          return;
      }
      Body body = first;
      while (true) {
          System.out.println(body.toString());
          if (body.next == first) {
              break;
          }
          body = body.next;
      }
  }

  //根据用户的输入计算出出圈的速度

  /**
   *
   * @param startNo       从第几个小孩开始数数
   * @param countNum      表示数几下
   * @param nums          表示最初有多少小孩在圈中
   */
  public void countBody(int startNo, int countNum, int nums) {
      //先对数据进行校验
      if (first == null || startNo < 1 || startNo >= nums) {
          System.out.println("参数输入有误");
          return;
      }
      Body helper = first;
      //创建一个辅助指针（变量）helper，事先应该指向环形列表的最后一个节点
      while (true) {
          if (helper.next == first) {
              break;
          }
          helper = helper.next;
      }
      //小孩报数前，先将first 和 helper 向后移动一位
      for (int i = 0; i < startNo - 1; i++) {
          helper = helper.next;
          first = first.next;
      }
      //这里是一个循环操作直到圈中只有一个节点
      while (true) {
          if (helper == first) {
              //说明圈中只有一个节点
              break;
          }
          //让first helper 同时移动 countNum 次出圈
          for (int i = 0; i < countNum - 1; i++) {
              first = first.next;
              helper = helper.next;
          }
          //这时first指向的节点就是要出圈的小孩的节点
          System.out.printf("小孩%d出圈\n", first.no);
          //这是将指向的小孩出圈
          first = first.next;
          helper.next = first;
      }
      System.out.printf("最后的小孩为%d\n", first.no);
  }
}

class Body {
  public int no;
  public Body next;

  public Body(int no) {
      this.no = no;
  }

  @Override
  public String toString() {
      return "Body{" +
              "no=" + no +
              '}';
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

双向环形链表

栈（stack）

栈是一个先进后出（FILO-First In Last Out）的有序列表

栈（stack）是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶（Top），另一端为固定的一段，称为栈底（Bottom）

根据栈的定义可知，最先放入栈中元素在栈底，最后放入元素的在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

出栈（pop）[弹栈]和入栈（push）[压栈]

栈的应用场景

子程序的调用：在跳往子程序前，会将下一个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，回到原来的程序中

处理递归调用：和子程序的调用类似，只是除了存储下一个指令的地址外，也将参数，区域变量等数据存入堆栈中

表达式的转换[中缀表达式转后缀表达式]与求值

二叉树的遍历

图形的深度优先（depth-first）搜索法

使用栈完成表达式的计算器

​ 通过一个index值（索引），来遍历我们的表达式

​ 如果我们发现是一个数组，就直接如数栈

​ 如果我们扫描到发现的是一个符号，就分如下情况

​ 如果发现当前的符号栈为空，就直接入栈

​ 如果符号栈有操作符，就进行比较，如果当前的操作符优先级小于或者等于栈中的操作符，就需要从数栈中取出两个数，再从符号栈中取出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈，如果当前的操作符的优先级大于栈中的操作符，就直接入符号栈

​ 当表达式扫描完成，就顺序从数栈和符号栈中取出相应的数和符号，并运算

​ 最后在数栈只有一个数字，就是表达式的结果

前缀表达式（波兰表达式）

前缀表达式又称波兰表达式，前缀表达式的运算符位于操作数之前

前缀表达式的计算机求值

​ 从左到右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对他们做相应的计算（栈顶元素和次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算的出的值即为表达式的结果

​ 例如：（3+4）* 5 – 6 对应的前缀表达式就是- * + 3 4 5 6, 针对前缀表达式求值步骤如下：

\1. 从右到左扫描，将6543压入堆栈

\2. 遇到 + 运算符，因此弹出3 4 （3栈顶 4 次顶），计算出 3 + 4的值为7，再将7入栈

\3. 接下来是*运算，因此弹出7 5 计算 7 * 5

\4. 最后是 – 计算 35 – 6

中缀表达式

​ 中缀表达式就是常见的运算表达式，如(3+4）* 5 – 6

​ 中缀表达式的求值是我们最熟悉，但是对计算机来说却不好操作 ，因此，在计算结果时，往往会将中缀表达式转成其他的表达式来操作

后缀表达式（逆波兰表达式）

后缀表达式又称为逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后

(3+4）* 5 – 6 对应的后缀表达式就是 3 4 + 5 * 6 –

后缀表达式的计算机求值

​

从左到右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对他们做相应的计算（栈顶 次顶）并将结果入栈，重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果 例如 ： （3+4）* 5 – 6对应的后缀表达式为 3 4 + 5 * 6 –

中缀表达式转后缀表达式的思路分析

中缀表达式 1 + （（2 + 3） * 4 ） - 5 =》 后缀表达式

\1. 初始化两个栈：运算符栈s1和存储中间结果的栈 s2

\2. 从左至右扫描中缀表达式

\3. 遇到操作数时，将其压入s2

\4. 遇到运算符时，比较其与s1栈顶运算符的优先级

a) 如果s1为空，或栈顶运算符为左括号“（”，这直接将此运算符入栈；

b) 否则，若优先级比栈顶运算符的高，也将运算符压入s1

c) 否则，将s1栈顶的运算符弹出并压入到s2，再次转到（4 – 1）与s1中的新的栈顶运算符相比较

\5. 遇到括号时

a) 如果是左括号，直接压入s1

b) 如果是右括号，这一次弹出s1栈顶元素的运算符，并压入s2，直到遇到左括号位置，此时将这一对括号丢弃

\6. 重复2-5，直到表达式最右

\7. 将s1中剩余的运算符依次弹出并压入s2

\8. 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

public class PolandNotation {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        /*
        定义一个中缀表达式
        定义一个中缀转后缀表达式的方法
         */

        String infixExpression = "1+((2+3)*4)-5";
//        String s = infixToSuffix(infixExpression);
//        System.out.println(s);


        //定义一个逆波兰表达式
        List<String> list1 = toInfixExpressionList(infixExpression);

        List<String> stringList = parseSuffixExpressionList(list1);
 
        String s = reverseAndSpace2(stringList);

        System.out.println(s);

        //将字符串放入到arrayList中

        /*将arrayList传递给一个方法
            方法中配合栈完成计算
                遍历arrayList*/

        List<String> list = getListString(s);

        int calculation = calculation(list);

        System.out.println(calculation);

        long end = System.currentTimeMillis();
        System.out.println("共耗时" + (end - start) + "毫秒");
    }

    private static List<String> parseSuffixExpressionList(List<String> list) {
        Stack<String> s1 = new Stack<>();
        List<String> s2 = new ArrayList<>();
        //遍历list
        for (String ch : list) {
            if (ch.matches("\\d+")) {
                s2.add(ch);
            } else if (ch.equals("(")) {
                s1.add(ch);
            } else if (ch.equals(")")) {
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();
            } else {
                //当ch优先级小于等于栈顶运算符的优先级
                while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(ch)) {
                    s2.add(s1.pop());
                }
                s1.push(ch);
            }
        }
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        return s2;
    }

    private static String infixToSuffix(String infixExpression) {
        /*
        将字符串存入list
        遍历
            if是数字直接入栈
                判断栈是否为空
                    如果是空的直接添加
                    如果不是空的判断传进来的是不是数字
                        如果是数字，直接和top结合后添加
            else是符号判断优先级
                如果为空直接入栈
                如果不为空
                    如果传入的符号的优先级大于栈顶的优先级那么直接将传入的符号入s2
                    如果传入的符号的优先级小于栈顶的优先级那么将栈顶的符号压入s2，将传入的符号压入s1
                    如果传入的优先级相等，那么将s1栈顶的符号压入s2
                    如果是括号判断是左括号还是右括号
                        如果是左括号，直接入栈
                        如果是右括号，取栈顶元素压入s2，直到找到左括号，取出后完成
         */
        Stack<String> s1 = new Stack<>();
        Stack<String> s2 = new Stack<>();
        int index = 0;
        boolean flag = true;
        List<String> list = new ArrayList<>();
        while (index > infixExpression.length()) {
            list.add(infixExpression.substring(index, index + 1).toString());
            index++;
        }
        for (int i = 0; i < list.size(); i++) {
            String ch = list.get(i);
            if (isNum(ch)) {
                s2.push(ch);
            } else {
                if (s1.isEmpty()) {
                    s1.push(ch);
                } else if ("(".equals(ch)) {
                    s1.push(ch);
                } else if (")".equals(ch)) {
                    while (true) {
                        String pop = s1.pop();
                        if ("(".equals(pop)) {
                            break;
                        }
                        if ("(".equals(pop)) {

                        } else {
                            s2.push(pop);
                        }
                        s1.pop();
                    }
                } else {
                    if (s1.isEmpty()) {
                        s1.push(ch);
                    } else {
                        int come = priority(ch);
                        int first = priority(s1.firstElement());
                        if (come > first) {
                            s1.push(ch);
                        } else if (come < first) {
                            s2.push(s1.pop());
                            s1.push(ch);
                        } else {
                            s1.push(ch);
                        }
                    }
                }
            }
        }
        for (int i = 0; i < s1.size(); i++) {
            s2.push(s1.pop());
        }
        String s = reverseAndSpace(s2);
        return s;
    }

    //将中缀表达式转为List
    public static List<String> toInfixExpressionList(String infixExpression) {
        ArrayList<String> arrayList = new ArrayList<>();
        int index = 0;
        String str;//多位拼接
        char c;//遍历到一个字符就放到c
        do {
            //如果是一个非数字，就加入到arrayList
            if ((c = infixExpression.charAt(index)) < 48 || (c = infixExpression.charAt(index)) > 57) {
                arrayList.add(String.valueOf(c));
                index++;
            } else {//考虑多位数的问题
                str = "";
                while (index < infixExpression.length() && (c = infixExpression.charAt(index)) >= 48 && (c = infixExpression.charAt(index)) >= 48) {
                    str += c;
                    index++;
                }
                arrayList.add(str);
            }
        } while (index < infixExpression.length());
        return arrayList;
    }

    //字符串反转和增加空格
    public static String reverseAndSpace(Stack<String> stack) {
        String[] strings = new String[stack.size()];
        int index = stack.size();
        for (int i = 0; i < index; i++) {
            strings[i] = stack.pop();
        }
        String s = "";
        for (int i = strings.length - 1; i >= 0; i--) {
            s += strings[i] + " ";
        }
        return s;
    }

    public static String reverseAndSpace2(List<String> list) {
        /*
        需要返回一个字符串
        并分出空格
         */
        String str = "";
        for (String strings : list) {
            str += strings + " ";
        }
        return str;
    }

    //判断数字的优先级
    public static int priority(String ch) {
        if ("*".equals(ch) || "/".equals(ch)) {
            return 2;
        } else if ("+".equals(ch) || "-".equals(ch)) {
            return 1;
        } else {
            throw new RuntimeException("gun");
        }
    }

    //判断是否是数字
    public static boolean isNum(String num) {
        return num.matches("\\d+");
    }

    //将后缀表达式，依次将数据和运算发放入到一个arrayList中
    public static List<String> getListString(String suffixExpression) {
        //将suffixExpression进行分割
        String[] strings = suffixExpression.split(" ");
        ArrayList<String> arrayList = new ArrayList<>();
        for (String string : strings) {
            arrayList.add(string);
        }
        return arrayList;
    }

    //完成运算
    public static int calculation(List<String> list) {
        Stack<String> stack = new Stack<>();
        //遍历list
        for (String item : list) {
            //使用正则表达式
            if (item.matches("\\d+")) {
                stack.push(item);
            } else {
                int popN = Integer.parseInt(stack.pop());
                int popF = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = popF + popN;
                } else if (item.equals("-")) {
                    res = popF - popN;
                } else if (item.equals("*")) {
                    res = popF * popN;
                } else if (item.equals("/")) {
                    res = popF / popN;
                } else {
                    throw new RuntimeException("gun你妈的");
                }
                stack.push(String.valueOf(res));
            }
        }
        return Integer.parseInt(stack.pop());
    }
}

class Operation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int NUL = 2;
    private static int DIV = 2;

    public static int getValue(String operation) {
        int result = 0;
        switch (operation) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = NUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                break;
        }
        return result;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276

递归

递归的概念

递归就是方法自己调用自己，每次调用时传入不同的变量

递归的调用规则

当程序执行到一个方法时，就会开辟一个独立的空间（栈）

每个空间的数据（局部变量），是独立的

递归需要遵守的重要规则

执行一个方法时，就创建一个新的受保护的独立空间（栈空间）

方法的局部变量是独立的，不会相互影响，比如n变量

如果方法中使用的是引用类型变量，就会共享该引用类型的数据

递归必须向退出递归条件逼近，否则就是无限递归，无归。

当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法指向完毕或者返回时，该方法也就执行完毕

递归问题

public static boolean setWay(int[][] map, int i, int j) {
    if (map[6][5] == 2) {
        return true;
    } else {
        if (map[i][j] == 0) {//如果当前这个点还没有走过
            //按照策略走
            //下右上左
            //改变策略，下左右上
            map[i][j] = 2;//假定该点可以走过
            if (setWay(map, i + 1, j)) {//向下走
                return true;
            } else if (setWay(map, i, j - 1)) {//左
                return true;
            } else if (setWay(map, i, j + 1)) {//右
                return true;
            } else if (setWay(map, i - 1, j)) {//上
                return true;
            } else {
                map[i][j] = 3;
                return false;
            }
        } else {//如果map i j 不等于0  可能是 1, 2, 3
            return false;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

八皇后问题

八皇后问题算法思路分析

​ 第一个皇后先放在第一行第一列

​ 第二个皇后放在第二行第一列，然后判断是否ok，如果不ok，继续放在第二列，第三列，依次把所有列都放完，找到一个合适的

​ 继续第三个皇后，还是第一列，第二列…直到第8列皇后也能放在一个不冲突的位置，算是找到了一个正解

​ 当得到一个正解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，得到全部

​ 然后回头继续第一个皇后放第二列，后面继续执行123的步骤

​ 【说明】理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题

public class Queue8 {
    //定义一个max表示共有多少个皇后
    int max = 8;
    //定义数组array，用于保存皇后放置位置的结果
    int[] array = new int[max];
    static int count = 0;
    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.println(count);
    }

    //编写一个方法放置第n个皇后
    //特别注意：check 是每一次递归时，进入到check中都有for循环，因此会有回溯
    public void check(int n) {
        if (n == max) {//说明是第9个皇后，其实前8个就已经放好了
            print();
            return;
        }
        //依次放入皇后，并判断是否冲突
        for (int i = 0; i < max; i++) {
            //先把当前的皇后 n，放到改行的第1列
            array[n] = i;
            //判断当放置第n个皇后到i列时，是否冲突
            if (judge(n)) {//不冲突
                //接着放n+1皇后
                check(n + 1);
            }
            //如果冲突就继续执行array[n] = i; 即将第n个皇后，放置在本行得后移的一个位置
        }
    }

    //查看当我们放置第n个皇后时时，就去检测该皇后时候和前面已经摆放的皇后是否冲突
    private boolean judge(int n) {//n 表示放置的第n个皇后
        for (int i = 0; i < n; i++) {
            /*
            说明：
                array[i] == array[n]  表示判断第n个皇后是否和前面的n-1个皇后在同一列
                Math.abs(n - i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i个皇后是否在同一斜线
             */
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                return false;
            }
        }
        return true;
    }

    //写一个方法，将皇后摆放的位置打印出来
    private void print() {
        count++;
        for (int s : array) {
            System.out.print(s + "  ");
        }
        System.out.println();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

排序算法

排序也称排序算法（Sort Algorithm），排序是将一组数据，依指定的顺序进行排序的过程

排序的分类

内部排序：指将需要处理的所有数据都加载到内部存储器中进行排序

外部排序法：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Hw8J5nKi-1674801911592)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image013.jpg)]

算法的时间复杂度

度量一个程序执行时间的两种方法

事后统计的方法

​ 这种方法可行，但是有两个问题：

​ 一是要想对设计的算法的运行性能进行评价，需要实际运行该程序

​ 二是所得时间的统计量依赖于计算机的硬件，软件等环境因素，这种发过誓，要在同一台计算机的相同状态下运行，才能比较那个算法速度更快

事前估算的方法

​ 通过分析某个算法的时间复杂度来判断那个算法更优

时间频度

一个算法花费的时间与算法中语句的执行次数成正比例，那个算法中语句执行次数多，它花费的时间就多。一个算法的语句执行次数称为语句频度或时间频度。记为T(n)

忽略常数项

​ 2n + 20 和 2n随着n变大，执行曲线无线接近，20可以忽略

忽略低次项

​ 2n ^ 2 和 2n^2 + 3n + 10 随着n变大，执行曲线无限接近，可以忽略 3n + 10

忽略系数

​ 随着n值变大，5n^2 + 7n和3n^2 + 2n，执行曲线重合，说明这种情况下，5和3可以忽略

而n^3 + 5n 和 6n^3+4n，指向曲线分离，说明多少次方是关键

​

​

时间复杂度

​ 一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近与无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n) = O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度

​ T(n)不同，但时间复杂度可能相同。如：T(n) = n²+7n+6 => T(n) = 3n²+2n+2它们的T(n)不同，但是时间复杂度相同，都为O(n²)

​ 计算时间复杂度的方法

​

1. 用常数1代替运行时间中所有加法常数T(n) = n²+7n+6 => T(n) = n²+7n+1 2. 修改后的运行次数函数中，只保留最高阶项 T(n) = n²+7n+1 => T(n) = n² 3. 去除最高阶项的系数T(n) = n² => O(n²)

常见见的时间复杂度

常数阶 O(1)

对数阶 O(log2n)

线性阶 O(n)

线性对数阶 O(nlog2n)

平方阶 O(n2)

立方阶 O(n3)

K次方阶 O(nK)

指数阶 O(2n)

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qdrswlhr-1674801911592)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image015.jpg)]

常数阶(O1)

无论代码执行了多少行，只要没有循环等复杂结构，哪这个代码的时间复杂度就都是O(1)

int i = 1; int j = 1;  ++i;  j++; int m = i + j;
1

上述代码在执行的时候，他消耗的时间并不随着某个变量的增长而增长，那么无论这个类的代码有多长，即使有n条，也都可以用O(1)来表示他的时间复杂度

对数阶O(log2n)

int i = 1; while (i < n) {   i = i * 2;  }
1

​ 在while循环中，每次都将I * 2 ，乘完以后，i距离n就越来越近了，假设循环x次之后，i就大于n了，此时这个循环就退出了，也就是说2的x次方等于n，那么x = log2n也就是说当循环log2n次以后，这个代码就结束了，因此这个代码的时间复杂度为：O(log2n))。O(log2n)这个2时间上是根据代码变化的，I = I * 3则是 O(log3n)

线性阶O(n)

for (int i = 0; i < n; ++i) {   j = i;   j++;  }
1

​ For循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化二变化的，因此这类代码都可以用O(n)来表示它的时间复杂度

线性对数阶O(nlogN)

for (int i = 0; i < n; i++) {   j = 1;   while (i < n) {     i = i * 2;   } }
1

​ 线性对数阶O(nlogN)，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是n * O(logN)，也就是O(nlogN)

平方阶O(n2)

​

for (int i = 0; i < n; i++) {   for (int k = 0; k < n; k++) {     j = i;     j++;   } }
1

平均时间复杂度和最坏时间复杂度

平均时间复杂度是指所有可能的输入实力均以等概率出现的情况下，该算法的运行时间

最坏情况下的时间复杂度称为最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实力上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长

平均时间复杂度和最坏时间复杂度是否一致，和算法有关

算法的空间复杂度详解

类似与时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模的运算

空间复杂度（SpaceComplexoty）是对一个算法在运行过程中临时占用存储空间大小的度量。有的算法需要占用临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况

在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品（redis, memcache）和算法（基数排序）本质就是用空间换时间

冒泡排序

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序这交换，使值较大的元素逐渐从前向后移动

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行交换，就说明序列有序，因此要在排序过程中设置一个flag判断元素是否进行过交换，从而减少不必要的比较

public static void bubble(int[] count) {
    int temp = 0;
    boolean flag = false;//表示是否进行过交换
    for (int i = 0; i < count.length - 1; i++) {
        for (int j = 0; j < count.length - 1 - i; j++) {
            if (count[j] > count[j + 1]) {
                flag = true;
                temp = count[j];
                count[j] = count[j + 1];
                count[j + 1] = temp;
            }
        }
        if (!flag) {//说明一次也没有交换过
            break;
        } else {
            flag = false;//重置flag，进行下次的判断
        }
    }
}
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

选择排序

选择排序（select sorting）也是一种简单的排序方法。他的基本思想是：第一次从arr[0]_{arr[n-1]中选取最小值，与arr[0]进行交换，第二次从arr[1]}arr[n - 1]中选取最小值，与arr[1]交换……第i次从arr[n – 2]~arr[n – 1]中选取最小值，与arr[n – 2]交换，总共通过n – 1次，得到一个安排序码从小到大排序的有序序列

public static void main(String[] args) {

//        int[] arr = new int[]{101, 34, 1, 119};
       int[] arr = new int[80000];
       for (int i = 0; i < 80000; i++) {
           arr[i] = (int)(Math.random() * 80000000);
       }
       Time.begin();
       selectSort(arr);
       Time.end();
   }


   public static void selectSort(int[] arr) {
       boolean flag = false;
       int minIndex = 0;
       int min = 0;
       for (int j = 0; j < arr.length - 1 ; j++) {
           //第一轮
           minIndex = j;
           min = arr[j];
           for (int i = j; i < arr.length; i++) {
               if (min < arr[i]) {//说明假定最小值并不是最小值
                   flag = true;
                   min = arr[i];
                   minIndex = i;
               }
           }
           //交换
           if (!flag) {
               break;
           } else {
               arr[minIndex] = arr[j];
               arr[j] = min;
           }
       }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

插入排序

插入排序输入内部排序法，是对于欲排序得元素以插入得方式寻找该元素的适当的位置，以达到排序的目的

插入排序（Insertion Sorting）的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把他的排序码一次与有序表元素的排序码进行比较，将他插入到有序表中的适当位置，使之称为新的有序表

public static void insertSort(int[] arr) {
  int insert = 0;
  int insertIndex = 0;
  for (int i = 1; i < arr.length; i++) {
      //第一轮得到  [34, 101, 1, 6]
      //定义待插入的数字
      insert = arr[i];
      insertIndex = i - 1;//即arr[1]前面的那个数的下标

      //给insert 找到插入的位置
      //insertIndex > 0 保证不越界
      //insert < arr[insertIndex]说明待插入的数还没有找到要插入的位置
      //需要将insertIndex向后移动
      while (insertIndex >= 0 && insert < arr[insertIndex]) {
          arr[insertIndex + 1] = arr[insertIndex];//后移
          insertIndex--;
      }
      //当退出while循环时，说明插入的位置找到，insertIndex + 1
      //判断是否需要赋值
      if (insertIndex + 1 != i) {
          arr[insertIndex + 1] = insert;
      }
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

简单插入排序存在的问题

​ [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-E1ca38sY-1674801911593)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image018.jpg)]

希尔排序

希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是 一种插入排序，他是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至一时，整个文件被分成一组，算法便终止

public static void shellSortMobile(int[] arr) {
   //增量gap，并逐步缩小增量
   int insertIndex = 0;
   int insert = 0;
   for (int gap = arr.length / 2; gap > 0; gap /= 2) {
       for (int i = gap; i < arr.length; i++) {
           insertIndex = i;
           insert = arr[i];
           if (arr[insertIndex] < arr[insertIndex - gap]) {
               while (insertIndex - gap >= 0 && insert < arr[insertIndex - gap]) {
                   arr[insertIndex] = arr[insertIndex - gap];
                   insertIndex -= gap;
               }
               //当退出while循环后就找到了插入的位置
               arr[insertIndex] = insert;
           }
       }
   }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

快速排序

快速排序（QuickSort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据小，然后再按此方法对两部分分数据进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

public static void quickSort(int[] arr, int left, int right) {
   int l = left;
   int r = right;
   int pivot = arr[(left + right) / 2];
   int temp = 0;
   //while循环的目的是让比pivot值小的放到左边
   // 比 pivot值大的放到右边
   while (l < r) {
       //在pivot的左边一直找，找到大于或等于pivot的值退出
       while (arr[l] < pivot) {
           l += 1;
       }
       //在pivot的右边找到一个小于等于 pivot的值退出
       while (arr[r] > pivot) {
           r -= 1;
       }
       //如果 left >= right说明pivot的左右俩边的值，已经按照左边全部是小于等于pivot值，右边是大于等于pivot的值
       if (l >= r) {
           break;
       }
       temp = arr[l];
       arr[l] = arr[r];
       arr[r] = temp;

       //如果交换完后发现arr[left] == pivot right--;  向前移动
       if (arr[l] == pivot) {
           r -= 1;
       }
       //如果交换完后发现arr[right] == pivot left++;  向前移动
       if (arr[r] == pivot) {
           l += 1;
       }
   }

   //如果  left == right 必须 left++, right--， 否则会出现栈溢出异常
   if (l == r) {
       l += 1;
       r -= 1;
   }

   if (left < r) {
       quickSort(arr, left, r);
   }

   if (right > l) {
       quickSort(arr, l, right);
   }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

归并排序（MERGE-SORT）是利用归并的思想实现的排序的方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分（divide）成一些小的问题然后递归求解，而治（conquer）的阶段则将分的阶段得到的各个答案“补修“在一起，即分而自治

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xv9vX7ko-1674801911594)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image019.png)]

可以看到这种结构很像一颗完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的去方式实现）。分阶段可以理解为就是递归拆分子序列的过程

//分 + 合方法
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
  if (left < right) {
      int mind = (left + right) / 2;//中间的索引
      //向左递归进行分解
      mergeSort(arr, left, mind, temp);
      //向右递归分解
      mergeSort(arr, mind + 1, right, temp);
      //到合并
      merge(arr, left, mind, right, temp);
  }
}

/**
*
* @param arr       排序的原始数组
* @param left      左边有序序列的初始索引
* @param mind      中间索引
* @param right     右边索引
* @param temp      做中转的数组
*/
public static void merge(int[] arr, int left, int mind, int right, int[] temp) {
  int i = left;//初始化i，左边有序序列的初始索引
  int j = mind + 1;//初始化j，右边有序序列的初始索引
  int t = 0;//指向temp数组的当前索引

  //（一）
  //先把左右两边（有序）的数据按照规则填充到temp数组
  //直到左右两边的有序，有一边处理完毕为止
  while (i <= mind && j <= right) {//继续
      //如果我们发现左边的有序序列元素小于或等于右边有序序列元素那么，将左边的元素放入temp的t坐标
      if (arr[i] <= arr[j]) {
          temp[t] = arr[i];
          t += 1;
          i += 1;
      } else { //反之
          temp[t] = arr[j];
          t += 1;
          j += 1;
      }
  }
  //（二）
  //把有剩余数据的一边的数据依次全部填充到temp
  while (i <= mind) {//如果这个式子成立，就表明左边的有序序列还有剩余的元素，就全部填充到temp
      temp[t] = arr[i];
      t += 1;
      i += 1;
  }
  while (j <= right) {
      temp[t] = arr[j];
      j += 1;
      t += 1;
  }
  //(三）
  //temp数组重新拷贝到arr数组
  //注意：并不是每一次都拷贝所有的
  t = 0;
  int tempLeft = left;
  //最后一次tempLeft = 0, right = 7
  while (tempLeft <= right) {//第一次合并 tempLeft = 0， right = 1 // 二   tempLeft = 2， right = 3   //三    tempLeft = 0， right = 3
      arr[tempLeft] = temp[t];
      t += 1;
      tempLeft += 1;
  }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

基数排序（桶排序）

基数排序（radix sort）属于“分配式排序”（distribution sort）, 又称“桶子法” （bucket sort）或bin sort，顾名思义，他是通过键值的各个位置的值，将要排序的元素分配至某些“桶”中，达到排序的作用

基数排序法是属于稳定性的排序，基数排序法是效率高的稳定性排序法

基数排序(Radix Sort)是桶排序的扩展

基数排序是1887年赫尔曼、何乐礼发明的。他是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较

基数排序的基本思想

将所有待比较数值统一为同样数位的长度，数位前面较短的数前面补0。然后，从最低位开始，依次进行依次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列

基数排序说明

​ 基数排序是对传统桶排序的扩展，速度很快

​ 基数排序是经典的空间换时间的方式，占内存很大，当对海量数据进行排序时，容易造成 OutOfMemoryError

​ 基数排序是稳定的。【注：假定在待排序的记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原来序列中，r[i]=r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法 是稳定的，否则称为不稳定】

//基数排序
public static void radixSort(int[] arr) {
  //根据前面的推到过程，我们可以得到最终的代码

  //得到数组中最大的位数
  int max = 0;//假设第一个数就是最大数
  for (int i = 1; i < arr.length; i++) {
      if (arr[i] > max) {
          max = arr[i];
      }
  }
  //得到最大的数是几位数
  int maxLength = (String.valueOf(max)).length();
  //第一轮排序（针对每个元素得各位进行排序处理）
  //定义一个二维数组，表示10个桶，每个桶就是一个一维数组
  /*
  说明：
      二维数组包含10个一维数组
      为了防止在放入数得时候，数据溢出，则每个一维数组（桶），大小定位arr.length
      很明确，基数排序是使用空间换时间的经典算法
   */
  int[][] bucket = new int[10][arr.length];

  //为了记录每个桶中实际存放了多少个数据，我们定义一个一维数组来记录各个桶的每次放入的数据个数
  //可以这样理解
  //bucketElement，记录的就是bucket[0] 桶的放入的个数
  int[] bucketElementCounts = new int[10];

  //这里我们使用循环将代码处理
  for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
      //针对每个元素的对应位进行排序处理，第一次是个位，第二次是十位，第三次是百位
      for (int j = 0; j < arr.length; j++) {
          //取出每个元素的个位
          int digitOfElement = arr[j] / n % 10;
          //放入到对应的桶中
          bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
          bucketElementCounts[digitOfElement]++;
      }
      //按照这个桶的顺序（一维数组的下标依次取出数据，放入原来的数组）
      int index = 0;
      //遍历每一个桶，并将桶中的数据放入到原数组
      for (int k = 0; k < bucketElementCounts.length; k++) {
          //如果桶中有数据才放入到原数组
          if (bucketElementCounts[k] != 0) {
              //循环该桶即第k个桶（即第k个一维数组）
              for (int l = 0; l < bucketElementCounts[k]; l++) {
                  //取出元素放入到arr中
                  arr[index++] = bucket[k][l];
              }
          }
          //每次都将清0
          bucketElementCounts[k] = 0;
      }
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

堆排序的基本介绍

堆排序是利用堆这种数据结构设计的的一种排序算法，堆排序是一种选择排序，他的最好，最坏，平均时间复杂度均为O(nlogn)，他也不是稳定排序

堆是具有以下性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大顶推，注意：没有要求节点的左孩子的值和右孩子的值的大小关系

每个节点的值都小于或等于左右孩子节点的值，称为小顶堆

大顶堆

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GK3GYVp9-1674801911594)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image021.jpg)]

特点

​ Arr[i] >= arr[2 * I + 1] && arr[i] >= arr[2 * I + 2]//i对应第几个节点，i从0开始编号

小顶推

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WOxI3zyP-1674801911596)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image023.jpg)]

特点

Arr[i] <= arr[2 * I + 1] && arr[2 * i + 2]//i对应第几节点，i从0开始编号

​

一般升序采用大顶堆，降序采用小顶堆

堆排序基本思想

​ 将等待排序序列构造成一个大顶堆

​ 此时，整个序列的最大值就是堆顶的根节点

​ 将其与末尾元素进行交换，此时末尾就为最大值

​ 然后将剩余n – 1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便可以得到一个有序序列

​ 可以看到在构建大堆顶的过程中，元素个数逐渐减少，最后一个就得到一个有序序列了

常用排序算法的对比

解释：

​ 稳定：如果a原本在b前面，而a = b,排序后a可能会出现在b的后面

​ 不稳定：如果a原本在b前面，而a = b，排序后a可能会出现在b后面

​ 内排序：所有排序操作都在内存中完成

​ 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘内存的数据存储才能进行

​ 时间复杂度：一个算法执行所耗费的时间

​ 空间复杂度：运行完一个程序所需内存的大小

​ N：数据规模

​ K：“桶”的个数

​ In-place：不占用额外内存

​ Out-place：占用额外内存

查找算法

顺序查找

public static int srqSearch(int[] arr, int value) {
    //线性查找是逐一比对，发现有相同的值时就返回下标
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == value) {
            return i;
        }
    }
    return -1;
}

1
2
3
4
5
6
7
8
9
10

二分查找/折半查找

思路分析

​ 首先确定该数组的中间下标 mind = (left + right) / 2

​ 然后让需要查找的数findVal 和 arr[mid]比较

​ FindVal > arr[mid]，说明你要查找的数在mid的右边，因此需要递归向右查找

​ FindVal < arr[mid]，说明你要查找的数在mid的左边，因此需要递归向左查找

​ FindVal == arr[mid]，说明找到，就返回

​ 什么时候我们需要结束递归

​ 找到就结束递归

​ 递归完成整个数组，仍然没有找到findVal，也需要结束递归当left>right就需要退出

public static int binarySearch(int[] arr, int left, int right, int findValue) {
   if (left > right) {
       return -1;
   }
   int mid = (left + right) / 2;
   int midNum = arr[mid];
   if (findValue > midNum) {
       return binarySearch(arr, mid + 1, right, findValue);
   } else if (findValue < midNum) {
       return binarySearch(arr, left, mid, findValue);
   } else {
       return mid;
   }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

插值查找

插值查找的原理

​ 插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找

​ 将折半查找中的求mid索引的公式，low表示左边索引left, high表示右边索引right.key就是之前的findVal

​ Int mid = low + (hight – low) * (key – arr[low]) / (arr[hight] – arr[low]);/插值索引/

插值查找的注意事项

​ 对于数据量较大，关键字分布均匀的查找表来说，采用插值查找，速度较快

​ 关键字分布不均匀的情况下，该方法不一定比折半查找要好

private static int insertValueSearchMy(int[] arr, int left, int right, int value) {
        if (left >= right || value < arr[0] || value > arr[arr.length - 1]) {
            return -1;
        }

//        int mid = left + (value - arr[left]) * (right - left) / (arr[right] - arr[left]);
        int mid = left + (right - left) *  (value - arr[left]) / (arr[right] - arr[left]);
        int midIndex = arr[mid];

        if (value > midIndex) {
            return insertValueSearchMy(arr, mid + 1, right, value);
        } else if (value < midIndex) {
            return insertValueSearchMy(arr, left, mid - 1, value);
        } else {
            return mid;
        }
    }


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

斐波那契查找

斐波那契（黄金分割法）查找基本介绍

​ 黄金分割指的是把一条线段分割成两个部分，使其中一部分与全长之比等于另一部分另一部分与这部分之比。取其前三位数字近似值是0.618。由于按比例设计的造型十分美丽，因此称为黄金分割，也称为中外比，这是一个神奇的数字，会带来意想不到的结果

​ 斐波那契数列（1,1,2,3,5,8,13,21,34,55）发现斐波那契数列的两个相邻数的比，无线接近黄金分割值

斐波那契（黄金分割法原理）

​ 斐波那契查找原理与前两种相似，仅仅改变了中间节点（mid）的位置，mid不再是中间或插值得到的，而是位于 黄金分割点附近，即mid = low+F(k + 1) – 1 (F)代表斐波那契数列

对F(k – 1) – 1的理解

​ 由斐波那契数列F[k] = F[k – 1] + F[k – 2]的性质，可以得到(F[k] – 1) = (F[k – 1] – 1) + (F[k – 2] – 1) + 1。该式说明：只要顺序表的长度位F[k] – 1,则可以将该表分成长度为F[k – 1]和F[k – 2] – 1的两段。从而中间位置为mid = low + F(k – 1) – 1.

​ 类似的 ，每一子段也可以用相同的方式分割

​ 但顺序表长度n不一定刚好等于F[k] – 1,所以需要将原来的顺序长度增加至F[k] – 1.这里的k值只要能使得F[k] – 1恰好大于或等于n即可

​ While (n > fib(k) – 1)

​ K ++;

//因为后面我们mid = low+F(k - 1) - 1,需要使用到斐波那契数列，因此我们先要获取到一个斐波那契数列
//使用非递归的方式得到一个斐波那契数列
public static int[] fibn() {
  int[] f = new int[maxSize];
  f[0] = 1;
  f[1] = 1;
  for (int i = 2; i < maxSize; i++) {
      f[i] = f[i - 1] + f[i - 2];
  }
  return f;
}

//斐波那契查找算法

/**
* 非递归
*
* @param a   数组
* @param key 需要查找的关键码
* @return 返回对应下标
*/
public static int fibSearch(int[] a, int key) {
  int low = 0;
  int high = a.length - 1;
  int k = 0;//表示斐波那契分割数值的下标
  int mid = 0;//存放mid值
  int f[] = fibn();//获取斐波那契数列
  //获取到斐波那契分割数值的下标
  while (high > f[k] - 1) {
      k++;
  }
  //因为f[k]可能大于数字的长度，因此我们需要使用Arrays类，构造一个新的数组，并指向a[]
  //不足的部分会使用0填充
  int[] temp = Arrays.copyOf(a, f[k]);
  //实际上需要使用a数组最后的数填充temp
  for (int i = high + 1; i < temp.length; i++) {
      temp[i] = a[high];
  }

  //使用while来循环处理，找到我们的数key
  while (low <= high) {//只要这个条件满足，就可以找
      mid = low + f[k - 1] - 1;
      if (key < temp[mid]) {//我们应该继续向数组的前面查找（左边）
          high = mid - 1;
          /*
          为什么是k--
          全部元素 = 前面的元素 + 后面的元素
          f[k] = f[k - 1] + f[k - 2]
          因为前面有 f[k - 1]个元素，所以我们可以继续拆分f[k - 1] = f[k - 2] + f[k - 3]
          即在f[k - 1]的前面继续查找 k--;
          即下次循环 mid = f[k - 1 - 1] - 1;
           */
          k--;
      } else if (key > temp[mid]) {//向数组的后面查找（右边）
          low = mid + 1;
          /*
          为什么是k -= 2
              说明
                  全部元素 = 前面元素 + 后面元素
                  f[k] = f[k - 1] + f[k - 2]
                  因为后面我们有f[k - 2] 所以我们可以继续拆分 f[k] = f[k - 3] + f[k - 4]
                  即在f[k - 2]的前面进行查找 k -= 2
                  即下次循环 mid = f[k - 1 - 2] - 1
           */
          k -= 2;
      } else {
          //需要确定，返回的是那个下标
          if (mid <= high) {
              return mid;
          } else {
              return high;
          }
      }
  }
  return -1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

哈希表

哈希表的基本介绍

散列表（Hash table, 也叫哈希表）是根据关键码值（key value）直接进行访问的数据结构。也就是说，它通过把关键字码值到表中一个位置来访问记录，以加快查找速度。这个映射函数也叫做散列函数，存放记录的数组叫做散列表

public class HashTabDemo {
    public static void main(String[] args) {
        //创建一个hash表
        HashTab hashTab = new HashTab(7);

        String key = "";
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("add : 添加");
            System.out.println("list : 查询");
            System.out.println("find : 根据id查找");
            System.out.println("exit : 退出");

            key = scanner.next();
            switch (key) {
                case "add" :
                    System.out.println("输入id");
                    int id = scanner.nextInt();
                    System.out.println("输入姓名");
                    String name = scanner.next();
                    Emp emp = new Emp(id, name);
                    hashTab.add(emp);
                    break;
                case "list":
                    hashTab.list();
                    break;
                case "find":
                    System.out.println("请输入要查找的id");
                    int findId = scanner.nextInt();
                    hashTab.findEmpById(findId);
                    break;
                case "del":
                    System.out.println("请输入要删除的id");
                    int delId = scanner.nextInt();
                    hashTab.del(delId);
                    break;
                case "exit":
                    scanner.close();
                    System.exit(0);
                default:
                    break;
            }
        }
    }
}

//表示一个雇员
class Emp {
    public int id;
    public String name;
    public Emp next;//next默认为空

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }
}

//创建EmpLinkedList,表示一条链表
class EmpLinkedList {
    //头指针，指向第一个Emp,因此我们这个链表是直接指向第一个Emp
    private Emp head;

    //添加雇员
    public void add(Emp emp) {
        if (head == null) {
            head = emp;
            return;
        }
        //如果不是第一个雇员，则使用一个辅助指针，帮助定位到最后
        Emp curEmp = head;
        while (true) {
            if (curEmp.next == null) {
                break;
            }
            curEmp = curEmp.next;//后移
        }
        //退出时直接将emp 加入链表
        curEmp.next = emp;
    }

    //遍历链表的雇员信息
    public void list(int index) {
        if (head == null) {//说明链表为空
            System.out.println("第" + (index + 1) + "链表为空");
            return;
        }
        System.out.print("第" + (index + 1) + "链表的信息为 ：");
        Emp curEmp = head;
        while (true) {
            System.out.printf(" => id = %d  name = %s\t", curEmp.id, curEmp.name);
            if (curEmp.next == null) {
                break;
            }
            curEmp = curEmp.next;//后移遍历
        }
        System.out.println();
    }

    //如果查找到就返回Emp，如果没有找到就返回空
    public Emp findEmpById(int id) {
        //判断链表是否为空
        if (head == null) {
            return null;
        }
        Emp curEmp = head;
        while (true) {
            if (curEmp.id == id) {
                break;
            }
            if (curEmp.next == null) {
                curEmp = null;
                //这里的break是为了不去指向下一个
                break;
            }
            curEmp = curEmp.next;
        }
        return curEmp;
    }

    public void delById(int id) {
        //判断链表是否为空
        if (head == null) {
            return;
        }
        Emp curEmp = head;
        while (true) {
            if (curEmp == null) {
                return;
            }
            if (curEmp.id == id) {
                head = curEmp.next;
            }
            curEmp = curEmp.next;
        }

    }
}

//创建HashTab  管理多条链表
class HashTab {
    private EmpLinkedList[] emplinkedListArray;
    private int size;//表示共有多少条链表

    public HashTab(int size) {
        this.size = size;
        //初始化empLinkedListArray
        emplinkedListArray = new EmpLinkedList[size];
        for (int i = 0; i < size; i++) {
            emplinkedListArray[i] = new EmpLinkedList();
        }
    }

    //根据输入的id查找雇员
    public void findEmpById(int id) {
        //使用散列函数确定到那条链表查找
        int empId = hashFun(id);
        Emp empById = emplinkedListArray[empId].findEmpById(id);
        if (empById != null) {
            System.out.printf("在第%d条链表中找到 雇员 id = %d  name = %s\t\n", (empId + 1), id, empById.name);
        } else {
            System.out.println("在哈希表中没有找到该雇员");
        }
    }

    //添加
    public void add(Emp emp) {
        //根据员工的id得到该员工应当添加到那条链表
        int emplinkedListNo = hashFun(emp.id);
        //将emp 添加到对应的链表中
        emplinkedListArray[emplinkedListNo].add(emp);
    }

    //遍历所有的链表，遍历hash表
    public void list() {
        for (int i = 0; i < size; i++) {
            emplinkedListArray[i].list(i);
        }
    }

    public void del(int id) {
        int hashId = hashFun(id);
        emplinkedListArray[hashId].delById(id);
    }

    //编写一个散列函数，使用简单的取%法
    public int hashFun(int id) {
        return id % size;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191

树

为什么要使用树这种数据结构

数组存储方式的分析

优点：通过下标方式访问元素，速度快。对于有序数组，还可以使用二分查找提高检索速度

缺点：如果要检索具体某个值，或者插入值（按一定顺序）会整体移动，效率较低

链式存储方式的分析

优点：在一定程度上对数组存储方式有优化（比如：插入一个数值节点，只需要将插入节点，连接到链表中即可，删除效率也很好）

缺点：在进行检索时，效率仍然较低，（比如检索某个值，需要从头节点开始遍历）

树存储方式的分析

​ 能提高数据存储，读取的效率，比如利用二叉排序树（Binary Sort Tree）,既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度

二叉树示意图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-v8iOXylL-1674801911597)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image025.jpg)]

二叉树

二叉树的概念

树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树

二叉树的子节点分为左节点和右节点

如果该二叉树的所有叶子节点都在最后一层，并且节点总数=2n – 1，n为层数，则我们称为满二叉树

如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称之为完全二叉树

满二叉树一定是完全二叉树

二叉树遍历

前序

先输出父节点，再遍历左子树和右子树

中序

先遍历左子树，再输出父节点，再遍历右子树

后序

先遍历左子树，再遍历右子树，最后输出父节

看输出父节点的顺序，就确定是前序，中序还是后序

public class BinaryTreeDemo {
  public static void main(String[] args) {
      //创建一课二叉树
      BinaryTree binaryTree = new BinaryTree();
      //创建需要的节点
      HeroNode root = new HeroNode(1, "松江");
      HeroNode node2 = new HeroNode(2, "吴用");
      HeroNode node3 = new HeroNode(3, "吕俊义");
      HeroNode node4 = new HeroNode(4, "林冲");

      //我们先手动创建二叉树
      binaryTree.setRoot(root);
      root.setLeft(node2);
      root.setRight(node3);
      node3.setRight(node4);

      //测试前序遍历
      binaryTree.preOrder();

      System.out.println();

      binaryTree.infixOrder();

      System.out.println();

      binaryTree.postOrder();
  }
}

//定义BinaryTree 二叉树
class BinaryTree {
  private HeroNode root;

  public HeroNode getRoot() {
      return root;
  }

  public void setRoot(HeroNode root) {
      this.root = root;
  }

  public BinaryTree() {
  }

  //前序遍历
  public void preOrder() {
      if (this.root != null) {
          this.root.preOrder();
      } else {
          System.out.println("二叉树为空，无法遍历");
      }
  }

  //中序遍历
  public void infixOrder() {
      if (this.root != null) {
          this.root.infixOrder();
      } else {
          System.out.println("二叉树为空，无法遍历");
      }
  }

  public void postOrder() {
      if (this.root != null) {
          this.root.postOrder();
      } else {
          System.out.println("二叉树为空，无法遍历");
      }
  }
}


//创建HeroNode节点
class HeroNode {
  private int no;
  private String name;
  private HeroNode left;//默认为null
  private HeroNode right;//默认为null

  public HeroNode(int no, String name) {
      this.no = no;
      this.name = name;
  }

  public int getNo() {
      return no;
  }

  public void setNo(int no) {
      this.no = no;
  }

  public String getName() {
      return name;
  }

  public void setName(String name) {
      this.name = name;
  }

  public HeroNode getLeft() {
      return left;
  }

  public void setLeft(HeroNode left) {
      this.left = left;
  }

  public HeroNode getRight() {
      return right;
  }

  public void setRight(HeroNode right) {
      this.right = right;
  }

  @Override
  public String toString() {
      return "HeroNode{" +
              "no=" + no +
              ", name='" + name + '\'' +
              '}';
  }
  //前序遍历的方法
  public void preOrder() {
      System.out.println(toString());//先输出父节点
      //递归向左子树前序遍历
      if (left != null) {
          this.left.preOrder();
      }
      //递归向右子树前序遍历
      if (right != null) {
          this.right.preOrder();
      }
  }
  //中序遍历的方法
  public void infixOrder() {
      //递归向左
      if (left != null) {
          left.infixOrder();
      }
      System.out.println(toString());
      if (right != null) {
          right.infixOrder();
      }
  }
  //后序遍历的方法
  public void postOrder() {
      if (left != null) {
          left.postOrder();
      }
      if (right != null) {
          right.postOrder();
      }
      System.out.println(this);
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

顺序存储二叉树

顺序存储二叉树的特点

​ 顺序存储二叉树通常只考虑完全二叉树

​ 第n个元素的左子节点为 2 * n + 1

​ 第n个元素的右子节点为 2 * n + 2

​ 第n个元素的父节点为 （n – 1）/ 2

​ N表示二叉树中的第几个元素（按0开始编号）

public class ArrBinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
        arrBinaryTree.preOrder();
    }
}

class ArrBinaryTree {
    private int[] arr;//存储数据节点

    public ArrBinaryTree(int[] arr) {
        this.arr = arr;
    }

    public void preOrder() {
        this.preOrder(0);
    }

    //编写一个方法，完成顺序存储二叉树的前序遍历
    public void preOrder(int index) {
        //如果数组为空，或者arr.length = 0
        if (arr.length == 0 && arr == null) {
            System.out.println("数组为空");
        }
        //输出当前这个元素
        System.out.println(arr[index]);
        if ((index * 2 + 1) < arr.length) {
            preOrder(2 * index + 1);
        }

        if ((index * 2 + 2) < arr.length) {
            preOrder(2 * index + 2);
        }
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

线索化二叉树

线索化二叉树基本介绍

N个节点的二叉链表中含有 n + 1【公式2n – (n – 1) = n + 1】个空指针域。利用二叉链表中的空指针域，存放指向节点在某种遍历次序下的前驱和后继节点的指针（这种附加的指针称为“线索”）

这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树（Threaded BinaryTree）。根据线索性质的不同，线索二叉树可分为前序线索二叉树，中序线索二叉树，后序线索二叉树三种

一个节点的前一个节点，称为前驱节点

一个节点的后一个节点，称为后驱节点

//遍历中序线索化二叉树的方法
public void threadedList() {
    //定义一个变量，临时存储当前遍历的一个节点
    HeroNode node = root;
    while (node != null) {
        //循环找到leftType == 1的节点，第一个找到的是8
        //后面随着遍历而变化，因为当leftType = 1时，说明该节点是按照线索化处理后的有效节点
        while (node.getLeftType() == 0) {
            node = node.getLeft();
        }
        System.out.println(node);
        //如果当前节点的右指针指向的是后继节点，就一直输出
        while (node.getRightType() == 1) {
            //获取到当前节点的后继节点
            node = node.getRight();
            System.out.println(node);
        }
        //替换这个遍历节点
        node = node.getRight();
    }
}

//编写对二叉树进行线索化的方法
/**
 *
 * @param heroNode  当前需要线索化的节点
 */
public void threadedNodes(HeroNode heroNode) {
    //如果当前节点为空那么无法线索化
    //如果node == null，那么直接退出，不能进行线索化
    if (heroNode == null) {
        return;
    }

    /*
    中序线索化步骤
        先线索化我们的左子树
        线索化当前的节点
        线索化右子树
     */
    threadedNodes(heroNode.getLeft());

    //先处理当前节点的前驱节点
   /* if (heroNode.getLeft() == null) {
        //当前节点的左指针，指向前驱节点
        heroNode.setLeft(pre);
        //修改当前节点的左指针类型, 指向前驱节点
        //以8节点来理解
        //8节点的.left = null, 8节点的.leftType = 1;
        heroNode.setLeftType(1);
    }*/

    if (heroNode.getLeft() == null) {
        heroNode.setLeft(pre);
        heroNode.setLeftType(1);
    }

    //处理后继节点
   /* if (pre != null && pre.getRight() == null) {
        //让前驱节点指针指向当前节点
        pre.setRight(heroNode);
        //修改前驱节点的右指针类型
        pre.setRightType(1);
    }*/
    if (pre != null && pre.getRight() == null) {
        pre.setRight(heroNode);
        pre.setRightType(1);
    }
    //每处理一个节点后，让当前节点是下一个前驱节点
    pre = heroNode;

    threadedNodes(heroNode.getRight());

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

赫夫曼树

基本介绍

​ 给定n个权值作为n个叶子节点，构造一棵二叉树，若该树的带权路径长度（wpl）达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树（HuffmanTree）

​ 赫夫曼树是带权路径长度最短树，权值较大的节点离跟很近

赫夫曼树几个重要的概念

​ 路径和路径长度：在一颗树中，从一个结点往下可以达到的孩子或孙子节点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定跟节点的层数为1，则从根节点到第L层节点的路径长度为L – 1

​ 节点的权及带权路径长度：若将树中节点赋值给一个有着某种含义的数值，则这个数值称为该节点的权。节点的带权路径长度为：从根节点到该节点之间的路径长度与该节点的权的乘积

​ 树的带权路径长度：树的带权路径长度规定为所有叶子节点的带权路径长度之和，记为WPL（weighted path length）,权值越大的节点离根节点越近的二叉树才是最优二叉树

​ WPL****最小的就是赫夫曼树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PM0yNr3x-1674801911598)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image027.jpg)]

public class HuffmanTree {
    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node node = createHuffmanTree(arr);
        preOrder(node);
    }

    //编写一个前序遍历的方法
    public static void preOrder(Node node) {
        if (node == null) {
            System.out.println("空树~~~");
        } else {
            node.preOrder();
        }
    }

    public static Node createHuffmanTree(int[] arr) {
        /*
        第一步为了操作方便
            遍历arr数值
            将arr的每个元素构建成一个Node
            将node放入到arrayList中
         */
        ArrayList<Node> nodes = new ArrayList<>();
        for(int values : arr) {
            nodes.add(new Node(values));
        }

        //处理的过程是一个循环的过程
        while (nodes.size() > 1) {

            //排序 从小到大
            Collections.sort(nodes);

            //取出根节点权值最小的两颗二叉树
            //取出权值最小的节点（二叉树）
            Node leftNode = nodes.get(0);
            //取出第二小的节点（二叉树）
            Node rightNode = nodes.get(1);

            //构建一颗新的二叉树
            Node parent = new Node(leftNode.value + rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;

            //从ArrayList中删除处理过的二叉树
            nodes.remove(leftNode);
            nodes.remove(rightNode);

            //将parent加入到nodes
            nodes.add(parent);
        }

        //返回赫夫曼树的最终root节点
        return nodes.get(0);
    }
}

//创建节点类
//为了让Node对象支持排序Collections集合排序
class Node implements Comparable<Node> {
    int value;//节点取值
    Node left;//指向左子节点
    Node right;//指向右子节点

    //写一个前序遍历
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return this.value - o.value ;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

赫夫曼编码

基本介绍

​ 赫夫曼编码也翻译为哈夫曼编码（Huffman Coding）,又称霍夫曼编码，是一种编码方式，属于一种程序算法

​ 赫夫曼编码是赫夫曼树在电通信中的经典之一。

​ 赫夫曼编码广泛的用于数据文件压缩。其压缩率通常在20%~90%之间

​ 赫夫曼编码是可边长编码（VLC）的一种。Huffman于1952年提出的一种编码方法。称之为最佳编码

赫夫曼编码的解压缩

根据赫夫曼编码压缩数据的原理，需要创建“I like like like java do you like java”对应的赫夫曼树

思路：

​ Node{data(存放数据)，weight(权值)，left和right}

​ 得到“I like like like java do you like java” 对应的 byte[] 数组

​ 编写一个方法，将准备构建赫夫曼树的Node节点放到List中，形式[Node[data= 97, weight = 5], Node[[]] : 体现：d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9

​ 通过List创建对应的赫夫曼树

压缩率：原长度 – 先长度 / 原长度

public static void main(String[] args) {
        String content = "i like like like java do you like a java";
        byte[] contentBytes = content.getBytes();
        /*List<Node> nodes = getNodes(contentBytes);

        //创建赫夫曼树
        Node root = createHuffmanTree(nodes);

        //前序遍历
        preOrder(root);

        //是否生成了对应的赫夫曼编码
        getCode(root);

        byte[] zip = zip(contentBytes, huffmanCode);
        System.out.println(Arrays.toString(zip));*/
        byte[] bytes = huffZip(contentBytes);
        System.out.println(Arrays.toString(bytes));

        byte[] deCode = deCode(huffmanCode, bytes);
        System.out.println(new String(deCode));

        //测试压缩文件
        String srcFile = "D://1.png";
        String srcOut = "D://2.zip";
        String file = "D://3.png";
//        zipFile(srcFile, srcOut);
        unZipFile(srcOut, file);
        System.out.println("ok");

        System.out.println(Integer.parseInt("23", 5));

    }

    //使用一个方法进行封装

    /**
     *
     * @param bytes 原始的字符串对应的字节数组
     * @return      返回的是经过 赫夫曼编码处理后的字节数组（压缩后的数组）
     */
    public static byte[] huffZip(byte[] bytes) {
        //对一个字符串进行一个记录，变成一个有序的List
        List<Node> nodes = getNodes(bytes);
        //创建赫夫曼树
        Node huffmanTree = createHuffmanTree(nodes);
        //创建对应的赫夫曼编码
        Map<Byte, String> code = getCode(huffmanTree);
        //对相应的赫夫曼编码进行压缩
        byte[] zip = zip(bytes, code);
        return zip;
    }

    //编写一个方法，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码表压缩后的byte[]数组

    /**
     *
     * @param bytes         原始的字符串对应的数组
     * @param huffmanCodes  生成的赫夫曼编码map
     * @return              返回赫夫曼编码处理后的 byte数组
     * 举例：String content = "i like like like java do you like a java" =》 byte[] contentBytes = content.getBytes();
     * 返回：101100110001001... 对应的byte数组 huffmanCodeByte, 即8位对应一个byte, 放入到huffmanCodeBytes
     *      huffmanCodeBytes[0] = 10101000(补码） =》 byte [推导 10101000 => 10101000 - 1 => 10100111(反码）=> 11011000 = -88]
     *      huffmanCodeBytes[1] = -88
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        //先利用 huffmanCodeBytes 将 bytes 转成 赫夫曼编码对应的字符串
        StringBuilder stringBuilder = new StringBuilder();
        //遍历bytes数组
        for (byte b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }
        //将”1010..."转成一个byte数组
//        System.out.println(stringBuilder.toString());

        //统计返回的 byte[] huffmanCodeBytes 长度
        int len;
        if (stringBuilder.length() % 8 == 0) {
            len = stringBuilder.length() / 8;
        } else {
            len = stringBuilder.length() / 8  + 1;
        }
        //创建huffmanBytes
        byte[] by = new byte[len];

        int index = 0;//记录是第几个byte
        for (int i = 0; i < stringBuilder.length(); i += 8) {//因为是每8位对应一个byte，所以步长 +8
            String strByte;
            if (i + 8 > stringBuilder.length()) {//不够8位
                strByte = stringBuilder.substring(i);
            } else {
                strByte = stringBuilder.substring(i, i + 8);
            }

            //将strByte转成一个byte，放入到by
            by[index] = (byte)Integer.parseInt(strByte, 2);
            index++;
        }
        return by;
    }

    //生成赫夫曼树对应的赫夫曼编码
    /*
    思路：
        将赫夫曼编码存放在Map<Byte, String> 形式    =01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010
        在生成赫夫曼编码表，需要去拼接路径，定义一个StringBuilder 存储某个叶子节点的路径
     */
    static StringBuilder stringBuilder = new StringBuilder();
    static Map<Byte, String> huffmanCode = new HashMap<>();

    //为了调用方便使用重载
    private static Map<Byte, String> getCode(Node root) {
        if (root == null) {
            return null;
        }
        //处理root的左子树
        getCode(root.left, "0", stringBuilder);
        getCode(root.right, "1", stringBuilder);
        return huffmanCode;
    }

    /**
     * 功能：将传入的node节点的所有叶子节点的赫夫曼编码得到，并放入到huffmanCode集合
     * @param node  传入节点
     * @param code  路径：左子节点就是0，右子节点就是0
     * @param stringBuilder 是用于拼接路径
     */
    private static void getCode(Node node, String code, StringBuilder stringBuilder) {
        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
        //将code 加入到 stringBuilder2
        stringBuilder2.append(code);
        if (node != null) {//如果 node == null不处理
            //判断当前node 叶子节点还是非叶子节点
            if (node.data == null) {//非叶子节点
                //递归处理
                //向左
                getCode(node.left, "0", stringBuilder2);
                //向右
                getCode(node.right, "1", stringBuilder2);
            } else {//说明是一个叶子节点
                //表示找到了某个叶子节点的最后
                huffmanCode.put(node.data, stringBuilder2.toString());
            }
        }
    }

    /**
     *
     * @param bytes 接受的字节数组
     * @return      返回的就是List 形式
     */
    private static List<Node> getNodes(byte[] bytes) {
        //创建一个ArrayList
        ArrayList<Node> nodes = new ArrayList<>();
        HashMap<Byte, Integer> counts = new HashMap<>();
        for (byte b : bytes) {
            Integer count = counts.get(b);
            if (count == null) {//说明一次也没有存放
                counts.put(b, 1);
            } else {
                counts.put(b, count + 1);
            }
        }
        //把每个键值对转成一个Node对象，并加入到nodes集合
        //遍历map
        for(Map.Entry<Byte, Integer> entry : counts.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }

    //通过list创建对应的赫夫曼树
    private static Node createHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            //排序
            Collections.sort(nodes);
            Node left = nodes.get(0);
            Node right = nodes.get(1);
            //创建一颗新的二叉树
            Node newNode = new Node(null, left.weight + right.weight);
            newNode.left = left;
            newNode.right = right;
            //删除
            nodes.remove(left);
            nodes.remove(right);

            nodes.add(newNode);
        }
        //返回的节点为root
        return nodes.get(0);
    }



    /*
    完成数据的解压
    思路
        将huffmanCodeButes:[-88,-65-56....]
            重新转成赫夫曼编码对应的二进制的字符串“1011.。。。”
        将赫夫曼编码对应的字符串“101101..."=>对照赫夫曼编码重新转成字符串
     */

    /**
     * 将一个byte转成一个二进制的字符串
     * @param b
     * @param flag 标志是否需要补高位如果是true,表示需要补高位，如果是false表示不补，如果是最后一个字节，无需补高位
     * @return
     */
    private static String byteTo(boolean flag, byte b) {
        //使用变量保存b
        int temp = b;//将b转成了int
        //如果是正数我们还需要部高位
        if (flag) {
            temp |= 256;
        }
        String str = Integer.toBinaryString(temp);
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }

    //编写一个方法，完成对压缩数据的解码

    /**
     *
     * @param huffmanCode   赫夫曼编码表
     * @param huffmanBytes  赫夫曼编码得到的字节数组
     * @return  就是原来的字符串对应的数组
     */
    private static byte[] deCode(Map<Byte, String> huffmanCode, byte[] huffmanBytes) {
        //先得到huffmanBytes对应的二进制的字符串
        StringBuilder stringBuilder = new StringBuilder();
        //将byte数组转成二进制的字符串
        for (int i = 0; i < huffmanBytes.length; i++) {
            boolean flag = (i == huffmanBytes.length - 1);
            stringBuilder.append(byteTo(!flag, huffmanBytes[i]));
        }
//        System.out.println(stringBuilder.toString());
        //把字符串按照指定的赫夫曼编码进行编码
        //把赫夫曼编码进行调换，因为要反向查询
        Map<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> entry : huffmanCode.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }
//        System.out.println("map=" + map);
        List<Byte> list = new ArrayList<>();
        for (int i = 0; i < stringBuilder.length(); ) {//i可以理解成就是一个索引
            int count = 1;      //小的计数器
            boolean flag = true;
            Byte b = null;
            while (flag) {
                //取出一个‘1’ ‘0’
                String key = stringBuilder.substring(i, i + count);//i不动让count移动，指定匹配到一个字符
                b = map.get(key);
                if (b == null) {//说明没有匹配到
                    count++;
                } else {
                    //匹配到
                    flag = false;
                }
            }
            list.add(b);
            i += count;//让i直接移动到count的这个位置
        }
        //当for循环结束后，我们list中就存放了所有的字符
        //把list中的数据放入到byte[] 并返回
        byte[] b = new byte[list.size()];
        for (int i = 0; i < b.length; i++) {
            b[i] = list.get(i);
        }
        return b;
    }


    //编写一个方法，将文件进行压缩

    /**
     *
     * @param srcFile   传入的希望压缩的文件的全路径
     * @param destFile  我们将压缩文件放到那个位置
     */
    public static void zipFile(String srcFile, String destFile) {
        //创建输出流
        //创建一个文件的输入流
        FileInputStream is = null;
        FileOutputStream os = null;
        ObjectOutputStream oos = null;
        try {
            is = new FileInputStream(srcFile);
            //创建一个源文件大小一样的byte[]
            byte[] b = new byte[is.available()];
            //读取文件
            is.read(b);
            //直接对bs数组进行压缩
            byte[] huffmanBytes = huffZip(b);
            //创建文件输出流，存放压缩文件
            os = new FileOutputStream(destFile);
            //创建一个和文件输出流关联的ObjectOutputStream
            oos = new ObjectOutputStream(os);
            //把赫夫曼编码的字节数组写入压缩文件
            oos.writeObject(huffmanBytes);
            //这里我们以对象流的方式写入 赫夫曼编码，是为了以后恢复源文件
            //注意一定要把赫夫曼编码写入压缩文件
            oos.writeObject(huffmanCode);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        } finally {
            try {
                is.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
            try {
                os.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
            try {
                oos.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    //编写一个方法完成对压缩文件的解压

    /**\
     *
     * @param zipFile   准备解压的文件
     * @param destFile  将文件解压到那个位置
     */
    public static void unZipFile(String zipFile, String destFile) {
        //定义文件的输入流
        InputStream is = null;
        OutputStream os = null;
        ObjectInputStream oos = null;
        try {
            //创建文件输入流
            is = new FileInputStream(zipFile);
            //创建一个和is关联的对象输入流
            oos = new ObjectInputStream(is);
            //读取by数组huffmanBytes
            byte[] huffmanBytes = (byte[])oos.readObject();
            //读取赫夫曼编码表
            Map<Byte, String> huffmanCode = (Map<Byte, String>)oos.readObject();

            //解码
            byte[] bytes = deCode(huffmanCode, huffmanBytes);
            //将bytes数组写入到目标文件
            os = new FileOutputStream(destFile);
            //写出数据
            os.write(bytes);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                is.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
            try {
                os.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
            try {
                oos.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    //前序遍历
    private static void preOrder(Node root) {
        if (root != null) {
            root.preOrder();
        } else {
            System.out.println("空树！！！");
        }
    }
}



//创建Node带权值，带数据
class Node implements Comparable<Node> {
    Byte data;//存放数据本身
    int weight;//权值，表示字符/数据出现的次数
    Node left;
    Node right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    //前序遍历
    public void preOrder() {
//        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        //从小到大排序
        return this.weight - o.weight;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426

二叉排序树

二叉排序树介绍

二叉排序树：BST：（Binary Sort（Search）Tree），对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点得值小，右子节点的值比当前节点的值大

public static void main(String[] args) {
        int[] arr = {7,3,10,12,5,1,9,2};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int i = 0; i < arr.length; i++) {
            binarySortTree.add(new Node(arr[i]));
        }
        binarySortTree.infixOrder();

        binarySortTree.delNode(1);

        System.out.println();

        binarySortTree.infixOrder();
    }
}

//创建二叉排序树
class BinarySortTree {
    Node root;

    //查找要删除的节点
    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    //查找父节点
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    //编写方法

    /**
     *  1.返回node为根节点的二叉排序树的最小的值
     *  2。删除node为根节点二叉排序树的最小节点
     * @param node  传入的节点，当作一颗二叉排序树的跟阶段
     * @return  以Node为根节点的二叉排序树的最小节点的值
     */
    public int delRightTreeMin(Node node) {
        Node target = node;
        //循环查找左节点,就会找到最小值
        while (target.left != null) {
            target = target.left;
        }
        //这时target就指向了最小节点
        //删除最小节点
        delNode(target.value);
        return target.value;
    }

    //删除节点
    public void delNode(int value) {
        if (root == null) {
            return;
        } else {
            //在删除一个节点的时候需要先找到删除的节点
            Node targetNode = search(value);
            if (targetNode == null) {//如果没有找到要删除的节点，直接返回
                return;
            }
            //如果当我们发现当前这颗二叉树只有一个节点
            if (root.left == null && root.right == null) {
                root = null;
                return;
            }
            //查找targetNode的父节点
            Node parent = searchParent(value);
            //如果要删除的节点是叶子节点
            if (targetNode.left == null && targetNode.right == null) {//这是一个叶子节点
                //判断targetNode是父节点的左子节点还是右子节点
                if (parent.left != null && parent.left.value == value) {
                    parent.left = null;
                    return;
                } else if (parent.right != null && parent.right.value == value) {
                    parent.right = null;
                    return;
                }
            } else if (targetNode.left != null && targetNode.right != null) {//第三种情况，有两颗子树
                int min = delRightTreeMin(targetNode.right);
                targetNode.value = min;
            } else {//删除只有一颗子树的节点
                //如果要删除的节点有左子节点
                if (targetNode.left != null) {
                    //如果targetNode是parent的左子节点
                    if (parent.left.value == value) {
                        parent.left = targetNode.left;
                    } else {
                        parent.right = targetNode.left;
                    }
                } else {//targetNode.right != null
                    if (parent.left.value == value) {
                        parent.left = targetNode.right;
                    } else {
                        parent.right = targetNode.right;
                    }
                }
            }
        }
    }

    //添加节点的方法
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }
    //中序遍历
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉排序树为空");
        }
    }
}

//创建node节点
class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    //查找要删除的节点

    /**
     *
     * @param value 希望删除的节点的值
     * @return  如果找到该节点，就返回该节点，否则返回null
     */
    public Node search(int value) {
        if (value == this.value) {
            return this;
        } else if (value < this.value) {//如果查找的值，小于当前节点，向左子树递归查找
            //判断如果左子节点位空就不找了
            if (this.left == null) {
                return null;
            }
            return this.left.search(value);
        } else {//如果查找的值大于当前的节点，向右子树递归查找
            if (this.right == null) {
                return null;
            }
            return this.right.search(value);
        }
    }

    //查找要删除节点的父节点

    /**
     *
     * @param value 要查找的节点的值
     * @return  返回的是要删除的节点的父节点，如果没有就返回null
     */
    public Node searchParent(int value) {
        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            //如果查找的这个值小于当前节点的这个值，并且节点不为空
            if (value < this.value && this.left != null) {
                return this.left.searchParent(value);
            } else if (value >= this.value && this.right != null) {
                return this.right.searchParent(value);
            } else {
                return null;//没有找到父节点
            }
        }
    }

    //添加节点的方法
    //递归的形式添加
    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (node.value > this.value) {
            if (this.right == null) {
                this.right = node;
            } else {
                //递归向右子树添加
                this.right.add(node);
            }
        } else {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222

平衡二叉树（AVL树）

基本介绍

​ 平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又称为AVL树，可以保证查询效率较高

​ 具有一下特点：它是一颗空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。平衡二叉树的常用实现方式有红黑树，AVL，替罪羊树，Treap，伸展树等

​ Avl树：[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jr1RvzpX-1674801911599)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image029.jpg)]

左旋转

当右子树大于左子树时，进行左旋转

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MaA0b2IO-1674801911600)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image031.jpg)]

右旋转

当左子树大于右子树时，进行右旋转

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wPpmbJx5-1674801911601)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image033.jpg)]

针对于双旋：

​ 如果右旋转,那么就要确保reight的reight >left

​ 如果左旋转，那么就要确保left的left > reight

public class AVLTreeDemo {
    public static void main(String[] args) {
//        int[] arr = {4,3,6,5,7,8};
        int[] arr = {10, 12, 8, 9, 7, 6};
//        int[] arr = {10,11,7,6,8,9};
        //创建一个AVLTree对象
        AVLTree avlTree = new AVLTree();
        //添加节点
        for (int i = 0; i < arr.length; i++) {
            avlTree.add(new Node(arr[i]));
        }

        //中序遍历
        avlTree.infixOrder();

        System.out.println("没有旋转之前，没有做平衡处理之前");
        System.out.println(avlTree.root.height());

        System.out.println("左子树的高度："+avlTree.root.left.height());
        System.out.println("右子树的高度："+avlTree.root.right.height());
        System.out.println();
        avlTree.infixOrder();
    }
}

class AVLTree {
    Node root;

    //查找要删除的节点
    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    //查找父节点
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    //编写方法

    /**
     *  1.返回node为根节点的二叉排序树的最小的值
     *  2。删除node为根节点二叉排序树的最小节点
     * @param node  传入的节点，当作一颗二叉排序树的跟阶段
     * @return  以Node为根节点的二叉排序树的最小节点的值
     */
    public int delRightTreeMin(Node node) {
        Node target = node;
        //循环查找左节点,就会找到最小值
        while (target.left != null) {
            target = target.left;
        }
        //这时target就指向了最小节点
        //删除最小节点
        delNode(target.value);
        return target.value;
    }

    //删除节点
    public void delNode(int value) {
        if (root == null) {
            return;
        } else {
            //在删除一个节点的时候需要先找到删除的节点
            Node targetNode = search(value);
            if (targetNode == null) {//如果没有找到要删除的节点，直接返回
                return;
            }
            //如果当我们发现当前这颗二叉树只有一个节点
            if (root.left == null && root.right == null) {
                root = null;
                return;
            }
            //查找targetNode的父节点
            Node parent = searchParent(value);
            //如果要删除的节点是叶子节点
            if (targetNode.left == null && targetNode.right == null) {//这是一个叶子节点
                //判断targetNode是父节点的左子节点还是右子节点
                if (parent.left != null && parent.left.value == value) {
                    parent.left = null;
                    return;
                } else if (parent.right != null && parent.right.value == value) {
                    parent.right = null;
                    return;
                }
            } else if (targetNode.left != null && targetNode.right != null) {//第三种情况，有两颗子树
                int min = delRightTreeMin(targetNode.right);
                targetNode.value = min;
            } else {//删除只有一颗子树的节点
                //如果要删除的节点有左子节点
                if (targetNode.left != null) {
                    //如果targetNode是parent的左子节点
                    if (parent != null){
                        if (parent.left.value == value) {
                            parent.left = targetNode.left;
                        } else {
                            parent.right = targetNode.left;
                        }
                    } else {
                        root = targetNode.left;
                    }
                } else {//targetNode.right != null
                    if (parent != null) {
                        if (parent.left.value == value) {
                            parent.left = targetNode.right;
                        } else {
                            parent.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }
            }
        }
    }

    //添加节点的方法
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }
    //中序遍历
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("二叉排序树为空");
        }
    }
}

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    //返回左子树的高度
    public int leftHeight() {
        if (left == null) {
            return 0;
        } else {
            return left.height();
        }
    }

    //返回右子树的高度
    public int rightHeight() {
        if (right == null) {
            return 0;
        } else {
            return right.height();
        }
    }

    //左旋转的方法
    private void leftRotate() {
        //创建新的节点，以当前根节点的值
        Node newNode = new Node(value);
        //把新的节点的左子树设置成当前节点的左子树
        newNode.left = left;
        //把新的节点的右子树设置成当前节点的右子树的左子树
        newNode.right = right.left;
        //把当前节点的值替换成右子节点的值的值
        value = right.value;
        //把当前节点的右子树设置成右子树的右子树
        right = right.right;
        //把当前节点的左子树设置成新的节点
        left = newNode;
    }

    //右旋转
    private void rightRotate() {
        Node newNode = new Node(value);
        newNode.right = right;
        newNode.left = left.right;
        value = left.value;
        left = left.left;
        right = newNode;
    }

    //返回以该节点为根节点的树的高度
    public int height() {
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    //查找要删除的节点

    /**
     *
     * @param value 希望删除的节点的值
     * @return  如果找到该节点，就返回该节点，否则返回null
     */
    public Node search(int value) {
        if (value == this.value) {
            return this;
        } else if (value < this.value) {//如果查找的值，小于当前节点，向左子树递归查找
            //判断如果左子节点位空就不找了
            if (this.left == null) {
                return null;
            }
            return this.left.search(value);
        } else {//如果查找的值大于当前的节点，向右子树递归查找
            if (this.right == null) {
                return null;
            }
            return this.right.search(value);
        }
    }

    //查找要删除节点的父节点

    /**
     *
     * @param value 要查找的节点的值
     * @return  返回的是要删除的节点的父节点，如果没有就返回null
     */
    public Node searchParent(int value) {
        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            //如果查找的这个值小于当前节点的这个值，并且节点不为空
            if (value < this.value && this.left != null) {
                return this.left.searchParent(value);
            } else if (value >= this.value && this.right != null) {
                return this.right.searchParent(value);
            } else {
                return null;//没有找到父节点
            }
        }
    }

    //添加节点的方法
    //递归的形式添加
    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (node.value > this.value) {
            if (this.right == null) {
                this.right = node;
            } else {
                //递归向右子树添加
                this.right.add(node);
            }
        } else {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        }

        //当添加完一个节点后，如果（右子树的高度 - 左子树的高度）> 1 ,那么就左旋转
        if (rightHeight() - leftHeight() > 1) {
            System.out.println("左旋转");
            if (right != null && right.rightHeight() < right.leftHeight()) {
                right.rightRotate();
                leftRotate();
            } else {
                leftRotate();
            }return;
        }
        //当添加完一个节点后，如果（左子树的高度 - 右子树的高度）> 1，那么就右旋转
        if (leftHeight() - rightHeight() > 1) {
            System.out.println("右旋转");
            //如果他的左子树的右子树的高度大于他左子树的左子树的高度
            if (left != null && left.rightHeight() > left.leftHeight()) {
                //先对当前节点的左节点（左子树）进行左旋转
                left.leftRotate();
                //再对当前节点进行右旋转
                rightRotate();
            } else {
                //直接进行右旋转
                rightRotate();
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-95I2kZpY-1674801911602)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image002.png)]

多叉树与B树

多叉树

​ 在二叉树中，每个节点有数据项，最多有两个子节点。如果允许每个节点可以有更多的数据和更多的子节点，就是多叉树

​ 2-3树，2-3-4树就是多叉树，多叉树通过重新组织节点，减少树的高度，能对二叉树进行优化

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-L5G8Mcf8-1674801911602)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image037.jpg)]

B树

基本介绍

B树通过重新组织节点，降低树的高度，并且减少i/o读写的次数来提升效率[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cVtKRTYf-1674801911603)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image039.jpg)]

​ 如图B树通过重新组织节点，降低了树的高度

​ 文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设置为等于一个（页得大小通常为4K），这样每个节点只需要一次I/O就可以完全载入

​ 将树的度M设置为1024，在600亿个元素中最多只需要4次I/O操作就可以读取到想要的元素，B树（B+）广泛用于文件存储系统以及数据库系统中

2-3树

基本介绍

​ 2-3树的所有叶子节点都在同一层（只要B树都满足这个条件）

​ 有两个子节点的节点二节点，二节点要么没有子节点，要么有两个子节点

​ 有三个子节点的节点叫做三节点，三节点要么没有子节点，要么有三个子节点

​ 2-3树是由二节点和三节点构成的树

除了23树，还有234树等。概念和23树类似，也是一种B树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6gyGq2oL-1674801911604)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image041.jpg)]

B树、B+树和B*树

B树

B-tree树即B树，B即Balanced，平衡的意思。有人把B-tree翻译成B-树，容易让人产生误会。会以为B-tree是一种树，而B树又是另一种树。实际上，B-tree就是指的B树

B+树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kjIciTGV-1674801911604)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image042.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-R3GebWI4-1674801911605)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image043.png)]

B*树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VA5YhVvu-1674801911606)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image044.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qpgBlAL3-1674801911606)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image045.png)]

图

图的基本介绍

为什么要有图

​ 前面学习线性表和树

​ 线性表局限于一个直接前驱和一个直接后继的关系

​ 树也只能有一个直接前驱也就是父节点

​ 当需要多对多关系时，这里就用到了图

图的举例

​ 图也是一种数据结构，其中可以具有零个或多个相邻元素。两个节点之间的连接称为便。节点也可以称为顶点。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jTurNCEw-1674801911607)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image047.jpg)]

图的常用概念

顶点（vertex）

边（edge）

路径

无向图[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-95u9mhWD-1674801911608)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image049.jpg)]

有向图[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xfsyfCIE-1674801911609)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image051.jpg)]

带权图[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7RXZ0F12-1674801911610)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image053.jpg)]

图的表示方式

图的表示方式有两种：二维数组表示（邻接矩阵）；链表表示（邻接表）

邻接矩阵

​ 邻接矩阵是表示图形中顶点之间相邻关系的矩阵。对于n个顶点的图而言，矩阵是row和col表示1…n个点

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ag85lWIK-1674801911610)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image055.jpg)]

邻接表

​ 邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在，会造成空间的一定损失

​ 邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-e3lL1QAU-1674801911611)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image057.jpg)]

图的遍历的介绍

所谓的图遍历，即是对节点的访问。一个图有那么多个节点，如何遍历这些节点，需要特定的策略，一般有两种访问策略：（1）深度优先遍历（2）广度优先遍历

图的深度优先遍历

​ 深度优先遍历，从从初始节点出发，初始访问节点可能有多个邻接节点，深度优先遍历的策略就是先访问第一个临界点，然后再以这个被访问的邻接节点作为初始节点，访问他的第一个邻接点，可以理解为：每次在访问完当前节点后首先访问当前节点的第一个邻接点

​ 可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个节点的所有邻接点进行横向访问

​ 显然，深度优先遍历是一个搜索递归的过程

深度优先遍历步骤

​ 访问初始节点v，并标记节点v为以访问

​ 查找节点v的第一个邻接节点w

​ 若w存在，则继续执行4，如果w不存在，则回到第一步，从v的下一个节点继续

​ 若w未被访问，对w进行深度优先遍历（即把w当作另一个v，然后进行123步骤）

​ 查找节点v的w邻节点的下一个邻节点，转到步骤3

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2pHlIC6N-1674801911612)(file:///C:/Users/16510/AppData/Local/Temp/msohtmlclip1/01/clip_image059.jpg)]

public int getFirstNeighbor(int index) {
   for (int i = 0; i < vertexList.size(); i++) {
       if (edges[index][i] > 0) {
           return i;
       }
   }
   return -1;
}

//根据前一个邻接节点的下标来获取下一个邻接节点
public int getNextNeighbor(int v1, int v2) {
   for (int i = v2 + 1; i < vertexList.size(); i++) {
       if (edges[v1][i] > 0) {
           return i;
       }
   }
   return -1;
}

//深度优先遍历算法
//i第一次就是0
private void dfs(boolean[] isVisited, int i) {
   //首先我们访问该节点,输出
   System.out.print(getValueByIndex(i) + "->   ");
   //将节点设置为以及访问
   isVisited[i] = true;
   //查找节点v的第一个邻接节点w
   int w = getFirstNeighbor(i);
   while (w != -1) {
       if (!isVisited[w]) {
           dfs(isVisited, w);
       }
       //如果w已经被访问过
       w = getNextNeighbor(i, w);
   }
}

//对dfs进行重载，遍历我们所有的节点并进行dfs
private void dfs() {
   //遍历所有的节点，进行dfs
   for (int i = 0; i < getNumOfVertex(); i++) {
       if (!isVisited[i]) {
           dfs(isVisited, i);
       }
   }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

图的广度优先遍历

广度优先遍历基本思想

​ 图的广度优先搜索（Broad First Search）

​ 类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点顺序，以便按这个顺序来访问这些节点的邻接点

广度优先遍历算法步骤

​ 访问初始节点v并标记为节点v为以访问

​ 节点v入队列

​ 当队列非空时，继续执行，否则算法结束

​ 出队列，取得头节点u。

​ 查找节点u的第一个邻接节点w

​ 若节点u的邻接w不存在，则转到第三步；否则循环执行以下三个步骤：

​ 若节点w尚未被访问，则访问节点w并标记为以访问

​ 节点w入队列

​ 查找节点u的继w邻接点后的下一个邻接点w，转到六

图的广度优先遍历和图的深度优先遍历之间的对比

​ 图的广度优先遍历的时间复杂度为O(n + e)

​ 图的深度优先遍历的时间复杂度为O(n²)

//对一个一个节点进行广度优先遍历
private void bfs(boolean[] isVisited, int i) {
    int u;//表示头节点对应的一个下标
    int w;//邻接节点的下标
    //队列，记录节点访问的顺序
    LinkedList<Object> linked = new LinkedList<>();
    //访问节点
    System.out.print(getValueByIndex(i) + "->   ");
    //标记为已经访问
    isVisited[i] = true;
    //将节点加入队列
    linked.addLast(i);

    while (!linked.isEmpty()) {
        //取出队列的头节点的下标
        u = (Integer)linked.removeFirst();
        //得到第一个邻接点的下标w
        w = getFirstNeighbor(u);
        while (w != -1) {//找到了
            //是否访问过
            if (!isVisited[w]) {
                System.out.print(getValueByIndex(w) + "->   ");
                //标记已经访问
                isVisited[w] = true;
                //入队
                linked.addLast(w);
            }
            //以u为前驱节点，找w后面的下一个邻接点
            w = getNextNeighbor(u, w);//体现出广度优先遍历
        }
    }
}

//遍历所有的节点都进行广度优先搜索
private void bfs() {
    for (int i = 0; i < getNumOfVertex(); i++) {
        if (!isVisited[i]) {
            bfs(isVisited, i);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

算法

二分查找算法（非递归）

​

public static int binarySearch(int[] arr, int value) { int left = 0; int right = arr.length - 1; int mind = 0; while (left <= right) { mind = (left + right) / 2; if (arr[mind] < value) { left = mind + 1; } else if (arr[mind] > value) { right = mind - 1; } else { return mind; } } return -1; }

分治算法

分治算法的基本步骤

分治法在每一层递归上都有三个步骤：

​ 分解：将原问题分解为若干个规模较小的问题，相互独立，与原问题形式相同的子问题

​ 解决：若子问题规模较小而容易被解决则直接解决，否则递归的解各个子问题

​ 合并：将各个子问题的解合并为原问题的解

分治(Divide-and-Conquer§)算法设计模式

​ 其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已经容易直接解出，不必再继续分解。ADHOC§是该分治算法中的基本子算法，用于直接解小规模问题P。因此，当P的规模不超过n0时，直接用算法ADHOC§求解。算法MERGE(y1, y2,…yk)是该分治算法中的合并子算法，用于将P的子问题P1, P2…Pk的相应的解y1,y2…yk合并为P的解

汉诺塔

public static int binarySearch(int[] arr, int value) {
   int left = 0;
   int right = arr.length - 1;
   int mind = 0;
   while (left <= right) {
       mind = (left + right) / 2;
       if (arr[mind] < value) {
           left = mind + 1;
       } else if (arr[mind] > value) {
           right = mind - 1;
       } else {
           return mind;
       }
   }
   return -1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

动态规划

动态规划算法介绍

​ 动态规划（Dynamic Programming）算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优的处理算法

​ 动态规划算法和分治算法类似，其基本思想也是将待求解问题分解成诺干子问题，先求解子问题，然后从这些子问题的解得到原问题的解

​ 与分治算法不同的是，适合用于动态规划求解的问题，经分解得到子问题往往不是互相独立的。（即下一个子阶段的求解是建立在上一个子阶段的解的基础之上，进行近一步的求解）

​ 动态规划可以通过填表的方式来逐步推进，得到最优的解

​ 动态规划算法是需要把一个大问题换成一个一个的小问题，而这些小问题都可以直接求解，但是每个动态规划算法的求解方式不一样，总结为 ：比如机器人走路的问题：

​ 这个问题的动态规划策略为：f[i] = f[I – 1][j] + f[i][j -1]，

​ 而背包问题的策略为：

​ V[i][j] = Max(v[I - 1][j], val[I - 1][j – w[I - 1]])

​ 虽然每个问题的最小问题的策略都会得到不同的公式，但是总结而言次的策略都是以这种形式来表达的

​ 动态规划最经典的案例是斐波那契数列，其策略为：

​ F[k] = f[k – 1] + f[k – 2]

背包问题

KMP算法

​ Kmp算法失配时：已匹配字符数 – 失配字符的上一位字符所对应的最大长度值

贪心算法

​ 贪心算法是指在对问题进行求解时，在每一步选择中都采取最好或者最优的算法

​ 贪婪算法所得到的结果不一定是最优的结果（有时候会是最优解），但是都是相对近似最优的结果

普利姆算法

普利姆（Prim）算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有(n -1)条边包含所有n个顶点的连通子图，也就是所谓的极小联通子图

普利姆的算法如下

设G = (V,E)是连通图，T=(U,D)是最小生成树，V,U是顶点集合，E，D是边的集合

若从顶点u开始构造最小生成树，从集合V中取出顶点u放入集合u中，标记顶点v的visited[u] = 1

若集合U中顶点ui与集合V – U中的顶点vj之间存在边，则寻找这些边中的权最小的边，但不能构成回路，将顶点vj加入集合U中，将边（ui,vj）加入到集合D中，标记visited[vj] = 1

克鲁斯卡尔算法

​ 克鲁斯卡尔（Kruskal）算法，是用来求加权连通图的最小生成树的算法

​ 基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路

​ 基本做法：首先构造一个只含有n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止

回路

加入的边的两个顶点不能都指向同一个终点，否则将构成回路

迪杰斯特拉算法

​ 迪杰斯特拉算法（Dijkstra）算法是经典的最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外 层层扩散（广度优先搜索思想），直到扩展到终点为止。

弗洛伊德算法VS迪杰斯特拉算法

迪杰斯特拉算法通过选定的被访问顶点，求出从出发顶点到其他顶点的最短路径；弗罗伊特算法中每一个顶点都是出发访问点，所以需要将每一个顶点看做被访问顶点，求出从每个顶点到其他顶点的最短路径

弗洛伊德算法

​ 设置顶点vi到顶点vk的最短路径已经直到为Lik，顶点vk到vj的最短路径已知为Lkj，顶点vi到vj的路径为lij，则vi到vj的最短路径为：min((Lik + Lkj), Lij)，vk的取值为图中所有顶点，则可获得vi到vk的最短路径

​ 至于vi到vk的最短路径Lik或者vk到vj的最短路径Lkj，是同样的方式获得

马踏棋盘算法

骑士周游问题的解决步骤和思路分析

​ 创建期盼 chessBoard，是一个二维数组

​ 将当前位置设置为已经访问，然后根据当前位置，计算马儿还能走到那个位置，并放到一个集合中（ArrayList），最多有8个位置，每走一步，就使用step + 1

​ 遍历ArrayList中存放的所有位置，看看那个可以走通，如果走通，就继续走，走不通就回溯

​ 判断马儿是否完成了任务，使用step和应该走的步数进行比较，如果没有达到数量，则表示没有完成任务，将整个棋盘置为0

​ （注意）马儿不同的走法（策略），会得到不同的结果，效率也会有所影响

package com.fax.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

public class HorseChessborad {
    private static int x;//表示棋盘的列
    private static int y;//表示棋盘的行
    //创建一个数组，标记棋盘的各个位置是否被访问过
    private static boolean visited[];
    //使用一个属性，标记是否棋盘所有位置都配访问过了
    private static boolean finished;//如果为true表示成功，反之就是表示没有成功
    public static void main(String[] args) {
        //测试骑士周游算法是否正确
        x = 8;
        y = 8;
        int row = 1;//马儿初始位置的行，从1开始编号
        int column = 1;//马儿初始的列，从1开始编号
        //创建棋盘
        int[][] chessboard = new int[x][y];
        visited = new boolean[x * y];//初始值都是false
        long begin = System.currentTimeMillis();
        traversalChessboard(chessboard, row - 1, column - 1, 1);
        long end = System.currentTimeMillis();
        System.out.println(end - begin);

        for (int[] rows : chessboard) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
    }

    /**
     * 完成其实周游问题的算法
     * @param chessboard    棋盘
     * @param row   马儿当前的位置行，从0开始
     * @param column    马儿当前位置的列
     * @param step  马儿走的是第几步，初始位置就是第一步
     */
    public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
        chessboard[row][column] = step;
        //row = 4 x = 8 column = 4 = 4 * 8 + 4
        visited[row * x + column] = true;//标记该位置已经访问
        //获取当前位置可以走的下一个位置的集合
        ArrayList<Point> ps = next(new Point(column, row));

        //对ps进行排序，排序的规则就是对ps所有的元素对象的下一步的位置的数目进行非递减排序
        sort(ps);

        //遍历ps
        while (!ps.isEmpty()) {
            Point p = ps.remove(0);//取出一个可以走的位置
            //判断该点是否已经访问
            if (!visited[p.y * x + p.x]) {//说明还没有访问过
                traversalChessboard(chessboard, p.y, p.x, step + 1);
            }
        }
        //判断马儿是否完成了任务，使用 step 和应该走的步数比较，如果没有达到数量，则表示没有完成任务，将整个棋盘置0
        /*
        说明：step < x * y 成立的情况有两种
            棋盘到目前为止仍然没有走完
            棋盘处于一个回溯过程
         */
        if (step < x * y && !finished) {
            chessboard[row][column] = 0;
            visited[row * x + column] = false;
        } else {
            finished = true;
        }
    }

    //功能：根据当前的位置
    public static ArrayList<Point> next(Point curPoint) {
        ArrayList<Point> ps = new ArrayList<>();
        Point p1 = new Point();
        //表示马儿可以走5这个位置
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 1) < x && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 2) < x && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 2) < x && (p1.y = curPoint.y + 1) < y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 1) < x && (p1.y = curPoint.y + 2) < y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < y) {
            ps.add(new Point(p1));
        }
        return ps;
    }

    //根据当前这一步的所有的下一步的选择位置进行非递减排序,减少回溯的可能
    public static void sort(ArrayList<Point> ps) {
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                //获取到o1的下一步的所有位置的个数
                int count1 = next(o1).size();
                int count2 = next(o2).size();
                if (count1 < count2) {
                    return -1;
                } else if (count1 == count2) {
                    return 0;
                } else {
                    return 1;
                }
            }
        });
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

断马儿是否完成了任务，使用step和应该走的步数进行比较，如果没有达到数量，则表示没有完成任务，将整个棋盘置为0

​ （注意）马儿不同的走法（策略），会得到不同的结果，效率也会有所影响

package com.fax.horse;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;

public class HorseChessborad {
    private static int x;//表示棋盘的列
    private static int y;//表示棋盘的行
    //创建一个数组，标记棋盘的各个位置是否被访问过
    private static boolean visited[];
    //使用一个属性，标记是否棋盘所有位置都配访问过了
    private static boolean finished;//如果为true表示成功，反之就是表示没有成功
    public static void main(String[] args) {
        //测试骑士周游算法是否正确
        x = 8;
        y = 8;
        int row = 1;//马儿初始位置的行，从1开始编号
        int column = 1;//马儿初始的列，从1开始编号
        //创建棋盘
        int[][] chessboard = new int[x][y];
        visited = new boolean[x * y];//初始值都是false
        long begin = System.currentTimeMillis();
        traversalChessboard(chessboard, row - 1, column - 1, 1);
        long end = System.currentTimeMillis();
        System.out.println(end - begin);

        for (int[] rows : chessboard) {
            for (int step : rows) {
                System.out.print(step + "\t");
            }
            System.out.println();
        }
    }

    /**
     * 完成其实周游问题的算法
     * @param chessboard    棋盘
     * @param row   马儿当前的位置行，从0开始
     * @param column    马儿当前位置的列
     * @param step  马儿走的是第几步，初始位置就是第一步
     */
    public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
        chessboard[row][column] = step;
        //row = 4 x = 8 column = 4 = 4 * 8 + 4
        visited[row * x + column] = true;//标记该位置已经访问
        //获取当前位置可以走的下一个位置的集合
        ArrayList<Point> ps = next(new Point(column, row));

        //对ps进行排序，排序的规则就是对ps所有的元素对象的下一步的位置的数目进行非递减排序
        sort(ps);

        //遍历ps
        while (!ps.isEmpty()) {
            Point p = ps.remove(0);//取出一个可以走的位置
            //判断该点是否已经访问
            if (!visited[p.y * x + p.x]) {//说明还没有访问过
                traversalChessboard(chessboard, p.y, p.x, step + 1);
            }
        }
        //判断马儿是否完成了任务，使用 step 和应该走的步数比较，如果没有达到数量，则表示没有完成任务，将整个棋盘置0
        /*
        说明：step < x * y 成立的情况有两种
            棋盘到目前为止仍然没有走完
            棋盘处于一个回溯过程
         */
        if (step < x * y && !finished) {
            chessboard[row][column] = 0;
            visited[row * x + column] = false;
        } else {
            finished = true;
        }
    }

    //功能：根据当前的位置
    public static ArrayList<Point> next(Point curPoint) {
        ArrayList<Point> ps = new ArrayList<>();
        Point p1 = new Point();
        //表示马儿可以走5这个位置
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 1) < x && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 2) < x && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 2) < x && (p1.y = curPoint.y + 1) < y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x + 1) < x && (p1.y = curPoint.y + 2) < y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < y) {
            ps.add(new Point(p1));
        }
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < y) {
            ps.add(new Point(p1));
        }
        return ps;
    }

    //根据当前这一步的所有的下一步的选择位置进行非递减排序,减少回溯的可能
    public static void sort(ArrayList<Point> ps) {
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                //获取到o1的下一步的所有位置的个数
                int count1 = next(o1).size();
                int count2 = next(o2).size();
                if (count1 < count2) {
                    return -1;
                } else if (count1 == count2) {
                    return 0;
                } else {
                    return 1;
                }
            }
        });
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127