第一章：數(shù)據(jù)結(jié)構(gòu)與算法

一、數(shù)據(jù)結(jié)構(gòu)概述

數(shù)據(jù)結(jié)構(gòu)包括：

• 線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在的一對一的線性關(guān)系
  • 兩種不同存儲結(jié)構(gòu):
    • 順序存儲結(jié)構(gòu) （使用順序表，順序表中存儲的元素是連續(xù)的，即存儲的位置是連續(xù)的）
    • 鏈?zhǔn)酱鎯Y(jié)構(gòu)（使用鏈?zhǔn)奖?#xff0c;存儲數(shù)據(jù)不一定是連續(xù)的，好處：利用磁盤的碎片化的空間）
  • 常見結(jié)構(gòu)：數(shù)組、隊列、鏈表和棧
• 非線性結(jié)構(gòu)：數(shù)據(jù)元素之間不一定是一對一的關(guān)系
  • 常用：二位數(shù)組、多維數(shù)組、廣義表、樹結(jié)構(gòu)、圖結(jié)構(gòu)

第二章：稀疏數(shù)組和隊列

一 、稀疏sparsearray 數(shù)組

（一）案例需求

案例：五子棋的數(shù)據(jù)的存盤和繼續(xù)上次棋盤

• 主要解決：其盤數(shù)據(jù)的存放問題

如果用二維數(shù)組進行連續(xù)存儲數(shù)據(jù)，會記錄很多無意義的數(shù)據(jù)

• 解決辦法：稀疏數(shù)組，來壓縮二維數(shù)組

（二）稀疏數(shù)組介紹

稀疏數(shù)組適用范圍：

• 數(shù)組中大部分的元素為0
• 元素為同一個值

稀疏數(shù)組處理方法：

• 記錄數(shù)組一共幾列幾行、不同值的個數(shù)
• 不同的元素的行、列、值記錄在稀疏數(shù)組中

（三）應(yīng)用實列

稀疏數(shù)組，可以用來保存二維數(shù)組（eg：棋盤、地圖等）

二維數(shù)組轉(zhuǎn)稀疏數(shù)組的思路：

1. 遍歷二維數(shù)組，得到有效數(shù)據(jù)的個數(shù) sum （即：知道列的個數(shù)，而行的個數(shù)是固定的3）

2. 根據(jù)sum就可以創(chuàng)建稀疏數(shù)組spareseArr int[sum+1][3]

3. 將二維數(shù)組的有效數(shù)據(jù)存入到稀疏數(shù)組

   （第一行數(shù)據(jù)為：行個數(shù)、列個數(shù)、數(shù)據(jù)個數(shù)）

   稀疏數(shù)組的形狀：[數(shù)據(jù)個數(shù)+1,3]

稀疏數(shù)組轉(zhuǎn)二維數(shù)組的思路：

1. 先讀取稀疏數(shù)組中第一行數(shù)據(jù)，來創(chuàng)建原始的二維數(shù)組
2. 在讀取稀疏數(shù)組中后幾行的數(shù)據(jù)，并將值賦給二維數(shù)組中

（四）代碼實現(xiàn)

創(chuàng)建DataStructures，創(chuàng)建package ：com.lcj.sparseArray,創(chuàng)建類：SparseArray

