基本数据结构 队列,链表,栈

基本数据结构 队列,链表,栈

数据结构和算法

介绍

数据结构和算法的关系

  • 数据(data)结构(structure)是一门研究组织数据的方法的学课
  • 生活中遇到的问题用程序去解决
  • 程序=数据结构+算法
  • 数据结构是算法的基础,换言之,想要学好算法,需要吧数据结构学到位

线行结构

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

非线行结构

非线性结构包括:二位数组,多维数组,广义表,树结构,图结构

线性数据结构

稀疏sparsearray数组

实际需求提出:

编写五子棋程序,有存盘溢出和续上盘的功能

用二维数组来记录棋子。

问题: 因为二维数组中很多值都是0,因此记录了很多无用的数据

基本介绍

当一个数组中大部分元素为0,或者为同一个值的数组时,可以是用稀疏数组来保存该数组
稀疏数组的处理方法是:

  • 记录数组一共有几行几列,有多少个不同的值
  • 打具有不同值的元素的行列及值记录在一个小规模的数组中。从而缩小程序的规模

数据结构01_稀疏数组.jpg

应用实例

  • 使用稀疏数组,来保存类似前面的二维数组
  • 把稀疏数组存盘,并且可以重新恢复原来的二维数组
  • 整体思路分析

稀疏数组 row col val
第一行的row记录原始数组的行col记录宽val记录数据的个数
剩下的行记录数据 row记录数据的行 col记录宽 val存储数据的值

二维数组转稀疏数组的思路
遍历,的到有效数据的个数sum
根据得到的sum可以创建稀疏数组 sparseArr int[sum+1][3]
将二维数组的有效数据存入稀疏数组即可

稀疏数组转二维数组的思路
先读取稀疏数组的第一行,根据第一行的数据创建原始的二维数组
读取稀疏数组后几行的数据并且付给原始的二维数组即可

  • 代码实现

代码实现

public class SparseArray {
    public static void main(String[] args) {
        // 先创建一个原始的二维数组 11*11
        // 0表示没有棋子,1表示黑子,2表示蓝子

        int chessArr1[][] = new int[11][11];
        chessArr1[1][2] = 1;
        chessArr1[2][3] = 2;
        // 输出原始的二维数组
        System.out.println("原始的二维数组");
        for (int[] row : chessArr1) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
        // 二维数组转换稀疏数组
        // 第一步: 先遍历 得到非零数据的个数
        int sum = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr1[i][j] != 0) {
                    sum++;
                }
            }
        }
        // 创建对应的稀疏数组
        int sparseArr[][] = new int[sum + 1][3];
        // 给稀疏数组赋值
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;

        // 遍历二维数组将非零值存放到稀疏数组中
        int count = 0; // 用于记录是第几个非零数据
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (chessArr1[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr1[i][j];
                }
            }
        }
        // 输出稀疏数组的形式
        System.out.println("得到的稀疏数组为");
        for (int i = 0; i < sparseArr.length; i++) {
            System.out.printf("%d\t%d\t%d\t\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
        }
        // 将稀疏数组恢复为二维数组

        // 1 读取稀疏数组第一行
        int chessArr2[][] = new int[sparseArr[0][1]][sparseArr[0][1]];

        for (int i = 1; i < sparseArr.length; i++) {
            chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        // 复原后的数组
        System.out.println("复原后的数组");
        for (int[] row : chessArr2) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }

    }
}

结果

数据结构02_稀疏数组结果.jpg

课后作业

将转化好的稀疏数组写入磁盘中
再从磁盘中读取转化为正常的数组

作业的实现
使用se知识中的字符读取/写入流,缓存字符流和对象字符流
很容易实现作业说的效果

// 使用io流将稀疏数组存储到磁盘中

// 创建字符输出流
FileOutputStream fos = new FileOutputStream("D:/map.data");
// 创建缓冲流
BufferedOutputStream bos = new BufferedOutputStream(fos);
// 创建对象包装流
ObjectOutputStream oos = new ObjectOutputStream(bos);
// 写入对象
oos.writeObject(sparseArr);
// 刷新缓存区域
oos.flush();
// 关闭流
oos.close();

// 使用io流读取在磁盘中的map.data

// 创建字符输入流
FileInputStream fis = new FileInputStream("D:/map.data");
// 缓冲流
BufferedInputStream bis = new BufferedInputStream(fis);
// 对象流
ObjectInputStream ois = new ObjectInputStream(bis);
// 读取
sparseArr = (int[][]) ois.readObject();
// 关闭流
ois.close();

队列

队列介绍

队列是一个有序列表,可以用数组或是链表实现
遵循先进后出的原则!
数据结构03_队列.jpg

数组的模拟队列

队列本身是有序列表,使用数组结构来存储队列的数据
因为队列的输入和输出是分别从前后端来处理的,因此需要两个变量front和rear分别记录队列的前端和后端的下标,front会随着数据输出而改变,而rear则是随着数据的输入改变而改变

我们将数据存入队列称为"addQuerue",addQuerue的处理需要有两个步骤:思路分析

  • 将尾指针向后移:rear+1,当front==rear 也就是空队的时候
  • 若尾指针 rear小于队列的最大下标 maxSize-1,则将数据存入rear所指的数据元素,否则无法存入数据。rear==maxSize-1 满队

代码实现队列[数组]

实现代码

