devbox
我家小花儿
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Java数据结构与算法(1)_数据结构与算法是一门

作者：我家小花儿 | 2024-05-25 02:48:48

赞

踩

数据结构与算法是一门
  1. 数据结构与算法概述
    1.1 数据结构与算法关系
    1.2 实际编程中遇到的问题
    1.3 线性结构和非线性结构
  2. 稀疏数组和队列
    2.1 稀疏数组 SparseArray
    2.2 队列
  3. 链表
    3.1 链表介绍
    3.2 单链表应用
    3.3 单链表常见面试题
    3.4 双向链表应用实例
    3.5 单项环形链表应用实例
  4. 栈
    4.1 栈的实际应用
    4.2 栈的介绍
    4.3 栈的应用场景
    4.4 快速入门
    4.5 栈实现综合计算器
    4.6 逆波兰计算器
    4.7 中缀表达式转换为后缀表达式
    4.8 逆波兰计算器完整版

1. 数据结构与算法概述

1.1 数据结构与算法关系

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

1.2 实际编程中遇到的问题

1.2.1 Java代码：

	public static void main(String[] args) {
		String str = "Java,Java, hello,world!";
		String newStr = str.replaceAll("Java", "尚硅谷~"); //算法
		System.out.println("newStr=" + newStr);
	}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

问：试写出用单链表表示的字符串类及字符串结点类的定义，并依次实现它的构造函数、以及计算串长度、串赋值、判断两串相等、求子串、两串连接、求子串在串中位置等7个成员函数。

1.2.2 一个五子棋程序

五子棋程序

问：如何判断游戏的输赢，并可以完成存盘退出和继续上局的功能 棋盘=>二维数组=>(稀疏数组)=> 写入文件 【存档功能】
读取文件=>稀疏数组=>二维数组=> 棋盘 【接上局】

1.2.3 约瑟夫问题（丢手帕问题）

问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表（单向环形链表），然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束

1.2.4 其他常见算法问题

  1. 修路问题 ： 最小生成树(加权值)【数据结构】+ 普利姆算法
  2. 最短路径问题 ： 图+弗洛伊德算法
  3. 汉诺塔 ： 分支算法
  4. 八皇后问题 ： 回溯法

1.3 线性结构和非线性结构

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

1.3.1 线性结构

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

1.3.2 非线性结构

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

2. 稀疏数组和队列

2.1 稀疏数组 SparseArray

2.1.1 先看一个实际需求

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

2.1.2 基本介绍

当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
稀疏数组的处理方法是: 记录数组一共有几行几列，有多少个不同的值 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

2.1.3 应用实例

  1. 使用稀疏数组，来保留类似前面的二维数组(棋盘、地图等等)
  2. 把稀疏数组存盘，并且可以从新恢复原来的二维数组数
  3. 整体思路分析
    稀疏数组
    代码实现
  4. 二维数组 转 稀疏数组的思路
    4.1. 遍历 原始的二维数组，得到有效数据的个数 sum
    4.2. 根据sum 就可以创建 稀疏数组 sparseArr int[sum + 1] [3]
    4.3. 将二维数组的有效数据数据存入到 稀疏数组
  5. 稀疏数组转原始的二维数组的思路
    5.1. 先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组，比如上面的 chessArr2 = int [11][11]
    5.2. 在读取稀疏数组后几行的数据，并赋给 原始的二维数组 即可.
