线性结构

特点：数据元素之间存在一对一的线性关系

存在两种不同的存储结构，分别为顺序存储结构和链式存储结构

  • 顺序存储的线性表：称为顺序表，顺序表中的存储元素是连续的
  • 链式存储的线性表：称为链表，链表中的存储元素不一定是连续的

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

1. 队列

介绍

  1. 队列是一个有序列表，可以用数组或者链表来实现
  2. 遵循先入先出的原则，也就是先存入队列的数据要先取出，后存入的要后取出
  3. 在结构图中有两个指针（也就是头指针front和尾指针rear），加数据时尾指针变化，出数据时头指针变化（总结来说：头出尾入）

数组模拟队列

  1. 使用数组的结构来存储队列的数据，在自己创建的队列类ArrayQueue中需要有四个属性，分别为maxSize、front、rear和arr
    • maxSize：int类型，表示队列的最大容量
    • front：int类型，头指针，也就是下一个该出的数据的位置
    • rear：int类型，尾指针，也就是刚刚进入的数据的位置
    • arr：int[]类型，存队列数据的数组
  2. 该类中存在的方法需要实现的功能
    • 判断队列是否已满
    • 判断队列是否为空
    • 添加数据到队列中
    • 从队列中取出数据
    • 查看队列中的所有数据
    • 查看队列中的头元素（不是取出，仅仅是查看）
  3. ArrayQueue类代码的实现
  1. package unimproved;
  3. public class ArrayQueue {
  5.     private int maxSize; //表示队列的最大容量
  6.     private int front; //队列的头
  7.     private int rear; //队列的尾
  8.     private int[] arr; //该数组用于存放数据
  10.     public ArrayQueue() {
  12.     }
  14.     public ArrayQueue(int maxSize) {
  15.         this.maxSize = maxSize;
  16.         arr = new int[this.maxSize];
  17.         front = -1; //指向队列头的前一个位置
  18.         rear = -1; //指向队列中尾部的数据
  19.     }
  21.     public void setMaxSize(int maxSize) {
  22.         this.maxSize = maxSize;
  23.     }
  25.     public int getMaxSize() {
  26.         return maxSize;
  27.     }
  29.     public int getFront() {
  30.         return front;
  31.     }
  33.     public int getRear() {
  34.         return rear;
  35.     }
  37.     //判断队列是否已满
  38.     public boolean isFull() {
  39.         return rear == maxSize - 1;
  40.     }
  42.     //判断队列是否为空
  43.     public boolean isEmpty() {
  44.         return front == rear;
  45.     }
  47.     //添加数据到队列
  48.     public void addQueue(int n) {
  49.         //判断队列是否已满
  50.         if (isFull()) {
  51.             System.out.println("队列已满，不能再向队列中添加数据...");
  52.             return;
  53.         }
  55.         //加数据
  56.         rear++;//让rear后移
  57.         arr[rear] = n;
  58.     }
  60.     //获取队列的数据，出队列
  61.     public int getQueue() {
  62.         //判断队列是否为空
  63.         if (isEmpty()) {
  64.             //通过抛出异常
  65.             throw new RuntimeException("队列为空，没有数据可出队列...");
  66.         }
  68.         //出数据
  69.         front++;//让front后移
  70.         return arr[front];
  71.     }
  73.     //显示队列的所有数据
  74.     public void showQueue() {
  75.         //判断队列是否为空
  76.         if (isEmpty()) {
  77.             System.out.println("队列为空，没有数据可查看...");
  78.             return;
  79.         }
  81.         //遍历arr数组
  82.         for (int e : arr) {
  83.             System.out.printf("%d ", e);
  84.         }
  85.         System.out.println();
  86.     }
  88.     //显示队列的头数据，并不是取出，就只是查看
  89.     public int headQueue() {
  90.         //判断队列是否为空
  91.         if (isEmpty()) {
  92.             //通过抛出异常
  93.             throw new RuntimeException("队列为空，没有头数据...");
  94.         }
  96.         return arr[front + 1];
  97.     }
  98. }
  1. ArrayQueueDemo测试类代码
  1. package unimproved;
  3. import java.util.Scanner;
  5. public class ArrayQueueDemo {
  7.     public static void main(String[] args) {
  8.         //初始化一个队列
  9.         ArrayQueue arrayQueue = new ArrayQueue(3);
  10.         char key = ' '; //接受用户输入
  12.         Scanner input = new Scanner(System.in);
  13.         boolean loop = true;
  15.         //输出一个菜单
  16.         while(loop) {
  17.             System.out.println("------------------------------");
  18.             System.out.println("s(show)：显示队列");
  19.             System.out.println("a(add)：添加数据到队列");
  20.             System.out.println("g(get)：从队列取出数据");
  21.             System.out.println("h(head)：查看队列的头数据");
  22.             System.out.println("e(exit)：退出程序");
  23.             System.out.println("------------------------------");
  24.             key = input.next().charAt(0);//接受一个字符
  25.             switch (key) {
  26.                 case 's':
  27.                     arrayQueue.showQueue();
  28.                     break;
  29.                 case 'a':
  30.                     System.out.println("请输入一个整数：");
  31.                     int number = input.nextInt();
  32.                     arrayQueue.addQueue(number);
  33.                     break;
  34.                 case 'g':
  35.                     try {
  36.                         int result = arrayQueue.getQueue();
  37.                         System.out.println("从队列取出的数据是：" + result);
  38.                     } catch (Exception e) {
  39.                         System.out.println(e.getMessage());
  40.                     }
  41.                     break;
  42.                 case 'h':
  43.                     try {
  44.                         int result = arrayQueue.headQueue();
  45.                         System.out.println("队列的头数据时：" + result);
  46.                     } catch (Exception e) {
  47.                         System.out.println(e.getMessage());
  48.                     }
  49.                     break;
  50.                 case 'e':
  51.                     input.close();
  52.                     loop = false;
  53.                     System.out.println("程序已退出...");
  54.                     break;
  55.                 default:
  56.                     break;
  57.             }
  58.         }
  59.     }
  61. }
  1. 发现该代码有缺陷，只能使用一次该数组，进行代码优化，数据模拟环形队列

