一、数据结构和算法概述

1、数据结构和算法的关系

1、数据（data ）结构（structure）是一门研究组织数据方式的学科，有了编程语言也就有了数据结构。学好数据结构可以编写出更加漂亮,更加有效率的代码。
2、要学习好数据结构就要多多考虑如何将生活中遇到的问题，用程序去实现解决
3、程序 = 数据结构 + 算法
4、数据结构是算法的基础, 换言之，想要学好算法，需要把数据结构学到位。

2、线性结构和非线性结构

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

2.1 线性结构

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

    2.2 非线性结构

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

    二、稀疏数组和队列

    1、 稀疏 sparsearray 数组

    1.1 实际需求

    编写的五子棋程序中，有存盘退出和续上盘的功能。
    image.png
    分析问题：
    因为该二维数组的很多值是默认值0，因此记录了很多没有意义的数据 -> 稀疏数组

1.2 基本介绍

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

稀疏数组的处理方法是：
1) 记录数组一共有几行几列，有多少个不同的值
2) 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

稀疏数组举例说明
image.png

1.3 应用实例

1) 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
2) 把稀疏数组存盘，并且可以从新恢复原来的二维数组数
3) 整体思路分析
image.png
4) 代码实现

  1. public class SparseArray {
  3.     public static void main(String[] args) {
  5.         // 创建一个原始的二维数组 11 * 11
  6.         // 0: 表示没有棋子， 1 表示 黑子 2 表蓝子
  7.         int chessArr1[][] = new int[11][11];
  8.         chessArr1[1][2] = 1;
  9.         chessArr1[2][3] = 2;
  10.         chessArr1[4][5] = 2;
  11.         // 输出原始的二维数组
  12.         System.out.println("原始的二维数组：");
  13.         for (int[] row : chessArr1) {
  14.             for (int data : row) {
  15.                 System.out.printf("%d\t", data);
  16.             }
  17.             System.out.println();
  18.         }
  20.         // 将二维数组 转 稀疏数组的思
  21.         // 1. 先遍历二维数组 得到非0数据的个数
  22.         int sum = 0;
  23.         for (int i = 0; i < 11; i++) {
  24.             for (int j = 0; j < 11; j++) {
  25.                 if (chessArr1[i][j] != 0) {
  26.                     sum++;
  27.                 }
  28.             }
  29.         }
  31.         // 2. 创建对应的稀疏数组
  32.         int sparseArr[][] = new int[sum + 1][3];
  33.         // 给稀疏数组赋值
  34.         sparseArr[0][0] = 11;
  35.         sparseArr[0][1] = 11;
  36.         sparseArr[0][2] = sum;
  38.         // 遍历二维数组，将非0的值存放到 sparseArr中
  39.         // count 用于记录是第几个非0数据
  40.         int count = 0;
  41.         for (int i = 0; i < 11; i++) {
  42.             for (int j = 0; j < 11; j++) {
  43.                 if (chessArr1[i][j] != 0) {
  44.                     count++;
  45.                     sparseArr[count][0] = i;
  46.                     sparseArr[count][1] = j;
  47.                     sparseArr[count][2] = chessArr1[i][j];
  48.                 }
  49.             }
  50.         }
  52.         // 输出稀疏数组的形式
  53.         System.out.println();
  54.         System.out.println("得到稀疏数组为：");
  55.         for (int i = 0; i < sparseArr.length; i++) {
  56.             System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
  57.         }
  58.         System.out.println();
  60.         // 将稀疏数组 --》 恢复成 原始的二维数组
  61.         /**
  62.          * 1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的  chessArr2 = int [11][11]
  63.          * 2. 在读取稀疏数组后几行的数据，并赋给 原始的二维数组 即可.
  64.          */
  65.         // 1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
  66.         int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];
  68.         // 2. 在读取稀疏数组后几行的数据(从第二行开始)，并赋给 原始的二维数组 即可
  69.         for(int i = 1; i < sparseArr.length; i++) {
  70.             chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
  71.         }
  73.         // 输出恢复后的二维数组
  74.         System.out.println();
  75.         System.out.println("恢复后的二维数组");
  77.         for (int[] row : chessArr2) {
  78.             for (int data : row) {
  79.                 System.out.printf("%d\t", data);
  80.             }
  81.             System.out.println();
  82.         }
  83.     }
  84. }

2、队列

2.1 使用场景

银行排队的案例：
image.png

2.2 队列介绍

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

