数据结构与算法（java版）

[TOC]

引子

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

• 线性结构
  • 特点：数据元素一对一的线性关系
  • 线性结构有两种不同的存储结构：一种是顺序存储结构，元素处于相邻地址空间，顺序存储的线性表又称为顺序表；另一种是链式存储结构，元素节点保存数据元素和相邻元素地址信息，相邻元素不一定在地址空间上连续。
  • 常见的线性结构：数组、队列、链表和栈
• 非线性结构
  • 常见的有：二维数组、多维数组、广义表、树结构、图结构

时间复杂度

• 时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。**一个算法中的语句执行次数成为语句频度或时间频度。**记为T(n) (注意：是语句重复执行的次数，而不是语句条数)

• 时间复杂度：一般情况下，算法的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋于无穷大时，T(n)/f(n)的极限值为不等于零的常熟，则成f(n)是T(n)的同数量级函数，记作**T(n)=O{f(n)}，称O{f(n)}为算法的渐进时间复杂度，简称时间复杂度**。

  时间频度不同，但时间复杂度可能相同。

  举例说明

  T(n)=n²+7n+6 与 T(n)=3n²+2n+2 它们的T(n) 不同，但时间复杂度相同，都为O(n²)

• 计算时间复杂度的方法

  • 用常数1代替运行时间中的所有加法常数 T(n) = n²+7n+6 => T(n) = n²+7n+1
  • 修改后的运行次数函数中，只保留最高阶项 T(n) = n²+7n+1 => T(n) = n²
  • 去除最高阶项的系数 T(n) = n² => T(n) = n² => O(n²)

• 常见的时间复杂度

  • 常数阶O(1)

    

  • 对数阶O(log2n)：以2为底，n为对数

    

  • 线性阶O(n)

    

  • 线性对数阶O(nlog2n)

    

  • 平方阶O(n^2)

    

  • 立方阶O(n^3)

    参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似

  • k次方阶O(n^k)

    参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似

  • 指数阶O(2^n) 我们应该尽可能避免使用指数阶的算法

    常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(nk) ＜Ο(2n) ，随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低

• 平均时间复杂度和最坏时间复杂度

  • 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。

  • 最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。

  • 平均时间复杂度和最坏时间复杂度是否一致，和算法有关。

    

空间复杂度

• 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模n的函数。
• 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况
• 在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间.

一、稀疏数组

• 原理

  原始数组之中有很多重复或无用的数据，可以通过记录大量重复数据的位置和值来代替原来的重复数据，从而达到压缩的目的。

• 处理方法

  1. 记录数组一共几行几列，有多少个不同的值
  2. 把具有不同数值的元素行列记录至一个新的数组中（这个数组肯定会小于原先的数组），从而达到压缩的目的。