class ArrayQueue {
    private int maxSize; // 数组的最大容量
    private int front; // 队列头
    private int rear; // 队列尾
    private int[] arr; // 该数组用于存放数据,模拟队列
    // 创建队列的构造器
    public ArrayQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1; // 指向队列头部,分析出front是指向队列头的前一个位置
        rear = -1;// 指向队列尾的具体位置
    }
    // 判断队列是否满
    public boolean isFull() {
        return rear == maxSize - 1;
    }
    // 判断队列是否为空
    public boolean isEmpty() {
        return rear == front;
    }
    // 添加数据到队列
    public void addQueue(int n) {
        // 判断队列是否满
        if (isFull()) {
            System.out.println("满队");
            return;
        }
        rear ++; // rear后移
        arr[rear] = n;
    }
    // 获取队列的数据, 出队列
    public int getQueue() {
        // 判断队列是否空
        if (isEmpty()) {
            // 通过抛出异常
            throw new RuntimeException("队列为空");
        }
        front++; // front后移
        return arr[front];
    }
    // 显示队列的所有数据
    public void showQueue() {
        // 遍历
        if (isEmpty()) {
            System.out.println("空队");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d%n", i, arr[i]);
        }
    }
    // 显示队列的头数据是多少,不是取出数据
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("空对");
        }
        return arr[front + 1];
    }
}

测试程序

public class ArrayQueueDemo {
    public static void main(String[] args) {
        // 创建一个队列
        ArrayQueue arrayQueue = new ArrayQueue(3);
        char key = ' '; //接收用户的输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        // 输出一个菜单
        while (loop) {
            System.out.println("s(show):显示队列");
            System.out.println("e(exit):退出程序");
            System.out.println("a(add):添加数据到队列");
            System.out.println("g(get):从队列中取数据");
            System.out.println("h(head):查看队列头的数据");
            key = scanner.next().charAt(0); // 接收一个字符
            switch (key) {
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'a':
                    System.out.println("输入一个数字");
                    int value = scanner.nextInt();
                    arrayQueue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int i = arrayQueue.getQueue();
                        System.out.println(i);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int i = arrayQueue.headQueue();
                        System.out.println(i);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();;
                    loop = false;
                    System.out.println("程序退出");
                    break;
                default:
                    System.out.println("输入正确的指令");
                    break;
            }
        }
    }
}

问题

上述代码看似很严谨,实际上纯在着巨大的漏洞
在出队之后,之前的数组空间就没办法继续使用了
导致,本来就算有3个空间,出队一个之后,有两个元素的时候继续添加也会显示满队

解决方案:使用环形队列

数组模拟环形队列思路分析

概念变更
maxSize:还是内置数组的最大长度,但是存储的数据最大数量位maxSize-1
rear:代表队列尾元素的下一个位置,这个位置是预留出来的,是变动的不存储任何数据
front:代表队列头元素

重要的膜表达式

因为实现的队列要是环形队列,所以说在数组的最后一个元素的之后的元素应该是第一个元素,在第一个元素前的位置是最有一个元素

为了实现上述逻辑有如下思路
思路一:使用逻辑判断,很复杂繁琐,不采用
思路二:使用膜除表达式算法实现

下一个位置:(当前元素位置+1)%一共有多少位置
上一个位置:(当前元素位置-1)%一共有多少位置

列出环形队列的需要的表达式

  1. 判满:

这个很简单,自需要判断尾部的下一个位置是不是开头的位置:(rear+1)%maxSize == front

  1. 判空

和之前一样的:rear == front

  1. 当前队列有效数据的个数

(rear + maxSize - front) % maxSize:
这个表达式有两种情况
第一种:rear>front 代表f在r的前面,存储的位置没有在从头开始,这样maxSize不会起作用,相当于直接r-f的结果取模maxSize,还是原来的结果,因为r-f不可能比maxSize大
数据结构03_环状队列.jpg
由图片实例看出,2-0=2,正好队列中有两个元素
第二种:front>rear 代表f在r的后面,存储的位置由后面开始到了开头又到了rear前的位置。里面的maxSize起作用也就是用maxSize减去了f-r的值,而f-r是没存储元素的个数,减去后正好是存储的元素的个数。
数据结构04_环状队列.jpg
首先图示这个队列中存储了3个元素rear前面的为尾元素,front为首元素
根据表达式 1-2+4 = 3 没问题!

环形队列代码实现

class CircleArray {
    private int maxSize; // 数组的最大容量-1
    private int front; // 队列头
    private int rear; // 队列尾的下一个位置
    private int[] arr; // 该数组用于存放数据,模拟队列

    public CircleArray(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
    }
    // 判断队列是否满
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }
    // 判断队列是否为空
    public boolean isEmpty() {
        return rear == front;
    }
    // 添加数据到队列
    public void addQueue(int n) {
        // 判断队列是否满
        if (isFull()) {
            System.out.println("满队");
            return;
        }
        // 直接将数据加入
        arr[rear] = n;
        // rear后移
        rear = (rear + 1) % maxSize;
    }
    // 获取队列的数据, 出队列
    public int getQueue() {
        // 判断队列是否空
        if (isEmpty()) {
            // 通过抛出异常
            throw new RuntimeException("队列为空");
        }
        // 这里需要分析front是指向队列的第一个元素
        // 1. 先把front的对应的值保存到临时的变量
        // 2. 将front后移,考虑取模
        // 3. 将临时保存的变量返回
        int val = arr[front];
        front = (front + 1) % maxSize;
        return val;
    }

    // 显示队列的所有数据
    public void showQueue() {
        // 遍历
        if (isEmpty()) {
            System.out.println("空队");
            return;
        }
        // 思路:从front开始遍历,遍历多少个元素
        for (int i = front; i < front + size(); i++) {
            System.out.printf("arr[%d]=%d%n", i % maxSize, arr[i % maxSize]);
        }
    }
    // 求出当前队列有效数据的个数
    public int size() {
        return (rear + maxSize - front) % maxSize;
    }
    // 显示队列的头数据是多少,不是取出数据
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("空对");
        }
        return arr[front];
    }
}

