数据结构与算法

原作者——3833恐高宇航员 有修改

O 度

  • 度量一个程序(算法)执行时间的两种方法

    时间复杂度：

    1. 事后统计法
      两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, 这种方式，要在同一台计算机的相同状态下运行，才能比较那个算法速度更快
    2. 事前估算的方法
      通过分析某个算法的时间复杂度来判断哪个算法更优

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

    时间频度：

    常见的时间复杂度：

    1. 常数阶 O(1)
    2. 对数阶 O(log2n)
    3. 线性阶 O(n)
    4. 线性对数阶
    5. 平方阶 O(n^2)
    6. 立方阶 O(n^3)
    7. k 次方阶 O(n^k)
    8. 指数阶O(2^n)
  • 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度

    空间复杂度：

1 稀疏数组和队列

1.1 稀疏数组

  • 当一个数组中大部分元素为0，或者为同一个值的数组时，可以使用稀疏数组来保存该数组

    基本介绍：

    二维数组转稀疏数组思路：

    1. 遍历原始的二维数组，得到有效数据的个数sum
    2. 根据sum就可以创建稀疏数组 sparseArr int[sum + 1] [3]

    3. 将二维数组的有效数据数据存入到稀疏数组

      稀疏数组转二维数组思路：

    4. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组

    5. 在读取稀疏数组后几行的数据，并赋给原始的二维数组

      代码实现：Java数据结构与算法-尚硅谷 - 图2

      ```java public class SparseArray { public static void main(String[] args) { // 创建一个原始的二维数组 11 * 11 // 0: 表示没有棋子， 1 表示 黑子 2 表蓝子 int chessArr1[][] = new int[11][11]; chessArr1[1][2] = 1; chessArr1[2][3] = 2; chessArr1[4][5] = 2; // 输出原始的二维数组 System.out.println(“原始的二维数组~~”); for (int[] row : chessArr1) {

      1.   for (int data : row) {
      2.       System.out.printf("%d\t", data);
      3.   }
      4.   System.out.println();

      }

      // 将二维数组 转 稀疏数组的思 // 1. 先遍历二维数组 得到非0数据的个数 int sum = 0; for (int i = 0; i < 11; i++) {

      1.   for (int j = 0; j < 11; j++) {
      2.       if (chessArr1[i][j] != 0) {
      3.           sum++;
      4.       }
      5.   }

      }

      // 2. 创建对应的稀疏数组 int sparseArr[][] = new int[sum + 1][3];

      // 给稀疏数组赋值 sparseArr[0][0] = 11; sparseArr[0][1] = 11; sparseArr[0][2] = sum;

      // 遍历二维数组，将非0的值存放到 sparseArr中 int count = 0; //count 用于记录是第几个非0数据 for (int i = 0; i < 11; i++) {

      1.   for (int j = 0; j < 11; j++) {
      2.       if (chessArr1[i][j] != 0) {
      3.           count++;
      4.           sparseArr[count][0] = i;
      5.           sparseArr[count][1] = j;
      6.           sparseArr[count][2] = chessArr1[i][j];
      7.       }
      8.   }

      }

      // 输出稀疏数组的形式 System.out.println(); System.out.println(“得到稀疏数组为~~~~”); for (int i = 0; i < sparseArr.length; i++) {

      1.   System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);

      } System.out.println();

  1.     //将稀疏数组 恢复成 原始的二维数组
  2.     /*
  3.      *  1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的  chessArr2 = int [11][11]
  4.           2. 在读取稀疏数组后几行的数据，并赋给 原始的二维数组 即可.
  5.      */
  7.     //1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
  9.     int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
  11.     //2. 在读取稀疏数组后几行的数据(从第二行开始)，并赋给 原始的二维数组 即可
  13.     for(int i = 1; i < sparseArr.length; i++) {
  14.         chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
  15.     }
  17.     // 输出恢复后的二维数组
  18.     System.out.println();
  19.     System.out.println("恢复后的二维数组");
  21.     for (int[] row : chessArr2) {
  22.         for (int data : row) {
  23.             System.out.printf("%d\t", data);
  24.         }
  25.         System.out.println();
  26.     }
  27. }

}

  3. <a name="925547f2"></a>
  4. ## 1.2队列
  5. <a name="568dc93e-1"></a>
  6. #### 基本介绍：
  8.    - 队列是一个有序列表，可以用数组或是链表来实现
  9.    - 遵循先入先出的原则：先存入队列的数据，要先取出。后存入的要后取出
  10. <a name="3ea03faf"></a>
  11. ### 1.2.1 数组模拟队列
  12. <a name="0fade1ff"></a>
  13. #### 思路分析
  15.    1. fornt：队列第一个元素的前一位
  16.    2. rear：队列最后元素
  17.    3. maxsize：队列的最大容量
  18.    4. 尾指针rear 小于队列的最大下标maxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据
  19.    5. front ==rear ：队列空
  20.    6. rear ==maxSize -1：队列满
  21. -  <br />![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-06-23%2017.18.46.jpg#id=xgTPM&originHeight=416&originWidth=1124&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=) 
  22. <a name="10c8962a"></a>
  23. #### 代码实现：
  24. ```java
  25. public class ArrayQueueDemo {
  26.     public static void main(String[] args) {
  27.         //测试一把
  28.         //创建一个队列
  29.         ArrayQueue queue = new ArrayQueue(3);
  30.         char key = ' '; //接收用户输入
  31.         Scanner scanner = new Scanner(System.in);//
  32.         boolean loop = true;
  33.         //输出一个菜单
  34.         while(loop) {
  35.             System.out.println("s(show): 显示队列");
  36.             System.out.println("e(exit): 退出程序");
  37.             System.out.println("a(add): 添加数据到队列");
  38.             System.out.println("g(get): 从队列取出数据");
  39.             System.out.println("h(head): 查看队列头的数据");
  40.             key = scanner.next().charAt(0);//接收一个字符
  41.             switch (key) {
  42.             case 's':
  43.                 queue.showQueue();
  44.                 break;
  45.             case 'a':
  46.                 System.out.println("输出一个数");
  47.                 int value = scanner.nextInt();
  48.                 queue.addQueue(value);
  49.                 break;
  50.             case 'g': //取出数据
  51.                 try {
  52.                     int res = queue.getQueue();
  53.                     System.out.printf("取出的数据是%d\n", res);
  54.                 } catch (Exception e) {
  55.                     // TODO: handle exception
  56.                     System.out.println(e.getMessage());
  57.                 }
  58.                 break;
  59.             case 'h': //查看队列头的数据
  60.                 try {
  61.                     int res = queue.headQueue();
  62.                     System.out.printf("队列头的数据是%d\n", res);
  63.                 } catch (Exception e) {
  64.                     // TODO: handle exception
  65.                     System.out.println(e.getMessage());
  66.                 }
  67.                 break;
  68.             case 'e': //退出
  69.                 scanner.close();
  70.                 loop = false;
  71.                 break;
  72.             default:
  73.                 break;
  74.             }
  75.         }
  76.         System.out.println("程序退出~~");
  77.     }
  78. }
  80. // 使用数组模拟队列-编写一个ArrayQueue类
  81. class ArrayQueue {
  82.     private int maxSize; // 表示数组的最大容量
  83.     private int front; // 队列头
  84.     private int rear; // 队列尾
  85.     private int[] arr; // 该数据用于存放数据, 模拟队列
  87.     // 创建队列的构造器
  88.     public ArrayQueue(int arrMaxSize) {
  89.         maxSize = arrMaxSize;
  90.         arr = new int[maxSize];
  91.         front = -1; // 指向队列头部，分析出front是指向队列头的前一个位置.
  92.         rear = -1; // 指向队列尾，指向队列尾的数据(即就是队列最后一个数据)
  93.     }
  95.     // 判断队列是否满
  96.     public boolean isFull() {
  97.         return rear == maxSize - 1;
  98.     }
  100.     // 判断队列是否为空
  101.     public boolean isEmpty() {
  102.         return rear == front;
  103.     }
  105.     // 添加数据到队列
  106.     public void addQueue(int n) {
  107.         // 判断队列是否满
  108.         if (isFull()) {
  109.             System.out.println("队列满，不能加入数据~");
  110.             return;
  111.         }
  112.         rear++; // 让rear 后移
  113.         arr[rear] = n;
  114.     }
  116.     // 获取队列的数据, 出队列
  117.     public int getQueue() {
  118.         // 判断队列是否空
  119.         if (isEmpty()) {
  120.             // 通过抛出异常
  121.             throw new RuntimeException("队列空，不能取数据");
  122.         }
  123.         front++; // front后移
  124.         return arr[front];
  126.     }
  128.     // 显示队列的所有数据
  129.     public void showQueue() {
  130.         // 遍历
  131.         if (isEmpty()) {
  132.             System.out.println("队列空的，没有数据~~");
  133.             return;
  134.         }
  135.         for (int i = 0; i < arr.length; i++) {
  136.             System.out.printf("arr[%d]=%d\n", i, arr[i]);
  137.         }
  138.     }
  140.     // 显示队列的头数据， 注意不是取出数据
  141.     public int headQueue() {
  142.         // 判断
  143.         if (isEmpty()) {
  144.             throw new RuntimeException("队列空的，没有数据~~");
  145.         }
  146.         return arr[front + 1];
  147.     }
  148. }

1.2.2 数组模拟环形队列

思路分析：

  1. front就指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素，front的初始值=0
  2. rear指向队列的最后一个元泰的后一个位置，因为希望空出一个空间做为约定，rear 的初始值=0
  3. 队列满： (rear +1) % maxsize =front
  4. 队列空：rear == front

  5. 队列中有效的数据的个数： (rear + maxsize - front) % maxSize

    代码实现：

    ```java public class CircleArrayQueueDemo {

    public static void main(String[] args) {

    System.out.println(“测试数组模拟环形队列的案例~~~”);

    // 创建一个环形队列 CircleArray queue = new CircleArray(4); //说明设置4, 其队列的有效数据最大是3 char key = ‘ ‘; // 接收用户输入 Scanner scanner = new Scanner(System.in);// boolean loop = true; // 输出一个菜单 while (loop) {

    1.   System.out.println("s(show): 显示队列");
    2.   System.out.println("e(exit): 退出程序");
    3.   System.out.println("a(add): 添加数据到队列");
    4.   System.out.println("g(get): 从队列取出数据");
    5.   System.out.println("h(head): 查看队列头的数据");
    6.   key = scanner.next().charAt(0);// 接收一个字符
    7.   switch (key) {
    8.   case 's':
    9.       queue.showQueue();
    10.       break;
    11.   case 'a':
    12.       System.out.println("输出一个数");
    13.       int value = scanner.nextInt();
    14.       queue.addQueue(value);
    15.       break;
    16.   case 'g': // 取出数据
    17.       try {
    18.           int res = queue.getQueue();
    19.           System.out.printf("取出的数据是%d\n", res);
    20.       } catch (Exception e) {
    21.           // TODO: handle exception
    22.           System.out.println(e.getMessage());
    23.       }
    24.       break;
    25.   case 'h': // 查看队列头的数据
    26.       try {
    27.           int res = queue.headQueue();
    28.           System.out.printf("队列头的数据是%d\n", res);
    29.       } catch (Exception e) {
    30.           // TODO: handle exception
    31.           System.out.println(e.getMessage());
    32.       }
    33.       break;
    34.   case 'e': // 退出
    35.       scanner.close();
    36.       loop = false;
    37.       break;
    38.   default:
    39.       break;
    40.   }

    } System.out.println(“程序退出~~”); }

}

class CircleArray { private int maxSize; // 表示数组的最大容量 //front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素 //front 的初始值 = 0 private int front; //rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定. //rear 的初始值 = 0 private int rear; // 队列尾 private int[] arr; // 该数据用于存放数据, 模拟队列

  1. public CircleArray(int arrMaxSize) {
  2.     maxSize = arrMaxSize;
  3.     arr = new int[maxSize];
  4. }
  6. // 判断队列是否满
  7. public boolean isFull() {
  8.     return (rear  + 1) % maxSize == front;
  9. }
  11. // 判断队列是否为空
  12. public boolean isEmpty() {
  13.     return rear == front;
  14. }
  16. // 添加数据到队列
  17. public void addQueue(int n) {
  18.     // 判断队列是否满
  19.     if (isFull()) {
  20.         System.out.println("队列满，不能加入数据~");
  21.         return;
  22.     }
  23.     //直接将数据加入
  24.     arr[rear] = n;
  25.     //将 rear 后移, 这里必须考虑取模
  26.     rear = (rear + 1) % maxSize;
  27. }
  29. // 获取队列的数据, 出队列
  30. public int getQueue() {
  31.     // 判断队列是否空
  32.     if (isEmpty()) {
  33.         // 通过抛出异常
  34.         throw new RuntimeException("队列空，不能取数据");
  35.     }
  36.     // 这里需要分析出 front是指向队列的第一个元素
  37.     // 1. 先把 front 对应的值保留到一个临时变量
  38.     // 2. 将 front 后移, 考虑取模
  39.     // 3. 将临时保存的变量返回
  40.     int value = arr[front];
  41.     front = (front + 1) % maxSize;
  42.     return value;
  44. }
  46. // 显示队列的所有数据
  47. public void showQueue() {
  48.     // 遍历
  49.     if (isEmpty()) {
  50.         System.out.println("队列空的，没有数据~~");
  51.         return;
  52.     }
  53.     // 思路：从front开始遍历，遍历多少个元素
  54.     // 动脑筋
  55.     for (int i = front; i < front + size() ; i++) {
  56.         System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
  57.     }
  58. }
  60. // 求出当前队列有效数据的个数
  61. public int size() {
  62.     // rear = 2
  63.     // front = 1
  64.     // maxSize = 3 
  65.     return (rear + maxSize - front) % maxSize;   
  66. }
  68. // 显示队列的头数据， 注意不是取出数据
  69. public int headQueue() {
  70.     // 判断
  71.     if (isEmpty()) {
  72.         throw new RuntimeException("队列空的，没有数据~~");
  73.     }
  74.     return arr[front];
  75. }

}

  2. <a name="5e619256"></a>
  3. # 2 链表
  5. - 链表是有序的列表，但是它在内存中是存储如下 ![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-06-26%2023.41.11.jpg#id=TXa8L&originHeight=734&originWidth=902&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=) 
  6. <a name="568dc93e-2"></a>
  7. #### 基本介绍：
  8. <a name="3d6266e7"></a>
  9. #### 小结：
  11.    1. 链表是以节点的方式来存储,是链式存储
  12.    2. 每个节点包含 data 域， next 域：指向下一个节点.
  13.    3. 发现链表的各个节点不一定是连续存储
  14.    4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
  16. <a name="f4899668"></a>
  17. ## 2.1 单向链表
  19. -  <br />![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-07-01%2010.13.56.jpg#id=X1PTN&originHeight=358&originWidth=1120&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=) 
  20. <a name="568dc93e-3"></a>
  21. #### 基本介绍：
  22. <a name="f4651bfe"></a>
  23. ### 2.1.1 功能实现
  24. <a name="acd64e4a"></a>
  25. #### 定义：
  26. ```java
  27. //定义HeroNode ， 每个HeroNode 对象就是一个节点
  28. class HeroNode {
  29.    public int no;
  30.    public String name;
  31.    public String nickname;
  32.    public HeroNode next; //指向下一个节点
  33.    //构造器
  34.    public HeroNode(int no, String name, String nickname) {
  35.       this.no = no;
  36.       this.name = name;
  37.       this.nickname = nickname;
  38.    }
  39.    //为了显示方法，我们重新toString
  40.    @Override
  41.    public String toString() {
  42.       return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
  43.    }
  44. }

遍历显示：

  1. //显示链表[遍历]
  2.     public void list() {
  3.         //判断链表是否为空
  4.         if(head.next == null) {
  5.             System.out.println("链表为空");
  6.             return;
  7.         }
  8.         //因为头节点，不能动，因此我们需要一个辅助变量来遍历
  9.         HeroNode temp = head.next;
  10.         while(true) {
  11.             //判断是否到链表最后
  12.             if(temp == null) {
  13.                 break;
  14.             }
  15.             //输出节点的信息
  16.             System.out.println(temp);
  17.             //将temp后移， 一定小心
  18.             temp = temp.next;
  19.         }


  • Java数据结构与算法-尚硅谷 - 图3

    尾部直接添加：

    1. //添加节点到单向链表
    3.  //思路，当不考虑编号顺序时
    4.  //1. 找到当前链表的最后节点
    5.  //2. 将最后这个节点的next 指向 新的节点
    6.  public void add(HeroNode heroNode) {
    8.      //因为head节点不能动，因此我们需要一个辅助遍历 temp
    9.      HeroNode temp = head;
    10.      //遍历链表，找到最后
    11.      while(true) {
    12.          //找到链表的最后
    13.          if(temp.next == null) {//
    14.              break;
    15.          }
    16.          //如果没有找到最后, 将将temp后移
    17.          temp = temp.next;
    18.      }
    19.      //当退出while循环时，temp就指向了链表的最后
    20.      //将最后这个节点的next 指向 新的节点
    21.      temp.next = heroNode;
    22.  }


  • Java数据结构与算法-尚硅谷 - 图4

    按照编号顺序添加：

    1. //第二种方式在添加英雄时，根据排名将英雄插入到指定位置
    2.  //(如果有这个排名，则添加失败，并给出提示)
    3.  public void addByOrder(HeroNode heroNode) {
    4.      //因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
    5.      //因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
    6.      HeroNode temp = head;
    7.      boolean flag = false; // flag标志添加的编号是否存在，默认为false
    8.      while(true) {
    9.          if(temp.next == null) {//说明temp已经在链表的最后
    10.              break; //
    11.          } 
    12.          if(temp.next.no > heroNode.no) { //位置找到，就在temp的后面插入
    13.              break;
    14.          } else if (temp.next.no == heroNode.no) {//说明希望添加的heroNode的编号已然存在
    16.              flag = true; //说明编号存在
    17.              break;
    18.          }
    19.          temp = temp.next; //后移，遍历当前链表
    20.      }
    21.      //判断flag 的值
    22.      if(flag) { //不能添加，说明编号存在
    23.          System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
    24.      } else {
    25.          //插入到链表中, temp的后面
    26.          heroNode.next = temp.next;
    27.          temp.next = heroNode;
    28.      }
    29.  }

  • 修改节点：

    1. //修改节点的信息, 根据no编号来修改，即no编号不能改.
    2. //说明
    3. //1. 根据 newHeroNode 的 no 来修改即可
    4. public void update(HeroNode newHeroNode) {
    5.     //判断是否空
    6.     if(head.next == null) {
    7.         System.out.println("链表为空~");
    8.         return;
    9.     }
    10.     //找到需要修改的节点, 根据no编号
    11.     //定义一个辅助变量
    12.     HeroNode temp = head.next;
    13.     boolean flag = false; //表示是否找到该节点
    14.     while(true) {
    15.         if (temp == null) {
    16.             break; //已经遍历完链表
    17.         }
    18.         if(temp.no == newHeroNode.no) {
    19.             //找到
    20.             flag = true;
    21.             break;
    22.         }
    23.         temp = temp.next;
    24.     }
    25.     //根据flag 判断是否找到要修改的节点
    26.     if(flag) {
    27.         temp.name = newHeroNode.name;
    28.         temp.nickname = newHeroNode.nickname;
    29.     } else { //没有找到
    30.         System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
    31.     }
    32. }

  • Java数据结构与算法-尚硅谷 - 图5

    删除节点：

    1. //删除节点
    2. //思路
    3. //1. head 不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
    4. //2. 说明我们在比较时，是temp.next.no 和  需要删除的节点的no比较
    5. public void del(int no) {
    6. HeroNode temp = head;
    7. boolean flag = false; // 标志是否找到待删除节点的
    8. while(true) {
    9.    if(temp.next == null) { //已经到链表的最后
    10.       break;
    11.    }
    12.    if(temp.next.no == no) {
    13.       //找到的待删除节点的前一个节点temp
    14.       flag = true;
    15.       break;
    16.    }
    17.    temp = temp.next; //temp后移，遍历
    18. }
    19. //判断flag
    20. if(flag) { //找到
    21.    //可以删除
    22.    temp.next = temp.next.next;
    23. }else {
    24.    System.out.printf("要删除的 %d 节点不存在\n", no);
    25. }
    26. }

2.1.2 面试题

获取到单链表的节点的个数：

  1. //方法：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点)
  2.    /**
  3.     * 
  4.     * @param head 链表的头节点
  5.     * @return 返回的就是有效节点的个数
  6.     */
  7.    public static int getLength(HeroNode head) {
  8.       if(head.next == null) { //空链表
  9.          return 0;
  10.       }
  11.       int length = 0;
  12.       //定义一个辅助的变量, 这里我们没有统计头节点
  13.       HeroNode cur = head.next;
  14.       while(cur != null) {
  15.          length++;
  16.          cur = cur.next; //遍历
  17.       }
  18.       return length;
  19.    }
  20. }

查找单链表中的倒数第k个结点：

  1. //查找单链表中的倒数第k个结点 【新浪面试题】
  2. //思路
  3. //1. 编写一个方法，接收head节点，同时接收一个index 
  4. //2. index 表示是倒数第index个节点
  5. //3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
  6. //4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
  7. //5. 如果找到了，则返回该节点，否则返回nulll
  8. public static HeroNode findLastIndexNode(HeroNode head, int index) {
  9.    //判断如果链表为空，返回null
  10.    if(head.next == null) {
  11.       return null;//没有找到
  12.    }
  13.    //第一个遍历得到链表的长度(节点个数)
  14.    int size = getLength(head);
  15.    //第二次遍历  size-index 位置，就是我们倒数的第K个节点
  16.    //先做一个index的校验
  17.    if(index <=0 || index > size) {
  18.       return null; 
  19.    }
  20.    //定义给辅助变量， for 循环定位到倒数的index
  21.    HeroNode cur = head.next; //3 // 3 - 1 = 2
  22.    for(int i =0; i< size - index; i++) {
  23.       cur = cur.next;
  24.    }
  25.    return cur;
  26. }


  • Java数据结构与算法-尚硅谷 - 图6

    单链表反转：

    1. public static void reversetList(HeroNode head) {
    2. //如果当前链表为空，或者只有一个节点，无需反转，直接返回
    3. if(head.next == null || head.next.next == null) {
    4.    return ;
    5. }
    7. //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
    8. HeroNode cur = head.next;
    9. HeroNode next = null;// 指向当前节点[cur]的下一个节点
    10. HeroNode reverseHead = new HeroNode(0, "", "");
    11. //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
    13. while(cur != null) { 
    14.    next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
    15.    cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的头节点的下一个
    16.    reverseHead.next = cur; //将cur 连接到新的链表上
    17.    cur = next;//让cur后移
    18. }
    19. //将head.next 指向 reverseHead.next , 实现单链表的反转
    20. head.next = reverseHead.next;
    21. }

合并两个有序列表：

  1. //合并两个有序链表
  2.     public static void combineList(HeroNode l1,HeroNode l2){
  3.         HeroNode preHead = new HeroNode(-1,"","");
  5.         HeroNode cur = preHead;
  6.         while (l1 != null && l2 != null){
  7.             if (l1.no <= l2.no){
  8.                 cur.next = l1;
  9.                 l1 = l1.next;
  10.             } else {
  11.                 cur.next = l2;
  12.                 l2 = l2.next;
  13.             }
  14.             cur = cur.next;
  15.         }
  16.         cur.next = l1 == null ? l2 : l1;
  17.     }

2.2 双向链表


  • Java数据结构与算法-尚硅谷 - 图7

    思路：

定义：

  1. // 定义HeroNode2 ， 每个HeroNode 对象就是一个节点
  2. class HeroNode2 {
  3.    public int no;
  4.    public String name;
  5.    public String nickname;
  6.    public HeroNode2 next; // 指向下一个节点, 默认为null
  7.    public HeroNode2 pre; // 指向前一个节点, 默认为null
  8.    // 构造器
  10.    public HeroNode2(int no, String name, String nickname) {
  11.       this.no = no;
  12.       this.name = name;
  13.       this.nickname = nickname;
  14.    }
  16.    // 为了显示方法，我们重新toString
  17.    @Override
  18.    public String toString() {
  19.       return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
  20.    }
  21. }

尾部直接添加：

  1. // 添加一个节点到双向链表的最后.
  2. public void add(HeroNode2 heroNode) {
  4.    // 因为head节点不能动，因此我们需要一个辅助遍历 temp
  5.    HeroNode2 temp = head;
  6.    // 遍历链表，找到最后
  7.    while (true) {
  8.       // 找到链表的最后
  9.       if (temp.next == null) {//
  10.          break;
  11.       }
  12.       // 如果没有找到最后, 将将temp后移
  13.       temp = temp.next;
  14.    }
  15.    // 当退出while循环时，temp就指向了链表的最后
  16.    // 形成一个双向链表
  17.    temp.next = heroNode;
  18.    heroNode.pre = temp;
  19. }

