1 稀疏数组
1.1 功能：
当一个数组中大部分元素为０，或者为同一个值的数组时，可以使用稀疏数组来保存该数组。
1.2 流程：
- 记录数组一共有几行几列，有多少个不同的值。
- 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模。
如图，把一个11*11的二维数组变为了一个3X3的稀疏数组。其中
- 第一行保存的是原二维数组的行、列值以及非0值的个数；
- 第二行和第三行保存的是每个非0值所在的位置及其数值。
1.3 转换思路：
1）二维数组转稀疏数组：
- 遍历二维数组，得到二维数组中有效值的个数sum
- 创建稀疏数组，有sum+1行，3列（固定），如
sparseArr=int[sum+1][sum] - 将二维数组中的有效值存入稀疏数组中
2）稀疏数组转二维数组
- 稀疏数组的第一行（原二维数组的行列信息），创建原始二维数组
- 读取稀疏数组的其他行，将值赋给二维数组的对应位置上的数
1.4 代码实现（转换+读档存档）
package com.datastructure.sparsearray;
import java.io.*;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;
public class SparsArraySave {
public static void main(String[] args) throws Exception {
//创建一个原始的二维数组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();
}
//将二维数组转化成稀疏数组
//1.先遍历二维数组，得到非零数据的个数
int sum=0;
for (int i = 0; i < chessArr1.length; i++) {
for (int j = 0; j < chessArr1[i].length; j++) {
if (chessArr1[i][j]!=0){
sum++;
}
}
}
//2.创建稀疏数组
int[][] sparsArr = new int[sum+1][3];
//给稀疏数组赋值
sparsArr[0][0] = chessArr1.length;
sparsArr[0][1] = chessArr1[0].length;
sparsArr[0][2] = sum;
//遍历二维数组，将非零的值放入稀疏数组
int count = 0; //用于记录是第几个非零值
for (int i = 0; i < chessArr1.length; i++) {
for (int j = 0; j < chessArr1[i].length; j++) {
if (chessArr1[i][j] != 0) {
count++;
sparsArr[count][0] = i;
sparsArr[count][1] = j;
sparsArr[count][2] = chessArr1[i][j];
}
}
}
//存档读档方式一：对象流
//3.存档稀疏数组
System.out.println("存档：");
FileOutputStream fos = new FileOutputStream("map.data");
BufferedOutputStream bos = new BufferedOutputStream(fos);
for (int i = 0; i < sparsArr.length; i++) {
for (int j = 0; j < sparsArr[i].length; j++) {
bos.write( (sparsArr[i][j]+"\t").getBytes());
}
bos.write("\r\n".getBytes());
}
bos.close();
fos.close();
//4.读档稀疏数组
List<String> list = new ArrayList<String>();
FileReader fr = new FileReader("map.data");
BufferedReader br = new BufferedReader(fr);
String line;
while ((line=br.readLine())!=null){
list.add(line);
}
int[][] readedArr = new int[list.size()][3];
for (int i =0; i<list.size();i++){
String[] arr = list.get(i).split("\t");
readedArr[i][0] = Integer.parseInt(arr[0]);
readedArr[i][1] = Integer.parseInt(arr[1]);
readedArr[i][2] = Integer.parseInt(arr[2]);
}
br.close();
fr.close();
// //存档读档方式二：对象流
// //3.使用对象流存档稀疏数组（序列化）
// FileOutputStream fos = new FileOutputStream("map2.data");
// ObjectOutputStream oos = new ObjectOutputStream(fos);
// oos.writeObject(sparsArr);
// oos.close();
// //3.使用对象流读档稀疏数组（反序列化）
// FileInputStream fis = new FileInputStream("map2.data");
// ObjectInputStream ois = new ObjectInputStream(fis);
// int[][] readedArr = (int[][]) ois.readObject();
// ois.close();
//5.打印稀疏数组
System.out.println("读取数组为：");
for (int i = 0; i < sparsArr.length; i++) {
System.out.println(readedArr[i][0]+"\t"+readedArr[i][1]+"\t"+readedArr[i][2]);
}
}
}
2 队列
2.1 定义：
- 队列是一个有序列表，可以用数组或者是链表来实现。
- 先入先出：先存入队列的数据，要先取出。后存入的要后取出。
2.2 数组模拟队列：
- 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量
- 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变
2.3 数组模拟队列思路：
将数据存入队列时称为”addQueue”，addQueue 有两个步骤：
- 将尾指针往后移：rear+1 , 当 front == rear 时，队列为空。
- 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。rear == maxSize - 1时，队列满。front指向的是队列首元素的前一个位置。
1) 代码实现
package com.datastructure.queue;
import java.util.Scanner;
public class ArrQueueDemo {
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 val = scanner.nextInt();
arrayQueue.addQueue(val);
break;
case 'g':
try {
int res = arrayQueue.getQueue();
System.out.printf("取出的数据是%d\n",res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int res = arrayQueue.headQueue();
System.out.printf("队列头是%d\n",res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e':
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出！");
}
}
//使用数组模拟队列————编写一个ArrayQueue类
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; //指向队列头部，指向队列头的前一个位置
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++;
arr[rear] = n;
}
//获取队列的数据，出队
public int getQueue(){
if (isEmpty()){
//通过抛出异常来处理
throw new RuntimeException("队列空，不能取数据");
}
front++;
return arr[front];
}
//显示队列的所有数据
public void showQueue(){
//遍历
if (isEmpty()){
System.out.println("队列是空的");
}
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d]=%d\n",i,arr[i]);
}
}
//显示队列的头数据，不是取数据
public int headQueue(){
if (isEmpty()){
System.out.println("队列是空的");
throw new RuntimeException("队列是空的");
}
return arr[front+1];
}
}
2) 分析并优化
- 目前数组使用一次就不能用了，没有达到复用的效果
- 对该数组使用算法，将其改进成环形队列。
2.5 数组模拟环形队列思路
- front变量指向队首元素，初值为0
- rear变量指向队尾元素的下一个元素，初值为0。规定空出一个位置
- 队列为空的判定条件：front == rear
- 队列为满的判定条件：(rear + 1) % maxSize == front
- 队列中有效元素的个数：(rear - front + maxSize) % maxSize
- 入队和出队时，都需要让标记对maxSize取模
1) 代码实现
package com.datastructure.queue;
import java.util.Scanner;
public class CircleArrQueue {
public static void main(String[] args) {
//测试
//创建一个环形队列
CircleArrayQueue arrayQueue = new CircleArrayQueue(4); //有效数据最大是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 val = scanner.nextInt();
arrayQueue.addQueue(val);
break;
case 'g':
try {
int res = arrayQueue.getQueue();
System.out.printf("取出的数据是%d\n",res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int res = arrayQueue.headQueue();
System.out.printf("队列头是%d\n",res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e':
scanner.close();
loop = false;
break;
default:
break;
}
}
System.out.println("程序退出！");
}
}
//使用数组模拟队列————编写一个ArrayQueue类
class CircleArrayQueue{
private int maxSize; //表示数组的最大容量
private int front; //队列头,front变量指向队首元素，初值为0
private int rear; //队列尾,rear变量指向队尾元素的下一个元素，初值为0。规定空出一个位置
private int[] arr; //该数组用于存放数据，模拟队列
public CircleArrayQueue(int arrMaxSize){
maxSize = arrMaxSize;
arr = new int[maxSize];
front=0; //指向队列头部，指向队列头的前一个位置
rear=0; //指向队列尾部，队列最后一个数据
}
//判断队列是否满
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+1)%maxSize;
}
//获取队列的数据，出队
public int getQueue(){
if (isEmpty()){
//通过抛出异常来处理
throw new RuntimeException("队列空，不能取数据");
}
//1.先把front对应的值保存到临时变量中
//2.将front后移，取模
//3.返回临时变量的值
int value = arr[front];
front = (front+1)%maxSize;
return value;
}
//显示队列的所有数据
public void showQueue(){
//遍历
if (isEmpty()){
System.out.println("队列是空的");
}
//从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-front+maxSize)%maxSize;
}
//显示队列的头数据，不是取数据
public int headQueue(){
if (isEmpty()){
System.out.println("队列是空的");
throw new RuntimeException("队列是空的");
}
return arr[front];
}
}
3 链表
3.1 单链表
1）特点
- 链表是以节点的方式来存储,是链式存储
- 每个节点包含 data 域 和 next 域。next域用来指向下一个节点
- 链表的各个节点不一定是连续存储的
- 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
2）实现思路（增删改查）
-
创建（添加）
- 先创建一个Head头节点，表示单链表的头
- 后面我们每添加一个节点，就放在链表的最后
-
遍历
- 通过一个辅助变量，来遍历整个链表
-
新增
- 先遍历链表，找到应该插入的位置
- 要插入的节点的next指向插入位置的后一个节点
- 插入位置的前一个节点的next指向要插入节点
- 插入前要判断是否在队尾插入
-
修改（根据某个属性节点）
- 先遍历节点，找到修改的位置
- 如果未找到修改节点，则不修改
3）代码实现——增删改查
package com.datastructure.linkedlist;
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.addNode(hero1);
// singleLinkedList.addNode(hero2);
// singleLinkedList.addNode(hero3);
// singleLinkedList.addNode(hero4);
//添加(不按顺序)
singleLinkedList.addByOrder(hero2);
singleLinkedList.addByOrder(hero4);
singleLinkedList.addByOrder(hero1);
singleLinkedList.addByOrder(hero3);
//显示
singleLinkedList.list();
//修改
HeroNode newHero = new HeroNode(2,"俊俊","小麒麟");
singleLinkedList.update(newHero);
System.out.println("修改后的链表：");
singleLinkedList.list();
//删除
singleLinkedList.delete(1);
System.out.println("删除后：");
singleLinkedList.list();
}
}
//定义SingleLinkedList管理英雄
class SingleLinkedList{
//初始化一个头节点，头节点不要动
private HeroNode head = new HeroNode(0,"","");
public HeroNode getHead() {
return head;
}
//添加节点到单链表
//思路一（不考虑节点序号）：
//1.找到当前链表的最后节点
//2.将最后这个节点的next指向新的节点
public void addNode(HeroNode node) {
//因为head节点不能动，因此需要一个辅助节点temp
HeroNode temp = head;
//遍历链表，找到最后
while (true){
//找到链表的最后
if (temp.next==null){
break;
}
//如果没有找到，就将temp后移
temp = temp.next;
}
//当退出while循环时，temp就指向了链表的最后
//将最后节点的next指向当前添加的节点
temp.next = node;
}
//思路二（考虑节点序号）：
//1.找到新添加节点的位置，通过辅助变量temp的遍历
//2.将新节点的next指向temp.next
//3.将temp.next=新节点
public void addByOrder(HeroNode heroNode){
//头节点不能动，因此通过辅助变量temp找到要添加的位置
//temp是位于添加位置的前一个结点，否则插入不了
HeroNode temp = head;
boolean flag = 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==true){
System.out.printf("准备插入的英雄编号%d已存在",heroNode.no);
}else {
//插入链表中（temp之后）
heroNode.next = temp.next;
temp.next = heroNode;
}
}
//修改节点的信息,根据编号修改
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 (temp.no == heroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.name = heroNode.name;
temp.nickName = heroNode.nickName;
}else {
System.out.printf("没有找到编号是%d的节点",heroNode.no);
}
}
//删除某一节点
//1.先找到需要删除的这个节点的前一个节点temp,将temp.next.no与待删节点.no进行比较
//2.temp.next.no = temp.next.next.no
//3.被删除的节点不会有其他的引用指向，会被垃圾回收机制回收
public void delete(int no){
HeroNode temp = head;
boolean flag = false;
while (true){
if (temp.next==null){
break;
}
if (temp.next.no==no){
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.next = temp.next.next;
}else {
System.out.printf("未找到编号为%d的节点",no);
}
}
//显示链表【遍历】
public void list(){
if(head.next==null){
System.out.println("链表为空");
return;
}
//因为头节点不能动，新建一个辅助变量来遍历
HeroNode temp = head.next;
while (true){
//判断是否到链表最后
if (temp==null){
break;
}
//输出节点信息
System.out.println(temp.toString());
//将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.no = hNo;
this.name = hName;
this.nickName = hNickName;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}
4）代码实现——单链表反转
public void reverse(HeroNode head){
//如果链表是空，或者只有一个节点，则无需反转，直接返回
if(head.next==null||head.next.next==null){
return;
}
//定义一个辅助变量，遍历链表
HeroNode cur = head.next;
HeroNode next = null; //指向当前节点[cur]的下一个节点
HeroNode reverseHead = new HeroNode(0,null,null);
//遍历原来的链表，每遍历一个节点，将其取出放在新链表的最前端
while (cur!=null){
next = cur.next;
cur.next = reverseHead.next;
reverseHead.next = cur;
cur = next;
}
//将head.next指向reverseHead.next
head.next = reverseHead.next;
}
5）代码实现——逆序打印（Stack）
//反向遍历链表(stack)
public 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;
}
while (stack.size()>0){
System.out.println(stack.pop());
}
}
3.2 双向链表
1）特点
- 新增一个pre指针，用于指向前一个节点。
2）实现思路（增删改查）
-
遍历
- 和单向链表的遍历相同，只是可前可后，需要一个辅助节点来保存当前正在遍历的节点
-
添加
- 双向链表多出了一个pre，所以在添加时，要让新增节点的pre指向链表尾节点
-
修改
- 和单向链表的修改相同
-
删除
- 使用temp来保存要删除的节点
- temp.pre.next指向temp.next
- temp.next.pre指向temp.pre
3）代码实现——增删改查
package com.datastructure.linkedlist;
public class DoubleLinkedListDemo {
public static void main(String[] args) {
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();
doubleLinkedList.addByOrder(hero4);
doubleLinkedList.addByOrder(hero3);
doubleLinkedList.addByOrder(hero1);
doubleLinkedList.addByOrder(hero2);
doubleLinkedList.list();
// System.out.println("删除元素后");
// doubleLinkedList.delete(2);
// doubleLinkedList.list();
// System.out.println("修改元素后");
// HeroNode2 newHero = new HeroNode2(1, "提莫", "迅捷斥候");
// doubleLinkedList.update(newHero);
// doubleLinkedList.list();
}
}
//创建一个双向链表的类
class DoubleLinkedList{
//初始化一个头节点，头节点不要动
private HeroNode2 head = new HeroNode2(0,"","");
public HeroNode2 getHead() {
return head;
}
//显示链表【遍历】
public void list(){
if(head.next==null){
System.out.println("链表为空");
return;
}
//因为头节点不能动，新建一个辅助变量来遍历
HeroNode2 temp = head.next;
while (true){
//判断是否到链表最后
if (temp==null){
break;
}
//输出节点信息
System.out.println(temp.toString());
//将temp后移
temp = temp.next;
}
}
//添加节点到单链表
//思路一（不考虑节点序号）：
//1.找到当前链表的最后节点
//2.将最后这个节点的next指向新的节点
public void add(HeroNode2 node) {
//因为head节点不能动，因此需要一个辅助节点temp
HeroNode2 temp = head;
//遍历链表，找到最后
while (true){
//找到链表的最后
if (temp.next==null){
break;
}
//如果没有找到，就将temp后移
temp = temp.next;
}
//当退出while循环时，temp就指向了链表的最后
//将最后节点的next指向当前添加的节点
temp.next = node;
node.pre = temp;
}
//思路二（考虑节点序号）：
//1.找到新添加节点的位置，通过辅助变量temp的遍历
//2.将新节点的next指向temp.next
//3.temp.next.pre = 新节点
//4.将temp.next=新节点
//5.新节点.pre = temp
public void addByOrder(HeroNode2 heroNode){
//头节点不能动，因此通过辅助变量temp找到要添加的位置
//temp是位于添加位置
HeroNode2 temp = head;
boolean flag = 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.printf("准备插入的英雄编号%d已存在",heroNode.no);
}else {
//插入链表中（temp之后）
if (temp.next != null) {
temp.next.pre = heroNode;
}
heroNode.next = temp.next;
heroNode.pre = temp;
temp.next = heroNode;
}
}
//修改节点的信息,根据编号修改(与单链表的修改一样)
public void update(HeroNode2 heroNode) {
//判断是否为空
if (head.next==null){
System.out.println("表为空");
return;
}
//找到需要修改的节点
//定义一个辅助变量
HeroNode2 temp = head.next;
boolean flag = false; //表示是否找到该节点
while (true){
if(temp==null){
break;
}
if (temp.no == heroNode.no) {
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.name = heroNode.name;
temp.nickName = heroNode.nickName;
}else {
System.out.printf("没有找到编号是%d的节点",heroNode.no);
}
}
//删除
//可以直接找到待删除的节点，单链表是找到待删除的前一节点
public void delete(int no){
if (head.next==null){
System.out.println("链表为空，无法删除");
return;
}
HeroNode2 temp = head.next;
boolean flag = false;
while (true){
if (temp==null){
break;
}
if (temp.no==no){
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.printf("未找到编号为%d的节点",no);
}
}
}
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.no = hNo;
this.name = hName;
this.nickName = hNickName;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}
3.2 环形链表
1）约瑟夫环
-
N个人围成一圈，从第S个人从1开始报数，数到m的那个人出列，他的下一位又从1报数，以此类推。直到所有人出列，由此产生一个出队编号的序列。
例如N=5，M=2，S=1，出队顺序是：2，4，1，5，3
2）实现思路
-
创建
-
先创建第一个节点，让first指向该节点，并形成环形
-
每创建一个新节点，就把该节点加入到环形链表中
-
-
遍历
- 添加辅助变量cur，指向first节点
- 通过while循环遍历该环形链表 ，cur.next==first时结束
3）代码实现
package com.datastructure.linkedlist;
public class Josefhu {
public static void main(String[] args) {
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(6);
circleSingleLinkedList.showBoy();
//小孩出圈
circleSingleLinkedList.countBoy(1,2,5);
}
}
//创建一个环形的单向链表
class CircleSingleLinkedList{
//创建一个first节点
private Boy first = new Boy(-1);
//添加小孩节点，构建成一个环形的链表
public void addBoy(int nums){
//nums 数据校验
if (nums<1){
System.out.println("num值不正确");
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; //让curBoy指向第一个小孩
}else {
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy;
}
}
}
public void showBoy(){
//判断链表是否为空
if (first==null){
System.out.println("链表为空");
return;
}
//first不能动，使用辅助指针完成遍历
Boy curBoy = first;
while (true){
System.out.printf("编号%d先输出\n",curBoy.getNo());
if(curBoy.getNext()==first){//说明已经遍历完毕
break;
}
curBoy = curBoy.getNext();
}
}
//根据用户的输入，计算出小孩出圈的顺序
/**
* @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 (true){
if (helper.getNext()==first){ //说明helper指向最后小孩节点
break;
}
helper = helper.getNext();
}
//报数钱，让first和helper移动k-1次
for (int i = 0; i < startNo - 1; i++) {
first = first.getNext();
helper = helper.getNext();
}
//报数时，让first和helper同时移动m-1次，然后出圈
//循环操作，直到圈中只有一个节点
while (true){
if (helper==first){
break;
}
//让first和helper同时移动countNUm-1
for (int i = 0; i < countNum-1; i++) {
first = first.getNext();
helper = helper.getNext();
}
//first指向的节点，就是要出圈的小孩节点
System.out.printf("编号%d出圈\n", first.getNo());
//将first指向的小孩出圈
first = first.getNext();
helper.setNext(first);
}
System.out.printf("最后留在圈中的小孩编号%d",first.getNo());
}
}
//创建一个Boy类，表示一个节点
class Boy{
private int no;
private Boy next;
public Boy(int no){
this.no = no;
}
public void setNext(Boy next) {
this.next = next;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
@Override
public String toString() {
return "Boy{" +
"no=" + no +
", next=" + next +
'}';
}
}
4 栈
4.1 定义
- 栈是一个先入后出的有序列表
- 栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶，另一端为固定的一端，称为栈底
- 最先放入的元素在栈底，且最后出栈。最后放入的元素在栈顶，且最先出栈
4.2 应用场景
- 子程序递归调用。如JVM中的虚拟机栈
- 表达式转换（中缀转后缀）与求值
- 二叉树的遍历
- 图的深度优先遍历
4.3 用数组模拟栈
1）思路
- 定义top表示栈顶，初始值为-1
- 入栈的操作，先让top++，再放入数组
- 出栈操作，先取出元素，让top–
- top == -1时，栈空
- top == maxSize-1时，栈满
2）代码实现
package com.datastructure.stack;
import java.util.Scanner;
public class ArrayStackDemo {
public static void main(String[] args) {
//测试栈
//先创建一个ArrayStack对象
ArrayStack arrayStack = new ArrayStack(4);
String key = "";
boolean loop = true; //控制是否退出菜单
Scanner scanner = new Scanner(System.in);
while (loop){
System.out.println("show:表示显示栈");
System.out.println("exit:表示退出栈");
System.out.println("pop:表示从栈取出数据（出栈）");
System.out.println("push:表示添加数据到栈（入栈）");
System.out.println("请输入选择：");
key = scanner.next();
switch (key){
case "show":
arrayStack.list();
break;
case "exit":
scanner.close();
loop = false;
break;
case "push":
System.out.println("请输入一个数");
int value = scanner.nextInt();
arrayStack.push(value);
break;
case "pop":
try {
int res = arrayStack.pop();
System.out.printf("出栈的数据是%d\n",res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
default:
break;
}
}
System.out.println("程序退出");
}
}
//栈结构
class ArrayStack{
private int maxSize; //栈的大小
private int[] stack; //数组，数组模拟栈，数据就放在该数组
private int top = -1; //top表示栈顶 初始化为-1
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack =new int[this.maxSize];
}
//栈满
public boolean isFull(){
return top == maxSize-1; //数组索引从0开始
}
//栈空
public boolean idEmpty(){
return top == -1;
}
//入栈
public void push(int value){
//先判断栈满
if (isFull()){
System.out.println("栈满了");
return;
}
top++;
stack[top] = value;
}
//出栈
public int pop(){
//先判断栈空
if (idEmpty()){
// System.out.println("栈为空");
// 抛出异常
throw new RuntimeException("栈空");
}
int value = stack[top];
top--;
return value;
}
//显示栈的情况（遍历栈），遍历时，需要从栈顶显示数据
public void list(){
if (idEmpty()){
System.out.println("栈空");
return;
}
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d",i,stack[i]);
}
}
}
4.4 表达式求值
1）思路
- 准备一个索引index，遍历表达式
- 如果index位置上的元素是一个数字，就直接入栈
- 如果index位置上的元素是一个符号
- 如果符号栈为空，直接入栈
- 如果符号栈不为空
- index位置上的符号的优先级小于或等于栈顶符号的优先级，则弹出两个数栈中的元素和符号栈中的一个符号，并且进行计算。将运算结果放入数栈中，依次判断，当符号的优先级大于符号栈栈顶符号的优先级时将当前符号入符号栈（同级运算符实现从左到右运算）。
- 当表达式遍历完，就弹出数栈中的2个数字和符号栈中的1个符号进行运算，并将运行结果入栈
- 最终数栈中只有一个值，这个值便是运算结果
- 注意：
- 读取的是字符，所以存入数字前需要减去0的ASCII码
- 如果数字是多位数，需要一直读，读到下一位不是数字为止，然后将读到的字符进行拼接，然后一起压入数栈
2）代码实现
package com.datastructure.stack;
public class Calculator {
public static void main(String[] args) {
String expression = "30-2*6-2";
//创建两个栈：数字栈，字符栈
ArrayStack2 numStack = new ArrayStack2(10);
ArrayStack2 operStack = new ArrayStack2(10);
//定义需要的相关变量
int index = 0; //扫描表达式
int num1 = 0;
int num2 = 0;
int oper = 0;
int res = 0;
char ch = ' '; //将每次扫描得到的char保存到ch
String keepNum = ""; //用于拼接多位数
//循环扫描expression
while (true) {
//依次得到循环扫描expression的每一个字符
ch = expression.substring(index, index + 1).charAt(0);
//判断ch是什么，再作相应处理
if (operStack.isOper(ch)) { //如果是运算符
//判断当前的符号栈是否为空
//index位置上的符号的优先级小于或等于栈顶符号的优先级，则弹出两个数栈中的元素和符号栈中的一个符号，并且进行计算。
//将运算结果放入数栈中
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);
}
//将index位置上的符号压入符号栈
operStack.push(ch);
} else { //如果是数字，直接入栈
//numStack.push(ch-48); //'1'->1
//分析思路：
//1.当处理多位数时，不能发现时一个数就立即入栈，因为可能是多位数
//2.在处理数时，需要向expression的index位置后面继续判断
//3.需要定义一个变量字符串，用于拼接
//处理多位数
keepNum += ch;
//如果ch是expression的最后一位，就直接入栈
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 = "";
}
}
}
//让index++ 并判断是否扫描到末尾
index++;
if (index >= expression.length()) {
break;
}
}
//当表达式遍历完，就弹出数栈中的2个数字和符号栈中的1个符号进行运算，并将运行结果入栈
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.printf("表达式%s=%d", expression, numStack.pop());
}
}
//创建一个栈，直接使用上文的数组栈，需要扩展功能
class ArrayStack2 {
private int maxSize; //栈的大小
private int[] stack; //数组，数组模拟栈，数据就放在该数组
private int top = -1; //top表示栈顶 初始化为-1
public ArrayStack2(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
//返回栈顶的值，不是pop
public int peek() {
return stack[top];
}
//栈满
public boolean isFull() {
return top == maxSize - 1; //数组索引从0开始
}
//栈空
public boolean isEmpty() {
return top == -1;
}
//入栈
public void push(int value) {
//先判断栈满
if (isFull()) {
System.out.println("栈满了");
return;
}
top++;
stack[top] = value;
}
//出栈
public int pop() {
//先判断栈空
if (isEmpty()) {
// System.out.println("栈为空");
// 抛出异常
throw new RuntimeException("栈空");
}
int value = stack[top];
top--;
return value;
}
//显示栈的情况（遍历栈），遍历时，需要从栈顶显示数据
public void list() {
if (isEmpty()) {
System.out.println("栈空");
return;
}
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d", i, stack[i]);
}
}
//返回运算符的优先级，优先级是程序员来确定，优先级使用数字表示，数值越大，优先级越高
public int priority(int oper) {
if (oper == '*' || oper == '/') {
return 1;
} else if (oper == '+' || oper == '-') {
return 0;
} else {
return -1; //假定目前的表达式只有加减乘除
}
}
//判断是不是一个运算符
public boolean isOper(char 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;
}
}
4.5 前缀、中缀、后缀表达式
1）前缀表达式
- 又称波兰式，运算符位于操作数之前。
2）前缀表达试的计算机求值
- 从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素和次顶元素），并将结果入栈：重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
- 例如：(3+4)×5-6对应的前缀表达式就是：-×+3456，针对前缀表达式求值步骤如下：
- 从右至左扫描，将6、5、4、3压入堆栈
- 遇到+运算符，因此弹出3和4(3为栈顶元素，4为次顶元素)，计算出3+4的值，得7，再将7入栈
- 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
- 最后是-运算符，计算出35-6的值，即29，由此得出最终结果
2）中缀表达式
- 常见的运算表达式
- 在计算机中，往往会将中缀表达式转成后缀表达式
3）后缀表达式
- 又称逆波兰表达式，运算符位于操作数之后
- (3+4)×5-6的后缀表达式是：34+5*6-
4）后缀表达式的计算机求值
- 从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素和栈顶元素），并将结果入栈：重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
- 例如：(3+4)×5-6对应的后缀表达式就是34+5×6-，针对后缀表达式求值步骤如下：
- 从左至右扫描，将3和4压入堆栈
- 遇到+运算符，因此弹出4和3(4为栈顶元素，3为次顶元素)，计算出3+4的值，得7，再将7入栈
- 将5入栈
- 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈
- 将6入栈
- 最后是-运算符，计算出35-6的值，即29，由此得出最终结果
5）代码实现逆波兰计算器
-
输入一个逆波兰表达式，使用栈(Stack)，计算其结果
-
支持小括号和多位数整数（只支持对整数的计算）
package com.datastructure.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class PolandNotation {
public static void main(String[] args) {
//先定义一个逆波兰表达式
//(3+4)×5-6 ---> 34+5×6-
String surffixExpression = "30 4 + 5 * 6 -";
//1.先将surffixExpression放到arrayList中
//2.将arrayList传递给一个方法，遍历arrayList配合栈完成计算
List<String> list = getListString(surffixExpression);
System.out.println(list);
int res = cal(list);
System.out.println("计算的结果是："+res);
}
//将逆波兰表达式放到arrayList中
public static List<String> getListString(String surffixExpression){
//将surffixExpression分割
String[] split = surffixExpression.split(" ");
List<String> list = new ArrayList<>();
for (String ele : split) {
list.add(ele);
}
return list;
}
//完成对逆波兰表达式的运算
public static int cal(List<String> list){
//创建栈
Stack<String> stack = new Stack<>();
//遍历 list
for (String item : list) {
//使用正则表达式取数
if (item.matches("\\d+")){ //匹配的是多位数
//入栈
stack.push(item);
}else {
//pop出两个数，运算完再入栈
int num2 = Integer.parseInt(stack.pop());
int num1 = Integer.parseInt(stack.pop());
int res = 0;
if (item.equals("+")){
res = num1+num2;
} else if (item.equals("-")) {
res = num1-num2;
} else if (item.equals("*")) {
res = num1*num2;
} else if (item.equals("/")) {
res = num1/num2;
} else {
throw new RuntimeException("运算符有误");
}
stack.push(res+""); //把证书转化成字符串
}
}
//最后留在stack中的数就是运算结果
return Integer.parseInt(stack.pop());
}
}
6）中缀表达式换为后缀表达式
- 初始化两个栈：运算符栈s1和储存中间结果的栈s2
- 从左至右扫描中缀表达式
- 遇到操作数时，将其压s2
- 遇到运算符时，比较其与s1栈顶运算符的优先级：
- 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈
- 否则，若优先级比栈顶运算符的高，也将运算符压入s1
- 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算
符相比较
public class Trans {
static Queue<String> queue = new LinkedList<>();
static Stack<String> stack = new Stack<>();
public static void main(String[] args) {
//中缀表达式，加上空格，方便取出
String infixExpression = "1 + ( ( 2 + 3 ) * 4 ) - 5";
String[] expressionArr = infixExpression.split(" ");
//用来保存该运算符的类型
int type;
//取出的字符串
String element;
//弹出栈的字符串
String stackEle;
for(int i=0; i<expressionArr.length; i++) {
element = expressionArr[i];
type = judgeOperator(element);
if(type == 0) {
//数字，直接入队
queue.add(element);
}else if(type == 1) {
//左括号，直接压栈
stack.push(element);
}else if(type == 3) {
//如果右括号，弹出栈顶元素，直到遇见左括号位置再停下来
do {
stackEle = stack.pop();
if(stackEle.equals("(")) {
break;
}
queue.add(stackEle);
//弹出栈中的左括号
}while (!stackEle.equals("("));
}else if(type == 2) {
if(stack.isEmpty()) {
//如果栈为空，直接入栈
stack.push(element);
continue;
}
int priority1 = getPriority(element);
//获得栈顶元素，并判断其优先级
stackEle = stack.peek();
int priority2 = getPriority(stackEle);
if(priority2 == 0) {
//为左括号，运算符直接入栈
stack.push(element);
}else if(priority1 > priority2) {
//该运算符优先级高于栈顶元素优先级，则入栈
stack.push(element);
}else {
stackEle = stack.pop();
queue.add(stackEle);
//重新判断该运算符
i--;
}
}
}
//把最后一个元素出栈并入队
stackEle = stack.pop();
queue.add(stackEle);
//保存队列长度，因为出队过程中队列的长度会被改变
int length = queue.size();
for(int i=0; i<length; i++) {
element = queue.remove();
System.out.print(element);
}
}
/**
* 判断该运算符是不是加减乘除
* @param operation 运算符
* @return true则该运算符为加减乘除
*/
public static boolean firstJudge(String operation) {
return operation.equals("*") || operation.equals("/") || operation.equals("+") || operation.equals("-");
}
/**
* 判断该字符串的类型
* @param operation 要判断的字符串
* @return 3->右括号 2->加减乘除运算符 1->左括号
*/
public static int judgeOperator(String operation) {
if(operation.equals(")")) {
return 3;
}
if(firstJudge(operation)) {
return 2;
}
if(operation.equals("(")) {
return 1;
} else {
return 0;
}
}
/**
* 判断运算符优先级
* @param operator 要判断的运算符
* @return 2代表乘除，1代表加减，0代表左括号
*/
public static int getPriority(String operator) {
if(operator.equals("*") || operator.equals("/")) {
return 2;
}else if(operator.equals("+") || operator.equals("-")) {
return 1;
} else {
return 0;
}
}
}