测试代码和上面的一样,改个实例即可!

链表

链表介绍(Linked List)

链表是有序列表,但是他在内存中存储方式是链式的

  1. 链表是以节点的方式存储的
  2. 每个节点包含data域,next域:指向下一个节点
  3. 链表的各个节点在内存中不一定是连续存放的
  4. 链表分,带头节点的链表,和没有头节点的链表,根据需求确定

应用案例

使用带head头的单向链表实现-水浒英雄排行帮的管理
完成对英雄人物的增删改查的操作
添加

  1. 直接添加到尾部
  2. 考虑排名插入

实现思路分析

示意图:
数据结构05_链表.jpg

添加:

  1. 先创建一个head头节点,作用是表示单链表的头
  2. 后面我们每添加一个节点,就直接加入到链表的最后

代码实现

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
        // 创建一个链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        // 加入
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero4);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        // 显示列表
        singleLinkedList.list();
    }
}

// 定义一个SingLinkedList
class SingleLinkedList {
    // 先初始化一个头节点,头节点不要动,不存放具体的数据
    private HeroNode head = new HeroNode(0, "", "");

    // 添加到节点的单向列表
    // 不考虑编号的顺序时,找到当前的链表的最后节点,将最后节点的next指向新节点
    public void add(HeroNode heroNode) {
        // 因为head节点不能动,因此我们需要一个辅助变量temp
        HeroNode temp = head;
        // 遍历链表,找到最后
        while (temp.next != null) {
            temp = temp.next;
        }
        // while 循环结束时 temp就指向了链表的最后
        temp.next = heroNode;
    }
    