按照编号顺序添加：

  1. //有序加入
  2. public void addByOrder(Node2 node2) {
  3.     Node2 temp = head;
  4.     boolean flag = false;
  5.     while (true) {
  6.         if (temp.next == null) {
  7.             break;
  8.         }
  9.         if (temp.next.no > node2.no) {
  10.             break;
  11.         } else if (temp.next.no == node2.no) {
  12.             flag = true;
  13.             break;
  14.         }
  15.         temp = temp.next;
  16.     }
  17.     if (flag == true) {
  18.         System.out.println("已存在" + node2.no);
  19.     } else {
  20.         node2.next = temp.next;
  21.         if (temp.next != null) {
  22.             temp.next.pre = node2;
  23.         }
  24.         temp.next = node2;
  25.         node2.pre = temp;
  26.     }
  27. }

修改节点：

  1. // 修改一个节点的内容, 可以看到双向链表的节点内容修改和单向链表一样
  2. // 只是 节点类型改成 HeroNode2
  3. public void update(HeroNode2 newHeroNode) {
  4.    // 判断是否空
  5.    if (head.next == null) {
  6.       System.out.println("链表为空~");
  7.       return;
  8.    }
  9.    // 找到需要修改的节点, 根据no编号
  10.    // 定义一个辅助变量
  11.    HeroNode2 temp = head.next;
  12.    boolean flag = false; // 表示是否找到该节点
  13.    while (true) {
  14.       if (temp == null) {
  15.          break; // 已经遍历完链表
  16.       }
  17.       if (temp.no == newHeroNode.no) {
  18.          // 找到
  19.          flag = true;
  20.          break;
  21.       }
  22.       temp = temp.next;
  23.    }
  24.    // 根据flag 判断是否找到要修改的节点
  25.    if (flag) {
  26.       temp.name = newHeroNode.name;
  27.       temp.nickname = newHeroNode.nickname;
  28.    } else { // 没有找到
  29.       System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
  30.    }
  31. }

删除节点：

  1. // 从双向链表中删除一个节点,
  2.    // 说明
  3.    // 1 对于双向链表，我们可以直接找到要删除的这个节点
  4.    // 2 找到后，自我删除即可
  5.    public void del(int no) {
  7.       // 判断当前链表是否为空
  8.       if (head.next == null) {// 空链表
  9.          System.out.println("链表为空，无法删除");
  10.          return;
  11.       }
  13.       HeroNode2 temp = head.next; // 辅助变量(指针)
  14.       boolean flag = false; // 标志是否找到待删除节点的
  15.       while (true) {
  16.          if (temp == null) { // 已经到链表的最后
  17.             break;
  18.          }
  19.          if (temp.no == no) {
  20.             // 找到的待删除节点的前一个节点temp
  21.             flag = true;
  22.             break;
  23.          }
  24.          temp = temp.next; // temp后移，遍历
  25.       }
  26.       // 判断flag
  27.       if (flag) { // 找到
  28.          // 可以删除
  29.          // temp.next = temp.next.next;[单向链表]
  30.          temp.pre.next = temp.next;
  31.          // 这里我们的代码有问题?
  32.          // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
  33.          if (temp.next != null) {
  34.             temp.next.pre = temp.pre;
  35.          }
  36.       } else {
  37.          System.out.printf("要删除的 %d 节点不存在\n", no);
  38.       }
  39.    }
  40. }

2.3 单向环形链表


  • Java数据结构与算法-尚硅谷 - 图8
    Java数据结构与算法-尚硅谷 - 图9

    思路：

    代码实现：

    ```java // 创建一个环形的单向链表 class CircleSingleLinkedList { // 创建一个first节点,当前没有编号 private Boy first = null;

    // 添加小孩节点，构建成一个环形的链表 public void addBoy(int nums) { // nums 做一个数据校验 if (nums < 1) {

    1.   System.out.println("nums的值不正确");
    2.   return;

    } Boy curBoy = null; // 辅助指针，帮助构建环形链表 // 使用for来创建我们的环形链表 for (int i = 1; i <= nums; i++) {

    1.   // 根据编号，创建小孩节点
    2.   Boy boy = new Boy(i);
    3.   // 如果是第一个小孩
    4.   if (i == 1) {
    5.      first = boy;
    6.      first.setNext(first); // 构成环
    7.      curBoy = first; // 让curBoy指向第一个小孩
    8.   } else {
    9.      curBoy.setNext(boy);//
    10.      boy.setNext(first);//
    11.      curBoy = boy;
    12.   }

    } }

    // 遍历当前的环形链表 public void showBoy() { // 判断链表是否为空 if (first == null) {

    1.   System.out.println("没有任何小孩~~");
    2.   return;

    } // 因为first不能动，因此我们仍然使用一个辅助指针完成遍历 Boy curBoy = first; while (true) {

    1.   System.out.printf("小孩的编号 %d \n", curBoy.getNo());
    2.   if (curBoy.getNext() == first) {// 说明已经遍历完毕
    3.      break;
    4.   }
    5.   curBoy = curBoy.getNext(); // curBoy后移

    } }

    // 根据用户的输入，计算出小孩出圈的顺序 /**

    • @param startNo
    • 表示从第几个小孩开始数数
    • @param countNum
    • 表示数几下
    • @param nums

    • 表示最初有多少小孩在圈中 */ public void countBoy(int startNo, int countNum, int nums) { // 先对数据进行校验 if (first == null || startNo < 1 || startNo > nums) { System.out.println(“参数输入有误， 请重新输入”); return; } // 创建要给辅助指针,帮助完成小孩出圈 Boy helper = first; // 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点 while (true) { if (helper.getNext() == first) { // 说明helper指向最后小孩节点 break; } helper = helper.getNext(); } //小孩报数前，先让 first 和 helper 移动 k - 1次 for(int j = 0; j < startNo - 1; j++) { first = first.getNext(); helper = helper.getNext(); } //当小孩报数时，让first 和 helper 指针同时 的移动 m - 1 次, 然后出圈 //这里是一个循环操作，知道圈中只有一个节点 while(true) { if(helper == first) { //说明圈中只有一个节点 break; } //让 first 和 helper 指针同时 的移动 countNum - 1 for(int j = 0; j < countNum - 1; j++) { first = first.getNext(); helper = helper.getNext(); } //这时first指向的节点，就是要出圈的小孩节点 System.out.printf(“小孩%d出圈\n”, first.getNo()); //这时将first指向的小孩节点出圈 first = first.getNext(); helper.setNext(first); //

      } System.out.printf(“最后留在圈中的小孩编号%d \n”, first.getNo());
      } }

// 创建一个Boy类，表示一个节点 class Boy { private int no;// 编号 private Boy next; // 指向下一个节点,默认null

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

public int getNo() { return no; }

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

public Boy getNext() { return next; }

public void setNext(Boy next) { this.next = next; } }

  2. <a name="36171e05"></a>
  3. # 3 栈
  4. <a name="69bbae1c"></a>
  5. ## 3.1 基本介绍
  7. -  栈的英文为(stack) 
  8. -  栈是一个先入后出的有序列表 
  9. -  )栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom) 
  10. -  根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除<br />![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-07-04%2023.10.46.jpg#id=gLKcs&originHeight=404&originWidth=1914&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=) 
  12. <a name="eff30928"></a>
  13. ## 3.2 应用场景
  15. 1. 子程序的调用：在跳往子程序前，先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中
  17. 2. 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中
  18. 3. 表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)
  19. 4. 二叉树的遍历
  20. 5. 图形的深度优先搜索法
  22. <a name="35b5beaf"></a>
  23. ## 3.3 数组模拟栈
  24. ![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-07-04%2023.15.25.jpg#id=KwymL&originHeight=948&originWidth=1914&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=)
  26. ```java
  27. public class ArrayStackDemo {
  29.     public static void main(String[] args) {
  30.         //测试一下ArrayStack 是否正确
  31.         //先创建一个ArrayStack对象->表示栈
  32.         ArrayStack stack = new ArrayStack(4);
  33.         String key = "";
  34.         boolean loop = true; //控制是否退出菜单
  35.         Scanner scanner = new Scanner(System.in);
  37.         while (loop) {
  38.             System.out.println("show: 表示显示栈");
  39.             System.out.println("exit: 退出程序");
  40.             System.out.println("push: 表示添加数据到栈(入栈)");
  41.             System.out.println("pop: 表示从栈取出数据(出栈)");
  42.             System.out.println("请输入你的选择");
  43.             key = scanner.next();
  44.             switch (key) {
  45.                 case "show":
  46.                     stack.list();
  47.                     break;
  48.                 case "push":
  49.                     System.out.println("请输入一个数");
  50.                     int value = scanner.nextInt();
  51.                     stack.push(value);
  52.                     break;
  53.                 case "pop":
  54.                     try {
  55.                         int res = stack.pop();
  56.                         System.out.printf("出栈的数据是 %d\n", res);
  57.                     } catch (Exception e) {
  58.                         // TODO: handle exception
  59.                         System.out.println(e.getMessage());
  60.                     }
  61.                     break;
  62.                 case "exit":
  63.                     scanner.close();
  64.                     loop = false;
  65.                     break;
  66.                 default:
  67.                     break;
  68.             }
  69.         }
  71.         System.out.println("程序退出~~~");
  72.     }
  74. }
  76. //定义一个 ArrayStack 表示栈
  77. class ArrayStack {
  78.     private int maxSize; // 栈的大小
  79.     private int[] stack; // 数组，数组模拟栈，数据就放在该数组
  80.     private int top = -1;// top表示栈顶，初始化为-1
  82.     //构造器
  83.     public ArrayStack(int maxSize) {
  84.         this.maxSize = maxSize;
  85.         stack = new int[this.maxSize];
  86.     }
  88.     //栈满
  89.     public boolean isFull() {
  90.         return top == maxSize - 1;
  91.     }
  93.     //栈空
  94.     public boolean isEmpty() {
  95.         return top == -1;
  96.     }
  98.     //入栈-push
  99.     public void push(int value) {
  100.         //先判断栈是否满
  101.         if (isFull()) {
  102.             System.out.println("栈满");
  103.             return;
  104.         }
  105.         top++;
  106.         stack[top] = value;
  107.     }
  109.     //出栈-pop, 将栈顶的数据返回
  110.     public int pop() {
  111.         //先判断栈是否空
  112.         if (isEmpty()) {
  113.             //抛出异常
  114.             throw new RuntimeException("栈空，没有数据~");
  115.         }
  116.         int value = stack[top];
  117.         top--;
  118.         return value;
  119.     }
  121.     //显示栈的情况[遍历栈]， 遍历时，需要从栈顶开始显示数据
  122.     public void list() {
  123.         if (isEmpty()) {
  124.             System.out.println("栈空，没有数据~~");
  125.             return;
  126.         }
  127.         //需要从栈顶开始显示数据
  128.         for (int i = top; i >= 0; i--) {
  129.             System.out.printf("stack[%d]=%d\n", i, stack[i]);
  130.         }
  131.     }
  132. }

3.4 中缀表达式

Java数据结构与算法-尚硅谷 - 图10

  1. public class Calculator {
  3.     public static void main(String[] args) {
  4.         //完成表达式的运算
  5.         String expression = "7*2*2-5+1-5+3-4"; // 15//如何处理多位数的问题？
  6.         //创建两个栈，数栈，一个符号栈
  7.         ArrayStack2 numStack = new ArrayStack2(10);
  8.         ArrayStack2 operStack = new ArrayStack2(10);
  9.         //定义需要的相关变量
  10.         int index = 0;//用于扫描
  11.         int num1 = 0;
  12.         int num2 = 0;
  13.         int oper = 0;
  14.         int res = 0;
  15.         char ch = ' '; //将每次扫描得到char保存到ch
  16.         String keepNum = ""; //用于拼接 多位数
  17.         //开始while循环的扫描expression
  18.         while (true) {
  19.             //依次得到expression 的每一个字符
  20.             ch = expression.substring(index, index + 1).charAt(0);
  21.             //判断ch是什么，然后做相应的处理
  22.             if (operStack.isOper(ch)) {//如果是运算符
  23.                 //判断当前的符号栈是否为空
  24.                 if (!operStack.isEmpty()) {
  25.                     //如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop出两个数,
  26.                     //在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈
  27.                     if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
  28.                         num1 = numStack.pop();
  29.                         num2 = numStack.pop();
  30.                         oper = operStack.pop();
  31.                         res = numStack.cal(num1, num2, oper);
  32.                         //把运算的结果如数栈
  33.                         numStack.push(res);
  34.                         //然后将当前的操作符入符号栈
  35.                         operStack.push(ch);
  36.                     } else {
  37.                         //如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.
  38.                         operStack.push(ch);
  39.                     }
  40.                 } else {
  41.                     //如果为空直接入符号栈..
  42.                     operStack.push(ch); // 1 + 3
  43.                 }
  44.             } else { //如果是数，则直接入数栈
  46.                 //numStack.push(ch - 48); //? "1+3" '1' => 1
  47.                 //分析思路
  48.                 //1. 当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
  49.                 //2. 在处理数，需要向expression的表达式的index 后再看一位,如果是数就进行扫描，如果是符号才入栈
  50.                 //3. 因此我们需要定义一个变量 字符串，用于拼接
  52.                 //处理多位数
  53.                 keepNum += ch;
  55.                 //如果ch已经是expression的最后一位，就直接入栈
  56.                 if (index == expression.length() - 1) {
  57.                     numStack.push(Integer.parseInt(keepNum));
  58.                 } else {
  60.                     //判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈
  61.                     //注意是看后一位，不是index++
  62.                     if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
  63.                         //如果后一位是运算符，则入栈 keepNum = "1" 或者 "123"
  64.                         numStack.push(Integer.parseInt(keepNum));
  65.                         //重要的!!!!!!, keepNum清空
  66.                         keepNum = "";
  68.                     }
  69.                 }
  70.             }
  71.             //让index + 1, 并判断是否扫描到expression最后.
  72.             index++;
  73.             if (index >= expression.length()) {
  74.                 break;
  75.             }
  76.         }
  78.         //当表达式扫描完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行.
  79.         while (true) {
  80.             //如果符号栈为空，则计算到最后的结果, 数栈中只有一个数字【结果】
  81.             if (operStack.isEmpty()) {
  82.                 break;
  83.             }
  84.             num1 = numStack.pop();
  85.             num2 = numStack.pop();
  86.             oper = operStack.pop();
  87.             res = numStack.cal(num1, num2, oper);
  88.             numStack.push(res);//入栈
  89.         }
  90.         //将数栈的最后数，pop出，就是结果
  91.         int res2 = numStack.pop();
  92.         System.out.printf("表达式 %s = %d", expression, res2);
  93.     }
  95. }
  97. //先创建一个栈,直接使用前面创建好
  98. //定义一个 ArrayStack2 表示栈, 需要扩展功能
  99. class ArrayStack2 {
  100.     private int maxSize; // 栈的大小
  101.     private int[] stack; // 数组，数组模拟栈，数据就放在该数组
  102.     private int top = -1;// top表示栈顶，初始化为-1
  104.     //构造器
  105.     public ArrayStack2(int maxSize) {
  106.         this.maxSize = maxSize;
  107.         stack = new int[this.maxSize];
  108.     }
  110.     //增加一个方法，可以返回当前栈顶的值, 但是不是真正的pop
  111.     public int peek() {
  112.         return stack[top];
  113.     }
  115.     //栈满
  116.     public boolean isFull() {
  117.         return top == maxSize - 1;
  118.     }
  120.     //栈空
  121.     public boolean isEmpty() {
  122.         return top == -1;
  123.     }
  125.     //入栈-push
  126.     public void push(int value) {
  127.         //先判断栈是否满
  128.         if (isFull()) {
  129.             System.out.println("栈满");
  130.             return;
  131.         }
  132.         top++;
  133.         stack[top] = value;
  134.     }
  136.     //出栈-pop, 将栈顶的数据返回
  137.     public int pop() {
  138.         //先判断栈是否空
  139.         if (isEmpty()) {
  140.             //抛出异常
  141.             throw new RuntimeException("栈空，没有数据~");
  142.         }
  143.         int value = stack[top];
  144.         top--;
  145.         return value;
  146.     }
  148.     //显示栈的情况[遍历栈]， 遍历时，需要从栈顶开始显示数据
  149.     public void list() {
  150.         if (isEmpty()) {
  151.             System.out.println("栈空，没有数据~~");
  152.             return;
  153.         }
  154.         //需要从栈顶开始显示数据
  155.         for (int i = top; i >= 0; i--) {
  156.             System.out.printf("stack[%d]=%d\n", i, stack[i]);
  157.         }
  158.     }
  160.     //返回运算符的优先级，优先级是程序员来确定, 优先级使用数字表示
  161.     //数字越大，则优先级就越高.
  162.     public int priority(int oper) {
  163.         if (oper == '*' || oper == '/') {
  164.             return 1;
  165.         } else if (oper == '+' || oper == '-') {
  166.             return 0;
  167.         } else {
  168.             return -1; // 假定目前的表达式只有 +, - , * , /
  169.         }
  170.     }
  172.     //判断是不是一个运算符
  173.     public boolean isOper(char val) {
  174.         return val == '+' || val == '-' || val == '*' || val == '/';
  175.     }
  177.     //计算方法
  178.     public int cal(int num1, int num2, int oper) {
  179.         int res = 0; // res 用于存放计算的结果
  180.         switch (oper) {
  181.             case '+':
  182.                 res = num1 + num2;
  183.                 break;
  184.             case '-':
  185.                 res = num2 - num1;// 注意顺序
  186.                 break;
  187.             case '*':
  188.                 res = num1 * num2;
  189.                 break;
  190.             case '/':
  191.                 res = num2 / num1;
  192.                 break;
  193.             default:
  194.                 break;
  195.         }
  196.         return res;
  197.     }
  198. }

3.5 中缀——>后缀表达式

Java数据结构与算法-尚硅谷 - 图11

  1. public class PolandNotation {
  3.     public static void main(String[] args) {
  4.         //完成将一个中缀表达式转成后缀表达式的功能
  5.         //说明
  6.         //1. 1+((2+3)×4)-5 => 转成  1 2 3 + 4 × + 5 –
  7.         //2. 因为直接对str 进行操作，不方便，因此 先将  "1+((2+3)×4)-5" =》 中缀的表达式对应的List
  8.         //   即 "1+((2+3)×4)-5" => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
  9.         //3. 将得到的中缀表达式对应的List => 后缀表达式对应的List
  10.         //   即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]  =》 ArrayList [1,2,3,+,4,*,+,5,–]
  12.         String expression = "1+((2+3)*4)-5";//注意表达式 
  13.         List<String> infixExpressionList = toInfixExpressionList(expression);
  14.         System.out.println("中缀表达式对应的List=" + infixExpressionList); // ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
  15.         List<String> suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);
  16.         System.out.println("后缀表达式对应的List" + suffixExpreesionList); //ArrayList [1,2,3,+,4,*,+,5,–] 
  18.         System.out.printf("expression=%d", calculate(suffixExpreesionList)); // ?
  22.         /*
  24.         //先定义给逆波兰表达式
  25.         //(30+4)×5-6  => 30 4 + 5 × 6 - => 164
  26.         // 4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / + 
  27.         //测试 
  28.         //说明为了方便，逆波兰表达式 的数字和符号使用空格隔开
  29.         //String suffixExpression = "30 4 + 5 * 6 -";
  30.         String suffixExpression = "4 5 * 8 - 60 + 8 2 / +"; // 76
  31.         //思路
  32.         //1. 先将 "3 4 + 5 × 6 - " => 放到ArrayList中
  33.         //2. 将 ArrayList 传递给一个方法，遍历 ArrayList 配合栈 完成计算
  35.         List<String> list = getListString(suffixExpression);
  36.         System.out.println("rpnList=" + list);
  37.         int res = calculate(list);
  38.         System.out.println("计算的结果是=" + res);
  40.         */
  41.     }
  44.     //即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]  =》 ArrayList [1,2,3,+,4,*,+,5,–]
  45.     //方法：将得到的中缀表达式对应的List => 后缀表达式对应的List
  46.     public static List<String> parseSuffixExpreesionList(List<String> ls) {
  47.         //定义两个栈
  48.         Stack<String> s1 = new Stack<String>(); // 符号栈
  49.         //说明：因为s2 这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
  50.         //因此比较麻烦，这里我们就不用 Stack<String> 直接使用 List<String> s2
  51.         //Stack<String> s2 = new Stack<String>(); // 储存中间结果的栈s2
  52.         List<String> s2 = new ArrayList<String>(); // 储存中间结果的Lists2
  54.         //遍历ls
  55.         for (String item : ls) {
  56.             //如果是一个数，加入s2
  57.             if (item.matches("\\d+")) {
  58.                 s2.add(item);
  59.             } else if (item.equals("(")) {
  60.                 s1.push(item);
  61.             } else if (item.equals(")")) {
  62.                 //如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
  63.                 while (!s1.peek().equals("(")) {
  64.                     s2.add(s1.pop());
  65.                 }
  66.                 s1.pop();//!!! 将 ( 弹出 s1栈， 消除小括号
  67.             } else {
  68.                 //当item的优先级小于等于s1栈顶运算符, 将s1栈顶的运算符弹出并加入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较
  69.                 //问题：我们缺少一个比较优先级高低的方法
  70.                 while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
  71.                     s2.add(s1.pop());
  72.                 }
  73.                 //还需要将item压入栈
  74.                 s1.push(item);
  75.             }
  76.         }
  78.         //将s1中剩余的运算符依次弹出并加入s2
  79.         while (s1.size() != 0) {
  80.             s2.add(s1.pop());
  81.         }
  82.         return s2; //注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List
  83.     }
  85.     //方法：将 中缀表达式转成对应的List
  86.     //  s="1+((2+3)×4)-5";
  87.     public static List<String> toInfixExpressionList(String s) {
  88.         //定义一个List,存放中缀表达式 对应的内容
  89.         List<String> ls = new ArrayList<String>();
  90.         int i = 0; //这时是一个指针，用于遍历 中缀表达式字符串
  91.         String str; // 对多位数的拼接
  92.         char c; // 每遍历到一个字符，就放入到c
  93.         do {
  94.             //如果c是一个非数字，我需要加入到ls
  95.             if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
  96.                 ls.add("" + c);
  97.                 i++; //i需要后移
  98.             } else { //如果是一个数，需要考虑多位数
  99.                 str = ""; //先将str 置成"" '0'[48]->'9'[57]
  100.                 while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
  101.                     str += c;//拼接
  102.                     i++;
  103.                 }
  104.                 ls.add(str);
  105.             }
  106.         } while (i < s.length());
  107.         return ls;//返回
  108.     }
  110.     //将一个逆波兰表达式， 依次将数据和运算符 放入到 ArrayList中
  111.     public static List<String> getListString(String suffixExpression) {
  112.         //将 suffixExpression 分割
  113.         String[] split = suffixExpression.split(" ");
  114.         List<String> list = new ArrayList<String>();
  115.         for (String ele : split) {
  116.             list.add(ele);
  117.         }
  118.         return list;
  120.     }
  122.     //完成对逆波兰表达式的运算
  123.     /*
  124.      * 1)从左至右扫描，将3和4压入堆栈；
  125.         2)遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
  126.         3)将5入栈；
  127.         4)接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
  128.         5)将6入栈；
  129.         6)最后是-运算符，计算出35-6的值，即29，由此得出最终结果
  130.      */
  132.     public static int calculate(List<String> ls) {
  133.         // 创建给栈, 只需要一个栈即可
  134.         Stack<String> stack = new Stack<String>();
  135.         // 遍历 ls
  136.         for (String item : ls) {
  137.             // 这里使用正则表达式来取出数
  138.             if (item.matches("\\d+")) { // 匹配的是多位数
  139.                 // 入栈
  140.                 stack.push(item);
  141.             } else {
  142.                 // pop出两个数，并运算， 再入栈
  143.                 int num2 = Integer.parseInt(stack.pop());
  144.                 int num1 = Integer.parseInt(stack.pop());
  145.                 int res = 0;
  146.                 if (item.equals("+")) {
  147.                     res = num1 + num2;
  148.                 } else if (item.equals("-")) {
  149.                     res = num1 - num2;
  150.                 } else if (item.equals("*")) {
  151.                     res = num1 * num2;
  152.                 } else if (item.equals("/")) {
  153.                     res = num1 / num2;
  154.                 } else {
  155.                     throw new RuntimeException("运算符有误");
  156.                 }
  157.                 //把res 入栈
  158.                 stack.push("" + res);
  159.             }
  161.         }
  162.         //最后留在stack中的数据是运算结果
  163.         return Integer.parseInt(stack.pop());
  164.     }
  165. }
  167. //编写一个类 Operation 可以返回一个运算符 对应的优先级
  168. class Operation {
  169.     private static int ADD = 1;
  170.     private static int SUB = 1;
  171.     private static int MUL = 2;
  172.     private static int DIV = 2;
  174.     //写一个方法，返回对应的优先级数字
  175.     public static int getValue(String operation) {
  176.         int result = 0;
  177.         switch (operation) {
  178.             case "+":
  179.                 result = ADD;
  180.                 break;
  181.             case "-":
  182.                 result = SUB;
  183.                 break;
  184.             case "*":
  185.                 result = MUL;
  186.                 break;
  187.             case "/":
  188.                 result = DIV;
  189.                 break;
  190.             default:
  191.                 System.out.println("不存在该运算符" + operation);
  192.                 break;
  193.         }
  194.         return result;
  195.     }
  196. }