数组模拟环形队列

  1. front变量的含义做一个调整，指向队列的第一个元素，之前是指向第一个元素的前一个位置，也就是arr[front]是低于个元素，不再是arr[front+1]，front的初始值为0
  2. rear变量的含义做一个调整，rear指向队列的最后一个元素的后一个位置，因为希望空出一个空间作为约定，rear的初始值为0
  3. 当队列满时，(rear + 1) % maxSize == front为true，这里取模是考虑到了当rear在arr最末尾跳到arr最前方，实现循环队列，后面取模运算皆是考虑到这里
  4. 当队列为空，front与rear相等时
  5. 队列中有效的数据的个数为(rear + maxSize - front) % maxSize
  6. 思考过以上几点后，就可以在数组模拟队列的代码上进行修改
  7. CircleQueue类代码的实现
  1. package improved;
  3. public class CircleQueue {
  5.     private int maxSize; //表示队列的最大容量
  6.     private int front; //队列的头，指向队列头一个数据的位置，这里初始值就为0，不用重新赋值
  7.     private int rear; //队列的尾，指向队列中尾部的数据的下一个位置，这里初始值就为0，不用重新赋值
  8.     private int[] arr; //该数组用于存放数据
  10.     public CircleQueue() {
  12.     }
  14.     public CircleQueue(int maxSize) {
  15.         this.maxSize = maxSize;
  16.         arr = new int[this.maxSize];
  17.     }
  19.     public void setMaxSize(int maxSize) {
  20.         this.maxSize = maxSize;
  21.     }
  23.     public int getMaxSize() {
  24.         return maxSize;
  25.     }
  27.     public int getFront() {
  28.         return front;
  29.     }
  31.     public int getRear() {
  32.         return rear;
  33.     }
  35.     //判断队列是否已满
  36.     public boolean isFull() {
  37.         return (rear + 1) % maxSize == front;
  38.     }
  40.     //判断队列是否为空
  41.     public boolean isEmpty() {
  42.         return front == rear;
  43.     }
  45.     //获取当前队列的有效数据个数
  46.     public int effectiveLength() {
  47.         return (rear + maxSize -front) % maxSize;
  48.     }
  51.     //添加数据到队列
  52.     public void addQueue(int n) {
  53.         //判断队列是否已满
  54.         if (isFull()) {
  55.             System.out.println("队列已满，不能再向队列中添加数据...");
  56.             return;
  57.         }
  59.         //加数据
  60.         arr[rear] = n;//先加入值
  61.         rear = (rear + 1) % maxSize;//再将rear后移，这里考虑回到数组最前面
  62.     }
  64.     //获取队列的数据，出队列
  65.     public int getQueue() {
  66.         //判断队列是否为空
  67.         if (isEmpty()) {
  68.             //通过抛出异常
  69.             throw new RuntimeException("队列为空，没有数据可出队列...");
  70.         }
  72.         //出数据
  73.         int temp = arr[front];//先将要出队的值保存在一个临时变量中，因为如果先直接return，后面的代码将不会运行，使得front不能移动
  74.         front = (front + 1) % maxSize;
  75.         return temp;
  76.     }
  78.     //显示队列的所有数据
  79.     public void showQueue() {
  80.         //判断队列是否为空
  81.         if (isEmpty()) {
  82.             System.out.println("队列为空，没有数据可查看...");
  83.             return;
  84.         }
  86.         //从front开始遍历，遍历多少个元素
  87.         for (int i = front; i < front + effectiveLength(); i++ ) {
  88.             System.out.printf("%d ", arr[i % maxSize]);
  89.         }
  90.         System.out.println();
  91.     }
  93.     //显示队列的头数据，并不是取出，就只是查看
  94.     public int headQueue() {
  95.         //判断队列是否为空
  96.         if (isEmpty()) {
  97.             //通过抛出异常
  98.             throw new RuntimeException("队列为空，没有头数据...");
  99.         }
  101.         return arr[front];
  102.     }
  103. }
  1. CircleQueueDemo测试类代码
  1. package improved;
  3. import java.util.Scanner;
  5. public class CircleQueueDemo {
  7.     public static void main(String[] args) {
  8.         //初始化一个队列
  9.         CircleQueue arrayQueue = new CircleQueue(4);//这里的队列长度最大为3，留了一个空位
  10.         char key = ' '; //接受用户输入
  12.         Scanner input = new Scanner(System.in);
  13.         boolean loop = true;
  15.         //输出一个菜单
  16.         while(loop) {
  17.             System.out.println("---------- -环形队列-----------");
  18.             System.out.println("s(show)：显示队列");
  19.             System.out.println("a(add)：添加数据到队列");
  20.             System.out.println("g(get)：从队列取出数据");
  21.             System.out.println("h(head)：查看队列的头数据");
  22.             System.out.println("e(exit)：退出程序");
  23.             System.out.println("------------------------------");
  24.             key = input.next().charAt(0);//接受一个字符
  25.             switch (key) {
  26.                 case 's':
  27.                     arrayQueue.showQueue();
  28.                     break;
  29.                 case 'a':
  30.                     System.out.println("请输入一个整数：");
  31.                     int number = input.nextInt();
  32.                     arrayQueue.addQueue(number);
  33.                     break;
  34.                 case 'g':
  35.                     try {
  36.                         int result = arrayQueue.getQueue();
  37.                         System.out.println("从队列取出的数据是：" + result);
  38.                     } catch (Exception e) {
  39.                         System.out.println(e.getMessage());
  40.                     }
  41.                     break;
  42.                 case 'h':
  43.                     try {
  44.                         int result = arrayQueue.headQueue();
  45.                         System.out.println("队列的头数据时：" + result);
  46.                     } catch (Exception e) {
  47.                         System.out.println(e.getMessage());
  48.                     }
  49.                     break;
  50.                 case 'e':
  51.                     input.close();
  52.                     loop = false;
  53.                     System.out.println("程序已退出...");
  54.                     break;
  55.                 default:
  56.                     break;
  57.             }
  58.         }
  59.     }
  61. }

2.链表

介绍

  1. 链表是有序的列表，但其实在存储中别不一定是有序的，链式存储
  2. 链表是以节点的方式来存储的
  3. 每个节点包含data域，next域（指向下一个节点，也就是下一个节点的地址）
  4. 链表分为带头节点（不存放具体的数据）的链表和没有头节点的链表，根据自己的需求选择