    // 显示链表
    public void list() {
        // 判断链表是否为空
        if (head.next == null) {
            //链表为空
            return;
        }
        HeroNode temp = head;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

// 定义一个HeroNode,每个HeroNode对象就是一个节点

class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;

    public HeroNode(int hNo, String hName, String hNickname) {
        this.name = hName;
        this.no = hNo;
        this.nickname = hNickname;
    }

    // 显示方便重写toString方法
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

以上实现的添加方法是不能自动排列顺序的
现在需求是:根据节点的编号自动排序,如果有这个编号了,就报错

整强添加方法

public void addByOrder(HeroNode heroNode) {
    // 因为头节点不能动,因此还是需要一个辅助变量来帮助找到添加的位置
    // 因为是个单链表,因此我们找的temp是位于添加位置的前一个节点,否则就插入不了了
    HeroNode temp = head;
    boolean flag = false; // 标志添加的编号是否纯在默认是false
    while (true) {
        if (temp.next == null) {
            break;
        }
        if (temp.next.no > heroNode.no) {
            break;
        } else if (temp.next.no == heroNode.no) { // 编号纯在
            flag = true; // 说明编号存在
            break;
        }
        temp = temp.next; // 后移
    }
    // 判断flag的值
    if (flag) {
        // 编号存在
        System.out.println("准备插入的英雄编号已经存在" + heroNode.no);
    } else {
        // 插入到链表中
        heroNode.next = temp.next;
        temp.next = heroNode;
    }
}

修改方法实现

// 修改节点的信息,根据编号来修改,即no编号不能改
// 根据newHeroNode的no修改
public void update(HeroNode newHeroNode) {
    // 判断链表是否为空
    if (head.next == null) {
        System.out.println("链表为空");
        return;
    }
    // 找到要修改的节点
    HeroNode temp = head.next;
    boolean flag = false; // 是否找到
    while (true) {
        if (temp == null) {
            break; // 到链表的最后了
        }
        if (temp.no == newHeroNode.no) {
            flag = true;
            break;
        }
        temp = temp.next;
    }
    // 根据flag判断是否找到
    if (flag) {
        temp.name = newHeroNode.name;
        temp.nickname = newHeroNode.nickname;
    } else {
        System.out.printf("没有找到编号位%d节点", newHeroNode.no);
    }
}

删除节点
思路很简单,直接看代码就完事了

// 删除节点
public void del (int n) {
    // 判断链表是否为空
    if (head.next == null) {
        System.out.println("链表为空");
        return;
    }
    HeroNode temp = head.next;
    boolean flag = false; // 是否找到
    while (true) {
        if (temp == null) {
            break; // 到链表的最后了
        }
        if (temp.next.no == n) {
            flag = true;
            break;
        }
        temp = temp.next;
    }
    if (flag) {
        temp.next = temp.next.next;
    } else {
        System.out.println("待删除节点不纯在");
    }
}

面试题

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

/**
 * @param head 链表的头节点
 * @return 链表的有效节点个数
 */
public static int getLength(HeroNode head) {
    if (head.next == null) { // 空链表
        return 0;
    }
    int length = 0;
    HeroNode cur = head.next;
    while (cur != null) {
        length++;
        cur = cur.next;
    }
    return length;
}

查找单链表中的倒数第k个结点(新浪面试题)

思路

  1. 编写一个方法接收head节点,同时接收一个index
  2. index表示倒数第index个节点
  3. 先把链表从头到尾遍历,把链表先从头到尾进行遍历,得到链表的总长度getLength
  4. 得到size后,我们从链表的第一个开始遍历(size-index)个,就可以得到
  5. 找到了就返回该节点,找不到返回null
    总结就是:判空 求长 校验 遍历 返回

代码

public static HeroNode findLastIndexNode(HeroNode head, int index) {
    // 判断如果链表为空 返回null
    if (head.next == null) {
        return null;
    }
    // 第一次遍历得到链表的长度(节点个数)
    int size = getLength(head);
    // 第二次遍历 size - index 位置就是倒数第k个节点
    // 先做一个index的校验
    if (index <= 0 || index > size) {
        return null;
    }
    // 定义一个辅助变量
    HeroNode cur = head.next;
    for (int i = 0; i < size - index; i++) {
        cur = cur.next;
    }
    return cur;
}

单链表的反转(腾讯面试题)

思路
有点难度哦!

  1. 先去定义一个节点,reverseHead = new HeroNode();
  2. 从头到尾遍历原来的链表,每遍历一个节点,就将其取出,并放在新链表的最前端
  3. 原来的链表的head.next=reverseHead.next

这种方法在算法书上叫做头插法,看着思路很是容易实现起来确有几个坑

这里我自己看教程之前实现了一遍,看完教程后发现和老师的有点差异,这里都贴出来

自己实现的

public static void reversal(HeroNode head) {
    // 判空
    if (head.next == null) {
        return;
    }
    HeroNode reverseHead = new HeroNode(0, "", "");
    // 遍历
    while (true) {
        HeroNode temp = head.next;
        if (temp == null) {
            break;
        }
        // 头插
        head.next = temp.next;
        temp.next = reverseHead.next;
        reverseHead.next = temp;
    }
    head.next = reverseHead.next;
}

老师的

public static void reverseList(HeroNode head) {
    // 判空
    if (head.next == null || head.next.next == null) {
        return;
    }
    // temp
    HeroNode cur = head.next;
    HeroNode next = null;// 指向当前下一个节点
    HeroNode reverseHead = new HeroNode(0, "", "");
    // 遍历原来的链表
    while (cur != null) {
        next = cur.next; // 保存当前节点的下一个节点
        cur.next = reverseHead.next;
        reverseHead.next = cur; // 将cur的下一个节点指向新链表的最前端
        cur = next;
    }
    head.next = reverseHead.next;
}

其实本质上都是使用的上述老师讲的思想,我的实现方式是用cur的时候直接将cur的下一个元素给head接上,老师的是再定义一个中间变量next来存储cur的下一个变量,就产生了细微的变化。

由上边判空的地方我漏掉了head.next.next的情况还是证明老师思考的更多
但是能自己实现一次,真的很有成就感!

从尾到头打印单链表(百度:要求方式1反向遍历,方式2Stack栈)

看到题目我第一眼想的就是递归,可能是我太菜了吧,但是有要求使用反向遍历或者是栈
反向遍历,其实就是反转后打印呗,之前写了反转了,而且这种方式破坏了原本链表的结构不推荐
使用栈
思路很简单,看代码就完事了

public static void reversePrint(HeroNode head) {
    // 判空
    if (head.next == null) {
        return;
    }
    // 创建一个栈,将节点压入栈中
    Stack<HeroNode> stack = new Stack<>();
    HeroNode cur = head.next;
    // 将链表的所有节点压入栈中
    while (cur != null) {
        stack.push(cur);
        cur = cur.next;
    }
    // 出栈 pop
    while (stack.size() > 0) {
        System.out.println(stack.pop());
    }
}

最后补一个自己用递归写的吧
其实递归的代码看似简单
从复杂度方面考虑消耗是非常大的

public static void recursion(HeroNode c) {
    if (c.next == null) {
        System.out.println(c);
        return;
    }
    recursion(c.next);
    System.out.println(c);
}

课后作业:合并两个链表,要求合并后依然有序

思路:老师给的思路
新建一个中间链表,判断需要合并的两个链表的编号,依次添加到新的链表中,其实这个思想的坑和反转链表的一样

思路:实现

public static SingleLinkedList merge(HeroNode head1, HeroNode head2) {
    // 判空
    SingleLinkedList linkedList = new SingleLinkedList();
    if (head1.next == null) {
        linkedList.setHead(head2);
        return linkedList;
    }
    if (head2.next == null) {
        linkedList.setHead(head1);
        return linkedList;
    }
    while (true) {
        HeroNode temp1 = head1.next;
        HeroNode temp2 = head2.next;
        if (temp1 == null && temp2 == null) {
            break;
        }
        if (temp1 != null && temp2 == null) {
            head1.next = temp1.next;
            temp1.next = null;
            linkedList.add(temp1);
            continue;
        }
        if (temp1 == null && temp2 != null) {
            head2.next = temp2.next;
            temp2.next = null;
            linkedList.add(temp2);
            continue;
        }
        if (temp1.no < temp2.no) {
            head1.next = temp1.next;
            temp1.next = null;
            linkedList.add(temp1);
        } else {
            head2.next = temp2.next;
            temp2.next = null;
            linkedList.add(temp2);
        }
    }
    return linkedList;
}

基本效果是实现了,但是我感觉冗余很大,有很大的优化空间

双向链表

单向链表的缺点分析

  1. 单向链表,查找只能是一个方向,而双向链表,则可以是想前或者向后查找
  2. 单向链表不能自我删除,双向链表,则可以实现自我删除。

思路分析

  1. 遍历:方式和单链表哦一样,只是可以想前,也可以向后查找
  2. 添加:(默认添加到双向链表最后)

线找到双向链表的最后的节点
temp.next = newHeroNode
newHeroNode.pre=temp

  1. 修改:也和原来的单向链表方式相同
  2. 删除:

因为是双向链表,因此我们可以实现自我哦哦删除某个节点,直接找到要删除的这个节点比如temp
temp.pre.next=temp.next temp.next.pre=temp.pre

代码实现

public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        System.out.println("双向列表的测试");
        HeroNode2 hero1 = new HeroNode2(1, "能天使", "抛光机");
        HeroNode2 hero2 = new HeroNode2(2, "银灰", "大脆皮");
        HeroNode2 hero3 = new HeroNode2(3, "闪灵", "喜羊羊");
        HeroNode2 hero4 = new HeroNode2(4, "王维娜", "卡手之王");
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add(hero1);
        doubleLinkedList.add(hero2);
        doubleLinkedList.add(hero3);
        doubleLinkedList.add(hero4);
        // 添加测试
        doubleLinkedList.list();
        // 修改测试
        HeroNode2 newNode = new HeroNode2(4, "阿米娅", "驴");
        doubleLinkedList.update(newNode);
        doubleLinkedList.list();
        // 删除测试
        doubleLinkedList.del(2);
        doubleLinkedList.list();
    }
}
// 创建一个双向链表的类
class DoubleLinkedList {
    // 先初始化一个头节点,头节点不要动,不存放具体的数据
    private HeroNode2 head = new HeroNode2(0, "", "");
    public HeroNode2 getHead() {
        return head;
    }
    public void add(HeroNode2 heroNode) {
        // 因为head节点不能动,因此我们需要一个辅助变量temp
        HeroNode2 temp = head;
        // 遍历链表,找到最后
        while (temp.next != null) {
            temp = temp.next;
        }
        // while 循环结束时 temp就指向了链表的最后
        temp.next = heroNode;
        heroNode.pre = temp;
    }
    // 修改 双向链表修改和单向列表一样
    public void update(HeroNode2 newHeroNode) {
        // 判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 找到要修改的节点
        HeroNode2 temp = head.next;
        boolean flag = false; // 是否找到
        while (true) {
            if (temp == null) {
                break; // 到链表的最后了
            }
            if (temp.no == newHeroNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 根据flag判断是否找到
        if (flag) {
            temp.name = newHeroNode.name;
            temp.nickname = newHeroNode.nickname;
        } else {
            System.out.printf("没有找到编号位%d节点", newHeroNode.no);
        }
    }
    // 删除节点
    // 对于双向链表,我们可以直接找到要删除的这个节点
    // 找到以后,自我删除即可
    public void del (int n) {
        // 判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode2 temp = head.next;
        boolean flag = false; // 是否找到
        while (true) {
            if (temp == null) {
                break; // 到链表的最后了
            }
            if (temp.no == n) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.pre.next = temp.next;
            if (temp.next != null) {
                // 这里代码有问题 如果是最后一个节点就不需要这句话,否则会出现空指针
                temp.next.pre = temp.pre;
            }
        } else {
            System.out.println("待删除节点不纯在");
        }
    }
    // 遍历双向链表
    // 显示链表
    public void list() {
        // 判断链表是否为空
        if (head.next == null) {
            //链表为空
            return;
        }
        HeroNode2 temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }
}
class HeroNode2 {
    public int no;
    public String name;
    public String nickname;
    public HeroNode2 next;
    public HeroNode2 pre;
    public HeroNode2(int hNo, String hName, String hNickname) {
        this.name = hName;
        this.no = hNo;
        this.nickname = hNickname;
    }
    // 显示方便重写toString方法
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

课后作业

实现根据序号添加的方法

public void addByOrder(HeroNode2 heroNode) {
    // 因为头节点不能动,因此还是需要一个辅助变量来帮助找到添加的位置
    // 因为是个单链表,因此我们找的temp是位于添加位置的前一个节点,否则就插入不了了
    HeroNode2 temp = head;
    boolean flag = false; // 标志添加的编号是否纯在默认是false
    while (true) {
        if (temp.next == null) {
            break;
        }
        if (temp.next.no > heroNode.no) {
            break;
        } else if (temp.next.no == heroNode.no) { // 编号纯在
            flag = true; // 说明编号存在
            break;
        }
        temp = temp.next; // 后移
    }
    // 判断flag的值
    if (flag) {
        // 编号存在
        System.out.println("准备插入的英雄编号已经存在" + heroNode.no);
    } else {
        // 插入到链表中
        if (temp.next != null) {
            temp.next.pre = heroNode;
        }
        heroNode.next = temp.next;
        temp.next = heroNode;
        heroNode.pre = temp;
    }
}

环形链表

Joseph(约瑟夫)问题

约瑟夫问题为:设编号为1,2...n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,报到m的那个人出列,他的下一位又由1开始报数,报到m的那个人继续出列,直到所有人都出列为止,求产生的出列编号。

约瑟夫问题可以使用环形链表解决;

单向环形链表实现约瑟夫问题思路

添加思路

  1. 构建第一个节点,让first指向该节点,并形成环形
  2. 后面当我们没创建一个新的节点就吧该节点加入到已有的环形链表

遍历环形链表

  1. 先让一个辅助指针,指向first节点
  2. 然后通过一个循环遍历该环形链表即可cur.next=first

根据输入,生成一个小孩出圈的顺序

  1. 需求创建一个辅助指针helper 事先指向环形链表的最后这个节点
  2. 报数之前first和helper移动到k-1次,当小孩报数时,让first和helper指针同时移动m-1次
  3. 这是就可以将first指向的小孩节点出圈

first = first.next
helper.next=first
原来first指向的节点没有任何的引用会被垃圾回收

代码实现

public class Joseph {
    public static void main(String[] args) {
        // 测试
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);
        circleSingleLinkedList.countBoy(1, 2, 5);
    }
}
// 创建环形单向链表
class CircleSingleLinkedList {
    // 创建一个first节点,当前没有编号
    private Boy first = null;

    // 添加小孩,构建成一个环形链表
    public void addBoy(int nums) {
        // nums 数据校验
        if (nums < 1) {
            System.out.println("nums的值不正确");
            return;
        }
        Boy curBoy = null; // 辅助指针
        // 使用for循环来创建我们的环形链表
        for (int i = 1; i <= nums; i++) {
            // 根据编号,创建小孩节点
            Boy boy = new Boy(i);
            // 第一个小孩
            if (i == 1) {
                first = boy;
                first.setNext(first); // 构成环形链表
                curBoy = first;
            } else {
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy = boy;
            }
        }
    }
    // 根据用户的输入计算出出圈的顺序
    /**
     * @param startNo  从第几个小孩开始
     * @param countNum 表示数几下
     * @param nums     表示最初有多少个小孩在圈中
     */
    public void countBoy(int startNo, int countNum, int nums) {
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("参数输入有误,重新输入");
            return;
        }
        // 辅助指针
        Boy helper = first;
        while (helper.getNext() != first) {
            helper = helper.getNext();
        }
        // 报数之前first和helper移动到k-1次
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }
        // 说明圈中只有一个人
        while (helper != first) {
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            System.out.printf("小孩%d出圈\n", first.getNo());
            // 出圈
            first = first.getNext();
            helper.setNext(first);
        }
        System.out.printf("小孩%d出圈\n", first.getNo());
    }
    // 遍历当前的环形链表
    public void showBoy() {
        // 判空
        if (first == null) {
            System.out.println("空链表");
            return;
        }
        // 因为first不能动,使用辅助指针
        Boy curBoy = first;
        while (true) {
            System.out.println("小孩的编号\n" + curBoy.getNo());
            if (curBoy.getNext() == first) {
                break;
            }
            curBoy = curBoy.getNext();
        }
    }
}
// 创建一个boy节点
class Boy {
    private int no;
    private Boy next;