4 递归


  • 递归就是方法自己调用自己,每次调用时传入不同的变量
    Java数据结构与算法-尚硅谷 - 图12

    基本介绍：

迷宫：

  1. public class MiGong {
  3.     public static void main(String[] args) {
  5.         int[][] map = new int[8][7];
  8.         for (int i = 0; i < 7; i++) {
  9.             map[0][i] = 1;
  10.             map[7][i] = 1;
  11.         }
  14.         for (int i = 0; i < 8; i++) {
  15.             map[i][0] = 1;
  16.             map[i][6] = 1;
  17.         }
  19.         map[3][1] = 1;
  20.         map[3][2] = 1;
  21. //        map[1][2] = 1;
  22. //        map[2][2] = 1;
  25.         System.out.println("地图");
  26.         for (int i = 0; i < 8; i++) {
  27.             for (int j = 0; j < 7; j++) {
  28.                 System.out.print(map[i][j] + " ");
  29.             }
  30.             System.out.println();
  31.         }
  33.         //setWay(map, 1, 1);
  34.         setWay2(map, 1, 1);
  37.         System.out.println("路径");
  38.         for (int i = 0; i < 8; i++) {
  39.             for (int j = 0; j < 7; j++) {
  40.                 System.out.print(map[i][j] + " ");
  41.             }
  42.             System.out.println();
  43.         }
  44.     }
  46.     public static boolean setWay(int[][] map, int i, int j) {
  47.         if (map[6][5] == 2) { 
  48.             return true;
  49.         } else {
  50.             if (map[i][j] == 0) { 
  52.                 map[i][j] = 2; 
  53.                 if (setWay(map, i + 1, j)) {
  54.                     return true;
  55.                 } else if (setWay(map, i, j + 1)) { 
  56.                     return true;
  57.                 } else if (setWay(map, i - 1, j)) { 
  58.                     return true;
  59.                 } else if (setWay(map, i, j - 1)) { 
  60.                     return true;
  61.                 } else {
  62.                     map[i][j] = 3;
  63.                     return false;
  64.                 }
  65.             } else { 
  66.                 return false;
  67.             }
  68.         }
  69.     }
  71.     public static boolean setWay2(int[][] map, int i, int j) {
  72.         if (map[6][5] == 2) { 
  73.             return true;
  74.         } else {
  75.             if (map[i][j] == 0) { 
  77.                 map[i][j] = 2; 
  78.                 if (setWay2(map, i - 1, j)) {
  79.                     return true;
  80.                 } else if (setWay2(map, i, j + 1)) { 
  81.                     return true;
  82.                 } else if (setWay2(map, i + 1, j)) { 
  83.                     return true;
  84.                 } else if (setWay2(map, i, j - 1)) { 
  85.                     return true;
  86.                 } else {
  87.                     map[i][j] = 3;
  88.                     return false;
  89.                 }
  90.             } else { 
  91.                 return false;
  92.             }
  93.         }
  94.     }
  95. }


  • Java数据结构与算法-尚硅谷 - 图13

    八皇后：

    ```java public class Queue8 {

    //定义一个max表示共有多少个皇后 int max = 8; //定义数组array, 保存皇后放置位置的结果,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3} int[] array = new int[max]; static int count = 0; static int judgeCount = 0; public static void main(String[] args) { //测试一把 ， 8皇后是否正确 Queue8 queue8 = new Queue8(); queue8.check(0); System.out.printf(“一共有%d解法”, count); System.out.printf(“一共判断冲突的次数%d次”, judgeCount); // 1.5w

    }

//编写一个方法，放置第n个皇后 //特别注意： check 是 每一次递归时，进入到check中都有 for(int i = 0; i < max; i++)，因此会有回溯 private void check(int n) { if(n == max) { //n = 8 , 其实8个皇后就既然放好 print(); return; }

  1.   //依次放入皇后，并判断是否冲突
  2.   for(int i = 0; i < max; i++) {
  3.      //先把当前这个皇后 n , 放到该行的第1列
  4.      array[n] = i;
  5.      //判断当放置第n个皇后到i列时，是否冲突
  6.      if(judge(n)) { // 不冲突
  7.         //接着放n+1个皇后,即开始递归
  8.         check(n+1); //  
  9.      }
  10.      //如果冲突，就继续执行 array[n] = i; 即将第n个皇后，放置在本行得 后移的一个位置
  11.   }

}

//查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突 /**

  1. * 
  2. * @param n 表示第n个皇后
  3. * @return
  4. */

private boolean judge(int n) { judgeCount++; for(int i = 0; i < n; i++) { // 说明 //1. array[i] == array[n] 表示判断 第n个皇后是否和前面的n-1个皇后在同一列 //2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线 // n = 1 放置第 2列 1 n = 1 array[1] = 1 // Math.abs(1-0) == 1 Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1 //3. 判断是否在同一行, 没有必要，n 每次都在递增 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 i = 0; i < array.length; i++) { System.out.print(array[i] + “ “); } System.out.println(); } }

  3. <a name="83409528"></a>
  4. # 5 排序
  6. -  排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程 
  7. <a name="568dc93e-5"></a>
  8. #### 基本介绍：
  10. -  <br />![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-07-09%2021.36.19.jpg#id=QYbqt&originHeight=624&originWidth=952&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=)<br />![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-07-09%2021.37.29.jpg#id=gWXNX&originHeight=724&originWidth=1108&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=) 
  11. <a name="1141ec49"></a>
  12. #### 常见排序：
  14. <a name="df35f26f"></a>
  15. ## 5.1 冒泡排序
  16. 思路：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部<br />![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-07-09%2021.42.03.jpg#id=KkuYh&originHeight=1078&originWidth=1782&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=)
  18. ```java
  19. // 将前面额冒泡排序算法，封装成一个方法
  20.     public static void bubbleSort(int[] arr) {
  21.         // 冒泡排序 的时间复杂度 O(n^2), 自己写出
  22.         int temp = 0; // 临时变量
  23.         boolean flag = false; // 标识变量，表示是否进行过交换
  24.         for (int i = 0; i < arr.length - 1; i++) {
  26.             for (int j = 0; j < arr.length - 1 - i; j++) {
  27.                 // 如果前面的数比后面的数大，则交换
  28.                 if (arr[j] > arr[j + 1]) {
  29.                     flag = true;
  30.                     temp = arr[j];
  31.                     arr[j] = arr[j + 1];
  32.                     arr[j + 1] = temp;
  33.                 }
  34.             }
  35.             //System.out.println("第" + (i + 1) + "趟排序后的数组");
  36.             //System.out.println(Arrays.toString(arr));
  38.             if (!flag) { // 在一趟排序中，一次交换都没有发生过
  39.                 break;
  40.             } else {
  41.                 flag = false; // 重置flag!!!, 进行下次判断
  42.             }
  43.         }
  44.     }

5.2 选择排序

思路：
第一次从arr[0]~arr[n-1]中选取最小值，与 arr[0]交换，

第二次从 arr[1]~arr[n-1]中选取最小值，与 arr[1]交换，

第三次从 arr[2]~arr[n-1]中选取最小值，与arr[2]交换，…

第 i 次从 arr[i-1]~arr[n-1]中选取最小值，与 arr[i-1]交换，…,

第 n-1 次从 arr[n-2]~arr[n-1]中选取最小值，与 arr[n-2]交换，总

共通过 n-1 次，得到一个按排序码从小到大排列的有序序列

Java数据结构与算法-尚硅谷 - 图14

  1. //选择排序
  2.     public static void selectSort(int[] arr) {
  5.         //在推导的过程，我们发现了规律，因此，可以使用for来解决
  6.         //选择排序时间复杂度是 O(n^2)
  7.         for (int i = 0; i < arr.length - 1; i++) {
  8.             int minIndex = i;
  9.             int min = arr[i];
  10.             for (int j = i + 1; j < arr.length; j++) {
  11.                 if (min > arr[j]) { // 说明假定的最小值，并不是最小
  12.                     min = arr[j]; // 重置min
  13.                     minIndex = j; // 重置minIndex
  14.                 }
  15.             }
  17.             // 将最小值，放在arr[0], 即交换
  18.             if (minIndex != i) {
  19.                 arr[minIndex] = arr[i];
  20.                 arr[i] = min;
  21.             }
  23.             //System.out.println("第"+(i+1)+"轮后~~");
  24.             //System.out.println(Arrays.toString(arr));// 1, 34, 119, 101
  25.         }

5.3 插入排序

思路：把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表
Java数据结构与算法-尚硅谷 - 图15

  1. //插入排序
  2.     public static void insertSort(int[] arr) {
  3.         int insertVal = 0;
  4.         int insertIndex = 0;
  5.         //使用for循环来把代码简化
  6.         for(int i = 1; i < arr.length; i++) {
  7.             //定义待插入的数
  8.             insertVal = arr[i];
  9.             insertIndex = i - 1; // 即arr[1]的前面这个数的下标
  11.             // 给insertVal 找到插入的位置
  12.             // 说明
  13.             // 1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界
  14.             // 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
  15.             // 3. 就需要将 arr[insertIndex] 后移
  16.             while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
  17.                 arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
  18.                 insertIndex--;
  19.             }
  20.             // 当退出while循环时，说明插入的位置找到, insertIndex + 1
  21.             // 举例：理解不了，我们一会 debug
  22.             //这里我们判断是否需要赋值
  23.             if(insertIndex + 1 != i) {
  24.                 arr[insertIndex + 1] = insertVal;
  25.             }
  27.             //System.out.println("第"+i+"轮插入");
  28.             //System.out.println(Arrays.toString(arr));
  29.         }

5.4 希尔排序

思路：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1

Java数据结构与算法-尚硅谷 - 图16

  1. // 希尔排序时， 对有序序列在插入时采用交换法, 
  2.     // 思路(算法) ===> 代码
  3.     public static void shellSort(int[] arr) {
  5.         int temp = 0;
  6.         int count = 0;
  7.         // 根据前面的逐步分析，使用循环处理
  8.         for (int gap = arr.length / 2; gap > 0; gap /= 2) {
  9.             for (int i = gap; i < arr.length; i++) {
  10.                 // 遍历各组中所有的元素(共gap组，每组有个元素), 步长gap
  11.                 for (int j = i - gap; j >= 0; j -= gap) {
  12.                     // 如果当前元素大于加上步长后的那个元素，说明交换
  13.                     if (arr[j] > arr[j + gap]) {
  14.                         temp = arr[j];
  15.                         arr[j] = arr[j + gap];
  16.                         arr[j + gap] = temp;
  17.                     }
  18.                 }
  19.             }
  20.             //System.out.println("希尔排序第" + (++count) + "轮 =" + Arrays.toString(arr));
  21.         }
  22.     }
  24.     //对交换式的希尔排序进行优化->移位法
  25.     public static void shellSort2(int[] arr) {
  27.         // 增量gap, 并逐步的缩小增量
  28.         for (int gap = arr.length / 2; gap > 0; gap /= 2) {
  29.             // 从第gap个元素，逐个对其所在的组进行直接插入排序
  30.             for (int i = gap; i < arr.length; i++) {
  31.                 int j = i;
  32.                 int temp = arr[j];
  33.                 if (arr[j] < arr[j - gap]) {
  34.                     while (j - gap >= 0 && temp < arr[j - gap]) {
  35.                         //移动
  36.                         arr[j] = arr[j-gap];
  37.                         j -= gap;
  38.                     }
  39.                     //当退出while后，就给temp找到插入的位置
  40.                     arr[j] = temp;
  41.                 }
  42.             }
  43.         }
  44.     }

5.5 快速排序

思路：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

Java数据结构与算法-尚硅谷 - 图17

  1. public static void quickSort(int[] arr,int left, int right) {
  3.         int l = left; //左下标
  4.         int r = right; //右下标
  5.         //pivot 中轴值
  6.         int pivot = arr[(left + right) / 2];
  7.         int temp = 0; //临时变量，作为交换时使用
  8.         //while循环的目的是让比pivot 值小放到左边
  9.         //比pivot 值大放到右边
  10.         while( l < r) { 
  11.             //在pivot的左边一直找,找到大于等于pivot值,才退出
  12.             while( arr[l] < pivot) {
  13.                 l += 1;
  14.             }
  15.             //在pivot的右边一直找,找到小于等于pivot值,才退出
  16.             while(arr[r] > pivot) {
  17.                 r -= 1;
  18.             }
  19.             //如果l >= r说明pivot 的左右两的值，已经按照左边全部是
  20.             //小于等于pivot值，右边全部是大于等于pivot值
  21.             if( l >= r) {
  22.                 break;
  23.             }
  25.             //交换
  26.             temp = arr[l];
  27.             arr[l] = arr[r];
  28.             arr[r] = temp;
  30.             //如果交换完后，发现这个arr[l] == pivot值 相等 r--， 前移
  31.             if(arr[l] == pivot) {
  32.                 r -= 1;
  33.             }
  34.             //如果交换完后，发现这个arr[r] == pivot值 相等 l++， 后移
  35.             if(arr[r] == pivot) {
  36.                 l += 1;
  37.             } 
  38.         }
  40.         // 如果 l == r, 必须l++, r--, 否则为出现栈溢出
  41.         if (l == r) {
  42.             l += 1;
  43.             r -= 1;
  44.         }
  45.         //向左递归
  46.         if(left < r) {
  47.             quickSort(arr, left, r);
  48.         }
  49.         //向右递归
  50.         if(right > l) {
  51.             quickSort(arr, l, right);
  52.         }            
  53.     }

5.6 归并排序

Java数据结构与算法-尚硅谷 - 图18

Java数据结构与算法-尚硅谷 - 图19

  1. //分+合方法
  2.     public static void mergeSort(int[] arr, int left, int right, int[] temp) {
  3.         if(left < right) {
  4.             int mid = (left + right) / 2; //中间索引
  5.             //向左递归进行分解
  6.             mergeSort(arr, left, mid, temp);
  7.             //向右递归进行分解
  8.             mergeSort(arr, mid + 1, right, temp);
  9.             //合并
  10.             merge(arr, left, mid, right, temp);
  12.         }
  13.     }
  15.     //合并的方法
  16.     /**
  17.      * 
  18.      * @param arr 排序的原始数组
  19.      * @param left 左边有序序列的初始索引
  20.      * @param mid 中间索引
  21.      * @param right 右边索引
  22.      * @param temp 做中转的数组
  23.      */
  24.     public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
  26.         int i = left; // 初始化i, 左边有序序列的初始索引
  27.         int j = mid + 1; //初始化j, 右边有序序列的初始索引
  28.         int t = 0; // 指向temp数组的当前索引
  30.         //(一)
  31.         //先把左右两边(有序)的数据按照规则填充到temp数组
  32.         //直到左右两边的有序序列，有一边处理完毕为止
  33.         while (i <= mid && j <= right) {//继续
  34.             //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
  35.             //即将左边的当前元素，填充到 temp数组 
  36.             //然后 t++, i++
  37.             if(arr[i] <= arr[j]) {
  38.                 temp[t] = arr[i];
  39.                 t += 1;
  40.                 i += 1;
  41.             } else { //反之,将右边有序序列的当前元素，填充到temp数组
  42.                 temp[t] = arr[j];
  43.                 t += 1;
  44.                 j += 1;
  45.             }
  46.         }
  48.         //(二)
  49.         //把有剩余数据的一边的数据依次全部填充到temp
  50.         while( i <= mid) { //左边的有序序列还有剩余的元素，就全部填充到temp
  51.             temp[t] = arr[i];
  52.             t += 1;
  53.             i += 1;    
  54.         }
  56.         while( j <= right) { //右边的有序序列还有剩余的元素，就全部填充到temp
  57.             temp[t] = arr[j];
  58.             t += 1;
  59.             j += 1;    
  60.         }
  63.         //(三)
  64.         //将temp数组的元素拷贝到arr
  65.         //注意，并不是每次都拷贝所有
  66.         t = 0;
  67.         int tempLeft = left; // 
  68.         //第一次合并 tempLeft = 0 , right = 1 //  tempLeft = 2  right = 3 // tL=0 ri=3
  69.         //最后一次 tempLeft = 0  right = 7
  70.         while(tempLeft <= right) { 
  71.             arr[tempLeft] = temp[t];
  72.             t += 1;
  73.             tempLeft += 1;
  74.         }    
  75.     }

5.7 基数排序

Java数据结构与算法-尚硅谷 - 图20

Java数据结构与算法-尚硅谷 - 图21

  1. public static void radixSort(int[] arr) {
  3.         //根据前面的推导过程，我们可以得到最终的基数排序代码
  5.         //1. 得到数组中最大的数的位数
  6.         int max = arr[0]; //假设第一数就是最大数
  7.         for(int i = 1; i < arr.length; i++) {
  8.             if (arr[i] > max) {
  9.                 max = arr[i];
  10.             }
  11.         }
  12.         //得到最大数是几位数
  13.         int maxLength = (max + "").length();
  16.         //定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
  17.         //说明
  18.         //1. 二维数组包含10个一维数组
  19.         //2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为arr.length
  20.         //3. 名明确，基数排序是使用空间换时间的经典算法
  21.         int[][] bucket = new int[10][arr.length];
  23.         //为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
  24.         //可以这里理解
  25.         //比如：bucketElementCounts[0] , 记录的就是  bucket[0] 桶的放入数据个数
  26.         int[] bucketElementCounts = new int[10];
  29.         //这里我们使用循环将代码处理
  31.         for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) {
  32.             //(针对每个元素的对应位进行排序处理)， 第一次是个位，第二次是十位，第三次是百位..
  33.             for(int j = 0; j < arr.length; j++) {
  34.                 //取出每个元素的对应位的值
  35.                 int digitOfElement = arr[j] / n % 10;
  36.                 //放入到对应的桶中
  37.                 bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
  38.                 bucketElementCounts[digitOfElement]++;
  39.             }
  40.             //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
  41.             int index = 0;
  42.             //遍历每一桶，并将桶中是数据，放入到原数组
  43.             for(int k = 0; k < bucketElementCounts.length; k++) {
  44.                 //如果桶中，有数据，我们才放入到原数组
  45.                 if(bucketElementCounts[k] != 0) {
  46.                     //循环该桶即第k个桶(即第k个一维数组), 放入
  47.                     for(int l = 0; l < bucketElementCounts[k]; l++) {
  48.                         //取出元素放入到arr
  49.                         arr[index++] = bucket[k][l];
  50.                     }
  51.                 }
  52.                 //第i+1轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
  53.                 bucketElementCounts[k] = 0;
  55.             }
  56.             //System.out.println("第"+(i+1)+"轮，对个位的排序处理 arr =" + Arrays.toString(arr));        
  57.         }

5.8 堆排序

Java数据结构与算法-尚硅谷 - 图22

  1. public class HeapSort {
  3.     public static void main(String[] args) {
  4.         //要求将数组进行升序排序
  5.         //int arr[] = {4, 6, 8, 5, 9};
  6.         // 创建要给80000个的随机的数组
  7.         int[] arr = new int[8000000];
  8.         for (int i = 0; i < 8000000; i++) {
  9.             arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
  10.         }
  12.         System.out.println("排序前");
  13.         Date data1 = new Date();
  14.         SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
  15.         String date1Str = simpleDateFormat.format(data1);
  16.         System.out.println("排序前的时间是=" + date1Str);
  18.         heapSort(arr);
  20.         Date data2 = new Date();
  21.         String date2Str = simpleDateFormat.format(data2);
  22.         System.out.println("排序前的时间是=" + date2Str);
  23.         //System.out.println("排序后=" + Arrays.toString(arr));
  24.     }
  26.     //编写一个堆排序的方法
  27.     public static void heapSort(int arr[]) {
  28.         int temp = 0;
  29.         System.out.println("堆排序!!");
  31. //        //分步完成
  32. //        adjustHeap(arr, 1, arr.length);
  33. //        System.out.println("第一次" + Arrays.toString(arr)); // 4, 9, 8, 5, 6
  34. //        
  35. //        adjustHeap(arr, 0, arr.length);
  36. //        System.out.println("第2次" + Arrays.toString(arr)); // 9,6,8,5,4
  38.         //完成我们最终代码
  39.         //将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
  40.         for(int i = arr.length / 2 -1; i >=0; i--) {
  41.             adjustHeap(arr, i, arr.length);
  42.         }
  44.         /*
  45.          * 2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
  46. 　　            3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
  47.          */
  48.         for(int j = arr.length-1;j >0; j--) {
  49.             //交换
  50.             temp = arr[j];
  51.             arr[j] = arr[0];
  52.             arr[0] = temp;
  53.             adjustHeap(arr, 0, j); 
  54.         }
  56.         //System.out.println("数组=" + Arrays.toString(arr)); 
  58.     }
  60.     //将一个数组(二叉树), 调整成一个大顶堆
  61.     /**
  62.      * 功能： 完成 将 以 i 对应的非叶子结点的树调整成大顶堆
  63.      * 举例  int arr[] = {4, 6, 8, 5, 9}; => i = 1 => adjustHeap => 得到 {4, 9, 8, 5, 6}
  64.      * 如果我们再次调用  adjustHeap 传入的是 i = 0 => 得到 {4, 9, 8, 5, 6} => {9,6,8,5, 4}
  65.      * @param arr 待调整的数组
  66.      * @param i 表示非叶子结点在数组中索引
  67.      * @param lenght 表示对多少个元素继续调整， length 是在逐渐的减少
  68.      */
  69.     public  static void adjustHeap(int arr[], int i, int lenght) {
  71.         int temp = arr[i];//先取出当前元素的值，保存在临时变量
  72.         //开始调整
  73.         //说明
  74.         //1. k = i * 2 + 1 k 是 i结点的左子结点
  75.         for(int k = i * 2 + 1; k < lenght; k = k * 2 + 1) {
  76.             if(k+1 < lenght && arr[k] < arr[k+1]) { //说明左子结点的值小于右子结点的值
  77.                 k++; // k 指向右子结点
  78.             }
  79.             if(arr[k] > temp) { //如果子结点大于父结点
  80.                 arr[i] = arr[k]; //把较大的值赋给当前结点
  81.                 i = k; //!!! i 指向 k,继续循环比较
  82.             } else {
  83.                 break;//!
  84.             }
  85.         }
  86.         //当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部)
  87.         arr[i] = temp;//将temp值放到调整后的位置
  88.     }    
  89. }

6 查找

6.1 二分查找

Java数据结构与算法-尚硅谷 - 图23

  1. public static int binarySearch(int[] arr, int left, int right, int findVal) {
  4.         // 当 left > right 时，说明递归整个数组，但是没有找到
  5.         if (left > right) {
  6.             return -1;
  7.         }
  8.         int mid = (left + right) / 2;
  9.         int midVal = arr[mid];
  11.         if (findVal > midVal) { // 向 右递归
  12.             return binarySearch(arr, mid + 1, right, findVal);
  13.         } else if (findVal < midVal) { // 向左递归
  14.             return binarySearch(arr, left, mid - 1, findVal);
  15.         } else {
  17.             return mid;
  18.         }
  20.     }
  22.     //完成一个课后思考题:
  23.     /*
  24.      * 课后思考题： {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，
  25.      * 有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000
  26.      * 
  27.      * 思路分析
  28.      * 1. 在找到mid 索引值，不要马上返回
  29.      * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
  30.      * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
  31.      * 4. 将Arraylist返回
  32.      */
  34.     public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
  36.         System.out.println("hello~");
  37.         // 当 left > right 时，说明递归整个数组，但是没有找到
  38.         if (left > right) {
  39.             return new ArrayList<Integer>();
  40.         }
  41.         int mid = (left + right) / 2;
  42.         int midVal = arr[mid];
  44.         if (findVal > midVal) { // 向 右递归
  45.             return binarySearch2(arr, mid + 1, right, findVal);
  46.         } else if (findVal < midVal) { // 向左递归
  47.             return binarySearch2(arr, left, mid - 1, findVal);
  48.         } else {
  49. //             * 思路分析
  50. //             * 1. 在找到mid 索引值，不要马上返回
  51. //             * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
  52. //             * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
  53. //             * 4. 将Arraylist返回
  55.             List<Integer> resIndexlist = new ArrayList<Integer>();
  56.             //向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
  57.             int temp = mid - 1;
  58.             while(true) {
  59.                 if (temp < 0 || arr[temp] != findVal) {//退出
  60.                     break;
  61.                 }
  62.                 //否则，就temp 放入到 resIndexlist
  63.                 resIndexlist.add(temp);
  64.                 temp -= 1; //temp左移
  65.             }
  66.             resIndexlist.add(mid);  //
  68.             //向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
  69.             temp = mid + 1;
  70.             while(true) {
  71.                 if (temp > arr.length - 1 || arr[temp] != findVal) {//退出
  72.                     break;
  73.                 }
  74.                 //否则，就temp 放入到 resIndexlist
  75.                 resIndexlist.add(temp);
  76.                 temp += 1; //temp右移
  77.             }
  79.             return resIndexlist;
  80.         }
  82.     }

6.2 插值查找