image.png
2.3 数组模拟队列思路

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front 及 rear 分别记录队列前后端的下标， front 会随着数据输出而改变，而 rear 则是随着数据输入而改变，如图所示：
image.png
当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：
思路分析：

  • 将尾指针往后移：rear+ 1 , 当front == rear 【空】

  • 若尾指针 rear 小于队列的最大下标 maxSize- 1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。 rear == maxSize - 1[队列满] ```java public class ArrayQueueDemo {

    public static void main(String[] args) {

    // 创建一个队列 ArrayQueue queue = new ArrayQueue(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(“程序退出~~”); }

}

// 使用数组模拟队列-编写一个ArrayQueue类 class ArrayQueue {

  1. private int maxSize;         // 表示数组的最大容量
  2. private int front;             // 队列头
  3. private int rear;             // 队列尾
  4. private int[] arr;             // 该数据用于存放数据, 模拟队列
  6. // 创建队列的构造器
  7. public ArrayQueue(int arrMaxSize) {
  8.     maxSize = arrMaxSize;
  9.     arr = new int[maxSize];
  10.     front = -1;             // 指向队列头部，分析出front是指向队列头的前一个位置.
  11.     rear = -1;                 // 指向队列尾，指向队列尾的数据(即就是队列最后一个数据)
  12. }
  14. // 判断队列是否满
  15. public boolean isFull() {
  16.     return rear == maxSize - 1;
  17. }
  19. // 判断队列是否为空
  20. public boolean isEmpty() {
  21.     return rear == front;
  22. }
  24. // 添加数据到队列
  25. public void addQueue(int n) {
  26.     // 判断队列是否满
  27.     if (isFull()) {
  28.         System.out.println("队列满，不能加入数据~");
  29.         return;
  30.     }
  31.     rear++; // 让rear 后移
  32.     arr[rear] = n;
  33. }
  35. // 获取队列的数据, 出队列
  36. public int getQueue() {
  37.     // 判断队列是否空
  38.     if (isEmpty()) {
  39.         // 通过抛出异常
  40.         throw new RuntimeException("队列空，不能取数据");
  41.     }
  42.     front++; // front后移
  43.     return arr[front];
  45. }
  47. // 显示队列的所有数据
  48. public void showQueue() {
  49.     // 遍历
  50.     if (isEmpty()) {
  51.         System.out.println("队列空的，没有数据~~");
  52.         return;
  53.     }
  54.     for (int i = 0; i < arr.length; i++) {
  55.         System.out.printf("arr[%d]=%d\n", i, arr[i]);
  56.     }
  57. }
  59. // 显示队列的头数据， 注意不是取出数据
  60. public int headQueue() {
  61.     // 判断
  62.     if (isEmpty()) {
  63.         throw new RuntimeException("队列空的，没有数据~~");
  64.     }
  65.     return arr[front + 1];
  66. }

}

  1. 问题分析并优化：<br />1)   目前数组使用一次就不能用，没有达到复用的效果<br />2)   将这个数组使用算法，改进成一个环形的队列取模：%
  2. <a name="QXVSu"></a>
  3. ### 2.4 数组模拟环形队列
  4. 对前面的数组模拟队列的优化，充分利用数组.  因此将数组看做是一个环形的。（通过取模的方式来实现即可）
  6. 分析说明：
  8. - 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的 时候需要注意 (rear + 1) % maxSize == front  满]
  9. - rear == front [空]
  10. - 分析示意图：
  12. ![image.png](https://cdn.nlark.com/yuque/0/2022/png/22523384/1649494707197-d3355d75-2368-44ab-9cb3-ec635b9338de.png#clientId=u46e433b2-4849-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=552&id=u7abd7ef1&margin=%5Bobject%20Object%5D&name=image.png&originHeight=552&originWidth=1028&originalType=binary&ratio=1&rotation=0&showTitle=false&size=104767&status=done&style=none&taskId=u2fb8f6d7-4d1b-490b-9b70-b87e39fda8c&title=&width=1028)
  13. ```java
  14. public class CircleArrayQueueDemo {
  16.     public static void main(String[] args) {
  18.         System.out.println("测试数组模拟环形队列的案例：");
  20.         // 创建一个环形队列
  21.         //说明：设置4, 其队列的有效数据最大是3
  22.         CircleArray queue = new CircleArray(4); 
  23.         char key = ' '; // 接收用户输入
  24.         Scanner scanner = new Scanner(System.in);//
  25.         boolean loop = true;
  26.         // 输出一个菜单
  27.         while (loop) {
  28.             System.out.println("s(show): 显示队列");
  29.             System.out.println("e(exit): 退出程序");
  30.             System.out.println("a(add): 添加数据到队列");
  31.             System.out.println("g(get): 从队列取出数据");
  32.             System.out.println("h(head): 查看队列头的数据");
  33.             key = scanner.next().charAt(0);// 接收一个字符
  34.             switch (key) {
  35.             case 's':
  36.                 queue.showQueue();
  37.                 break;
  38.             case 'a':
  39.                 System.out.println("输出一个数");
  40.                 int value = scanner.nextInt();
  41.                 queue.addQueue(value);
  42.                 break;
  43.             case 'g': // 取出数据
  44.                 try {
  45.                     int res = queue.getQueue();
  46.                     System.out.printf("取出的数据是%d\n", res);
  47.                 } catch (Exception e) {
  48.                     // TODO: handle exception
  49.                     System.out.println(e.getMessage());
  50.                 }
  51.                 break;
  52.             case 'h': // 查看队列头的数据
  53.                 try {
  54.                     int res = queue.headQueue();
  55.                     System.out.printf("队列头的数据是%d\n", res);
  56.                 } catch (Exception e) {
  57.                     // TODO: handle exception
  58.                     System.out.println(e.getMessage());
  59.                 }
  60.                 break;
  61.             case 'e': // 退出
  62.                 scanner.close();
  63.                 loop = false;
  64.                 break;
  65.             default:
  66.                 break;
  67.             }
  68.         }
  69.         System.out.println("程序退出~~");
  70.     }
  71. }
  73. class CircleArray {
  74.     private int maxSize; // 表示数组的最大容量
  75.     // front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素 
  76.     // front 的初始值 = 0
  77.     private int front; 
  78.     // rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.
  79.     // rear 的初始值 = 0
  80.     private int rear; // 队列尾
  81.     private int[] arr; // 该数据用于存放数据, 模拟队列
  83.     public CircleArray(int arrMaxSize) {
  84.         maxSize = arrMaxSize;
  85.         arr = new int[maxSize];
  86.     }
  88.     // 判断队列是否满
  89.     public boolean isFull() {
  90.         return (rear  + 1) % maxSize == front;
  91.     }
  93.     // 判断队列是否为空
  94.     public boolean isEmpty() {
  95.         return rear == front;
  96.     }
  98.     // 添加数据到队列
  99.     public void addQueue(int n) {
  100.         // 判断队列是否满
  101.         if (isFull()) {
  102.             System.out.println("队列满，不能加入数据~");
  103.             return;
  104.         }
  105.         //直接将数据加入
  106.         arr[rear] = n;
  107.         //将 rear 后移, 这里必须考虑取模
  108.         rear = (rear + 1) % maxSize;
  109.     }
  111.     // 获取队列的数据, 出队列
  112.     public int getQueue() {
  113.         // 判断队列是否空
  114.         if (isEmpty()) {
  115.             // 通过抛出异常
  116.             throw new RuntimeException("队列空，不能取数据");
  117.         }
  118.         // 这里需要分析出 front是指向队列的第一个元素
  119.         // 1. 先把 front 对应的值保留到一个临时变量
  120.         // 2. 将 front 后移, 考虑取模
  121.         // 3. 将临时保存的变量返回
  122.         int value = arr[front];
  123.         front = (front + 1) % maxSize;
  124.         return value;
  125.     }
  127.     // 显示队列的所有数据
  128.     public void showQueue() {
  129.         // 遍历
  130.         if (isEmpty()) {
  131.             System.out.println("队列空的，没有数据~~");
  132.             return;
  133.         }
  134.         // 思路：从front开始遍历，遍历多少个元素
  135.         // 动脑筋
  136.         for (int i = front; i < front + size() ; i++) {
  137.             System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
  138.         }
  139.     }
  141.     // 求出当前队列有效数据的个数
  142.     public int size() {
  143.         // rear = 2
  144.         // front = 1
  145.         // maxSize = 3 
  146.         return (rear + maxSize - front) % maxSize;   
  147.     }
  149.     // 显示队列的头数据， 注意不是取出数据
  150.     public int headQueue() {
  151.         // 判断
  152.         if (isEmpty()) {
  153.             throw new RuntimeException("队列空的，没有数据~~");
  154.         }
  155.         return arr[front];
  156.     }
  157. }