单向链表

  1. 使用带head头的单向链表实现水浒英雄排行榜管理，完成对英雄人物的增删改查操作，在添加英雄时，一种是直接添加到链表的尾部，另一种是添加到指定位置，若要添加的英雄已存在链表，则会添加失败，并给出提示
  2. 添加（创建）单链表实现思路
    • 先创建一个head头节点，作用就是表示单链表的头
    • 后面每添加一个节点，就直接加入到链表的最后
  3. 遍历单链表实现思路
    • 通过一个辅助变量来实现整个单链表的遍历
  4. 需要按照编号顺序添加
    • 首先找到新添加节点的位置，通过辅助变量来找到
    • 新节点.next = temp.next
    • 让temp.next = 新节点
    • 通过遍历来寻找对应位置
  5. 从单链表中删除指定节点
    • 指定一个辅助变量，来找到需要删除节点的前一个节点
    • temp.next = temp.next.next
    • 被删除的节点，将不会有其他引用指向，会被垃圾回收机制回收

  6. 代码实现

    • 节点类HeroNode

      1. //定义HeroNode，每个HeroNode对象就是一个节点
      2. public class HeroNode {
      4. public int serialNumber;//序号
      5. public String name;//姓名
      6. public String nickName;//昵称
      7. public HeroNode next;//指向下一个节点
      9. public HeroNode() {}
      11. public HeroNode(int serialNumber, String name, String nickName) {
      12.    this.serialNumber = serialNumber;
      13.    this.name = name;
      14.    this.nickName = nickName;
      15. }
      17. @Override
      18. public String toString() {
      19.    return "HeroNode{" +
      20.            "serialNumber=" + serialNumber +
      21.            ", name='" + name + '\'' +
      22.            ", nickName='" + nickName + '\'' +
      23.            '}';
      24. }
      25. }

    • 链表类SingleLinkedList

      1. //定义SingleLinkedList，管理我们的水浒英雄们
      2. public class SingleLinkedList {
      4. //先初始化头节点，头节点不要改变，若是改变了整个链表都找不到了
      5. private HeroNode head = new HeroNode(0, "", "");
      7. public SingleLinkedList() {}
      9. public HeroNode getHead() {
      10.    return head;
      11. }
      13. //添加节点到单向链表（链表末端）
      14. //思路：
      15. //当不考虑编号顺序时
      16. //1. 找到当前链表的最后节点
      17. //2. 将最后这个节点的next指向新的节点
      18. public void add(HeroNode heroNode) {
      20.    //因为head节点不能动，我们需要一个辅助指针遍历temp
      21.    HeroNode temp = head;
      22.    //遍历链表，找到最后
      23.    while (true) {
      24.        //找到链表的最后
      25.        if (temp.next == null) {
      26.            break;
      27.        }
      28.        //如果没有找到最后,将节点后移
      29.        temp = temp.next;
      30.    }
      31.    //当退出while循环时，temp就指向了链表的最后
      32.    //将最后这个节点的next指向新的节点
      33.    temp.next = heroNode;
      34. }
      36. //添加节点到链表，按照标号大小顺序插入
      37. public void addByOrder(HeroNode heroNode) {
      38.    //因为头节点不能动，用辅助指针代替
      39.    HeroNode temp = head;
      40.    boolean flag = false;//标志新添加的英雄是否存在，这里默认不存在
      41.    while(true) {
      42.        if (temp.next == null) {//说明temp已经是链表的最后一个节点
      43.            break;
      44.        }
      45.        if (temp.next.serialNumber > heroNode.serialNumber) {//位置找到了，就在temp后方
      46.            break;
      47.        } else if (temp.next.serialNumber == heroNode.serialNumber) {//若成立，说明该节点单链表中已存在
      48.            flag = true;
      49.            break;
      50.        }
      51.        temp = temp.next;
      52.    }
      53.    if (flag) {
      54.        System.out.println("准备存入的英雄的编号" + heroNode.serialNumber + "已经存在，不能加入");
      55.    } else {
      56.        heroNode.next = temp.next;
      57.        temp.next = heroNode;
      58.    }
      59. }
      61. //修改节点信息，很久编号来修改，即编号不能变
      62. public void update(HeroNode newHeroNode) {
      63.    //先判断链表是否为空
      64.    if (head.next == null) {
      65.        System.out.println("链表为空，修改失败...");
      66.        return;
      67.    }
      68.    HeroNode temp = head.next;
      69.    boolean flag = false;//表示是否找到需要修改的节点
      70.    while (true) {
      71.        if (temp == null) {
      72.            break;//已经遍历完
      73.        }
      74.        if (temp.serialNumber == newHeroNode.serialNumber) {
      75.            flag = true;
      76.            break;
      77.        }
      78.        temp = temp.next;
      79.    }
      80.    //根据flag判断是否找到
      81.    if (flag) {
      82.        temp.name = newHeroNode.name;
      83.        temp.nickName = newHeroNode.nickName;
      84.    } else {//没有找到
      85.        System.out.println("没有找到编号为" + newHeroNode.serialNumber + "的英雄...");
      86.    }
      87. }
      89. //删除指定节点
      90. //head不能动，因此我们需要辅助指针来指向待删除节点的前一个节点
      91. public void del(int serialNumber) {
      92.    HeroNode temp = head;
      93.    boolean flag = false;//标志是否找到待删除节点
      94.    while (true) {
      95.        if (temp.next == null) {
      96.            break;
      97.        }
      98.        if (temp.next.serialNumber == serialNumber) {
      99.            //找到了待删除节点的前一个节点temp
      100.            flag = true;
      101.            break;
      102.        }
      103.        temp = temp.next;
      104.    }
      105.    //判断flag
      106.    if (flag) {
      107.        temp.next = temp.next.next;
      108.    } else {
      109.        System.out.println("要删除的编号" + serialNumber + "不存在...");
      110.    }
      111. }
      113. //遍历链表
      114. public void list() {
      115.    //判断链表是否为空
      116.    if (head.next == null) {
      117.        System.out.println("链表为空...");
      118.        return;
      119.    }
      120.    //因为头节点不能动，我们需要一个辅助变量temp来遍历链表
      121.    HeroNode temp = head.next;
      122.    while (true) {
      123.        //判断是否到了链表的最后
      124.        if (temp == null) {
      125.            break;
      126.        }
      127.        //不为空就输出该节点信息
      128.        System.out.println(temp.toString());
      129.        //将temp后移
      130.        temp = temp.next;
      131.    }
      132. }

}

  2. - 测试类SingleLinkedListDemo
  4. ```java
  5. public class SingleLinkedListDemo {
  7.     public static void main(String[] args) {
  8.         //进行测试
  9.         //先创建节点
  10.         HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  11.         HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  12.         HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  13.         HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
  14.         HeroNode hero5 = new HeroNode(3, "吴用", "智多星");
  16.         //创建链表
  17.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  18.         //向链表中加入英雄
  19.         singleLinkedList.addByOrder(hero1);
  20.         singleLinkedList.addByOrder(hero3);
  21.         singleLinkedList.addByOrder(hero4);
  22.         singleLinkedList.addByOrder(hero2);
  23.         singleLinkedList.addByOrder(hero5);
  24. //        //向链表中加入英雄
  25. //        singleLinkedList.add(hero1);
  26. //        singleLinkedList.add(hero2);
  27. //        singleLinkedList.add(hero3);
  28. //        singleLinkedList.add(hero4);
  29.         //遍历
  30.         singleLinkedList.list();
  32.         HeroNode newHero2 = new HeroNode(2, "小卢","小麒麟");
  33.         //测试修改节点的代码
  34.         singleLinkedList.update(newHero2);
  36.         System.out.println("修改后再次遍历...");
  37.         //遍历
  38.         singleLinkedList.list();
  40.         singleLinkedList.del(1);
  41.         singleLinkedList.del(4);
  42.         singleLinkedList.del(3);
  43.         singleLinkedList.del(2);
  45.         System.out.println("删除后再次遍历...");
  46.         //遍历
  47.         singleLinkedList.list();
  48.     }
  50. }

单链表面试题

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

    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.      }
    12.      int length = 0;
    14.      //定义一个辅助变量
    15.      HeroNode cur = head.next;
    16.      while (cur != null) {
    17.          length++;
    18.          cur = cur.next;
    19.      }
    20.      return length;
    21.  }

  2. 查找单链表中的倒数第k个节点（新浪面试题）

    1.  //查找单链表中的倒数第k个节点
    2.  /**
    3.   *
    4.   * @param head 表示头节点
    5.   * @param index 要找的倒数第几个节点
    6.   * @return 返回的指定节点，
    7.   */
    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便是我们想要得到的节点
    16.      if (index <= 0 || index > size) {
    17.          return null;
    18.      }
    19.      //定义辅助变量
    20.      HeroNode cur = head.next;
    21.      for (int i = 0; i < (size - index); i++) {//这里注意循环次数
    22.          cur = cur.next;
    23.      }
    24.      return cur;
    25.  }

  3. 单链表的反转（腾讯面试题）

    1.  //将单链表反转
    2.  //1.先定义一个加节点，reverse = new HeroNode();
    3.  //2. 从头到尾遍历原来的链表，每遍历一个节点，并放在心的链表的最前端
    4.  //3. 最后将原来的head.next = reverse.next
    5.  public static void reverseList(HeroNode head) {
    6.      //如果当前链表为空或者只有一个节点，则不用进行任何操作
    7.      if (head.next == null || head.next.next == null) {
    8.          return;
    9.      }
    11.      //定义一个辅助变量来遍历原单链表
    12.      HeroNode cur = head.next;
    13.      HeroNode next = null;//指向当前节点的下一个节点，不用的话就会丢失后面的节点
    14.      HeroNode reverseHead = new HeroNode(0, "", "");
    15.      //遍历原来的链表，实行反转的功能
    16.      while (cur != null) {
    17.          next = cur.next;//暂时保存当前节点的下一个节点
    18.          cur.next =reverseHead.next;
    19.          reverseHead.next = cur;//这里注意要将反转列表的头节点指向插入的cur（这里用到了头插法思想）
    20.          cur = next;
    21.      }
    22.      head.next = reverseHead.next;
    23.  }

  4. 从尾到头打印单链表（百度面试题，要求方式1：方向遍历；要求方式2：Stack栈）

    1.  //从尾到头打印单链表
    2.  //1. 逆序打印单链表
    3.  //2. 方式1：将单链表反转，再按照顺序打印，但是这样做会破坏原来单链表的结构，不建议这么做
    4.  //3. 方式2：可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，实现逆序打印
    6.  //方式2
    7.  public static void reversePrint(HeroNode head) {
    8.      if (head.next == null) {
    9.          System.out.println("链表为空，没有节点信息可打印...");
    10.          return;
    11.      }
    12.      //创建一个栈
    13.      Stack<HeroNode> stack = new Stack<>();
    14.      HeroNode cur = head.next;
    15.      //将每个节点压入栈中
    16.      while (cur != null) {
    17.          stack.push(cur);
    18.          cur = cur.next;
    19.      }
    20.      //从栈中弹出节点，打印各个节点信息
    21.      while (stack.size() > 0) {
    22.          System.out.println(stack.pop());
    23.      }
    24.  }

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

    1.  //合并两个有序的单链表
    2.  //1. 基本思想就是哪个单链表的节点序号小就先加入到新的单链表的最后面
    3.  //2. 需要考虑的是两个单链表中存在重复的节点，所以在将节点添加到新的单链表的时候需要先判断该节点是否在新单链表中已经存在
    4.  /**
    5.   *
    6.   * @param head1 : 有序单链表1
    7.   * @param head2 : 有序单链表2
    8.   * @return : 返回的是拼接后的有序单链表
    9.   */
    10.  public static HeroNode twoToOne(HeroNode head1, HeroNode head2) {
    11.      //定义新单链表的头节点
    12.      HeroNode newHead = new HeroNode(0,"","");
    14.      //若两个单链表都为空，则直接返回一个空的单链表头节点
    15.      if (head1.next == null && head2.next == null) {
    16.          return newHead;
    17.      }
    18.      //若单链表1为空，则newHead.next直接指向单链表2，head2.next
    19.      if (head1.next == null) {
    20.          newHead.next = head2.next;
    21.          return newHead;
    22.      }
    23.      //若单链表2为空，则newHead.next直接指向单链表1，head1.next
    24.      if (head2.next == null) {
    25.          newHead.next = head1.next;
    26.          return newHead;
    27.      }
    28.      //定义三个辅助变量，分别代替head1、head2和newHead
    29.      HeroNode temp1 = head1.next;
    30.      HeroNode temp2 = head2.next;
    31.      HeroNode newTemp = newHead;
    32.      //再带那个一一个变量，来记录上一个存入新单链表的节点的序号，避免重复
    33.      int flag = 0;
    35.      while (temp1 != null && temp2 !=null) {
    36.          //判断下个节点是否与上一个到新单链表的节点是否重复
    37.          if (flag == temp1.serialNumber) {
    38.              temp1 = temp1.next;
    39.              continue;
    40.          }
    41.          if (flag == temp2.serialNumber) {
    42.              temp2 = temp2.next;
    43.              continue;
    44.          }
    46.          //比较两节点当前位置序号的大小，哪个节点小就加入到新链表末尾，并自己后移
    47.          if (temp1.serialNumber < temp2.serialNumber) {
    48.              newTemp.next = new HeroNode(temp1.serialNumber, temp1.name, temp1.nickName);
    49.              flag = temp1.serialNumber;
    50.              temp1 = temp1.next;
    51.              newTemp = newTemp.next;
    52.          } else {
    53.              newTemp.next = new HeroNode(temp2.serialNumber, temp2.name, temp2.nickName);
    54.              flag = temp2.serialNumber;
    55.              temp2 = temp2.next;
    56.              newTemp = newTemp.next;
    57.          }
    58.      }
    60.      if (temp1 == null) {
    61.          while (temp2 != null) {
    62.              if (flag == temp2.serialNumber) {
    63.                  temp2 = temp2.next;
    64.                  continue;
    65.              }
    66.              newTemp.next = new HeroNode(temp2.serialNumber, temp2.name, temp2.nickName);
    67.              flag = temp2.serialNumber;
    68.              temp2 = temp2.next;
    69.              newTemp = newTemp.next;
    70.          }
    71.      } else {
    72.          while (temp1 != null) {
    73.              if (flag == temp1.serialNumber) {
    74.                  temp1 = temp1.next;
    75.                  continue;
    76.              }
    77.              newTemp.next = new HeroNode(temp1.serialNumber, temp1.name, temp1.nickName);
    78.              flag = temp1.serialNumber;
    79.              temp1 = temp1.next;
    80.              newTemp = newTemp.next;
    81.          }
    82.      }
    83.      return newHead;
    84.  }

  6. 测试代码如下

    1. public static void main(String[] args) {
    2.      //进行测试
    3.      //先创建节点
    4.      HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
    5.      HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
    6.      HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
    7.      HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
    8.      HeroNode hero5 = new HeroNode(3, "吴用", "智多星");
    10.      //创建链表
    11.      SingleLinkedList singleLinkedList = new SingleLinkedList();
    12.      //向链表中加入英雄
    13.      singleLinkedList.addByOrder(hero1);
    14.      singleLinkedList.addByOrder(hero3);
    15.      singleLinkedList.addByOrder(hero4);
    16.      singleLinkedList.addByOrder(hero2);
    17.      singleLinkedList.addByOrder(hero5);
    18. //        //向链表中加入英雄
    19. //        singleLinkedList.add(hero1);
    20. //        singleLinkedList.add(hero2);
    21. //        singleLinkedList.add(hero3);
    22. //        singleLinkedList.add(hero4);
    23.      //遍历
    24.      singleLinkedList.list();
    26.      HeroNode newHero2 = new HeroNode(2, "小卢","小麒麟");
    27.      //测试修改节点的代码
    28.      singleLinkedList.update(newHero2);
    30.      System.out.println("修改后再次遍历...");
    31.      //遍历
    32.      singleLinkedList.list();
    34.      singleLinkedList.del(1);
    35. //        singleLinkedList.del(4);
    36. //        singleLinkedList.del(3);
    37. //        singleLinkedList.del(2);
    39.      System.out.println("删除后再次遍历...");
    40.      //遍历
    41.      singleLinkedList.list();
    43.      //测试一下，单链表的有效节点数
    44.      System.out.println("有效的节点个数：" + getLength(singleLinkedList.getHead()));
    46.      //测试一下，是否得到倒数第k个节点
    47.      int index = 2;
    48.      HeroNode res = findLastIndexNode(singleLinkedList.getHead(), index);
    49.      System.out.println("倒数第" + index + "个节点为：" + res);
    50.      System.out.println("反转后的单链表：");
    51.      reverseList(singleLinkedList.getHead());
    52.      singleLinkedList.list();
    54.      //直接反序输出链表个节点(栈)
    55.      System.out.println("反序输出链表各节点信息（没有改变链表自身的结构）：");
    56.      reversePrint(singleLinkedList.getHead());
    58.      System.out.println("------------------------测试合并两链表------------------------");
    60.      SingleLinkedList sll1 = new SingleLinkedList();
    61.      SingleLinkedList sll2 = new SingleLinkedList();
    63.      SingleLinkedList sll3 = new SingleLinkedList();
    65.      sll1.addByOrder(hero1);
    66.      sll1.addByOrder(hero3);
    67.      sll2.addByOrder(hero2);
    68.      sll2.addByOrder(hero4);
    70.      System.out.println("链表1：");
    71.      sll1.list();
    72.      System.out.println("链表2：");
    73.      sll2.list();
    75.      HeroNode temp = twoToOne(sll1.getHead(), sll2.getHead());
    76.      sll3.getHead().next = temp.next;
    78.      System.out.println("链表3：");
    79.      sll3.list();
    80. }

双向链表

  1. 单链表查找的方向只有一个head指向的方向；在单向链表删除节点的时候往往是找到需要删除节点的前一个节点，而不是自我删除；而双向链表便是优化了的数据结构
  2. 分析一下双向链表的遍历、添加、修改、删除的操作思想
    • 遍历方式：和单链表一样，只是可以向前查找，也可以向后查找
    • 添加方式(默认添加到双向链表的最后)：首先通过遍历找到双向链表的最后一个节点，temp.next = newHeroNode;newHeroNode.pre = temp;
    • 修改方式：和单向链表一样，有稍微变动
    • 删除方式：因为是双向链表，因此我们可以实现自我删除某个节点，所以直接找到要删除的节点比如是temp，temp.pre.next = temp.next; temp.next.pre = temp.pre;

  3. 节点类HeroNode代码 ```java package doublylinkedlist;