Java数据结构与算法-尚硅谷 - 图24

  1. public static int insertValueSearch(int[] arr, int left, int right, int findVal) { 
  3.         System.out.println("插值查找次数~~");
  5.         //注意：findVal < arr[0]  和  findVal > arr[arr.length - 1] 必须需要
  6.         //否则我们得到的 mid 可能越界
  7.         if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
  8.             return -1;
  9.         }
  11.         // 求出mid, 自适应
  12.         int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
  13.         int midVal = arr[mid];
  14.         if (findVal > midVal) { // 说明应该向右边递归
  15.             return insertValueSearch(arr, mid + 1, right, findVal);
  16.         } else if (findVal < midVal) { // 说明向左递归查找
  17.             return insertValueSearch(arr, left, mid - 1, findVal);
  18.         } else {
  19.             return mid;
  20.         }
  21.     }

6.3 斐波那契查找

Java数据结构与算法-尚硅谷 - 图25

  1. //因为后面我们mid=low+F(k-1)-1，需要使用到斐波那契数列，因此我们需要先获取到一个斐波那契数列
  2.     //非递归方法得到一个斐波那契数列
  3.     public static int[] fib() {
  4.         int[] f = new int[maxSize];
  5.         f[0] = 1;
  6.         f[1] = 1;
  7.         for (int i = 2; i < maxSize; i++) {
  8.             f[i] = f[i - 1] + f[i - 2];
  9.         }
  10.         return f;
  11.     }
  13.     //编写斐波那契查找算法
  14.     //使用非递归的方式编写算法
  15.     /**
  16.      * 
  17.      * @param a  数组
  18.      * @param key 我们需要查找的关键码(值)
  19.      * @return 返回对应的下标，如果没有-1
  20.      */
  21.     public static int fibSearch(int[] a, int key) {
  22.         int low = 0;
  23.         int high = a.length - 1;
  24.         int k = 0; //表示斐波那契分割数值的下标
  25.         int mid = 0; //存放mid值
  26.         int f[] = fib(); //获取到斐波那契数列
  27.         //获取到斐波那契分割数值的下标
  28.         while(high > f[k] - 1) {
  29.             k++;
  30.         }
  31.         //因为 f[k] 值 可能大于 a 的 长度，因此我们需要使用Arrays类，构造一个新的数组，并指向temp[]
  32.         //不足的部分会使用0填充
  33.         int[] temp = Arrays.copyOf(a, f[k]);
  34.         //实际上需求使用a数组最后的数填充 temp
  35.         //举例:
  36.         //temp = {1,8, 10, 89, 1000, 1234, 0, 0}  => {1,8, 10, 89, 1000, 1234, 1234, 1234,}
  37.         for(int i = high + 1; i < temp.length; i++) {
  38.             temp[i] = a[high];
  39.         }
  41.         // 使用while来循环处理，找到我们的数 key
  42.         while (low <= high) { // 只要这个条件满足，就可以找
  43.             mid = low + f[k - 1] - 1;
  44.             if(key < temp[mid]) { //我们应该继续向数组的前面查找(左边)
  45.                 high = mid - 1;
  46.                 //为甚是 k--
  47.                 //说明
  48.                 //1. 全部元素 = 前面的元素 + 后边元素
  49.                 //2. f[k] = f[k-1] + f[k-2]
  50.                 //因为 前面有 f[k-1]个元素,所以可以继续拆分 f[k-1] = f[k-2] + f[k-3]
  51.                 //即 在 f[k-1] 的前面继续查找 k--
  52.                 //即下次循环 mid = f[k-1-1]-1
  53.                 k--;
  54.             } else if ( key > temp[mid]) { // 我们应该继续向数组的后面查找(右边)
  55.                 low = mid + 1;
  56.                 //为什么是k -=2
  57.                 //说明
  58.                 //1. 全部元素 = 前面的元素 + 后边元素
  59.                 //2. f[k] = f[k-1] + f[k-2]
  60.                 //3. 因为后面我们有f[k-2] 所以可以继续拆分 f[k-1] = f[k-3] + f[k-4]
  61.                 //4. 即在f[k-2] 的前面进行查找 k -=2
  62.                 //5. 即下次循环 mid = f[k - 1 - 2] - 1
  63.                 k -= 2;
  64.             } else { //找到
  65.                 //需要确定，返回的是哪个下标
  66.                 if(mid <= high) {
  67.                     return mid;
  68.                 } else {
  69.                     return high;
  70.                 }
  71.             }
  72.         }
  73.         return -1;
  74.     }

7 哈希表


  • 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表
    Java数据结构与算法-尚硅谷 - 图26

    基本介绍：

  • google上机题：

    ```java public class HashTabDemo {

    public static void main(String[] args) {

    1. //创建哈希表
    2. HashTab hashTab = new HashTab(7);
    4. //写一个简单的菜单
    5. String key = "";
    6. Scanner scanner = new Scanner(System.in);
    7. while (true) {
    8.     System.out.println("add:  添加雇员");
    9.     System.out.println("list: 显示雇员");
    10.     System.out.println("find: 查找雇员");
    11.     System.out.println("exit: 退出系统");
    13.     key = scanner.next();
    14.     switch (key) {
    15.         case "add":
    16.             System.out.println("输入id");
    17.             int id = scanner.nextInt();
    18.             System.out.println("输入名字");
    19.             String name = scanner.next();
    20.             //创建 雇员
    21.             Emp emp = new Emp(id, name);
    22.             hashTab.add(emp);
    23.             break;
    24.         case "list":
    25.             hashTab.list();
    26.             break;
    27.         case "find":
    28.             System.out.println("请输入要查找的id");
    29.             id = scanner.nextInt();
    30.             hashTab.findEmpById(id);
    31.             break;
    32.         case "exit":
    33.             scanner.close();
    34.             System.exit(0);
    35.         default:
    36.             break;
    37.     }
    38. }

    } }

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

  1. //构造器
  2. public HashTab(int size) {
  3.     this.size = size;
  4.     //初始化empLinkedListArray
  5.     empLinkedListArray = new EmpLinkedList[size];
  6.     //？留一个坑, 这时不要分别初始化每个链表
  7.     for (int i = 0; i < size; i++) {
  8.         empLinkedListArray[i] = new EmpLinkedList();
  9.     }
  10. }
  12. //添加雇员
  13. public void add(Emp emp) {
  14.     //根据员工的id ,得到该员工应当添加到哪条链表
  15.     int empLinkedListNO = hashFun(emp.id);
  16.     //将emp 添加到对应的链表中
  17.     empLinkedListArray[empLinkedListNO].add(emp);
  19. }
  21. //遍历所有的链表,遍历hashtab
  22. public void list() {
  23.     for (int i = 0; i < size; i++) {
  24.         empLinkedListArray[i].list(i);
  25.     }
  26. }
  28. //根据输入的id,查找雇员
  29. public void findEmpById(int id) {
  30.     //使用散列函数确定到哪条链表查找
  31.     int empLinkedListNO = hashFun(id);
  32.     Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);
  33.     if (emp != null) {//找到
  34.         System.out.printf("在第%d条链表中找到 雇员 id = %d\n", (empLinkedListNO + 1), id);
  35.     } else {
  36.         System.out.println("在哈希表中，没有找到该雇员~");
  37.     }
  38. }
  40. //编写散列函数, 使用一个简单取模法
  41. public int hashFun(int id) {
  42.     return id % size;
  43. }

}

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

  1. public Emp(int id, String name) {
  2.     super();
  3.     this.id = id;
  4.     this.name = name;
  5. }

}

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

  1. //添加雇员到链表
  2. //说明
  3. //1. 假定，当添加雇员时，id 是自增长，即id的分配总是从小到大
  4. //   因此我们将该雇员直接加入到本链表的最后即可
  5. public void add(Emp emp) {
  6.     //如果是添加第一个雇员
  7.     if (head == null) {
  8.         head = emp;
  9.         return;
  10.     }
  11.     //如果不是第一个雇员，则使用一个辅助的指针，帮助定位到最后
  12.     Emp curEmp = head;
  13.     while (true) {
  14.         if (curEmp.next == null) {//说明到链表最后
  15.             break;
  16.         }
  17.         curEmp = curEmp.next; //后移
  18.     }
  19.     //退出时直接将emp 加入链表
  20.     curEmp.next = emp;
  21. }
  23. //遍历链表的雇员信息
  24. public void list(int no) {
  25.     if (head == null) { //说明链表为空
  26.         System.out.println("第 " + (no + 1) + " 链表为空");
  27.         return;
  28.     }
  29.     System.out.print("第 " + (no + 1) + " 链表的信息为");
  30.     Emp curEmp = head; //辅助指针
  31.     while (true) {
  32.         System.out.printf(" => id=%d name=%s\t", curEmp.id, curEmp.name);
  33.         if (curEmp.next == null) {//说明curEmp已经是最后结点
  34.             break;
  35.         }
  36.         curEmp = curEmp.next; //后移，遍历
  37.     }
  38.     System.out.println();
  39. }
  41. //根据id查找雇员
  42. //如果查找到，就返回Emp, 如果没有找到，就返回null
  43. public Emp findEmpById(int id) {
  44.     //判断链表是否为空
  45.     if (head == null) {
  46.         System.out.println("链表为空");
  47.         return null;
  48.     }
  49.     //辅助指针
  50.     Emp curEmp = head;
  51.     while (true) {
  52.         if (curEmp.id == id) {//找到
  53.             break;//这时curEmp就指向要查找的雇员
  54.         }
  55.         //退出
  56.         if (curEmp.next == null) {//说明遍历当前链表没有找到该雇员
  57.             curEmp = null;
  58.             break;
  59.         }
  60.         curEmp = curEmp.next;//以后
  61.     }
  62.     return curEmp;
  63. }

}

  3. <a name="2b75f85a"></a>
  4. # 8 树(基础)
  6. -   ![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-07-31%2014.29.56.jpg#id=wbCPC&originHeight=1490&originWidth=1192&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=) 
  7. <a name="568dc93e-7"></a>
  8. #### 基本介绍：
  10. <a name="71dea625"></a>
  11. ## 8.1 二叉树
  13. -   
  14. <a name="05fc9f50"></a>
  15. #### 基础介绍：
  17.    1. 树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
  18.    2. 二叉树的子节点分为左节点和右节点
  19.    3. 如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树
  20.    4. 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树
  21. -   
  22. <a name="8bffa6ab"></a>
  23. #### 遍历：
  25.    1.  前序遍历: 先输出父节点，再遍历左子树和右子树 
  26.    2.  中序遍历: 先遍历左子树，再输出父节点，再遍历右子树 
  27.    3.  后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点<br />![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-07-31%2014.33.45.jpg#id=YKaH7&originHeight=666&originWidth=1640&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=)<br />![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-07-31%2014.40.10.jpg#id=NdAo2&originHeight=798&originWidth=1900&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=)<br />![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-07-31%2014.41.21.jpg#id=MJXAo&originHeight=798&originWidth=1900&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=) 
  28. ```java
  29. public class BinaryTreeDemo {
  31.     public static void main(String[] args) {
  32.         //先需要创建一颗二叉树
  33.         BinaryTree binaryTree = new BinaryTree();
  34.         //创建需要的结点
  35.         HeroNode root = new HeroNode(1, "宋江");
  36.         HeroNode node2 = new HeroNode(2, "吴用");
  37.         HeroNode node3 = new HeroNode(3, "卢俊义");
  38.         HeroNode node4 = new HeroNode(4, "林冲");
  39.         HeroNode node5 = new HeroNode(5, "关胜");
  41.         //说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树
  42.         root.setLeft(node2);
  43.         root.setRight(node3);
  44.         node3.setRight(node4);
  45.         node3.setLeft(node5);
  46.         binaryTree.setRoot(root);
  48.         //测试
  49. //        System.out.println("前序遍历"); // 1,2,3,5,4
  50. //        binaryTree.preOrder();
  52.         //测试 
  53. //        System.out.println("中序遍历");
  54. //        binaryTree.infixOrder(); // 2,1,5,3,4
  55. //        
  56. //        System.out.println("后序遍历");
  57. //        binaryTree.postOrder(); // 2,5,4,3,1
  59.         //前序遍历
  60.         //前序遍历的次数 ：4 
  61. //        System.out.println("前序遍历方式~~~");
  62. //        HeroNode resNode = binaryTree.preOrderSearch(5);
  63. //        if (resNode != null) {
  64. //            System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
  65. //        } else {
  66. //            System.out.printf("没有找到 no = %d 的英雄", 5);
  67. //        }
  69.         //中序遍历查找
  70.         //中序遍历3次
  71. //        System.out.println("中序遍历方式~~~");
  72. //        HeroNode resNode = binaryTree.infixOrderSearch(5);
  73. //        if (resNode != null) {
  74. //            System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
  75. //        } else {
  76. //            System.out.printf("没有找到 no = %d 的英雄", 5);
  77. //        }
  79.         //后序遍历查找
  80.         //后序遍历查找的次数  2次
  81. //        System.out.println("后序遍历方式~~~");
  82. //        HeroNode resNode = binaryTree.postOrderSearch(5);
  83. //        if (resNode != null) {
  84. //            System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
  85. //        } else {
  86. //            System.out.printf("没有找到 no = %d 的英雄", 5);
  87. //        }
  89.         //测试一把删除结点
  91.         System.out.println("删除前,前序遍历");
  92.         binaryTree.preOrder(); //  1,2,3,5,4
  93.         binaryTree.delNode(5);
  94.         //binaryTree.delNode(3);
  95.         System.out.println("删除后，前序遍历");
  96.         binaryTree.preOrder(); // 1,2,3,4
  99.     }
  101. }
  103. //定义BinaryTree 二叉树
  104. class BinaryTree {
  105.     private HeroNode root;
  107.     public void setRoot(HeroNode root) {
  108.         this.root = root;
  109.     }
  111.     //删除结点
  112.     public void delNode(int no) {
  113.         if (root != null) {
  114.             //如果只有一个root结点, 这里立即判断root是不是就是要删除结点
  115.             if (root.getNo() == no) {
  116.                 root = null;
  117.             } else {
  118.                 //递归删除
  119.                 root.delNode(no);
  120.             }
  121.         } else {
  122.             System.out.println("空树，不能删除~");
  123.         }
  124.     }
  126.     //前序遍历
  127.     public void preOrder() {
  128.         if (this.root != null) {
  129.             this.root.preOrder();
  130.         } else {
  131.             System.out.println("二叉树为空，无法遍历");
  132.         }
  133.     }
  135.     //中序遍历
  136.     public void infixOrder() {
  137.         if (this.root != null) {
  138.             this.root.infixOrder();
  139.         } else {
  140.             System.out.println("二叉树为空，无法遍历");
  141.         }
  142.     }
  144.     //后序遍历
  145.     public void postOrder() {
  146.         if (this.root != null) {
  147.             this.root.postOrder();
  148.         } else {
  149.             System.out.println("二叉树为空，无法遍历");
  150.         }
  151.     }
  153.     //前序遍历
  154.     public HeroNode preOrderSearch(int no) {
  155.         if (root != null) {
  156.             return root.preOrderSearch(no);
  157.         } else {
  158.             return null;
  159.         }
  160.     }
  162.     //中序遍历
  163.     public HeroNode infixOrderSearch(int no) {
  164.         if (root != null) {
  165.             return root.infixOrderSearch(no);
  166.         } else {
  167.             return null;
  168.         }
  169.     }
  171.     //后序遍历
  172.     public HeroNode postOrderSearch(int no) {
  173.         if (root != null) {
  174.             return this.root.postOrderSearch(no);
  175.         } else {
  176.             return null;
  177.         }
  178.     }
  179. }
  181. //先创建HeroNode 结点
  182. class HeroNode {
  183.     private int no;
  184.     private String name;
  185.     private HeroNode left; //默认null
  186.     private HeroNode right; //默认null
  188.     public HeroNode(int no, String name) {
  189.         this.no = no;
  190.         this.name = name;
  191.     }
  193.     public int getNo() {
  194.         return no;
  195.     }
  197.     public void setNo(int no) {
  198.         this.no = no;
  199.     }
  201.     public String getName() {
  202.         return name;
  203.     }
  205.     public void setName(String name) {
  206.         this.name = name;
  207.     }
  209.     public HeroNode getLeft() {
  210.         return left;
  211.     }
  213.     public void setLeft(HeroNode left) {
  214.         this.left = left;
  215.     }
  217.     public HeroNode getRight() {
  218.         return right;
  219.     }
  221.     public void setRight(HeroNode right) {
  222.         this.right = right;
  223.     }
  225.     @Override
  226.     public String toString() {
  227.         return "HeroNode [no=" + no + ", name=" + name + "]";
  228.     }
  230.     //递归删除结点
  231.     //1.如果删除的节点是叶子节点，则删除该节点
  232.     //2.如果删除的节点是非叶子节点，则删除该子树
  233.     public void delNode(int no) {
  235.         //思路
  236.         /*
  237.          *     1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点.
  238.             2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
  239.             3. 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
  240.             4. 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
  241.             5.  如果第4步也没有删除结点，则应当向右子树进行递归删除.
  243.          */
  244.         //2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
  245.         if (this.left != null && this.left.no == no) {
  246.             this.left = null;
  247.             return;
  248.         }
  249.         //3.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
  250.         if (this.right != null && this.right.no == no) {
  251.             this.right = null;
  252.             return;
  253.         }
  254.         //4.我们就需要向左子树进行递归删除
  255.         if (this.left != null) {
  256.             this.left.delNode(no);
  257.         }
  258.         //5.则应当向右子树进行递归删除
  259.         if (this.right != null) {
  260.             this.right.delNode(no);
  261.         }
  262.     }
  264.     //编写前序遍历的方法
  265.     public void preOrder() {
  266.         System.out.println(this); //先输出父结点
  267.         //递归向左子树前序遍历
  268.         if (this.left != null) {
  269.             this.left.preOrder();
  270.         }
  271.         //递归向右子树前序遍历
  272.         if (this.right != null) {
  273.             this.right.preOrder();
  274.         }
  275.     }
  277.     //中序遍历
  278.     public void infixOrder() {
  280.         //递归向左子树中序遍历
  281.         if (this.left != null) {
  282.             this.left.infixOrder();
  283.         }
  284.         //输出父结点
  285.         System.out.println(this);
  286.         //递归向右子树中序遍历
  287.         if (this.right != null) {
  288.             this.right.infixOrder();
  289.         }
  290.     }
  292.     //后序遍历
  293.     public void postOrder() {
  294.         if (this.left != null) {
  295.             this.left.postOrder();
  296.         }
  297.         if (this.right != null) {
  298.             this.right.postOrder();
  299.         }
  300.         System.out.println(this);
  301.     }
  303.     //前序遍历查找
  305.     /**
  306.      * @param no 查找no
  307.      * @return 如果找到就返回该Node ,如果没有找到返回 null
  308.      */
  309.     public HeroNode preOrderSearch(int no) {
  310.         System.out.println("进入前序遍历");
  311.         //比较当前结点是不是
  312.         if (this.no == no) {
  313.             return this;
  314.         }
  315.         //1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
  316.         //2.如果左递归前序查找，找到结点，则返回
  317.         HeroNode resNode = null;
  318.         if (this.left != null) {
  319.             resNode = this.left.preOrderSearch(no);
  320.         }
  321.         if (resNode != null) {//说明我们左子树找到
  322.             return resNode;
  323.         }
  324.         //1.左递归前序查找，找到结点，则返回，否继续判断，
  325.         //2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
  326.         if (this.right != null) {
  327.             resNode = this.right.preOrderSearch(no);
  328.         }
  329.         return resNode;
  330.     }
  332.     //中序遍历查找
  333.     public HeroNode infixOrderSearch(int no) {
  334.         //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
  335.         HeroNode resNode = null;
  336.         if (this.left != null) {
  337.             resNode = this.left.infixOrderSearch(no);
  338.         }
  339.         if (resNode != null) {
  340.             return resNode;
  341.         }
  342.         System.out.println("进入中序查找");
  343.         //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点
  344.         if (this.no == no) {
  345.             return this;
  346.         }
  347.         //否则继续进行右递归的中序查找
  348.         if (this.right != null) {
  349.             resNode = this.right.infixOrderSearch(no);
  350.         }
  351.         return resNode;
  353.     }
  355.     //后序遍历查找
  356.     public HeroNode postOrderSearch(int no) {
  358.         //判断当前结点的左子节点是否为空，如果不为空，则递归后序查找
  359.         HeroNode resNode = null;
  360.         if (this.left != null) {
  361.             resNode = this.left.postOrderSearch(no);
  362.         }
  363.         if (resNode != null) {//说明在左子树找到
  364.             return resNode;
  365.         }
  367.         //如果左子树没有找到，则向右子树递归进行后序遍历查找
  368.         if (this.right != null) {
  369.             resNode = this.right.postOrderSearch(no);
  370.         }
  371.         if (resNode != null) {
  372.             return resNode;
  373.         }
  374.         System.out.println("进入后序查找");
  375.         //如果左右子树都没有找到，就比较当前结点是不是
  376.         if (this.no == no) {
  377.             return this;
  378.         }
  379.         return resNode;
  380.     }
  382. }