三、链表（Linked List）

1、链表的介绍

链表是有序的列表，但是它在内存中是存储如下
image.png
小结：
1) 链表是以节点的方式来存储,是链式存储
2) 每个节点包含 data 域， next 域：指向下一个节点.
3) 如图：发现链表的各个节点不一定是连续存储.
4) 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

单链表(带头结点) 逻辑结构示意图如下
image.png

2、单链表的应用实例

使用带 head 头的单向链表实现 – 水浒英雄排行榜管理。完成对英雄人物的增删改查操作，注: 删除和修改，查找
2.1 第一种方法在添加英雄时，直接添加到链表的尾部
思路分析示意图：
image.png
2.2 第二种方式在添加英雄时，根据排名将英雄插入到指定位置（如果有这个排名，则添加失败，并给出提示）。思路的分析示意图：
image.png
2.3 修改节点功能

  • 先找到该节点，通过遍历
  • temp.name = newHeroNode.name ; temp.nickname= newHeroNode.nickname

2.4 删除节点。思路分析的示意图：
image.png

  1. package com.atguigu.linkedlist;
  3. import java.util.Stack;
  5. public class SingleLinkedListDemo {
  7.     public static void main(String[] args) {
  9.         //进行测试
  10.         //先创建节点
  11.         HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  12.         HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  13.         HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  14.         HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
  16.         //创建要给链表
  17.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  20.         //加入
  21.         singleLinkedList.add(hero1);
  22.         singleLinkedList.add(hero4);
  23.         singleLinkedList.add(hero2);
  24.         singleLinkedList.add(hero3);
  26.         // 测试一下单链表的反转功能
  27.         System.out.println("原来链表的情况~~");
  28.         singleLinkedList.list();
  30. //        System.out.println("反转单链表~~");
  31. //        reversetList(singleLinkedList.getHead());
  32. //        singleLinkedList.list();
  34.         System.out.println("测试逆序打印单链表, 没有改变链表的结构~~");
  35.         reversePrint(singleLinkedList.getHead());
  37. /*        
  38.         //加入按照编号的顺序
  39.         singleLinkedList.addByOrder(hero1);
  40.         singleLinkedList.addByOrder(hero4);
  41.         singleLinkedList.addByOrder(hero2);
  42.         singleLinkedList.addByOrder(hero3);
  44.         //显示一把
  45.         singleLinkedList.list();
  47.         //测试修改节点的代码
  48.         HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
  49.         singleLinkedList.update(newHeroNode);
  51.         System.out.println("修改后的链表情况~~");
  52.         singleLinkedList.list();
  54.         //删除一个节点
  55.         singleLinkedList.del(1);
  56.         singleLinkedList.del(4);
  57.         System.out.println("删除后的链表情况~~");
  58.         singleLinkedList.list();
  60.         //测试一下 求单链表中有效节点的个数
  61.         System.out.println("有效的节点个数=" + getLength(singleLinkedList.getHead()));//2
  63.         //测试一下看看是否得到了倒数第K个节点
  64.         HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 3);
  65.         System.out.println("res=" + res);
  66. */
  67.     }
  69.     //方式2：
  70.     //可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
  71.     public static void reversePrint(HeroNode head) {
  72.         if(head.next == null) {
  73.             return;//空链表，不能打印
  74.         }
  75.         //创建要给一个栈，将各个节点压入栈
  76.         Stack<HeroNode> stack = new Stack<HeroNode>();
  77.         HeroNode cur = head.next;
  78.         //将链表的所有节点压入栈
  79.         while(cur != null) {
  80.             stack.push(cur);
  81.             cur = cur.next; //cur后移，这样就可以压入下一个节点
  82.         }
  83.         //将栈中的节点进行打印,pop 出栈
  84.         while (stack.size() > 0) {
  85.             System.out.println(stack.pop()); //stack的特点是先进后出
  86.         }
  87.     }
  89.     //将单链表反转
  90.     public static void reversetList(HeroNode head) {
  91.         //如果当前链表为空，或者只有一个节点，无需反转，直接返回
  92.         if(head.next == null || head.next.next == null) {
  93.             return ;
  94.         }
  96.         //定义一个辅助的指针(变量)，帮助我们遍历原来的链表
  97.         HeroNode cur = head.next;
  98.         HeroNode next = null;// 指向当前节点[cur]的下一个节点
  99.         HeroNode reverseHead = new HeroNode(0, "", "");
  100.         //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
  101.         //动脑筋
  102.         while(cur != null) { 
  103.             next = cur.next;//先暂时保存当前节点的下一个节点，因为后面需要使用
  104.             cur.next = reverseHead.next;//将cur的下一个节点指向新的链表的最前端
  105.             reverseHead.next = cur; //将cur 连接到新的链表上
  106.             cur = next;//让cur后移
  107.         }
  108.         //将head.next 指向 reverseHead.next , 实现单链表的反转
  109.         head.next = reverseHead.next;
  110.     }
  112.     //查找单链表中的倒数第k个结点 【新浪面试题】
  113.     //思路
  114.     //1. 编写一个方法，接收head节点，同时接收一个index 
  115.     //2. index 表示是倒数第index个节点
  116.     //3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
  117.     //4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
  118.     //5. 如果找到了，则返回该节点，否则返回nulll
  119.     public static HeroNode findLastIndexNode(HeroNode head, int index) {
  120.         //判断如果链表为空，返回null
  121.         if(head.next == null) {
  122.             return null;//没有找到
  123.         }
  124.         //第一个遍历得到链表的长度(节点个数)
  125.         int size = getLength(head);
  126.         //第二次遍历  size-index 位置，就是我们倒数的第K个节点
  127.         //先做一个index的校验
  128.         if(index <=0 || index > size) {
  129.             return null; 
  130.         }
  131.         //定义给辅助变量， for 循环定位到倒数的index
  132.         HeroNode cur = head.next; //3 // 3 - 1 = 2
  133.         for(int i =0; i< size - index; i++) {
  134.             cur = cur.next;
  135.         }
  136.         return cur;
  138.     }
  140.     //方法：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点)
  141.     /**
  142.      * 
  143.      * @param head 链表的头节点
  144.      * @return 返回的就是有效节点的个数
  145.      */
  146.     public static int getLength(HeroNode head) {
  147.         if(head.next == null) { //空链表
  148.             return 0;
  149.         }
  150.         int length = 0;
  151.         //定义一个辅助的变量, 这里我们没有统计头节点
  152.         HeroNode cur = head.next;
  153.         while(cur != null) {
  154.             length++;
  155.             cur = cur.next; //遍历
  156.         }
  157.         return length;
  158.     }
  160. }
  162. //定义SingleLinkedList 管理我们的英雄
  163. class SingleLinkedList {
  164.     //先初始化一个头节点, 头节点不要动, 不存放具体的数据
  165.     private HeroNode head = new HeroNode(0, "", "");
  168.     //返回头节点
  169.     public HeroNode getHead() {
  170.         return head;
  171.     }
  173.     //添加节点到单向链表
  174.     //思路，当不考虑编号顺序时
  175.     //1. 找到当前链表的最后节点
  176.     //2. 将最后这个节点的next 指向 新的节点
  177.     public void add(HeroNode heroNode) {
  179.         //因为head节点不能动，因此我们需要一个辅助遍历 temp
  180.         HeroNode temp = head;
  181.         //遍历链表，找到最后
  182.         while(true) {
  183.             //找到链表的最后
  184.             if(temp.next == null) {//
  185.                 break;
  186.             }
  187.             //如果没有找到最后, 将将temp后移
  188.             temp = temp.next;
  189.         }
  190.         //当退出while循环时，temp就指向了链表的最后
  191.         //将最后这个节点的next 指向 新的节点
  192.         temp.next = heroNode;
  193.     }
  195.     //第二种方式在添加英雄时，根据排名将英雄插入到指定位置
  196.     //(如果有这个排名，则添加失败，并给出提示)
  197.     public void addByOrder(HeroNode heroNode) {
  198.         //因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
  199.         //因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
  200.         HeroNode temp = head;
  201.         boolean flag = false; // flag标志添加的编号是否存在，默认为false
  202.         while(true) {
  203.             if(temp.next == null) {//说明temp已经在链表的最后
  204.                 break; //
  205.             } 
  206.             if(temp.next.no > heroNode.no) { //位置找到，就在temp的后面插入
  207.                 break;
  208.             } else if (temp.next.no == heroNode.no) {//说明希望添加的heroNode的编号已然存在
  210.                 flag = true; //说明编号存在
  211.                 break;
  212.             }
  213.             temp = temp.next; //后移，遍历当前链表
  214.         }
  215.         //判断flag 的值
  216.         if(flag) { //不能添加，说明编号存在
  217.             System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
  218.         } else {
  219.             //插入到链表中, temp的后面
  220.             heroNode.next = temp.next;
  221.             temp.next = heroNode;
  222.         }
  223.     }
  225.     //修改节点的信息, 根据no编号来修改，即no编号不能改.
  226.     //说明
  227.     //1. 根据 newHeroNode 的 no 来修改即可
  228.     public void update(HeroNode newHeroNode) {
  229.         //判断是否空
  230.         if(head.next == null) {
  231.             System.out.println("链表为空~");
  232.             return;
  233.         }
  234.         //找到需要修改的节点, 根据no编号
  235.         //定义一个辅助变量
  236.         HeroNode temp = head.next;
  237.         boolean flag = false; //表示是否找到该节点
  238.         while(true) {
  239.             if (temp == null) {
  240.                 break; //已经遍历完链表
  241.             }
  242.             if(temp.no == newHeroNode.no) {
  243.                 //找到
  244.                 flag = true;
  245.                 break;
  246.             }
  247.             temp = temp.next;
  248.         }
  249.         //根据flag 判断是否找到要修改的节点
  250.         if(flag) {
  251.             temp.name = newHeroNode.name;
  252.             temp.nickname = newHeroNode.nickname;
  253.         } else { //没有找到
  254.             System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
  255.         }
  256.     }
  258.     //删除节点
  259.     //思路
  260.     //1. head 不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
  261.     //2. 说明我们在比较时，是temp.next.no 和  需要删除的节点的no比较
  262.     public void del(int no) {
  263.         HeroNode temp = head;
  264.         boolean flag = false; // 标志是否找到待删除节点的
  265.         while(true) {
  266.             if(temp.next == null) { //已经到链表的最后
  267.                 break;
  268.             }
  269.             if(temp.next.no == no) {
  270.                 //找到的待删除节点的前一个节点temp
  271.                 flag = true;
  272.                 break;
  273.             }
  274.             temp = temp.next; //temp后移，遍历
  275.         }
  276.         //判断flag
  277.         if(flag) { //找到
  278.             //可以删除
  279.             temp.next = temp.next.next;
  280.         }else {
  281.             System.out.printf("要删除的 %d 节点不存在\n", no);
  282.         }
  283.     }
  285.     //显示链表[遍历]
  286.     public void list() {
  287.         //判断链表是否为空
  288.         if(head.next == null) {
  289.             System.out.println("链表为空");
  290.             return;
  291.         }
  292.         //因为头节点，不能动，因此我们需要一个辅助变量来遍历
  293.         HeroNode temp = head.next;
  294.         while(true) {
  295.             //判断是否到链表最后
  296.             if(temp == null) {
  297.                 break;
  298.             }
  299.             //输出节点的信息
  300.             System.out.println(temp);
  301.             //将temp后移， 一定小心
  302.             temp = temp.next;
  303.         }
  304.     }
  305. }
  307. // 定义HeroNode ， 每个HeroNode对象就是一个节点
  308. class HeroNode {
  310.     public int no;
  311.     public String name;
  312.     public String nickname;
  313.     public HeroNode next; //指向下一个节点
  314.     // 构造器
  315.     public HeroNode(int no, String name, String nickname) {
  316.         this.no = no;
  317.         this.name = name;
  318.         this.nickname = nickname;
  319.     }
  321.     //为了显示方法，我们重新toString
  322.     @Override
  323.     public String toString() {
  324.         return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
  325.     }
  326. }