public class HeroNode {

  1. public int serialNumber;//序号
  2. public String name;//姓名
  3. public String nickName;//昵称
  4. public HeroNode next;//指向下一个节点，默认为null
  5. public HeroNode pre;//指向上一个节点，默认为null
  7. public HeroNode() {
  8. }
  10. public HeroNode(int serialNumber, String name, String nickName) {
  11.     this.serialNumber = serialNumber;
  12.     this.name = name;
  13.     this.nickName = nickName;
  14. }
  16. @Override
  17. public String toString() {
  18.     return "HeroNode{" +
  19.             "serialNumber=" + serialNumber +
  20.             ", name='" + name + '\'' +
  21.             ", nickName='" + nickName + '\'' +
  22.             '}';
  23. }

}

  2. 4. 链表类DoublyLinkedList 代码
  3. ```java
  4. package doublylinkedlist;
  6. public class DoublyLinkedList {
  8.     private HeroNode head = new HeroNode(0, "", "");
  10.     public HeroNode getHead() {
  11.         return head;
  12.     }
  14.     //遍历双向链表
  15.     public void list() {
  16.         //判断该链表是否为空
  17.         if (head.next == null) {
  18.             System.out.println("链表为空...");
  19.             return;
  20.         }
  21.         //辅助节点
  22.         HeroNode temp = head.next;
  23.         //实现遍历
  24.         while (true) {
  25.             //判断链表是否到达了最后
  26.             if (temp == null) {
  27.                 break;
  28.             }
  29.             //输出节点相关信息
  30.             System.out.println(temp);
  31.             //将temp指向下一个节点
  32.             temp = temp.next;
  33.         }
  34.     }
  36.     //添加，默认添加到链表末尾
  37.     public void add(HeroNode heroNode) {
  38.         //辅助节点
  39.         HeroNode temp = head;
  40.         //遍历该链表，找到链表的最后位置
  41.         while (true) {
  42.             if (temp.next == null) {
  43.                 break;
  44.             }
  45.             //如果没有找到，则temp向后移
  46.             temp = temp.next;
  47.         }
  48.         //当退出while循环时，说明temp已经指向了链表最后一个节点
  49.         //添加传入的节点到链表最后
  50.         temp.next = heroNode;
  51.         heroNode.pre = temp;
  52.     }
  54.     //添加，有序的,从小到大，注意这里的判断顺序！！！
  55.     public void addByOrder(HeroNode heroNode) {
  56.         //创建一个辅助变量
  57.         HeroNode temp = head;
  58.         while (true) {
  59.             if (heroNode.serialNumber == temp.serialNumber) {
  60.                 System.out.println("编号为" + heroNode.serialNumber + "的节点已存在，添加失败...");
  61.                 break;
  62.             }
  63.             if (heroNode.serialNumber < temp.serialNumber) {
  64.                 temp.pre.next = heroNode;
  65.                 heroNode.pre = temp.pre;
  66.                 heroNode.next = temp;
  67.                 temp.pre = heroNode;
  68.                 break;
  69.             }
  70.             if (temp.next == null) {
  71.                 temp.next = heroNode;
  72.                 heroNode.pre = temp;
  73.                 break;
  74.             }
  75.             temp = temp.next;
  76.         }
  77.     }
  79.     //修改一个节点的内容
  80.     public void update(HeroNode heroNode) {
  81.         //判断链表是否为空
  82.         if (head.next ==null) {
  83.             System.out.println("链表为空...");
  84.             return;
  85.         }
  86.         //找到需要修改的节点，根据节点编号来找，也就是serialNumber
  87.         //定义一个辅助变量
  88.         HeroNode temp = head.next;
  89.         boolean flag = false;//表示是否找到该节点
  90.         while (true) {
  91.             if (temp == null) {
  92.                 break;//表示已经到链表的末尾了
  93.             }
  94.             if (temp.serialNumber == heroNode.serialNumber) {
  95.                 flag = true;//找到我们要修改的节点了
  96.                 break;
  97.             }
  98.             temp = temp.next;//没找到就继续后移
  99.         }
  100.         //判断flag，是否找到
  101.         if (flag) {
  102.             temp.name = heroNode.name;
  103.             temp.nickName = heroNode.nickName;
  104.         } else {
  105.             System.out.println("没有找到编号为" + heroNode.serialNumber + "的节点，修改失败...");
  106.         }
  107.     }
  109.     //删除双向链表节点，双向链表是直接找到要删除的节点，不用再找到前一个节点
  110.     public void del(int serialNumber) {
  111.         //判断该链表是否为空
  112.         if (head.next == null) {
  113.             System.out.println("链表为空，无法删除...");
  114.             return;
  115.         }
  116.         //定义一个辅助变量
  117.         HeroNode temp = head.next;
  118.         boolean flag = false;//是否找到了要删除的节点
  119.         while(true) {
  120.             if (temp == null) {
  121.                 break;
  122.             }
  123.             if (temp.serialNumber == serialNumber) {
  124.                 flag = true;
  125.                 break;
  126.             }
  127.             temp = temp.next;
  128.         }
  129.         if (flag) {
  130.             temp.pre.next = temp.next;
  131.             if (temp.next != null) {
  132.                 temp.next.pre = temp.pre;//这里要注意当删除最后一个节点时，就不需要执行这句代码，否则会出现空指针异常
  133.             }
  134.         } else {
  135.             System.out.println("没有找到编号为" +serialNumber + "的节点，删除失败...");
  136.         }
  138.     }
  142. }
  1. 测试类DoublyLinkedListDemo代码 ```java package doublylinkedlist;