8.2 顺序存储二叉树：

  1. 顺序二叉树通常只考虑完全二叉树
  2. 第 n 个元素的左子节点为 2 * n + 1
  3. 第 n 个元素的右子节点为 2 * n + 2
  4. 第 n 个元素的父节点为 (n-1) / 2
  5. n : 表示二叉树中的第几个元素(按

Java数据结构与算法-尚硅谷 - 图27

  1. public class ArrBinaryTreeDemo {
  3.     public static void main(String[] args) {
  4.         int[] arr = {1, 2, 3, 4, 5, 6, 7};
  5.         //创建一个 ArrBinaryTree
  6.         ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
  7.         arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7
  8.     }
  10. }
  12. //编写一个ArrayBinaryTree, 实现顺序存储二叉树遍历
  14. class ArrBinaryTree {
  15.     private int[] arr;//存储数据结点的数组
  17.     public ArrBinaryTree(int[] arr) {
  18.         this.arr = arr;
  19.     }
  21.     //重载preOrder
  22.     public void preOrder() {
  23.         this.preOrder(0);
  24.     }
  26.     //编写一个方法，完成顺序存储二叉树的前序遍历
  28.     /**
  29.      * @param index 数组的下标
  30.      */
  31.     public void preOrder(int index) {
  32.         //如果数组为空，或者 arr.length = 0
  33.         if (arr == null || arr.length == 0) {
  34.             System.out.println("数组为空，不能按照二叉树的前序遍历");
  35.         }
  36.         //输出当前这个元素
  37.         System.out.println(arr[index]);
  38.         //向左递归遍历
  39.         if ((index * 2 + 1) < arr.length) {
  40.             preOrder(2 * index + 1);
  41.         }
  42.         //向右递归遍历
  43.         if ((index * 2 + 2) < arr.length) {
  44.             preOrder(2 * index + 2);
  45.         }
  46.     }
  47. }

8.3 线索化二叉树：

  1. n 个结点的二叉链表中含有 n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为”线索”）
  2. 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
  3. 一个结点的前一个结点，称为前驱结点
  4. 一个结点的后一个结点，称为后继结点
    Java数据结构与算法-尚硅谷 - 图28 ```java package com.atguigu.tree.threadedbinarytree;

import java.util.concurrent.SynchronousQueue;

public class ThreadedBinaryTreeDemo {

  1. public static void main(String[] args) {
  2.     //测试一把中序线索二叉树的功能
  3.     HeroNode root = new HeroNode(1, "tom");
  4.     HeroNode node2 = new HeroNode(3, "jack");
  5.     HeroNode node3 = new HeroNode(6, "smith");
  6.     HeroNode node4 = new HeroNode(8, "mary");
  7.     HeroNode node5 = new HeroNode(10, "king");
  8.     HeroNode node6 = new HeroNode(14, "dim");
  10.     //二叉树，后面我们要递归创建, 现在简单处理使用手动创建
  11.     root.setLeft(node2);
  12.     root.setRight(node3);
  13.     node2.setLeft(node4);
  14.     node2.setRight(node5);
  15.     node3.setLeft(node6);
  17.     //测试中序线索化
  18.     ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
  19.     threadedBinaryTree.setRoot(root);
  20.     threadedBinaryTree.threadedNodes();
  22.     //测试: 以10号节点测试
  23.     HeroNode leftNode = node5.getLeft();
  24.     HeroNode rightNode = node5.getRight();
  25.     System.out.println("10号结点的前驱结点是 =" + leftNode); //3
  26.     System.out.println("10号结点的后继结点是=" + rightNode); //1
  28.     //当线索化二叉树后，能在使用原来的遍历方法
  29.     //threadedBinaryTree.infixOrder();
  30.     System.out.println("使用线索化的方式遍历 线索化二叉树");
  31.     threadedBinaryTree.threadedList(); // 8, 3, 10, 1, 14, 6
  33. }

}

//定义ThreadedBinaryTree 实现了线索化功能的二叉树 class ThreadedBinaryTree { private HeroNode root;

  1. //为了实现线索化，需要创建要给指向当前结点的前驱结点的指针
  2. //在递归进行线索化时，pre 总是保留前一个结点
  3. private HeroNode pre = null;
  5. public void setRoot(HeroNode root) {
  6.     this.root = root;
  7. }
  9. //重载一把threadedNodes方法
  10. public void threadedNodes() {
  11.     this.threadedNodes(root);
  12. }
  14. //遍历线索化二叉树的方法
  15. public void threadedList() {
  16.     //定义一个变量，存储当前遍历的结点，从root开始
  17.     HeroNode node = root;
  18.     while (node != null) {
  19.         //循环的找到leftType == 1的结点，第一个找到就是8结点
  20.         //后面随着遍历而变化,因为当leftType==1时，说明该结点是按照线索化
  21.         //处理后的有效结点
  22.         while (node.getLeftType() == 0) {
  23.             node = node.getLeft();
  24.         }
  26.         //打印当前这个结点
  27.         System.out.println(node);
  28.         //如果当前结点的右指针指向的是后继结点,就一直输出
  29.         while (node.getRightType() == 1) {
  30.             //获取到当前结点的后继结点
  31.             node = node.getRight();
  32.             System.out.println(node);
  33.         }
  34.         //替换这个遍历的结点
  35.         node = node.getRight();
  37.     }
  38. }
  40. //编写对二叉树进行中序线索化的方法
  42. /**
  43.  * @param node 就是当前需要线索化的结点
  44.  */
  45. public void threadedNodes(HeroNode node) {
  47.     //如果node==null, 不能线索化
  48.     if (node == null) {
  49.         return;
  50.     }
  52.     //(一)先线索化左子树
  53.     threadedNodes(node.getLeft());
  54.     //(二)线索化当前结点[有难度]
  56.     //处理当前结点的前驱结点
  57.     //以8结点来理解
  58.     //8结点的.left = null , 8结点的.leftType = 1
  59.     if (node.getLeft() == null) {
  60.         //让当前结点的左指针指向前驱结点 
  61.         node.setLeft(pre);
  62.         //修改当前结点的左指针的类型,指向前驱结点
  63.         node.setLeftType(1);
  64.     }
  66.     //处理后继结点
  67.     if (pre != null && pre.getRight() == null) {
  68.         //让前驱结点的右指针指向当前结点
  69.         pre.setRight(node);
  70.         //修改前驱结点的右指针类型
  71.         pre.setRightType(1);
  72.     }
  73.     //!!! 每处理一个结点后，让当前结点是下一个结点的前驱结点
  74.     pre = node;
  76.     //(三)在线索化右子树
  77.     threadedNodes(node.getRight());
  80. }
  82. //删除结点
  83. public void delNode(int no) {
  84.     if (root != null) {
  85.         //如果只有一个root结点, 这里立即判断root是不是就是要删除结点
  86.         if (root.getNo() == no) {
  87.             root = null;
  88.         } else {
  89.             //递归删除
  90.             root.delNode(no);
  91.         }
  92.     } else {
  93.         System.out.println("空树，不能删除~");
  94.     }
  95. }
  97. //前序遍历
  98. public void preOrder() {
  99.     if (this.root != null) {
  100.         this.root.preOrder();
  101.     } else {
  102.         System.out.println("二叉树为空，无法遍历");
  103.     }
  104. }
  106. //中序遍历
  107. public void infixOrder() {
  108.     if (this.root != null) {
  109.         this.root.infixOrder();
  110.     } else {
  111.         System.out.println("二叉树为空，无法遍历");
  112.     }
  113. }
  115. //后序遍历
  116. public void postOrder() {
  117.     if (this.root != null) {
  118.         this.root.postOrder();
  119.     } else {
  120.         System.out.println("二叉树为空，无法遍历");
  121.     }
  122. }
  124. //前序遍历
  125. public HeroNode preOrderSearch(int no) {
  126.     if (root != null) {
  127.         return root.preOrderSearch(no);
  128.     } else {
  129.         return null;
  130.     }
  131. }
  133. //中序遍历
  134. public HeroNode infixOrderSearch(int no) {
  135.     if (root != null) {
  136.         return root.infixOrderSearch(no);
  137.     } else {
  138.         return null;
  139.     }
  140. }
  142. //后序遍历
  143. public HeroNode postOrderSearch(int no) {
  144.     if (root != null) {
  145.         return this.root.postOrderSearch(no);
  146.     } else {
  147.         return null;
  148.     }
  149. }

}

//先创建HeroNode 结点 class HeroNode { private int no; private String name; private HeroNode left; //默认null private HeroNode right; //默认null //说明 //1. 如果leftType == 0 表示指向的是左子树, 如果 1 则表示指向前驱结点 //2. 如果rightType == 0 表示指向是右子树, 如果 1表示指向后继结点 private int leftType; private int rightType;

  1. public int getLeftType() {
  2.     return leftType;
  3. }
  5. public void setLeftType(int leftType) {
  6.     this.leftType = leftType;
  7. }
  9. public int getRightType() {
  10.     return rightType;
  11. }
  13. public void setRightType(int rightType) {
  14.     this.rightType = rightType;
  15. }
  17. public HeroNode(int no, String name) {
  18.     this.no = no;
  19.     this.name = name;
  20. }
  22. public int getNo() {
  23.     return no;
  24. }
  26. public void setNo(int no) {
  27.     this.no = no;
  28. }
  30. public String getName() {
  31.     return name;
  32. }
  34. public void setName(String name) {
  35.     this.name = name;
  36. }
  38. public HeroNode getLeft() {
  39.     return left;
  40. }
  42. public void setLeft(HeroNode left) {
  43.     this.left = left;
  44. }
  46. public HeroNode getRight() {
  47.     return right;
  48. }
  50. public void setRight(HeroNode right) {
  51.     this.right = right;
  52. }
  54. @Override
  55. public String toString() {
  56.     return "HeroNode [no=" + no + ", name=" + name + "]";
  57. }
  59. //递归删除结点
  60. //1.如果删除的节点是叶子节点，则删除该节点
  61. //2.如果删除的节点是非叶子节点，则删除该子树
  62. public void delNode(int no) {
  64.     //思路
  65.     /*
  66.      *     1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点.
  67.         2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
  68.         3. 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
  69.         4. 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
  70.         5.  如果第4步也没有删除结点，则应当向右子树进行递归删除.
  72.      */
  73.     //2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
  74.     if (this.left != null && this.left.no == no) {
  75.         this.left = null;
  76.         return;
  77.     }
  78.     //3.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
  79.     if (this.right != null && this.right.no == no) {
  80.         this.right = null;
  81.         return;
  82.     }
  83.     //4.我们就需要向左子树进行递归删除
  84.     if (this.left != null) {
  85.         this.left.delNode(no);
  86.     }
  87.     //5.则应当向右子树进行递归删除
  88.     if (this.right != null) {
  89.         this.right.delNode(no);
  90.     }
  91. }
  93. //编写前序遍历的方法
  94. public void preOrder() {
  95.     System.out.println(this); //先输出父结点
  96.     //递归向左子树前序遍历
  97.     if (this.left != null) {
  98.         this.left.preOrder();
  99.     }
  100.     //递归向右子树前序遍历
  101.     if (this.right != null) {
  102.         this.right.preOrder();
  103.     }
  104. }
  106. //中序遍历
  107. public void infixOrder() {
  109.     //递归向左子树中序遍历
  110.     if (this.left != null) {
  111.         this.left.infixOrder();
  112.     }
  113.     //输出父结点
  114.     System.out.println(this);
  115.     //递归向右子树中序遍历
  116.     if (this.right != null) {
  117.         this.right.infixOrder();
  118.     }
  119. }
  121. //后序遍历
  122. public void postOrder() {
  123.     if (this.left != null) {
  124.         this.left.postOrder();
  125.     }
  126.     if (this.right != null) {
  127.         this.right.postOrder();
  128.     }
  129.     System.out.println(this);
  130. }
  132. //前序遍历查找
  134. /**
  135.  * @param no 查找no
  136.  * @return 如果找到就返回该Node ,如果没有找到返回 null
  137.  */
  138. public HeroNode preOrderSearch(int no) {
  139.     System.out.println("进入前序遍历");
  140.     //比较当前结点是不是
  141.     if (this.no == no) {
  142.         return this;
  143.     }
  144.     //1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
  145.     //2.如果左递归前序查找，找到结点，则返回
  146.     HeroNode resNode = null;
  147.     if (this.left != null) {
  148.         resNode = this.left.preOrderSearch(no);
  149.     }
  150.     if (resNode != null) {//说明我们左子树找到
  151.         return resNode;
  152.     }
  153.     //1.左递归前序查找，找到结点，则返回，否继续判断，
  154.     //2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
  155.     if (this.right != null) {
  156.         resNode = this.right.preOrderSearch(no);
  157.     }
  158.     return resNode;
  159. }
  161. //中序遍历查找
  162. public HeroNode infixOrderSearch(int no) {
  163.     //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
  164.     HeroNode resNode = null;
  165.     if (this.left != null) {
  166.         resNode = this.left.infixOrderSearch(no);
  167.     }
  168.     if (resNode != null) {
  169.         return resNode;
  170.     }
  171.     System.out.println("进入中序查找");
  172.     //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点
  173.     if (this.no == no) {
  174.         return this;
  175.     }
  176.     //否则继续进行右递归的中序查找
  177.     if (this.right != null) {
  178.         resNode = this.right.infixOrderSearch(no);
  179.     }
  180.     return resNode;
  182. }
  184. //后序遍历查找
  185. public HeroNode postOrderSearch(int no) {
  187.     //判断当前结点的左子节点是否为空，如果不为空，则递归后序查找
  188.     HeroNode resNode = null;
  189.     if (this.left != null) {
  190.         resNode = this.left.postOrderSearch(no);
  191.     }
  192.     if (resNode != null) {//说明在左子树找到
  193.         return resNode;
  194.     }
  196.     //如果左子树没有找到，则向右子树递归进行后序遍历查找
  197.     if (this.right != null) {
  198.         resNode = this.right.postOrderSearch(no);
  199.     }
  200.     if (resNode != null) {
  201.         return resNode;
  202.     }
  203.     System.out.println("进入后序查找");
  204.     //如果左右子树都没有找到，就比较当前结点是不是
  205.     if (this.no == no) {
  206.         return this;
  207.     }
  208.     return resNode;
  209. }

}

  3. <a name="fdbf05c4"></a>
  4. # 9 树(应用)
  6. <a name="b2048f24"></a>
  7. ## 9.1 赫夫曼树
  9. -   
  10. <a name="568dc93e-8"></a>
  11. #### 基本介绍：
  13.    1. 给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。
  14.    2. 赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近
  15. -   
  16. <a name="3321d5c9"></a>
  17. #### 构成步骤：
  19.    1.  从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树 
  20.    2.  取出根节点权值最小的两颗二叉树 
  21.    3.  组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和 
  22.    4.  再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树 
  23. ```java
  24. public class HuffmanTree {
  26.     public static void main(String[] args) {
  27.         int arr[] = {13, 7, 8, 3, 29, 6, 1};
  28.         Node root = createHuffmanTree(arr);
  30.         //测试一把
  31.         preOrder(root); //
  33.     }
  35.     //编写一个前序遍历的方法
  36.     public static void preOrder(Node root) {
  37.         if (root != null) {
  38.             root.preOrder();
  39.         } else {
  40.             System.out.println("是空树，不能遍历~~");
  41.         }
  42.     }
  44.     // 创建赫夫曼树的方法
  46.     /**
  47.      * @param arr 需要创建成哈夫曼树的数组
  48.      * @return 创建好后的赫夫曼树的root结点
  49.      */
  50.     public static Node createHuffmanTree(int[] arr) {
  51.         // 第一步为了操作方便
  52.         // 1. 遍历 arr 数组
  53.         // 2. 将arr的每个元素构成成一个Node
  54.         // 3. 将Node 放入到ArrayList中
  55.         List<Node> nodes = new ArrayList<Node>();
  56.         for (int value : arr) {
  57.             nodes.add(new Node(value));
  58.         }
  60.         //我们处理的过程是一个循环的过程
  63.         while (nodes.size() > 1) {
  65.             //排序 从小到大 
  66.             Collections.sort(nodes);
  68.             System.out.println("nodes =" + nodes);
  70.             //取出根节点权值最小的两颗二叉树 
  71.             //(1) 取出权值最小的结点（二叉树）
  72.             Node leftNode = nodes.get(0);
  73.             //(2) 取出权值第二小的结点（二叉树）
  74.             Node rightNode = nodes.get(1);
  76.             //(3)构建一颗新的二叉树
  77.             Node parent = new Node(leftNode.value + rightNode.value);
  78.             parent.left = leftNode;
  79.             parent.right = rightNode;
  81.             //(4)从ArrayList删除处理过的二叉树
  82.             nodes.remove(leftNode);
  83.             nodes.remove(rightNode);
  84.             //(5)将parent加入到nodes
  85.             nodes.add(parent);
  86.         }
  88.         //返回哈夫曼树的root结点
  89.         return nodes.get(0);
  90.     }
  91. }
  93. // 创建结点类
  94. // 为了让Node 对象持续排序Collections集合排序
  95. // 让Node 实现Comparable接口
  96. class Node implements Comparable<Node> {
  97.     int value; // 结点权值
  98.     char c; //字符
  99.     Node left; // 指向左子结点
  100.     Node right; // 指向右子结点
  102.     //写一个前序遍历
  103.     public void preOrder() {
  104.         System.out.println(this);
  105.         if (this.left != null) {
  106.             this.left.preOrder();
  107.         }
  108.         if (this.right != null) {
  109.             this.right.preOrder();
  110.         }
  111.     }
  113.     public Node(int value) {
  114.         this.value = value;
  115.     }
  117.     @Override
  118.     public String toString() {
  119.         return "Node [value=" + value + "]";
  120.     }
  122.     @Override
  123.     public int compareTo(Node o) {
  124.         // TODO Auto-generated method stub
  125.         // 表示从小到大排序
  126.         return this.value - o.value;
  127.     }
  128. }

9.2 赫夫曼编码


  • Java数据结构与算法-尚硅谷 - 图29

    基本介绍：

  • 步骤：

    1. 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树
    2. 取出根节点权值最小的两颗二叉树
    3. 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
    4. 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树 ```java public class HuffmanCode {

    public static void main(String[] args) {

    1. //测试压缩文件

    // String srcFile = “d://Uninstall.xml”; // String dstFile = “d://Uninstall.zip”; //
    // zipFile(srcFile, dstFile); // System.out.println(“压缩文件ok~~”);

  1.     //测试解压文件
  2.     String zipFile = "d://Uninstall.zip";
  3.     String dstFile = "d://Uninstall2.xml";
  4.     unZipFile(zipFile, dstFile);
  5.     System.out.println("解压成功!");
  7.     /*
  8.     String content = "i like like like java do you like a java";
  9.     byte[] contentBytes = content.getBytes();
  10.     System.out.println(contentBytes.length); //40
  12.     byte[] huffmanCodesBytes= huffmanZip(contentBytes);
  13.     System.out.println("压缩后的结果是:" + Arrays.toString(huffmanCodesBytes) + " 长度= " + huffmanCodesBytes.length);
  16.     //测试一把byteToBitString方法
  17.     //System.out.println(byteToBitString((byte)1));
  18.     byte[] sourceBytes = decode(huffmanCodes, huffmanCodesBytes);
  20.     System.out.println("原来的字符串=" + new String(sourceBytes)); // "i like like like java do you like a java"
  21.     */
  25.     //如何将 数据进行解压(解码)  
  26.     //分步过程
  27.     /*
  28.     List<Node> nodes = getNodes(contentBytes);
  29.     System.out.println("nodes=" + nodes);
  31.     //测试一把，创建的赫夫曼树
  32.     System.out.println("赫夫曼树");
  33.     Node huffmanTreeRoot = createHuffmanTree(nodes);
  34.     System.out.println("前序遍历");
  35.     huffmanTreeRoot.preOrder();
  37.     //测试一把是否生成了对应的赫夫曼编码
  38.     Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
  39.     System.out.println("~生成的赫夫曼编码表= " + huffmanCodes);
  41.     //测试
  42.     byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
  43.     System.out.println("huffmanCodeBytes=" + Arrays.toString(huffmanCodeBytes));//17
  45.     //发送huffmanCodeBytes 数组 */
  48. }
  50. //编写一个方法，完成对压缩文件的解压
  51. /**
  52.  * 
  53.  * @param zipFile 准备解压的文件
  54.  * @param dstFile 将文件解压到哪个路径
  55.  */
  56. public static void unZipFile(String zipFile, String dstFile) {
  58.     //定义文件输入流
  59.     InputStream is = null;
  60.     //定义一个对象输入流
  61.     ObjectInputStream ois = null;
  62.     //定义文件的输出流
  63.     OutputStream os = null;
  64.     try {
  65.         //创建文件输入流
  66.         is = new FileInputStream(zipFile);
  67.         //创建一个和  is关联的对象输入流
  68.         ois = new ObjectInputStream(is);
  69.         //读取byte数组  huffmanBytes
  70.         byte[] huffmanBytes = (byte[])ois.readObject();
  71.         //读取赫夫曼编码表
  72.         Map<Byte,String> huffmanCodes = (Map<Byte,String>)ois.readObject();
  74.         //解码
  75.         byte[] bytes = decode(huffmanCodes, huffmanBytes);
  76.         //将bytes 数组写入到目标文件
  77.         os = new FileOutputStream(dstFile);
  78.         //写数据到 dstFile 文件
  79.         os.write(bytes);
  80.     } catch (Exception e) {
  81.         // TODO: handle exception
  82.         System.out.println(e.getMessage());
  83.     } finally {
  85.         try {
  86.             os.close();
  87.             ois.close();
  88.             is.close();
  89.         } catch (Exception e2) {
  90.             // TODO: handle exception
  91.             System.out.println(e2.getMessage());
  92.         }
  94.     }
  95. }
  97. //编写方法，将一个文件进行压缩
  98. /**
  99.  * 
  100.  * @param srcFile 你传入的希望压缩的文件的全路径
  101.  * @param dstFile 我们压缩后将压缩文件放到哪个目录
  102.  */
  103. public static void zipFile(String srcFile, String dstFile) {
  105.     //创建输出流
  106.     OutputStream os = null;
  107.     ObjectOutputStream oos = null;
  108.     //创建文件的输入流
  109.     FileInputStream is = null;
  110.     try {
  111.         //创建文件的输入流
  112.         is = new FileInputStream(srcFile);
  113.         //创建一个和源文件大小一样的byte[]
  114.         byte[] b = new byte[is.available()];
  115.         //读取文件
  116.         is.read(b);
  117.         //直接对源文件压缩
  118.         byte[] huffmanBytes = huffmanZip(b);
  119.         //创建文件的输出流, 存放压缩文件
  120.         os = new FileOutputStream(dstFile);
  121.         //创建一个和文件输出流关联的ObjectOutputStream
  122.         oos = new ObjectOutputStream(os);
  123.         //把 赫夫曼编码后的字节数组写入压缩文件
  124.         oos.writeObject(huffmanBytes); //我们是把
  125.         //这里我们以对象流的方式写入 赫夫曼编码，是为了以后我们恢复源文件时使用
  126.         //注意一定要把赫夫曼编码 写入压缩文件
  127.         oos.writeObject(huffmanCodes);
  130.     }catch (Exception e) {
  131.         // TODO: handle exception
  132.         System.out.println(e.getMessage());
  133.     }finally {
  134.         try {
  135.             is.close();
  136.             oos.close();
  137.             os.close();
  138.         }catch (Exception e) {
  139.             // TODO: handle exception
  140.             System.out.println(e.getMessage());
  141.         }
  142.     }    
  143. }
  145. //完成数据的解压
  146. //思路
  147. //1. 将huffmanCodeBytes [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
  148. //   重写先转成 赫夫曼编码对应的二进制的字符串 "1010100010111..."
  149. //2.  赫夫曼编码对应的二进制的字符串 "1010100010111..." =》 对照 赫夫曼编码  =》 "i like like like java do you like a java"
  152. //编写一个方法，完成对压缩数据的解码
  153. /**
  154.  * 
  155.  * @param huffmanCodes 赫夫曼编码表 map
  156.  * @param huffmanBytes 赫夫曼编码得到的字节数组
  157.  * @return 就是原来的字符串对应的数组
  158.  */
  159. private static byte[] decode(Map<Byte,String> huffmanCodes, byte[] huffmanBytes) {
  161.     //1. 先得到 huffmanBytes 对应的 二进制的字符串 ， 形式 1010100010111...
  162.     StringBuilder stringBuilder = new StringBuilder();
  163.     //将byte数组转成二进制的字符串
  164.     for(int i = 0; i < huffmanBytes.length; i++) {
  165.         byte b = huffmanBytes[i];
  166.         //判断是不是最后一个字节
  167.         boolean flag = (i == huffmanBytes.length - 1);
  168.         stringBuilder.append(byteToBitString(!flag, b));
  169.     }
  170.     //把字符串安装指定的赫夫曼编码进行解码
  171.     //把赫夫曼编码表进行调换，因为反向查询 a->100 100->a
  172.     Map<String, Byte>  map = new HashMap<String,Byte>();
  173.     for(Map.Entry<Byte, String> entry: huffmanCodes.entrySet()) {
  174.         map.put(entry.getValue(), entry.getKey());
  175.     }
  177.     //创建要给集合，存放byte
  178.     List<Byte> list = new ArrayList<>();
  179.     //i 可以理解成就是索引,扫描 stringBuilder 
  180.     for(int  i = 0; i < stringBuilder.length(); ) {
  181.         int count = 1; // 小的计数器
  182.         boolean flag = true;
  183.         Byte b = null;
  185.         while(flag) {
  186.             //1010100010111...
  187.             //递增的取出 key 1 
  188.             String key = stringBuilder.substring(i, i+count);//i 不动，让count移动，指定匹配到一个字符
  189.             b = map.get(key);
  190.             if(b == null) {//说明没有匹配到
  191.                 count++;
  192.             }else {
  193.                 //匹配到
  194.                 flag = false;
  195.             }
  196.         }
  197.         list.add(b);
  198.         i += count;//i 直接移动到 count    
  199.     }
  200.     //当for循环结束后，我们list中就存放了所有的字符  "i like like like java do you like a java"
  201.     //把list 中的数据放入到byte[] 并返回
  202.     byte b[] = new byte[list.size()];
  203.     for(int i = 0;i < b.length; i++) {
  204.         b[i] = list.get(i);
  205.     }
  206.     return b;
  207. }
  209. /**
  210.  * 将一个byte 转成一个二进制的字符串, 如果看不懂，可以参考我讲的Java基础 二进制的原码，反码，补码
  211.  * @param b 传入的 byte
  212.  * @param flag 标志是否需要补高位如果是true ，表示需要补高位，如果是false表示不补, 如果是最后一个字节，无需补高位
  213.  * @return 是该b 对应的二进制的字符串，（注意是按补码返回）
  214.  */
  215. private static String byteToBitString(boolean flag, byte b) {
  216.     //使用变量保存 b
  217.     int temp = b; //将 b 转成 int
  218.     //如果是正数我们还存在补高位
  219.     if(flag) {
  220.         temp |= 256; //按位与 256  1 0000 0000  | 0000 0001 => 1 0000 0001
  221.     }
  222.     String str = Integer.toBinaryString(temp); //返回的是temp对应的二进制的补码
  223.     if(flag) {
  224.         return str.substring(str.length() - 8);
  225.     } else {
  226.         return str;
  227.     }
  228. }
  230. //使用一个方法，将前面的方法封装起来，便于我们的调用.
  231. /**
  232.  * 
  233.  * @param bytes 原始的字符串对应的字节数组
  234.  * @return 是经过 赫夫曼编码处理后的字节数组(压缩后的数组)
  235.  */
  236. private static byte[] huffmanZip(byte[] bytes) {
  237.     List<Node> nodes = getNodes(bytes);
  238.     //根据 nodes 创建的赫夫曼树
  239.     Node huffmanTreeRoot = createHuffmanTree(nodes);
  240.     //对应的赫夫曼编码(根据 赫夫曼树)
  241.     Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
  242.     //根据生成的赫夫曼编码，压缩得到压缩后的赫夫曼编码字节数组
  243.     byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
  244.     return huffmanCodeBytes;
  245. }
  248. //编写一个方法，将字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码 压缩后的byte[]
  249. /**
  250.  * 
  251.  * @param bytes 这时原始的字符串对应的 byte[]
  252.  * @param huffmanCodes 生成的赫夫曼编码map
  253.  * @return 返回赫夫曼编码处理后的 byte[] 
  254.  * 举例： String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
  255.  * 返回的是 字符串 "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100"
  256.  * => 对应的 byte[] huffmanCodeBytes  ，即 8位对应一个 byte,放入到 huffmanCodeBytes
  257.  * huffmanCodeBytes[0] =  10101000(补码) => byte  [推导  10101000=> 10101000 - 1 => 10100111(反码)=> 11011000= -88 ]
  258.  * huffmanCodeBytes[1] = -88
  259.  */
  260. private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
  262.     //1.利用 huffmanCodes 将  bytes 转成  赫夫曼编码对应的字符串
  263.     StringBuilder stringBuilder = new StringBuilder();
  264.     //遍历bytes 数组 
  265.     for(byte b: bytes) {
  266.         stringBuilder.append(huffmanCodes.get(b));
  267.     }
  269.     //System.out.println("测试 stringBuilder~~~=" + stringBuilder.toString());
  271.     //将 "1010100010111111110..." 转成 byte[]
  273.     //统计返回  byte[] huffmanCodeBytes 长度
  274.     //一句话 int len = (stringBuilder.length() + 7) / 8;
  275.     int len;
  276.     if(stringBuilder.length() % 8 == 0) {
  277.         len = stringBuilder.length() / 8;
  278.     } else {
  279.         len = stringBuilder.length() / 8 + 1;
  280.     }
  281.     //创建 存储压缩后的 byte数组
  282.     byte[] huffmanCodeBytes = new byte[len];
  283.     int index = 0;//记录是第几个byte
  284.     for (int i = 0; i < stringBuilder.length(); i += 8) { //因为是每8位对应一个byte,所以步长 +8
  285.             String strByte;
  286.             if(i+8 > stringBuilder.length()) {//不够8位
  287.                 strByte = stringBuilder.substring(i);
  288.             }else{
  289.                 strByte = stringBuilder.substring(i, i + 8);
  290.             }    
  291.             //将strByte 转成一个byte,放入到 huffmanCodeBytes
  292.             huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);
  293.             index++;
  294.     }
  295.     return huffmanCodeBytes;
  296. }
  298. //生成赫夫曼树对应的赫夫曼编码
  299. //思路:
  300. //1. 将赫夫曼编码表存放在 Map<Byte,String> 形式
  301. //   生成的赫夫曼编码表{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
  302. static Map<Byte, String> huffmanCodes = new HashMap<Byte,String>();
  303. //2. 在生成赫夫曼编码表示，需要去拼接路径, 定义一个StringBuilder 存储某个叶子结点的路径
  304. static StringBuilder stringBuilder = new StringBuilder();
  307. //为了调用方便，我们重载 getCodes
  308. private static Map<Byte, String> getCodes(Node root) {
  309.     if(root == null) {
  310.         return null;
  311.     }
  312.     //处理root的左子树
  313.     getCodes(root.left, "0", stringBuilder);
  314.     //处理root的右子树
  315.     getCodes(root.right, "1", stringBuilder);
  316.     return huffmanCodes;
  317. }
  319. /**
  320.  * 功能：将传入的node结点的所有叶子结点的赫夫曼编码得到，并放入到huffmanCodes集合
  321.  * @param node  传入结点
  322.  * @param code  路径： 左子结点是 0, 右子结点 1
  323.  * @param stringBuilder 用于拼接路径
  324.  */
  325. private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
  326.     StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
  327.     //将code 加入到 stringBuilder2
  328.     stringBuilder2.append(code);
  329.     if(node != null) { //如果node == null不处理
  330.         //判断当前node 是叶子结点还是非叶子结点
  331.         if(node.data == null) { //非叶子结点
  332.             //递归处理
  333.             //向左递归
  334.             getCodes(node.left, "0", stringBuilder2);
  335.             //向右递归
  336.             getCodes(node.right, "1", stringBuilder2);
  337.         } else { //说明是一个叶子结点
  338.             //就表示找到某个叶子结点的最后
  339.             huffmanCodes.put(node.data, stringBuilder2.toString());
  340.         }
  341.     }
  342. }
  344. //前序遍历的方法
  345. private static void preOrder(Node root) {
  346.     if(root != null) {
  347.         root.preOrder();
  348.     }else {
  349.         System.out.println("赫夫曼树为空");
  350.     }
  351. }
  353. /**
  354.  * 
  355.  * @param bytes 接收字节数组
  356.  * @return 返回的就是 List 形式   [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],
  357.  */
  358. private static List<Node> getNodes(byte[] bytes) {
  360.     //1创建一个ArrayList
  361.     ArrayList<Node> nodes = new ArrayList<Node>();
  363.     //遍历 bytes , 统计 每一个byte出现的次数->map[key,value]
  364.     Map<Byte, Integer> counts = new HashMap<>();
  365.     for (byte b : bytes) {
  366.         Integer count = counts.get(b);
  367.         if (count == null) { // Map还没有这个字符数据,第一次
  368.             counts.put(b, 1);
  369.         } else {
  370.             counts.put(b, count + 1);
  371.         }
  372.     }
  374.     //把每一个键值对转成一个Node 对象，并加入到nodes集合
  375.     //遍历map
  376.     for(Map.Entry<Byte, Integer> entry: counts.entrySet()) {
  377.         nodes.add(new Node(entry.getKey(), entry.getValue()));
  378.     }
  379.     return nodes;
  381. }
  383. //可以通过List 创建对应的赫夫曼树
  384. private static Node createHuffmanTree(List<Node> nodes) {
  386.     while(nodes.size() > 1) {
  387.         //排序, 从小到大
  388.         Collections.sort(nodes);
  389.         //取出第一颗最小的二叉树
  390.         Node leftNode = nodes.get(0);
  391.         //取出第二颗最小的二叉树
  392.         Node rightNode = nodes.get(1);
  393.         //创建一颗新的二叉树,它的根节点 没有data, 只有权值
  394.         Node parent = new Node(null, leftNode.weight + rightNode.weight);
  395.         parent.left = leftNode;
  396.         parent.right = rightNode;
  398.         //将已经处理的两颗二叉树从nodes删除
  399.         nodes.remove(leftNode);
  400.         nodes.remove(rightNode);
  401.         //将新的二叉树，加入到nodes
  402.         nodes.add(parent);
  404.     }
  405.     //nodes 最后的结点，就是赫夫曼树的根结点
  406.     return nodes.get(0);    
  407. }

}

//创建Node ,待数据和权值 class Node implements Comparable { Byte data; // 存放数据(字符)本身，比如’a’ => 97 ‘ ‘ => 32 int weight; //权值, 表示字符出现的次数 Node left;// Node right; public Node(Byte data, int weight) {

  1.     this.data = data;
  2.     this.weight = weight;
  3. }
  4. @Override
  5. public int compareTo(Node o) {
  6.     // 从小到大排序
  7.     return this.weight - o.weight;
  8. }
  10. public String toString() {
  11.     return "Node [data = " + data + " weight=" + weight + "]";
  12. }
  14. //前序遍历
  15. public void preOrder() {
  16.     System.out.println(this);
  17.     if(this.left != null) {
  18.         this.left.preOrder();
  19.     }
  20.     if(this.right != null) {
  21.         this.right.preOrder();
  22.     }
  23. }

}

  3. <a name="76e2a46c"></a>
  4. ## 9.3 平衡二叉树
  6. -   
  7. <a name="568dc93e-10"></a>
  8. #### 基本介绍：
  10.    1. 平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为 AVL 树，可以保证查询效率较高
  11.    2. 具有以下特点：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等
  12. -  <br />![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-07-31%2015.57.18.jpg#id=qIoVf&originHeight=658&originWidth=2036&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=) 
  13. <a name="10c8962a-3"></a>
  14. #### 代码实现：
  15. ```java
  16. public class AVLTreeDemo {
  18.     public static void main(String[] args) {
  19.         //int[] arr = {4,3,6,5,7,8};
  20.         //int[] arr = { 10, 12, 8, 9, 7, 6 };
  21.         int[] arr = { 10, 11, 7, 6, 8, 9 };  
  22.         //创建一个 AVLTree对象
  23.         AVLTree avlTree = new AVLTree();
  24.         //添加结点
  25.         for(int i=0; i < arr.length; i++) {
  26.             avlTree.add(new Node(arr[i]));
  27.         }
  29.         //遍历
  30.         System.out.println("中序遍历");
  31.         avlTree.infixOrder();
  33.         System.out.println("在平衡处理~~");
  34.         System.out.println("树的高度=" + avlTree.getRoot().height()); //3
  35.         System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight()); // 2
  36.         System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight()); // 2
  37.         System.out.println("当前的根结点=" + avlTree.getRoot());//8
  39.     }
  40. }
  42. // 创建AVLTree
  43. class AVLTree {
  44.     private Node root;
  46.     public Node getRoot() {
  47.         return root;
  48.     }
  50.     // 查找要删除的结点
  51.     public Node search(int value) {
  52.         if (root == null) {
  53.             return null;
  54.         } else {
  55.             return root.search(value);
  56.         }
  57.     }
  59.     // 查找父结点
  60.     public Node searchParent(int value) {
  61.         if (root == null) {
  62.             return null;
  63.         } else {
  64.             return root.searchParent(value);
  65.         }
  66.     }
  68.     // 编写方法:
  69.     // 1. 返回的 以node 为根结点的二叉排序树的最小结点的值
  70.     // 2. 删除node 为根结点的二叉排序树的最小结点
  71.     /**
  72.      * 
  73.      * @param node
  74.      *            传入的结点(当做二叉排序树的根结点)
  75.      * @return 返回的 以node 为根结点的二叉排序树的最小结点的值
  76.      */
  77.     public int delRightTreeMin(Node node) {
  78.         Node target = node;
  79.         // 循环的查找左子节点，就会找到最小值
  80.         while (target.left != null) {
  81.             target = target.left;
  82.         }
  83.         // 这时 target就指向了最小结点
  84.         // 删除最小结点
  85.         delNode(target.value);
  86.         return target.value;
  87.     }
  89.     // 删除结点
  90.     public void delNode(int value) {
  91.         if (root == null) {
  92.             return;
  93.         } else {
  94.             // 1.需求先去找到要删除的结点 targetNode
  95.             Node targetNode = search(value);
  96.             // 如果没有找到要删除的结点
  97.             if (targetNode == null) {
  98.                 return;
  99.             }
  100.             // 如果我们发现当前这颗二叉排序树只有一个结点
  101.             if (root.left == null && root.right == null) {
  102.                 root = null;
  103.                 return;
  104.             }
  106.             // 去找到targetNode的父结点
  107.             Node parent = searchParent(value);
  108.             // 如果要删除的结点是叶子结点
  109.             if (targetNode.left == null && targetNode.right == null) {
  110.                 // 判断targetNode 是父结点的左子结点，还是右子结点
  111.                 if (parent.left != null && parent.left.value == value) { // 是左子结点
  112.                     parent.left = null;
  113.                 } else if (parent.right != null && parent.right.value == value) {// 是由子结点
  114.                     parent.right = null;
  115.                 }
  116.             } else if (targetNode.left != null && targetNode.right != null) { // 删除有两颗子树的节点
  117.                 int minVal = delRightTreeMin(targetNode.right);
  118.                 targetNode.value = minVal;
  120.             } else { // 删除只有一颗子树的结点
  121.                 // 如果要删除的结点有左子结点
  122.                 if (targetNode.left != null) {
  123.                     if (parent != null) {
  124.                         // 如果 targetNode 是 parent 的左子结点
  125.                         if (parent.left.value == value) {
  126.                             parent.left = targetNode.left;
  127.                         } else { // targetNode 是 parent 的右子结点
  128.                             parent.right = targetNode.left;
  129.                         }
  130.                     } else {
  131.                         root = targetNode.left;
  132.                     }
  133.                 } else { // 如果要删除的结点有右子结点
  134.                     if (parent != null) {
  135.                         // 如果 targetNode 是 parent 的左子结点
  136.                         if (parent.left.value == value) {
  137.                             parent.left = targetNode.right;
  138.                         } else { // 如果 targetNode 是 parent 的右子结点
  139.                             parent.right = targetNode.right;
  140.                         }
  141.                     } else {
  142.                         root = targetNode.right;
  143.                     }
  144.                 }
  145.             }
  146.         }
  147.     }
  149.     // 添加结点的方法
  150.     public void add(Node node) {
  151.         if (root == null) {
  152.             root = node;// 如果root为空则直接让root指向node
  153.         } else {
  154.             root.add(node);
  155.         }
  156.     }
  158.     // 中序遍历
  159.     public void infixOrder() {
  160.         if (root != null) {
  161.             root.infixOrder();
  162.         } else {
  163.             System.out.println("二叉排序树为空，不能遍历");
  164.         }
  165.     }
  166. }
  168. // 创建Node结点
  169. class Node {
  170.     int value;
  171.     Node left;
  172.     Node right;
  174.     public Node(int value) {
  176.         this.value = value;
  177.     }
  179.     // 返回左子树的高度
  180.     public int leftHeight() {
  181.         if (left == null) {
  182.             return 0;
  183.         }
  184.         return left.height();
  185.     }
  187.     // 返回右子树的高度
  188.     public int rightHeight() {
  189.         if (right == null) {
  190.             return 0;
  191.         }
  192.         return right.height();
  193.     }
  195.     // 返回 以该结点为根结点的树的高度
  196.     public int height() {
  197.         return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
  198.     }
  200.     //左旋转方法
  201.     private void leftRotate() {
  203.         //创建新的结点，以当前根结点的值
  204.         Node newNode = new Node(value);
  205.         //把新的结点的左子树设置成当前结点的左子树
  206.         newNode.left = left;
  207.         //把新的结点的右子树设置成带你过去结点的右子树的左子树
  208.         newNode.right = right.left;
  209.         //把当前结点的值替换成右子结点的值
  210.         value = right.value;
  211.         //把当前结点的右子树设置成当前结点右子树的右子树
  212.         right = right.right;
  213.         //把当前结点的左子树(左子结点)设置成新的结点
  214.         left = newNode;
  217.     }
  219.     //右旋转
  220.     private void rightRotate() {
  221.         Node newNode = new Node(value);
  222.         newNode.right = right;
  223.         newNode.left = left.right;
  224.         value = left.value;
  225.         left = left.left;
  226.         right = newNode;
  227.     }
  229.     // 查找要删除的结点
  230.     /**
  231.      * 
  232.      * @param value
  233.      *            希望删除的结点的值
  234.      * @return 如果找到返回该结点，否则返回null
  235.      */
  236.     public Node search(int value) {
  237.         if (value == this.value) { // 找到就是该结点
  238.             return this;
  239.         } else if (value < this.value) {// 如果查找的值小于当前结点，向左子树递归查找
  240.             // 如果左子结点为空
  241.             if (this.left == null) {
  242.                 return null;
  243.             }
  244.             return this.left.search(value);
  245.         } else { // 如果查找的值不小于当前结点，向右子树递归查找
  246.             if (this.right == null) {
  247.                 return null;
  248.             }
  249.             return this.right.search(value);
  250.         }
  251.     }
  253.     // 查找要删除结点的父结点
  254.     /**
  255.      * 
  256.      * @param value
  257.      *            要找到的结点的值
  258.      * @return 返回的是要删除的结点的父结点，如果没有就返回null
  259.      */
  260.     public Node searchParent(int value) {
  261.         // 如果当前结点就是要删除的结点的父结点，就返回
  262.         if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
  263.             return this;
  264.         } else {
  265.             // 如果查找的值小于当前结点的值, 并且当前结点的左子结点不为空
  266.             if (value < this.value && this.left != null) {
  267.                 return this.left.searchParent(value); // 向左子树递归查找
  268.             } else if (value >= this.value && this.right != null) {
  269.                 return this.right.searchParent(value); // 向右子树递归查找
  270.             } else {
  271.                 return null; // 没有找到父结点
  272.             }
  273.         }
  274.     }
  276.     @Override
  277.     public String toString() {
  278.         return "Node [value=" + value + "]";
  279.     }
  281.     // 添加结点的方法
  282.     // 递归的形式添加结点，注意需要满足二叉排序树的要求
  283.     public void add(Node node) {
  284.         if (node == null) {
  285.             return;
  286.         }
  288.         // 判断传入的结点的值，和当前子树的根结点的值关系
  289.         if (node.value < this.value) {
  290.             // 如果当前结点左子结点为null
  291.             if (this.left == null) {
  292.                 this.left = node;
  293.             } else {
  294.                 // 递归的向左子树添加
  295.                 this.left.add(node);
  296.             }
  297.         } else { // 添加的结点的值大于 当前结点的值
  298.             if (this.right == null) {
  299.                 this.right = node;
  300.             } else {
  301.                 // 递归的向右子树添加
  302.                 this.right.add(node);
  303.             }
  304.         }
  306.         //当添加完一个结点后，如果: (右子树的高度-左子树的高度) > 1 , 左旋转
  307.         if(rightHeight() - leftHeight() > 1) {
  308.             //如果它的右子树的左子树的高度大于它的右子树的右子树的高度
  309.             if(right != null && right.leftHeight() > right.rightHeight()) {
  310.                 //先对右子结点进行右旋转
  311.                 right.rightRotate();
  312.                 //然后在对当前结点进行左旋转
  313.                 leftRotate(); //左旋转..
  314.             } else {
  315.                 //直接进行左旋转即可
  316.                 leftRotate();
  317.             }
  318.             return ; //必须要!!!
  319.         }
  321.         //当添加完一个结点后，如果 (左子树的高度 - 右子树的高度) > 1, 右旋转
  322.         if(leftHeight() - rightHeight() > 1) {
  323.             //如果它的左子树的右子树高度大于它的左子树的高度
  324.             if(left != null && left.rightHeight() > left.leftHeight()) {
  325.                 //先对当前结点的左结点(左子树)->左旋转
  326.                 left.leftRotate();
  327.                 //再对当前结点进行右旋转
  328.                 rightRotate();
  329.             } else {
  330.                 //直接进行右旋转即可
  331.                 rightRotate();
  332.             }
  333.         }
  334.     }
  336.     // 中序遍历
  337.     public void infixOrder() {
  338.         if (this.left != null) {
  339.             this.left.infixOrder();
  340.         }
  341.         System.out.println(this);
  342.         if (this.right != null) {
  343.             this.right.infixOrder();
  344.         }
  345.     }
  346. }