• 代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

  import java.util.Arrays; public class first { public static void main(String[] args) { //初始化二维数组 int[][] oldArray =new int[10][10]; oldArray[1][3]=1; oldArray[2][7]=3; oldArray[5][2]=10; System.out.println(Arrays.deepToString(oldArray)); int validNum =0; //获取不同值个数 for (int i=0;i<oldArray.length;i++){ for (int j=0;j<oldArray[i].length;j++){ //将非重复元素存到压缩数组 if (oldArray[i][j]!=0){ validNum++; } } } //初始化稀疏数组，确定深度 int[][] parseArray =new int[validNum+1][3]; int index=0; //初始化稀疏数组第一个索引，用来表示原数组的个数及值重值 parseArray[0][0]=oldArray.length; parseArray[0][1]=oldArray[0].length; parseArray[0][2]=0; for (int i=0;i<oldArray.length;i++){ for (int j=0;j<oldArray[i].length;j++){ //将非重复元素存到压缩数组 if (oldArray[i][j]!=0){ index++; //记录非零值 parseArray[index][0]=i; parseArray[index][1]=j; parseArray[index][2]=oldArray[i][j]; } } } //稀疏数组结果 System.out.println(Arrays.deepToString(parseArray)); //还原稀疏数组 //初始化稀疏数组大小 int[][] newArray =new int[parseArray[0][0]][parseArray[0][1]]; //读取稀疏数组数值 for (int i=1;i<parseArray.length;i++){ newArray[parseArray[i][0]][parseArray[i][1]]=parseArray[i][2]; } System.out.println(Arrays.deepToString(newArray)); } }

二、队列

1. 非循环队列(一般不使用)

• 原理

  • 队列是一个有序列表，可以使用数组或者链表实现。数组的特点是相邻地址索引快，读操作效率更高；链表是链式存储，写操作效率更高

  • 遵循先入先出的原则

  • 示意图

    

• 处理方法（数组）

  • 队列初始化时，默认front==rear==-1，头指针始终指向队列第一个元素的前一个索引位置（不一定存在），；尾指针始终指向队列队后一个元素的索引位置

  • 队列元素增加：尾指针后移，rear+1，当rear=maxSize-1表示队列已满

  • 队列元素取出：头指针后移，front-1，当front==rear表示队列已空

• 代码实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

  public class queue { //队列深度 private int maxSize; //队头指针 private int front; //队尾指针 private int rear; //队列元素使用数组作为队列结构 private int[] arr; //添加队列元素 public void addQueue(int e){ if (isFull()){ System.out.println("the queue is full..."); return; } this.rear++; this.arr[this.rear]=e; } //取出队列元素 public int getQueue(){ //判断队列是否为空 if (isEmpty()){ throw new RuntimeException("the queue is empty..."); } this.front++; return this.arr[this.front]; } //显示队列数据 public void list() { for (int v : arr) { System.out.print(v+" "); } } //判断队列是否已满 public boolean isFull(){ return this.maxSize-1==this.rear; } //判断队列是否为空 public boolean isEmpty(){ return this.rear==this.front; } //构造队列 public queue(int maxSize) { this.maxSize = maxSize; this.front = -1; this.rear = -1; this.arr = new int[maxSize]; } }

2. 循环队列

• 非循环队列的缺陷

  非循环队列的空间不能反复利用，队列空间一旦填满不能再对队列进行写操作。其问题在于，非循环队列元素添加的实现只是简单的将队列进行后移，每添加一次元素，rear后移一个位置，直到rear==maxSize-1时，不能再往后移（队列已满)。也就是说，目前数组使用一次就不能使用了，比较浪费

  但是可以通过对队列的指针取余（也叫取模），可以解决这个缺陷。内存上并没有环形的结构，因此环形队列实际上是数组的线性空间来实现的。当数据到了尾部应该怎么处理呢？它将转回到原来位置进行处理，通过取模操作来实现

  所谓取模，只是将不断增大的rear通过取模（取余）的方式，将rear大小不断缩小在一个“环”里，rear沿着“环”走

• 原理图

  

• 处理方法

  • front头指针指向队列第一个元素；rear尾指针指向队列最后一个元素的后一个位置。（与非循环队列相反）
  • 队满时，(rear+1)%maxSize==front，意即rear后一个位置的下一个元素如果是front，表示队列已满
  • 队空时，rear==front
  • 队列初始化时，rear==front==0
  • 队列之中的有效数据个数：(rear+maxSize-front)%maxSize或者Math.abs(rear-front)，两者结果一样，因为rear与front的差值不可能查过maxSize

• 代码实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

  public class circleQueue { private int maxSize; private int front; private int rear; private int[] arr; //判断队列是否为空 public boolean isEmpty(){ return this.front==this.rear; } //判断队列是否满了 public boolean isFull(){ return (this.rear+1)%maxSize==this.front; } //添加队列元素 public void addQueue(int e){ if (isFull()){ throw new RuntimeException("queue is full\n"); } this.arr[this.rear]=e; //注意取模 this.rear=(this.rear+1)%this.maxSize; } //取出队列元素 public int getQueue(){ if (isEmpty()){ throw new RuntimeException("queue is empty\n"); } int v = arr[front]; //取模 front=(front+1)%maxSize; return v; } //获取有效个数 public void list(){ for (int i = 0; i < (rear + maxSize - front) % maxSize; i++) { System.out.print(arr[front+i]+" "); } } public circleQueue(int maxSize) { this.maxSize = maxSize; this.front=0; this.rear=0; this.arr=new int[maxSize]; } }

三、链表

1. 单链表

• 原理

  • 链表是以节点的方式存储的，每个节点包含data域（存放数据）、next域（指向下一个节点）

  • 链表的各个节点地址不一定是连续

  • 链表分类：带头节点的链表和没有头节点的链表。

  • 原理图

    

    head头节点：不存放数据

• 处理方法

  • 创建一个head头节点。作用是表示整个链表的地址
  • 添加一个节点就将链表的最后一个节点的next域指向这个节点
  • 插入一个节点就先遍历链表找出需要插入的位置，然后让指针插入对应即可
  • 删除一个节点就先遍历找到这个节点，然后将这个节点的前后节点指针相连，这个节点就没有指针指向他，在java中会被垃圾回收机制回收

• 代码实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145

  public class singleLinkedList { public static void main(String[] args) { heroNode h1 = new heroNode(1, "刘海斌"); heroNode h2 = new heroNode(2, "包文杰"); heroNode h3 = new heroNode(3, "王铁霖"); heroNode h4 = new heroNode(4, "牟国柱"); managerSingleList manager = new managerSingleList(); manager.addNode(h1); manager.addNode(h2); manager.addNode(h3); manager.addNode(h4); manager.showList(); manager.updateList("cold bin", 1); manager.insertNode(new heroNode(0, "无"), 1); manager.showList(); manager.delNode(3); manager.showList(); } } class managerSingleList { //头节点 private heroNode head; public managerSingleList() { this.head = new heroNode(0, ""); } //添加 public void addNode(heroNode node) { //遍历链表至最后一个节点 heroNode temp = head; while (temp.next != null) { temp = temp.next; } //插入尾节点 temp.next = node; node.next = null; System.out.println("添加成功"); } //删除 public void delNode(int no) { heroNode head = this.head; if (head.next == null) { System.out.println("链表为空"); return; } heroNode temp = head; while (temp.next != null) { //记录要删除节点的前一个结点 heroNode beforeNode = temp; temp = temp.next; if (temp.no == no) { //将删除节点的前一个节点next指向删除节点的下一个节点 beforeNode.next = temp.next; System.out.println("删除成功"); return; } } System.out.println("没有找到编号"); } //插入：在编号之前 public void insertNode(heroNode node, int no) { heroNode head = this.head; if (head.next == null) { System.out.println("链表为空"); return; } heroNode temp = head; while (temp.next != null) { heroNode beforeNode = temp; temp = temp.next; if (temp.no == no) { //记录对应编号节点的前一个节点位置，将新节点插入这个位置，意即beforeNode之后，temp之前； beforeNode.next = node; node.next = temp; System.out.println("插入成功"); return; } } System.out.println("没有找到编号"); } //修改 public void updateList(String newName, int no) { heroNode head = this.head; if (head.next == null) { System.out.println("链表为空"); return; } heroNode temp = head; while (temp.next != null) { temp = temp.next; if (temp.no == no) { temp.name = newName; System.out.println("更新成功"); return; } } System.out.println("没有找到编号"); } //查询 public void showList() { heroNode head = this.head; if (head.next == null) { System.out.println("链表为空"); return; } heroNode temp = head; while (temp.next != null) { //头节点无数据，因此跳过 temp = temp.next; System.out.println(temp); } } } class heroNode { int no; String name; heroNode next; public heroNode(int no, String name) { this.no = no; this.name = name; } @Override public String toString() { return "heroNode{" + "no=" + no + ", name=" + name + '}'; } }

  删除的原理：被删除的节点将不会有其他引用指向，会被垃圾回收机制回收

• 应用场景：

  单链表的应用的话一般能用在 2 种场景下：

  • 第 1 种基操。 在你应用的场景中，插入和删除的操作特别多，你不想因为这俩操作浪费你太多的时间，此时用单链表，可以改善插入和删除操作浪费的时间。

  • 第 2 种骚操。在你应用的场景种，不知道有多少个元素，那这个时候你用单链表，每来一个新的元素你就链在表里，这种情况是用链表处理的绝佳方式。也是很容易被大家忽略的。

• 单链表常见面试题

  • 单链表中节点的个数：遍历单链表有效节点个数（不算头节点）
  • 单链表反转：先定义一个反转之后的头节点；然后遍历原始链表，每遍历一个链表元素就将这个链表元素插进紧跟反转链表的头节点之后的位置。然后再将原来头节点换成现在的头节点，意即，反转链表。
  • 逆序打印单链表：
    1. 打印链表反转之后的链表，这样做的问题是会破坏单链表的结构；（不建议）
    2. 栈，将各个节点压入栈中，打印时，从栈中取出（不同的语言对栈的使用不一样，也可以考虑自己利用队列实现一个栈）

2. 双链表

• 单链表存在的问题

  • 单向链表查找的方向只能是一个方向（即头节点往后），而双向链表可以向前或者向后查找。
  • 单向链表不能自我删除，需要借助辅助节点，而双向链表可以自我删除

• 示意图

  

• 处理方法

  • 遍历和单链表一样，只是多了一个pre指针，可以双向遍历（向前向后查找）

  • 添加节点，将节点的两个指针连在双向链表最后一个节点即可

  • 修改节点，先遍历找到节点，然后改变其值

  • 删除节点，先便利找到这个节点temp，将前节点的next指针指向后节点，后节点的pre指针指向前节点（此处可以temp.pre.next=temp.next&&temp.next.pre=temp.pre）

  • 按顺序插入节点，先确定插入位置，然后插入，原理如下图（分四步，顺序不能乱）

    

• 代码实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135

  package linkedList; public class doublyLinkedList { public static void main(String[] args) { heroNode1 h1 = new heroNode1(1, "刘海斌"); heroNode1 h2 = new heroNode1(2, "包文杰"); heroNode1 h3 = new heroNode1(3, "王铁霖"); heroNode1 h4 = new heroNode1(4, "牟国柱"); managerHeroNode1 m =new managerHeroNode1(); m.addNode(h1); m.addNode(h2); m.addNode(h3); m.addNode(h4); m.listNode(); m.updateNode(new heroNode1(2,"小包")); m.insertNode(new heroNode1(3,"邓涔浩")); m.deleteNode(4); m.listNode(); } } class managerHeroNode1 { heroNode1 head; public managerHeroNode1() { this.head = new heroNode1(-1, ""); } public boolean isEmpty() { if (head.next != null) return false; else return true; } //末尾添加node public void addNode(heroNode1 node) { heroNode1 temp = head; //遍历到末尾 while (temp.next != null) { temp = temp.next; } temp.next = node; node.pre = temp; System.out.println("成功添加"); } //修改节点 public void updateNode(heroNode1 node) { if (isEmpty()) { System.out.println("链表为空"); return; } heroNode1 temp = head; while (temp.no != node.no) { temp = temp.next; if (temp == null) { System.out.println("没找到该节点"); return; } } temp.name = node.name; System.out.println("修改成功:" + temp); } //删除节点 public void deleteNode(int no) { if (isEmpty()) { System.out.println("链表为空"); return; } heroNode1 temp = head; while (temp.no != no) { temp = temp.next; } //temp的下一个节点的pre指针指向temp的上一个节点 // temp.next.pre=temp.pre;//注意如果temp是最后一个节点，这里有错： if (temp.next != null) temp.next.pre = temp.pre; //temp的上一个节点的next指针指向temp的下一个节点 temp.pre.next = temp.next; System.out.println("删除成功:" + temp); } //按序插入节点 public void insertNode(heroNode1 node) { if (isEmpty()) { System.out.println("链表为空"); return; } heroNode1 temp = head; while (temp.no <= node.no) { temp = temp.next; //如果插入节点在最后，直接添加 if (temp==null){ addNode(node); return; } } //此操作注意先后顺序，否则会因为链条一部分断裂而导致后面的节点变成null //首先 node.pre=temp; node.next=temp.next; temp.next=node; temp.next.pre=node; System.out.println("插入成功:" + node); } //遍历链表 public void listNode() { if (isEmpty()) { System.out.println("链表为空"); return; } heroNode1 temp = head; while (temp.next != null) { temp = temp.next; System.out.println(temp); } } } class heroNode1 { //节点data属性 int no; String name; //指针域 heroNode1 pre; heroNode1 next; public heroNode1(int no, String name) { this.no = no; this.name = name; } @Override public String toString() { return "heroNode1{" + "no=" + no + ", name='" + name + '\'' + '}'; } }

3. 单向环形链表

• 原理

  

• 约瑟夫问题

  在罗马人占领乔塔帕特后，39个犹太人和Josephus及他的朋友躲进一个洞里，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第一个人开始报数，报数到3的人就自杀，再由下一个人重新报1，报数到3的人就自杀，这样依次下去，知道剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向链表描述该结构并呈现整个自杀过程。

  单向环形链表解决

• 代码实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

  package linkedList; public class singleRingLinkedList { public static void main(String[] args) { managerList m = new managerList(); m.addNode(41); m.list(); System.out.println(); m.pops(1, 3, 5); } } class managerList { boyNode head; public managerList() { //头节点，标记首位置 head = new boyNode(-1); head.next = head;//注意闭环 } //添加 public void addNode(int num) { if (num < 1) { System.out.println("参数错误"); return; } boyNode curNode = head; for (int i = 1; i <= num; i++) { boyNode node = new boyNode(i); if (i == 1) { head.no = node.no; continue; } curNode.next = node; node.next = head; //记录当前节点 curNode = node; } System.out.println("添加成功"); } //遍历链表 public void list() { if (head == null) { System.out.println("链表为空"); return; } boyNode curNode = head; while (curNode.next != head) { System.out.println(curNode); curNode = curNode.next; } System.out.println(curNode); } //取出节点 public void pops(int startNo, int countNum, int nums) { //先对数据进行检验 if (head==null||countNum<1||countNum>nums){ System.out.println("参数输入有误"); return; } //helper指针指向链表尾节点 boyNode helper = head; while (helper.next != head) { helper = helper.next; } //移动到报数节点 for (int i = 0; i < startNo-1; i++) { helper = helper.next; head = head.next; } while (head != helper) { //报数移动countNum-1次 for (int i = 1; i < countNum; i++) { helper = helper.next; head = head.next; } int number = head.no; head = head.next; helper.next = head; System.out.println("移除节点：" + number); } System.out.println("最后的节点：" + head.no); } } class boyNode { int no;//编号 boyNode next;//指针域 public boyNode(int no) { this.no = no; } @Override public String toString() { return "boyNode{" + "no=" + no + '}'; } }

四、栈

1. 原理

• 栈是一个先入后出的有序列表

• 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶；另一端为固定的一端，成为栈底

• 最先放入栈的元素在栈底，最后放入的元素在栈顶；而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

• 原理图

  

2. 代码实现（数组模拟栈）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

package stack;
public class stackDemo {
    public static void main(String[] args) {
        managerStack m = new managerStack(5);
        m.push(new node(1));
        m.push(new node(2));
        m.push(new node(3));
        m.list();
        System.out.println(m.pop());
        System.out.println(m.pop());
        m.list();
        System.out.println(m.pop());
        m.push(new node(4));
        m.list();
        System.out.println(m.pop());
    }
    //入栈
}
class managerStack {
    int top;
    int maxSize;
    node[] nodes;
    public managerStack(int maxSize) {
        //初始化栈顶
        top = -1;
        //栈的容量
        this.maxSize = maxSize;
        //初始化栈的大小
        nodes = new node[maxSize];
    }
    //入栈
    public void push(node node) {
        if (top < maxSize - 1) {
            nodes[++top] = node;
            return;
        }
        System.out.println("栈溢出");
    }
    //出栈
    public node pop() {
        if (top == -1) {
            throw new RuntimeException("栈空");
        }
        return nodes[top--];
    }
    //遍历
    public void list() {
        if (top == -1) {
            throw new RuntimeException("栈空");
        }
        System.out.println("栈元素：");
        for (int i = top; i >= 0; i--) {
            System.out.printf("nodes[%d]=%d\n", i, nodes[i].no);
        }
    }
}
class node {
    int no;

    public node(int no) {
        this.no = no;
    }
    @Override
    public String toString() {
        return "node{" +
                "no=" + no +
                '}';
    }
}

3. 波兰计算器

① 无括号版波兰计算器

• 思路

  

  针对多位数运算时的逻辑：如果扫描到数字就继续扫描下一位直到不是数字为止，将扫描的数字字符拼接成串然后转化为数字

• 代码实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127

  package stack; import java.util.Scanner; public class calculatorByStackDemo { public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("请输入合法表达式："); String express = sc.next(); char[] chars = express.toCharArray(); //数字栈 stack stackNumber = new stack(10); //符号栈 stack stackOperation = new stack(10); int num1 = 0; int num2 = 0; int val = 0; int operation = 0; String number = ""; for (int i = 0; i < chars.length; ) { //符号 if (stackOperation.isOperation(chars[i])) { //符号栈为空，将符号压入符号栈 if (stackOperation.isEmpty()) stackOperation.push(chars[i]); else if (!stackOperation.isFull()) { //如果符号栈有操作符，进行比较，如果当前操作符的优先级低于或等于栈中的操作符， //就需要从数栈中pop两个数，再从符号栈里pop出一个符号进行运算，将得到的结果压 //入数栈，然后再将当前的操作符压入符号栈中 if (stackOperation.priority(chars[i]) <= stackOperation.priority(stackOperation.showTop())) { num1 = stackNumber.pop(); num2 = stackNumber.pop(); operation = stackOperation.pop(); val = stackNumber.calculate(num2, num1, operation); stackNumber.push(val); stackOperation.push(chars[i]); } else { //当前操作符优先级更高，再压入符号栈中 stackOperation.push(chars[i]); } } i++; } //如果是数字，先别慌入栈，再判断下一位是否是数字,是数字就拼接在一起 // if (stackNumber.isDigital(chars[i])){ // stackNumber.push(Character.getNumericValue(number)); // } while (stackNumber.isDigital(chars[i])) { number = number + chars[i]; i++; if (i == chars.length) break; } System.out.println(number); stackNumber.push(Integer.parseInt(number)); number = "";//清空上次数字残余 } //扫描完毕后，顺序从数栈和符号栈pop出两个数字和一个符号，并运算，最后数栈只有一个数字就是结果 //最后的栈中运算符都是同等优先级的运算符 while (!stackOperation.isEmpty()) { num1 = stackNumber.pop(); num2 = stackNumber.pop(); operation = stackOperation.pop(); val = stackOperation.calculate(num2, num1, operation); stackNumber.push(val); } System.out.println("计算的结果是：" + stackNumber.showButton()); } } class stack { int top; int maxSize; int[] nodes; public stack(int maxSize) { top = -1; this.maxSize = maxSize; nodes = new int[maxSize]; } public boolean isEmpty() { return top == -1; } public boolean isFull() { return top == maxSize - 1; } //入栈 public void push(int node) { if (isFull()) throw new RuntimeException("栈溢出"); nodes[++top] = node; } //出栈 public int pop() { if (isEmpty()) throw new RuntimeException("栈空"); return nodes[top--]; } //显示栈顶元素，但不取出 public int showTop() { return nodes[top]; } public int showButton() { return nodes[0]; } //优先级 public int priority(int operation) { if (operation == '*' || operation == '/') return 1; else if (operation == '+' || operation == '-') return 0; return -1; } //判断是不是操作符 public boolean isOperation(int operation) { return operation == '+' || operation == '-' || operation == '*' || operation == '/'; } //判断是不是数字 public boolean isDigital(int number) { return Character.isDigit(number); } //计算方法 public int calculate(int num1, int num2, int operation) { switch (operation) { case '+': return num1 + num2; case '-': return num1 - num2; case '*': return num1 * num2; case '/': return num1 / num2; default: return 0; } } }