public class DoublyLinkedListDemo {

  1. public static void main(String[] args) {
  2.     System.out.println("-------------------------双向链表的测试-------------------------");
  3.     //先创建节点
  4.     HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  5.     HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  6.     HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  7.     HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
  10.     DoublyLinkedList doublyLinkedList = new DoublyLinkedList();
  12.     System.out.println("-------------------------双向链表的添加和遍历测试-------------------------");
  13.     doublyLinkedList.add(hero1);
  14.     doublyLinkedList.add(hero2);
  15.     doublyLinkedList.add(hero3);
  16.     doublyLinkedList.add(hero4);
  17.     doublyLinkedList.list();
  19.     System.out.println("-------------------------双向链表的修改测试-------------------------");
  20.     HeroNode newHero4 = new HeroNode(4, "公孙胜", "入云龙");
  21.     doublyLinkedList.update(newHero4);
  22.     doublyLinkedList.list();
  24.     HeroNode newHero5 = new HeroNode(5, "时迁", "偷儿");
  25.     doublyLinkedList.update(newHero5);
  27.     System.out.println("-------------------------双向链表的删除测试-------------------------");
  28.     doublyLinkedList.del(3);

// doublyLinkedList.del(4); doublyLinkedList.list();

  1.     doublyLinkedList.del(5);
  3.     System.out.println("-------------------------双向链表的有序添加测试-------------------------");
  4.     HeroNode hero1_1 = new HeroNode(1, "宋江", "及时雨");
  5.     HeroNode hero2_2 = new HeroNode(2, "卢俊义", "玉麒麟");
  6.     HeroNode hero3_3 = new HeroNode(3, "吴用", "智多星");
  7.     HeroNode hero4_4 = new HeroNode(4, "林冲", "豹子头");
  8.     DoublyLinkedList doublyLinkedList2 = new DoublyLinkedList();
  10.     doublyLinkedList2.addByOrder(hero3_3);
  11.     doublyLinkedList2.addByOrder(hero1_1);
  12.     doublyLinkedList2.addByOrder(hero2_2);
  13.     doublyLinkedList2.addByOrder(hero3_3);
  14.     doublyLinkedList2.addByOrder(hero4_4);
  16.     doublyLinkedList2.list();
  18. }

}

  2. <a name="4ac61592"></a>
  3. ### 单向循环链表
  5. 1. Joseph(约瑟夫、约瑟夫环)问题：约瑟夫问题，设编号为1,2,...,n的n个人围坐一圈，约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，他的下一位又开始由1开始报数，数到m的那个人又出列，依次类推，直到所有人都出列，由此产生一个出队编号的序列。使用单向循环链表完成，也可以使用环形队列实现，但前者更形象
  6. 1. 构建一个单向环形链表的思路
  7.    - 先创建第一个节点，让first指向该节点，并形成环状
  8.    - 当每创建一个新的节点，就把该节点加入到已有的环形中即可
  9. 3. 遍历环形链表
  10.    - 先让一个辅助变量curBoy，指向first节点
  11.    - 然后通过一个while循环遍历该环形链表即可，即curBoy.next = first
  12. 4. 根据用户输入，生成一个小孩出圈的顺序
  13.    - n：小孩人数；k：从第几个小孩开始报数；m：从1数到m
  14.    - 需要创建一个辅助变量helper，事先应该指向环形链表的最后的那个节点
  15.    - 小孩报数时，先让first和helper移动k-1次
  16.    - 当小孩报数时，让first和helper同时移动m-1次
  17.    - 这时就可以将first指向的小孩节点出圈，first = first.next; helper.next = first; 原来first指向的这个节点就没有任何引用了，就会被回收
  18. 5. 节点类Boy代码
  19. ```java
  20. package singlycircularlinkedlist;
  22. public class Boy {
  24.     private int no;
  25.     private Boy next;
  27.     public Boy() {
  28.     }
  30.     public Boy(int no) {
  31.         this.no = no;
  32.     }
  34.     public int getNo() {
  35.         return no;
  36.     }
  38.     public void setNo(int no) {
  39.         this.no = no;
  40.     }
  42.     public Boy getNext() {
  43.         return next;
  44.     }
  46.     public void setNext(Boy next) {
  47.         this.next = next;
  48.     }
  50.     @Override
  51.     public String toString() {
  52.         return "Boy{" +
  53.                 "no='" + no + '\'' +
  54.                 '}';
  55.     }
  56. }
  1. 链表类SinglyCircularLinkedList代码 ```java package singlycircularlinkedlist;

public class SinglyCircularLinkedList {