3、单链表面试题

3.1 求单链表中有效节点的个数

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

3.3 单链表的反转
image.png
image.png

3.4 从尾到头打印单链表【要求方式1 ：反向遍历。 方式2 ：Stack 栈】
image.png

代码实现
写了一个小程序，测试 Stack 的使用

单链表的逆序打印代码:

3.5 合并两个有序的单链表，合并之后的链表依然有序

4、双向链表应用实例

4.1 双向链表的操作分析和实现
使用带 head 头的双向链表实现 –水浒英雄排行榜
管理单向链表的缺点分析:
1) 单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
2) 单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除 时节点，总是找到 temp,temp 是待删除节点的前一个节点(认真体会).
3) 分析了双向链表如何完成遍历，添加，修改和删除的思路

尚硅谷Java 数据结构和算法

对上图的说明:
分析 双向链表的遍历，添加，修改，删除的操作思路===》代码实现
1) 遍历 方和 单链表一样，只是可以向前，也可以向后查找
2) 添加 (默认添加到双向链表的最后)
( 1) 先找到双向链表的最后这个节点
(2) temp.next = newHeroNode
(3) newHeroNode.pre = temp;
3) 修改 思路和 原来的单向链表一样.
4) 删除
( 1) 因为是双向链表，因此，我们可以实现自我删除某个节点
(2) 直接找到要删除的这个节点，比如temp
(3) temp.pre.next = temp.next
(4) temp.next.pre = temp.pre;
双向链表的代码实现