9.4 多路查找树

  • B树：

    1. B 树通过重新组织节点， 降低了树的高度
    2. 文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页(页得大小通常为4k)，这样每个节点只需要一次 I/O 就可以完全载入
    3. 将树的度 M 设置为 1024，在 600 亿个元素中最多只需要 4 次 I/O 操作就可以读取到想要的元素, B树(B+)广泛应用于文件存储系统以及数据库系统中

  • 2-3树：

    1. 2-3 树的所有叶子节点都在同一层.(只要是 B 树都满足这个条件)
    2. 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点
    3. 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点
    4. 2-3 树是由二节点和三节点构成的树

Java数据结构与算法-尚硅谷 - 图30

  • 2-3树插入规则：

    1. 2-3 树的所有叶子节点都在同一层.(只要是 B 树都满足这个条件)
    2. 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点. 3) 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点
    3. 当按照规则插入一个数到某个节点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满，则拆本层，拆后仍然需要满足上面 3 个条件
    4. 对于三节点的子树的值大小仍然遵守(BST二叉树排序)规则

  • B树特点：

    1. B 树的阶：节点的最多子节点个数
    2. B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点
    3. 关键字集合分布在整颗树中, 即叶子节点和非叶子节点都存放数据
    4. 搜索有可能在非叶子结点结束
    5. 其搜索性能等价于在关键字全集内做一次二分查找
      Java数据结构与算法-尚硅谷 - 图31

  • B+树：

    1. B+树的搜索与 B 树也基本相同，区别是 B+树只有达到叶子结点才命中（B 树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找
    2. 所有关键字都出现在叶子结点的链表中（即数据只能在叶子节点【也叫稠密索引】），且链表中的关键字(数据)恰好是有序的
    3. 不可能在非叶子结点命中
    4. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层
      Java数据结构与算法-尚硅谷 - 图32

  • B*树：

    1. B_树定义了非叶子结点关键字个数至少为(2/3)_M，即块的最低使用率为 2/3，而B+树的块的最低使用率为的1/2
    2. 从第 1 个特点我们可以看出，B*树分配新结点的概率比 B+
      Java数据结构与算法-尚硅谷 - 图33

10 图


  • Java数据结构与算法-尚硅谷 - 图34

    邻接矩阵：


  • Java数据结构与算法-尚硅谷 - 图35

    邻接表：

  1. public class Graph {
  3.     private ArrayList<String> vertexList; //存储顶点集合
  4.     private int[][] edges; //存储图对应的邻结矩阵
  5.     private int numOfEdges; //表示边的数目
  6.     //定义给数组boolean[], 记录某个结点是否被访问
  7.     private boolean[] isVisited;
  9.     public static void main(String[] args) {
  10.         //测试一把图是否创建ok
  11.         int n = 8;  //结点的个数
  12.         //String Vertexs[] = {"A", "B", "C", "D", "E"};
  13.         String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
  15.         //创建图对象
  16.         Graph graph = new Graph(n);
  17.         //循环的添加顶点
  18.         for (String vertex : Vertexs) {
  19.             graph.insertVertex(vertex);
  20.         }
  22.         //添加边
  23.         //A-B A-C B-C B-D B-E 
  24. //    graph.insertEdge(0, 1, 1); // A-B
  25. //    graph.insertEdge(0, 2, 1); // 
  26. //    graph.insertEdge(1, 2, 1); // 
  27. //    graph.insertEdge(1, 3, 1); // 
  28. //    graph.insertEdge(1, 4, 1); // 
  30.         //更新边的关系
  31.         graph.insertEdge(0, 1, 1);
  32.         graph.insertEdge(0, 2, 1);
  33.         graph.insertEdge(1, 3, 1);
  34.         graph.insertEdge(1, 4, 1);
  35.         graph.insertEdge(3, 7, 1);
  36.         graph.insertEdge(4, 7, 1);
  37.         graph.insertEdge(2, 5, 1);
  38.         graph.insertEdge(2, 6, 1);
  39.         graph.insertEdge(5, 6, 1);
  42.         //显示一把邻结矩阵
  43.         graph.showGraph();
  45.         //测试一把，我们的dfs遍历是否ok
  46.         System.out.println("深度遍历");
  47.         graph.dfs(); // A->B->C->D->E [1->2->4->8->5->3->6->7]
  48. //    System.out.println();
  49.         System.out.println("广度优先!");
  50.         graph.bfs(); // A->B->C->D-E [1->2->3->4->5->6->7->8]
  52.     }
  54.     //构造器
  55.     public Graph(int n) {
  56.         //初始化矩阵和vertexList
  57.         edges = new int[n][n];
  58.         vertexList = new ArrayList<String>(n);
  59.         numOfEdges = 0;
  61.     }
  63.     //得到第一个邻接结点的下标 w 
  65.     /**
  66.      * @param index
  67.      * @return 如果存在就返回对应的下标，否则返回-1
  68.      */
  69.     public int getFirstNeighbor(int index) {
  70.         for (int j = 0; j < vertexList.size(); j++) {
  71.             if (edges[index][j] > 0) {
  72.                 return j;
  73.             }
  74.         }
  75.         return -1;
  76.     }
  78.     //根据前一个邻接结点的下标来获取下一个邻接结点
  79.     public int getNextNeighbor(int v1, int v2) {
  80.         for (int j = v2 + 1; j < vertexList.size(); j++) {
  81.             if (edges[v1][j] > 0) {
  82.                 return j;
  83.             }
  84.         }
  85.         return -1;
  86.     }
  88.     //深度优先遍历算法
  89.     //i 第一次就是 0
  90.     private void dfs(boolean[] isVisited, int i) {
  91.         //首先我们访问该结点,输出
  92.         System.out.print(getValueByIndex(i) + "->");
  93.         //将结点设置为已经访问
  94.         isVisited[i] = true;
  95.         //查找结点i的第一个邻接结点w
  96.         int w = getFirstNeighbor(i);
  97.         while (w != -1) {//说明有
  98.             if (!isVisited[w]) {
  99.                 dfs(isVisited, w);
  100.             }
  101.             //如果w结点已经被访问过
  102.             w = getNextNeighbor(i, w);
  103.         }
  105.     }
  107.     //对dfs 进行一个重载, 遍历我们所有的结点，并进行 dfs
  108.     public void dfs() {
  109.         isVisited = new boolean[vertexList.size()];
  110.         //遍历所有的结点，进行dfs[回溯]
  111.         for (int i = 0; i < getNumOfVertex(); i++) {
  112.             if (!isVisited[i]) {
  113.                 dfs(isVisited, i);
  114.             }
  115.         }
  116.     }
  118.     //对一个结点进行广度优先遍历的方法
  119.     private void bfs(boolean[] isVisited, int i) {
  120.         int u; // 表示队列的头结点对应下标
  121.         int w; // 邻接结点w
  122.         //队列，记录结点访问的顺序
  123.         LinkedList queue = new LinkedList();
  124.         //访问结点，输出结点信息
  125.         System.out.print(getValueByIndex(i) + "=>");
  126.         //标记为已访问
  127.         isVisited[i] = true;
  128.         //将结点加入队列
  129.         queue.addLast(i);
  131.         while (!queue.isEmpty()) {
  132.             //取出队列的头结点下标
  133.             u = (Integer) queue.removeFirst();
  134.             //得到第一个邻接结点的下标 w 
  135.             w = getFirstNeighbor(u);
  136.             while (w != -1) {//找到
  137.                 //是否访问过
  138.                 if (!isVisited[w]) {
  139.                     System.out.print(getValueByIndex(w) + "=>");
  140.                     //标记已经访问
  141.                     isVisited[w] = true;
  142.                     //入队
  143.                     queue.addLast(w);
  144.                 }
  145.                 //以u为前驱点，找w后面的下一个邻结点
  146.                 w = getNextNeighbor(u, w); //体现出我们的广度优先
  147.             }
  148.         }
  150.     }
  152.     //遍历所有的结点，都进行广度优先搜索
  153.     public void bfs() {
  154.         isVisited = new boolean[vertexList.size()];
  155.         for (int i = 0; i < getNumOfVertex(); i++) {
  156.             if (!isVisited[i]) {
  157.                 bfs(isVisited, i);
  158.             }
  159.         }
  160.     }
  162.     //图中常用的方法
  163.     //返回结点的个数
  164.     public int getNumOfVertex() {
  165.         return vertexList.size();
  166.     }
  168.     //显示图对应的矩阵
  169.     public void showGraph() {
  170.         for (int[] link : edges) {
  171.             System.err.println(Arrays.toString(link));
  172.         }
  173.     }
  175.     //得到边的数目
  176.     public int getNumOfEdges() {
  177.         return numOfEdges;
  178.     }
  180.     //返回结点i(下标)对应的数据 0->"A" 1->"B" 2->"C"
  181.     public String getValueByIndex(int i) {
  182.         return vertexList.get(i);
  183.     }
  185.     //返回v1和v2的权值
  186.     public int getWeight(int v1, int v2) {
  187.         return edges[v1][v2];
  188.     }
  190.     //插入结点
  191.     public void insertVertex(String vertex) {
  192.         vertexList.add(vertex);
  193.     }
  194.     //添加边
  196.     /**
  197.      * @param v1     表示点的下标即使第几个顶点  "A"-"B" "A"->0 "B"->1
  198.      * @param v2     第二个顶点对应的下标
  199.      * @param weight 表示
  200.      */
  201.     public void insertEdge(int v1, int v2, int weight) {
  202.         edges[v1][v2] = weight;
  203.         edges[v2][v1] = weight;
  204.         numOfEdges++;
  205.     }
  206. }