  1. private Boy first = null;//当前没有编号
  3. public void addBoy(int nums) {
  4.     //对nums做一个校验
  5.     if (nums < 1) {
  6.         System.out.println("nums数据有误...");
  7.         return;
  8.     }
  9.     Boy curBoy = null;//辅助指针帮助构建环形链表
  10.     for (int i = 1; i <=nums; i++) {
  11.         //根据编号创建小孩节点
  12.         Boy boy = new Boy(i);
  13.         //如果是第一个小孩
  14.         if (i == 1) {
  15.             first = boy;
  16.             first.setNext(first);//构成环
  17.             curBoy = first;
  18.         } else {
  19.             curBoy.setNext(boy);
  20.             boy.setNext(first);
  21.             curBoy = boy;
  22.         }
  23.     }
  24. }
  26. //遍历当前环形链表
  27. public void showBoy() {
  28.     //判断链表是否为空
  29.     if (first == null) {
  30.         System.out.println("没有任何小孩...");
  31.         return;
  32.     }
  33.     //创建辅助变量
  34.     Boy curBoy = first;
  35.     while (true) {
  36.         System.out.println("小孩的编号为" + curBoy.getNo());
  37.         if (curBoy.getNext() == first) {//判断是否遍历完毕
  38.             break;
  39.         }
  40.         curBoy = curBoy.getNext();
  41.     }
  42. }
  44. //根据用户输入，计算出小孩出圈的顺序
  46. /**
  47.  *
  48.  * @param startNo 表示从第几个小孩开始数
  49.  * @param countNum 表示数到数字几出圈
  50.  * @param nums 表示最初圈中的小孩数量
  51.  */
  52. public void countBoy(int startNo, int countNum, int nums) {
  53.     //先进行数据的校验
  54.     if (first == null || startNo < 1 || startNo >nums) {
  55.         System.out.println("参数输入有误，请输入有效数据...");
  56.         return;
  57.     }
  58.     //创建一个辅助变量
  59.     Boy helper = first;
  60.     //先让helper指向最后一个节点
  61.     while (true) {
  62.         if (helper.getNext() == first) {//判断是否到达最后一个节点
  63.             break;
  64.         }
  65.         helper = helper.getNext();
  66.     }
  67.     //小孩报数前，先让first和helper移动startNo - 1 次，也就是first移动到开始报数那个小孩节点，helper移动到此时first之前一个节点
  68.     for (int i = 0; i < startNo - 1; i++) {
  69.         first = first.getNext();
  70.         helper = helper.getNext();
  71.     }
  72.     //当小孩报数时，让first和helper指针同时移动countNum-1次，然后出圈
  73.     //这里是一个循环操作，知道圈中只有一个节点
  74.     while (true) {
  75.         if (helper == first) {//说明圈中只有一个节点
  76.             break;
  77.         }
  78.         //让first和helper指针同时移动countNum-1次，让后出圈
  79.         for (int i = 0; i < countNum - 1; i++) {
  80.             first = first.getNext();
  81.             helper = helper.getNext();
  82.         }
  83.         //这时first指向的节点就是需要出圈的小孩节点
  84.         System.out.println("小孩" + first.getNo() + "出圈");
  85.         first = first.getNext();
  86.         helper.setNext(first);
  87.     }
  88.     System.out.println("最后留在圈中的小孩编号为:" + first.getNo());
  89. }

}

  2. 7. 测试类Joseph代码
  3. ```java
  4. package singlycircularlinkedlist;
  6. public class Joseph {
  8.     public static void main(String[] args) {
  9.         //测试构建与遍历是否存在问题
  10.         SinglyCircularLinkedList singlyCircularLinkedList = new SinglyCircularLinkedList();
  11.         singlyCircularLinkedList.addBoy(5);//加入5个小孩节点
  12.         singlyCircularLinkedList.showBoy();
  14.         System.out.println("---------------------------------");
  16.         //测试小孩出圈是否存在问题
  17.         singlyCircularLinkedList.countBoy(1,2,5);
  18.     }
  20. }

3.栈（Stack）

介绍

  1. 栈是一个先进后出（FILO First in Last out）的有序列表
  2. 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表，允许插入和删除的一端，为变化的一端，称为栈顶(top)，另外一端为固定的一端，称为栈底(bottom)
  3. 根据栈的定义可知，最先放入栈中的元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除
  4. 栈的应用场景
    • 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中
    • 处理递归调用：和子程序的调用类似，只是除了存储下一个指令的地址外，也将参数、区域变量等数据存入堆栈中
    • 表达式的转换（中缀表达式转后缀表达式）与求值
    • 二叉树遍历
    • 图形的深度优先搜索法

数组模拟栈

  1. 思路分析
    • 定义一个top来表示栈顶，初始化为-1
    • 入栈(push)操作，当有数据加入到栈时，top++；stack[top] = data
    • 出栈(pop)操作，当数据要出栈时，int value = stack[top]; top—;return value;
  2. 数组栈类ArrayStack代码 ```java package arraystack;

//定义一个ArrayStark类 表示栈 public class ArrayStack {

  1. private int maxSize;//栈的大小
  2. private int[] stack;//数组，数组模拟栈，数据放在该数组中
  3. private int top = -1;//top表示栈顶，初始化为-1
  5. public ArrayStack() {
  6. }
  8. public ArrayStack(int maxSize) {
  9.     this.maxSize = maxSize;
  10.     stack = new int[this.maxSize];
  11. }
  13. //栈满
  14. public boolean isFull() {
  15.     return top == maxSize-1;
  16. }
  18. //栈空
  19. public boolean isEmpty() {
  20.     return top == -1;
  21. }
  23. //入栈
  24. public void push(int value) {
  25.     if (isFull()) {
  26.         System.out.println("栈满，入栈失败...");
  27.         return;
  28.     }
  29.     top++;
  30.     stack[top] = value;
  31. }
  33. //出栈
  34. public int pop() {
  35.     if (isEmpty()) {
  36.         throw new RuntimeException("栈空，出栈失败...");
  37.     }
  38.     int value = stack[top];
  39.     top--;
  40.     return value;
  41. }
  43. //遍历栈，遍历时，需要从栈顶开始显示
  44. public void list() {
  45.     if (isEmpty()) {
  46.         System.out.println("栈空，无数据...");
  47.     }
  48.     for (int i = top; i >= 0; i--) {
  49.         System.out.println("stack["+ i +"]=" + stack[i]);
  50.     }
  51. }

}

  2. 3. 测试类ArrayStackDemo代码
  3. ```java
  4. package arraystack;
  6. import java.util.Scanner;
  8. public class ArrayStackDemo {
  10.     public static void main(String[] args) {
  11.         //测试ArrayStack是否正确
  12.         //先创建一个ArrayStack，表示栈
  13.         ArrayStack stack = new ArrayStack(4);
  14.         String key = "";
  15.         boolean loop = true;//控制是否退出菜单
  16.         Scanner input = new Scanner(System.in);
  18.         while (loop) {
  19.             System.out.println("------------------");
  20.             System.out.println("show:显示栈");
  21.             System.out.println("push:添加数据到栈");
  22.             System.out.println("pop:从栈中取出数据");
  23.             System.out.println("exit:退出程序");
  24.             System.out.println("------------------");
  25.             System.out.println("请输入你要进行的操作：");
  26.             key = input.nextLine();
  27.             switch (key) {
  28.                 case "show":
  29.                     stack.list();
  30.                     break;
  31.                 case "push":
  32.                     System.out.println("请输入一个整数：");
  33.                     int value = input.nextInt();
  34.                     input.nextLine();
  35.                     stack.push(value);
  36.                     break;
  37.                 case "pop":
  38.                     try{
  39.                         int result = stack.pop();
  40.                         System.out.println("出栈的数据为：" + result);
  41.                     } catch (Exception e) {
  42.                         System.out.println(e.getMessage());
  43.                     }
  44.                     break;
  45.                 case "exit":
  46.                     input.close();
  47.                     loop = false;
  48.                     break;
  49.                 default:
  50.                     System.out.println("无效输入，重新输入...");
  51.                     break;
  52.             }
  53.         }
  54.         System.out.println("退出程序...");
  55.     }
  57. }

单链表模拟栈

  1. 思路分析
    • 用单链表来模拟栈第一个想到的是单链表的头插法，再结合单链表栈每次出栈都出头节点head的下一个节点，并将head的next指向head的next的next，实现先进后出
    • 判断栈空(isEmpty)：只要head.next为空，即head.next == null为true，则栈为空
    • 判断栈满(isFull)：这里我没有设置栈满，主要原因是因为单向链表无长度限制，如果要实现，则可以在SinglyLinkedListStack类中添加一个maxSize属性(通过构造器来设置)来控制，然后再设置一个size属性来获取当前栈的长度，默认为0，每进行一次入栈操作，size++，当然，每次入栈时都要判断size是否等于了maxSize，如果等于栈就已经满了，就入栈失败，然后出栈每次size都要size—
    • 入栈操作(push)：使用头插法，node.next = head.next；head.next = node；可以理解为先进入栈的节点，被挤向了后面
    • 出栈操作(pop)：每次出栈都出的是head节点的下一个节点，也就是删除head的下一个节点
    • 遍历栈(list)：就是单链表的遍历
  2. 节点类Node代码 ```java package singlylinkedliststack;

public class Node {

  1. private int data;
  2. private Node next;
  4. public Node() {
  5. }
  7. public Node(int data) {
  8.     this.data = data;
  9. }
  11. public int getData() {
  12.     return data;
  13. }
  15. public void setData(int data) {
  16.     this.data = data;
  17. }
  19. public Node getNext() {
  20.     return next;
  21. }
  23. public void setNext(Node next) {
  24.     this.next = next;
  25. }
  27. @Override
  28. public String toString() {
  29.     return "Node{" +
  30.             "data=" + data +
  31.             '}';
  32. }

}

  2. 3. 单链表栈类SinglyLinkedListStack代码
  3. ```java
  4. package singlylinkedliststack;
  6. public class SinglyLinkedListStack {
  8.     private Node head = new Node();
  10.     public SinglyLinkedListStack() {
  11.     }
  13.     public Node getHead() {
  14.         return head;
  15.     }
  17.     //判断栈是否为空
  18.     public boolean isEmpty() {
  19.         return head.getNext() == null;
  20.     }
  22.     //入栈
  23.     public void push(Node node) {
  24.         node.setNext(head.getNext());
  25.         head.setNext(node);
  26.     }
  28.     //出栈
  29.     public Node pop() {
  30.         //栈空就抛出错误
  31.         if (isEmpty()) {
  32.             throw new RuntimeException("栈空，出栈失败...");
  33.         }
  34.         //栈不为空就出栈
  35.         Node result = head.getNext();
  36.         head.setNext(head.getNext().getNext());
  37.         return result;
  38.     }
  40.     public void list() {
  41.         //栈空就无数据可打印
  42.         if (isEmpty()) {
  43.             System.out.println("栈空，无数据...");
  44.             return;
  45.         }
  46.         //栈不为空就打印信息
  47.         //辅助变量，方便遍历整个栈
  48.         Node temp = head.getNext();
  49.         while (true) {
  50.             if (temp == null) {
  51.                 break;
  52.             }
  53.             System.out.println(temp);
  54.             temp = temp.getNext();
  55.         }
  56.     }
  58. }
  1. 测试类SinglyLinkedListStackDemo代码 ```java package singlylinkedliststack;