5、单向环形链表应用场景

Josephu(约瑟夫、约瑟夫环) 问题
Josephu 问题为：设编号为 1 ，2 ，… n 的 n 个人围坐一圈，约定编号为k（1<=k<=n ）的人从 1 开始报数，数 到 m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由 此产生一个出队编号的序列。

提示：用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由k 结 点起从 1 开始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直 到最后一个结点从链表中删除算法结束。

6、单向环形链表介绍

7、Josephu 问题

约瑟夫问题的示意图

Josephu 问题
Josephu 问题为：设编号为1 ，2 ， … n 的n 个人围坐一圈，约定编号为k （1<=k<=n ）的人从 1 开始报数，数到m 的那个人出列，它的下一位又从 1 开始报数，数到 m 的那个人又出列，依次类推，直到所有人出列为止，由此 产生一个出队编号的序列。

提示
用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有 n 个结点的单循环链表，然后由k 结点起从 1 开 始计数，计到 m 时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从 1 开始计数，直到最后一个

尚硅谷Java 数据结构和算法
结点从链表中删除算法结束。

约瑟夫问题-创建环形链表的思路图解

四、栈

1、栈的实际需求

请输入一个表达式，计算式：[722-5+ 1-5+3-3] 点击计算【如下图】
image.png
请问：计算机底层是如何运算得到结果的？ 注意不是简单的把算式列出运算，因为我们看这个算式 7 2 2 - 5，但是计算机怎么理解这个算式的（对计算机而言，它接收到的就是一个字符串），我们讨论的是这个问题。—-> 栈

2、栈的介绍

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

image.png
image.png

3、栈的应用场景

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

    4、栈的快速入门

  • 用数组模拟栈的使用，由于栈是一种有序列表，当然可以使用数组的结构来储存栈的数据内容，下面我们就用数组模拟栈的出栈，入栈等操作。
  • 实现思路分析，并画出示意图