    public Boy(int no) {
        this.no = no;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public Boy getNext() {
        return next;
    }
    public void setNext(Boy next) {
        this.next = next;
    }
}

实际需求引出

输入一个表达式
计算[722-5+2-5+3-3]
这个问题不是让我们来拼字符串之类的求结果
而是探求计算器内部底层是怎么计算的
这就用到了 栈

栈(stack)介绍

  1. 栈是一个**先入后出(FILO-First In Last Out)**的有序序列表
  2. 栈是限制线行表中的元素的插入和删除只能在线行表的同一端进行的一种特殊线性表。允许插入和删除的一端位变化的一段,称之为栈顶(Top),另一端为固定的一端称之为栈底(Bottom)
  3. 最先放入的在栈底,最后放入的在栈顶

数组模拟栈思路分析

  1. 使用数组模拟栈
  2. 定义一个top,来表示栈顶,初始化为-1
  3. 入栈的操作,当有数据加入到栈时, top++;stack[top] = data;
  4. 出栈的操作,int val = stack[top],top--,return val

代码实现

实现很简单 看代码就完事了

public class ArrayStackDemo {

    public static void main(String[] args) {
        ArrayStack arrayStack = new ArrayStack(5);
        arrayStack.push(5);
        arrayStack.push(4);
        arrayStack.push(3);
        arrayStack.push(2);
        arrayStack.push(1);
        arrayStack.push(0);
        arrayStack.list();
        System.out.println(arrayStack.pop());
        System.out.println(arrayStack.pop());
        System.out.println(arrayStack.pop());
        arrayStack.list();
    }
}
class ArrayStack {
    private int maxSize;
    private int[] stack;
    private int top = -1;

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        this.stack = new int[maxSize];
    }