public static void main(String[] args) {
		/* 创建一个原始二维数组 11*11
		   1代表黑子，2代表蓝子，0代表没有
		 */
		int[][] chessArr1 = new int[11][11];
		chessArr1[1][2] = 1;
		chessArr1[2][3] = 2;
		System.out.println("二维数组为:");
		for (int[] rows : chessArr1) {
			for (int data : rows) {
				System.out.printf("%d\t",data);
			}
			System.out.println();
		}
		
		int[][] sparseArr = chessToSparseArr(chessArr1);
		System.out.println("稀疏数组为：");
		for (int[] row : sparseArr) {
			for (int data : row) {
				System.out.printf("%d\t",data);
			}
			System.out.println();
		}
		
		int[][] chessArr2 = sparseToChessArr(sparseArr);
		System.out.println("原始数组为：");
		for (int[] row : chessArr2) {
			for (int data : row) {
				System.out.printf("%d\t",data);
			}
			System.out.println();
		}
		
	}

	public static int[][] chessToSparseArr(int[][] chessArr1) {
		//二维数组转稀疏数组
		//1.先遍历二维数组得到非0元素的个数
		int sum = 0;
		for (int[] rows : chessArr1) {
			for (int data : rows) {
				if(data != 0)
					sum++;
			}
		}
		//2.创建对应的稀疏数组
		int[][] sparseArr = new int[sum+1][3];
		sparseArr[0][0] = chessArr1.length; 
		sparseArr[0][1] = chessArr1[0].length; 
		sparseArr[0][2] = sum; 
		//遍历二维数组，将非0值存入
		int count = 0;
		for (int i = 0; i < chessArr1.length; i++) {
			for (int j = 0; j < chessArr1[0].length; j++) {
				if(chessArr1[i][j] != 0) {
					count++;
					sparseArr[count][0] = i;
					sparseArr[count][1] = j;
					sparseArr[count][2] = chessArr1[i][j];
				}
			}
		}
		
		return sparseArr;
	}

	public static int[][] sparseToChessArr(int[][] sparseArr){
		//稀疏数组恢复为原始二维数组
		int[][] chessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
		for (int i = 1; i < sparseArr.length; i++) {
			chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
		}
		
		return chessArr2;
	}

  • 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

2.2 队列

2.2.1 队列介绍

队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则。

2.2.2 数组模拟队列

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示:
数组模拟队列

代码实现

class ArrayQueue{
	
	private int maxSize;  //最大容量
	private int front;    //队首
	private int rear;     //队尾
	private int[] arr;    //存放数据
	
	public ArrayQueue(int maxSize) {
		this.maxSize = maxSize;
		this.front = -1;  //指向队列头部，分析出是队首的前一个位置
		this.rear = -1;   //指向队列尾部，分析出是队尾的数据
		arr = new int[maxSize];
	}
	
	//判断队列是否为空
	public boolean isEmpty() {
		return front == rear;
	}
	
	//判断队列是否已满
	public boolean isFull() {
		return rear == maxSize-1;
	}
	
	//添加数据，即入队列
	public void addQueue(int n) {
		if(isFull()) {
			System.out.println("队列已满");
			return;
		}
		rear++;
		arr[rear] = n;
	}
	
	//获取数据，即出队列
	public int getQueue() {
		if(isEmpty()) {
			throw new RuntimeException("队列为空");
		}
		front++;
		return arr[front];
	}
	
	//获取队首元素，不出队列
	public int peek() {
		if(isEmpty()) {
			throw new RuntimeException("队列为空");
		}
		return arr[front+1];
	}
	
	//打印队列全部数据
	public void getData() {
		if(isEmpty()) {
			System.out.println("队列为空");
			return;
		}
		for (int i = front+1; i <= rear; i++) {
			System.out.print(arr[i]+"\t");
		}
	}
}

  • 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

问题分析并优化

目前数组使用一次就不能用了，没有达到复用的效果
使用算法，改进成一个环形的队列
尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意 **(rear + 1) % maxSize == front [满]****rear == front [空]**

优化后的代码

class CircleArrayQueue {

	private int maxSize; // 最大容量
	private int front; // 队首
	private int rear; // 队尾
	private int[] arr; // 存放数据

	public CircleArrayQueue(int maxSize) {
		this.maxSize = maxSize + 1; // 即将队列容量空出一个作为约定
		/*
		 * this.front = 0; //指向队列头部的位置 this.rear = 0; //指向队列尾部的后一个位置
		 */
		arr = new int[this.maxSize];
	}

	// 判断队列是否为空
	public boolean isEmpty() {
		return front == rear;
	}

	// 判断队列是否已满
	public boolean isFull() {
		return (rear + 1) % maxSize == front;
	}

	// 添加数据，即入队列
	public void addQueue(int n) {
		if (isFull()) {
			System.out.println("队列已满");
			return;
		}
		arr[rear] = n;
		rear = (rear + 1) % maxSize;
	}

	// 获取数据，即出队列
	public int getQueue() {
		if (isEmpty()) {
			throw new RuntimeException("队列为空");
		}
		int res = arr[front];
		front = (front + 1) % maxSize;
		return res;
	}