public class SinglyLinkedListStackDemo {

  1. public static void main(String[] args) {
  3.     //新建一个栈对象
  4.     SinglyLinkedListStack singlyLinkedListStack = new SinglyLinkedListStack();
  6.     Node node1 = new Node(1);
  7.     Node node2 = new Node(2);
  8.     Node node3 = new Node(3);
  9.     Node node4 = new Node(4);
  10.     Node node5 = new Node(5);
  12.     System.out.println("------------栈空测试遍历------------");
  13.     singlyLinkedListStack.list();
  14.     System.out.println("------------node1入栈------------");
  15.     singlyLinkedListStack.push(node1);
  16.     singlyLinkedListStack.list();
  17.     System.out.println("------------node2入栈------------");
  18.     singlyLinkedListStack.push(node2);
  19.     singlyLinkedListStack.list();
  20.     System.out.println("------------node3、node4、node5依次入栈------------");
  21.     singlyLinkedListStack.push(node3);
  22.     singlyLinkedListStack.push(node4);
  23.     singlyLinkedListStack.push(node5);
  24.     singlyLinkedListStack.list();
  25.     System.out.println("------------第一次出栈------------");
  26.     try {
  27.         System.out.println("出栈的数据为：" + singlyLinkedListStack.pop().toString());
  28.     } catch (Exception e) {
  29.         System.out.println(e.getMessage());
  30.     }
  31.     singlyLinkedListStack.list();
  32.     System.out.println("------------第二次出栈------------");
  33.     try {
  34.         System.out.println("出栈的数据为：" + singlyLinkedListStack.pop().toString());
  35.     } catch (Exception e) {
  36.         System.out.println(e.getMessage());
  37.     }
  38.     singlyLinkedListStack.list();
  39.     System.out.println("------------将栈中数据出栈完------------");
  40.     try {
  41.         System.out.println("出栈的数据为：" + singlyLinkedListStack.pop().toString());
  42.         System.out.println("出栈的数据为：" + singlyLinkedListStack.pop().toString());
  43.         System.out.println("出栈的数据为：" + singlyLinkedListStack.pop().toString());
  44.         System.out.println("出栈的数据为：" + singlyLinkedListStack.pop().toString());
  45.     } catch (Exception e) {
  46.         System.out.println(e.getMessage());
  47.     }
  48.     singlyLinkedListStack.list();
  50. }

}

  2. <a name="8da66b64"></a>
  3. ### 栈实现综合计算器
  5. 1. 要求：使用栈完成计算一个表达式的结果eg：7*2*2-5+1-5+3-4
  6. 1. 需要使用用两个栈，分别为数栈（存储数）和符号栈（存储运算符）
  7. 1. 思路
  8.    - 通过一个index值（索引），来遍历我们的表达式
  9.    - 如果扫描发现是一个数字，就直接入数栈
  10.    - 如果扫描发现是符号，分以下情况
  11.       - 如果发现当前的符号栈为空，就直接入栈
  12.       - 如果符号栈有操作符，就进行比较，**如果当前的操作符的优先级小于或者等于栈中的操作符**，这时就需要从数栈中pop出两个数，然后再从符号栈中pop出一个运算符，进行运算，将得到的结果再入数栈，**这里注意！！**，不能只比一次，要清楚有可能栈中有时还有运算符，可能是优先级相等的，需要再次出栈，而在判断优先级大小时需要再次查看运算符栈是否为空，然后还需要将此时的操作符入符号栈；**如果当前的操作符的有限级大于栈中的操作符**，就直接入符号栈
  13.    - 当表达式扫描完毕，就顺序地从数栈和符号栈中pop出相应的数和符号，并运行
  14.    - 最后在数栈中只有一个数字，就是表达式的结果
  15.    - 这里要注意的是除法中被除数不能为0，以及这是整数型的计算器，“/”可能使得计算结果不精确
  16. 4. 栈类ArrayStac代码
  17. ```java
  18. package calculator;
  20. //定义一个ArrayStark类 表示栈
  21. public class ArrayStack {
  23.     private int maxSize;//栈的大小
  24.     private int[] stack;//数组，数组模拟栈，数据放在该数组中
  25.     private int top = -1;//top表示栈顶，初始化为-1
  27.     public ArrayStack() {
  28.     }
  30.     public ArrayStack(int maxSize) {
  31.         this.maxSize = maxSize;
  32.         stack = new int[this.maxSize];
  33.     }
  35.     //栈满
  36.     public boolean isFull() {
  37.         return top == maxSize-1;
  38.     }
  40.     //栈空
  41.     public boolean isEmpty() {
  42.         return top == -1;
  43.     }
  45.     //入栈
  46.     public void push(int value) {
  47.         if (isFull()) {
  48.             System.out.println("栈满，入栈失败...");
  49.             return;
  50.         }
  51.         top++;
  52.         stack[top] = value;
  53.     }
  55.     //出栈
  56.     public int pop() {
  57.         if (isEmpty()) {
  58.             throw new RuntimeException("栈空，出栈失败...");
  59.         }
  60.         int value = stack[top];
  61.         top--;
  62.         return value;
  63.     }
  65.     //查看栈顶元素，并不是真正出栈
  66.     public int peek() {
  67.         return stack[top];
  68.     }
  70.     //遍历栈，遍历时，需要从栈顶开始显示
  71.     public void list() {
  72.         if (isEmpty()) {
  73.             System.out.println("栈空，无数据...");
  74.         }
  75.         for (int i = top; i >= 0; i--) {
  76.             System.out.println("stack["+ i +"]=" + stack[i]);
  77.         }
  78.     }
  80.     //返回运算符的优先级，优先级是程序员来确定，优先级使用数字表示
  81.     //数字优先级使用数字来表示
  82.     public int priority(int operator) {
  83.         if (operator == '*' || operator == '/') {
  84.             return 1;
  85.         } else if (operator == '+' || operator == '-') {
  86.             return 0;
  87.         } else {
  88.             return -1;//假定目前表达式只有+，-，*，/
  89.         }
  90.     }
  92.     //判断是否为一个运算符
  93.     public boolean isOperator(char val) {
  94.         return val == '+' || val == '-' || val == '*' || val == '/';
  95.     }
  97.     //计算方法
  99.     /**
  100.      *
  101.      * @param num1 先弹出的那个数
  102.      * @param num2 后弹出的那个数
  103.      * @param operator 弹出的运算符
  104.      * @return 返回的运算结果
  105.      */
  106.     public int cal(int num1, int num2, int operator) {
  107.         int result = 0;
  108.         switch (operator) {
  109.             case '+':
  110.                 result = num2 + num1;
  111.                 break;
  112.             case '-':
  113.                 result = num2 - num1;
  114.                 break;
  115.             case '*':
  116.                 result = num2 * num1;
  117.                 break;
  118.             case '/':
  119.                 if (num1 == 0) {
  120.                     System.out.println("表达式有误，会使被除数为0...");
  121.                     System.out.println("如下: " + num2 +  "/" + num1);
  122.                     System.exit(0);
  123.                 }
  124.                 result = num2 / num1;
  125.                 break;
  126.         }
  127.         return result;
  128.     }
  129. }
  1. 计算器类Calculator代码 ```java package calculator;

public class Calculator {