    // 栈满

    public boolean isFul() {
        return top == maxSize - 1;
    }

    // 空栈

    public boolean isEmpty() {
        return top == -1;
    }

    // 入栈
    public void push(int value) {
        // 先判断是否满栈
        if (isFul()) {
            System.out.println("满栈");
            return;
        }
        top++;
        stack[top] = value;
    }

    // 出栈
    public int pop() {
        if (isEmpty()) {
            // 抛出异常
            throw new RuntimeException("空栈");
        }
        int val = stack[top];
        top--;
        return val;
    }

    // 遍历栈 需要从栈顶开始显示
    public void list() {
        if (isEmpty()) {
            System.out.println("空栈");
            return;
        }
        for (int i = top; i >= 0; i--) {
            System.out.println(stack[i]);
        }
    }
}

栈实现综合计算器

思路分析

数据结构06_栈示意图.png

代码实现(一.最基础实现)

首先给之前的栈添加几个方法,便于实现计算器

// 返回运算符的优先级,优先级是程序员来定的,优先级由数字表示,数字大优先级高‘
public int priority(int oper) {
    if (oper == '*' || oper == '/') {
        return 1;
    } else if (oper == '+' || oper == '-'){
        return 0;
    } else {
        return -1; // 现在假定计算的表达式只有+-*/
    }
}
// 判断是不是一个运算符
public boolean isOper(int val) {
    return val == '+' || val == '-' || val == '*' || val == '/';
}
// 计算方法
public int cal (int num1, int num2, int oper) {
    int res = 0; // 计算结果
    switch (oper) {
        case '+':
            res = num1 + num2;
            break;
        case '-':
            res = num2 - num1;// 注意顺序
            break;
        case '*':
            res = num1 * num2;
            break;
        case '/':
            res = num2 / num1;// 顺序
            break;
        default:
            break;
    }
    return res;
}

