• 数据结构和算法——数据结构

    目录

    线性结构

     队列结构的队列

    链表结构的队列

    链表的面试题

    单向链表应用场景

    约瑟夫环问题

    栈结构

    中缀表达式

    前缀表达式

    后缀表达式

    非线性结构

    图

    递归解决迷宫问题

    递归解决八皇后问题

    线性结构

    顺序存储方式，顺序表

    常见的顺序存储结构有：数组、队列、链表、栈

    链式存储方式，链表

    数组结构

    队列结构的队列

    队列可以使用数组结构或者链表结构来存储，先入先出，后进后出。

    数组结构的队列：

    1. public class Demo {
    2.     public static void main(String[] args) {
    3.         CircleArrayQueue arrayQueue = new CircleArrayQueue(3);
    4.         char key;
    5.         Scanner scanner = new Scanner(System.in);
    6.         boolean loop = true;
    7.         while (loop) {
    8.             System.out.println("s(show)：显示队列");
    9.             System.out.println("e(exit)：退出程序");
    10.             System.out.println("a(add)：添加数据到队列");
    11.             System.out.println("g(get)：从队列取出数据");
    12.             System.out.println("h(head)：查看队列头的数据");
    13.             key = scanner.next().charAt(0);
    14.             switch (key) {
    15.                 case 's':
    16.                     arrayQueue.showQueue();
    17.                     break;
    18.                 case 'a':
    19.                     System.out.println("请输入一个数字");
    20.                     int value = scanner.nextInt();
    21.                     arrayQueue.addQueue(value);
    22.                     break;
    23.                 case 'g':
    24.                     try {
    25.                         int res = arrayQueue.getQueue();
    26.                         System.out.println("取出的数据为=" + res);
    27.                     } catch (Exception e) {
    28.                         System.out.println(e.getMessage());
    29.                     }
    30.                     break;
    31.                 case 'e':
    32.                     loop = false;
    33.                     scanner.close();
    34.                     System.out.println("程序退出...");
    35.                     break;
    36.                 case 'h':
    37.                     try {
    38.                         int res = arrayQueue.headQueue();
    39.                         System.out.println("查看的数据为=" + res);
    40.                     } catch (Exception e) {
    41.                         System.out.println(e.getMessage());
    42.                     }
    43.                     break;
    44.                 default:
    45.                     break;
    46.             }
    47.         }
    48.     }
    49. }
    50.  
    51. class CircleArrayQueue {
    52.     private int maxSize;
    53.     // 指向队列头的位置
    54.     private int front;
    55.     // 指向队列尾的数据的下一个的位置，它指向的队尾的数据代表有值的
    56.     private int rear;
    57.     private int[] arr;
    58.  
    59.     public CircleArrayQueue(int arrMaxSize) {
    60.         // 实际上队列有maxSize个元素，因为空出了一个位置
    61.         maxSize = arrMaxSize + 1;
    62.         arr = new int[maxSize];
    63.         front = rear = 0;
    64.     }
    65.  
    66.     public boolean isFull() {
    67.         return (rear + 1) % maxSize == front;
    68.     }
    69.  
    70.     public boolean isEmpty() {
    71.         return front == rear;
    72.     }
    73.  
    74.     public void addQueue(int n) {
    75.         if (isFull()) {
    76.             System.out.println("队列为满，不能加入数据");
    77.             return;
    78.         }
    79.         arr[rear] = n;
    80.         rear++;
    81.         if (rear % maxSize == 0) {
    82.             rear = 0;
    83.         }
    84.     }
    85.  
    86.     public int getQueue() {
    87.         if (isEmpty()) {
    88.             throw new RuntimeException("队列为空，不能取值");
    89.         }
    90.         int res = arr[front];
    91.         front++;
    92.         if (front % maxSize == 0) {
    93.             front = 0;
    94.         }
    95.         return res;
    96.     }
    97.  
    98.     public void showQueue() {
    99.         if (isEmpty()) {
    100.             System.out.println("队列为空，没有数据");
    101.             return;
    102.         }
    103. //        for (int i = front; i != rear; i = (i + 1) % maxSize) {
    104.         for (int i = front; i < front + size(); i++) {
    105.             System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
    106.         }
    107.     }
    108.  
    109.     public int headQueue() {
    110.         if (isEmpty()) {
    111.             throw new RuntimeException("队列为空，没有头数据");
    112.         }
    113.         return arr[front];
    114.     }
    115.  
    116.     private int size() {
    117.         return (rear + maxSize - front) % maxSize;
    118.     }
    119. }

     栈结构

    1. public class ArrayStackDemo {
    2.     public static void main(String[] args) {
    3.         ArrayStack stack = new ArrayStack(4);
    4.         String key;
    5.         boolean loop = true;
    6.         Scanner scanner = new Scanner(System.in);
    7.         while (loop) {
    8.             System.out.println("show：表示显示栈");
    9.             System.out.println("exit：表示退出栈");
    10.             System.out.println("push：表示压栈");
    11.             System.out.println("pop：表示出栈");
    12.             System.out.println("请输入你的选择：");
    13.             key = scanner.next();
    14.             switch (key) {
    15.                 case "s":
    16.                     stack.list();
    17.                     break;
    18.                 case "e":
    19.                     loop = false;
    20.                     break;
    21.                 case "pu":
    22.                     try {
    23.                         System.out.println("请输入要压栈的数据");
    24.                         int value = scanner.nextInt();
    25.                         stack.push(value);
    26.                     } catch (Exception e) {
    27.                         System.out.println(e.getMessage());
    28.                     }
    29.                     break;
    30.                 case "po":
    31.                     try {
    32.                         System.out.println(stack.pop());
    33.                     } catch (Exception e) {
    34.                         System.out.println(e.getMessage());
    35.                     }
    36.                     break;
    37.                 default:
    38.                     System.out.println("输入有误");
    39.                     break;
    40.             }
    41.         }
    42.         System.out.println("程序退出了...");
    43.     }
    44. }
    45.  
    46. class ArrayStack {
    47.     private int maxSize;
    48.     private int[] stack;
    49.     private int top = -1;
    50.  
    51.     public ArrayStack(int maxSize) {
    52.         this.maxSize = maxSize;
    53.         stack = new int[maxSize];
    54.     }
    55.  
    56.     public boolean isFull() {
    57.         return top == maxSize - 1;
    58.     }
    59.  
    60.     public boolean isEmpty() {
    61.         return top == -1;
    62.     }
    63.  
    64.     public void push(int value) {
    65.         if (isFull()) {
    66.             System.out.println("栈满");
    67.             return;
    68.         }
    69.         top++;
    70.         stack[top] = value;
    71.     }
    72.  
    73.     public int pop() {
    74.         if (isEmpty()) {
    75.             throw new RuntimeException("栈空，没有数据");
    76.         }
    77.         int res = stack[top];
    78.         top--;
    79.         return res;
    80.     }
    81.  
    82.     public void list() {
    83.         if (isEmpty()) {
    84.             System.out.println("栈空，没有数据");
    85.             return;
    86.         }
    87.         for (int i = top; i >= 0; i--) {
    88.             System.out.printf("a[%d]=%d\n", i, stack[i]);
    89.         }
    90.     }
    91. }
    中缀表达式

    人阅读的表达式。用来实现一个简单的计算器：

    1. public class Calculator {
    2.     public static void main(String[] args) {
    3.         String expression = "7*2*2-5+1-5+3-4";
    4.         ArrayStack2 numStack = new ArrayStack2(10);
    5.         ArrayStack2 operStack = new ArrayStack2(10);
    6.         int index = 0;
    7.         int num1 = 0;
    8.         int num2 = 0;
    9.         int oper = 0;
    10.         int res = 0;
    11.         char ch = ' ';
    12.         while (true) {
    13.             ch = expression.substring(index, index + 1).charAt(0);
    14.             if (operStack.isOper(ch)) {
    15.                 if (!operStack.isEmpty()) {
    16.                     if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
    17.                         num1 = numStack.pop();
    18.                         num2 = numStack.pop();
    19.                         oper = operStack.pop();
    20.                         res = numStack.cal(num1, num2, (char) oper);
    21.                         numStack.push(res);
    22.                         operStack.push(ch);
    23.                     } else {
    24.                         operStack.push(ch);
    25.                     }
    26.                 } else {
    27.                     operStack.push(ch);
    28.                 }
    29.             } else {
    30.                 // numStack.push(ch - '0');
    31.                 int keepNum = ch - '0';
    32.                 while (index < expression.length() - 1) {
    33.                     index++;
    34.                     ch = expression.substring(index, index + 1).charAt(0);
    35.                     if (!operStack.isOper(ch)) {
    36.                         keepNum = keepNum * 10 + (ch - '0');
    37.                     } else {
    38.                         index--;
    39.                         break;
    40.                     }
    41.                 }
    42.                 numStack.push(keepNum);
    43.             }
    44.             index++;
    45.             if (index == expression.length()) {
    46.                 break;
    47.             }
    48.         }
    49.         while (true) {
    50.             if (operStack.isEmpty()) {
    51.                 break;
    52.             }
    53.             num1 = numStack.pop();
    54.             num2 = numStack.pop();
    55.             oper = operStack.pop();
    56.             res = numStack.cal(num1, num2, (char) oper);
    57.             numStack.push(res);
    58.         }
    59.         System.out.printf("表达式 %s = %d\n", expression, numStack.pop());
    60.     }
    61. }
    62.  
    63. class ArrayStack2 {
    64.     private int maxSize;
    65.     private int[] stack;
    66.     private int top = -1;
    67.  
    68.     public ArrayStack2(int maxSize) {
    69.         this.maxSize = maxSize;
    70.         stack = new int[maxSize];
    71.     }
    72.  
    73.     public boolean isFull() {
    74.         return top == maxSize - 1;
    75.     }
    76.  
    77.     public boolean isEmpty() {
    78.         return top == -1;
    79.     }
    80.  
    81.     public void push(int value) {
    82.         if (isFull()) {
    83.             System.out.println("栈满");
    84.             return;
    85.         }
    86.         top++;
    87.         stack[top] = value;
    88.     }
    89.  
    90.     public int pop() {
    91.         if (isEmpty()) {
    92.             throw new RuntimeException("栈空，没有数据");
    93.         }
    94.         int res = stack[top];
    95.         top--;
    96.         return res;
    97.     }
    98.  
    99.     public void list() {
    100.         if (isEmpty()) {
    101.             System.out.println("栈空，没有数据");
    102.             return;
    103.         }
    104.         for (int i = top; i >= 0; i--) {
    105.             System.out.printf("a[%d]=%d\n", i, stack[i]);
    106.         }
    107.     }
    108.  
    109.     public int priority(int oper) {
    110.         if (oper == '*' || oper == '/') {
    111.             return 1;
    112.         } else if (oper == '+' || oper == '-') {
    113.             return 0;
    114.         }
    115.         return -1;
    116.     }
    117.  
    118.     public boolean isOper(char val) {
    119.         return val == '+' || val == '-' || val == '*' || val == '/';
    120.     }
    121.  
    122.     public int cal(int num1, int num2, char oper) {
    123.         int res = 0;
    124.         switch (oper) {
    125.             case '+':
    126.                 res = num1 + num2;
    127.                 break;
    128.             case '-':
    129.                 res = num2 - num1;
    130.                 break;
    131.             case '*':
    132.                 res = num1 * num2;
    133.                 break;
    134.             case '/':
    135.                 res = num2 / num1;
    136.                 break;
    137.             default:
    138.                 break;
    139.         }
    140.         return res;
    141.     }
    142.  
    143.     public int peek() {
    144.         return stack[top];
    145.     }
    146. }
    前缀表达式

    也叫波兰表达式，(3+4)x5-6对应的前缀表达式为 - x + 3 4 5 6，从右向左扫描，遇到数字的时，将数字压入，遇到运算符时，弹出栈顶的两个数字进行计算，将结果压入栈，

    后缀表达式

    也叫逆波兰表达式，(3+4)x5-6 对应的逆波兰表达式为 3 4 + 5 x 6 - ，从左到右扫描，遇到数字把数字压栈，遇到运算符弹出栈顶的两个数字，进行运算，最后将结果压栈。可以用来写计算器：

    代码：

    1. public class PolandNotation {
    2.     public static void main(String[] args) {
    3.         // 逆波兰表达式
    4.         // (3+4)*5-6
    5. //        String suffixExpression = "3 4 + 5 * 6 -";
    6.         // 4*5-8+60+8/2
    7.         String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";
    8.         List list = getListString(suffixExpression);
    9.         int res = calculate(list);
    10.     }
    11.  
    12.     public static List getListString(String suffixExpression) {
    13.         String[] s = suffixExpression.split(" ");
    14.         List list = new ArrayList<>();
    15.         for (String ele : s) {
    16.             list.add(ele);
    17.         }
    18.         return list;
    19.     }
    20.  
    21.     public static int calculate(List list) {
    22.         Stack stack = new Stack<>();
    23.         for (String item : list) {
    24.             if (item.matches("\\d+")) {
    25.                 stack.push(item);
    26.             } else {
    27.                 int n2 = Integer.parseInt(stack.pop());
    28.                 int n1 = Integer.parseInt(stack.pop());
    29.                 int res = 0;
    30.                 if (item.equals("+")) {
    31.                     res = n1 + n2;
    32.                 } else if (item.equals("-")) {
    33.                     res = n1 - n2;
    34.                 } else if (item.equals("*")) {
    35.                     res = n1 * n2;
    36.                 } else if (item.equals("/")) {
    37.                     res = n1 / n2;
    38.                 } else {
    39.                     throw new RuntimeException("运算符有误");
    40.                 }
    41.                 stack.push(res + "");
    42.             }
    43.         }
    44.         return Integer.parseInt(stack.pop());
    45.     }
    46. }

    如何中缀转后缀表达式：

    1）初始化两个栈，运算符栈s1和存储中间结果的栈s2；

    2）从左到右扫描中缀表达式；

    3）遇到数时，压入栈s2；

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

    1.如果栈s1为空，或栈顶运算符为左括号，则直接将此运算符压栈s1；

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

    3.否则，将栈s1栈顶的运算符弹出并压入栈s2，再次（4 - 1）与 s1 中新的栈顶运算符比较；

    5）遇到括号时：

    1.如果是左括号，则直接压入栈s1；

    2.如果是右括号，则依次弹出s1栈顶的运算符，并压入栈s2，直到遇到左括号为止，此时将一对括号丢弃；

    6）重复步骤2至5，直到表达式最右边；

    7）将s1中剩余的运算符依次弹出并压入栈s2；

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

    代码：

    1. public class PolandNotation {
    2.     public static void main(String[] args) {
    3.         String expression = "1+((2+3)*4)-5"; // 后缀表达式：1 2 3 + 4 * + 5 -
    4.         List list = infixExpressionList(expression);
    5.         List result = parseSuffixExpreesionList(list);
    6.     }
    7.  
    8.     public static List parseSuffixExpreesionList(List list) {
    9.         Stack s1 = new Stack<>(); // 运算符栈
    10.         List s2 = new ArrayList<>(); // 存储中间结果的栈
    11.         for (String item : list) {
    12.             if (item.matches("\\d+")) {
    13.                 s2.add(item);
    14.             } else if (item.equals("(")) {
    15.                 s1.push(item);
    16.             } else if (item.equals(")")) {
    17.                 while (!s1.peek().equals("(")) {
    18.                     s2.add(s1.pop());
    19.                 }
    20.                 s1.pop(); // 弹栈 (
    21.             } else {
    22.                 while (!s1.isEmpty() && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
    23.                     s2.add(s1.pop());
    24.                 }
    25.                 s1.add(item);
    26.             }
    27.         }
    28.         while (!s1.isEmpty()) {
    29.             s2.add(s1.pop());
    30.         }
    31.         return s2;
    32.     }
    33.  
    34.     private static List infixExpressionList(String s) {
    35.         ArrayList list = new ArrayList<>();
    36.         int i = 0;
    37.         String str;
    38.         char c;
    39.         do {
    40.             c = s.charAt(i);
    41.             if (c < '0' || c > '9') {
    42.                 list.add("" + c);
    43.                 i++;
    44.             } else {
    45.                 str = "";
    46.                 while (i < s.length() && (c = s.charAt(i)) >= '0' && c <= '9') {
    47.                     str += c;
    48.                     i++;
    49.                 }
    50.                 list.add(str);
    51.             }
    52.         } while (i < s.length());
    53.         return list;
    54.     }
    55. }
    56.  
    57. class Operation {
    58.     private static int ADD = 1;
    59.     private static int SUB = 1;
    60.     private static int MUL = 1;
    61.     private static int DIV = 1;
    62.  
    63.     public static int getValue(String operation) {
    64.         int result = 0;
    65.         switch (operation) {
    66.             case "+":
    67.                 result = ADD;
    68.                 break;
    69.             case "-":
    70.                 result = SUB;
    71.                 break;
    72.             case "*":
    73.                 result = MUL;
    74.                 break;
    75.             case "/":
    76.                 result = DIV;
    77.                 break;
    78.             default:
    79.                 System.out.println("不存在该运算符");
    80.                 break;
    81.         }
    82.         return result;
    83.     }
    84. }

    链表结构的队列

    1. public class SingleLinkListDemo {
    2.     public static void main(String[] args) {
    3.         HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
    4.         HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
    5.         HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
    6.         SingleLinkList singleLinkList = new SingleLinkList();
    7.         singleLinkList.add(hero3);
    8.         singleLinkList.add(hero2);
    9.         singleLinkList.add(hero1);
    10. //        singleLinkList.add(hero3);
    11. //        HeroNode newHero = new HeroNode(3, "张三", "法外狂徒");
    12. //        singleLinkList.update(newHero);
    13.         HeroNode delHero1 = new HeroNode(1, "", "");
    14.         singleLinkList.del(delHero1);
    15.         singleLinkList.reverse();
    16.         singleLinkList.list();
    17.     }
    18. }
    19.  
    20. class SingleLinkList {
    21.     private HeroNode headNode = new HeroNode(0, "", "");
    22.  
    23.     // 非递归反转
    24.     public void reverse3() {
    25.         if (headNode.getNext() == null || headNode.getNext().getNext() == null) {
    26.             return;
    27.         }
    28.         HeroNode nextNode1, nextNode2, nextNode3;
    29.         nextNode1 = headNode.getNext();
    30.         nextNode2 = nextNode1.getNext();
    31.         nextNode3 = nextNode2.getNext();
    32.         nextNode2.setNext(nextNode1);
    33.         nextNode1.setNext(null);
    34.  
    35.         while (nextNode3 != null) {
    36.             nextNode1 = nextNode2;
    37.             nextNode2 = nextNode3;
    38.             nextNode3 = nextNode3.getNext();
    39.             nextNode2.setNext(nextNode1);
    40.         }
    41.         headNode.setNext(nextNode2);
    42.     }
    43.  
    44.     // 递归反转
    45.     public void reverse() {
    46.         HeroNode nextNode = headNode.getNext();
    47.         headNode.setNext(reverse2(headNode.getNext()));
    48.         nextNode.setNext(null);
    49.     }
    50.     private HeroNode reverse2(HeroNode heroNode) {
    51.         if (heroNode.getNext() != null) {
    52.             HeroNode lastNode = reverse2(heroNode.getNext());
    53.             heroNode.getNext().setNext(heroNode);
    54.             return lastNode;
    55.         }
    56.         return heroNode;
    57.     }
    58.  
    59.     public void del(HeroNode delHeroNode) {
    60.         if (headNode.getNext() == null) {
    61.             System.out.println("链表为空");
    62.             return;
    63.         }
    64.         HeroNode preNode, nextNode;
    65.         preNode = headNode;
    66.         nextNode = headNode.getNext();
    67.         while (nextNode != null) {
    68.             if (nextNode.getNo() == delHeroNode.getNo()) {
    69.                 preNode.setNext(nextNode.getNext());
    70.                 // nextNode.setNext(null);
    71.                 return;
    72.             }
    73.             preNode = nextNode;
    74.             nextNode = nextNode.getNext();
    75.         }
    76.         System.out.println("删除编号= " + delHeroNode.getNo() + " 的元素没有找到");
    77.     }
    78.  
    79.     public void update(HeroNode newHeroNode) {
    80.         if (headNode.getNext() == null) {
    81.             System.out.println("链表为空");
    82.             return;
    83.         }
    84.         HeroNode preNode, nextNode;
    85.         preNode = headNode;
    86.         nextNode = headNode.getNext();
    87.         while (nextNode != null) {
    88.             if (nextNode.getNo() == newHeroNode.getNo()) {
    89.                 newHeroNode.setNext(nextNode.getNext());
    90.                 preNode.setNext(newHeroNode);
    91.                 return;
    92.             }
    93.             preNode = nextNode;
    94.             nextNode = nextNode.getNext();
    95.         }
    96.         System.out.println("编号= " + newHeroNode.getNo() + " 的元素没有找到");
    97.     }
    98.  
    99.     public void add(HeroNode heroNode) {
    100.         HeroNode nextNode, preNode;
    101.         preNode = headNode;
    102.         nextNode = headNode.getNext();
    103.         // 头插法
    104.         if (nextNode == null) {
    105.             headNode.setNext(heroNode);
    106.             heroNode.setNext(null);
    107.             return;
    108.         }
    109.         // 中插法
    110.         while (nextNode != null) {
    111.             if (heroNode.getNo() < nextNode.getNo()) {
    112.                 preNode.setNext(heroNode);
    113.                 heroNode.setNext(nextNode);
    114.                 return;
    115.             }
    116.             // 相同的数据不能进行插入
    117.             if (heroNode.getNo() == nextNode.getNo()) {
    118.                 System.out.println("编号=" + heroNode.getNo() + " 已存在，不能添加");
    119.                 return;
    120.             }
    121.             preNode = nextNode;
    122.             nextNode = nextNode.getNext();
    123.         }
    124.         // 尾插法
    125.         preNode.setNext(heroNode);
    126.         heroNode.setNext(null);
    127.     }
    128.  
    129.     public void list() {
    130.         HeroNode tmpNode = headNode.getNext();
    131.         if (tmpNode == null) {
    132.             System.out.println("链表为空");
    133.             return;
    134.         }
    135.         while (tmpNode != null) {
    136.             System.out.println("node= " + tmpNode + " -->");
    137.             tmpNode = tmpNode.getNext();
    138.         }
    139.     }
    140. }
    141.  
    142. @Data
    143. class HeroNode {
    144.     private int no;
    145.     private String name;
    146.     private String nickName;
    147.     private HeroNode next;
    148.  
    149.     public HeroNode(int hNo, String hName, String hNickName) {
    150.         this.no = hNo;
    151.         this.name = hName;
    152.         this.nickName = hNickName;
    153.     }
    154.  
    155.     @Override
    156.     public String toString() {
    157.         return "HeroNode{" +
    158.                 "no=" + no +
    159.                 ", name='" + name + '\'' +
    160.                 ", nickName='" + nickName + '\'' +
    161.                 '}';
    162.     }
    163. }

    约瑟夫环问题

    1. public class Josephu {
    2.     public static void main(String[] args) {
    3.         CircleSingleLinkedList list = new CircleSingleLinkedList();
    4.         list.addBoy(5);
    5.         list.countBoy(1, 2, 5);
    6. //        list.showBoy();
    7.     }
    8. }
    9.  
    10. class CircleSingleLinkedList {
    11.     private Boy first = null;
    12.  
    13.     public void addBoy(int nums) {
    14.         if (nums < 2) {
    15.             System.out.println("nums的值不正确");
    16.             return;
    17.         }
    18.         Boy curBoy = null;
    19.         for (int i = 0; i < nums; i++) {
    20.             Boy boy = new Boy(i + 1);
    21.             if (i == 0) {
    22.                 first = boy;
    23.                 first.setNext(first);
    24.                 curBoy = first;
    25.             } else {
    26.                 curBoy.setNext(boy);
    27.                 boy.setNext(first);
    28.                 curBoy = boy;
    29.             }
    30.         }
    31.     }
    32.  
    33.     public void showBoy() {
    34.         if (first == null) {
    35.             System.out.println("链表为空");
    36.             return;
    37.         }
    38.         Boy curBoy = first;
    39.         do {
    40.             System.out.println("编号= " + curBoy.getNo() + " -->");
    41.             curBoy = curBoy.getNext();
    42.         } while (curBoy != first);
    43.     }
    44.  
    45.     /**
    46.      * @param startNo  从第几个开始
    47.      * @param countNum 数几下
    48.      * @param nums     最初有多少个小孩
    49.      */
    50.     public void countBoy(int startNo, int countNum, int nums) {
    51.         if (first == null || startNo < 1 || startNo > nums) {
    52.             System.out.println("参数输入有误，请重新输入");
    53.             return;
    54.         }
    55.         Boy helper = first;
    56.         while (helper.getNext() != first) {
    57.             helper = helper.getNext();
    58.         }
    59.         for (int i = 0; i < startNo - 1; i++) {
    60.             first = first.getNext();
    61.             helper = helper.getNext();
    62.         }
    63.         while (helper != first) {
    64.             for (int i = 0; i < countNum - 1; i++) {
    65.                 first = first.getNext();
    66.                 helper = helper.getNext();
    67.             }
    68.             System.out.println("小孩 " + first.getNo() + " 出圈");
    69.             first = first.getNext();
    70.             helper.setNext(first);
    71. //            nums--;
    72.         }
    73.         System.out.println("最后留在圈中的小孩编号 " + first.getNo());
    74.     }
    75. }
    76.  
    77. class Boy {
    78.     private int no;
    79.     private Boy next;
    80.  
    81.     public Boy(int no) {
    82.         this.no = no;
    83.     }
    84.  
    85.     //#region get|set
    86.     public int getNo() {
    87.         return no;
    88.     }
    89.  
    90.     public void setNo(int no) {
    91.         this.no = no;
    92.     }
    93.  
    94.     public Boy getNext() {
    95.         return next;
    96.     }
    97.  
    98.     public void setNext(Boy next) {
    99.         this.next = next;
    100.     }
    101.     //#endregion
    102. }

    非线性结构

    常见的非线性结构有：二维数组、多维数组、广义表、树结构、图结构。

    图结构

    递归解决迷宫问题

    1. public class MiGong {
    2.     public static void main(String[] args) {
    3.         int[][] map = new int[8][7]; // 1 墙 0 未走 2 已走
    4.         for (int i = 0; i < 7; i++) {
    5.             map[0][i] = 1;
    6.             map[7][i] = 1;
    7.             map[i][0] = 1;
    8.             map[i][6] = 1;
    9.         }
    10.         map[3][1] = 1;
    11.         map[3][2] = 1;
    12.         setWay(map, 1, 1);
    13.     }
    14.  
    15.     public static boolean setWay(int[][] map, int i, int j) {
    16.         if (map[6][5] == 2) {
    17.             return true;
    18.         } else {
    19.             if (map[i][j] == 0) {
    20.                 map[i][j] = 2;
    21.                 if (setWay(map, i + 1, j)) { // 上
    22.                     return true;
    23.                 } else if (setWay(map, i, j + 1)) { // 又
    24.                     return true;
    25.                 } else if (setWay(map, i - 1, j)) { // 下
    26.                     return true;
    27.                 } else if (setWay(map, i, j - 1)) { // 左
    28.                     return true;
    29.                 } else {
    30.                     map[i][j] = 3; // 已走未通过
    31.                     return false;
    32.                 }
    33.             } else {
    34.                 return false; // 值可能是 1、2、3
    35.             }
    36.         }
    37.     }
    38. }

    递归解决八皇后问题

    1. public class Queue8 {
    2.     int max = 8;
    3.     int[] array = new int[max];
    4.  
    5.     /**
    6.      * 有几种解法
    7.      **/
    8.     int count = 0;
    9.     // int judgeCount=0;
    10.  
    11.     public static void main(String[] args) {
    12.         Queue8 queue8 = new Queue8();
    13.         queue8.check(0);
    14.         // System.out.println("解法count=" + queue8.count + "种");
    15.     }
    16.  
    17.     /**
    18.      * 放置第n个皇后
    19.      *
    20.      * @param n
    21.      */
    22.     private void check(int n) {
    23.         if (n == max) {
    24.             print();
    25.             return;
    26.         }
    27.         for (int i = 0; i < max; i++) {
    28.             array[n] = i;
    29.             if (judge(n)) { // 不冲突
    30.                 check(n + 1);
    31.             }
    32.         }
    33.     }
    34.  
    35.     /**
    36.      * 是否与之前的皇后冲突
    37.      *
    38.      * @param n 第n个皇后，从0开始
    39.      * @return
    40.      */
    41.     private boolean judge(int n) {
    42.         // judgeCount++;
    43.         for (int i = 0; i < n; i++) {
    44.             if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[i] - array[n])) { // 同列 同斜线
    45.                 return false;
    46.             }
    47.         }
    48.         return true;
    49.     }
    50.  
    51.     private void print() {
    52.         for (int i = 0; i < array.length; i++) {
    53.             System.out.print(array[i] + " ");
    54.         }
    55.         System.out.println();
    56.         count++;
    57.     }
    58. }

    树结构

    数据结构和算法——树结构-CSDN博客

    增强的顺序结构

    哈希表

    是数组加链表的数据结构，用到了拉链法。

    实例问题：

    有一个公司，当有新员工来报道时，要求将该员工的信息加入（id，性别，年龄，住址...），当输入该员工的id时，要求查找到该员工的所有信息。

    1. public class HashTableDemo {
    2.     public static void main(String[] args) {
    3.         HashTable hashTable = new HashTable(7);
    4.         String key = "";
    5.         Scanner scanner = new Scanner(System.in);
    6.         boolean loop = true;
    7.         while (loop) {
    8.             System.out.println("add：添加雇员");
    9.             System.out.println("list：显示雇员");
    10.             System.out.println("find：查找雇员");
    11.             System.out.println("del：删除雇员");
    12.             System.out.println("exit：退出系统");
    13.             key = scanner.nextLine();
    14.             switch (key) {
    15.                 case "a":
    16.                     System.out.println("输入id：");
    17.                     int id = scanner.nextInt();
    18.                     System.out.println("输入名字：");
    19.                     String name = scanner.next();
    20.                     Emp emp = new Emp(id, name);
    21.                     hashTable.add(emp);
    22.                     continue;
    23.                 case "l":
    24.                     hashTable.list();
    25.                     break;
    26.                 case "d":
    27.                     System.out.println("输入id：");
    28.                     id = scanner.nextInt();
    29.                     hashTable.delEmpById(id);
    30.                     break;
    31.                 case "f":
    32.                     System.out.println("输入id：");
    33.                     id = scanner.nextInt();
    34.                     emp = hashTable.findEmpById(id);
    35.                     if (emp == null) {
    36.                         System.out.println("该雇员不存在");
    37.                     } else {
    38.                         System.out.println(emp);
    39.                     }
    40.                     break;
    41.                 case "e":
    42.                     loop = false;
    43.                     break;
    44.                 default:
    45.                     loop = true;
    46.                     break;
    47.             }
    48.         }
    49.     }
    50. }
    51.  
    52. class Emp {
    53.     public int id;
    54.     public String name;
    55.     public Emp next;
    56.  
    57.     public Emp(int id, String name) {
    58.         this.id = id;
    59.         this.name = name;
    60.         this.next = next;
    61.     }
    62.  
    63.     @Override
    64.     public String toString() {
    65.         return "Emp{" +
    66.                 "id=" + id +
    67.                 ", name='" + name + '\'' +
    68.                 '}';
    69.     }
    70. }
    71.  
    72. class EmpLinkedList {
    73.     private Emp head;
    74.  
    75.     public EmpLinkedList(Emp head) {
    76.         this.head = head;
    77.     }
    78.  
    79.     public void add(Emp emp) {
    80.         if (head == null) {
    81.             head = emp;
    82.         } else {
    83.             Emp curEmp = head;
    84.             while (curEmp.next != null) {
    85.                 curEmp = curEmp.next;
    86.             }
    87.             curEmp.next = emp;
    88.         }
    89.     }
    90.  
    91.     public void list() {
    92.         if (head == null) {
    93.             System.out.println("当前链表为空");
    94.             return;
    95.         }
    96.         System.out.println("当前链表的信息为：");
    97.         Emp curEmp = head;
    98.         while (curEmp != null) {
    99.             System.out.println("emp= " + curEmp);
    100.             curEmp = curEmp.next;
    101.         }
    102.     }
    103.  
    104.     public Emp findEmpById(int id) {
    105.         Emp curEmp = head;
    106.         while (curEmp != null) {
    107.             if (curEmp.id == id) {
    108.                 return curEmp;
    109.             }
    110.             curEmp = curEmp.next;
    111.         }
    112.         return null;
    113.     }
    114.  
    115.     public void delEmpById(int id) {
    116.         if (head == null) {
    117.             System.out.println("该雇员不存在");
    118.             return;
    119.         }
    120.         if (head.id == id) {
    121.             head = null;
    122.             return;
    123.         }
    124.         Emp curEmp = head;
    125.         while (curEmp.next != null) {
    126.             if (curEmp.next.id == id) {
    127.                 curEmp.next = curEmp.next.next;
    128.                 System.out.println("删除雇员成功");
    129.                 return;
    130.             }
    131.             curEmp = curEmp.next;
    132.         }
    133.         System.out.println("该雇员不存在");
    134.     }
    135. }
    136.  
    137. class HashTable {
    138.     private EmpLinkedList[] empListedListArray;
    139.     private int size;
    140.  
    141.     public HashTable(int size) {
    142.         this.size = size;
    143.         this.empListedListArray = new EmpLinkedList[this.size];
    144.     }
    145.  
    146.     public void add(Emp emp) {
    147.         // 根据id得到下标
    148.         int index = hashFun(emp.id);
    149.         if (empListedListArray[index] == null) {
    150.             EmpLinkedList empLinkedList = new EmpLinkedList(emp);
    151.             empListedListArray[index] = empLinkedList;
    152.         } else {
    153.             empListedListArray[index].add(emp);
    154.         }
    155.     }
    156.  
    157.     public int hashFun(int id) {
    158.         return id % this.size;
    159.     }
    160.  
    161.     public void list() {
    162.         for (int i = 0; i < this.size; i++) {
    163.             EmpLinkedList empLinkedList = empListedListArray[i];
    164.             if (empLinkedList != null) {
    165.                 empLinkedList.list();
    166.                 System.out.println("----------------");
    167.             }
    168.         }
    169.     }
    170.  
    171.     public Emp findEmpById(int id) {
    172.         int index = hashFun(id);
    173.         if (empListedListArray[index] == null) {
    174.             return null;
    175.         }
    176.         Emp emp = empListedListArray[index].findEmpById(id);
    177.         return emp;
    178.     }
    179.  
    180.     public void delEmpById(int id) {
    181.         int index = hashFun(id);
    182.         if (empListedListArray[index] == null) {
    183.             System.out.println("该雇员不存在");
    184.             return;
    185.         }
    186.         empListedListArray[index].delEmpById(id);
    187.     }
    188. }

    数组加二叉树的结构。

    参考教程视频：【尚硅谷】数据结构与算法（Java数据结构与算法）_哔哩哔哩_bilibili

  • 相关阅读:
    修改ubuntu终端目录背景颜色
    【笔试强训选择题】Day35.习题（错题）解析
    FDTD script command （对结构/数据操作）
    Dreamweaver网页作业——紫罗兰永恒花园动漫价绍网页 7页，含有table表格，js表单验证还有首页视频。以及列表页。浮动布局。div+css+js
    [YOLOv7]基于YOLO＆Deepsort的车速＆车流量检测系统(源码＆部署教程)
    [Kubernetes] 多调度器(1/3)：如何编译scheduler，以默认调度器 kube-scheduler为例
    k8s二进制（ETCD的部署安装）
    Android 11 AudioPolicyService 启动流程
    【Flink源码】再谈Flink程序提交流程（下）
    浏览器插件不会装？保姆级教程分享！
  • 原文地址：https://blog.csdn.net/m0_58961367/article/details/133584081