image.png

  • 代码实现 ```java public class ArrayStackDemo {

    public static void main(String[] args) {

    1.   // 测试一下ArrayStack 是否正确
    2.   // 先创建一个ArrayStack对象->表示栈
    3.   ArrayStack stack = new ArrayStack(4);
    4.   String key = "";
    5.   boolean loop = true; // 控制是否退出菜单
    6.   Scanner scanner = new Scanner(System.in);
    8.   while(loop) {
    9.       System.out.println("show: 表示显示栈");
    10.       System.out.println("exit: 退出程序");
    11.       System.out.println("push: 表示添加数据到栈(入栈)");
    12.       System.out.println("pop: 表示从栈取出数据(出栈)");
    13.       System.out.println("请输入你的选择");
    14.       key = scanner.next();
    15.       switch (key) {
    16.       case "show":
    17.           stack.list();
    18.           break;
    19.       case "push":
    20.           System.out.println("请输入一个数");
    21.           int value = scanner.nextInt();
    22.           stack.push(value);
    23.           break;
    24.       case "pop":
    25.           try {
    26.               int res = stack.pop();
    27.               System.out.printf("出栈的数据是 %d\n", res);
    28.           } catch (Exception e) {
    29.               // TODO: handle exception
    30.               System.out.println(e.getMessage());
    31.           }
    32.           break;
    33.       case "exit":
    34.           scanner.close();
    35.           loop = false;
    36.           break;
    37.       default:
    38.           break;
    39.       }
    40.   }
    41.   System.out.println("程序退出~~~");

    } }

// 定义一个 ArrayStack 表示栈 class ArrayStack {

  1. private int maxSize;     // 栈的大小
  2. private int[] stack;     // 数组，数组模拟栈，数据就放在该数组
  3. private int top = -1;    // top表示栈顶，初始化为-1
  5. // 构造器
  6. public ArrayStack(int maxSize) {
  7.     this.maxSize = maxSize;
  8.     stack = new int[this.maxSize];    // 初始化数组
  9. }
  11. // 栈满
  12. public boolean isFull() {
  13.     return top == maxSize - 1;
  14. }
  15. // 栈空
  16. public boolean isEmpty() {
  17.     return top == -1;
  18. }
  19. // 入栈 - push
  20. public void push(int value) {
  21.     // 先判断栈是否满
  22.     if(isFull()) {
  23.         System.out.println("栈满");
  24.         return;
  25.     }
  26.     top++;
  27.     stack[top] = value;
  28. }
  29. // 出栈 - pop, 将栈顶的数据返回
  30. public int pop() {
  31.     // 先判断栈是否空
  32.     if(isEmpty()) {
  33.         // 抛出异常
  34.         throw new RuntimeException("栈空，没有数据~");
  35.     }
  36.     int value = stack[top];
  37.     top--;
  38.     return value;
  39. }
  40. // 显示栈的情况【遍历栈】，遍历时，需要从栈顶开始显示数据
  41. public void list() {
  42.     if(isEmpty()) {
  43.         System.out.println("栈空，没有数据~~");
  44.         return;
  45.     }
  46.     // 需要从栈顶开始显示数据
  47.     for(int i = top; i >= 0 ; i--) {
  48.         System.out.printf("stack[%d] = %d\n", i, stack[i]);
  49.     }
  50. }

}

  2. - 关于栈的一个小练习
  4. 课堂练习，将老师写的程序改成使用链表来模拟栈。
  5. <a name="tIP7b"></a>
  6. ## 5、栈实现综合计算器（中缀表达式）
  8. - 使用栈来实现综合计算器：自定义优先级【priority】
  10. ![image.png](https://cdn.nlark.com/yuque/0/2022/png/22523384/1649584738244-863b9d74-b387-488c-8d4f-ff99cf250a44.png#clientId=u0db40e17-6fce-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=93&id=uccedc6dc&margin=%5Bobject%20Object%5D&name=image.png&originHeight=93&originWidth=478&originalType=binary&ratio=1&rotation=0&showTitle=false&size=27896&status=done&style=none&taskId=uc74c4b2b-d9a6-47f4-9dff-6697bd6ac6e&title=&width=478)
  12. - 思路分析（图解）：
  14. ![image.png](https://cdn.nlark.com/yuque/0/2022/png/22523384/1649595552808-655d91f1-2c8b-48fb-a27d-af191c916ded.png#clientId=udc00f2bc-841c-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=427&id=u302975b3&margin=%5Bobject%20Object%5D&name=image.png&originHeight=427&originWidth=1243&originalType=binary&ratio=1&rotation=0&showTitle=false&size=86137&status=done&style=none&taskId=u5f48c1f3-82b0-4c26-bff6-015c9ab8f5e&title=&width=1243)
  16. - 代价实现：【1、先实现一位数的运算，2、扩展到多位数的运算】
  18. p34-942
  20. - 课后的练习：给表达式加入小括号
  21. <a name="ZCgm9"></a>
  22. ## 6、逆波兰计算器
  23. 我们完成一个逆波兰计算器，要求完成如下任务:
  25. 1)   输入一个逆波兰表达式(后缀表达式) ，使用栈(Stack),  计算其结果<br />2)    支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算。<br />3)    思路分析
  27. | 例如: (3+4)×5-6  对应的后缀表达式就是 3 4 + 5  × 6 - ,  针对后缀表达式求值步骤如下:<br /><br /><br />1 ．从左至右扫描，将3 和4 压入堆栈；<br />2 ．遇到+运算符，因此弹出4 和3  （4 为栈顶元素，3 为次顶元素），计算出3+4 的值，得 7 ，再将 7 入栈；<br />3 ．将5 入栈；<br />4 ．接下来是×运算符，因此弹出 5 和7 ，计算出7×5=35 ，将35 入栈；<br />5 ．将 6 入栈；<br />6 ．最后是-运算符，计算出 35-6 的值，即 29 ，由此得出最终结果 |
  28. | --- |
  31. 4)   代码完成
  33. <a name="Cp8vS"></a>
  34. ## 7、中缀表达式转换为后缀表达式
  35. 大家看到，后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发 中，我们需要将 中缀表达式转成后缀表达式。
  37. <a name="sc5IE"></a>
  38. ### 7.1 具体步骤如下
  39. 1)  初始化两个栈：运算符栈 s1 和储存中间结果的栈s2；<br />2)  从左至右扫描中缀表达式；<br />3)  遇到操作数时，将其压 s2；<br />4)  遇到运算符时，比较其与 s1 栈顶运算符的优先级：<br />1.如果 s1 为空，或栈顶运算符为左括号“( ”，则直接将此运算符入栈；<br />2.否则，若优先级比栈顶运算符的高，也将运算符压入 s1；<br />3.否则，将 s1 栈顶的运算符弹出并压入到 s2 中，再次转到(4- 1)与s1 中新的栈顶运算符相比较；<br />5)  遇到括号时：<br />( 1)  如果是左括号“( ”，则直接压入s1<br />(2)  如果是右括号“) ”，则依次弹出 s1 栈顶的运算符，并压入 s2 ，直到遇到左括号为止，此时将这一对括号丢弃<br />6)  重复步骤2 至5 ，直到表达式的最右边<br />7)  将 s1 中剩余的运算符依次弹出并压入 s2<br />8)  依次弹出 s2 中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
  41. <a name="joITm"></a>
  42. ### 7.2 举例说明
  43. 将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下<br />因此结果为 :"1 2 3 + 4  × + 5   –"
  45. <a name="jYGNY"></a>
  46. ### 7.3 代码实现中缀表达式转为后缀表达式
  47.  思路分析
  49.  代码实现
  51. <a name="L7V2M"></a>
  52. ## 8、逆波兰计算器完整版
  53. <a name="HeEJo"></a>
  54. ### 8.1 完整版的逆波兰计算器，功能包括
  55. 1)  支持 + - * / ( )<br />2)  多位数，支持小数,<br />3)  兼容处理,  过滤任何空白字符，包括空格、制表符、换页符
  57. 说明：逆波兰计算器完整版考虑的因素较多，下面给出完整版代码供同学们学习，其基本思路和前面一样，也 是使用到：中缀表达式转后缀表达式。<br />代码实现：
  59. <a name="YTjf9"></a>
  60. # 五、递归
  61. <a name="E51NU"></a>
  62. ## 1、递归应用场景
  63. 看个实际应用场景：迷宫问题（回溯），递归（Recursion）<br />![image.png](https://cdn.nlark.com/yuque/0/2022/png/22523384/1649595692875-649fc26f-7071-4799-8e5d-ceafdcfd9157.png#clientId=udc00f2bc-841c-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=325&id=u39de3f32&margin=%5Bobject%20Object%5D&name=image.png&originHeight=325&originWidth=329&originalType=binary&ratio=1&rotation=0&showTitle=false&size=23878&status=done&style=none&taskId=ub34ad4dd-4fc1-43e5-b0fa-3ff22aba285&title=&width=329)
  64. <a name="A5sMn"></a>
  65. ## 2、递归的概念
  66. 简单的说：递归就是方法自己调用自己，每次调用时传入不同的变量。递归有助于编程者解决复杂的问题，同时可以让代码变得简洁。
  67. <a name="XRH81"></a>
  68. ## 3、递归调用机制
  69. 列举两个小案例，来帮助大家理解递归调用机制<br />**1)   打印问题**
  70. ```java
  71. public class RecursionTest {
  73.     public static void main(String[] args) {
  74.         // 通过打印问题，回顾递归调用机制
  75.         test(4);
  76.         System.out.println("****************");
  77.         test1(4);
  78.     }
  79.     // 打印问题1
  80.     public static void test(int n) {
  81.         if (n > 2) {
  82.             test(n - 1);
  83.         }
  84.         System.out.println("n = " + n);
  85.     }
  86.     // n = 2
  87.     // n = 3
  88.     // n = 4
  90.     // 打印问题2
  91.     public static void test1(int n) {
  92.         if (n > 2) {
  93.             test(n - 1);
  94.         } else {
  95.             System.out.println("n = " + n);
  96.         }
  97.     }
  98.     // n = 2
  99. }