实现代码

public class Calculator {
    public static void main(String[] args) {
        // 根据思路完成表达式的求解
        String expression = "3+2*6-2";
        // 创建两个栈
        ArrayStack numStack = new ArrayStack ( 10 );
        ArrayStack operStack = new ArrayStack ( 10 );
        // 定义需要的相关变量
        int index = 0;
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        char ch = ' '; // 每次扫描的char
        // 循环
        while(true) {
            if(index >= expression.length()) {
                break;
            }
            // 得到expression
            ch = expression.substring (index, index + 1).charAt (0);
            // 判断ch
            if (operStack.isOper(ch)) {
                // 运算符
                // 当前符号栈是否为空
                if (!operStack.isEmpty ()) {
                    // 非空
                    if (operStack.priority (ch) <= operStack.priority (operStack.peek())) {
                        num1 = numStack.pop ();
                        num2 = numStack.pop ();
                        oper = operStack.pop();
                        res = numStack.cal (num1, num2, oper);
                        // 压栈
                        numStack.push (res);
                        // 当前符号入栈
                        operStack.push (ch);
                    } else {
                        operStack.push (ch);
                    }
                } else {
                    // 为空 入栈
                    operStack.push(ch);
                }
            } else {
                numStack.push (ch - '0');
            }
            index++;
        }
        // 顺序算
        while (true) {
            // 如果符号栈为空,则计算到最后结果,数栈只有一个数字
            if (operStack.isEmpty ()) {
                break;
            }
            num1 = numStack.pop ();
            num2 = numStack.pop ();
            oper = operStack.pop();
            res = numStack.cal (num1, num2, oper);
            // 压栈
            numStack.push (res);
        }
        // 结果
        System.out.println (numStack.pop());
    }
}

存在的问题

  1. 只能计算个位数
  2. 计算3-2*6+2会出问题,因为只能判段当前字符和上一个如果优先级比上一个小或者相同,先算上一个,那么当前字符和上上一个是没有进行比较的,所以会出现计算出错的问题

二.解决多位数问题

思路
在压入数字的时候判断下一个字符是否为数字,是就存储起来拼串,直到不是数字的时候,将拼好的字符串转化为数字压入栈中
代码

String keepNum = ""; // 用于拼接
// 下面的代码 替代之前代码的numStack.push (ch - '0');即可
// 处理多位数
keepNum += ch;
// 如果ch是最后以为就直接入栈
if (index == expression.length() - 1) {
    numStack.push (Integer.parseInt (keepNum));
} else {
    // 判断下一个是不是数字,是继续扫描,不是就入栈
    if (operStack.isOper ( expression.substring ( index + 1, index + 2 ).charAt ( 0 ) )) {
        // 是操作符
        numStack.push ( Integer.parseInt ( keepNum ) );
        keepNum = "";
    }
}

三.解决个别运算顺序问题