10.1 深度优先

Java数据结构与算法-尚硅谷 - 图36

  1. //深度优先遍历算法
  2.     //i 第一次就是 0
  3.     private void dfs(boolean[] isVisited, int i) {
  4.         //首先我们访问该结点,输出
  5.         System.out.print(getValueByIndex(i) + "->");
  6.         //将结点设置为已经访问
  7.         isVisited[i] = true;
  8.         //查找结点i的第一个邻接结点w
  9.         int w = getFirstNeighbor(i);
  10.         while (w != -1) {//说明有
  11.             if (!isVisited[w]) {
  12.                 dfs(isVisited, w);
  13.             }
  14.             //如果w结点已经被访问过
  15.             w = getNextNeighbor(i, w);
  16.         }
  18.     }
  20.     //对dfs 进行一个重载, 遍历我们所有的结点，并进行 dfs
  21.     public void dfs() {
  22.         isVisited = new boolean[vertexList.size()];
  23.         //遍历所有的结点，进行dfs[回溯]
  24.         for (int i = 0; i < getNumOfVertex(); i++) {
  25.             if (!isVisited[i]) {
  26.                 dfs(isVisited, i);
  27.             }
  28.         }
  29.     }

10.2 广度优先

Java数据结构与算法-尚硅谷 - 图37

  1. //对一个结点进行广度优先遍历的方法
  2.     private void bfs(boolean[] isVisited, int i) {
  3.         int u; // 表示队列的头结点对应下标
  4.         int w; // 邻接结点w
  5.         //队列，记录结点访问的顺序
  6.         LinkedList queue = new LinkedList();
  7.         //访问结点，输出结点信息
  8.         System.out.print(getValueByIndex(i) + "=>");
  9.         //标记为已访问
  10.         isVisited[i] = true;
  11.         //将结点加入队列
  12.         queue.addLast(i);
  14.         while (!queue.isEmpty()) {
  15.             //取出队列的头结点下标
  16.             u = (Integer) queue.removeFirst();
  17.             //得到第一个邻接结点的下标 w
  18.             w = getFirstNeighbor(u);
  19.             while (w != -1) {//找到
  20.                 //是否访问过
  21.                 if (!isVisited[w]) {
  22.                     System.out.print(getValueByIndex(w) + "=>");
  23.                     //标记已经访问
  24.                     isVisited[w] = true;
  25.                     //入队
  26.                     queue.addLast(w);
  27.                 }
  28.                 //以u为前驱点，找w后面的下一个邻结点
  29.                 w = getNextNeighbor(u, w); //体现出我们的广度优先
  30.             }
  31.         }
  33.     }
  35.     //遍历所有的结点，都进行广度优先搜索
  36.     public void bfs() {
  37.         isVisited = new boolean[vertexList.size()];
  38.         for (int i = 0; i < getNumOfVertex(); i++) {
  39.             if (!isVisited[i]) {
  40.                 bfs(isVisited, i);
  41.             }
  42.         }
  43.     }

11 常用算法

11.1 二分查找(非递归)

  • 代码：

    1. public class BinarySearchNoRecur {
    3. public static void main(String[] args) {
    4.     //测试
    5.     int[] arr = {1, 3, 8, 10, 11, 67, 100};
    6.     int index = binarySearch(arr, 100);
    7.     System.out.println("index=" + index);//
    8. }
    10. //二分查找的非递归实现
    12. /**
    13.  * @param arr    待查找的数组, arr是升序排序
    14.  * @param target 需要查找的数
    15.  * @return 返回对应下标，-1表示没有找到
    16.  */
    17. public static int binarySearch(int[] arr, int target) {
    19.     int left = 0;
    20.     int right = arr.length - 1;
    21.     while (left <= right) { //说明继续查找
    22.         int mid = (left + right) / 2;
    23.         if (arr[mid] == target) {
    24.             return mid;
    25.         } else if (arr[mid] > target) {
    26.             right = mid - 1;//需要向左边查找
    27.         } else {
    28.             left = mid + 1; //需要向右边查找
    29.         }
    30.     }
    31.     return -1;
    32. }
    33. }

11.2 分治算法


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

    基本介绍：

    1. 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
    2. 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
    3. 合并：将各个子问题的解合并为原问题的解

  • 思路：

    1. 如果是有一个盘， A->C
      如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的盘 2. 上面的盘
    2. 先把 最上面的盘 A->B
    3. 把最下边的盘 A->C
    4. 把 B塔的所有盘 从 B->C

  • 代码：

    1. public class Hanoitower {
    3. public static void main(String[] args) {
    4.     hanoiTower(10, 'A', 'B', 'C');
    5. }
    7. //汉诺塔的移动的方法
    8. //使用分治算法
    10. public static void hanoiTower(int num, char a, char b, char c) {
    11.     //如果只有一个盘
    12.     if (num == 1) {
    13.         System.out.println("第1个盘从 " + a + "->" + c);
    14.     } else {
    15.         //如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的一个盘 2. 上面的所有盘
    16.         //1. 先把 最上面的所有盘 A->B， 移动过程会使用到 c
    17.         hanoiTower(num - 1, a, c, b);
    18.         //2. 把最下边的盘 A->C
    19.         System.out.println("第" + num + "个盘从 " + a + "->" + c);
    20.         //3. 把B塔的所有盘 从 B->C , 移动过程使用到 a塔
    21.         hanoiTower(num - 1, b, a, c);
    23.     }
    24. }
    25. }

11.3 动态规划

  • 基本介绍：

    1. 动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法
    2. 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解
    3. 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
    4. 动态规划可以通过填表的方式来逐步推进，得到最优解


  • Java数据结构与算法-尚硅谷 - 图38

    思路：

    1. 背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。其中又分 01 背包和完全背包(完全背包指的是：每种物品都有无限件可用)
    2. 这里的问题属于 01 背包，即每个物品最多放一个。而无限背包可以转化为 01 背包
    3. 算法的主要思想，利用动态规划来解决。每次遍历到的第 i 个物品，根据 w[i]和 v[i]来确定是否需要将该物品
      放入背包中。即对于给定的 n 个物品，设 v[i]、w[i]分别为第 i 个物品的价值和重量，C 为背包的容量。再令 v[i][j]
      表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值

Java数据结构与算法-尚硅谷 - 图39

  • 代码：

    ```java public class KnapsackProblem {

    public static void main(String[] args) { // TODO Auto-generated method stub int[] w = {1, 4, 3};//物品的重量 int[] val = {1500, 3000, 2000}; //物品的价值 这里val[i] 就是前面讲的v[i] int m = 4; //背包的容量 int n = val.length; //物品的个数

  1.   //创建二维数组，
  2.   //v[i][j] 表示在前i个物品中能够装入容量为j的背包中的最大价值
  3.   int[][] v = new int[n + 1][m + 1];
  4.   //为了记录放入商品的情况，我们定一个二维数组
  5.   int[][] path = new int[n + 1][m + 1];
  7.   //初始化第一行和第一列, 这里在本程序中，可以不去处理，因为默认就是0
  8.   for (int i = 0; i < v.length; i++) {
  9.      v[i][0] = 0; //将第一列设置为0
  10.   }
  11.   for (int i = 0; i < v[0].length; i++) {
  12.      v[0][i] = 0; //将第一行设置0
  13.   }
  16.   //根据前面得到公式来动态规划处理
  17.   for (int i = 1; i < v.length; i++) { //不处理第一行 i是从1开始的
  18.      for (int j = 1; j < v[0].length; j++) {//不处理第一列, j是从1开始的
  19.         //公式
  20.         if (w[i - 1] > j) { // 因为我们程序i 是从1开始的，因此原来公式中的 w[i] 修改成 w[i-1]
  21.            v[i][j] = v[i - 1][j];
  22.         } else {
  23.            //说明:
  24.            //因为我们的i 从1开始的， 因此公式需要调整成
  25.            //v[i][j]=Math.max(v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]);
  26.            //v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
  27.            //为了记录商品存放到背包的情况，我们不能直接的使用上面的公式，需要使用if-else来体现公式
  28.            if (v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
  29.               v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
  30.               //把当前的情况记录到path
  31.               path[i][j] = 1;
  32.            } else {
  33.               v[i][j] = v[i - 1][j];
  34.            }
  36.         }
  37.      }
  38.   }
  40.   //输出一下v 看看目前的情况
  41.   for (int i = 0; i < v.length; i++) {
  42.      for (int j = 0; j < v[i].length; j++) {
  43.         System.out.print(v[i][j] + " ");
  44.      }
  45.      System.out.println();
  46.   }
  48.   System.out.println("============================");
  49.   //输出最后我们是放入的哪些商品
  50.   //遍历path, 这样输出会把所有的放入情况都得到, 其实我们只需要最后的放入

// for(int i = 0; i < path.length; i++) { // for(int j=0; j < path[i].length; j++) { // if(path[i][j] == 1) { // System.out.printf(“第%d个商品放入到背包\n”, i); // } // } // }

  1.   //动脑筋
  2.   int i = path.length - 1; //行的最大下标
  3.   int j = path[0].length - 1;  //列的最大下标
  4.   while (i > 0 && j > 0) { //从path的最后开始找
  5.      if (path[i][j] == 1) {
  6.         System.out.printf("第%d个商品放入到背包\n", i);
  7.         j -= w[i - 1]; //w[i-1]
  8.      }
  9.      i--;
  10.   }

} }

  3. <a name="791ea0b8"></a>
  4. ## 11.4 KMP
  6. -   
  7. <a name="568dc93e-13"></a>
  8. #### 基本介绍：
  10.    1. KMP 是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法
  11.    2. Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法”，常用于在一个文本串 S 内查找一个模式串 P 的<br />出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，故取这 3 人的<br />姓氏命名此算法.
  12.    3. KMP 方法算法就利用之前判断过信息，通过一个 next 数组，保存模式串中前后最长公共子序列的长度，每次<br />回溯时，通过 next 数组找到，前面匹配过的位置，省去了大量的计算时间
  13. -  <br />[https://blog.csdn.net/v_JULY_v/article/details/7041827?ops_request_misc=%7B%22request%5Fid%22%3A%22166331315916782417047476%22%2C%22scm%22%3A%2220140713.130102334..%22%7D&request_id=166331315916782417047476&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2](https://blog.csdn.net/v_JULY_v/article/details/7041827?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522166331315916782417047476%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=166331315916782417047476&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2)alltop_positive~default-1-7041827-null-null.142v47pc_rank_34_default_23,201v3control_2&utm_term=kmp&spm=1018.2226.3001.4187 
  14. <a name="4f7d0e2b-4"></a>
  15. #### 思路：
  17. -  <br />[https://www.zhihu.com/zvideo/1376978253073182720](https://www.zhihu.com/zvideo/1376978253073182720) 
  18. <a name="99bc5cde"></a>
  19. #### 动画：
  21. -   
  22. <a name="4cf6fd20-3"></a>
  23. #### 代码：
  24. ```java
  25. public class KMPAlgorithm {
  27.    public static void main(String[] args) {
  28.       // TODO Auto-generated method stub
  29.       String str1 = "BBC ABCDAB ABCDABCDABDE";
  30.       String str2 = "ABCDABD";
  31.       //String str2 = "BBC";
  33.       int[] next = kmpNext("ABCDABD"); //[0, 1, 2, 0]
  34.       System.out.println("next=" + Arrays.toString(next));
  36.       int index = kmpSearch(str1, str2, next);
  37.       System.out.println("index=" + index); // 15了  
  38.    }
  40.    //写出我们的kmp搜索算法
  41.    /**
  42.     * 
  43.     * @param str1 源字符串
  44.     * @param str2 子串
  45.     * @param next 部分匹配表, 是子串对应的部分匹配表
  46.     * @return 如果是-1就是没有匹配到，否则返回第一个匹配的位置
  47.     */
  48.    public static int kmpSearch(String str1, String str2, int[] next) {
  50.       //遍历 
  51.       for(int i = 0, j = 0; i < str1.length(); i++) {
  53.          //需要处理 str1.charAt(i) ！= str2.charAt(j), 去调整j的大小
  54.          //KMP算法核心点, 可以验证...
  55.          while( j > 0 && str1.charAt(i) != str2.charAt(j)) {
  56.             j = next[j-1]; 
  57.          }
  59.          if(str1.charAt(i) == str2.charAt(j)) {
  60.             j++;
  61.          }        
  62.          if(j == str2.length()) {//找到了 // j = 3 i 
  63.             return i - j + 1;
  64.          }
  65.       }
  66.       return  -1;
  67.    }
  69.    //获取到一个字符串(子串) 的部分匹配值表
  70.    public static  int[] kmpNext(String dest) {
  71.       //创建一个next 数组保存部分匹配值
  72.       int[] next = new int[dest.length()];
  73.       next[0] = 0; //如果字符串是长度为1 部分匹配值就是0
  74.       for(int i = 1, j = 0; i < dest.length(); i++) {
  75.          //当dest.charAt(i) != dest.charAt(j) ，我们需要从next[j-1]获取新的j
  76.          //直到我们发现 有  dest.charAt(i) == dest.charAt(j)成立才退出
  77.          //这时kmp算法的核心点
  78.          while(j > 0 && dest.charAt(i) != dest.charAt(j)) {
  79.             j = next[j-1];
  80.          }
  82.          //当dest.charAt(i) == dest.charAt(j) 满足时，部分匹配值就是+1
  83.          if(dest.charAt(i) == dest.charAt(j)) {
  84.             j++;
  85.          }
  86.          next[i] = j;
  87.       }
  88.       return next;
  89.    }
  90. }

11.5 贪心算法

  • 基本介绍：

    1. 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法
    2. 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果


  • Java数据结构与算法-尚硅谷 - 图40

    思路：

    1. 遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关系）
    2. 将这个电台加入到一个集合中(比如ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
    3. 重复第 1 步直到覆盖了全部的地区

  • 代码：

    ```java public class GreedyAlgorithm {

    public static void main(String[] args) { //创建广播电台,放入到Map HashMap> broadcasts = new HashMap>(); //将各个电台放入到broadcasts HashSet hashSet1 = new HashSet(); hashSet1.add(“北京”); hashSet1.add(“上海”); hashSet1.add(“天津”);

    HashSet hashSet2 = new HashSet(); hashSet2.add(“广州”); hashSet2.add(“北京”); hashSet2.add(“深圳”);

    HashSet hashSet3 = new HashSet(); hashSet3.add(“成都”); hashSet3.add(“上海”); hashSet3.add(“杭州”);

  1.   HashSet<String> hashSet4 = new HashSet<String>();
  2.   hashSet4.add("上海");
  3.   hashSet4.add("天津");
  5.   HashSet<String> hashSet5 = new HashSet<String>();
  6.   hashSet5.add("杭州");
  7.   hashSet5.add("大连");
  9.   //加入到map
  10.   broadcasts.put("K1", hashSet1);
  11.   broadcasts.put("K2", hashSet2);
  12.   broadcasts.put("K3", hashSet3);
  13.   broadcasts.put("K4", hashSet4);
  14.   broadcasts.put("K5", hashSet5);
  16.   //allAreas 存放所有的地区
  17.   HashSet<String> allAreas = new HashSet<String>();
  18.   allAreas.add("北京");
  19.   allAreas.add("上海");
  20.   allAreas.add("天津");
  21.   allAreas.add("广州");
  22.   allAreas.add("深圳");
  23.   allAreas.add("成都");
  24.   allAreas.add("杭州");
  25.   allAreas.add("大连");
  27.   //创建ArrayList, 存放选择的电台集合
  28.   ArrayList<String> selects = new ArrayList<String>();
  30.   //定义一个临时的集合， 在遍历的过程中，存放遍历过程中的电台覆盖的地区和当前还没有覆盖的地区的交集
  31.   HashSet<String> tempSet = new HashSet<String>();
  33.   //定义给maxKey ， 保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的电台的key
  34.   //如果maxKey 不为null , 则会加入到 selects
  35.   String maxKey = null;
  36.   while(allAreas.size() != 0) { // 如果allAreas 不为0, 则表示还没有覆盖到所有的地区
  37.      //每进行一次while,需要
  38.      maxKey = null;
  40.      //遍历 broadcasts, 取出对应key
  41.      for(String key : broadcasts.keySet()) {
  42.         //每进行一次for
  43.         tempSet.clear();
  44.         //当前这个key能够覆盖的地区
  45.         HashSet<String> areas = broadcasts.get(key);
  46.         tempSet.addAll(areas);
  47.         //求出tempSet 和   allAreas 集合的交集, 交集会赋给 tempSet
  48.         tempSet.retainAll(allAreas);
  49.         //如果当前这个集合包含的未覆盖地区的数量，比maxKey指向的集合地区还多
  50.         //就需要重置maxKey
  51.         // tempSet.size() >broadcasts.get(maxKey).size()) 体现出贪心算法的特点,每次都选择最优的
  52.         if(tempSet.size() > 0 && 
  53.               (maxKey == null || tempSet.size() >broadcasts.get(maxKey).size())){
  54.            maxKey = key;
  55.         }
  56.      }
  57.      //maxKey != null, 就应该将maxKey 加入selects
  58.      if(maxKey != null) {
  59.         selects.add(maxKey);
  60.         //将maxKey指向的广播电台覆盖的地区，从 allAreas 去掉
  61.         allAreas.removeAll(broadcasts.get(maxKey));
  62.      }
  64.   }
  66.   System.out.println("得到的选择结果是" + selects);//[K1,K2,K3,K5]

} }

  3. <a name="efe4f4f3"></a>
  4. ## 11.6 普里姆算法
  6. -  <br />普利姆(Prim)算法求最小生成树，也就是在包含 n 个顶点的连通图中，找出只有(n-1)条边包含所有 n 个顶点的连通子图，也就是所谓的极小连通子图 
  7. <a name="568dc93e-15"></a>
  8. #### 基本介绍：
  10. -   
  11. <a name="4f7d0e2b-6"></a>
  12. #### 思路：
  14. ![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-09-16%2015.49.47.jpg#id=HtWjQ&originHeight=928&originWidth=2250&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=)
  16. ![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-09-16%2015.50.34.jpg#id=fLHca&originHeight=844&originWidth=2134&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=)
  18. 普利姆的算法如下:
  20. 1. 设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U是顶点集合，E,D是边的集合
  21. 2. 若从顶点 u 开始构造最小生成树，则从集合V中取出顶点 u 放入集合U中，标记顶点 v 的 visited[u]=1
  22. 3. 若集合U中顶点 ui 与集合V-U中的顶点 vj 之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将<br />顶点 vj 加入集合U中，将边（ui,vj）加入集合D中，标记 visited[vj]=1
  23. 4. 重复步骤②，直到U与V相等，即所有顶点都被标记为访问过，此时D中有 n-1 条边
  25. -   
  26. <a name="4cf6fd20-5"></a>
  27. #### 代码：
  28. ```java
  29. public class PrimAlgorithm {
  31.    public static void main(String[] args) {
  32.       //测试看看图是否创建ok
  33.       char[] data = new char[]{'A','B','C','D','E','F','G'};
  34.       int verxs = data.length;
  35.       //邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
  36.       int [][]weight=new int[][]{
  37.             {10000,5,7,10000,10000,10000,2},
  38.             {5,10000,10000,9,10000,10000,3},
  39.             {7,10000,10000,10000,8,10000,10000},
  40.             {10000,9,10000,10000,10000,4,10000},
  41.             {10000,10000,8,10000,10000,5,4},
  42.             {10000,10000,10000,4,5,10000,6},
  43.             {2,3,10000,10000,4,6,10000},};
  45.         //创建MGraph对象
  46.         MGraph graph = new MGraph(verxs);
  47.         //创建一个MinTree对象
  48.         MinTree minTree = new MinTree();
  49.         minTree.createGraph(graph, verxs, data, weight);
  50.         //输出
  51.         minTree.showGraph(graph);
  52.         //测试普利姆算法
  53.         minTree.prim(graph, 1);// 
  54.    }
  56. }
  58. //创建最小生成树->村庄的图
  59. class MinTree {
  60.    //创建图的邻接矩阵
  61.    /**
  62.     * 
  63.     * @param graph 图对象
  64.     * @param verxs 图对应的顶点个数
  65.     * @param data 图的各个顶点的值
  66.     * @param weight 图的邻接矩阵
  67.     */
  68.    public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) {
  69.       int i, j;
  70.       for(i = 0; i < verxs; i++) {//顶点
  71.          graph.data[i] = data[i];
  72.          for(j = 0; j < verxs; j++) {
  73.             graph.weight[i][j] = weight[i][j];
  74.          }
  75.       }
  76.    }
  78.    //显示图的邻接矩阵
  79.    public void showGraph(MGraph graph) {
  80.       for(int[] link: graph.weight) {
  81.          System.out.println(Arrays.toString(link));
  82.       }
  83.    }
  85.    //编写prim算法，得到最小生成树
  86.    /**
  87.     * 
  88.     * @param graph 图
  89.     * @param v 表示从图的第几个顶点开始生成'A'->0 'B'->1...
  90.     */
  91.    public void prim(MGraph graph, int v) {
  92.       //visited[] 标记结点(顶点)是否被访问过
  93.       int visited[] = new int[graph.verxs];
  94.       //visited[] 默认元素的值都是0, 表示没有访问过
  95. //    for(int i =0; i <graph.verxs; i++) {
  96. //       visited[i] = 0;
  97. //    }
  99.       //把当前这个结点标记为已访问
  100.       visited[v] = 1;
  101.       //h1 和 h2 记录两个顶点的下标
  102.       int h1 = -1;
  103.       int h2 = -1;
  104.       int minWeight = 10000; //将 minWeight 初始成一个大数，后面在遍历过程中，会被替换
  105.       for(int k = 1; k < graph.verxs; k++) {//因为有 graph.verxs顶点，普利姆算法结束后，有 graph.verxs-1边
  107.          //这个是确定每一次生成的子图 ，和哪个结点的距离最近
  108.          for(int i = 0; i < graph.verxs; i++) {// i结点表示被访问过的结点
  109.             for(int j = 0; j< graph.verxs;j++) {//j结点表示还没有访问过的结点
  110.                if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
  111.                   //替换minWeight(寻找已经访问过的结点和未访问过的结点间的权值最小的边)
  112.                   minWeight = graph.weight[i][j];
  113.                   h1 = i;
  114.                   h2 = j;
  115.                }
  116.             }
  117.          }
  118.          //找到一条边是最小
  119.          System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值:" + minWeight);
  120.          //将当前这个结点标记为已经访问
  121.          visited[h2] = 1;
  122.          //minWeight 重新设置为最大值 10000
  123.          minWeight = 10000;
  124.       }
  126.    }
  127. }
  129. class MGraph {
  130.    int verxs; //表示图的节点个数
  131.    char[] data;//存放结点数据
  132.    int[][] weight; //存放边，就是我们的邻接矩阵
  134.    public MGraph(int verxs) {
  135.       this.verxs = verxs;
  136.       data = new char[verxs];
  137.       weight = new int[verxs][verxs];
  138.    }
  139. }