package com.lcj.sparseArray;
/*
* 編寫時間：202208014
* 編寫人員：lcj
* 編寫目的：聯(lián)系稀疏數(shù)組
* */
public class SparseAarray {public static void main(String[] args){// 1. 創(chuàng)建11*11的二維數(shù)組（棋盤）// 0 表示沒有棋子，1表示黑棋，2表示藍棋int chessArr1[][] = new int[11][11];chessArr1[1][2] = 1;chessArr1[2][3] = 2;// 輸出原始棋盤的數(shù)據(jù)for (int[] row:chessArr1){for (int data:row){System.out.printf("%d\t",data);}System.out.println();}
// __________________________________________________________________//(一)：二維數(shù)組轉(zhuǎn)為稀疏數(shù)組// 1.先遍歷二維數(shù)組，得到數(shù)據(jù)的個數(shù) （稀疏數(shù)組 形狀：[個數(shù)+1,3]）int count = 0;for(int i = 0;i < chessArr1.length;i++){for (int j=0;j < chessArr1[1].length;j++){if(chessArr1[i][j] != 0)count++;}}System.out.println("數(shù)值的個數(shù)："+count);// 2.創(chuàng)建稀疏數(shù)組int sparseArray[][] = new int[count+1][3];// 第一行的數(shù)據(jù)sparseArray[0][0] = chessArr1.length;sparseArray[0][1] = chessArr1[1].length;sparseArray[0][2] = count;// 3.添加數(shù)值int a = 0; // 作用：統(tǒng)計不為零的數(shù)值的個數(shù)來確定，稀疏數(shù)組的行下標(biāo)for(int i = 0;i < chessArr1.length;i++){for (int j=0;j < chessArr1[1].length;j++){if(chessArr1[i][j] != 0) {a++;sparseArray[a][0] = i; // 數(shù)據(jù)的行sparseArray[a][1] = j; // 數(shù)據(jù)的列sparseArray[a][2] = chessArr1[i][j]; // 數(shù)據(jù)值}}}// 4.輸出稀疏數(shù)組for (int[] row : sparseArray) {for (int data : row) {System.out.printf("%d\t",data);}System.out.println();}// _____________________________________________________________________//（二）：稀疏數(shù)組轉(zhuǎn)換為二維數(shù)組// 1.創(chuàng)建二維數(shù)組int chessArr2[][] = new int[sparseArray[0][0]][sparseArray[0][1]];//2.添加數(shù)值到二維數(shù)組中for (int i =1 ;i< sparseArray.length; i++){chessArr2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];}// 3.輸出二維數(shù)組for (int[] row : chessArr2) {for (int data : row) {System.out.printf("%d\t",data);}System.out.println();}}
}

課后練習(xí)題：

1. 在前面的基礎(chǔ)上，將稀疏數(shù)組保存到磁盤中，eg：map.data

2. 恢復(fù)原來的數(shù)組時，讀取map.data進行恢復(fù)

二、隊列

隊列的特點：先進先出

實現(xiàn)方法：數(shù)組和鏈表

（一）數(shù)組模擬隊列

加入數(shù)據(jù)【addQueue】的思路：

1. 將尾指針往后移：rear+1，當(dāng)front==rear [空]
2. 若尾指針rear小于隊列的最大值maxsize-1，可以將數(shù)據(jù)存入到隊列中，如果等于maxsize-1，則無法進行存儲數(shù)據(jù)

注意：

• rear 指向隊列中最后一個元素
• front指向隊列中第一個元素中前一個位置

代碼實現(xiàn)

創(chuàng)建package：com.lcj.queue,創(chuàng)建類名：ArrayQueueDamon

package com.lcj.queue;import java.util.Scanner;/** 編寫時間：20220814* 編寫人員：lcj* 編寫目的：數(shù)組模擬隊列* */
public class ArrayQueueDamon {public static void main(String[] args) {// 代碼測試//創(chuàng)建對象arrayQueue Queue = new arrayQueue(3);  //最大值為3char key = ' ';//接收用戶輸入Scanner scanner = new Scanner(System.in);boolean loop = true;  //創(chuàng)建循環(huán)條件// 輸出一個菜單while(loop){ // 創(chuàng)建死循環(huán)System.out.println("s(show):顯示隊列");System.out.println("e(exit):退出隊列");System.out.println("a(add):添加數(shù)據(jù)到隊列");System.out.println("g(get):從隊列中取數(shù)據(jù)");System.out.println("h(head):查隊列中頭部數(shù)據(jù)");key = scanner.next().charAt(0); //獲取單個字符switch (key){case 's':Queue.showQueue();break;case 'a':System.out.println("請輸入一個數(shù)據(jù):");int value = scanner.nextInt();Queue.addQueue(value);break;case 'g':try {int res = Queue.getQueu();System.out.printf("取出數(shù)據(jù)：%d\n",res);}catch (Exception e){System.out.println(e.getMessage());}break;case 'h':try {int res = Queue.headQueue();System.out.printf("輸入數(shù)據(jù)隊列頭部數(shù)據(jù)：%d\n",res);}catch (Exception e){System.out.println(e.getMessage());}break;case 'e':scanner.close(); // 關(guān)閉scannerloop = false;break;default:break;}}System.out.println("退出成功");}
}// 使用數(shù)組來模擬隊列
class arrayQueue{private int maxsize; // 最大值private int rear;  // 隊列的尾指針，private int front; // 隊列的頭指針，private int[] arr; // 存放數(shù)據(jù)// 創(chuàng)建隊列的構(gòu)造器public arrayQueue(int MaxSize){maxsize = MaxSize; // 最大值arr = new int[maxsize];rear = -1; // 指向隊列尾部的數(shù)據(jù)，包含尾部數(shù)據(jù)front = -1; // 指向隊列的頭部的前一個位置，不包含尾部數(shù)據(jù)}// 判斷隊列是否滿，滿就不能插入數(shù)據(jù)，滿就可以讀取數(shù)據(jù)public boolean isFull(){return rear == maxsize-1;}// 判斷隊列是否為空，空就不能讀取數(shù)據(jù)，空就能插入數(shù)據(jù)public boolean isEmpty(){return rear == front;}// 添加數(shù)據(jù)到隊列public void addQueue(int n){// 判斷隊列是否滿了if(isFull()){System.out.println("隊列已經(jīng)滿了，不能添加數(shù)據(jù)");return;}rear++; // rear需要往后移動arr[rear] = n; //添加數(shù)據(jù)}// 獲取隊列的數(shù)據(jù) （出隊列）public int getQueu(){// 判斷數(shù)據(jù)是否為空if(isEmpty()){
//            System.out.println("隊列數(shù)據(jù)為空");
//            return 0;throw new RuntimeException("隊列數(shù)據(jù)為空");}front++; //front數(shù)據(jù)后移return arr[front];}// 顯示隊列的所有數(shù)據(jù)public void showQueue(){// 判斷隊列是否為空if (isEmpty()){
//            throw new RuntimeException("隊列數(shù)據(jù)為空，不能展示數(shù)據(jù)");System.out.println("隊列數(shù)據(jù)為空，不能展示數(shù)據(jù)");return;}for (int i= front+1; i<=rear; i++){System.out.printf("arr[%d]=%d\n",i,arr[i]);}}//顯示隊列的頭數(shù)據(jù)，注意不是取出數(shù)據(jù)public int headQueue(){//判斷數(shù)據(jù)是否為空if (isEmpty()){throw new RuntimeException("數(shù)據(jù)為空");}return arr[front+1];}
}

注意：需要測試一下代碼

問題：

• 當(dāng)前這種形式的隊列數(shù)據(jù)有問題，front往后移動后，front前面的數(shù)據(jù)雖然是無效數(shù)據(jù)，但是想要添加數(shù)據(jù)是無法再添加數(shù)據(jù)的，這導(dǎo)致資源的浪費了
• 隊列不能重復(fù)使用，沒有達到復(fù)用的效果

解決辦法：

• 環(huán)形隊列

（二）數(shù)組模擬環(huán)形隊列

注意：

• rear 變量的含義發(fā)生了變換，和數(shù)組模擬隊列的不一樣了，現(xiàn)在是指向最后一個元素的后一個位置
• front 變量的含義也發(fā)生了變化，指向了隊列的第一個元素，也就是說==arr[front] 的第一個元素位置==，原來是第一個元素前一個位置。
• 隊列滿的條件：(rear+1)%maxsize = front
• 隊列為空：rear =front
• 隊列中有效個數(shù)：(rear+maxsize-front)%maxsize

代碼實現(xiàn)：

創(chuàng)建類：CircleArrayQueueDaemon

package com.lcj.queue;import jdk.nashorn.internal.ir.CallNode;import java.util.Scanner;/*
* 編寫人：lcj
* 編寫時間：20220815
* 編寫目的：學(xué)習(xí)環(huán)形隊列
* */
public class CircleArrayQueueDaemon {public static void main(String[] args){//測試思考//創(chuàng)建對象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):獲取對列數(shù)據(jù)");System.out.println("h(head):隊列頭部數(shù)據(jù)");System.out.println("n(num):隊列有效數(shù)據(jù)");key = scanner.next().charAt(0);switch (key){case 's':System.out.println("展示隊列數(shù)據(jù)");circleArray.showQueue();break;case 'a':System.out.println("添加數(shù)據(jù),請輸入數(shù)據(jù)");int value = scanner.nextInt();circleArray.addQueu(value);break;case 'e':System.out.println("退出程序");loop = false; // 跳出循環(huán)break;case 'g':try {System.out.println("獲取隊列的數(shù)據(jù)");int num = circleArray.getQueue();System.out.println("值："+num);}catch (Exception e){e.getMessage();}break;case 'h':System.out.print("獲取隊列的頭部數(shù)據(jù):");System.out.println(circleArray.getHead());break;case 'n':System.out.println("查看隊列的有效數(shù)據(jù)" );int size = circleArray.size();System.out.println("有效數(shù)據(jù)為："+size);break;default:System.out.println("數(shù)據(jù)輸入有誤請重新輸入");break;}}System.out.println("程序已經(jīng)退出成功");}
}
class CircleArray{private int maxsize;  // 隊列長度private int front; // 隊列的頭private int rear; // 隊列的尾private int[] arr; // 隊列的數(shù)組// 創(chuàng)建構(gòu)造器public CircleArray(int maxsize) {this.maxsize = maxsize;front = 0; // 指向元素第一位置rear = 0; // 指向元素的第二個位置，即 尾部序號+1arr = new int[maxsize];}// 判斷是否滿了public boolean isFull(){return (rear+1)%maxsize == front;}// 判斷是否為空public boolean isEmpty(){return rear==front;}//添加數(shù)據(jù)，會不會添加數(shù)據(jù)導(dǎo)致覆蓋原來的數(shù)據(jù)public void addQueu(int n){// 判斷是否滿if(isFull() && size()<maxsize){System.out.println("隊列已滿，不能添加數(shù)據(jù)");return;}arr[rear] = n;
//        rear++; // rear往后移動數(shù)據(jù) erro:不能實現(xiàn)環(huán)形隊列rear=(rear+1)%maxsize;// 注意：這里rear+1 == rear++}//取出數(shù)據(jù)public int getQueue(){//判斷數(shù)據(jù)是否為空if(isEmpty()){throw new RuntimeException("數(shù)據(jù)為空，不能取數(shù)");}// 取出數(shù)據(jù)后，front需要往后移動，需要一個值來保存數(shù)據(jù)//方法一：int value = arr[front];
//        front++;front = (front+1)%maxsize; //front+1 = front++return value;//方法二：
//        front = (front+1)%maxsize;
//        return arr[(front-1)%maxsize];}// 獲取數(shù)據(jù)頭部public  int getHead(){return arr[front];}// 顯示所有的數(shù)據(jù)public void showQueue(){//判斷隊列是否為空if(isEmpty()){System.out.println("隊列為空");return;}//遍歷數(shù)據(jù),front+（rear-front+maxsize）%maxsizefor (int i=front;i < front+(rear-front+maxsize)%maxsize;i++){        // (rear-front+maxsize)%maxsize 有效數(shù)據(jù)System.out.printf("arr[%d]=%d\n",i%maxsize,arr[i%maxsize]);}}// 數(shù)據(jù)有效個數(shù)public int size(){return (rear+maxsize-front)%maxsize;}}

第三章：鏈表

一、鏈表

（一）鏈表介紹

鏈表是有序的列表

data域：數(shù)據(jù)

next域：地址

特點：

1. 鏈表是以節(jié)點的方式來存儲數(shù)據(jù)
2. 每一個節(jié)點包含data域，next域 （指向下一個節(jié)點）
3. 鏈表中的數(shù)據(jù)并不一定是連續(xù)存放的
4. 鏈表分為：
   • 帶頭節(jié)點的鏈表 （head節(jié)點：不存放具體的數(shù)據(jù)）
   • 沒有帶頭節(jié)點的鏈表

單鏈表的應(yīng)用實例

eg：單鏈表來管理水滸傳的人物圖

實現(xiàn)：代頭節(jié)點的單向鏈表

代碼實現(xiàn)

創(chuàng)建package：linkedlist，創(chuàng)建類：SingleLinkedListDemo

要求一：添加英雄，直接添加到鏈表的尾部中

package com.lcj.linkedlist;public class SignalLinkedList {public static void main(String[] args) {// 測試數(shù)據(jù)HeroNode hero1 = new HeroNode(1,"宋江","及時雨");HeroNode hero2 = new HeroNode(2,"宋江","及時雨");HeroNode hero3 = new HeroNode(3,"宋江","及時雨");// 創(chuàng)建鏈表管理器LinkedManager linkedManager = new LinkedManager();// 添加數(shù)據(jù)linkedManager.add(hero1);linkedManager.add(hero2);linkedManager.add(hero3);// 展示數(shù)據(jù)linkedManager.list();}}// 管理節(jié)點數(shù)據(jù)
class LinkedManager {//先創(chuàng)建一個頭節(jié)點數(shù)據(jù),但是并不存放數(shù)據(jù)private HeroNode head = new HeroNode(0, "", "");//添加節(jié)點到單鏈表中,但是數(shù)據(jù)需要添加到節(jié)點中的最后一個數(shù)據(jù)的Next為（Null）// 不考慮數(shù)據(jù)的編號public void add(HeroNode Node) {// 創(chuàng)建一個輔助指針來判斷數(shù)據(jù)是否到達尾部HeroNode tmp = head;// 遍歷循環(huán)while (true) {// 找最后節(jié)點數(shù)據(jù)if (tmp.next == null) {break;}// 如果沒有找到最后一個節(jié)點，需要往后移動tmp = tmp.next;}// 退出循環(huán)的時候，就是指向最后節(jié)點，現(xiàn)在需要添加新的節(jié)點tmp.next = Node;}// 顯示數(shù)據(jù)（遍歷數(shù)據(jù)）public void list(){//判斷鏈表是否為空,沒有指向其他的節(jié)點if(head.next == null){System.out.println("鏈表為空");return;}//頭節(jié)點不能動，需要創(chuàng)建輔助節(jié)點遍歷數(shù)據(jù)HeroNode tmp = head.next;while(true){//判斷是否到達最后if(tmp == null){
//                System.out.println("最后的");break;}// 數(shù)據(jù)節(jié)點信息System.out.println(tmp);// 將tmp往后移動tmp = tmp.next;}}
}
// 創(chuàng)建節(jié)點數(shù)據(jù)
class HeroNode{public int no; // 創(chuàng)建序號public String name;//英雄名字public String nickname; // 昵稱public HeroNode next; //指向下一個節(jié)點 ，值為java的引用，類似于c語言的指針//創(chuàng)建構(gòu)造器public HeroNode(int no, String name, String nickname) {this.no = no;this.name = name;this.nickname = nickname;}
// 數(shù)據(jù)進行格式，便于后期數(shù)據(jù)的展示@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +", nickname='" + nickname + '\'' +'}';}
}

要求二：根據(jù)英雄的編號進行數(shù)據(jù)排序、修改節(jié)點值

添加數(shù)據(jù)

需要按照編號的順序添加

1. 首先找到新添加的節(jié)點位置
2. 新的節(jié)點數(shù)據(jù).next = tmp.next
3. tmp.next = 新節(jié)點

思路：

• 找到序號前一個位置
• 插入數(shù)據(jù)

//按照數(shù)據(jù)序號順序進行添加數(shù)據(jù)public void addByOrder(HeroNode node){HeroNode tmp = head;// 查找序號位置時，tmp要指向插入數(shù)據(jù)的前一個位置，不是能插入數(shù)據(jù)boolean flag = false; // 判斷需要的編號是否存在，存在就不能添加while(true){if(tmp.next == null){//找到數(shù)據(jù)鏈尾了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("序號存在，請重新輸入數(shù)據(jù)");}else{node.next = tmp.next; //新節(jié)點的后序是tmp的后序tmp.next = node; // 舊節(jié)點的后序等于新節(jié)點}}

修改數(shù)據(jù)

// 修改節(jié)點的信息，根據(jù)no編號來修改，即no編號不能改// 根據(jù)node的no序號來進行修改public void update(HeroNode node){if(head.next == null){System.out.println("鏈表為空");return;}//找需要修改的序號，因此需要進行遍歷數(shù)據(jù)/* 版本一boolean flage = true;HeroNode tmp = head.next; // 創(chuàng)建臨時的引用來遍歷數(shù)據(jù)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; // 創(chuàng)建臨時的引用來遍歷數(shù)據(jù)while (true){if(tmp == null){ //到達鏈尾break;}if (tmp.no == node.no){flage = true;break;}else{tmp = tmp.next;}}// flage 為true會執(zhí)行文件if(flage){tmp.name = node.name;tmp.nickname = node.nickname;}else{System.out.println("該節(jié)點數(shù)據(jù)沒有找到");}}

刪除節(jié)點

1. 找到需要刪除點的前一個點 tmp
2. tmp.next = tmp.next.next
3. 被刪除的節(jié)點，將不會有其引用指向，會被垃圾回收機制回收

// 刪除節(jié)點//思路：找到需要刪除點的前一個點 tmp；public void del(int no){HeroNode tmp = head;boolean flag = false;   // 標(biāo)志是否找到待刪除節(jié)點while(true){if(tmp.next == null){ // 位置處于數(shù)據(jù)的鏈尾break;}if(tmp.next.no == no){ //找到待刪除節(jié)點的前一個節(jié)點的tmpflag = true;break;}tmp = tmp.next; //tmp后移，遍歷}//判斷flagif (flag){tmp.next = tmp.next.next;}else{System.out.println("該節(jié)點不存在");}}

完整代碼

完整代碼：添加數(shù)據(jù)（有序添加、排序添加）、修改數(shù)據(jù)、刪除數(shù)據(jù)、

package com.lcj.linkedlist;public class SignalLinkedList {public static void main(String[] args) {// 測試數(shù)據(jù)HeroNode hero1 = new HeroNode(1,"宋江","及時雨");HeroNode hero2 = new HeroNode(2,"宋江","及時雨");HeroNode hero3 = new HeroNode(3,"宋江","及時雨");// 創(chuàng)建鏈表管理器LinkedManager linkedManager = new LinkedManager();// 添加數(shù)據(jù)
//        linkedManager.add(hero1);
//        linkedManager.add(hero2);
//        linkedManager.add(hero3);//順序添加數(shù)據(jù)linkedManager.addByOrder(hero3);linkedManager.addByOrder(hero2);linkedManager.addByOrder(hero1);// 展示數(shù)據(jù)linkedManager.list();System.out.println("======================================");// 修改節(jié)點數(shù)據(jù)HeroNode hero4 = new HeroNode(3,"法外張三","羅翔");linkedManager.update(hero4);linkedManager.list();// 展示數(shù)據(jù)// 刪除節(jié)點linkedManager.del(1);System.out.println("==========刪除數(shù)據(jù)后=========");linkedManager.list();}
}// 管理節(jié)點數(shù)據(jù)
class LinkedManager {//先創(chuàng)建一個頭節(jié)點數(shù)據(jù),但是并不存放數(shù)據(jù)private HeroNode head = new HeroNode(0, "", "");//添加節(jié)點到單鏈表中,但是數(shù)據(jù)需要添加到節(jié)點中的最后一個數(shù)據(jù)的Next為（Null）// 不考慮數(shù)據(jù)的編號public void add(HeroNode Node) {// 創(chuàng)建一個輔助指針來判斷數(shù)據(jù)是否到達尾部HeroNode tmp = head;// 遍歷循環(huán)while (true) {// 找最后節(jié)點數(shù)據(jù)if (tmp.next == null) {break;}// 如果沒有找到最后一個節(jié)點，需要往后移動tmp = tmp.next;}// 退出循環(huán)的時候，就是指向最后節(jié)點，現(xiàn)在需要添加新的節(jié)點tmp.next = Node;}// 修改節(jié)點的信息，根據(jù)no編號來修改，即no編號不能改// 根據(jù)node的no序號來進行修改public void update(HeroNode node){if(head.next == null){System.out.println("鏈表為空");return;}//找需要修改的序號，因此需要進行遍歷數(shù)據(jù)/* 版本一boolean flage = true;HeroNode tmp = head.next; // 創(chuàng)建臨時的引用來遍歷數(shù)據(jù)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; // 創(chuàng)建臨時的引用來遍歷數(shù)據(jù)while (true){if(tmp == null){ //到達鏈尾break;}if (tmp.no == node.no){flage = true;break;}else{tmp = tmp.next;}}// flage 為true會執(zhí)行文件if(flage){tmp.name = node.name;tmp.nickname = node.nickname;}else{System.out.println("該節(jié)點數(shù)據(jù)沒有找到");}}//按照數(shù)據(jù)序號順序進行添加數(shù)據(jù)public void addByOrder(HeroNode node){HeroNode tmp = head;// 查找序號位置時，tmp要指向插入數(shù)據(jù)的前一個位置，不是能插入數(shù)據(jù)boolean flag = false; // 判斷需要的編號是否存在，存在就不能添加while(true){if(tmp.next == null){//找到數(shù)據(jù)鏈尾了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("序號存在，請重新輸入數(shù)據(jù)");}else{node.next = tmp.next; //新節(jié)點的后序是tmp的后序tmp.next = node; // 舊節(jié)點的后序等于新節(jié)點}}// 刪除節(jié)點//思路：找到需要刪除點的前一個點 tmp；public void del(int no){HeroNode tmp = head;boolean flag = false;   // 標(biāo)志是否找到待刪除節(jié)點while(true){if(tmp.next == null){ // 位置處于數(shù)據(jù)的鏈尾break;}if(tmp.next.no == no){ //找到待刪除節(jié)點的前一個節(jié)點的tmpflag = true;break;}tmp = tmp.next; //tmp后移，遍歷}//判斷flagif (flag){tmp.next = tmp.next.next;}else{System.out.println("該節(jié)點不存在");}}// 顯示數(shù)據(jù)（遍歷數(shù)據(jù)）public void list(){//判斷鏈表是否為空,沒有指向其他的節(jié)點if(head.next == null){System.out.println("鏈表為空");return;}//頭節(jié)點不能動，需要創(chuàng)建輔助節(jié)點遍歷數(shù)據(jù)HeroNode tmp = head.next;while(true){//判斷是否到達最后if(tmp == null){
//                System.out.println("最后的");break;}// 數(shù)據(jù)節(jié)點信息System.out.println(tmp);// 將tmp往后移動tmp = tmp.next;}}
}
// 創(chuàng)建節(jié)點數(shù)據(jù)
class HeroNode{public int no; // 創(chuàng)建序號public String name;//英雄名字public String nickname; // 昵稱public HeroNode next; //指向下一個節(jié)點 ，值為java的引用，類似于c語言的指針//創(chuàng)建構(gòu)造器public HeroNode(int no, String name, String nickname) {this.no = no;this.name = name;this.nickname = nickname;}
// 數(shù)據(jù)進行格式，便于后期數(shù)據(jù)的展示@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +", nickname='" + nickname + '\'' +'}';}
}

（二）面試題

1. 求單鏈表中有效節(jié)點的個數(shù)
2. 查找單鏈表中的倒數(shù)第K個節(jié)點——新浪面試
3. 單鏈表的反轉(zhuǎn) ——騰訊面試
4. 從尾到頭打印單鏈表——百度：要求（1）反向遍歷 （2）stack棧
5. 合并兩個有序的單鏈表，合并之后的鏈表依然有序

題一：求單鏈表中有效節(jié)點的個數(shù)

注意：不要將頭節(jié)點也統(tǒng)計進去

    public void nodeNum(){HeroNode temp = head.next;int count=0;while(true){//如果到達鏈尾if(temp == null){break;}temp = temp.next;count++;}System.out.println("節(jié)點個數(shù)為："+count);}

題目二：查找單鏈表中的倒數(shù)第K個節(jié)點——新浪面試

• 思路：
  • 先遍歷一下數(shù)據(jù)，統(tǒng)計數(shù)據(jù)的有效個數(shù)
  • 有效個數(shù) - k，得到需要找的

public void findLastIndex(int k){HeroNode temp = head.next;// 統(tǒng)計個數(shù)int count=0;while(true){//如果到達鏈尾if(temp == null){break;}temp = temp.next;count++;}// 判斷k是否有效if(k > count|| k<=0){System.out.println("超出了鏈表范圍");return;}else{  //讀取第k個值的位置int flag = count - k;HeroNode temp1 = head.next;for(int i=0;i<flag;i++){temp1 = temp1.next;}System.out.printf("序號：%d \t 名字：%s",temp1.no,temp1.name);}        }

注意：if(k > count|| k<=0)我遺漏了k<=0的問題

題目三：單鏈表的反轉(zhuǎn) ——騰訊面試

• 思路：（頭插入數(shù)據(jù)）

  • 新建一個鏈表，用來存儲數(shù)據(jù)
  • 將舊鏈表中的節(jié)點數(shù)據(jù)移動到新節(jié)點中
  • 新鏈表指向舊鏈表的頭

  public static  void reversetList(HeroNode head){//判斷鏈表是否為空,或者只有一個節(jié)點的，無需反轉(zhuǎn)if (head.next == null || head.next.next ==null){return;}HeroNode tmp = head.next;HeroNode next = null;  //用來指向tmp的下一個節(jié)點數(shù)據(jù)HeroNode reversetHead = new HeroNode(0,"",""); //新鏈表的頭節(jié)點數(shù)// 遍歷鏈表,將舊鏈表中的節(jié)點數(shù)據(jù)移動到新節(jié)點中while(tmp != null){next = tmp.next ; //用于保存當(dāng)前節(jié)點下一個節(jié)點數(shù)據(jù)tmp.next = reversetHead.next;reversetHead.next = tmp;tmp = next;  //往后移動}head.next = reversetHead.next;}
  

  核心代碼：

  next = tmp.next ; //用于保存當(dāng)前節(jié)點下一個節(jié)點數(shù)據(jù)
  tmp.next = reversetHead.next;
  reversetHead.next = tmp;
  tmp = next; //往后移動

題目四：從尾到頭打印單鏈表——百度：要求（1）反向遍歷 （2）stack棧

• 方法一：先將單鏈表進行反轉(zhuǎn)操作，然后再遍歷即可，但是不建議使用，破壞數(shù)據(jù)的原結(jié)構(gòu)

• 方法二：利用棧將各個節(jié)點的數(shù)據(jù)壓入到棧中，然后利用棧的先進后出特點

   //利用棧將各個節(jié)點的數(shù)據(jù)壓入到棧中，然后利用棧的==先進后出==特點public static void reserverPrinter(HeroNode head){if(head.next == null){return;}Stack<HeroNode> stack = new Stack<>();HeroNode tmp = head.next;//數(shù)據(jù)入棧while (tmp != null){ //數(shù)據(jù)不能為空，為空代表到達鏈尾stack.push(tmp);//stack中添加數(shù)據(jù)pushtmp = tmp.next;}//數(shù)據(jù)出棧while(stack.size()>0){System.out.println(stack.pop()); //pop 將數(shù)據(jù)彈出}}
  

題目五：合并兩個有序的單鏈表，合并之后的鏈表依然有序

二、雙鏈表

（一）、雙向鏈表的介紹

雙向鏈表添加了pre，目的：用它來指向節(jié)點的前一個節(jié)點

雙向節(jié)點刪除數(shù)據(jù)：

• 可以指向待刪除的節(jié)點 temp

• temp.pre.next = temp.next

• temp.next.pre = temp.pre

單鏈表存在的問題：

1. 單向鏈表查找的方向只能是一個方向，而雙向鏈表可以向前或者向后查找
2. 單向鏈表不能自我刪除，需要靠輔助節(jié)點，而雙向鏈表可以自我刪除

?

(二) 、應(yīng)用案例

實現(xiàn)英雄的案列

創(chuàng)建類：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,"宋江","及時雨");//創(chuàng)建一個雙向鏈表DoubleLinkedList doubleLinkedList = new DoubleLinkedList();doubleLinkedList.add(hero2);doubleLinkedList.add(hero1);doubleLinkedList.add(hero3);//數(shù)據(jù)展示doubleLinkedList.list();// 數(shù)據(jù)修改System.out.println("==========數(shù)據(jù)修改============");HeroNode2 hero4 = new HeroNode2(3,"張三","及時雨");doubleLinkedList.update(hero4);doubleLinkedList.list();//數(shù)據(jù)刪除System.out.println("==========數(shù)據(jù)刪除==========");doubleLinkedList.del(3);doubleLinkedList.list();//添加數(shù)據(jù)System.out.println("===========添加數(shù)據(jù)=========");HeroNode2 hero5 = new HeroNode2(5,"lisi","李四");doubleLinkedList.add(hero5);doubleLinkedList.list();}
}
// 管理雙向鏈表
class DoubleLinkedList{private HeroNode2 head = new HeroNode2(0,"","");// 顯示數(shù)據(jù)（遍歷數(shù)據(jù)）public void list(){//判斷鏈表是否為空,沒有指向其他的節(jié)點if(head.next == null){System.out.println("鏈表為空");return;}//頭節(jié)點不能動，需要創(chuàng)建輔助節(jié)點遍歷數(shù)據(jù)HeroNode2 tmp = head.next;while(true){//判斷是否到達最后if(tmp == null){
//                System.out.println("最后的");break;}// 數(shù)據(jù)節(jié)點信息System.out.println(tmp);// 將tmp往后移動tmp = tmp.next;}}//添加數(shù)據(jù)到鏈表的末尾//思路：找到鏈表末尾public void add(HeroNode2 Node) {// 創(chuàng)建一個輔助指針來判斷數(shù)據(jù)是否到達尾部HeroNode2 tmp = head;// 遍歷循環(huán)while (true) {// 找最后節(jié)點數(shù)據(jù)if (tmp.next == null) {break;}// 如果沒有找到最后一個節(jié)點，需要往后移動tmp = tmp.next;}// 退出循環(huán)的時候，就是指向最后節(jié)點，現(xiàn)在需要添加新的節(jié)點，形成雙向鏈tmp.next = Node;Node.pre = tmp;}//添加數(shù)據(jù)    要求：按照序號進行添加數(shù)據(jù)public void addByOrder(HeroNode2 node){HeroNode2 tmp = head;// 查找序號位置時，tmp要指向插入數(shù)據(jù)的前一個位置，不是能插入數(shù)據(jù)boolean flag = false; // 判斷需要的編號是否存在，存在就不能添加while(true){if(tmp.next == null){//找到數(shù)據(jù)鏈尾了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("序號存在，請重新輸入數(shù)據(jù)");}else{node.next = tmp.next; //新節(jié)點的后序是tmp的后序tmp.next = node; // 舊節(jié)點的后序等于新節(jié)點}}//修改節(jié)點內(nèi)容//思路：主要是找到節(jié)點的位置// 根據(jù)node的no序號來進行修改，public void update(HeroNode2 node){if(head.next == null){System.out.println("鏈表為空");return;}//找需要修改的序號，因此需要進行遍歷數(shù)據(jù)/* 版本一boolean flage = true;HeroNode tmp = head.next; // 創(chuàng)建臨時的引用來遍歷數(shù)據(jù)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; // 創(chuàng)建臨時的引用來遍歷數(shù)據(jù)while (true){if(tmp == null){ //到達鏈尾break;}if (tmp.no == node.no){flage = true;break;}else{tmp = tmp.next;}}// flage 為true會執(zhí)行文件if(flage){tmp.name = node.name;tmp.nickname = node.nickname;}else{System.out.println("該節(jié)點數(shù)據(jù)沒有找到");}}//刪除節(jié)點數(shù)// 只需要直接找到需要刪除的節(jié)點，不需要像單鏈表一樣找到前面的節(jié)點，再進行數(shù)據(jù)刪除public void del(int no){//判斷數(shù)據(jù)是否為空if(head.next == null){System.out.println("數(shù)據(jù)為空");return;}HeroNode2 tmp = head.next;boolean flag = false;   // 標(biāo)志是否找到待刪除節(jié)點while(true){if(tmp == null){ // 位置處于數(shù)據(jù)的鏈尾break;}if(tmp.no == no){ //找到待刪除節(jié)點的前一個節(jié)點的tmpflag = true;break;}tmp = tmp.next; //tmp后移，遍歷}//判斷flagif (flag){tmp.pre.next = tmp.next;// 如果是最后一個節(jié)點，不需要執(zhí)行這個，否則會出現(xiàn)空指針的問題if(tmp.next !=null) {tmp.next.pre = tmp.pre;}}else{System.out.println("該節(jié)點不存在");
class HeroNode2{public int no;public String name;public String nickname;public HeroNode2 next;  //指向下一個節(jié)點public HeroNode2 pre;  // 指向前一個節(jié)點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 + '\'' +'}';}

三、單向環(huán)形鏈表應(yīng)用場景

（一）約瑟夫問題

人數(shù) n=5

開始序號： k= 1

取出數(shù)據(jù)間隔 m=2

（二） 代碼實現(xiàn)

要求：

• 構(gòu)建單向環(huán)形鏈表

  • 創(chuàng)建第一個節(jié)點，通過first指向該節(jié)點，并形成環(huán)形
  • 當(dāng)每創(chuàng)建創(chuàng)建一個新的節(jié)點，將該節(jié)點加入到鏈表中

• 遍歷環(huán)形鏈表

  • 通過一個輔助指針 tmp ，指向first 節(jié)點
  • 通過while循環(huán)進行統(tǒng)計，循環(huán)終止條件 tmp.next = first

• 創(chuàng)建出隊列的編號序列

  • 人數(shù) n=5

    開始序號： k= 1

    取出數(shù)據(jù)間隔 m=2

  • 創(chuàng)建輔助節(jié)點 helper，指向代刪除的節(jié)點的前一個節(jié)點，注意起始位置位于環(huán)形列表的最后一個位置 ，報數(shù)自己也需要報一次

    補充：先將first 和helper 需要移動到k-1的位置

  • 報數(shù)時，讓first和helper 移動m-1次

  • 刪除節(jié)點：

    • first = first.next
    • per.next =first

創(chuàng)建類：Josephu

package com.lcj.linkedlist;
/*
* 編寫目的：學(xué)習(xí)約瑟夫問題，了解單向環(huán)形鏈表
* 類似于丟手絹的游戲，只是固定了次數(shù)
* */
public class Joseph {public static void main(String[] args){// 測試CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
//        circleSingleLinkedList.addBoy(5);  // 創(chuàng)建5個節(jié)點
//        circleSingleLinkedList.showBody();//出圈測試int startNum = 2;int countNum = 2;int nums = 10;circleSingleLinkedList.addBoy(nums);circleSingleLinkedList.showBody();circleSingleLinkedList.countBoy(startNum,countNum,nums);}
}//創(chuàng)建單向環(huán)形鏈表
class CircleSingleLinkedList{// 創(chuàng)建一個first節(jié)點，但是沒有編號的private Boy first = null;//添加節(jié)點數(shù)據(jù)，構(gòu)建成一個環(huán)形的鏈表// nums 的數(shù)量為 創(chuàng)建節(jié)點的個數(shù)public void addBoy(int nums){//判斷nums 的個數(shù)if(nums < 1){System.out.println("輸入nums的值不正確");return;}Boy curBoy = null; //輔助指針，幫助構(gòu)建形式鏈表// 創(chuàng)建環(huán)形鏈表for (int i = 1; i <= nums ; i++) {Boy boy = new Boy(i);if (i==1){first = boy;first.setNext(first); // first 的后序是自己本身，這樣才能構(gòu)成環(huán)curBoy = first;}else{curBoy.setNext(boy); // 連接新的節(jié)boy.setNext(first); // 形成 環(huán)形curBoy = boy; //  將輔助節(jié)點往新的節(jié)點進行移動}}}// 遍歷當(dāng)前的環(huán)形鏈表public void showBody(){// 判斷鏈表是否為空if(first == null){System.out.println("鏈表為空");return;}// 創(chuàng)建輔助節(jié)點Boy curBoy1 = first;while (true){System.out.printf("小朋友編號：%d\n", curBoy1.getNo());if (curBoy1.getNext() == first) {System.out.println("數(shù)據(jù)遍歷完成");break;}curBoy1 = curBoy1.getNext();  //指針往后移動}}/*
* startNo 是從第幾個小孩開始數(shù)數(shù)
* countNum 間隔的人數(shù)
* nums 小孩人數(shù)
* */public void countBoy(int startNo,int countNum,int nums){if(first ==null || startNo <1 || startNo > nums){System.out.println("參數(shù)輸入有誤");return;}//創(chuàng)建一個輔助節(jié)點數(shù)據(jù)Boy helper = first;//將helper指向鏈尾，即first的前一個節(jié)點上，目的是便于刪除數(shù)據(jù)while(true){if(helper.getNext() == first){ //判斷helper是否到達鏈尾，主要是為了刪除數(shù)據(jù)時，指向刪除點的前一個位置break;}helper = helper.getNext();}// 將frist和helper的移動startNo-1的位置for (int i = 0; i < startNo-1; i++) {helper = helper.getNext();first = first.getNext();}// 小孩子報數(shù)，讓first和helper移動countNum -1次，然后出圈（刪除）while(true){if(helper == first){ // 只有一個數(shù)據(jù)，helper是在first前面的break;}//first和helper移動countNum -1次for (int i = 0; i < countNum-1; i++) {helper = helper.getNext();first = first.getNext();}//first指向節(jié)點System.out.printf("小孩%d出圈\n",first.getNo());// 刪除數(shù)據(jù)first = first.getNext();helper.setNext(first);}System.out.printf("最后的節(jié)點為%d\n",first.getNo());}
}//創(chuàng)建節(jié)點 ，名字為boy
class Boy{private int no; // 節(jié)點的編號private Boy next; // 指向下一個節(jié)點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;}
}

注意：只有一個節(jié)點可以自己指向自己

第四章：棧

（一）、棧介紹

1. 棧是一種先進先出（first in last out）的有效列表

2. 允許插入和刪除的一端，為變化的一端，稱為棧頂（Top），另一端固定為棧底（Bottom），

3. 棧的應(yīng)用

   

   中綴表達式轉(zhuǎn)后綴表達式 是面試中常考的

（二）數(shù)組模擬棧的思路分析

1. 使用數(shù)組來模擬棧

2. 定義一個top，來表示棧頂，初始化為-1

3. 入棧的操作，當(dāng)數(shù)據(jù)加入棧時，top++，stack[top]=data;

4. 出棧的操作，int value = stack[top], top–

創(chuàng)建packe：com.lcj.Stack

創(chuàng)建class：ArrayStackDemo

package com.lcj.stack;import com.sun.imageio.plugins.wbmp.WBMPImageReader;import java.util.Scanner;// 數(shù)組棧的學(xué)習(xí)
public class ArrayStackDamon {public static void main(String[] args){//數(shù)組棧測試ArrayStack stack = new ArrayStack(4);String key = "";  //輸入的數(shù)據(jù)boolean loop = true;  //判斷循環(huán)的條件Scanner scanner = new Scanner(System.in);// 測試菜單while(loop){System.out.println("輸入exit:退出");System.out.println("輸入push數(shù)據(jù)入棧");System.out.println("輸入pop數(shù)據(jù)出棧");System.out.println("輸入show 顯示棧");key = scanner.next();switch (key){case "show":stack.list();break;case "push":System.out.println("請輸入需要插入的數(shù)據(jù)");int value = scanner.nextInt();stack.push(1);break;case "exit":System.out.println("退出");loop = false;break;case "pop":System.out.println("數(shù)據(jù)出棧");try{int v = stack.pop();System.out.println("出棧的數(shù)值為"+v);}catch(Exception e){System.out.println(e.getMessage());}default:break;}}System.out.println("退出成功");}
}//棧
class ArrayStack{private int top = -1; //標(biāo)記棧頂?shù)奈恢?/span>private int maxSize;  //棧的最大長度private int stack[]; // 棧數(shù)組進行存儲數(shù)據(jù)//構(gòu)建器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開始計算的}//數(shù)據(jù)入棧public void push(int value){//判斷是否棧滿if (isFull()){System.out.println("棧滿");return;}top++; // top指向的是有數(shù)據(jù)的棧頂stack[top] = value;}//數(shù)據(jù)出棧public int pop(){//判斷數(shù)據(jù)是否為空if (isEmpty()){throw new RuntimeException("棧為空"); // 因為這點數(shù)據(jù)結(jié)果有類型，需要使用運行異常來解決}int value = stack[top];top--;return value;}// 遍歷數(shù)據(jù)public void list(){//判斷數(shù)據(jù)是否為空if (isEmpty()) {System.out.println("棧為空");return;}for (int i = top; i >= 0 ; i--) {System.out.printf("stack[%d]=%d\n",i,stack[i]);}}
}

（三）練習(xí)：使用鏈表來模擬棧

思路一：雙鏈表doubleLinked

• 創(chuàng)建雙鏈表doubleLinked，兩個指針 ：next、pre，棧頂指針：top
• 入棧：節(jié)點tmp 添加到鏈尾，前一個節(jié)點.next = tmp , 前一個節(jié)點的.next.pre = tmp
• 出棧：tmp.pre.next = null ,tmp.pre = null,
• 遍歷數(shù)據(jù)

版本一：雙鏈表實現(xiàn)棧

package com.lcj.stack;
/*
* 創(chuàng)建人：lcj
* 創(chuàng)建時間：2022年8月29
* 目的：用鏈表來實現(xiàn)棧
* */
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{//創(chuàng)建一個first的頭節(jié)點doubleLinked head =  new doubleLinked(1);//top 確定棧頂位置public doubleLinked topSite(){doubleLinked tmp = head; //創(chuàng)建一個輔助節(jié)點while (true){if(tmp.getNext() == null){//                break;
//                System.out.println("1");return tmp;}tmp = tmp.getNext();  //往后移動}}//添加數(shù)據(jù)public void add(doubleLinked node){doubleLinked tmp = topSite(); //創(chuàng)建一個輔助節(jié)點tmp.setNext(node);  // 連接nexttmp.getNext().setPre(tmp); // 將新節(jié)點的pre連接到前一節(jié)點上
//        System.out.println(tmp.getNext().getValue());}//展示數(shù)據(jù)public void show(){doubleLinked top = topSite();while(true){if (top.getPre()==null){ // 到達 head 之前break;}System.out.println(top.getValue());top = top.getPre(); //將輔助指針往前面進行移動}}//數(shù)據(jù)出棧public int pop(){doubleLinked top = topSite(); // 獲得棧頂int value = top.getValue();top.getPre().setNext(null);top.setPre(null);System.out.println("刪除");return value;}
}// 用雙鏈表來實現(xiàn)
class doubleLinked{private int value; // 鏈表中保存的值private doubleLinked next; //指向后序private doubleLinked pre; //指向前序private doubleLinked top; // 棧頂//構(gòu)建對象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;}
}

版本二：雙鏈表實現(xiàn)棧

package com.lcj.stack;
/*
* 創(chuàng)建人：lcj
* 創(chuàng)建時間：2022年8月29
* 目的：用鏈表來實現(xiàn)棧
* */
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{//創(chuàng)建一個first的頭節(jié)點doubleLinked head =  new doubleLinked(1);//top 確定棧頂位置public doubleLinked topSite(){doubleLinked tmp = head; //創(chuàng)建一個輔助節(jié)點while (true){if(tmp.next == null){//                break;
//                System.out.println("top找到");return tmp;}tmp = tmp.next;  //往后移動}}//添加數(shù)據(jù)public void add(doubleLinked node){doubleLinked tmp = topSite(); //創(chuàng)建一個輔助節(jié)點tmp.next = node;  // 連接nexttmp.next.pre = tmp; // 將新節(jié)點的pre連接到前一節(jié)點上}//展示數(shù)據(jù)public void show(){doubleLinked top = topSite();while(true){if (top.pre==null){ // 到達 head 之前break;}System.out.println(top.getValue());top = top.pre; //將輔助指針往前面進行移動}}//數(shù)據(jù)出棧public int pop(){doubleLinked top = topSite(); // 獲得棧頂int value = top.getValue();top.pre.next = null;top.pre = null;System.out.println("刪除");return value;}}// 用雙鏈表來實現(xiàn)
class doubleLinked{public int value; // 鏈表中保存的值public doubleLinked next; //指向后序public doubleLinked pre; //指向前序public doubleLinked top; // 棧頂//構(gòu)建對象public doubleLinked(int value) {this.value = value;}public int getValue() {return value;}public void setValue(int value) {this.value = value;}
}

思想二：創(chuàng)建一個單鏈表

• 創(chuàng)建一個singalLinked

• 添加鏈表的數(shù)據(jù)tmp ：前一節(jié)點.next = tmp

• 數(shù)據(jù)出棧：

  • 方法一：遍歷數(shù)據(jù)，找到最后一個數(shù)據(jù)，缺點時間過長
  • 方法二：將鏈表的反轉(zhuǎn)，將數(shù)據(jù)出棧后，由反轉(zhuǎn)回去

• 數(shù)據(jù)入棧：

  • 思路一：直接找到鏈尾進行插入數(shù)據(jù)

  

  注意：添加數(shù)據(jù)和數(shù)據(jù)出棧都需要，注意后面節(jié)點是否存在

版本三：單鏈表實現(xiàn)

package com.lcj.stack;
/** 創(chuàng)建人：lcj* 創(chuàng)建時間：2022年8月29* 目的：用單鏈表來實現(xiàn)棧* */
public class SingalLinkedStackDaemon {public  static void main(String[] args){// 測試StackLinked stack1 = new StackLinked();//添加數(shù)據(jù)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);// 展示數(shù)據(jù)System.out.println("展示數(shù)據(jù)");stack1.show();//數(shù)據(jù)出棧System.out.println("數(shù)據(jù)出棧");try {stack1.pop();stack1.pop();}catch (Exception e){System.out.println(e.getMessage());}stack1.show();}
}// 創(chuàng)建棧
class StackLinked{singalLinked head = new singalLinked(1); // 棧的頭節(jié)點，需要保持不動//添加數(shù)據(jù)和數(shù)據(jù)出棧都需要，注意后面節(jié)點是否存在，即棧是否空的情況public boolean isEmpty(){return  head.next == null;}//數(shù)據(jù)入棧public  void push(singalLinked node){//判斷鏈表是否空if (isEmpty()){head.next = node;  //直接將數(shù)據(jù)連接到node上，不需要連接后面的return;}// 鏈表為不空時node.next = head.next;  //  將后面連接head.next = node;  //將前面head連接}//數(shù)據(jù)出棧public int pop(){// 棧是否為空if (isEmpty()){throw  new RuntimeException("棧表為空");}// 棧只存在一個節(jié)點if (head.next.next == null ){head.next = null;return head.next.getValue();  // 返回被刪除的值}int value = head.next.getValue();head.next = head.next.next;  // 將head連接刪除的節(jié)點的后面一個return value;  // 返回被刪除的值}//展示數(shù)據(jù)public void show(){singalLinked tmp = head;//判斷是否空if (isEmpty()){System.out.println("棧為空");return;  //退出}while(true){//判斷數(shù)據(jù)是否到達鏈尾if(tmp.next == null){break;}tmp = tmp.next; //往后移動System.out.printf("%d\n",tmp.getValue());}}
}//創(chuàng)建單鏈表
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;}
}

版本四：單鏈表實現(xiàn) ，改變測試環(huán)境（推薦）

package com.lcj.stack;import java.util.Scanner;/** 創(chuàng)建人：lcj* 創(chuàng)建時間：2022年8月29* 目的：用單鏈表來實現(xiàn)棧* */
public class SingalLinkedStackDaemon {public  static void main(String[] args){/*  測一// 測試StackLinked stack1 = new StackLinked();//添加數(shù)據(jù)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);// 展示數(shù)據(jù)System.out.println("展示數(shù)據(jù)");stack1.show();//數(shù)據(jù)出棧System.out.println("數(shù)據(jù)出棧");try {stack1.pop();stack1.pop();}catch (Exception e){System.out.println(e.getMessage());}stack1.show();*///測試二StackLinked stack1 = new StackLinked();boolean loop = true ; // 循環(huán)跳出的條件Scanner scanner = new Scanner(System.in);String key = ""; // 輸入的關(guān)鍵字while(loop){System.out.println("輸入exit退出");System.out.println("輸入push數(shù)據(jù)入棧");System.out.println("輸入pop數(shù)據(jù)出棧");System.out.println("輸入show展示數(shù)據(jù)");key = scanner.next();switch (key){case  "exit":System.out.println("退出");loop = false;break;case "push":System.out.println("數(shù)據(jù)入棧");System.out.println("請輸入節(jié)點數(shù)據(jù)：");int index = scanner.nextInt();
//                    singalLinked Linked = new singalLinked(index);stack1.push(new singalLinked(index));break;case "pop":System.out.println("數(shù)據(jù)出棧");int a = stack1.pop();System.out.println("刪除的值為："+a);break;case "show":System.out.println("展示數(shù)據(jù)");stack1.show();break;default:System.out.println("輸入有誤");break;}}System.out.println("退出成功");}
}// 創(chuàng)建棧
class StackLinked{singalLinked head = new singalLinked(1); // 棧的頭節(jié)點，需要保持不動//添加數(shù)據(jù)和數(shù)據(jù)出棧都需要，注意后面節(jié)點是否存在，即棧是否空的情況public boolean isEmpty(){return  head.next == null;}//數(shù)據(jù)入棧public  void push(singalLinked node){//判斷鏈表是否空if (isEmpty()){head.next = node;  //直接將數(shù)據(jù)連接到node上，不需要連接后面的return;}// 鏈表為不空時node.next = head.next;  //  將后面連接head.next = node;  //將前面head連接}//數(shù)據(jù)出棧public int pop(){// 棧是否為空if (isEmpty()){throw  new RuntimeException("棧表為空");}// 棧只存在一個節(jié)點if (head.next.next == null ){head.next = null;return head.next.getValue();  // 返回被刪除的值}int value = head.next.getValue();head.next = head.next.next;  // 將head連接刪除的節(jié)點的后面一個return value;  // 返回被刪除的值}//展示數(shù)據(jù)public void show(){singalLinked tmp = head;//判斷是否空if (isEmpty()){System.out.println("棧為空");return;  //退出}while(true){//判斷數(shù)據(jù)是否到達鏈尾if(tmp.next == null){break;}tmp = tmp.next; //往后移動System.out.printf("%d\n",tmp.getValue());}}
}//創(chuàng)建單鏈表
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;}
}

（四）棧實現(xiàn)綜合案例——計算器

思路：創(chuàng)建兩個棧，一個數(shù)棧 numStack（用于存儲數(shù)值） ，一個符號棧 operStack（存儲符號）

1. 通過一個index來判斷計算表達式中數(shù)值和符號

2. 發(fā)現(xiàn)數(shù)值直接入數(shù)據(jù)棧

3. 如果發(fā)現(xiàn)是符號，需要分兩種情況：

   ? 3.1符號棧為空，直接添加到符號棧中

   ? 3.2符號棧已經(jīng)存在了，需要判斷待添加的符號和符號棧中棧頂?shù)姆?#xff0c;比較優(yōu)先級

   ? 3.2.1如果待入棧的符號大于棧頂?shù)?#xff0c;則直接入棧

   ? 3.2.2如果待入棧的符號小于、等于棧頂?shù)?#xff0c;則需要pop 兩個數(shù)棧中的，與pop符號棧的中的符號進行計算，并將運算結(jié)果和待入棧的符號分別入棧

4. 當(dāng)計算表達式掃描完成后，就順序從數(shù)據(jù)棧中和符號棧中pop出兩個數(shù)值和符合，并將結(jié)果放進數(shù)據(jù)棧中

5. 最后在數(shù)棧只有一個數(shù)字，即表達式的結(jié)果

   注意：符號棧是更加棧頂特點：先進后出，因此將優(yōu)先級高的后出。

創(chuàng)建class：calculatot

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 = "3+2*6-2";//創(chuàng)建兩個棧ArrayStack1 numStack = new ArrayStack1(20); //數(shù)棧ArrayStack1 operStack = new ArrayStack1(20); //符號棧//定義需要的相關(guān)變量int index = 0;  //用于掃描，表達式的int num1 = 0;int num2 = 0;int res = 0;int oper = 0;char ch = ' '; //符號保存到這里面的//通過while循環(huán)進行掃描表達式while (true){//依次得到expression的每一個字符ch = expression.substring(index,index+1).charAt(0);// substring(開始，結(jié)束)//判斷ch的類型進行下一步的操作if(operStack.isOper(ch)){ //如果是運算符//1. 判斷當(dāng)前的符號棧是否為空，為空直接入棧if (!operStack.isEmpty()){//2 如果待入棧的符號大于棧頂?shù)?#xff0c;則直接入棧//3 如果待入棧的符號小于、等于棧頂?shù)?/span>if (operStack.priority(ch) <= operStack.priority(operStack.peek())){num1 = numStack.pop();num2 = numStack.pop();oper = operStack.pop();res = numStack.cal(num1,num2,oper);//將結(jié)果入數(shù)棧numStack.push(res);//將符號入棧operStack.push(ch);} else {operStack.push(ch);}}else{ // 不為空operStack.push(ch);}}else{  //數(shù)字直接入棧numStack.push(ch - 48); //注意：ch是字符串，在ASCII碼中需要 - 48}//判斷是否掃描完index++;if(expression.length() <= index){break;}}//當(dāng)計算表達式掃描完成后，就**順序從數(shù)據(jù)棧中和符號棧中pop出兩個數(shù)值和符合**，并將結(jié)果放進數(shù)據(jù)棧中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("結(jié)果為:"+numStack.pop());}
}
//棧
class ArrayStack1{private int top = -1; //標(biāo)記棧頂?shù)奈恢?/span>private int maxSize;  //棧的最大長度private int stack[]; // 棧數(shù)組進行存儲數(shù)據(jù)//構(gòu)建器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開始計算的}//數(shù)據(jù)入棧public void push(int value){//判斷是否棧滿if (isFull()){System.out.println("棧滿");return;}top++; // top指向的是有數(shù)據(jù)的棧頂stack[top] = value;}//數(shù)據(jù)出棧public int pop(){//判斷數(shù)據(jù)是否為空if (isEmpty()){throw new RuntimeException("棧為空"); // 因為這點數(shù)據(jù)結(jié)果有類型，需要使用運行異常來解決}int value = stack[top];top--;return value;}// 遍歷數(shù)據(jù)public void list(){//判斷數(shù)據(jù)是否為空if (isEmpty()) {System.out.println("棧為空");return;}for (int i = top; i >= 0 ; i--) {System.out.printf("stack[%d]=%d\n",i,stack[i]);}}//查看棧頂?shù)闹?/span>public int peek(){return stack[top];}// 符號的優(yōu)先級，通過定義數(shù)值來表達符號的優(yōu)先級，數(shù)值越大優(yōu)先級越高// 目的直接將符號轉(zhuǎn)換為成為數(shù)組，便于更好的進行比較優(yōu)先級public int priority(int oper){  //oper 符號if(oper == '*' || oper == '/'){return 1;}else if (oper == '+' || oper == '-'){return 0;}else{return -1; //目前忽略了%、（）、[] 等符號}}//判斷是否為運算符,好處：不用判斷字符是否為數(shù)值public boolean isOper(char val){return val == '*' || val == '/' || val == '+' || val == '-';}//計算public int cal(int num1,int num2,int oper){int res = 0;// 返回的結(jié)果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;}}

缺點：只能計算數(shù)值為單個數(shù)據(jù)的，而不能計算數(shù)據(jù)為兩位數(shù)的

（五）棧的三種表達式

前綴（波蘭表達式）、中綴、后綴表達式（逆波蘭表達式）

注意：中綴轉(zhuǎn)后綴，再面試必問

前綴表達式相關(guān)知識

后綴表達式相關(guān)知識 ==>講解了中綴表達式到后綴表達式

后綴表達式的計算

1、前綴表達式

又被稱為波蘭表達式，運算符位于操作數(shù)之前

eg：（3+4）x 5- 6 ==》前綴表達式：- x + 3 4 5 6

補充知識：

從右往左

2、后綴表達式

從左往右

注意：

1. 通過兩個棧: 符號棧s1（存儲）、數(shù)據(jù)棧 s2來存儲運算符和數(shù)值

2. 從左至右掃描中綴表達式

3. 遇到數(shù)值直接入棧s2

4. 遇到操作符，需要分成以下情況：

   4.1 如果s1為空時，直接將**符號入棧s1**中，或者為 ( 時，也是==直接入棧s2中==

   4.2 不為空需要分成兩種情況：

   ? 4.2.1 當(dāng)待入棧的操作符，與棧頂?shù)牟僮鬟M行比較，棧頂操作符小于 等于 待入棧的操作符時，直接將待入棧的操作符直接入棧s1

   ? 4.2.2 當(dāng)待入棧的操作符，與棧頂?shù)牟僮鬟M行比較，棧頂操作符大于等待入棧的操作符時，**需要將操作符中的棧pop出棧頂， 并入棧到s2的中**

   ? 注意：待入棧還是需要和棧頂繼續(xù)比較，如果待入棧大于符號棧棧頂?shù)?/mark>（滿足4.2.1的條件），直接入棧。如果不滿足還是需要執(zhí) 行4.2.2中

   4.3 遇到左括號是直接入棧中，但是待入棧操作符為右括號時，需要將操作符棧的中的操作符pop出來，并pop出的操作符加入到s2中，一直都遇到操作符棧中的左操作符，停止pop。注意：左右括號去除掉，不用保存在操作符棧s1中

5. 重復(fù)第二步到第四步，一直到表達式掃描結(jié)束。

6. 掃描結(jié)束后，將s1中剩余的運算符依次出棧并加入到s2中

7. 依次彈出s2，s2出棧的逆序就是后綴表達式

將（3+4）* 5-6 轉(zhuǎn)換成后綴表達式

掃描到的元素:（3+4）*5-6	s2（棧底到棧頂 ）存儲數(shù)據(jù)	s1(棧底到棧頂) 存儲操作符	說明
(		(	s1棧為空，直接將操作符加入棧中
3	3	(	遇到數(shù)值直接加入到棧中
+	3	(+	如果直接有左括號，符號不用比較直接加入
4	3 4	(+	遇到數(shù)值直接加入到棧中
)	3 4 +		遇到右括號，需要將s1 pop出來，一直到pop都了右括號
*	3 4 +	*	s1棧為空，直接將操作符加入棧中
5	3 4 + 5	*	遇到數(shù)值直接加入到棧中
-	3 4 + 5 *	-	- 優(yōu) 先級比 * 低,需要將s1 pop 出來,加入到s2中,一直比較直到待入棧大于s1的棧頂,待入可以入棧中
6	3 4 + 5 * 6	-	掃描完后
	3 4 + 5 * 6 -		將s1全部pop到s2中

（六）逆波蘭計算器

目前是個位數(shù)據(jù)

創(chuàng)建類：PolandNotation

方法一：通過系統(tǒng)提供的棧stack來實現(xiàn)

將后綴表達式存儲到數(shù)組中，就不需要使用index進執(zhí)行指向，數(shù)組遍歷更加便捷

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來，實現(xiàn)逆波蘭計算器*/
public class PolandNotation {public static  void main(String[] args){//定義一個后綴表達式// （3+4）*5-6  =》 3 4 + 5 * 6 -String suffixExpression = "3 4 + 5 * 6 -"; //通過空格進行分割，便于后面分割//將"3 4 + 5 * 6 -" 放進ArrayList中List<String> rpnList = getListString(suffixExpression);//計算結(jié)果為：int res = cal(rpnList);System.out.println("計算結(jié)果為："+res);}//將后綴表達式放進到ArrayList中public static List<String> getListString(String expression){//將表達式：expression進行分割String[] split = expression.split(" ");List<String> list = new ArrayList<>();for (String s : split) {list.add(s);}return list;}//完成計算public static int cal(List<String> ls){//創(chuàng)建棧Stack<String> stack = new Stack<String>();for (String item : ls) {if (item.matches("\\d+")){ // 用正則表達式進行判斷多位數(shù)stack.push(item); // 數(shù)據(jù)直接入棧}else{  //為操作符//需要從stack中取出兩個值，并將計算結(jié)果進入到stacke中int num2 = Integer.parseInt(stack.pop());  // 棧的數(shù)據(jù)是字符串的，需要轉(zhuǎn)換為整數(shù)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;}//將結(jié)果入棧stack.push(res+""); //將整數(shù)轉(zhuǎn)換字符串，因為創(chuàng)建的是字符串的Stack}}//到最后stack中只有一個值，即結(jié)果return Integer.parseInt(stack.pop());}
}

注意：將數(shù)值類型的字符串轉(zhuǎn)換為int ： Interget.parseInt('1');

方法二：編寫一個數(shù)組棧

自己編寫一個數(shù)組棧，實現(xiàn)中綴表達式轉(zhuǎn)換為后綴表達式，再通過后綴表達式的計算

ArrayList操作方法：

• add（data） 添加數(shù)據(jù)
• get（index） 獲取值 （eg：index 下標(biāo)）
• set（index，值） 修改值
• remove（index） 刪除值
  注意: 字符串比較大小，使用== 是比較的字符串存儲的內(nèi)存位置是否相同，需要使用 equals進行比較

版本一：中綴表達式轉(zhuǎn)為后綴表達式

實現(xiàn)中綴表達式轉(zhuǎn)為后綴表達式

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，實現(xiàn)：*          1. 將中綴表達式轉(zhuǎn)換為后綴表達式，并輸出后綴表達式*          2.計算后綴表達式的數(shù)據(jù)結(jié)果*   中綴表達式:（3+4）*5-6  ==> 后綴表達式：3 4 + 5 * 6 -*/
public class PolandNotationStack {public static void main(String[] args){stackDemon stack = new stackDemon(new ArrayList<>());  //鏈表：存儲 后綴表達式的String exception = "(3+4)*5-6";
//        String exception = "()";
//        stack.push("1");
//        stack.show();
//        System.out.println( stack.transform("*"));//將中綴表達式 轉(zhuǎn)成 后綴表達try {stackDemon suffix = transsuffix(exception, stack);suffix.show();System.out.println(suffix.show());   //后綴表達式的結(jié)果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切片出的數(shù)據(jù)，可以直接從左到右進行遍歷for (String iteam : split) {// 1.如果數(shù)值直接加入if (iteam.matches("\\d+")){ //判斷是否為多個數(shù)值，通過正則表達式stack.push(iteam);  //數(shù)值存儲到stack中}else{//2 判斷operStack 中是否為空,直接將數(shù)據(jù)入棧,或者是左括號 (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：棧頂?shù)牟僮鞣?還有為空if (operStack.isEmpty() || operStack.compare(iteam, operStack.peek()) ){ //num1 待入棧的操作符 ，num2：棧頂?shù)牟僮鞣?/span>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())) {  // 不能為空，空了也沒有數(shù)據(jù)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;}
}//創(chuàng)建stack
class stackDemon{//創(chuàng)建toppublic int top = -1; // 初始位置為：-1//數(shù)組List<String>private List<String>  stack;public stackDemon(List<String> stack) {this.stack = stack;}//判斷是否為空public  boolean isEmpty(){return stack.size() == 0;  //大小為0}//數(shù)據(jù)入棧public void push(String key){stack.add(key);}//數(shù)據(jù)出棧public String pop(){String value = "";//判斷是否為空if (stack.size()!= 0) {value = stack.get(stack.size()-1);stack.remove(stack.size() - 1);  // 刪除最后一個數(shù)據(jù)}return value;}//展示數(shù)據(jù)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;}// 展示棧頂?shù)脑?/span>public String peek(){if (isEmpty()){throw new RuntimeException("棧為空");}return stack.get(stack.size()-1);}//操作符轉(zhuǎn)換，將操作符轉(zhuǎn)換成數(shù)值，便于操作符的比較優(yōu)先級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;}
}

版本二：功能完整實現(xiàn)

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，實現(xiàn)：*          1. 將中綴表達式轉(zhuǎn)換為后綴表達式，并輸出后綴表達式*          2.計算后綴表達式的數(shù)據(jù)結(jié)果*   中綴表達式:（3+4）*5-6  ==> 后綴表達式：3 4 + 5 * 6 -*/
public class PolandNotationStack {public static void main(String[] args){stackDemon stack = new stackDemon(new ArrayList<>());  //鏈表：存儲 后綴表達式的String exception = "(3+4)*5-6";String suffixExpection = "";
//        String exception = "()";
//        stack.push("1");
//        stack.show();
//        System.out.println( stack.transform("*"));//將中綴表達式 轉(zhuǎn)成 后綴表達try {stackDemon suffix = transsuffix(exception, stack);suffix.show();System.out.println(suffix.show());   //后綴表達式的結(jié)果suffixExpection = suffix.show();}catch (Exception e){System.out.println( e.getMessage());}//結(jié)果為：suffixCal(suffixExpection);}//將后綴表達式進行計算結(jié)果public static void suffixCal(String su){String exp = su;  //后綴表達式String[] s = exp.split(" ");int res = 0; //結(jié)果值ArrayList<String> list = new ArrayList<String>();for (String s1 : s) {//1.遇到數(shù)值直接將數(shù)值輸入到list中if (s1.matches("\\d+")){  //用正則表達式中判斷字符舒是否為數(shù)值list.add(s1);}else{ //不為數(shù)值時，遇到操作符需要將數(shù)值取出來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);  //將中間結(jié)果保存在list中}}System.out.println(res);}//實現(xiàn)將中綴表達式轉(zhuǎn)換為后綴表達式中public static stackDemon  transsuffix(String exception,stackDemon stack1){stackDemon stack = stack1;stackDemon operStack = new stackDemon(new ArrayList<>());  //存儲操作符的String[] split = exception.split(""); //將表達式切分一個一個的//注意：后綴表達式是從左往右的，因此split切片出的數(shù)據(jù)，可以直接從左到右進行遍歷for (String iteam : split) {// 1.如果數(shù)值直接加入if (iteam.matches("\\d+")){ //判斷是否為多個數(shù)值，通過正則表達式stack.push(iteam);  //數(shù)值存儲到stack中}else{//2 判斷operStack 中是否為空,直接將數(shù)據(jù)入棧,或者是左括號 (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：棧頂?shù)牟僮鞣?還有為空if (operStack.isEmpty() || operStack.compare(iteam, operStack.peek()) ){ //num1 待入棧的操作符 ，num2：棧頂?shù)牟僮鞣?/span>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())) {  // 不能為空，空了也沒有數(shù)據(jù)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;}
}//創(chuàng)建stack
class stackDemon{//創(chuàng)建toppublic int top = -1; // 初始位置為：-1//數(shù)組List<String>private List<String>  stack;public stackDemon(List<String> stack) {this.stack = stack;}//判斷是否為空public  boolean isEmpty(){return stack.size() == 0;  //大小為0}//數(shù)據(jù)入棧public void push(String key){stack.add(key);}//數(shù)據(jù)出棧public String pop(){String value = "";//判斷是否為空if (stack.size()!= 0) {value = stack.get(stack.size()-1);stack.remove(stack.size() - 1);  // 刪除最后一個數(shù)據(jù)}return value;}//展示數(shù)據(jù)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;}// 展示棧頂?shù)脑?/span>public String peek(){if (isEmpty()){throw new RuntimeException("棧為空");}return stack.get(stack.size()-1);}//操作符轉(zhuǎn)換，將操作符轉(zhuǎn)換成數(shù)值，便于操作符的比較優(yōu)先級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;}
}

第五章：遞歸

（一）遞歸介紹

應(yīng)用場景：迷宮問題（回溯）、遞歸（recursion）、漢羅塔、階乘問題、8皇后問題

• 算法中也會使用遞歸 eg：快排、歸并排序、二分查找、分治算法

遞歸：方法自己調(diào)用自己，每次調(diào)用時傳入不同的變量，有助于解決復(fù)雜的問題

JVM組成：棧、堆、代碼區(qū)（包括常量）

遞歸調(diào)用規(guī)則：

1. 當(dāng)程序執(zhí)行到一個方法時，就會開辟一個獨立的空間（?？臻g）
2. 方法的局部變量是獨立的，不會相互影響的
3. 如果方法中使用的是引用類型變量（eg：數(shù)組），就會共享該引用類型的數(shù)據(jù)
4. 遞歸必須向退出的遞歸條件逼近，否則就死循環(huán)了
5. 當(dāng)一個方法執(zhí)行完畢后，或者遇到了return，就會返回，遵守誰調(diào)用，就將結(jié)果返回給誰，同時當(dāng)方法執(zhí)行完畢或者返回時，該方法也就執(zhí)行完畢

（二）迷宮回溯問題分析與實現(xiàn)

迷宮回溯問題：

創(chuàng)建package：com.lcj.recursion

創(chuàng)建class：MiGong

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){//先創(chuàng)建一個二維數(shù)組，模型迷宮//地圖為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;}//創(chuàng)建墻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、i，j 表示起始位置* 3、map[7][6] 為終點* 4、當(dāng)map[i][j] 為 0表示 該節(jié)點沒有走過，為1表示墻，2表示通路，3表示該節(jié)點已經(jīng)走過，但是走不通* */public static boolean setWay(int[][] map,int i,int j){if(map[6][5] == 2){return true;}else{if (map[i][j] == 0){ // 當(dāng)前的節(jié)點沒有走過//按照的策略為：下 -> 右 ->上 ->左map[i][j] = 2;if (setWay(map,i+1,j)){return true;}else if(setWay(map,i,j+1)){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]節(jié)點 不為0,可能是1（墻）,2（已經(jīng)走過）,3（死路）return false; //不要再走}}}
}

注意：誰調(diào)用，誰用值

（三）八皇后問題（回溯問題）

1、介紹

任意兩個皇后都不能同時處于同一行、同一列或者同一斜線

用一維數(shù)組解決棋盤位置：eg:arr[8] = {0,4,7,5,2,6,1,3} // arr對應(yīng)的下標(biāo)表示第幾行，arr[i] = val ，val表示第i+1個皇后，放在第i+1行的第val+1列中

2、代碼實現(xiàn)

創(chuàng)建class：Queue8

package com.lcj.recursion;/*** @Version 1.0* @Author:lcj* @Date:2022/9/5-21:05* @Content:*/
public class Queue8 {int max = 8;  //皇后的個數(shù)//定義數(shù)值array，保存皇后放置位置的結(jié)果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("個數(shù)為：%d",count);}//編寫一個方法，放置第n個皇后private void check(int n){if(n == max){ // n = 8print(); //輸出結(jié)果return; //已經(jīng)將結(jié)果放好}//依次放入皇后，并判斷是否沖突for (int i = 0; i < max; i++) {//先把當(dāng)前這個皇后n，放到該行的第1列中array[n] = i;if(judge(n)){  //不沖突check(n+1);}//如果沖突會跳轉(zhuǎn)到array[n] = i 上面的，將n往后繼續(xù)移動}}//判斷是否沖突,查看當(dāng)我們放置第n個皇后是否和前面的已經(jīng)擺放的皇后沖突//同行（不需要判斷，因為每次一行只有一個數(shù)值）、同列、同斜線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++;}
}

第六章：排序算法

一、排序算法

1. 排序算法（sort Algorithm）：將數(shù)據(jù)按著一定的順序進行排序的過程。

2. 排序的分類：

   • 內(nèi)部排序：將數(shù)據(jù)加載到內(nèi)存中進行排序
   • 外部排序法：數(shù)量大的時候，無法加載到內(nèi)存中時，用外部存儲進行排序

   

   直接插入、簡單選擇、冒泡排序法必須要掌握

二、算法的時間復(fù)雜度

（一）算法的評判方法

1. 事后統(tǒng)計的方法

   在計算運行后，再計算運行時間

   • 有問題需要運行程序，但是要受到計算機硬件性能的影響
   • 運行程序可能需要很長的時間

2. 事前估算的方法——時間復(fù)雜度

   通過分析算法的時間復(fù)雜度來判斷那個算法比較優(yōu)秀

（二）時間復(fù)雜度

1、時間頻度

時間頻數(shù)：一個算法花費時間與算法中語句執(zhí)行次數(shù)成正比，即語句多花費時間多。

• 語句頻數(shù) 或者 時間頻數(shù)，記作T(n)：算法中語句執(zhí)行的次數(shù)

  

特點：

• 忽略時間頻數(shù)中的常數(shù)項

• 忽略時間頻數(shù)中低次項

  

• 忽略時間頻數(shù)的系數(shù)

  

2 、時間復(fù)雜度

時間復(fù)雜度：

2.1 算法中基本操作語句的重復(fù)執(zhí)行次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示（時間頻數(shù)），若有某個輔助函數(shù)f(n)，使得當(dāng)n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱為f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O (f(n)) ,稱O(f(n))為算法的漸進時間復(fù)雜度，簡稱時間復(fù)雜度。

$T(n)=3n^2+3n+1$ ==> $T(n)=n^2$

$f(n)=n^2$

結(jié)果為：

$T(n)/f(n)=O(n^2)$

$O(1)<O(lo{g}_2^n)<O(n)<O(nlo{g}_2^n)<O(n^2)<O(n^3)<O(n^k)<O(2^n)<(n!)$

常數(shù)階$O(1)$ :沒有循環(huán)代碼

（三）平均時間復(fù)雜度

1、平均時間復(fù)雜度

平均時間復(fù)雜度：所有可能的輸入實例的時間平均之后的算法運行時間

2、最壞時間復(fù)雜度

最壞時間復(fù)雜度：算法運行最壞的時間復(fù)雜度，作用：相對于算法的運行時間界限，不會出現(xiàn)最壞的結(jié)果

（四）空間復(fù)雜度——空間換時間

三、冒泡排序算法(bubble sorting)

• 一共需要進行數(shù)組長度-1次排序
• 每一次內(nèi)部排序在逐漸減少
• 優(yōu)化：如果在排序中，沒有發(fā)生交換，說明已經(jīng)是有序的，直接將結(jié)果輸出

（一）代碼實現(xiàn)

創(chuàng)建package：com.lcj.sort

創(chuàng)建class：Bubble 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: 創(chuàng)建冒泡排序法*/
public class BubblerSorting {public static void main(String[] args){int arr[] = {3,9,-1,10,-2};for(int i=0; i<arr.length-1;i++){ // 循環(huán)每次減少for(int j=0;j <arr.length-1-i;j++){int temp = 0;if (arr[j]<arr[j+1]){temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}//        System.out.println(arr.toString());System.out.println(Arrays.toString(arr));}
}

升級：

如果在排序中，如果數(shù)據(jù)已經(jīng)排序完成了，直接中止排序輸出結(jié)果

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: 創(chuàng)建冒泡排序法*/
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; // 目的：判斷數(shù)據(jù)是否交換，如果沒有發(fā)生交換說明數(shù)據(jù)已經(jīng)排序完成for(int i=0; i<arr.length-1;i++){ // 循環(huán)每次減少for(int j=0;j <arr.length-1-i;j++){int temp = 0;if (arr[j] > arr[j+1]){flage = true;temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}System.out.printf("第%d次循環(huán)",i);System.out.println(Arrays.toString(arr));if(flage == false){break;}else{flage = false;  //注意需要將數(shù)據(jù)轉(zhuǎn)換成false}}//        System.out.println(arr.toString());System.out.println(Arrays.toString(arr));}
}

測試：將數(shù)量達到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: 創(chuàng)建冒泡排序法*/import java.util.Date;public class BubblerSorting {public static void main(String[] args){
//        int arr[] = {3,9,-1,10,-2};// 測試當(dāng)數(shù)據(jù)量的大的時候，執(zhí)行時間的變化int[] arr = new int[80000];//添加數(shù)據(jù)for(int i=0; i<80000 ;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 i=0; i<arr.length-1;i++){ // 循環(huán)每次減少for(int j=0;j <arr.length-1-i;j++){int temp = 0;if (arr[j]<arr[j+1]){temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}Date date2 = new Date();System.out.println("結(jié)束時間："+simpleDateFormat.format(date2));//        System.out.println(Arrays.toString(arr));  //展示全部數(shù)據(jù)}
}

四、選擇排序算法

（一）選舉排序介紹

選擇排序：是從待排序的的數(shù)據(jù)中，按指定規(guī)則選出某一元素，再依次交換位置后達到排序的目的。

（二）代碼實現(xiàn)

案例：將101,34,119,1，通過選擇排序從==低到高進行排序==

創(chuàng)建class：SelectSort

時間復(fù)雜度:$O(n^2)$

package com.lcj.sort;import java.util.Arrays;/*** @Version 1.0* @Author:lcj* @Date:2022/9/14-20:59* @Content:選擇排序?qū)崿F(xiàn)*/
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 i=0;i<arr.length-1;i++){ //選擇排序中外部排序只有： 數(shù)組長度-1int minIndex = i; //記錄最大下標(biāo)int min = arr[minIndex];for (int j=i+1;j<arr.length;j++){if(min > arr[j]){minIndex = j;min = arr[minIndex];  //將最值進行更新，目前是為了確定最小值的位置}}//交換數(shù)據(jù)if(minIdex !=i){  //優(yōu)化：部分情況，是后面已經(jīng)排好序了，就不需要進行排序了temp =min;arr[minIndex] = arr[i];arr[i] = temp;}System.out.println(Arrays.toString(arr));}System.out.println(Arrays.toString(arr));}
}

注意：先將算法簡單化，再將算法復(fù)雜化 ，一部分一部分進行實現(xiàn)

五、插入排序算法

（一）介紹

插入排序?qū)儆趦?nèi)部排序，通過將要排序的數(shù)據(jù)插入到指定位置來達到排序的

（二）代碼實現(xiàn)

創(chuàng)建class：IndexSort

自己實現(xiàn)：

版本一：

package com.lcj.sort;import java.util.Arrays;/*** @Version 1.0* @Author:lcj* @Date:2022/9/16-22:06* @Content: 自己實現(xiàn)插入排序 ：從小到大*/
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;//待插入數(shù)據(jù)的下標(biāo)int indexNum = 0; //待插入數(shù)據(jù)for(int i=1;i<arr.length;i++){index = i; //待插入數(shù)據(jù)的下標(biāo),為第一次for循環(huán)的下標(biāo)indexNum = arr[i];// 待插入值//有序表進行排序// 1.實現(xiàn)待插入數(shù)據(jù)的位置確定// 2.實現(xiàn)插入數(shù)據(jù)（需要將數(shù)據(jù)進行移動，這里主要是往后移動，因此需要找到待插入的位置）// 2.1插入位置的判斷for(int j=0;j < i;j++){int indexLoc = 0;  //插入數(shù)據(jù)的位置boolean flag = false;//尋找插入數(shù)據(jù)的位置—暴力法if (arr[i]<=arr[j]){indexLoc = j; //獲得插入數(shù)據(jù)的位置flag = true;  //可以執(zhí)行后移操作}if(flag) {//執(zhí)行后移操作for (int k =i;k>j;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: 自己實現(xiàn)插入排序 ：從小到大*/
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;//待插入數(shù)據(jù)的下標(biāo)int indexNum = 0; //待插入數(shù)據(jù)for(int i=1;i<arr.length;i++){index = i; //待插入數(shù)據(jù)的下標(biāo),為第一次for循環(huán)的下標(biāo)indexNum = arr[i];// 待插入值//有序表進行排序// 1.實現(xiàn)待插入數(shù)據(jù)的位置確定// 2.實現(xiàn)插入數(shù)據(jù)（需要將數(shù)據(jù)進行移動，這里主要是往后移動，因此需要找到待插入的位置）// 2.1插入位置的判斷for(int j=0;j < i;j++){int indexLoc = 0;  //插入數(shù)據(jù)的位置boolean flag = false;//尋找插入數(shù)據(jù)的位置—暴力法if (arr[i]<=arr[j]){indexLoc = j; //獲得插入數(shù)據(jù)的位置flag = true;  //可以執(zhí)行后移操作}if(flag){for(int k=j;j<=i;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: 自己實現(xiàn)插入排序 ：從小到大*/
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;//待插入數(shù)據(jù)的下標(biāo)int indexNum = 0; //待插入數(shù)據(jù)for(int i=1;i<arr.length;i++){index = i; //待插入數(shù)據(jù)的下標(biāo),為第一次for循環(huán)的下標(biāo)indexNum = arr[i];// 待插入值//有序表進行排序// 1.實現(xiàn)待插入數(shù)據(jù)的位置確定// 2.實現(xiàn)插入數(shù)據(jù)（需要將數(shù)據(jù)進行移動，這里主要是往后移動，因此需要找到待插入的位置）// 2.1插入位置的判斷for(int j=0;j < i;j++){int indexLoc = 0;  //插入數(shù)據(jù)的位置boolean flag = false;//尋找插入數(shù)據(jù)的位置—暴力法if (arr[i]<=arr[j]){indexLoc = j; //獲得插入數(shù)據(jù)的位置flag = true;  //可以執(zhí)行后移操作}
//                if(flag) {
//                    //執(zhí)行后移操作
//                    for (int k =i;k>j;k--){
//                        arr[k]=arr[k-1];
//                    }
//                    arr[j] = indexNum;
//                }if(flag){for(int k=j;j<=i;j++){int temp =arr[i];arr[i] = arr[j];arr[j] = temp;}}}}}
}

六、希爾排序算法（shell）

（一）希爾排序算法介紹

希爾排序是經(jīng)過改進之后的一個更高效的版本，也稱為縮小增量排序

基本思想：

• 希爾排序是把記錄按下標(biāo)的一定增量分組，對每組使用直接插入排序算法排序，隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時，整個文件恰好被分成一組

（二）代碼實現(xiàn)

方法一：交換法

package com.lcj.sort;import java.util.Arrays;/*** @Version 1.0* @Author:lcj* @Date:2022/9/19-10:40* @Content:希爾排序算法，自己排序?qū)崿F(xiàn)*/
public class ShellSort {public static void main(String[] args){int[] arr = {8,9,1,7,2,3,5,4,6,0};shellSort(arr);}//使用逐步推導(dǎo)的過程進行實現(xiàn)代碼public static void shellSort(int[] arr){int temp = 0;for(int grap=arr.length/2; grap > 0; grap/=2){  // 分組的次數(shù) 5,2,1
//            System.out.println(grap); //測試for(int i=grap;i<arr.length;i++){  //循環(huán)一次是一組for (int j=i-grap;j>=0;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:希爾排序算法，自己排序?qū)崿F(xiàn)*/
public class ShellSort {public static void main(String[] args){int[] arr = {8,9,1,7,2,3,5,4,6,0};shellSort(arr); // 移動式}//使用逐步推導(dǎo)的過程進行實現(xiàn)代碼public static void shellSort(int[] arr){int temp = 0;for(int grap=arr.length/2; grap > 0; grap/=2){  // 分組的次數(shù) 5,2,1
//          System.out.println(grap); //測試for(int i=grap;i<arr.length;i++) {  //循環(huán)一次是一組int j = i;//待插入數(shù)據(jù)的下標(biāo)int insertValue = arr[i]; //待插入值if (arr[j] < arr[j-grap]) {  //待插入值小于之前的，說明待入數(shù)值需要在[j-grap] 之前，但是位置未確定while(j-grap>=0 && insertValue <arr[j-grap] ){  //insertValue 小于 arr[j-grap]插入數(shù)據(jù)//將數(shù)據(jù)往后移動arr[j]= arr[j-grap];j-=grap;  //將標(biāo)往后移動}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:希爾排序算法，自己排序?qū)崿F(xiàn)*/
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);}//使用逐步推導(dǎo)的過程進行實現(xiàn)代碼public static void shellSort(int[] arr){int temp = 0;for(int grap=arr.length/2; grap > 0; grap/=2){  // 分組的次數(shù) 5,2,1
//          System.out.println(grap); //測試for(int i=grap;i<arr.length;i++) {  //循環(huán)一次是一組int j = i;//待插入數(shù)據(jù)的下標(biāo)int insertValue = arr[i]; //待插入值if (arr[j] < arr[j-grap]) {  //待插入值小于之前的，說明待入數(shù)值需要在[j-grap] 之前，但是位置未確定while(j-grap>=0 && insertValue <arr[j-grap] ){  //insertValue 小于 arr[j-grap]插入數(shù)據(jù)//將數(shù)據(jù)往后移動arr[j]= arr[j-grap];j-=grap;  //將標(biāo)往后移動}arr[j] = insertValue;}}}//System.out.println(Arrays.toString(arr));}}

七、快排算法——Quicksort

（一）快排算法介紹

動畫演示1

動畫演示2

快排算法是對冒泡排序算法的升級。

基本思想：通過一趟排序?qū)?shù)據(jù)，將排序數(shù)據(jù)分成兩部分，注意其他一部分要比另一部小，然后另外兩部分也根據(jù)這樣方式進行排序，最終實現(xiàn)排序數(shù)據(jù)有序。（可以采取遞歸實現(xiàn)）

（二）代碼實現(xiàn)

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; //左下標(biāo)int r = right; //右下標(biāo)int pivot = arr[(left+right)/2]; //取左右的中間值，作為基準(zhǔn)，左邊是全部小于int temp = 0;//臨時變量while(l < r){//只要arr[l] 小于 pivot ，將l向右移動一格，只要arr[l] > pivot就終止移動if(arr[l] < pivot){l+=1;}//只要arr[r] 大于 pivot ，將r向左移動一格，只要arr[r] < pivot就終止移動if(arr[r] > pivot ){r -=1;}//如果l大于r說明privot 左邊的數(shù)據(jù)已經(jīng)是最小的了，右邊的數(shù)據(jù)是最大的了if(l >= r){break;}//交換temp = arr[l];arr[l] = arr[r];arr[r] = temp;//如果交換完后，發(fā)現(xiàn)這個arr[l] == pivot 值,相等于r--，前移if(arr[l] == pivot){  //注意:r指向的是交換的元素，如果不說不進行后移的話，會死循環(huán)r -=1;}//如果交換完后，發(fā)現(xiàn)這個arr[r] == pivot 值,相等于l++，后移if(arr[r] == pivot){l +=1;}}// 如果l==r，必須l++，r--,否則出現(xiàn)棧溢出,即死循環(huán)if (l==r){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; //左下標(biāo)int r = right; //右下標(biāo)int pivot = arr[(left+right)/2]; //取左右的中間值，作為基準(zhǔn)，左邊是全部小于int temp = 0;//臨時變量while(l < r){//只要arr[l] 小于 pivot ，將l向右移動一格，只要arr[l] > pivot就終止移動if(arr[l] < pivot){l+=1;}//只要arr[r] 大于 pivot ，將r向左移動一格，只要arr[r] < pivot就終止移動if(arr[r] > pivot ){r -=1;}//如果l大于r說明privot 左邊的數(shù)據(jù)已經(jīng)是最小的了，右邊的數(shù)據(jù)是最大的了if(l >= r){break;}//交換temp = arr[l];arr[l] = arr[r];arr[r] = temp;//如果交換完后，發(fā)現(xiàn)這個arr[l] == pivot 值,相等于r--，前移if(arr[l] == pivot){  //注意:r指向的是交換的元素，如果不說不進行后移的話，會死循環(huán)r -=1;}//如果交換完后，發(fā)現(xiàn)這個arr[r] == pivot 值,相等于l++，后移if(arr[r] == pivot){l +=1;}}// 如果l==r，必須l++，r--,否則出現(xiàn)棧溢出,即死循環(huán)if (l==r){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）是利用歸并的思想實現(xiàn)排序，采用經(jīng)典的分治（divide-and-conquer）策略（分治問題是將問題：1.分成一些小的問題，然后遞歸求解，2.治：將分階段得到的各答案“修補”在一起，即分而治之）

將84571362 按照從小到大進行排序

（二）代碼實現(xiàn)

創(chuàng)建class：MergetSort

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,mid+1,right,temp);//合并merg(arr,left,mid,right,temp);}}//合并方法/** arr:數(shù)據(jù)數(shù)值* left：左邊有序數(shù)列的初始索引* right：右邊有序數(shù)列的最右邊索引* mid ：是中間索引* tmp：臨時數(shù)組* */public static void merg(int[] arr,int left,int mid,int right,int[] tmp){int i = left; //初始化最左邊的索引int j = mid +1 ;int t = 0 ; //臨時數(shù)組的初始索引//第一步：先將左右兩邊（），按照從小到的大順序?qū)?shù)據(jù)放進到臨時數(shù)組中,直到一邊處理完成// 注意：左右兩邊的數(shù)據(jù)分別是有序的while(i<=mid && j<=right){// 如果左邊的數(shù)據(jù)小于右邊時，將左邊數(shù)據(jù)移動到tmp中if (arr[i] <= arr[j]){tmp[t] = arr[i];t += 1; //將t往后進行移動i += 1; // 將i往后進行移動}else{   // 將右邊的數(shù)據(jù)大于左邊的數(shù)據(jù)時tmp[t] = arr[j];t += 1;  // 將t往后進行移動j += 1;}}// 第二步：將剩下的數(shù)組依次放進到臨時數(shù)組中while(i <= mid){  // 左邊數(shù)據(jù)剩余tmp[t] = arr[i];i ++;t ++;}while(j <= right){  // 右邊數(shù)據(jù)剩余tmp[t] = arr[j];j ++;t ++;}// 第三步：將臨時數(shù)組數(shù)據(jù)放進arr中t =0;int tempLeft = left;while(tempLeft <= right){arr[tempLeft] = tmp[t];t += 1;tempLeft +=1;}}
}

九、基數(shù)排序

（一）基礎(chǔ)知識

基數(shù)排序（radix sort）屬于“分配式排序” ，或者稱為“桶子排序”。主要是通過將數(shù)據(jù)的個位、十位等位數(shù)放進行相應(yīng)的“桶”中，來達到排序的效果

• 基數(shù)排序?qū)儆?mark>效率高的穩(wěn)定性排序
• 基數(shù)排序是桶排序的擴展

思路：

• 將所有待排序的數(shù)據(jù)，統(tǒng)一長度（位數(shù)短的在前面補充0），然后按照從低位到高位對數(shù)據(jù)進行排序

eg：{53,3，542,748,14，214} 進行升序排序

（二）代碼實現(xiàn)

創(chuàng)建類：RadixSort

package com.lcj.sort;import java.util.Arrays;/*** @Version 1.0* @Author:lcj* @Date:2022/10/16-10:44* @Content:基數(shù)排序* 主要思路：* 1. 創(chuàng)建對應(yīng)的10個桶，即十個數(shù)組，分別代表的是從0-9的數(shù)字* 2. 獲取個位、十位等數(shù)據(jù)，將數(shù)據(jù)對應(yīng)放進到數(shù)組中，并數(shù)據(jù)讀取到原來的數(shù)組中，進行排序* 3. 重復(fù)第2步驟，循環(huán)次數(shù)為數(shù)據(jù)中最大值的個數(shù)* */
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));}//基數(shù)排序方法public static void radixSort(int[] arr){//1.通過創(chuàng)建二維數(shù)據(jù)，來表示桶，長度為arr.length來避免數(shù)據(jù)溢出的問題//通過空間換時間int[][] bucket = new int[10][arr.length];//記錄每一個桶中的數(shù)量，并不是所有的桶中有數(shù)據(jù)// eg：bucketElementCounts[1] 存儲的是bucket[1]中的數(shù)據(jù)個數(shù)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(); //最大值的長度，決定循環(huán)的次數(shù)// 4. 循環(huán)執(zhí)行for(int k = 0 ,n=1;k< maxLength ;k++,n *= 10) {// 3，獲取數(shù)據(jù)循環(huán)for (int i = 0; i < arr.length; i++) {//遍歷所有數(shù)據(jù),獲取位數(shù)//取除元素的位數(shù)int digitOfELement = arr[i]/n % 10;bucket[digitOfELement][bucketElementCounts[digitOfELement]] = arr[i];bucketElementCounts[digitOfELement]++; //元素的個數(shù)統(tǒng)計需要改變}//將二維數(shù)組中的數(shù)據(jù)轉(zhuǎn)移到arr中int index = 0; //初始化的索引下標(biāo)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];  // 將二維數(shù)組的元素重新賦給arr數(shù)組中index++;}bucketElementCounts[j] = 0 ; //注意一定要將這點的數(shù)據(jù)清為0}}}}}

注意事項：數(shù)據(jù)量特別大的時候會占用大量的內(nèi)存

~~~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));

十、排序總結(jié)

排序算法	平均時間復(fù)雜度	最好情況	最壞情況	空間復(fù)雜度	排序方式	穩(wěn)定性
冒泡排序	$O(n^2)$	$O(n)$	$O(n^2)$	$O(n^2)$	In-Place	穩(wěn)定
選擇排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	In-Place	不穩(wěn)定
插入排序	$O(n^2)$	$O()$
希爾排序
歸并排序
快速排序
堆排序
計數(shù)排序
桶排序
基數(shù)排序

$O(1)<O(lo{g}_2^n)<O(n)<O(nlo{g}_2^n)<O(n^2)<O(n^3)<O(n^k)<O(2^n)<(n!)$