思路
问题发生的原因之前写了,解决方案很简单,把判断换成循环就好了,计算完成后不要直接压栈让它继续和下一个比较就好了
代码
将之前的if (!operStack.isEmpty ()) {体变为以下代码即可

while (!operStack.isEmpty() && operStack.priority(ch) <= operStack.priority(operStack.peek())) {
    num1 = numStack.pop ();
    num2 = numStack.pop ();
    oper = operStack.pop();
    res = numStack.cal (num1, num2, oper);
    // 压栈
    numStack.push (res);
}
// 当前符号入栈
operStack.push(ch);

小结

老师的代码解决了位数的问题,但是从弹幕看到了有人在说个别情况会计算出错,就分析了出错的原因并写出了解决方案,收获颇多。
也说明了,跟一个码字机器一样跟着老师走是学不到东西的,要自己动手,自己实践才行!

前缀(波兰),中缀,后缀(逆波兰)表达式

前缀表达式(波兰表达式)

  1. 前缀表达式又称波兰表达式,前缀表达式的运算符位于操作数之前
  2. 举例说明:(3+4)5-6对应的前缀表达式就是-+3456

前缀表达式的计算机求值
从右到左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对他们做相应的计算(栈顶元素和次顶元素),并将结果入栈:重复上述过程直到表达式最左端,最后运算得出的值即是表达式的结果

例如(3+4)5-6对应的前缀表达式就是-+3456,针对前缀表达式的求值如下:

  1. 从右到左扫描,将6,5,4,3压入堆栈
  2. 遇到+运算符,因此弹出3和4,计算3+4得7压入栈中
  3. 接下来是因此弹出7和5计算75=35压入栈中
  4. 最后是-计算35-6得29,为最终结果

中缀表达式

  1. 中缀表达式就是常见得运算表达式比如 76+14+423
  2. 中缀表达式求值是我们人人最熟悉得,但是对于计算机很不友好,所以一般会将中缀表达式转化为其他得表达式(一般是后缀表达式)

后缀表达式

  1. 后缀表达式又称逆波兰表达式与前缀表达式相类似,只是运算符位于操作数之后
  2. 举例:(3+4)5-6 的逆波兰表达式就是 **34+56-**
  3. 更多例子
中缀表达式后缀(逆波兰)表达式
a+bab+
a+(b-c)abc-+
a+(b-c)*dabc-d*+
a+d*(b-c)adbc-*+
a=1+3a13+=

后缀表达式的计算机求值
从左到右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对他们做相应的计算,并将结果入栈:从夫上诉过程知到表达式到达最右侧,对吼运算得出的值即为表达式的结果

例如:(3+4)5-6对应的前缀表达式就是34+56,针对后缀表达式求值步骤如下:

  1. 从左到右扫描,将3和4压入堆栈
  2. 遇到+运算符,因此弹出3和4,计算3+4 = 7压入栈中
  3. 5入栈
  4. 遇到弹出5和7计算75=35入栈
  5. 6入栈
  6. -运算符计算35-6=29最终结果

逆波兰计算器实现

完成一个后缀表达式计算器

  1. 输入一个逆波兰表达式(后缀表达式),使用栈(Stack jdk提供的)计算结果
  2. 支持小括号和多位整数计算

代码
思想就是之前后缀表达式的计算机求值的分析

public class PolandNotation {
    public static void main(String[] args) {
        // 先定义一个逆波兰表达式, 数字和符号使用空格隔开
        String suffixExpression = "3 4 + 5 * 6 - ";
        // 思路
        // 1. 先将suffixExpression放到一个ArrayList中
        // 2. ArrayList传递给一个方法,这个方法配合栈完成计算
        List<String> listString = getListString ( suffixExpression );
        System.out.println (calculate (listString));
    }
    // 将一个逆波兰表达式,依次将数据和运算符 放入ArrayList中
    public static List<String> getListString(String suffixExpression) {
        // 将字符串分割
        String[] split = suffixExpression.split ( " " );
        ArrayList<String> list = new ArrayList<> ();
        for (String ele : split) {
            list.add (ele);
        }
        return list;
    }
    // 完成对逆波兰表达式的运算
    public static int calculate(List<String> list) {
        // 创建一个栈。只需要一个栈
        Stack<String> strings = new Stack<> ();
        for (String item : list) {
            // 使用一个正则表达式来取出数
            if (item.matches ("\\d+")) { // 匹配的时多位数
                // 入栈
                strings.push (item);
            } else {
                // 弹出两个数运算再压入
                int a = Integer.parseInt (strings.pop());
                int b = Integer.parseInt (strings.pop());
                int res = 0;
                if (item.equals ("+")) {
                    res = a + b;
                } else if (item.equals ("-")) {
                    res = b - a;
                } else if (item.equals ("*")) {
                    res = a * b;
                } else if (item.equals ("/")) {
                    res = b / a;
                } else {
                    throw new RuntimeException ("符号有误");
                }
                strings.push (String.valueOf(res));
            }
        }
        // 最后再Stack中的数据就时运算结果
        return Integer.parseInt (strings.pop());
    }
}

中缀表达式转后缀表达式

具体步骤(七大步)

  1. 初始化两个栈:运算符栈s1和储存中间结果栈s2;
  2. 从左至右扫描中缀表达式
  3. 遇到操作数时,将其压s2
  4. 遇到运算符时比较其与s1栈顶运算符的优先级
    1. 如果s1为空或者栈顶运算符为左括号(则直接将次运算符入栈
    2. 否则,若优先级比栈顶运算符的高,也将运算符压入s1
    3. 否则,将s1栈顶的运算符弹出并压入到s2中,再次转到(4-1)与s1中新的栈顶运算符比较
  5. 遇到括号时
    1. 如果时左括号直接压入s1
    2. 如果时右括号则一次弹出栈顶的运算符并压入s2直到遇到左括号为止,此时将这一对括号丢弃
  6. 重复步骤2到5直到到达表达式最右边
  7. 依次弹出s2中的元素并输出,结果的逆序就是中缀表达式对应得后缀表达式

图例步骤
例子:1+((2+3)*4)-5 转化为后缀表达式
数据结构07_栈后缀表达式.png

代码实现

辅助方法编写

将中缀表达式转成一个list

public static List<String> toInfixExpressionList(String s) {
    ArrayList<String> ls = new ArrayList<> ();
    int i = 0; // 指针用于,遍历s
    String str; // 对多位数的拼接
    char c; // 遍历到一个字符放入c
    do {
        // c是一个非数字,需要加入到ls中去
        if ((c = s.charAt (i)) < 48 || (c = s.charAt (i)) > 57) {
            ls.add("" + c);
            i++; // i需要后移
        } else { // 如果是一个数 需要考虑多位数问题
            str = ""; // 制空
            while (i < s.length () && (c = s.charAt (i)) >= 48 && (c = s.charAt (i)) <= 57) {
                str += c; // 拼接
                i++;
            }
            ls.add (str);
        }
    } while (i < s.length ());
    return ls;
}

编写一个类 operation 返回一个运算符的优先级

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

    // 返回对应的优先级数字

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

中缀转后缀代码

public static List<String> parseSuffixExpreesionList(List<String> ls) {
Stack<String> s1 = new Stack<> (); // 符号栈
// 因为s2再转换过程中没有pop操作 后面还需要逆序操作,所以用ArrayList替代
ArrayList<String> s2 = new ArrayList<> ();

// 遍历ls
for (String item : ls) {
    // 如果是一个数就加入s2
    if (item.matches ("\\d+")) {
        s2.add (item);
    } else if (item.equals ("(")) {
        s1.push (item);
    } else if (item.equals (")")) {
        // 直到碰到(前弹出s1加入s2
        while (!s1.peek().equals ("(")) {
            s2.add (s1.pop ());
        }
        // 左括号要弹出
        s1.pop ();
    } else {
        // item的优先级小于等于栈顶优先级运算符,将s1栈顶的运算符弹出压入到s2中
        // 我们缺少一个优先级高低的方法
        while (s1.size () != 0 && Operation.getValue (s1.peek ()) >= Operation.getValue (item)) {
            s2.add (s1.pop ());
        }
        // 将item压入栈中
        s1.push (item);
    }
}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://www.byfree.top/archives/algorithm01