11.7 克鲁斯卡

  • 基本介绍：

    1. 克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
    2. 基本思想：按照权值从小到大的顺序选择 n-1 条边，并保证这 n-1 条边不构成回路
    3. 具体做法：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森
      林中不产生回路，直至森林变成一棵树为止


  • Java数据结构与算法-尚硅谷 - 图41
    Java数据结构与算法-尚硅谷 - 图42

    思路分析：

  • 代码：

    ```java public class KruskalCase {

    private int edgeNum; //边的个数 private char[] vertexs; //顶点数组 private int[][] matrix; //邻接矩阵 //使用 INF 表示两个顶点不能连通 private static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) { char[] vertexs = {‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’}; //克鲁斯卡尔算法的邻接矩阵 

    1.  int matrix[][] = {
    2.  /*A*//*B*//*C*//*D*//*E*//*F*//*G*/

    /A/ { 0, 12, INF, INF, INF, 16, 14}, /B/ { 12, 0, 10, INF, INF, 7, INF}, /C/ { INF, 10, 0, 3, 5, 6, INF}, /D/ { INF, INF, 3, 0, 4, INF, INF}, /E/ { INF, INF, 5, 4, 0, 2, 8}, /F/ { 16, 7, 6, INF, 2, 0, 9}, /G/ { 14, INF, INF, INF, 8, 9, 0}}; 

    1.  //大家可以在去测试其它的邻接矩阵，结果都可以得到最小生成树.
    3.  //创建KruskalCase 对象实例
    4.  KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
    5.  //输出构建的
    6.  kruskalCase.print();
    7.  kruskalCase.kruskal();

    }

    //构造器 public KruskalCase(char[] vertexs, int[][] matrix) { //初始化顶点数和边的个数 int vlen = vertexs.length;

    //初始化顶点, 复制拷贝的方式 this.vertexs = new char[vlen]; for(int i = 0; i < vertexs.length; i++) {

    1.  this.vertexs[i] = vertexs[i];

    }

    //初始化边, 使用的是复制拷贝的方式 this.matrix = new int[vlen][vlen]; for(int i = 0; i < vlen; i++) {

    1.  for(int j= 0; j < vlen; j++) {
    2.     this.matrix[i][j] = matrix[i][j];
    3.  }

    } //统计边的条数 for(int i =0; i < vlen; i++) {

    1.  for(int j = i+1; j < vlen; j++) {
    2.     if(this.matrix[i][j] != INF) {
    3.        edgeNum++;
    4.     }
    5.  }

    }

    } public void kruskal() { int index = 0; //表示最后结果数组的索引 int[] ends = new int[edgeNum]; //用于保存”已有最小生成树” 中的每个顶点在最小生成树中的终点 //创建结果数组, 保存最后的最小生成树 EData[] rets = new EData[edgeNum];

    //获取图中 所有的边的集合 ， 一共有12边 EData[] edges = getEdges(); System.out.println(“图的边的集合=” + Arrays.toString(edges) + “ 共”+ edges.length); //12

    //按照边的权值大小进行排序(从小到大) sortEdges(edges);

    //遍历edges 数组，将边添加到最小生成树中时，判断是准备加入的边否形成了回路，如果没有，就加入 rets, 否则不能加入 for(int i=0; i < edgeNum; i++) {

    1.  //获取到第i条边的第一个顶点(起点)
    2.  int p1 = getPosition(edges[i].start); //p1=4
    3.  //获取到第i条边的第2个顶点
    4.  int p2 = getPosition(edges[i].end); //p2 = 5
    6.  //获取p1这个顶点在已有最小生成树中的终点
    7.  int m = getEnd(ends, p1); //m = 4
    8.  //获取p2这个顶点在已有最小生成树中的终点
    9.  int n = getEnd(ends, p2); // n = 5
    10.  //是否构成回路
    11.  if(m != n) { //没有构成回路
    12.     ends[m] = n; // 设置m 在"已有最小生成树"中的终点 <E,F> [0,0,0,0,5,0,0,0,0,0,0,0]
    13.     rets[index++] = edges[i]; //有一条边加入到rets数组
    14.  }

    } // 。 //统计并打印 “最小生成树”, 输出 rets System.out.println(“最小生成树为”); for(int i = 0; i < index; i++) {

    1.  System.out.println(rets[i]);

    }

}

//打印邻接矩阵 public void print() { System.out.println(“邻接矩阵为: \n”); for(int i = 0; i < vertexs.length; i++) { for(int j=0; j < vertexs.length; j++) { System.out.printf(“%12d”, matrix[i][j]); } System.out.println();//换行 } }

/**

  1. * 功能：对边进行排序处理, 冒泡排序
  2. * @param edges 边的集合
  3. */

private void sortEdges(EData[] edges) { for(int i = 0; i < edges.length - 1; i++) { for(int j = 0; j < edges.length - 1 - i; j++) { if(edges[j].weight > edges[j+1].weight) {//交换 EData tmp = edges[j]; edges[j] = edges[j+1]; edges[j+1] = tmp; } } } } /**

  1. * 
  2. * @param ch 顶点的值，比如'A','B'
  3. * @return 返回ch顶点对应的下标，如果找不到，返回-1
  4. */

private int getPosition(char ch) { for(int i = 0; i < vertexs.length; i++) { if(vertexs[i] == ch) {//找到 return i; } } //找不到,返回-1 return -1; } /**

  1. * 功能: 获取图中边，放到EData[] 数组中，后面我们需要遍历该数组
  2. * 是通过matrix 邻接矩阵来获取
  3. * EData[] 形式 [['A','B', 12], ['B','F',7], .....]
  4. * @return
  5. */

private EData[] getEdges() { int index = 0; EData[] edges = new EData[edgeNum]; for(int i = 0; i < vertexs.length; i++) { for(int j=i+1; j <vertexs.length; j++) { if(matrix[i][j] != INF) { edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]); } } } return edges; } /**

  1. * 功能: 获取下标为i的顶点的终点(), 用于后面判断两个顶点的终点是否相同
  2. * @param ends ： 数组就是记录了各个顶点对应的终点是哪个,ends 数组是在遍历过程中，逐步形成
  3. * @param i : 表示传入的顶点对应的下标
  4. * @return 返回的就是 下标为i的这个顶点对应的终点的下标, 一会回头还有来理解
  5. */

private int getEnd(int[] ends, int i) { // i = 4 [0,0,0,0,5,0,0,0,0,0,0,0] while(ends[i] != 0) { i = ends[i]; } return i; }

}

//创建一个类EData ，它的对象实例就表示一条边 class EData { char start; //边的一个点 char end; //边的另外一个点 int weight; //边的权值 //构造器 public EData(char start, char end, int weight) { this.start = start; this.end = end; this.weight = weight; } //重写toString, 便于输出边信息 @Override public String toString() { return “EData [<” + start + “, “ + end + “>= “ + weight + “]”; }
}

  3. <a name="5f08b723"></a>
  4. ## 11.8 迪杰斯特拉
  6. -  <br />迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。它的主要特点是以<br />起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止 
  7. <a name="568dc93e-17"></a>
  8. #### 基本介绍：
  10. -  <br />![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-09-16%2016.10.26.jpg#id=I89zr&originHeight=1174&originWidth=2312&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=) 
  11. <a name="4f7d0e2b-7"></a>
  12. #### 思路：
  14.    1. 设置出发顶点为 v，顶点集合 V{v1,v2,vi...}，v 到 V 中各顶点的距离构成距离集合 Dis，Dis{d1,d2,di...}，Dis<br />集合记录着 v 到图中各顶点的距离(到自身可以看作 0，v 到 vi 距离对应为 di)
  15.    2. 从Dis 中选择值最小的 di 并移出Dis 集合，同时移出V集合中对应的顶点 vi，此时的 v 到 vi 即为最短路径
  16.    3. 更新Dis 集合，更新规则为：比较 v 到V集合中顶点的距离值，与 v 通过 vi 到 V集合中顶点的距离值，保留<br />值较小的一个(同时也应该更新顶点的前驱节点为 vi，表明是通过 vi 到达的)
  17.    4. 重复执行两步骤，直到最短路径顶点为目标顶点即可结束
  18. -  <br />[https://www.bilibili.com/video/BV1EW411u7th?p=13&vd_source=0733adff24bb4c66f106d178f11ed3d3](https://www.bilibili.com/video/BV1EW411u7th?p=13&vd_source=0733adff24bb4c66f106d178f11ed3d3) 
  19. <a name="de45ba05"></a>
  20. #### 视频：
  22. -   
  23. <a name="4cf6fd20-7"></a>
  24. #### 代码：
  25. ```java
  26. public class DijkstraAlgorithm {
  28.    public static void main(String[] args) {
  29.       char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
  30.       //邻接矩阵
  31.       int[][] matrix = new int[vertex.length][vertex.length];
  32.       final int N = 65535;// 表示不可以连接
  33.       matrix[0]=new int[]{N,5,7,N,N,N,2};  
  34.         matrix[1]=new int[]{5,N,N,9,N,N,3};  
  35.         matrix[2]=new int[]{7,N,N,N,8,N,N};  
  36.         matrix[3]=new int[]{N,9,N,N,N,4,N};  
  37.         matrix[4]=new int[]{N,N,8,N,N,5,4};  
  38.         matrix[5]=new int[]{N,N,N,4,5,N,6};  
  39.         matrix[6]=new int[]{2,3,N,N,4,6,N};
  40.         //创建 Graph对象
  41.         Graph graph = new Graph(vertex, matrix);
  42.         //测试, 看看图的邻接矩阵是否ok
  43.         graph.showGraph();
  44.         //测试迪杰斯特拉算法
  45.         graph.dsj(2);//C
  46.         graph.showDijkstra();
  49.    }
  51. }
  53. class Graph {
  54.    private char[] vertex; // 顶点数组
  55.    private int[][] matrix; // 邻接矩阵
  56.    private VisitedVertex vv; //已经访问的顶点的集合
  58.    // 构造器
  59.    public Graph(char[] vertex, int[][] matrix) {
  60.       this.vertex = vertex;
  61.       this.matrix = matrix;
  62.    }
  64.    //显示结果
  65.    public void showDijkstra() {
  66.       vv.show();
  67.    }
  69.    // 显示图
  70.    public void showGraph() {
  71.       for (int[] link : matrix) {
  72.          System.out.println(Arrays.toString(link));
  73.       }
  74.    }
  76.    //迪杰斯特拉算法实现
  77.    /**
  78.     * 
  79.     * @param index 表示出发顶点对应的下标
  80.     */
  81.    public void dsj(int index) {
  82.       vv = new VisitedVertex(vertex.length, index);
  83.       update(index);//更新index顶点到周围顶点的距离和前驱顶点
  84.       for(int j = 1; j <vertex.length; j++) {
  85.          index = vv.updateArr();// 选择并返回新的访问顶点
  86.          update(index); // 更新index顶点到周围顶点的距离和前驱顶点
  87.       } 
  88.    }
  92.    //更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点,
  93.    private void update(int index) {
  94.       int len = 0;
  95.       //根据遍历我们的邻接矩阵的  matrix[index]行
  96.       for(int j = 0; j < matrix[index].length; j++) {
  97.          // len 含义是 : 出发顶点到index顶点的距离 + 从index顶点到j顶点的距离的和 
  98.          len = vv.getDis(index) + matrix[index][j];
  99.          // 如果j顶点没有被访问过，并且 len 小于出发顶点到j顶点的距离，就需要更新
  100.          if(!vv.in(j) && len < vv.getDis(j)) {
  101.             vv.updatePre(j, index); //更新j顶点的前驱为index顶点
  102.             vv.updateDis(j, len); //更新出发顶点到j顶点的距离
  103.          }
  104.       }
  105.    }
  106. }
  108. // 已访问顶点集合
  109. class VisitedVertex {
  110.    // 记录各个顶点是否访问过 1表示访问过,0未访问,会动态更新
  111.    public int[] already_arr;
  112.    // 每个下标对应的值为前一个顶点下标, 会动态更新
  113.    public int[] pre_visited;
  114.    // 记录出发顶点到其他所有顶点的距离,比如G为出发顶点，就会记录G到其它顶点的距离，会动态更新，求的最短距离就会存放到dis
  115.    public int[] dis;
  117.    //构造器
  118.    /**
  119.     * 
  120.     * @param length :表示顶点的个数 
  121.     * @param index: 出发顶点对应的下标, 比如G顶点，下标就是6
  122.     */
  123.    public VisitedVertex(int length, int index) {
  124.       this.already_arr = new int[length];
  125.       this.pre_visited = new int[length];
  126.       this.dis = new int[length];
  127.       //初始化 dis数组
  128.       Arrays.fill(dis, 65535);
  129.       this.already_arr[index] = 1; //设置出发顶点被访问过
  130.       this.dis[index] = 0;//设置出发顶点的访问距离为0
  132.    }
  133.    /**
  134.     * 功能: 判断index顶点是否被访问过
  135.     * @param index
  136.     * @return 如果访问过，就返回true, 否则访问false
  137.     */
  138.    public boolean in(int index) {
  139.       return already_arr[index] == 1;
  140.    }
  142.    /**
  143.     * 功能: 更新出发顶点到index顶点的距离
  144.     * @param index
  145.     * @param len
  146.     */
  147.    public void updateDis(int index, int len) {
  148.       dis[index] = len;
  149.    }
  150.    /**
  151.     * 功能: 更新pre这个顶点的前驱顶点为index顶点
  152.     * @param pre
  153.     * @param index
  154.     */
  155.    public void updatePre(int pre, int index) {
  156.       pre_visited[pre] = index;
  157.    }
  158.    /**
  159.     * 功能:返回出发顶点到index顶点的距离
  160.     * @param index
  161.     */
  162.    public int getDis(int index) {
  163.       return dis[index];
  164.    }
  167.    /**
  168.     * 继续选择并返回新的访问顶点， 比如这里的G 完后，就是 A点作为新的访问顶点(注意不是出发顶点)
  169.     * @return
  170.     */
  171.    public int updateArr() {
  172.       int min = 65535, index = 0;
  173.       for(int i = 0; i < already_arr.length; i++) {
  174.          if(already_arr[i] == 0 && dis[i] < min ) {
  175.             min = dis[i];
  176.             index = i;
  177.          }
  178.       }
  179.       //更新 index 顶点被访问过
  180.       already_arr[index] = 1;
  181.       return index;
  182.    }
  184.    //显示最后的结果
  185.    //即将三个数组的情况输出
  186.    public void show() {
  188.       System.out.println("==========================");
  189.       //输出already_arr
  190.       for(int i : already_arr) {
  191.          System.out.print(i + " ");
  192.       }
  193.       System.out.println();
  194.       //输出pre_visited
  195.       for(int i : pre_visited) {
  196.          System.out.print(i + " ");
  197.       }
  198.       System.out.println();
  199.       //输出dis
  200.       for(int i : dis) {
  201.          System.out.print(i + " ");
  202.       }
  203.       System.out.println();
  204.       //为了好看最后的最短距离，我们处理
  205.       char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
  206.       int count = 0;
  207.       for (int i : dis) {
  208.          if (i != 65535) {
  209.             System.out.print(vertex[count] + "("+i+") ");
  210.          } else {
  211.             System.out.println("N ");
  212.          }
  213.          count++;
  214.       }
  215.       System.out.println();     
  216.    }
  217. }

11.9 佛洛依德

  • 基本介绍：

    1. 和Dijkstra 算法一样，弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法
      名称以创始人之一、1978 年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名
    2. 弗洛伊德算法(Floyd)计算图中各个顶点之间的最短路径
    3. 迪杰斯特拉算法用于计算图中某一个顶点到其他顶点的最短路径
    4. 弗洛伊德算法 VS 迪杰斯特拉算法：迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其他顶点
      的最短路径；弗洛伊德算法中每一个顶点都是出发访问点，所以需要将每一个顶点看做被访问顶点，求出从每
      一个顶点到其他顶点的最短路径


  • Java数据结构与算法-尚硅谷 - 图43

    思路：

    1. 设置顶点 vi 到顶点 vk 的最短路径已知为 Lik，顶点 vk 到 vj 的最短路径已知为 Lkj，顶点 vi 到 vj 的路径为 Lij，
      则 vi 到 vj 的最短路径为：min((Lik+Lkj),Lij)，vk 的取值为图中所有顶点，则可获得 vi 到 vj 的最短路径
    2. 至于 vi 到 vk 的最短路径 Lik 或者 vk 到 vj 的最短路径 Lkj，是以同样的方式获得

  • 代码：

    ```java public class FloydAlgorithm {

    public static void main(String[] args) { // 测试看看图是否创建成功 char[] vertex = { ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’ }; //创建邻接矩阵 int[][] matrix = new int[vertex.length][vertex.length]; final int N = 65535; matrix[0] = new int[] { 0, 5, 7, N, N, N, 2 }; matrix[1] = new int[] { 5, 0, N, 9, N, N, 3 }; matrix[2] = new int[] { 7, N, 0, N, 8, N, N }; matrix[3] = new int[] { N, 9, N, 0, N, 4, N }; matrix[4] = new int[] { N, N, 8, N, 0, 5, 4 }; matrix[5] = new int[] { N, N, N, 4, 5, 0, 6 }; matrix[6] = new int[] { 2, 3, N, N, 4, 6, 0 };

    //创建 Graph 对象 Graph graph = new Graph(vertex.length, matrix, vertex); //调用弗洛伊德算法 graph.floyd(); graph.show(); }

}

// 创建图 class Graph { private char[] vertex; // 存放顶点的数组 private int[][] dis; // 保存，从各个顶点出发到其它顶点的距离，最后的结果，也是保留在该数组 private int[][] pre;// 保存到达目标顶点的前驱顶点

// 构造器 /**

  1. * 
  2. * @param length
  3. *            大小
  4. * @param matrix
  5. *            邻接矩阵
  6. * @param vertex
  7. *            顶点数组
  8. */

public Graph(int length, int[][] matrix, char[] vertex) { this.vertex = vertex; this.dis = matrix; this.pre = new int[length][length]; // 对pre数组初始化, 注意存放的是前驱顶点的下标 for (int i = 0; i < length; i++) { Arrays.fill(pre[i], i); } }

// 显示pre数组和dis数组 public void show() {

  1.   //为了显示便于阅读，我们优化一下输出
  2.   char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
  3.   for (int k = 0; k < dis.length; k++) {
  4.      // 先将pre数组输出的一行
  5.      for (int i = 0; i < dis.length; i++) {
  6.         System.out.print(vertex[pre[k][i]] + " ");
  7.      }
  8.      System.out.println();
  9.      // 输出dis数组的一行数据
  10.      for (int i = 0; i < dis.length; i++) {
  11.         System.out.print("("+vertex[k]+"到"+vertex[i]+"的最短路径是" + dis[k][i] + ") ");
  12.      }
  13.      System.out.println();
  14.      System.out.println();
  16.   }

}

//弗洛伊德算法, 比较容易理解，而且容易实现 public void floyd() { int len = 0; //变量保存距离 //对中间顶点遍历， k 就是中间顶点的下标 [A, B, C, D, E, F, G] for(int k = 0; k < dis.length; k++) { // //从i顶点开始出发 [A, B, C, D, E, F, G] for(int i = 0; i < dis.length; i++) { //到达j顶点 // [A, B, C, D, E, F, G] for(int j = 0; j < dis.length; j++) { len = dis[i][k] + dis[k][j];// => 求出从i 顶点出发，经过 k中间顶点，到达 j 顶点距离 if(len < dis[i][j]) {//如果len小于 dis[i][j] dis[i][j] = len;//更新距离 pre[i][j] = pre[k][j];//更新前驱顶点 } } } } } }

  3. <a name="9e44a11e"></a>
  4. ## 11.10 马踏棋盘
  6. -  <br />![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-09-16%2016.21.34.jpg#id=qnPBS&originHeight=878&originWidth=2262&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=)<br />![](https://xingqiu-tuchuang-1256524210.cos.ap-shanghai.myqcloud.com/3833/%E6%88%AA%E5%B1%8F2022-09-16%2016.21.42.jpg#id=SnSCI&originHeight=748&originWidth=2262&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=shadow&title=) 
  7. <a name="4f7d0e2b-9"></a>
  8. #### 思路：
  10. -   
  11. <a name="4cf6fd20-9"></a>
  12. #### 代码：
  13. ```java
  14. public class HorseChessboard {
  16.    private static int X; // 棋盘的列数
  17.    private static int Y; // 棋盘的行数
  18.    //创建一个数组，标记棋盘的各个位置是否被访问过
  19.    private static boolean visited[];
  20.    //使用一个属性，标记是否棋盘的所有位置都被访问
  21.    private static boolean finished; // 如果为true,表示成功
  23.    public static void main(String[] args) {
  24.       System.out.println("骑士周游算法，开始运行~~");
  25.       //测试骑士周游算法是否正确
  26.       X = 8;
  27.       Y = 8;
  28.       int row = 1; //马儿初始位置的行，从1开始编号
  29.       int column = 1; //马儿初始位置的列，从1开始编号
  30.       //创建棋盘
  31.       int[][] chessboard = new int[X][Y];
  32.       visited = new boolean[X * Y];//初始值都是false
  33.       //测试一下耗时
  34.       long start = System.currentTimeMillis();
  35.       traversalChessboard(chessboard, row - 1, column - 1, 1);
  36.       long end = System.currentTimeMillis();
  37.       System.out.println("共耗时: " + (end - start) + " 毫秒");
  39.       //输出棋盘的最后情况
  40.       for(int[] rows : chessboard) {
  41.          for(int step: rows) {
  42.             System.out.print(step + "\t");
  43.          }
  44.          System.out.println();
  45.       }
  46.    }
  48.    /**
  49.     * 完成骑士周游问题的算法
  50.     * @param chessboard 棋盘
  51.     * @param row 马儿当前的位置的行 从0开始 
  52.     * @param column 马儿当前的位置的列  从0开始
  53.     * @param step 是第几步 ,初始位置就是第1步 
  54.     */
  55.    public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
  56.       chessboard[row][column] = step;
  57.       //row = 4 X = 8 column = 4 = 4 * 8 + 4 = 36
  58.       visited[row * X + column] = true; //标记该位置已经访问
  59.       //获取当前位置可以走的下一个位置的集合 
  60.       ArrayList<Point> ps = next(new Point(column, row));
  61.       //对ps进行排序,排序的规则就是对ps的所有的Point对象的下一步的位置的数目，进行非递减排序
  62.       sort(ps);
  63.       //遍历 ps
  64.       while(!ps.isEmpty()) {
  65.          Point p = ps.remove(0);//取出下一个可以走的位置
  66.          //判断该点是否已经访问过
  67.          if(!visited[p.y * X + p.x]) {//说明还没有访问过
  68.             traversalChessboard(chessboard, p.y, p.x, step + 1);
  69.          }
  70.       }
  71.       //判断马儿是否完成了任务，使用   step 和应该走的步数比较 ， 
  72.       //如果没有达到数量，则表示没有完成任务，将整个棋盘置0
  73.       //说明: step < X * Y  成立的情况有两种
  74.       //1. 棋盘到目前位置,仍然没有走完
  75.       //2. 棋盘处于一个回溯过程
  76.       if(step < X * Y && !finished ) {
  77.          chessboard[row][column] = 0;
  78.          visited[row * X + column] = false;
  79.       } else {
  80.          finished = true;
  81.       }
  83.    }
  85.    /**
  86.     * 功能： 根据当前位置(Point对象)，计算马儿还能走哪些位置(Point)，并放入到一个集合中(ArrayList), 最多有8个位置
  87.     * @param curPoint
  88.     * @return
  89.     */
  90.    public static ArrayList<Point> next(Point curPoint) {
  91.       //创建一个ArrayList
  92.       ArrayList<Point> ps = new ArrayList<Point>();
  93.       //创建一个Point
  94.       Point p1 = new Point();
  95.       //表示马儿可以走5这个位置
  96.       if((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y -1) >= 0) {
  97.          ps.add(new Point(p1));
  98.       }
  99.       //判断马儿可以走6这个位置
  100.       if((p1.x = curPoint.x - 1) >=0 && (p1.y=curPoint.y-2)>=0) {
  101.          ps.add(new Point(p1));
  102.       }
  103.       //判断马儿可以走7这个位置
  104.       if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
  105.          ps.add(new Point(p1));
  106.       }
  107.       //判断马儿可以走0这个位置
  108.       if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
  109.          ps.add(new Point(p1));
  110.       }
  111.       //判断马儿可以走1这个位置
  112.       if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
  113.          ps.add(new Point(p1));
  114.       }
  115.       //判断马儿可以走2这个位置
  116.       if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
  117.          ps.add(new Point(p1));
  118.       }
  119.       //判断马儿可以走3这个位置
  120.       if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
  121.          ps.add(new Point(p1));
  122.       }
  123.       //判断马儿可以走4这个位置
  124.       if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
  125.          ps.add(new Point(p1));
  126.       }
  127.       return ps;
  128.    }
  130.    //根据当前这个一步的所有的下一步的选择位置，进行非递减排序, 减少回溯的次数
  131.    public static void sort(ArrayList<Point> ps) {
  132.       ps.sort(new Comparator<Point>() {
  134.          @Override
  135.          public int compare(Point o1, Point o2) {
  136.             // TODO Auto-generated method stub
  137.             //获取到o1的下一步的所有位置个数
  138.             int count1 = next(o1).size();
  139.             //获取到o2的下一步的所有位置个数
  140.             int count2 = next(o2).size();
  141.             if(count1 < count2) {
  142.                return -1;
  143.             } else if (count1 == count2) {
  144.                return 0;
  145.             } else {
  146.                return 1;
  147.             }
  148.          }
  150.       });
  151.    }
  152. }