2) 阶乘问题

  1. public class RecursionTest {
  3.     public static void main(String[] args) {
  5.         int res = factorial(3);
  6.         System.out.println("res = " + res);     // 输出：res = 6
  7.     }
  9.     // 阶乘问题
  10.     public static int factorial(int n) {
  11.         if (n == 1) { 
  12.             return 1;
  13.         } else {
  14.             return factorial(n - 1) * n;     // 1 * 2 * 3
  15.         }
  16.     }
  17. }

3) 使用图解方式说明了递归的调用机制
image.png

4、递归能解决的问题

  • 各种数学问题如：8皇后问题、汉诺塔、阶乘问题、迷宫问题、球和篮子的问题（google 编程大赛）
  • 各种算法中也会使用到递归，比如快排、归并排序、二分查找、分治算法等。

  • 将用栈解决的问题 —> 递归代码比较简洁

    5、递归需要遵守的重要规则

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

  • 方法的局部变量是独立的，不会相互影响，比如n变量
  • 如果方法中使用的是引用类型变量（比如数组），就会共享该引用类型的数据
  • 递归必须向退出递归的条件逼近，否则就是无限递归，出现StackOverflowError，死龟了

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

    6、递归：迷宫问题

    6.1 迷宫问题

    线性结构 - 图21
    说明：

  • 小球得到的路径，和程序员设置的找路策略有关即：找路的上下左右的顺序相关

  • 再得到小球路径时，可以先使用（下右上左），再改成（上右下左），看看路径是不是有变化
  • 测试回溯现象

  • 思考：如何求出最短路径？ 思路 -》 代码实现

    6.2 代码实现

    1. public class MiGong {
    3. public static void main(String[] args) {
    4.    // 先创建一个二维数组，模拟迷宫
    5.    // 地图
    6.    int[][] map = new int[8][7];
    7.    // 使用1 表示墙
    8.    // 上下全部置为1
    9.    for (int i = 0; i < 7; i++) {
    10.        map[0][i] = 1;
    11.        map[7][i] = 1;
    12.    }
    14.    // 左右全部置为1
    15.    for (int i = 0; i < 8; i++) {
    16.        map[i][0] = 1;
    17.        map[i][6] = 1;
    18.    }
    19.    //设置挡板, 用1表示
    20.    map[3][1] = 1;
    21.    map[3][2] = 1;
    22. //        map[1][2] = 1;
    23. //        map[2][2] = 1;
    25.    // 输出地图
    26.    System.out.println("地图的情况");
    27.    for (int i = 0; i < 8; i++) {
    28.        for (int j = 0; j < 7; j++) {
    29.            System.out.print(map[i][j] + " ");
    30.        }
    31.        System.out.println();
    32.    }
    34.    //使用递归回溯给小球找路
    35.    //setWay(map, 1, 1);
    36.    setWay2(map, 1, 1);
    38.    //输出新的地图, 小球走过，并标识过的递归
    39.    System.out.println("小球走过，并标识过的 地图的情况");
    40.    for (int i = 0; i < 8; i++) {
    41.        for (int j = 0; j < 7; j++) {
    42.            System.out.print(map[i][j] + " ");
    43.        }
    44.        System.out.println();
    45.    }
    47. }
    49. //使用递归回溯来给小球找路
    50. //1. map表示地图
    51. //2. i, j 表示从地图的哪个位置开始出发 (1,1)
    52. //3. 如果小球能到 map[6][5] 位置，则说明通路找到.
    53. //4. 约定： 当map[i][j] 为 0 表示该点没有走过 当为 1 表示墙  ； 2 表示通路可以走 ； 3 表示该点已经走过，但是走不通
    54. //5. 在走迷宫时，需要确定一个策略(方法) 下->右->上->左 , 如果该点走不通，再回溯
    55. /** 
    56. * @param map     表示地图
    57. * @param i     从哪个位置开始找
    58. * @param j 
    59. * @return         如果找到通路，就返回true, 否则返回false
    60. */
    61. public static boolean setWay(int[][] map, int i, int j) {
    62.    if(map[6][5] == 2) { // 通路已经找到ok
    63.        return true;
    64.    } else {
    65.        // 如果当前这个点还没有走过
    66.        if(map[i][j] == 0) { 
    67.            // 按照策略 下 -> 右 -> 上 -> 左  走
    68.            map[i][j] = 2;     // 假定该点是可以走通.
    69.            if(setWay(map, i+1, j)) {                // 向下走
    70.                return true;
    71.            } else if (setWay(map, i, j+1)) {         // 向右走
    72.                return true;
    73.            } else if (setWay(map, i-1, j)) {         // 向上
    74.                return true;
    75.            } else if (setWay(map, i, j-1)){         // 向左走
    76.                return true;
    77.            } else {
    78.                // 说明该点是走不通，是死路
    79.                map[i][j] = 3;
    80.                return false;
    81.            }
    82.        } else { // 如果map[i][j] != 0 , 可能是 1， 2， 3
    83.            return false;
    84.        }
    85.    }
    86. }
    88. // 修改找路的策略，改成：上 -> 右 -> 下 -> 左
    89. public static boolean setWay2(int[][] map, int i, int j) {
    90.    if(map[6][5] == 2) { // 通路已经找到ok
    91.        return true;
    92.    } else {
    93.        // 如果当前这个点还没有走过
    94.        if(map[i][j] == 0) { 
    95.            // 按照策略 上 -> 右 -> 下 -> 左
    96.            map[i][j] = 2; // 首先假定该点是可以走通
    97.            if(setWay2(map, i-1, j)) {            //    向上走
    98.                return true;
    99.            } else if (setWay2(map, i, j+1)) {     // 向右走
    100.                return true;
    101.            } else if (setWay2(map, i+1, j)) {     // 向下
    102.                return true;
    103.            } else if (setWay2(map, i, j-1)){     // 向左走
    104.                return true;
    105.            } else {
    106.                // 说明该点是走不通，是死路
    107.                map[i][j] = 3;
    108.                return false;
    109.            }
    110.        } else { // 如果map[i][j] != 0 , 可能是 1， 2， 3
    111.            return false;
    112.        }
    113.    }
    114. }
    115. }

    7、递归：八皇后问题（回溯算法）

    7.1 八皇后问题介绍

    八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯 ·贝瑟尔于 1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法（92）
    image.pngimage.png

    7.2 八皇后问题算法思路分析

  • 第一个皇后先放第一行第一列
  • 第二个皇后放在第二行第一列、然后判断是否 OK，如果不 OK，继续放在第二列、第三列、依次把所有列都 放完，找到一个合适
  • 继续第三个皇后，还是第一列、第二列……直到第 8 个皇后也能放在一个不冲突的位置，算是找到了一个正确解
  • 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到。
  • 然后回头继续第一个皇后放第二列，后面继续循环执行1, 2, 3, 4的步骤
  • 示意图：