	// 获取队首元素，不出队列
	public int peek() {
		if (isEmpty()) {
			throw new RuntimeException("队列为空");
		}
		return arr[front];
	}

	// 打印队列全部数据
	public void getData() {
		if (isEmpty()) {
			System.out.println("队列为空");
			return;
		}
		for (int i = front; i < front + size(); i++) {
			System.out.print(arr[i%maxSize] + "\t");
		}
		System.out.println();
	}

	// 获取有效数据的个数
	public int size() {
		return (rear + maxSize - 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
  • 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

3.链表

3.1链表介绍

链表是以节点的方式来存储,是链式存储
每个节点包含 data 域， next 域：指向下一个节点.
如图：发现链表的各个节点不一定是连续存储.
链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

3.2 单链表应用

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

class SingleLinkedList{
	/**
	* head节点不能动
	*/
	private HeroNode head = new HeroNode(0,"","");
	
	/**
	 * 	不按顺序添加，添加到尾部
	 */
	public void add(HeroNode heroNode) {
		
		HeroNode temp = head;
		
		while(temp.next != null) {
			temp = temp.next;
		}
		temp.next = heroNode;
	}
	
	/**
	 * 	添加时，按照排名插入到指定位置
	 */
	public void addByOrder(HeroNode heroNode) {
		
		HeroNode temp = head;
		boolean flag = false; //标识该排名的英雄是否存在
		
		while(true) {
			if(temp.next == null) {
				break;
			}
			if(temp.next.id > heroNode.id ) {
				break;
			}else if(temp.next.id == heroNode.id) {
				flag = true;
				break;
			}
			
			temp = temp.next;
		}
		
		if(flag == true) {
			System.out.println("该排名的英雄已存在");
		}else {
			heroNode.next = temp.next;
			temp.next = heroNode;
		}
	}
	
	/**
	 * 根据id修改节点，id不能变
	 */
	public void update(HeroNode heroNode) {
		
		if(head.next == null) {
			System.out.println("链表为空，不能修改");
			return;
		}
		
		HeroNode temp = head.next;
		boolean flag = false;
		while(true) {
			if(temp == null) {
				break;
			}
			if(heroNode.id == temp.id) {
				flag = true;
				break;
			}
			temp = temp.next;
		}
		
		if(flag == false) {
			System.out.println("没有该节点，无法修改");
		}else {
			temp.name = heroNode.name;
			temp.nickName = heroNode.nickName;
		}
	}
	
	/**
	 * 	删除节点
	 * 
	 * 	利用辅助节点找到待删除节点的前一个节点，temp.next = temp.next.next;
	 */
	public void del(int id) {
		
		if(head.next == null) {
			System.out.println("链表为空，找不到节点");
			return;
		}
		
		HeroNode temp = head.next;
		boolean flag = false;
		while(true) {
			if(temp.next == null)
				break;
			if(temp.next.id == id) {
				flag = true;
				break;
			}
			temp = temp.next;
		}
		
		if(flag) {
			temp.next = temp.next.next;
		}else {
			System.out.println("链表中没有该节点");
		}
		
	}
	
	
	public void list() {
		HeroNode temp = head.next;
		while(true) {
			if(temp == null) {
				break;
			}
			System.out.println(temp);
			temp = temp.next;
		}
	}
}

class HeroNode{
	
	public int id;
	public String name;
	public String nickName;
	public HeroNode next;
	
	public HeroNode(int id, String name, String nickName) {
		super();
		this.id = id;
		this.name = name;
		this.nickName = nickName;
	}

	@Override
	public String toString() {
		return "HeroNode [hid=" + id + ", name=" + name + ", nickName=" + nickName + "]";
	}

  • 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

3.3 单链表常见面试题

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

	/**
	 * @param head:头节点
	 * @return 有效节点的个数，如果是包含头节点的链表，不统计头节点
	 */
	public static int getLength(HeroNode head) {
		if(head.next == null) {
			return 0;
		}
		
		HeroNode temp = head.next;
		int length = 0;
		while(temp != null) {
			length++;
			temp = temp.next;
		}
		return length;
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

3.3.2 查找单链表中的倒数第k个结点 【新浪面试题】

类似于：牛客网剑指offer – 链表中倒数第k个节点（不含头节点）
本题的链表包含头节点

	/**
	 * @param head:头节点
	 * @param index：倒数第index个节点
	 * @return
	 * 
	 * 	利用快慢两个指针，快指针先走k步，满指针再走，快指针到末尾，慢指针刚好到倒数第k个节点
	 */
	public static HeroNode FindKthToTail(HeroNode head ,int index) {
		if(head.next == null || index < 0) {
			return null;
		}
		HeroNode fast,slow;
		fast = slow = head;
		int count = 0;
		while(fast != null) {
			if(count >= index) {
				slow = slow.next;
			}
			fast = fast.next;
			count++;
		}
		return count<index ? null : slow;
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23

3.3.3 单链表的反转【腾讯面试题】

类似于：牛客网剑指offer – 反转链表（不含头节点）
本题的链表包含头节点

	/**
	 * 反转链表
	 */
	public static HeroNode ReverseList(HeroNode head) {
		if(head.next == null || head.next.next == null) {
			return head;
		}
		HeroNode cur = head.next;//当前节点
		HeroNode next = null;
		HeroNode reverseHead = new HeroNode(0,"","");
		while(cur != null) {
			next = cur.next;//1.用于保存当前节点的下一个节点
			cur.next = reverseHead.next;//2.当前节点的next指向反转链表的next
			reverseHead.next = cur;//3.反转链表的next指向当前链表，2，3两步是为了每次把当前节点放在反转链表的头节点后
			cur = next;//4.当前节点向后移
		}
		head.next = reverseHead.next;//将反转链表除头节点以外移给原头节点
		return head;
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

3.3.4 从尾到头打印单链表 【百度面试题】

牛客网剑指offer – 反转链表（不含头节点）
反转链表，再打印，但会破坏原来结构
可以利用Stack类(栈)先入后出的特性

	/**
	 * 倒序打印链表，不打印头节点
	 */
	public static void printFromTailToHead(HeroNode head) {
		if(head.next == null) {
			System.out.println("链表为空");
			return;
		}
		Stack<HeroNode> stack = new Stack<>();
		HeroNode temp = head.next;
		while(temp != null) {
			stack.push(temp);
			temp = temp.next;
		}
		while(!stack.empty()) {
			System.out.println(stack.pop());
		}
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

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

牛客网剑指offer – 合并两个排序的链表

3.4 双向链表应用实例

使用带head头的双向链表实现 –水浒英雄排行榜
管理单向链表的缺点分析:
单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找。
单向链表不能自我删除，需要靠辅助节点 ，而双向链表，则可以自我删除，所以前面我们单链表删除节点时，总是找到temp,temp是待删除节点的前一个节点

//创建双向链表类
class DoubleLinkedList{
	
	public HeroNode2 head = new HeroNode2(0,"","");
	
	/**
	 * 默认添加到链表尾部,与单链表相同
	 */
	public void add(HeroNode2 heroNode) {
		//参考单链表add()
	}
	
	//按顺序插入
	public void addByOrder(HeroNode2 heroNode) {
		HeroNode2 temp = head;
		boolean flag = true;
		while(temp.next != null) {

			if(temp.next.id == heroNode.id) {
				flag = false;
				break;
			}
			if(temp.next.id > heroNode.id) {
				break;
			}
			temp = temp.next;
		}
		if(flag) {
			HeroNode2 next = temp.next;
			temp.next = heroNode;
			heroNode.pre = temp;
			heroNode.next = next;
		}else {
			System.out.println("该排名的英雄已存在");
		}
	}
	
	//修改节点
	public void update(HeroNode2 heroNode) {
		//参考单链表update()
	}
	
	//删除节点
	public void del(int id) {
		if(head.next == null) {
			System.out.println("链表为空");
			return;
		}
		HeroNode2 temp = head.next;
		boolean flag = false;
		while(temp != null) {
			if(temp.id == id) {
				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 HeroNode2 getHead() {
		return head;
	}
	
	public void list() {
		//参考单链表list()
	}
	
}

class HeroNode2{
	//参考单链表的节点类，只是多了一个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

3.5 单项环形链表应用实例

环形链表

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

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

//创建环形链表类
class CircleLinkedList{
	
	private Man first = null;		//代表第一个节点
	
	/**
	 * 创建指定人数的单向环形链表
	 */
	public void addMan(int nums) {
		if(nums < 1) {
			System.out.println("人数不合法");
			return;
		}
		
		Man curMan = null;		//代表当前节点
		for (int i = 1; i <= nums; i++) {
			Man man = new Man(i);
			if(i == 1) {		//先创建一个节点，然后让first指向它，并形成环
				first = man;
				first.setNext(first);
				curMan = first;
			}else {				//每创建一个节点，就把该节点加入到环形链表中
				curMan.setNext(man);
				man.setNext(first);
				curMan = man;
			}
			
		}
	}
	
	/**
	 * 计算约瑟夫问题的出圈序列
	 * @param starN 从第几个开始
	 * @param countN 一次数几个
	 * @param nums 总的人数
	 * @return
	 */
	public List<Integer> getJosephu(int starN, int countN ,int nums) {
		if( first == null || starN < 1 || starN > nums ) {
			throw new RuntimeException("输入的数据不合法"); 
		}
		List<Integer> res = new ArrayList<>();
		Man helper = first;    //创建一个辅助指针，用于指向最后一个节点
		
		//遍历链表，让helper指向最后一个节点
		while(helper.getNext() != first) {
			helper = helper.getNext();
		}
		
		//先让first和helper向前移动 starN - 1 个位置 ,表示从第starN个开始
		for (int i = 0; i < starN-1; i++) {
			first = first.getNext();
			helper = helper.getNext();
		}
		
		//开始循环，当链表中只剩下一个节点时退出循环
		while(helper != first) {
			//让first和helper向前移动 countN - 1，表示一次走countN个位置
			for (int i = 0; i < countN-1; i++) {
				first = first.getNext();
				helper = helper.getNext();
			}
			res.add(first.getId()); //此时first的位置就是出圈的位置
			//接下来从环形链表中移除first位置的节点，代表出圈
			first = first.getNext();
			helper.setNext(first);
		}
		res.add(first.getId());  //将最后一个节点加入出圈序列
		return res;
	}
	
	/**
	 * 遍历链表
	 */
	public void showMan() {
		if(first == null) {
			System.out.println("该链表为空");
			return;
		}
		
		Man curMan = first;
		while(true){ 
			System.out.print(curMan.getId() + "\t");
			if(curMan.getNext() == first) {
				break;
			}
			curMan = curMan.getNext();
		}
	}
	
}

class Man{
	private int id;
	private Man next;
	
	public Man(int id) {
		super();
		this.id = id;
	}
	public int getId() {
		return id;
	}
	public void setId(int id) {
		this.id = id;
	}
	public Man getNext() {
		return next;
	}
	public void setNext(Man next) {
		this.next = next;
	}
	
}

  • 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

4 栈

4.1 栈的实际应用

计算器

请问: 计算机底层是如何运算得到结果的？计算机怎么理解这个算式的(对计算机而言，它接收到的就是一个字符串)

4.2 栈的介绍

  1. 栈是一个先入后出(FILO-First In Last Out)的有序列表。
  2. 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
  3. 根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除

4.3 栈的应用场景

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

4.4 快速入门

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

class ArrayStack{
	
	private int maxSize;   //栈的最大容量
	private int top = -1;  //栈顶，默认为-1
	private int[] arr;		//用来模拟栈的数组
	public ArrayStack(int maxSize) {
		super();
		this.maxSize = maxSize;
		arr = new int[maxSize];
	}
	
	public boolean isEmpty() {
		return top == -1;
	}
	
	public boolean isFull() {
		return top == maxSize-1;
	}
	
	//模拟入栈
	public void push(int nums) {
		
		if(isFull()) {
			System.out.println("栈已满");
			return;
		}
		top++;
		arr[top] = nums;
	}
	
	//模拟出栈
	public int pop() {
		
		if(isEmpty()) {
			throw new RuntimeException("栈为空");
		}
		int result = arr[top];
		top--;
		return result;
	}
	
	//遍历栈中元素，从栈顶开始遍历
	public void list() {
		
		if(isEmpty()) {
			System.out.println("栈为空");
			return;
		}
		for (int i = top; i >= 0; i--) {
			System.out.print(arr[i]+"\t");
		}
	}
}

  • 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

4.5 栈实现综合计算器（中缀表达式）

先只实现 + ，- ，* ，/

public class Calculator {

	public static void main(String[] args) {
		String expression = "78-9-8+3*5-111";

		ArrayStack2 numStack = new ArrayStack2(10); // 创建数栈
		ArrayStack2 operStack = new ArrayStack2(10); // 创建运算符栈

		int index = 0; // 用于扫描表达式
		int num1 = 0;
		int num2 = 0;
		int oper = 0; // 运算符
		String keepNum = ""; // 用于拼接多位数
		char c = ' '; // 从表达式取出的字符
		int res = 0;

		// 扫描运算符，存到栈中
		while (index < expression.length()) {
			c = expression.substring(index, index + 1).charAt(0);
			if (operStack.isOperator(c)) { // 如果字符c是运算符
				if (operStack.isEmpty()) { // 如果运算符栈为空，直接入栈
					operStack.push(c);
				} else {
					while (!operStack.isEmpty() && operStack.priority(c) <= operStack.priority(operStack.peek())) {
						// 如果当前运算符优先级 < 栈顶运算符优先级，取出数栈两个数字和运算符栈顶运算符进行计算，再把运算结果和当前运算符进栈
						num1 = numStack.pop();
						num2 = numStack.pop();
						oper = operStack.pop();
						res = numStack.calculate(num1, num2, oper);
						numStack.push(res);
					}
					// 否则，运算符直接进栈
					operStack.push(c);

				}

			} else {
				// numStack.push(c - 48); //如果为数进数栈，将asc编码转为数值
				// 如果为多位数,需要向index后再看几位，遇到符号再入栈
				keepNum += c;	//拼接相邻的字符
				if (index == expression.length() - 1) { // 如果index是表达式最后一位，直接入栈
					numStack.push(Integer.parseInt(keepNum));
				} else {
					
					//判断index的下一位是否是运算符，是就入栈字符串
					if(operStack.isOperator(expression.substring(index+1, index + 2).charAt(0))) {
						numStack.push(Integer.parseInt(keepNum));
						keepNum = "";		//记得清空keepNum,否则下次会继续拼接
					}
				}
			}
			index++;
		}

		// 表达式扫描完毕，顺序的从数栈和符号栈中pop出数和运算符进行运算
		while (!operStack.isEmpty()) {
			num1 = numStack.pop();
			num2 = numStack.pop();
			oper = operStack.pop();
			res = numStack.calculate(num1, num2, oper);
			numStack.push(res);
		}

		res = numStack.pop(); // 数栈中最后一个数为运算结果
		System.out.println("运算结果为：" + res);
	}

}

class ArrayStack2 {

	//与上节数组实现栈ArrayStack类相同，多了priority()，isOperator()，calculate()以及peek()方法

	// 判断运算符的优先级
	public int priority(int c) {
		if (c == '*' || c == '/') {
			return 1;
		} else if (c == '+' || c == '-') {
			return 0;
		} else {
			return -1;
		}
	}

	// 判断是否是运算符
	public boolean isOperator(int c) {
		return c == '+' || c == '-' || c == '*' || c == '/';
	}

	public int calculate(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 = num1 / num2;
			break;
		default:
			break;
		}
		return res;
	}

	// 查看栈顶元素
	public int peek() {
		return arr[top];
	}
}


  • 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

4.6 逆波兰表达式

4.6.1 前缀表达式（波兰表达式）

前缀表达式的运算符位于操作数之前
举例说明： (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6

前缀表达式的计算机求值

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

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

  1. 从右至左扫描，将6、5、4、3压入堆栈 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈
  2. 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈 最后是-运算符，计算出35-6的值，即29，由此得出最终结果

4.6.2 中缀表达式

中缀表达式就是常见的运算表达式，如(3+4)×5-6

中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作(前面我们讲的案例就能看的这个问题)，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.)

4.6.3 后缀表达式（逆波兰表达式）

后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后
举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –

后缀表达式的计算机求值

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果

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

  1. 从左至右扫描，将3和4压入栈； 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
  2. 将5入栈； 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈； 将6入栈；
  3. 最后是-运算符，计算出35-6的值，即29，由此得出最终结果

4.7 中缀表达式转换为后缀表达式

后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将 中缀表达式转成后缀表达式。

具体步骤如下:

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

举例说明:
将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下
中缀转后缀

代码实现：见下节

4.8 逆波兰表达式完整版

我们完成一个逆波兰计算器，要求完成如下任务:

输入一个逆波兰表达式(后缀表达式)，使用栈(Stack),
计算其结果。支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，只支持对整数的计算

/**
 * 	逆波兰计算器
 */
public class PolandNotation {

	public static void main(String[] args) {
		
		String infixExp = "18+((2+3)*4)-5/2";	// 中缀表达式
		List<String> infixList = infixToList(infixExp);
		
		List<String> suffixExp = infixToSuffix(infixList);
		System.out.println(suffixExp);
		int result = calculate(suffixExp);
		System.out.println("运算结果为："+result);
	}

	//静态内部类，用于访问运算符的优先级
	static 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 getVal(String oper) {
			int res = 0;
			switch (oper) {
			case "+":
				res = ADD;
				break;
			case "-":
				res = SUB;
				break;
			case "*":
				res = MUL;
				break;
			case "/":
				res = DIV;
				break;
				
			default:
				break;
			}
			return res;
		}
	}
	
	//中缀表达式转后缀表达式
	public static List<String> infixToSuffix(List<String> infixList){
		
		Stack<String> s1 = new Stack<String>();//存放运算符
		//Stack<String> s2 = new Stack<String>();//存放中间结果
		//s2在转换过程中没有pop操作，结束后还要逆序输出，所以我们直接用List
		List<String> s2 = new ArrayList<>();
		
		for (String str : infixList) {
			if(str.matches("\\d+")) {	//遇到操作数时，将其压s2
				s2.add(str);
			}else if(str.equals("(")) {
				s1.push(str);
			}else if(str.equals(")")) {
				//如果遇到右括号，则依次弹出s1栈顶的运算符，并压入s2
				while(!s1.peek().equals("(")) {
					s2.add(s1.pop());
				}
				s1.pop(); //消除(
			}else {
				//遇到运算符时，比较其与s1栈顶运算符的优先级
				//若优先级没有栈顶运算符的高，将s1栈顶的运算符弹出并压入到s2中，再次转到与s1中新的栈顶运算符相比较；
				while(!s1.empty() && Operation.getVal(str) <= Operation.getVal(s1.peek())) {
					s2.add(s1.pop());
				}
				// 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；若优先级比栈顶运算符的高，也将运算符压入s1；
				s1.push(str);
			}
		}
		
		//将s1中剩余元素存入s2
		while(!s1.empty()) {
			s2.add(s1.pop());
		}
		
		return s2;
	}
	
	/**
	 * 	中缀表达式转为List
	 */
	public static List<String> infixToList(String infixExp) {
		List<String> list = new ArrayList<>();
		int index = 0; //扫描字符串的索引
		String str; //用于拼接多位数
		char c; //获取字符
		
		do {
			if((c=infixExp.charAt(index)) < 48 || (c=infixExp.charAt(index)) > 57) {	//如果c是一个非数字
				list.add(c+"");
				index++;
			}else {		//如果c是一个数字，考虑多位数
				str = "";	//先将str置为空串
				while(index < infixExp.length() && (c=infixExp.charAt(index)) > 48 && (c=infixExp.charAt(index)) < 57) {
					str += c;
					index++;
				}
				list.add(str);
			}
		}while(index < infixExp.length());
		
		return list;
	}
	
	//完成对逆波兰表达式的运算
	public static int calculate(List<String> list) {
		
		Stack<String> stack = new Stack<String>();
		for (String str : list) {
			//使用正则表达式匹配多位整数
			if(str.matches("\\d+")) {
				stack.push(str);
			}else {
				int num2 = Integer.parseInt(stack.pop());
				int num1 = Integer.parseInt(stack.pop());
				int res = calculate(num1 ,num2 , str);
				stack.push(res+"");
			}
		}
		
		return Integer.parseInt(stack.pop());
	}
	
	//重载的方法，用于求值
	public static int calculate(int num1 ,int num2 ,String oper) {
		int res = 0;
		switch (oper) {
		case "+":
			res = num1 + num2 ;
			break;
		case "-":
			res = num1 - num2 ;
			break;
		case "*":
			res = num1 * num2 ;
			break;
		case "/":
			res = num1 / num2 ;
			break;
		default:
			break;
		}
		return res;
	}
}

  • 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
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/620260
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号