网站建设职能绩效目标,超级外链推广,网站广告推广价格,pc网站开发微信支付文章目录第一章#xff1a;数据结构与算法第二章#xff1a;稀疏数组和队列一 、稀疏sparsearray 数组#xff08;一#xff09;案例需求#xff08;二#xff09;稀疏数组介绍#xff08;三#xff09;应用实列#xff08;四#xff09;代码实现二、队列#xff08…
文章目录第一章数据结构与算法第二章稀疏数组和队列一 、稀疏sparsearray 数组一案例需求二稀疏数组介绍三应用实列四代码实现二、队列一数组模拟队列代码实现二数组模拟环形队列第三章链表一、链表一链表介绍单链表的应用实例代码实现修改数据删除节点完整代码二面试题二、双链表一、双向链表的介绍(二) 、应用案例三、单向环形链表应用场景一约瑟夫问题二 代码实现第四章栈一、栈介绍二数组模拟栈的思路分析三练习使用链表来模拟栈版本一双链表实现栈版本二双链表实现栈版本三单链表实现版本四单链表实现 改变测试环境推荐四栈实现综合案例——计算器五栈的三种表达式1、前缀表达式2、后缀表达式六逆波兰计算器**方法一**通过系统提供的栈stack来实现**方法二**编写一个数组栈版本一中缀表达式转为后缀表达式版本二功能完整实现第五章递归一递归介绍二迷宫回溯问题分析与实现三八皇后问题回溯问题1、介绍2、代码实现第六章排序算法一、排序算法二、算法的时间复杂度一算法的评判方法二时间复杂度1、时间频度2 、时间复杂度三平均时间复杂度1、平均时间复杂度2、最坏时间复杂度四空间复杂度——空间换时间三、冒泡排序算法(bubble sorting)一代码实现四、选择排序算法一选举排序介绍二代码实现五、插入排序算法一介绍二代码实现六、希尔排序算法shell一希尔排序算法介绍二代码实现方法一交换法方法二移动法——插入法七、快排算法——Quicksort一快排算法介绍二代码实现八、归并排算法一介绍二代码实现九、基数排序一基础知识二代码实现十、排序总结第一章数据结构与算法
一、数据结构概述
数据结构包括
线性结构数据元素之间存在的一对一的线性关系 两种不同存储结构: 顺序存储结构 使用顺序表顺序表中存储的元素是连续的即存储的位置是连续的链式存储结构使用链式表存储数据不一定是连续的好处利用磁盘的碎片化的空间 常见结构数组、队列、链表和栈 非线性结构数据元素之间不一定是一对一的关系 常用二位数组、多维数组、广义表、树结构、图结构
第二章稀疏数组和队列
一 、稀疏sparsearray 数组
一案例需求
案例五子棋的数据的存盘和继续上次棋盘
主要解决其盘数据的存放问题
如果用二维数组进行连续存储数据会记录很多无意义的数据
解决办法稀疏数组来压缩二维数组 二稀疏数组介绍
稀疏数组适用范围
数组中大部分的元素为0元素为同一个值
稀疏数组处理方法
记录数组一共几列几行、不同值的个数不同的元素的行、列、值记录在稀疏数组中 三应用实列
稀疏数组可以用来保存二维数组eg棋盘、地图等
二维数组转稀疏数组的思路 遍历二维数组得到有效数据的个数 sum 即知道列的个数而行的个数是固定的3 根据sum就可以创建稀疏数组spareseArr int[sum1][3] 将二维数组的有效数据存入到稀疏数组 第一行数据为行个数、列个数、数据个数 稀疏数组的形状[数据个数1,3]
稀疏数组转二维数组的思路
先读取稀疏数组中第一行数据来创建原始的二维数组在读取稀疏数组中后几行的数据并将值赋给二维数组中
四代码实现
创建DataStructures创建package com.lcj.sparseArray,创建类SparseArray package com.lcj.sparseArray;
/*
* 编写时间202208014
* 编写人员lcj
* 编写目的联系稀疏数组
* */
public class SparseAarray {public static void main(String[] args){// 1. 创建11*11的二维数组棋盘// 0 表示没有棋子1表示黑棋2表示蓝棋int chessArr1[][] new int[11][11];chessArr1[1][2] 1;chessArr1[2][3] 2;// 输出原始棋盘的数据for (int[] row:chessArr1){for (int data:row){System.out.printf(%d\t,data);}System.out.println();}
// __________________________________________________________________//(一)二维数组转为稀疏数组// 1.先遍历二维数组得到数据的个数 稀疏数组 形状[个数1,3]int count 0;for(int i 0;i chessArr1.length;i){for (int j0;j chessArr1[1].length;j){if(chessArr1[i][j] ! 0)count;}}System.out.println(数值的个数count);// 2.创建稀疏数组int sparseArray[][] new int[count1][3];// 第一行的数据sparseArray[0][0] chessArr1.length;sparseArray[0][1] chessArr1[1].length;sparseArray[0][2] count;// 3.添加数值int a 0; // 作用统计不为零的数值的个数来确定稀疏数组的行下标for(int i 0;i chessArr1.length;i){for (int j0;j chessArr1[1].length;j){if(chessArr1[i][j] ! 0) {a;sparseArray[a][0] i; // 数据的行sparseArray[a][1] j; // 数据的列sparseArray[a][2] chessArr1[i][j]; // 数据值}}}// 4.输出稀疏数组for (int[] row : sparseArray) {for (int data : row) {System.out.printf(%d\t,data);}System.out.println();}// _____________________________________________________________________//二稀疏数组转换为二维数组// 1.创建二维数组int chessArr2[][] new int[sparseArray[0][0]][sparseArray[0][1]];//2.添加数值到二维数组中for (int i 1 ;i sparseArray.length; i){chessArr2[sparseArray[i][0]][sparseArray[i][1]] sparseArray[i][2];}// 3.输出二维数组for (int[] row : chessArr2) {for (int data : row) {System.out.printf(%d\t,data);}System.out.println();}}
}
课后练习题 在前面的基础上将稀疏数组保存到磁盘中egmap.data 恢复原来的数组时读取map.data进行恢复
二、队列
队列的特点先进先出
实现方法数组和链表
一数组模拟队列 加入数据【addQueue】的思路
将尾指针往后移rear1当frontrear [空]若尾指针rear小于队列的最大值maxsize-1可以将数据存入到队列中如果等于maxsize-1则无法进行存储数据
注意
rear 指向队列中最后一个元素front指向队列中第一个元素中前一个位置
代码实现
创建packagecom.lcj.queue,创建类名ArrayQueueDamon
package com.lcj.queue;import java.util.Scanner;/** 编写时间20220814* 编写人员lcj* 编写目的数组模拟队列* */
public class ArrayQueueDamon {public static void main(String[] args) {// 代码测试//创建对象arrayQueue Queue new arrayQueue(3); //最大值为3char 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:Queue.showQueue();break;case a:System.out.println(请输入一个数据:);int value scanner.nextInt();Queue.addQueue(value);break;case g:try {int res Queue.getQueu();System.out.printf(取出数据%d\n,res);}catch (Exception e){System.out.println(e.getMessage());}break;case h:try {int res Queue.headQueue();System.out.printf(输入数据队列头部数据%d\n,res);}catch (Exception e){System.out.println(e.getMessage());}break;case e:scanner.close(); // 关闭scannerloop false;break;default:break;}}System.out.println(退出成功);}
}// 使用数组来模拟队列
class arrayQueue{private int maxsize; // 最大值private int rear; // 队列的尾指针private int front; // 队列的头指针private int[] arr; // 存放数据// 创建队列的构造器public arrayQueue(int MaxSize){maxsize MaxSize; // 最大值arr new int[maxsize];rear -1; // 指向队列尾部的数据包含尾部数据front -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 getQueu(){// 判断数据是否为空if(isEmpty()){
// System.out.println(队列数据为空);
// return 0;throw new RuntimeException(队列数据为空);}front; //front数据后移return arr[front];}// 显示队列的所有数据public void showQueue(){// 判断队列是否为空if (isEmpty()){
// throw new RuntimeException(队列数据为空不能展示数据);System.out.println(队列数据为空不能展示数据);return;}for (int i front1; irear; i){System.out.printf(arr[%d]%d\n,i,arr[i]);}}//显示队列的头数据注意不是取出数据public int headQueue(){//判断数据是否为空if (isEmpty()){throw new RuntimeException(数据为空);}return arr[front1];}
}
注意需要测试一下代码
问题
当前这种形式的队列数据有问题front往后移动后front前面的数据虽然是无效数据但是想要添加数据是无法再添加数据的这导致资源的浪费了队列不能重复使用没有达到复用的效果
解决办法
环形队列
二数组模拟环形队列 注意
rear 变量的含义发生了变换和数组模拟队列的不一样了现在是指向最后一个元素的后一个位置front 变量的含义也发生了变化指向了队列的第一个元素也就是说arr[front] 的第一个元素位置原来是第一个元素前一个位置。队列满的条件(rear1)%maxsize front队列为空rear front队列中有效个数(rearmaxsize-front)%maxsize
代码实现
创建类CircleArrayQueueDaemon
package com.lcj.queue;import jdk.nashorn.internal.ir.CallNode;import java.util.Scanner;/*
* 编写人lcj
* 编写时间20220815
* 编写目的学习环形队列
* */
public class CircleArrayQueueDaemon {public static void main(String[] args){//测试思考//创建对象CircleArray circleArray new CircleArray(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):队列头部数据);System.out.println(n(num):队列有效数据);key scanner.next().charAt(0);switch (key){case s:System.out.println(展示队列数据);circleArray.showQueue();break;case a:System.out.println(添加数据,请输入数据);int value scanner.nextInt();circleArray.addQueu(value);break;case e:System.out.println(退出程序);loop false; // 跳出循环break;case g:try {System.out.println(获取队列的数据);int num circleArray.getQueue();System.out.println(值num);}catch (Exception e){e.getMessage();}break;case h:System.out.print(获取队列的头部数据:);System.out.println(circleArray.getHead());break;case n:System.out.println(查看队列的有效数据 );int size circleArray.size();System.out.println(有效数据为size);break;default:System.out.println(数据输入有误请重新输入);break;}}System.out.println(程序已经退出成功);}
}
class CircleArray{private int maxsize; // 队列长度private int front; // 队列的头private int rear; // 队列的尾private int[] arr; // 队列的数组// 创建构造器public CircleArray(int maxsize) {this.maxsize maxsize;front 0; // 指向元素第一位置rear 0; // 指向元素的第二个位置即 尾部序号1arr new int[maxsize];}// 判断是否满了public boolean isFull(){return (rear1)%maxsize front;}// 判断是否为空public boolean isEmpty(){return rearfront;}//添加数据会不会添加数据导致覆盖原来的数据public void addQueu(int n){// 判断是否满if(isFull() size()maxsize){System.out.println(队列已满不能添加数据);return;}arr[rear] n;
// rear; // rear往后移动数据 erro:不能实现环形队列rear(rear1)%maxsize;// 注意这里rear1 rear}//取出数据public int getQueue(){//判断数据是否为空if(isEmpty()){throw new RuntimeException(数据为空不能取数);}// 取出数据后front需要往后移动需要一个值来保存数据//方法一int value arr[front];
// front;front (front1)%maxsize; //front1 frontreturn value;//方法二
// front (front1)%maxsize;
// return arr[(front-1)%maxsize];}// 获取数据头部public int getHead(){return arr[front];}// 显示所有的数据public void showQueue(){//判断队列是否为空if(isEmpty()){System.out.println(队列为空);return;}//遍历数据,frontrear-frontmaxsize%maxsizefor (int ifront;i front(rear-frontmaxsize)%maxsize;i){ // (rear-frontmaxsize)%maxsize 有效数据System.out.printf(arr[%d]%d\n,i%maxsize,arr[i%maxsize]);}}// 数据有效个数public int size(){return (rearmaxsize-front)%maxsize;}}
第三章链表
一、链表
一链表介绍
链表是有序的列表
data域数据
next域地址 特点
链表是以节点的方式来存储数据每一个节点包含data域next域 指向下一个节点链表中的数据并不一定是连续存放的链表分为 带头节点的链表 head节点不存放具体的数据没有带头节点的链表
单链表的应用实例
eg单链表来管理水浒传的人物图
实现代头节点的单向链表
代码实现
创建packagelinkedlist创建类SingleLinkedListDemo
要求一添加英雄直接添加到链表的尾部中
package com.lcj.linkedlist;public class SignalLinkedList {public static void main(String[] args) {// 测试数据HeroNode hero1 new HeroNode(1,宋江,及时雨);HeroNode hero2 new HeroNode(2,宋江,及时雨);HeroNode hero3 new HeroNode(3,宋江,及时雨);// 创建链表管理器LinkedManager linkedManager new LinkedManager();// 添加数据linkedManager.add(hero1);linkedManager.add(hero2);linkedManager.add(hero3);// 展示数据linkedManager.list();}}// 管理节点数据
class LinkedManager {//先创建一个头节点数据,但是并不存放数据private HeroNode head new HeroNode(0, , );//添加节点到单链表中,但是数据需要添加到节点中的最后一个数据的Next为Null// 不考虑数据的编号public void add(HeroNode Node) {// 创建一个辅助指针来判断数据是否到达尾部HeroNode tmp head;// 遍历循环while (true) {// 找最后节点数据if (tmp.next null) {break;}// 如果没有找到最后一个节点需要往后移动tmp tmp.next;}// 退出循环的时候就是指向最后节点现在需要添加新的节点tmp.next Node;}// 显示数据遍历数据public void list(){//判断链表是否为空,没有指向其他的节点if(head.next null){System.out.println(链表为空);return;}//头节点不能动需要创建辅助节点遍历数据HeroNode tmp head.next;while(true){//判断是否到达最后if(tmp null){
// System.out.println(最后的);break;}// 数据节点信息System.out.println(tmp);// 将tmp往后移动tmp tmp.next;}}
}
// 创建节点数据
class HeroNode{public int no; // 创建序号public String name;//英雄名字public String nickname; // 昵称public HeroNode next; //指向下一个节点 值为java的引用类似于c语言的指针//创建构造器public HeroNode(int no, String name, String nickname) {this.no no;this.name name;this.nickname nickname;}
// 数据进行格式便于后期数据的展示Overridepublic String toString() {return HeroNode{ no no , name name \ , nickname nickname \ };}
}要求二根据英雄的编号进行数据排序、修改节点值
添加数据 需要按照编号的顺序添加
首先找到新添加的节点位置新的节点数据.next tmp.nexttmp.next 新节点
思路
找到序号前一个位置插入数据
//按照数据序号顺序进行添加数据public void addByOrder(HeroNode node){HeroNode tmp head;// 查找序号位置时tmp要指向插入数据的前一个位置不是能插入数据boolean flag false; // 判断需要的编号是否存在存在就不能添加while(true){if(tmp.next null){//找到数据链尾了break;}if (tmp.next.no node.no){ //判断位置成功就位置在tmp处break;}else if (tmp.next.no node.no){ //说明编号存在flag true;break;}tmp tmp.next;}// 判断flagif(flag){System.out.println(序号存在请重新输入数据);}else{node.next tmp.next; //新节点的后序是tmp的后序tmp.next node; // 旧节点的后序等于新节点}}修改数据
// 修改节点的信息根据no编号来修改即no编号不能改// 根据node的no序号来进行修改public void update(HeroNode node){if(head.next null){System.out.println(链表为空);return;}//找需要修改的序号因此需要进行遍历数据/* 版本一boolean flage true;HeroNode tmp head.next; // 创建临时的引用来遍历数据while (flage){if(tmp null){ //到达链尾break;}if (tmp.no node.no){tmp.name node.name;tmp.nickname node.nickname;break;}else{tmp tmp.next;}}*/// 版本二boolean flage false;HeroNode tmp head.next; // 创建临时的引用来遍历数据while (true){if(tmp null){ //到达链尾break;}if (tmp.no node.no){flage true;break;}else{tmp tmp.next;}}// flage 为true会执行文件if(flage){tmp.name node.name;tmp.nickname node.nickname;}else{System.out.println(该节点数据没有找到);}}
删除节点 找到需要删除点的前一个点 tmptmp.next tmp.next.next被删除的节点将不会有其引用指向会被垃圾回收机制回收
// 删除节点//思路找到需要删除点的前一个点 tmppublic void del(int no){HeroNode tmp head;boolean flag false; // 标志是否找到待删除节点while(true){if(tmp.next null){ // 位置处于数据的链尾break;}if(tmp.next.no no){ //找到待删除节点的前一个节点的tmpflag true;break;}tmp tmp.next; //tmp后移遍历}//判断flagif (flag){tmp.next tmp.next.next;}else{System.out.println(该节点不存在);}}完整代码
完整代码添加数据有序添加、排序添加、修改数据、删除数据、
package com.lcj.linkedlist;public class SignalLinkedList {public static void main(String[] args) {// 测试数据HeroNode hero1 new HeroNode(1,宋江,及时雨);HeroNode hero2 new HeroNode(2,宋江,及时雨);HeroNode hero3 new HeroNode(3,宋江,及时雨);// 创建链表管理器LinkedManager linkedManager new LinkedManager();// 添加数据
// linkedManager.add(hero1);
// linkedManager.add(hero2);
// linkedManager.add(hero3);//顺序添加数据linkedManager.addByOrder(hero3);linkedManager.addByOrder(hero2);linkedManager.addByOrder(hero1);// 展示数据linkedManager.list();System.out.println();// 修改节点数据HeroNode hero4 new HeroNode(3,法外张三,罗翔);linkedManager.update(hero4);linkedManager.list();// 展示数据// 删除节点linkedManager.del(1);System.out.println(删除数据后);linkedManager.list();}
}// 管理节点数据
class LinkedManager {//先创建一个头节点数据,但是并不存放数据private HeroNode head new HeroNode(0, , );//添加节点到单链表中,但是数据需要添加到节点中的最后一个数据的Next为Null// 不考虑数据的编号public void add(HeroNode Node) {// 创建一个辅助指针来判断数据是否到达尾部HeroNode tmp head;// 遍历循环while (true) {// 找最后节点数据if (tmp.next null) {break;}// 如果没有找到最后一个节点需要往后移动tmp tmp.next;}// 退出循环的时候就是指向最后节点现在需要添加新的节点tmp.next Node;}// 修改节点的信息根据no编号来修改即no编号不能改// 根据node的no序号来进行修改public void update(HeroNode node){if(head.next null){System.out.println(链表为空);return;}//找需要修改的序号因此需要进行遍历数据/* 版本一boolean flage true;HeroNode tmp head.next; // 创建临时的引用来遍历数据while (flage){if(tmp null){ //到达链尾break;}if (tmp.no node.no){tmp.name node.name;tmp.nickname node.nickname;break;}else{tmp tmp.next;}}*/// 版本二boolean flage false;HeroNode tmp head.next; // 创建临时的引用来遍历数据while (true){if(tmp null){ //到达链尾break;}if (tmp.no node.no){flage true;break;}else{tmp tmp.next;}}// flage 为true会执行文件if(flage){tmp.name node.name;tmp.nickname node.nickname;}else{System.out.println(该节点数据没有找到);}}//按照数据序号顺序进行添加数据public void addByOrder(HeroNode node){HeroNode tmp head;// 查找序号位置时tmp要指向插入数据的前一个位置不是能插入数据boolean flag false; // 判断需要的编号是否存在存在就不能添加while(true){if(tmp.next null){//找到数据链尾了break;}if (tmp.next.no node.no){ //判断位置成功就位置在tmp处break;}else if (tmp.next.no node.no){ //说明编号存在flag true;break;}tmp tmp.next;}// 判断flagif(flag){System.out.println(序号存在请重新输入数据);}else{node.next tmp.next; //新节点的后序是tmp的后序tmp.next node; // 旧节点的后序等于新节点}}// 删除节点//思路找到需要删除点的前一个点 tmppublic void del(int no){HeroNode tmp head;boolean flag false; // 标志是否找到待删除节点while(true){if(tmp.next null){ // 位置处于数据的链尾break;}if(tmp.next.no no){ //找到待删除节点的前一个节点的tmpflag true;break;}tmp tmp.next; //tmp后移遍历}//判断flagif (flag){tmp.next tmp.next.next;}else{System.out.println(该节点不存在);}}// 显示数据遍历数据public void list(){//判断链表是否为空,没有指向其他的节点if(head.next null){System.out.println(链表为空);return;}//头节点不能动需要创建辅助节点遍历数据HeroNode tmp head.next;while(true){//判断是否到达最后if(tmp null){
// System.out.println(最后的);break;}// 数据节点信息System.out.println(tmp);// 将tmp往后移动tmp tmp.next;}}
}
// 创建节点数据
class HeroNode{public int no; // 创建序号public String name;//英雄名字public String nickname; // 昵称public HeroNode next; //指向下一个节点 值为java的引用类似于c语言的指针//创建构造器public HeroNode(int no, String name, String nickname) {this.no no;this.name name;this.nickname nickname;}
// 数据进行格式便于后期数据的展示Overridepublic String toString() {return HeroNode{ no no , name name \ , nickname nickname \ };}
}二面试题
求单链表中有效节点的个数查找单链表中的倒数第K个节点——新浪面试单链表的反转 ——腾讯面试从尾到头打印单链表——百度要求1反向遍历 2stack栈合并两个有序的单链表合并之后的链表依然有序
题一求单链表中有效节点的个数
注意不要将头节点也统计进去 public void nodeNum(){HeroNode temp head.next;int count0;while(true){//如果到达链尾if(temp null){break;}temp temp.next;count;}System.out.println(节点个数为count);}
题目二查找单链表中的倒数第K个节点——新浪面试
思路 先遍历一下数据统计数据的有效个数有效个数 - k得到需要找的
public void findLastIndex(int k){HeroNode temp head.next;// 统计个数int count0;while(true){//如果到达链尾if(temp null){break;}temp temp.next;count;}// 判断k是否有效if(k count|| k0){System.out.println(超出了链表范围);return;}else{ //读取第k个值的位置int flag count - k;HeroNode temp1 head.next;for(int i0;iflag;i){temp1 temp1.next;}System.out.printf(序号%d \t 名字%s,temp1.no,temp1.name);} }注意if(k count|| k0)我遗漏了k0的问题
题目三单链表的反转 ——腾讯面试 思路头插入数据 新建一个链表用来存储数据将旧链表中的节点数据移动到新节点中新链表指向旧链表的头 public static void reversetList(HeroNode head){//判断链表是否为空,或者只有一个节点的无需反转if (head.next null || head.next.next null){return;}HeroNode tmp head.next;HeroNode next null; //用来指向tmp的下一个节点数据HeroNode reversetHead new HeroNode(0,,); //新链表的头节点数// 遍历链表,将旧链表中的节点数据移动到新节点中while(tmp ! null){next tmp.next ; //用于保存当前节点下一个节点数据tmp.next reversetHead.next;reversetHead.next tmp;tmp next; //往后移动}head.next reversetHead.next;}核心代码 next tmp.next ; //用于保存当前节点下一个节点数据 tmp.next reversetHead.next; reversetHead.next tmp; tmp next; //往后移动
题目四从尾到头打印单链表——百度要求1反向遍历 2stack栈 方法一先将单链表进行反转操作然后再遍历即可但是不建议使用破坏数据的原结构 方法二利用栈将各个节点的数据压入到栈中然后利用栈的先进后出特点 //利用栈将各个节点的数据压入到栈中然后利用栈的先进后出特点public static void reserverPrinter(HeroNode head){if(head.next null){return;}StackHeroNode stack new Stack();HeroNode tmp head.next;//数据入栈while (tmp ! null){ //数据不能为空为空代表到达链尾stack.push(tmp);//stack中添加数据pushtmp tmp.next;}//数据出栈while(stack.size()0){System.out.println(stack.pop()); //pop 将数据弹出}}题目五合并两个有序的单链表合并之后的链表依然有序
二、双链表
一、双向链表的介绍 双向链表添加了pre目的用它来指向节点的前一个节点
双向节点删除数据 可以指向待删除的节点 temp temp.pre.next temp.next temp.next.pre temp.pre
单链表存在的问题
单向链表查找的方向只能是一个方向而双向链表可以向前或者向后查找单向链表不能自我删除需要靠辅助节点而双向链表可以自我删除
(二) 、应用案例
实现英雄的案列
创建类DoubleLinkedListDamon
package com.lcj.linkedlist;public class DoubleLinkedListDaemon {public static void main(String[] args){HeroNode2 hero1 new HeroNode2(1,宋江,及时雨);HeroNode2 hero2 new HeroNode2(8,宋江,及时雨);HeroNode2 hero3 new HeroNode2(3,宋江,及时雨);//创建一个双向链表DoubleLinkedList doubleLinkedList new DoubleLinkedList();doubleLinkedList.add(hero2);doubleLinkedList.add(hero1);doubleLinkedList.add(hero3);//数据展示doubleLinkedList.list();// 数据修改System.out.println(数据修改);HeroNode2 hero4 new HeroNode2(3,张三,及时雨);doubleLinkedList.update(hero4);doubleLinkedList.list();//数据删除System.out.println(数据删除);doubleLinkedList.del(3);doubleLinkedList.list();//添加数据System.out.println(添加数据);HeroNode2 hero5 new HeroNode2(5,lisi,李四);doubleLinkedList.add(hero5);doubleLinkedList.list();}
}
// 管理双向链表
class DoubleLinkedList{private HeroNode2 head new HeroNode2(0,,);// 显示数据遍历数据public void list(){//判断链表是否为空,没有指向其他的节点if(head.next null){System.out.println(链表为空);return;}//头节点不能动需要创建辅助节点遍历数据HeroNode2 tmp head.next;while(true){//判断是否到达最后if(tmp null){
// System.out.println(最后的);break;}// 数据节点信息System.out.println(tmp);// 将tmp往后移动tmp tmp.next;}}//添加数据到链表的末尾//思路找到链表末尾public void add(HeroNode2 Node) {// 创建一个辅助指针来判断数据是否到达尾部HeroNode2 tmp head;// 遍历循环while (true) {// 找最后节点数据if (tmp.next null) {break;}// 如果没有找到最后一个节点需要往后移动tmp tmp.next;}// 退出循环的时候就是指向最后节点现在需要添加新的节点形成双向链tmp.next Node;Node.pre tmp;}//添加数据 要求按照序号进行添加数据public void addByOrder(HeroNode2 node){HeroNode2 tmp head;// 查找序号位置时tmp要指向插入数据的前一个位置不是能插入数据boolean flag false; // 判断需要的编号是否存在存在就不能添加while(true){if(tmp.next null){//找到数据链尾了break;}if (tmp.next.no node.no){ //判断位置成功就位置在tmp处break;}else if (tmp.next.no node.no){ //说明编号存在flag true;break;}tmp tmp.next;}// 判断flagif(flag){System.out.println(序号存在请重新输入数据);}else{node.next tmp.next; //新节点的后序是tmp的后序tmp.next node; // 旧节点的后序等于新节点}}//修改节点内容//思路主要是找到节点的位置// 根据node的no序号来进行修改public void update(HeroNode2 node){if(head.next null){System.out.println(链表为空);return;}//找需要修改的序号因此需要进行遍历数据/* 版本一boolean flage true;HeroNode tmp head.next; // 创建临时的引用来遍历数据while (flage){if(tmp null){ //到达链尾break;}if (tmp.no node.no){tmp.name node.name;tmp.nickname node.nickname;break;}else{tmp tmp.next;}}*/// 版本二boolean flage false;HeroNode2 tmp head.next; // 创建临时的引用来遍历数据while (true){if(tmp null){ //到达链尾break;}if (tmp.no node.no){flage true;break;}else{tmp tmp.next;}}// flage 为true会执行文件if(flage){tmp.name node.name;tmp.nickname node.nickname;}else{System.out.println(该节点数据没有找到);}}//删除节点数// 只需要直接找到需要删除的节点不需要像单链表一样找到前面的节点再进行数据删除public void del(int no){//判断数据是否为空if(head.next null){System.out.println(数据为空);return;}HeroNode2 tmp head.next;boolean flag false; // 标志是否找到待删除节点while(true){if(tmp null){ // 位置处于数据的链尾break;}if(tmp.no no){ //找到待删除节点的前一个节点的tmpflag true;break;}tmp tmp.next; //tmp后移遍历}//判断flagif (flag){tmp.pre.next tmp.next;// 如果是最后一个节点不需要执行这个否则会出现空指针的问题if(tmp.next !null) {tmp.next.pre tmp.pre;}}else{System.out.println(该节点不存在);
class HeroNode2{public int no;public String name;public String nickname;public HeroNode2 next; //指向下一个节点public HeroNode2 pre; // 指向前一个节点public HeroNode2(int no, String name, String nickname) {this.no no;this.name name;this.nickname nickname;}Overridepublic String toString() {return HeroNode2{ no no , name name \ , nickname nickname \ };}三、单向环形链表应用场景
一约瑟夫问题 人数 n5
开始序号 k 1
取出数据间隔 m2 二 代码实现 要求 构建单向环形链表 创建第一个节点通过first指向该节点并形成环形当每创建创建一个新的节点将该节点加入到链表中 遍历环形链表 通过一个辅助指针 tmp 指向first 节点通过while循环进行统计循环终止条件 tmp.next first 创建出队列的编号序列 人数 n5 开始序号 k 1 取出数据间隔 m2 创建辅助节点 helper指向代删除的节点的前一个节点注意起始位置位于环形列表的最后一个位置 报数自己也需要报一次 补充先将first 和helper 需要移动到k-1的位置 报数时让first和helper 移动m-1次 删除节点 first first.nextper.next first
创建类Josephu
package com.lcj.linkedlist;
/*
* 编写目的学习约瑟夫问题了解单向环形链表
* 类似于丢手绢的游戏只是固定了次数
* */
public class Joseph {public static void main(String[] args){// 测试CircleSingleLinkedList circleSingleLinkedList new CircleSingleLinkedList();
// circleSingleLinkedList.addBoy(5); // 创建5个节点
// circleSingleLinkedList.showBody();//出圈测试int startNum 2;int countNum 2;int nums 10;circleSingleLinkedList.addBoy(nums);circleSingleLinkedList.showBody();circleSingleLinkedList.countBoy(startNum,countNum,nums);}
}//创建单向环形链表
class CircleSingleLinkedList{// 创建一个first节点但是没有编号的private Boy first null;//添加节点数据构建成一个环形的链表// nums 的数量为 创建节点的个数public void addBoy(int nums){//判断nums 的个数if(nums 1){System.out.println(输入nums的值不正确);return;}Boy curBoy null; //辅助指针帮助构建形式链表// 创建环形链表for (int i 1; i nums ; i) {Boy boy new Boy(i);if (i1){first boy;first.setNext(first); // first 的后序是自己本身这样才能构成环curBoy first;}else{curBoy.setNext(boy); // 连接新的节boy.setNext(first); // 形成 环形curBoy boy; // 将辅助节点往新的节点进行移动}}}// 遍历当前的环形链表public void showBody(){// 判断链表是否为空if(first null){System.out.println(链表为空);return;}// 创建辅助节点Boy curBoy1 first;while (true){System.out.printf(小朋友编号%d\n, curBoy1.getNo());if (curBoy1.getNext() first) {System.out.println(数据遍历完成);break;}curBoy1 curBoy1.getNext(); //指针往后移动}}/*
* startNo 是从第几个小孩开始数数
* countNum 间隔的人数
* nums 小孩人数
* */public void countBoy(int startNo,int countNum,int nums){if(first null || startNo 1 || startNo nums){System.out.println(参数输入有误);return;}//创建一个辅助节点数据Boy helper first;//将helper指向链尾即first的前一个节点上目的是便于删除数据while(true){if(helper.getNext() first){ //判断helper是否到达链尾主要是为了删除数据时指向删除点的前一个位置break;}helper helper.getNext();}// 将frist和helper的移动startNo-1的位置for (int i 0; i startNo-1; i) {helper helper.getNext();first first.getNext();}// 小孩子报数让first和helper移动countNum -1次然后出圈删除while(true){if(helper first){ // 只有一个数据helper是在first前面的break;}//first和helper移动countNum -1次for (int i 0; i countNum-1; i) {helper helper.getNext();first first.getNext();}//first指向节点System.out.printf(小孩%d出圈\n,first.getNo());// 删除数据first first.getNext();helper.setNext(first);}System.out.printf(最后的节点为%d\n,first.getNo());}
}//创建节点 名字为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;}
}
注意只有一个节点可以自己指向自己
第四章栈 一、栈介绍 栈是一种先进先出first in last out的有效列表 允许插入和删除的一端为变化的一端称为栈顶Top另一端固定为栈底Bottom 栈的应用 中缀表达式转后缀表达式 是面试中常考的
二数组模拟栈的思路分析 使用数组来模拟栈 定义一个top来表示栈顶初始化为-1 入栈的操作当数据加入栈时topstack[top]data; 出栈的操作int value stack[top], top–
创建packecom.lcj.Stack
创建classArrayStackDemo
package com.lcj.stack;import com.sun.imageio.plugins.wbmp.WBMPImageReader;import java.util.Scanner;// 数组栈的学习
public class ArrayStackDamon {public static void main(String[] args){//数组栈测试ArrayStack stack new ArrayStack(4);String key ; //输入的数据boolean loop true; //判断循环的条件Scanner scanner new Scanner(System.in);// 测试菜单while(loop){System.out.println(输入exit:退出);System.out.println(输入push数据入栈);System.out.println(输入pop数据出栈);System.out.println(输入show 显示栈);key scanner.next();switch (key){case show:stack.list();break;case push:System.out.println(请输入需要插入的数据);int value scanner.nextInt();stack.push(1);break;case exit:System.out.println(退出);loop false;break;case pop:System.out.println(数据出栈);try{int v stack.pop();System.out.println(出栈的数值为v);}catch(Exception e){System.out.println(e.getMessage());}default:break;}}System.out.println(退出成功);}
}//栈
class ArrayStack{private int top -1; //标记栈顶的位置private int maxSize; //栈的最大长度private int stack[]; // 栈数组进行存储数据//构建器public ArrayStack(int maxSize){this.maxSize maxSize;stack new int[this.maxSize];}//判断是否为空public boolean isEmpty(){return top-1;}//判断是否栈满,即达到maxsizepublic boolean isFull(){return top maxSize-1 ;// 注意这点是从0开始计算的}//数据入栈public void push(int value){//判断是否栈满if (isFull()){System.out.println(栈满);return;}top; // top指向的是有数据的栈顶stack[top] value;}//数据出栈public int pop(){//判断数据是否为空if (isEmpty()){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\n,i,stack[i]);}}
}三练习使用链表来模拟栈
思路一双链表doubleLinked
创建双链表doubleLinked两个指针 next、pre栈顶指针top入栈节点tmp 添加到链尾前一个节点.next tmp , 前一个节点的.next.pre tmp出栈tmp.pre.next null ,tmp.pre null,遍历数据
版本一双链表实现栈
package com.lcj.stack;
/*
* 创建人lcj
* 创建时间2022年8月29
* 目的用链表来实现栈
* */
public class LinkedStackDamon {public static void main(String[] args){//测试stack stack new stack();
// System.out.println(stack.topSite()); //测试topSite是否运行正常doubleLinked node1 new doubleLinked(2);doubleLinked node2 new doubleLinked(3);doubleLinked node3 new doubleLinked(4);stack.add(node1);stack.add(node2);stack.add(node3);stack.show();stack.pop();
// System.out.println(stack.topSite());stack.show();}
}//stack
class stack{//创建一个first的头节点doubleLinked head new doubleLinked(1);//top 确定栈顶位置public doubleLinked topSite(){doubleLinked tmp head; //创建一个辅助节点while (true){if(tmp.getNext() null){// break;
// System.out.println(1);return tmp;}tmp tmp.getNext(); //往后移动}}//添加数据public void add(doubleLinked node){doubleLinked tmp topSite(); //创建一个辅助节点tmp.setNext(node); // 连接nexttmp.getNext().setPre(tmp); // 将新节点的pre连接到前一节点上
// System.out.println(tmp.getNext().getValue());}//展示数据public void show(){doubleLinked top topSite();while(true){if (top.getPre()null){ // 到达 head 之前break;}System.out.println(top.getValue());top top.getPre(); //将辅助指针往前面进行移动}}//数据出栈public int pop(){doubleLinked top topSite(); // 获得栈顶int value top.getValue();top.getPre().setNext(null);top.setPre(null);System.out.println(删除);return value;}
}// 用双链表来实现
class doubleLinked{private int value; // 链表中保存的值private doubleLinked next; //指向后序private doubleLinked pre; //指向前序private doubleLinked top; // 栈顶//构建对象public doubleLinked(int value) {this.value value;}public int getValue() {return value;}public void setValue(int value) {this.value value;}public doubleLinked getNext() {return next;}public void setNext(doubleLinked next) {this.next next;}public doubleLinked getPre() {return pre;}public void setPre(doubleLinked pre) {this.pre pre;}public doubleLinked getTop() {return top;}public void setTop(doubleLinked top) {this.top top;}
}版本二双链表实现栈
package com.lcj.stack;
/*
* 创建人lcj
* 创建时间2022年8月29
* 目的用链表来实现栈
* */
public class LinkedStackDamon {public static void main(String[] args){//测试stack stack new stack();
// System.out.println(stack.topSite()); //测试topSite是否运行正常doubleLinked node1 new doubleLinked(2);doubleLinked node2 new doubleLinked(3);doubleLinked node3 new doubleLinked(4);stack.add(node1);stack.add(node2);stack.add(node3);stack.show();stack.pop();
// System.out.println(stack.topSite());stack.show();}
}//stack
class stack{//创建一个first的头节点doubleLinked head new doubleLinked(1);//top 确定栈顶位置public doubleLinked topSite(){doubleLinked tmp head; //创建一个辅助节点while (true){if(tmp.next null){// break;
// System.out.println(top找到);return tmp;}tmp tmp.next; //往后移动}}//添加数据public void add(doubleLinked node){doubleLinked tmp topSite(); //创建一个辅助节点tmp.next node; // 连接nexttmp.next.pre tmp; // 将新节点的pre连接到前一节点上}//展示数据public void show(){doubleLinked top topSite();while(true){if (top.prenull){ // 到达 head 之前break;}System.out.println(top.getValue());top top.pre; //将辅助指针往前面进行移动}}//数据出栈public int pop(){doubleLinked top topSite(); // 获得栈顶int value top.getValue();top.pre.next null;top.pre null;System.out.println(删除);return value;}}// 用双链表来实现
class doubleLinked{public int value; // 链表中保存的值public doubleLinked next; //指向后序public doubleLinked pre; //指向前序public doubleLinked top; // 栈顶//构建对象public doubleLinked(int value) {this.value value;}public int getValue() {return value;}public void setValue(int value) {this.value value;}
}思想二创建一个单链表 创建一个singalLinked 添加链表的数据tmp 前一节点.next tmp 数据出栈 方法一遍历数据找到最后一个数据缺点时间过长方法二将链表的反转将数据出栈后由反转回去 数据入栈 思路一直接找到链尾进行插入数据 注意添加数据和数据出栈都需要注意后面节点是否存在
版本三单链表实现
package com.lcj.stack;
/** 创建人lcj* 创建时间2022年8月29* 目的用单链表来实现栈* */
public class SingalLinkedStackDaemon {public static void main(String[] args){// 测试StackLinked stack1 new StackLinked();//添加数据singalLinked Linked1 new singalLinked(1);singalLinked Linked2 new singalLinked(2);singalLinked Linked3 new singalLinked(3);singalLinked Linked4 new singalLinked(4);stack1.push(Linked1);stack1.push(Linked2);stack1.push(Linked3);stack1.push(Linked4);// 展示数据System.out.println(展示数据);stack1.show();//数据出栈System.out.println(数据出栈);try {stack1.pop();stack1.pop();}catch (Exception e){System.out.println(e.getMessage());}stack1.show();}
}// 创建栈
class StackLinked{singalLinked head new singalLinked(1); // 栈的头节点需要保持不动//添加数据和数据出栈都需要注意后面节点是否存在即栈是否空的情况public boolean isEmpty(){return head.next null;}//数据入栈public void push(singalLinked node){//判断链表是否空if (isEmpty()){head.next node; //直接将数据连接到node上不需要连接后面的return;}// 链表为不空时node.next head.next; // 将后面连接head.next node; //将前面head连接}//数据出栈public int pop(){// 栈是否为空if (isEmpty()){throw new RuntimeException(栈表为空);}// 栈只存在一个节点if (head.next.next null ){head.next null;return head.next.getValue(); // 返回被删除的值}int value head.next.getValue();head.next head.next.next; // 将head连接删除的节点的后面一个return value; // 返回被删除的值}//展示数据public void show(){singalLinked tmp head;//判断是否空if (isEmpty()){System.out.println(栈为空);return; //退出}while(true){//判断数据是否到达链尾if(tmp.next null){break;}tmp tmp.next; //往后移动System.out.printf(%d\n,tmp.getValue());}}
}//创建单链表
class singalLinked{public int value; // value 是指栈中的值public singalLinked next;public singalLinked(int value) {this.value value;}public int getValue() {return value;}public void setValue(int value) {this.value value;}
}版本四单链表实现 改变测试环境推荐
package com.lcj.stack;import java.util.Scanner;/** 创建人lcj* 创建时间2022年8月29* 目的用单链表来实现栈* */
public class SingalLinkedStackDaemon {public static void main(String[] args){/* 测一// 测试StackLinked stack1 new StackLinked();//添加数据singalLinked Linked1 new singalLinked(1);singalLinked Linked2 new singalLinked(2);singalLinked Linked3 new singalLinked(3);singalLinked Linked4 new singalLinked(4);stack1.push(Linked1);stack1.push(Linked2);stack1.push(Linked3);stack1.push(Linked4);// 展示数据System.out.println(展示数据);stack1.show();//数据出栈System.out.println(数据出栈);try {stack1.pop();stack1.pop();}catch (Exception e){System.out.println(e.getMessage());}stack1.show();*///测试二StackLinked stack1 new StackLinked();boolean loop true ; // 循环跳出的条件Scanner scanner new Scanner(System.in);String key ; // 输入的关键字while(loop){System.out.println(输入exit退出);System.out.println(输入push数据入栈);System.out.println(输入pop数据出栈);System.out.println(输入show展示数据);key scanner.next();switch (key){case exit:System.out.println(退出);loop false;break;case push:System.out.println(数据入栈);System.out.println(请输入节点数据);int index scanner.nextInt();
// singalLinked Linked new singalLinked(index);stack1.push(new singalLinked(index));break;case pop:System.out.println(数据出栈);int a stack1.pop();System.out.println(删除的值为a);break;case show:System.out.println(展示数据);stack1.show();break;default:System.out.println(输入有误);break;}}System.out.println(退出成功);}
}// 创建栈
class StackLinked{singalLinked head new singalLinked(1); // 栈的头节点需要保持不动//添加数据和数据出栈都需要注意后面节点是否存在即栈是否空的情况public boolean isEmpty(){return head.next null;}//数据入栈public void push(singalLinked node){//判断链表是否空if (isEmpty()){head.next node; //直接将数据连接到node上不需要连接后面的return;}// 链表为不空时node.next head.next; // 将后面连接head.next node; //将前面head连接}//数据出栈public int pop(){// 栈是否为空if (isEmpty()){throw new RuntimeException(栈表为空);}// 栈只存在一个节点if (head.next.next null ){head.next null;return head.next.getValue(); // 返回被删除的值}int value head.next.getValue();head.next head.next.next; // 将head连接删除的节点的后面一个return value; // 返回被删除的值}//展示数据public void show(){singalLinked tmp head;//判断是否空if (isEmpty()){System.out.println(栈为空);return; //退出}while(true){//判断数据是否到达链尾if(tmp.next null){break;}tmp tmp.next; //往后移动System.out.printf(%d\n,tmp.getValue());}}
}//创建单链表
class singalLinked{public int value; // value 是指栈中的值public singalLinked next;public singalLinked(int value) {this.value value;}public int getValue() {return value;}public void setValue(int value) {this.value value;}
}
四栈实现综合案例——计算器 思路创建两个栈一个数栈 numStack用于存储数值 一个符号栈 operStack存储符号 通过一个index来判断计算表达式中数值和符号 发现数值直接入数据栈 如果发现是符号需要分两种情况 3.1符号栈为空直接添加到符号栈中 3.2符号栈已经存在了需要判断待添加的符号和符号栈中栈顶的符号比较优先级 3.2.1如果待入栈的符号大于栈顶的则直接入栈 3.2.2如果待入栈的符号小于、等于栈顶的则需要pop 两个数栈中的与pop符号栈的中的符号进行计算并将运算结果和待入栈的符号分别入栈 当计算表达式扫描完成后就顺序从数据栈中和符号栈中pop出两个数值和符合并将结果放进数据栈中 最后在数栈只有一个数字即表达式的结果 注意符号栈是更加栈顶特点先进后出因此将优先级高的后出。
创建classcalculatot
package com.lcj.stack;import com.sun.deploy.security.SelectableSecurityManager;
import sun.font.DelegatingShape;public class Calculator {public static void main(String[] args) {String expression 32*6-2;//创建两个栈ArrayStack1 numStack new ArrayStack1(20); //数栈ArrayStack1 operStack new ArrayStack1(20); //符号栈//定义需要的相关变量int index 0; //用于扫描表达式的int num1 0;int num2 0;int res 0;int oper 0;char ch ; //符号保存到这里面的//通过while循环进行扫描表达式while (true){//依次得到expression的每一个字符ch expression.substring(index,index1).charAt(0);// substring(开始结束)//判断ch的类型进行下一步的操作if(operStack.isOper(ch)){ //如果是运算符//1. 判断当前的符号栈是否为空为空直接入栈if (!operStack.isEmpty()){//2 如果待入栈的符号大于栈顶的则直接入栈//3 如果待入栈的符号小于、等于栈顶的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 - 48); //注意ch是字符串在ASCII码中需要 - 48}//判断是否扫描完index;if(expression.length() index){break;}}//当计算表达式扫描完成后就**顺序从数据栈中和符号栈中pop出两个数值和符合**并将结果放进数据栈中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());}
}
//栈
class ArrayStack1{private int top -1; //标记栈顶的位置private int maxSize; //栈的最大长度private int stack[]; // 栈数组进行存储数据//构建器public ArrayStack1(int maxSize){this.maxSize maxSize;stack new int[this.maxSize];}//判断是否为空public boolean isEmpty(){return top-1;} // top的初始位置为-1//判断是否栈满,即达到maxsizepublic boolean isFull(){return top maxSize-1 ;// 注意这点是从0开始计算的}//数据入栈public void push(int value){//判断是否栈满if (isFull()){System.out.println(栈满);return;}top; // top指向的是有数据的栈顶stack[top] value;}//数据出栈public int pop(){//判断数据是否为空if (isEmpty()){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\n,i,stack[i]);}}//查看栈顶的值public int peek(){return stack[top];}// 符号的优先级通过定义数值来表达符号的优先级数值越大优先级越高// 目的直接将符号转换为成为数组便于更好的进行比较优先级public int priority(int oper){ //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; //注意有向后顺序从栈最先出来是num1最后出来的是num2break;case :res num1 num2;break;case -:res num2 - num1;//注意有向后顺序从栈最先出来是num1最后出来的是num2break;}return res;}}
缺点只能计算数值为单个数据的而不能计算数据为两位数的
五栈的三种表达式
前缀波兰表达式、中缀、后缀表达式逆波兰表达式
注意中缀转后缀再面试必问
前缀表达式相关知识
后缀表达式相关知识 讲解了中缀表达式到后缀表达式
后缀表达式的计算
1、前缀表达式
又被称为波兰表达式运算符位于操作数之前
eg34x 5- 6 》前缀表达式- x 3 4 5 6
补充知识
从右往左 2、后缀表达式
从左往右 注意 通过两个栈: 符号栈s1存储、数据栈 s2来存储运算符和数值 从左至右扫描中缀表达式 遇到数值直接入栈s2 遇到操作符需要分成以下情况 4.1 如果s1为空时直接将**符号入栈s1**中或者为 ( 时也是直接入栈s2中 4.2 不为空需要分成两种情况 4.2.1 当待入栈的操作符与栈顶的操作进行比较栈顶操作符小于 等于 待入栈的操作符时直接将待入栈的操作符直接入栈s1 4.2.2 当待入栈的操作符与栈顶的操作进行比较栈顶操作符大于等待入栈的操作符时**需要将操作符中的栈pop出栈顶 并入栈到s2的中** 注意待入栈还是需要和栈顶继续比较如果待入栈大于符号栈栈顶的满足4.2.1的条件直接入栈。如果不满足还是需要执 行4.2.2中 4.3 遇到左括号是直接入栈中但是待入栈操作符为右括号时需要将操作符栈的中的操作符pop出来并pop出的操作符加入到s2中一直都遇到操作符栈中的左操作符停止pop。注意左右括号去除掉不用保存在操作符栈s1中 重复第二步到第四步一直到表达式扫描结束。 扫描结束后将s1中剩余的运算符依次出栈并加入到s2中 依次弹出s2s2出栈的逆序就是后缀表达式 将34* 5-6 转换成后缀表达式
扫描到的元素:34*5-6s2栈底到栈顶 存储数据s1(栈底到栈顶) 存储操作符说明((s1栈为空直接将操作符加入栈中33(遇到数值直接加入到栈中3(如果直接有左括号符号不用比较直接加入43 4(遇到数值直接加入到栈中)3 4 遇到右括号需要将s1 pop出来一直到pop都了右括号*3 4 *s1栈为空直接将操作符加入栈中53 4 5*遇到数值直接加入到栈中-3 4 5 *-- 优 先级比 * 低,需要将s1 pop 出来,加入到s2中,一直比较直到待入栈大于s1的栈顶,待入可以入栈中63 4 5 * 6-扫描完后3 4 5 * 6 -将s1全部pop到s2中
六逆波兰计算器
目前是个位数据
创建类PolandNotation
方法一通过系统提供的栈stack来实现
将后缀表达式存储到数组中就不需要使用index进执行指向数组遍历更加便捷
package com.lcj.stack;import java.util.ArrayList;
import java.util.List;
import java.util.Stack;/*** Version 1.0* Author:lcj* Date:2022/8/30* Content: 通过自带的stack来实现逆波兰计算器*/
public class PolandNotation {public static void main(String[] args){//定义一个后缀表达式// 34*5-6 》 3 4 5 * 6 -String suffixExpression 3 4 5 * 6 -; //通过空格进行分割便于后面分割//将3 4 5 * 6 - 放进ArrayList中ListString rpnList getListString(suffixExpression);//计算结果为int res cal(rpnList);System.out.println(计算结果为res);}//将后缀表达式放进到ArrayList中public static ListString getListString(String expression){//将表达式expression进行分割String[] split expression.split( );ListString list new ArrayList();for (String s : split) {list.add(s);}return list;}//完成计算public static int cal(ListString ls){//创建栈StackString stack new StackString();for (String item : ls) {if (item.matches(\\d)){ // 用正则表达式进行判断多位数stack.push(item); // 数据直接入栈}else{ //为操作符//需要从stack中取出两个值并将计算结果进入到stacke中int num2 Integer.parseInt(stack.pop()); // 栈的数据是字符串的需要转换为整数int num1 Integer.parseInt(stack.pop());int res 0;switch (item){case *:res num1 * num2;break;case /:res num1 / num2;break;case -:res num1 - num2;break;case :res num1 num2;break;default:System.out.println(目前只支持* - /);break;}//将结果入栈stack.push(res); //将整数转换字符串因为创建的是字符串的Stack}}//到最后stack中只有一个值即结果return Integer.parseInt(stack.pop());}
}注意将数值类型的字符串转换为int Interget.parseInt(1);
方法二编写一个数组栈
自己编写一个数组栈实现中缀表达式转换为后缀表达式再通过后缀表达式的计算
ArrayList操作方法
adddata 添加数据getindex 获取值 egindex 下标setindex值 修改值removeindex 删除值 注意: 字符串比较大小使用 是比较的字符串存储的内存位置是否相同需要使用 equals进行比较
版本一中缀表达式转为后缀表达式
实现中缀表达式转为后缀表达式
package com.lcj.stack;import com.sun.deploy.security.SelectableSecurityManager;
import sun.java2d.opengl.OGLRenderQueue;import java.util.ArrayList;
import java.util.List;/*** Version 1.0* Author:lcj* Date:2022/8/30-17:00* Content: 自己编写stack实现* 1. 将中缀表达式转换为后缀表达式并输出后缀表达式* 2.计算后缀表达式的数据结果* 中缀表达式:34*5-6 后缀表达式3 4 5 * 6 -*/
public class PolandNotationStack {public static void main(String[] args){stackDemon stack new stackDemon(new ArrayList()); //链表存储 后缀表达式的String exception (34)*5-6;
// String exception ();
// stack.push(1);
// stack.show();
// System.out.println( stack.transform(*));//将中缀表达式 转成 后缀表达try {stackDemon suffix transsuffix(exception, stack);suffix.show();System.out.println(suffix.show()); //后缀表达式的结果String suffixExpection suffix.show();}catch (Exception e){System.out.println( e.getMessage());}}public static stackDemon transsuffix(String exception,stackDemon stack1){stackDemon stack stack1;stackDemon operStack new stackDemon(new ArrayList()); //存储操作符的String[] split exception.split(); //将表达式切分一个一个的//注意后缀表达式是从左往右的因此split切片出的数据可以直接从左到右进行遍历for (String iteam : split) {// 1.如果数值直接加入if (iteam.matches(\\d)){ //判断是否为多个数值通过正则表达式stack.push(iteam); //数值存储到stack中}else{//2 判断operStack 中是否为空,直接将数据入栈,或者是左括号 (if (operStack.isEmpty() || iteam.equals(()) {operStack.push(iteam);} else if (iteam.equals())){//将operStack进行pop,一直到(while (true){String oper operStack.pop();
// if(operStack.pop() (){ // 该代码有问题会删除多个operif (oper.equals(()){break;}else{stack.push(oper); // 将操作符加入到栈中}}}else{//2.1 待入栈的操作符比较栈顶操作符大小//2.1.1待入栈的操作符大于栈顶操作符,直接入栈if (operStack.compare(iteam, operStack.peek())){ //num1 待入栈的操作符 num2栈顶的操作符,还有为空if (operStack.isEmpty() || operStack.compare(iteam, operStack.peek()) ){ //num1 待入栈的操作符 num2栈顶的操作符operStack.push(iteam);}else if(!operStack.compare(iteam, operStack.peek())){ // 2.1.2 待入栈的操作符小于 等于 栈顶操作符,将operStack的栈顶pop出来保存在stack中
// stack.push(operStack.pop());//待入栈的符号需要再一次比较栈顶操作符boolean loop true;while (loop) {if (!operStack.isEmpty() !operStack.compare(iteam, operStack.peek())) { // 不能为空空了也没有数据stack.push(operStack.pop()); //一直将operStack加入到stack中去}else{loop false;operStack.push(iteam); //将待入栈的操作符入栈}}}}}}//遍历完成后将operStack中所有全部加入到stack中// System.out.println(测试operStack.show());String show operStack.show();String[] s show.split( );for (String s1 : s) {stack.push(s1);}return stack;}
}//创建stack
class stackDemon{//创建toppublic int top -1; // 初始位置为-1//数组ListStringprivate ListString stack;public stackDemon(ListString stack) {this.stack stack;}//判断是否为空public boolean isEmpty(){return stack.size() 0; //大小为0}//数据入栈public void push(String key){stack.add(key);}//数据出栈public String pop(){String value ;//判断是否为空if (stack.size()! 0) {value stack.get(stack.size()-1);stack.remove(stack.size() - 1); // 删除最后一个数据}return value;}//展示数据public String show(){int i 0;String suffix ;for (String s : stack) {if(i 0){
// System.out.print(s);suffix s;i;continue;}
// System.out.print( s);suffix s;}return suffix;}// 展示栈顶的元素public String peek(){if (isEmpty()){throw new RuntimeException(栈为空);}return stack.get(stack.size()-1);}//操作符转换将操作符转换成数值便于操作符的比较优先级public int transform(String num1){int grand 0;switch (num1){case :grand 0;break;case -:grand 0;break;case *:grand 1;break;case /:grand 1;break;default:grand -1 ; // 目的是为了让待入栈的操作符和操作符进行比较类似于 栈顶是 左括号的情况break;}return grand;}//比较操作符的大小public boolean compare(String num1,String num2){ //num1 为待入栈的操作符 num2为入栈的操作符return transform(num1) transform(num2); //待入栈的操作符大于栈顶操作符}//计算public int cal(int num1,int num2,String ch){int res 0;switch (ch){case :res num1 num2;break;case -:res num1 - num2;break;case *:res num1 * num2;break;case /:res num1 / num2;break;}return res;}
}版本二功能完整实现
package com.lcj.stack;import java.util.ArrayList;
import java.util.List;/*** Version 1.0* Author:lcj* Date:2022/8/30-17:00* Content: 自己编写stack实现* 1. 将中缀表达式转换为后缀表达式并输出后缀表达式* 2.计算后缀表达式的数据结果* 中缀表达式:34*5-6 后缀表达式3 4 5 * 6 -*/
public class PolandNotationStack {public static void main(String[] args){stackDemon stack new stackDemon(new ArrayList()); //链表存储 后缀表达式的String exception (34)*5-6;String suffixExpection ;
// String exception ();
// stack.push(1);
// stack.show();
// System.out.println( stack.transform(*));//将中缀表达式 转成 后缀表达try {stackDemon suffix transsuffix(exception, stack);suffix.show();System.out.println(suffix.show()); //后缀表达式的结果suffixExpection suffix.show();}catch (Exception e){System.out.println( e.getMessage());}//结果为suffixCal(suffixExpection);}//将后缀表达式进行计算结果public static void suffixCal(String su){String exp su; //后缀表达式String[] s exp.split( );int res 0; //结果值ArrayListString list new ArrayListString();for (String s1 : s) {//1.遇到数值直接将数值输入到list中if (s1.matches(\\d)){ //用正则表达式中判断字符舒是否为数值list.add(s1);}else{ //不为数值时遇到操作符需要将数值取出来int num2 Integer.parseInt(list.get(list.size()-1));int num1 Integer.parseInt(list.get(list.size()-2));switch (s1){case :res num1 num2;break;case -:res num1 - num2;break;case *:res num1 * num2;break;case /:res num1 / num2;break;}list.add(res); //将中间结果保存在list中}}System.out.println(res);}//实现将中缀表达式转换为后缀表达式中public static stackDemon transsuffix(String exception,stackDemon stack1){stackDemon stack stack1;stackDemon operStack new stackDemon(new ArrayList()); //存储操作符的String[] split exception.split(); //将表达式切分一个一个的//注意后缀表达式是从左往右的因此split切片出的数据可以直接从左到右进行遍历for (String iteam : split) {// 1.如果数值直接加入if (iteam.matches(\\d)){ //判断是否为多个数值通过正则表达式stack.push(iteam); //数值存储到stack中}else{//2 判断operStack 中是否为空,直接将数据入栈,或者是左括号 (if (operStack.isEmpty() || iteam.equals(()) {operStack.push(iteam);} else if (iteam.equals())){//将operStack进行pop,一直到(while (true){String oper operStack.pop();
// if(operStack.pop() (){ // 该代码有问题会删除多个operif (oper.equals(()){break;}else{stack.push(oper); // 将操作符加入到栈中}}}else{//2.1 待入栈的操作符比较栈顶操作符大小//2.1.1待入栈的操作符大于栈顶操作符,直接入栈if (operStack.compare(iteam, operStack.peek())){ //num1 待入栈的操作符 num2栈顶的操作符,还有为空if (operStack.isEmpty() || operStack.compare(iteam, operStack.peek()) ){ //num1 待入栈的操作符 num2栈顶的操作符operStack.push(iteam);}else if(!operStack.compare(iteam, operStack.peek())){ // 2.1.2 待入栈的操作符小于 等于 栈顶操作符,将operStack的栈顶pop出来保存在stack中
// stack.push(operStack.pop());//待入栈的符号需要再一次比较栈顶操作符boolean loop true;while (loop) {if (!operStack.isEmpty() !operStack.compare(iteam, operStack.peek())) { // 不能为空空了也没有数据stack.push(operStack.pop()); //一直将operStack加入到stack中去}else{loop false;operStack.push(iteam); //将待入栈的操作符入栈}}}}}}//遍历完成后将operStack中所有全部加入到stack中// System.out.println(测试operStack.show());String show operStack.show();String[] s show.split( );for (String s1 : s) {stack.push(s1);}return stack;}
}//创建stack
class stackDemon{//创建toppublic int top -1; // 初始位置为-1//数组ListStringprivate ListString stack;public stackDemon(ListString stack) {this.stack stack;}//判断是否为空public boolean isEmpty(){return stack.size() 0; //大小为0}//数据入栈public void push(String key){stack.add(key);}//数据出栈public String pop(){String value ;//判断是否为空if (stack.size()! 0) {value stack.get(stack.size()-1);stack.remove(stack.size() - 1); // 删除最后一个数据}return value;}//展示数据public String show(){int i 0;String suffix ;for (String s : stack) {if(i 0){
// System.out.print(s);suffix s;i;continue;}
// System.out.print( s);suffix s;}return suffix;}// 展示栈顶的元素public String peek(){if (isEmpty()){throw new RuntimeException(栈为空);}return stack.get(stack.size()-1);}//操作符转换将操作符转换成数值便于操作符的比较优先级public int transform(String num1){int grand 0;switch (num1){case :grand 0;break;case -:grand 0;break;case *:grand 1;break;case /:grand 1;break;default:grand -1 ; // 目的是为了让待入栈的操作符和操作符进行比较类似于 栈顶是 左括号的情况break;}return grand;}//比较操作符的大小public boolean compare(String num1,String num2){ //num1 为待入栈的操作符 num2为入栈的操作符return transform(num1) transform(num2); //待入栈的操作符大于栈顶操作符}//计算public int cal(int num1,int num2,String ch){int res 0;switch (ch){case :res num1 num2;break;case -:res num1 - num2;break;case *:res num1 * num2;break;case /:res num1 / num2;break;}return res;}
}第五章递归
一递归介绍
应用场景迷宫问题回溯、递归recursion、汉罗塔、阶乘问题、8皇后问题
算法中也会使用递归 eg快排、归并排序、二分查找、分治算法
递归方法自己调用自己每次调用时传入不同的变量有助于解决复杂的问题 JVM组成栈、堆、代码区包括常量
递归调用规则
当程序执行到一个方法时就会开辟一个独立的空间栈空间方法的局部变量是独立的不会相互影响的如果方法中使用的是引用类型变量eg数组就会共享该引用类型的数据递归必须向退出的递归条件逼近否则就死循环了当一个方法执行完毕后或者遇到了return就会返回遵守谁调用就将结果返回给谁同时当方法执行完毕或者返回时该方法也就执行完毕
二迷宫回溯问题分析与实现
迷宫回溯问题 创建packagecom.lcj.recursion
创建classMiGong
package com.lcj.recursion;/*** Version 1.0* Author:lcj* Date:2022/9/2-21:17* Content:*/
public class MiGong {public static void main(String[] args){//先创建一个二维数组模型迷宫//地图为8行7列的int[][] map new int[8][7];//用1来代表是墙//上下墙for (int i 0; i 7; i) {map[0][i] 1;map[7][i] 1;}//左右为墙for (int i 0; i 8; i) {map[i][0] 1;map[i][6] 1;}//创建墙map[3][1] 1;map[3][2] 1;// 找路方法setWay(map,1,1);//输出地图for (int i 0; i 8; i) {for (int j 0; j 7; j) {System.out.print(map[i][j] );}System.out.println();}
// System.out.println(map[1].length);}//使用递归回溯小球/** 1、map :表示地图* 2、ij 表示起始位置* 3、map[7][6] 为终点* 4、当map[i][j] 为 0表示 该节点没有走过为1表示墙2表示通路3表示该节点已经走过但是走不通* */public static boolean setWay(int[][] map,int i,int j){if(map[6][5] 2){return true;}else{if (map[i][j] 0){ // 当前的节点没有走过//按照的策略为下 - 右 -上 -左map[i][j] 2;if (setWay(map,i1,j)){return true;}else if(setWay(map,i,j1)){return true;}else if(setWay(map,i-1,j)){return true;}else if(setWay(map,i,j-1)){return true;}else {//说明该点是走不通的map[i][j] 3;return false;}}else { //该map[i][j]节点 不为0,可能是1墙,2已经走过,3死路return false; //不要再走}}}
}注意谁调用谁用值
三八皇后问题回溯问题
1、介绍
任意两个皇后都不能同时处于同一行、同一列或者同一斜线 用一维数组解决棋盘位置eg:arr[8] {0,4,7,5,2,6,1,3} // arr对应的下标表示第几行arr[i] val val表示第i1个皇后放在第i1行的第val1列中
2、代码实现
创建classQueue8
package com.lcj.recursion;/*** Version 1.0* Author:lcj* Date:2022/9/5-21:05* Content:*/
public class Queue8 {int max 8; //皇后的个数//定义数值array保存皇后放置位置的结果int[] array new int[max];static int count 0;public static void main(String[] args){//测试Queue8 queue8 new Queue8();queue8.check(0); //第0行第0列开始System.out.printf(个数为%d,count);}//编写一个方法放置第n个皇后private void check(int n){if(n max){ // n 8print(); //输出结果return; //已经将结果放好}//依次放入皇后并判断是否冲突for (int i 0; i max; i) {//先把当前这个皇后n放到该行的第1列中array[n] i;if(judge(n)){ //不冲突check(n1);}//如果冲突会跳转到array[n] i 上面的将n往后继续移动}}//判断是否冲突,查看当我们放置第n个皇后是否和前面的已经摆放的皇后冲突//同行不需要判断因为每次一行只有一个数值、同列、同斜线private boolean judge(int n){for (int i 0; i n; i) {//array[i] array[n] 判断是否在同一列/*Math.abs(n-i) Math.abs(array[n]-array[i]) 主要是判断是否在同一条斜线上Math.abs 是 绝对值n-i 是行之差array[n]-array[i] 是列之差值相同说明是斜线* */if (array[i] array[n] || Math.abs(n-i) Math.abs(array[n]-array[i])){return false;}}return true; // 不冲突}//将皇后摆放的位置输出来private void print(){for (int i 0; i array.length; i) {System.out.print(array[i] );}System.out.println(); //换行count;}
}第六章排序算法
一、排序算法 排序算法sort Algorithm将数据按着一定的顺序进行排序的过程。 排序的分类 内部排序将数据加载到内存中进行排序外部排序法数量大的时候无法加载到内存中时用外部存储进行排序 直接插入、简单选择、冒泡排序法必须要掌握
二、算法的时间复杂度
一算法的评判方法 事后统计的方法 在计算运行后再计算运行时间 有问题需要运行程序但是要受到计算机硬件性能的影响运行程序可能需要很长的时间 事前估算的方法——时间复杂度 通过分析算法的时间复杂度来判断那个算法比较优秀
二时间复杂度
1、时间频度
时间频数一个算法花费时间与算法中语句执行次数成正比即语句多花费时间多。 语句频数 或者 时间频数记作T(n)算法中语句执行的次数
特点
忽略时间频数中的常数项 忽略时间频数中低次项 忽略时间频数的系数
2 、时间复杂度
时间复杂度
2.1 算法中基本操作语句的重复执行次数是问题规模n的某个函数用T(n)表示时间频数若有某个辅助函数f(n)使得当n趋近于无穷大时T(n)/f(n)的极限值为不等于零的常数则称为f(n)是T(n)的同数量级函数。记作T(n)O (f(n)) ,称O(f(n))为算法的渐进时间复杂度简称时间复杂度。 T(n)3n23n1T(n)3n^23n1T(n)3n23n1 T(n)n2T(n)n^2T(n)n2
f(n)n2f(n)n^2f(n)n2
结果为
T(n)/f(n)O(n2)T(n)/f(n)O(n^2)T(n)/f(n)O(n2) O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(nk)O(2n)(n!)O(1) O(log_2^n) O(n) O(nlog_2^n) O(n^2) O(n^3) O(n^k) O(2^n)(n!)O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(nk)O(2n)(n!) 常数阶O(1)O(1)O(1) :没有循环代码 三平均时间复杂度
1、平均时间复杂度
平均时间复杂度所有可能的输入实例的时间平均之后的算法运行时间
2、最坏时间复杂度
最坏时间复杂度算法运行最坏的时间复杂度作用相对于算法的运行时间界限不会出现最坏的结果 四空间复杂度——空间换时间 三、冒泡排序算法(bubble sorting)
一共需要进行数组长度-1次排序每一次内部排序在逐渐减少优化如果在排序中没有发生交换说明已经是有序的直接将结果输出
一代码实现
创建packagecom.lcj.sort
创建classBubble Sorting
package com.lcj.sort;import java.lang.reflect.Array;
import java.util.Arrays;/*** Version 1.0* Author:lcj* Date:2022/9/13-21:10* Content: 创建冒泡排序法*/
public class BubblerSorting {public static void main(String[] args){int arr[] {3,9,-1,10,-2};for(int i0; iarr.length-1;i){ // 循环每次减少for(int j0;j arr.length-1-i;j){int temp 0;if (arr[j]arr[j1]){temp arr[j];arr[j] arr[j1];arr[j1] temp;}}}// System.out.println(arr.toString());System.out.println(Arrays.toString(arr));}
}升级
如果在排序中如果数据已经排序完成了直接中止排序输出结果
package com.lcj.sort;import java.lang.reflect.Array;
import java.util.Arrays;/*** Version 1.0* Author:lcj* Date:2022/9/13-21:10* Content: 创建冒泡排序法*/
public class BubblerSorting {public static void main(String[] args){
// int arr[] {3,9,-1,10,-2};int arr[] {1,3,2,4,5};boolean flage false; // 目的判断数据是否交换如果没有发生交换说明数据已经排序完成for(int i0; iarr.length-1;i){ // 循环每次减少for(int j0;j arr.length-1-i;j){int temp 0;if (arr[j] arr[j1]){flage true;temp arr[j];arr[j] arr[j1];arr[j1] temp;}}System.out.printf(第%d次循环,i);System.out.println(Arrays.toString(arr));if(flage false){break;}else{flage false; //注意需要将数据转换成false}}// System.out.println(arr.toString());System.out.println(Arrays.toString(arr));}
}测试将数量达到8万条时运行时间较长
package com.lcj.sort;import java.text.SimpleDateFormat;
import java.util.Arrays;/*** Version 1.0* Author:lcj* Date:2022/9/13-21:10* Content: 创建冒泡排序法*/import java.util.Date;public class BubblerSorting {public static void main(String[] args){
// int arr[] {3,9,-1,10,-2};// 测试当数据量的大的时候执行时间的变化int[] arr new int[80000];//添加数据for(int i0; i80000 ;i){arr[i] (int)(Math.random()*80000) ; // 生成[0,1) * 80000 范围为:[0,80000)}Date date1 new Date(); //生成时间SimpleDateFormat simpleDateFormat new SimpleDateFormat(YYYY-MM-DD hh:mm:ss); //将时间进行格式化
// System.out.println(date1);System.out.println(开始时间simpleDateFormat.format(date1));for(int i0; iarr.length-1;i){ // 循环每次减少for(int j0;j arr.length-1-i;j){int temp 0;if (arr[j]arr[j1]){temp arr[j];arr[j] arr[j1];arr[j1] temp;}}}Date date2 new Date();System.out.println(结束时间simpleDateFormat.format(date2));// System.out.println(Arrays.toString(arr)); //展示全部数据}
}四、选择排序算法
一选举排序介绍
选择排序是从待排序的的数据中按指定规则选出某一元素再依次交换位置后达到排序的目的。 二代码实现
案例将101,34,119,1通过选择排序从低到高进行排序
创建classSelectSort
时间复杂度:O(n2)O(n^2)O(n2)
package com.lcj.sort;import java.util.Arrays;/*** Version 1.0* Author:lcj* Date:2022/9/14-20:59* Content:选择排序实现*/
public class SelectSort {public static void main(String[] args){int[] arr1 new int[]{101, 34, 119, 1};selectSort(arr1);}//选择排序的方法public static void selectSort(int[] arr){int temp 0;for (int i0;iarr.length-1;i){ //选择排序中外部排序只有 数组长度-1int minIndex i; //记录最大下标int min arr[minIndex];for (int ji1;jarr.length;j){if(min arr[j]){minIndex j;min arr[minIndex]; //将最值进行更新目前是为了确定最小值的位置}}//交换数据if(minIdex !i){ //优化部分情况是后面已经排好序了就不需要进行排序了temp min;arr[minIndex] arr[i];arr[i] temp;}System.out.println(Arrays.toString(arr));}System.out.println(Arrays.toString(arr));}
}注意先将算法简单化再将算法复杂化 一部分一部分进行实现
五、插入排序算法
一介绍
插入排序属于内部排序通过将要排序的数据插入到指定位置来达到排序的 二代码实现
创建classIndexSort
自己实现
版本一
package com.lcj.sort;import java.util.Arrays;/*** Version 1.0* Author:lcj* Date:2022/9/16-22:06* Content: 自己实现插入排序 从小到大*/
public class IndexSort {public static void main(String[] args){int arr[] {17,3,25,14,20,9};indexSorting(arr);}public static void indexSorting(int[] arr){int index 0;//待插入数据的下标int indexNum 0; //待插入数据for(int i1;iarr.length;i){index i; //待插入数据的下标,为第一次for循环的下标indexNum arr[i];// 待插入值//有序表进行排序// 1.实现待插入数据的位置确定// 2.实现插入数据需要将数据进行移动这里主要是往后移动因此需要找到待插入的位置// 2.1插入位置的判断for(int j0;j i;j){int indexLoc 0; //插入数据的位置boolean flag false;//寻找插入数据的位置—暴力法if (arr[i]arr[j]){indexLoc j; //获得插入数据的位置flag true; //可以执行后移操作}if(flag) {//执行后移操作for (int k i;kj;k--){arr[k]arr[k-1];}arr[j] indexNum;}}System.out.printf(第%d次,i);System.out.println(Arrays.toString(arr));}}
}版本二
package com.lcj.sort;import java.util.Arrays;/*** Version 1.0* Author:lcj* Date:2022/9/16-22:06* Content: 自己实现插入排序 从小到大*/
public class IndexSort {public static void main(String[] args){int arr[] {17,3,25,14,20,9};indexSorting(arr);}public static void indexSorting(int[] arr){int index 0;//待插入数据的下标int indexNum 0; //待插入数据for(int i1;iarr.length;i){index i; //待插入数据的下标,为第一次for循环的下标indexNum arr[i];// 待插入值//有序表进行排序// 1.实现待插入数据的位置确定// 2.实现插入数据需要将数据进行移动这里主要是往后移动因此需要找到待插入的位置// 2.1插入位置的判断for(int j0;j i;j){int indexLoc 0; //插入数据的位置boolean flag false;//寻找插入数据的位置—暴力法if (arr[i]arr[j]){indexLoc j; //获得插入数据的位置flag true; //可以执行后移操作}if(flag){for(int kj;ji;j){int temp arr[i];arr[i] arr[j];arr[j] temp;}}}System.out.printf(第%d次,i);System.out.println(Arrays.toString(arr));}}
}测试
package com.lcj.sort;import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;/*** Version 1.0* Author:lcj* Date:2022/9/16-22:06* Content: 自己实现插入排序 从小到大*/
public class IndexSort {public static void main(String[] args){
// int arr[] {17,3,25,14,20,9};int[] arr new int[80000];for (int i 0; i arr.length; i) {arr[i] (int)(Math.random()*arr.length);}Date date1 new Date();SimpleDateFormat simpleDateFormat new SimpleDateFormat(YYYY-MM-DD hh:mm:ss);System.out.println(开始时间simpleDateFormat.format(date1));indexSorting(arr);Date date2 new Date();
// SimpleDateFormat simpleDateFormat new SimpleDateFormat(YYYY-MM-DD hh:mm:ss);System.out.println(开始时间simpleDateFormat.format(date2));}public static void indexSorting(int[] arr){int index 0;//待插入数据的下标int indexNum 0; //待插入数据for(int i1;iarr.length;i){index i; //待插入数据的下标,为第一次for循环的下标indexNum arr[i];// 待插入值//有序表进行排序// 1.实现待插入数据的位置确定// 2.实现插入数据需要将数据进行移动这里主要是往后移动因此需要找到待插入的位置// 2.1插入位置的判断for(int j0;j i;j){int indexLoc 0; //插入数据的位置boolean flag false;//寻找插入数据的位置—暴力法if (arr[i]arr[j]){indexLoc j; //获得插入数据的位置flag true; //可以执行后移操作}
// if(flag) {
// //执行后移操作
// for (int k i;kj;k--){
// arr[k]arr[k-1];
// }
// arr[j] indexNum;
// }if(flag){for(int kj;ji;j){int temp arr[i];arr[i] arr[j];arr[j] temp;}}}}}
}六、希尔排序算法shell 一希尔排序算法介绍
希尔排序是经过改进之后的一个更高效的版本也称为缩小增量排序
基本思想
希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至1时整个文件恰好被分成一组 二代码实现 方法一交换法
package com.lcj.sort;import java.util.Arrays;/*** Version 1.0* Author:lcj* Date:2022/9/19-10:40* Content:希尔排序算法自己排序实现*/
public class ShellSort {public static void main(String[] args){int[] arr {8,9,1,7,2,3,5,4,6,0};shellSort(arr);}//使用逐步推导的过程进行实现代码public static void shellSort(int[] arr){int temp 0;for(int graparr.length/2; grap 0; grap/2){ // 分组的次数 5,2,1
// System.out.println(grap); //测试for(int igrap;iarr.length;i){ //循环一次是一组for (int ji-grap;j0;j-grap) {if (arr[j] arr[j grap]) {temp arr[j];arr[j] arr[j grap];arr[j grap] temp;}}}}System.out.println(Arrays.toString(arr));}
}方法二移动法——插入法
package com.lcj.sort;import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;/*** Version 1.0* Author:lcj* Date:2022/9/19-10:40* Content:希尔排序算法自己排序实现*/
public class ShellSort {public static void main(String[] args){int[] arr {8,9,1,7,2,3,5,4,6,0};shellSort(arr); // 移动式}//使用逐步推导的过程进行实现代码public static void shellSort(int[] arr){int temp 0;for(int graparr.length/2; grap 0; grap/2){ // 分组的次数 5,2,1
// System.out.println(grap); //测试for(int igrap;iarr.length;i) { //循环一次是一组int j i;//待插入数据的下标int insertValue arr[i]; //待插入值if (arr[j] arr[j-grap]) { //待插入值小于之前的说明待入数值需要在[j-grap] 之前但是位置未确定while(j-grap0 insertValue arr[j-grap] ){ //insertValue 小于 arr[j-grap]插入数据//将数据往后移动arr[j] arr[j-grap];j-grap; //将标往后移动}arr[j] insertValue;}}}System.out.println(Arrays.toString(arr));}}
测试运行时间1S
package com.lcj.sort;import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;/*** Version 1.0* Author:lcj* Date:2022/9/19-10:40* Content:希尔排序算法自己排序实现*/
public class ShellSort {public static void main(String[] args){//int[] arr {8,9,1,7,2,3,5,4,6,0};int arr[] new int[80000];for (int i 0; i arr.length; i) {arr[i] (int)(Math.random()*arr.length);}Date date1 new Date();SimpleDateFormat simple new SimpleDateFormat(yyyy-MM-dd HH:mm:ss);String dateString simple.format(date1);System.out.println(dateString);shellSort(arr); // 移动式Date date2 new Date();String date2String simple.format(date2);System.out.println(date2String);}//使用逐步推导的过程进行实现代码public static void shellSort(int[] arr){int temp 0;for(int graparr.length/2; grap 0; grap/2){ // 分组的次数 5,2,1
// System.out.println(grap); //测试for(int igrap;iarr.length;i) { //循环一次是一组int j i;//待插入数据的下标int insertValue arr[i]; //待插入值if (arr[j] arr[j-grap]) { //待插入值小于之前的说明待入数值需要在[j-grap] 之前但是位置未确定while(j-grap0 insertValue arr[j-grap] ){ //insertValue 小于 arr[j-grap]插入数据//将数据往后移动arr[j] arr[j-grap];j-grap; //将标往后移动}arr[j] insertValue;}}}//System.out.println(Arrays.toString(arr));}}七、快排算法——Quicksort
一快排算法介绍
动画演示1
动画演示2
快排算法是对冒泡排序算法的升级。
基本思想通过一趟排序将数据将排序数据分成两部分注意其他一部分要比另一部小然后另外两部分也根据这样方式进行排序最终实现排序数据有序。可以采取递归实现 二代码实现
package com.lcj.sort;import java.util.Arrays;/*** Version 1.0* Author:lcj* Date:2022/9/21-22:08* Content:*/
public class QuickSort {public static void main(String[] arg){int arr[] {-9,78,0,23,-567,70};quickSort(arr,0, arr.length-1);}public static void quickSort(int[] arr,int left,int right){int l left; //左下标int r right; //右下标int pivot arr[(leftright)/2]; //取左右的中间值作为基准左边是全部小于int temp 0;//临时变量while(l r){//只要arr[l] 小于 pivot 将l向右移动一格只要arr[l] pivot就终止移动if(arr[l] pivot){l1;}//只要arr[r] 大于 pivot 将r向左移动一格只要arr[r] pivot就终止移动if(arr[r] pivot ){r -1;}//如果l大于r说明privot 左边的数据已经是最小的了右边的数据是最大的了if(l r){break;}//交换temp arr[l];arr[l] arr[r];arr[r] temp;//如果交换完后发现这个arr[l] pivot 值,相等于r--前移if(arr[l] pivot){ //注意:r指向的是交换的元素如果不说不进行后移的话会死循环r -1;}//如果交换完后发现这个arr[r] pivot 值,相等于l后移if(arr[r] pivot){l 1;}}// 如果lr必须lr--,否则出现栈溢出,即死循环if (lr){l 1;r - 1;}//向左递归if (left r){quickSort(arr,left,r);}//向右递归,if (l right){quickSort(arr,l,right);}System.out.println(Arrays.toString(arr));}
}压力测试
package com.lcj.sort;import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;/*** Version 1.0* Author:lcj* Date:2022/9/21-22:08* Content:*/
public class QuickSort {public static void main(String[] arg){
// int arr[] {-9,78,0,23,-567,70};int[] arr new int[80000];for (int i 0; i arr.length; i) {arr[i] (int)(Math.random()*80000);}Date date1 new Date();SimpleDateFormat simpleDateFormat new SimpleDateFormat(YYYY-MM-DD hh:mm:ss);System.out.println(simpleDateFormat.format(date1));quickSort(arr,0, arr.length-1);Date date new Date();System.out.println(simpleDateFormat.format(date));}public static void quickSort(int[] arr,int left,int right){int l left; //左下标int r right; //右下标int pivot arr[(leftright)/2]; //取左右的中间值作为基准左边是全部小于int temp 0;//临时变量while(l r){//只要arr[l] 小于 pivot 将l向右移动一格只要arr[l] pivot就终止移动if(arr[l] pivot){l1;}//只要arr[r] 大于 pivot 将r向左移动一格只要arr[r] pivot就终止移动if(arr[r] pivot ){r -1;}//如果l大于r说明privot 左边的数据已经是最小的了右边的数据是最大的了if(l r){break;}//交换temp arr[l];arr[l] arr[r];arr[r] temp;//如果交换完后发现这个arr[l] pivot 值,相等于r--前移if(arr[l] pivot){ //注意:r指向的是交换的元素如果不说不进行后移的话会死循环r -1;}//如果交换完后发现这个arr[r] pivot 值,相等于l后移if(arr[r] pivot){l 1;}}// 如果lr必须lr--,否则出现栈溢出,即死循环if (lr){l 1;r - 1;}//向左递归if (left r){quickSort(arr,left,r);}//向右递归,if (l right){quickSort(arr,l,right);}
// System.out.println(Arrays.toString(arr));}
}运行时间
2022-09-269 04:37:14
2022-09-269 04:37:14八、归并排算法
将大问题分成小问题来解决
一介绍
归并排序merge-sort是利用归并的思想实现排序采用经典的分治divide-and-conquer策略分治问题是将问题1.分成一些小的问题然后递归求解2.治将分阶段得到的各答案“修补”在一起即分而治之
将84571362 按照从小到大进行排序 二代码实现
创建classMergetSort
package com.lcj.sort;import java.util.Arrays;/*** Version 1.0* Author:lcj* Date:2022/10/13-22:09* Content:归并排序算法*/
public class MergeSort {public static void main(String[] args) {int arr[] {8, 4, 5, 6, 1, 3, 6, 2};int[] temp new int[arr.length];mergeSort(arr,0,arr.length - 1,temp);System.out.println(归并排序后 Arrays.toString(arr));}//分合的算法public static void mergeSort(int[] arr,int left,int right,int[] temp){if(left right){int mid (left right)/2;//向左进行递归mergeSort(arr,left,mid,temp);//向右进行递归mergeSort(arr,mid1,right,temp);//合并merg(arr,left,mid,right,temp);}}//合并方法/** arr:数据数值* left左边有序数列的初始索引* right右边有序数列的最右边索引* mid 是中间索引* tmp临时数组* */public static void merg(int[] arr,int left,int mid,int right,int[] tmp){int i left; //初始化最左边的索引int j mid 1 ;int t 0 ; //临时数组的初始索引//第一步先将左右两边按照从小到的大顺序将数据放进到临时数组中,直到一边处理完成// 注意左右两边的数据分别是有序的while(imid jright){// 如果左边的数据小于右边时将左边数据移动到tmp中if (arr[i] arr[j]){tmp[t] arr[i];t 1; //将t往后进行移动i 1; // 将i往后进行移动}else{ // 将右边的数据大于左边的数据时tmp[t] arr[j];t 1; // 将t往后进行移动j 1;}}// 第二步将剩下的数组依次放进到临时数组中while(i mid){ // 左边数据剩余tmp[t] arr[i];i ;t ;}while(j right){ // 右边数据剩余tmp[t] arr[j];j ;t ;}// 第三步将临时数组数据放进arr中t 0;int tempLeft left;while(tempLeft right){arr[tempLeft] tmp[t];t 1;tempLeft 1;}}
}九、基数排序
一基础知识
基数排序radix sort属于“分配式排序” 或者称为“桶子排序”。主要是通过将数据的个位、十位等位数放进行相应的“桶”中来达到排序的效果
基数排序属于效率高的稳定性排序基数排序是桶排序的扩展
思路
将所有待排序的数据统一长度位数短的在前面补充0然后按照从低位到高位对数据进行排序
eg{53,3542,748,14214} 进行升序排序 二代码实现
创建类RadixSort
package com.lcj.sort;import java.util.Arrays;/*** Version 1.0* Author:lcj* Date:2022/10/16-10:44* Content:基数排序* 主要思路* 1. 创建对应的10个桶即十个数组分别代表的是从0-9的数字* 2. 获取个位、十位等数据将数据对应放进到数组中并数据读取到原来的数组中进行排序* 3. 重复第2步骤循环次数为数据中最大值的个数* */
public class RadixSort {public static void main(String[] args){int arr[] {53,3,42,748,14,214};radixSort(arr);System.out.println(Arrays.toString(arr));}//基数排序方法public static void radixSort(int[] arr){//1.通过创建二维数据来表示桶长度为arr.length来避免数据溢出的问题//通过空间换时间int[][] bucket new int[10][arr.length];//记录每一个桶中的数量并不是所有的桶中有数据// egbucketElementCounts[1] 存储的是bucket[1]中的数据个数int[] bucketElementCounts new int[10];//2.获取到最大值的长度int max arr[0];for(int i 0;i arr.length-1;i){if(max arr[i]){max arr[i];}}int maxLength (max).length(); //最大值的长度决定循环的次数// 4. 循环执行for(int k 0 ,n1;k maxLength ;k,n * 10) {// 3获取数据循环for (int i 0; i arr.length; i) {//遍历所有数据,获取位数//取除元素的位数int digitOfELement arr[i]/n % 10;bucket[digitOfELement][bucketElementCounts[digitOfELement]] arr[i];bucketElementCounts[digitOfELement]; //元素的个数统计需要改变}//将二维数组中的数据转移到arr中int index 0; //初始化的索引下标for (int j 0; j bucketElementCounts.length; j) { //bucketElementCounts 10if (bucketElementCounts[j] 0) {for (int l 0; l bucketElementCounts[j]; l) {arr[index] bucket[j][l]; // 将二维数组的元素重新赋给arr数组中index;}bucketElementCounts[j] 0 ; //注意一定要将这点的数据清为0}}}}}注意事项数据量特别大的时候会占用大量的内存
~~~java
Date date1 new Date(); //生成时间SimpleDateFormat simpleDateFormat new SimpleDateFormat(YYYY-MM-DD hh:mm:ss); //将时间进行格式化
// System.out.println(date1);System.out.println(开始时间simpleDateFormat.format(date1));十、排序总结
排序算法平均时间复杂度最好情况最坏情况空间复杂度排序方式稳定性冒泡排序O(n2)O(n^2)O(n2)O(n)O(n)O(n)O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)In-Place稳定选择排序O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)O(1)O(1)O(1)In-Place不稳定插入排序O(n2)O(n^2)O(n2)O()O()O()希尔排序归并排序快速排序堆排序计数排序桶排序基数排序
O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(nk)O(2n)(n!)O(1) O(log_2^n) O(n) O(nlog_2^n) O(n^2) O(n^3) O(n^k) O(2^n)(n!)O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(nk)O(2n)(n!)