  1. public static void main(String[] args) {
  2.     //表达式
  3.     String expression = "5-3-2*3+1";
  4.     //创建数栈
  5.     ArrayStack numberStack = new ArrayStack(10);
  6.     //创建符号栈
  7.     ArrayStack operatorStack = new ArrayStack(10);
  8.     //用于扫描
  9.     int index = 0;
  10.     int number1 = 0;
  11.     int number2 = 0;
  12.     int operator = 0;
  13.     int result = 0;
  14.     char ch = ' ';//将每次得到的char保存到ch变量中
  15.     String keepNumber = "";//用于拼接多位数
  16.     //开始while循环扫描
  17.     while(true) {
  18.         //一次得到表达式的每一个字符
  19.         ch = expression.substring(index,index+1).charAt(0);
  20.         //判断是数字还是运算符
  21.         if (operatorStack.isOperator(ch)) {//如果是运算符
  22.             //判断当前符号栈是否为空
  23.             if (!operatorStack.isEmpty()) {
  24.                 //如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中的操作符，
  25.                 //这时就需要从数栈中pop出两个数，然后再从符号栈中pop出一个运算符，进行运算，将得到的结果再入数栈，然后循环判定是否此时运算符号栈的栈顶优先级，直到为空或者是栈顶优先级小于此时的ch，再将此时的操作符入符号栈
  26.                 while (true) {
  27.                     if (operatorStack.isEmpty()) {
  28.                         operatorStack.push(ch);
  29.                         break;
  30.                     }
  31.                     if (operatorStack.priority(ch) <= operatorStack.priority(operatorStack.peek())) {
  32.                         //弹出运算需要用到的数据和运算符
  33.                         number1 = numberStack.pop();
  34.                         number2 = numberStack.pop();
  35.                         operator = operatorStack.pop();
  36.                         //得到运算结果
  37.                         result = numberStack.cal(number1, number2, operator);
  38.                         //把得到的结果入栈到数据栈中
  39.                         numberStack.push(result);
  40.                         //当前的操作符入符号栈
  41.                     } else {
  42.                         operatorStack.push(ch);
  43.                         break;
  44.                     }
  45.                 }
  46.             } else {
  47.                 //如果为空，直接入栈
  48.                 operatorStack.push(ch);
  49.             }
  50.         } else { //如果是数
  51.             //numberStack.push(Integer.parseInt(ch + ""));
  52.             //1. 处理多位数时，不能发现一个数就直接入栈，可能是多位数，也有可能是一位的数
  53.             //2. 在入栈时，需要问表达式的index后再看一位，如果是数就进行扫描，如果数运算符，就直接入栈
  54.             //3. 需要定义一个字符串变量，用于拼接
  56.             //处理多位数
  57.             keepNumber += ch;
  59.             //如果ch是表达式的最后一位了，就直接入栈
  60.             if (index == expression.length() - 1) {
  61.                 numberStack.push(Integer.parseInt(keepNumber));
  62.                 //需要重置keepNumber
  63.                 keepNumber = "";
  64.             } else {
  65.                 //判断下一个字符是不是数字，如果是数字，进行扫描，如不是，将数字入数据栈
  66.                 //注意index
  67.                 if (operatorStack.isOperator(expression.substring(index + 1, index + 2).charAt(0))) {
  68.                     numberStack.push(Integer.parseInt(keepNumber));
  69.                     //需要重置keepNumber
  70.                     keepNumber = "";
  71.                 }
  72.             }
  73.         }
  74.         //index+1，判断是否扫描到表达式的最末端
  75.         index++;
  76.         if (index == expression.length()) {
  77.             break;
  78.         }
  79.     }
  80.     while(true) {
  81.         //如果符号栈为空，则计算到了最后的结果，数栈中只有一个数字
  82.         if (operatorStack.isEmpty()) {
  83.             break;
  84.         } else {
  85.             //弹出运算需要用到的数据和运算符
  86.             number1 = numberStack.pop();
  87.             number2 = numberStack.pop();
  88.             operator = operatorStack.pop();
  89.             //得到运算结果
  90.             result = numberStack.cal(number1, number2, operator);
  91.             //把得到的结果入栈到数据栈中
  92.             numberStack.push(result);
  93.         }
  94.     }
  95.     //显示结果
  96.     System.out.println("表达式：" + expression + " = " + numberStack.pop());
  97. }

}

  2. 6. <br />
  4. <a name="7229bf53"></a>
  5. # 非线性结构
  7. 常见的有：二维数组、多维数组、广义表、树结构和图结构
  9. 非线性结构常见的有：**二维数组**、**多维数组**、**广义表**、**树结构**和**图结构**
  11. <a name="ebbdd8cc"></a>
  12. ## 1. 稀疏数组(sparse array)
  14. <a name="61a3ec66-3"></a>
  15. ### 介绍
  17. 当一个数组中大部分元素为0，或者为同一个值的时候，可以使用稀疏数组来保存。（我的理解就是记关键的信息，这样可以节约数据的占用空间）
  19. 稀疏数组的处理方法是：
  21. 1. 记录数组一共有几行几列，有多少个不同的值；
  22. 1. 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小数组的规模。
  24. 例子：一个多行多列的二维数组，第一行记录的是原二维数组的行数、列数和值的个数，除去第一行外，转为稀疏数组将会是第一列为行号，第二列为列号，第三列为前面行号和列号在原二维数组所对应的值。
  26. <a name="5b0520a9"></a>
  27. ### 应用
  29. 五子棋对局保存和加载：
  31. 1. 二维数组转稀疏数组的思路
  32.    - 遍历原始二维数组，得到有效数据的个数sum
  33.    - 根据sum创建稀疏数组，int[][] sparseArray = new int[sum+1][3]
  34.    - 将原始二维数组的数据存入到稀疏数组sparseArray中
  35. 2. 稀疏数组转原始的二维数组的思路
  36.    - 先读取系数数组的第一行，根据第一行的数据创建原始二维数组，int[][] originalArray = new int[sparseArray[0][0]][sparseArray[0][1]]
  37.    - 读取稀疏数组后几行的数据并赋给原始数组
  38.    - 最后再将空白的值赋上自己默认的值，一般为0
  40. ```java
  41. public class SparseArray {
  43.     public static void main(String[] args) {
  45.         //稀疏数组代码实现，五子棋应用
  47.         //创建一个原始的二维数组
  48.         // 0:无子 1:黑子 2:蓝子
  49.         int[][] originalArray = new int[11][11];
  51.         originalArray[1][2] = 1;
  52.         originalArray[2][3] = 2;
  53.         originalArray[5][6] = 2;
  55.         //输出原始二维数组
  56.         System.out.println("----------原始二维数组----------");
  57.         for (int[] row : originalArray) {
  58.             for (int data : row) {
  59.                 System.out.printf("%d ", data);
  60.             }
  61.             System.out.println();
  62.         }
  64.         //遍历原始二维数组，得到非0值得个数
  65.         System.out.println("----------得到原始数组里不为0的数的个数----------");
  66.         int sum = 0;
  67.         for (int[] row : originalArray) {
  68.             for (int data : row) {
  69.                 if (data != 0) {
  70.                     sum++;
  71.                 }
  72.             }
  73.         }
  74.         System.out.println(sum);
  76.         //创建对应的稀疏数组
  77.         int[][] sparseArray = new int[sum+1][3];
  79.         //给系数数组赋值
  80.         sparseArray[0][0] = originalArray.length;
  81.         sparseArray[0][1] = originalArray[0].length;
  82.         sparseArray[0][2] = sum;
  84.         //再次遍历原始二维数组，将非零的值存放在稀疏数组中
  85.         int count = 0;//用来记录到了第几个非零值
  86.         for (int i = 0; i < originalArray.length; i++) {
  87.             for (int j = 0; j < originalArray[i].length; j++) {
  88.                 if (originalArray[i][j] != 0) {
  89.                     count++;
  90.                     sparseArray[count][0] = i;
  91.                     sparseArray[count][1] = j;
  92.                     sparseArray[count][2] = originalArray[i][j];
  93.                 }
  94.             }
  95.         }
  97.         //输出生成的稀疏数组
  98.         System.out.println("----------原始二维数组所对应的稀疏数组----------");
  99.         for (int[] row : sparseArray) {
  100.             for (int data : row) {
  101.                 System.out.printf("%d\t", data);
  102.             }
  103.             System.out.println();
  104.         }
  106.         //将稀疏数组恢复为原始数组
  107.         int[][] originalArray2 = new int[sparseArray[0][0]][sparseArray[0][1]];
  109.         //遍历稀疏数组为恢复的原始二维数组赋值
  110.         for (int i = 1; i < sparseArray.length; i++) {
  111.             originalArray2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
  112.         }
  114.         //恢复后的原始二维数组
  115.         System.out.println("----------恢复后的原始二维数组----------");
  116.         for (int[] row : originalArray2) {
  117.             for (int data : row) {
  118.                 System.out.printf("%d ", data);
  119.             }
  120.             System.out.println();
  121.         }
  123.     }
  125. }