image.png
说明：
理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题。arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} // 对应 arr 下标表示第几行，即第几个皇后，arr[i] = val，val 表示第 i+1个皇后，放在第i+1行的第val+1列

7.3 八皇后问题算法代码实现

  1. package com.atguigu.recursion;
  3. public class Queue8 {
  5.     // 定义一个max表示共有多少个皇后
  6.     int max = 8;
  7.     // 定义数组array, 保存皇后放置位置的结果, 比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3} 
  8.     int[] array = new int[max];
  9.     static int count = 0;
  10.     static int judgeCount = 0;
  12.     public static void main(String[] args) {
  13.         // 测试一把，八皇后是否正确
  14.         Queue8 queue8 = new Queue8();
  15.         queue8.check(0);
  16.         System.out.printf("一共有%d解法", count);
  17.         System.out.printf("一共判断冲突的次数%d次", judgeCount); // 1.5w
  18.     }
  20.     // 编写一个方法，放置第n个皇后
  21.     // 特别注意：check是每一次递归时，进入到check中都有for(int i = 0; i < max; i++)，因此会有回溯
  22.     private void check(int n) {
  23.         if(n == max) {  // n = 8，其实8个皇后就既然放好
  24.             print();
  25.             return;
  26.         }
  28.         // 依次放入皇后，并判断是否冲突
  29.         for(int i = 0; i < max; i++) {
  30.             // 先把当前这个皇后 n , 放到该行的第1列
  31.             array[n] = i;
  32.             // 判断当放置第n个皇后到i列时，是否冲突
  33.             if(judge(n)) { // 不冲突
  34.                 // 接着放n+1个皇后,即开始递归
  35.                 check(n+1); //  
  36.             }
  37.             // 如果冲突，就继续执行 array[n] = i; 即将第n个皇后，放置在本行得 后移的一个位置
  38.         }
  39.     }
  41.     /** 查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突
  42.      * 
  43.      * @param n 表示第n个皇后
  44.      * @return
  45.      */
  46.     private boolean judge(int n) {
  47.         judgeCount++;
  48.         for(int i = 0; i < n; i++) {
  49.             // 说明
  50.             // 1. array[i] == array[n]表示判断第n个皇后是否和前面的n-1个皇后在同一列
  51.             // 2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线
  52.             //    n = 1  放置第 2列 1 n = 1 array[1] = 1
  53.             //    Math.abs(1-0) == 1  Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
  54.             // 3. 判断是否在同一行, 没有必要，n每次都在递增
  55.             if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) {
  56.                 return false;
  57.             }
  58.         }
  59.         return true;
  60.     }
  62.     // 写一个方法，可以将皇后摆放的位置输出
  63.     private void print() {
  64.         count++;
  65.         for (int i = 0; i < array.length; i++) {
  66.             System.out.print(array[i] + " ");
  67.         }
  68.         System.out.println();
  69.     }
  70. }