教程學習地址：

https://www.bilibili.com/video/BV1E4411H73v

一、數(shù)據(jù)結構和算法的關系

• 數(shù)據(jù)data結構(structure)是一門研究組織數(shù)據(jù)方式的學科，有了編程語言也就有了數(shù)據(jù)結構.學好數(shù)據(jù)結構可以編寫出更加漂亮,更加有效率的代碼。
• 要學習好數(shù)據(jù)結構就要多多考慮如何將生活中遇到的問題,用程序去實現(xiàn)解決.
• 程序 = 數(shù)據(jù)結構 + 算法
• 數(shù)據(jù)結構是算法的基礎, 換言之，想要學好算法，需要把數(shù)據(jù)結構學到位。
  總結：數(shù)據(jù)結構是基石，研究數(shù)據(jù)方式；算法是是數(shù)據(jù)處理更有效，更優(yōu)雅

數(shù)據(jù)結構

一、線性結構和非線性結構

1、線性結構(常見結構：數(shù)組、隊列、鏈表和棧)

• 線性結構作為最常用的數(shù)據(jù)結構，其特點是數(shù)據(jù)元素之間存在一對一的線性關系
• 線性結構有兩種不同的存儲結構，即順序存儲結構和鏈式存儲結構。順序存儲的線性表稱為順序表，順序表中的存儲元素是連續(xù)的
• 鏈式存儲的線性表稱為鏈表，鏈表中的存儲元素不一定是連續(xù)的，元素節(jié)點中存放數(shù)據(jù)元素以及相鄰元素的地址信息
• 線性結構常見的有：數(shù)組、隊列、鏈表和棧
  

1.1、稀疏數(shù)組(sparsearray)

1.1.1 稀疏數(shù)組用于解決問題場景

解決二維數(shù)組資源浪費的問題。

1.1.2 解決方案：使用稀疏數(shù)組

稀疏數(shù)組的處理方法是:
記錄數(shù)組一共有幾行幾列，有多少個不同的值
把具有不同值的元素的行列及值記錄在一個小規(guī)模的數(shù)組中，從而縮小程序的規(guī)模

1.1.3 應用實例

1.1.4 數(shù)組轉稀疏數(shù)組思路

1.1.4 代碼實現(xiàn)

流程：正常的二維數(shù)組—>稀疏數(shù)組—>保存到磁盤中—>將磁盤中的數(shù)據(jù)還原成稀疏數(shù)組

package com.bear.稀疏數(shù)組;import java.io.*;/*** <簡述>* <詳細描述>** @author LiuShanshan* @version $Id$*/ public class SparsearryTest {public static void main(String[] args) throws IOException, ClassNotFoundException {System.out.println("二維數(shù)組：");// 生成二維數(shù)組 行 8 ，列7int charArray[][] = new int[8][7];// 1代表黑棋charArray[1][2] = 1;// 2代表藍旗// 沒有賦值的為0charArray[2][3] = 2;charArray[4][3] = 3;int sum = 0;for (int[] hang : charArray) { // 2維數(shù)組變1維數(shù)組for (int i : hang) {if(i != 0){sum ++;}System.out.printf("%d\t", i);}System.out.printf("\n");}System.out.println("=======================");System.out.println("稀疏數(shù)組:");// 生成散列數(shù)組 已知只會有3列，現(xiàn)在需要確實有幾行int sparseArray[][] = new int[sum + 1][3];sparseArray[0][0] = 8;sparseArray[0][1] = 7;sparseArray[0][2] = sum;int count = 0;for (int i = 0; i < 8; i++) {for (int j = 0; j < 7; j++){if(charArray[i][j] != 0){count ++;sparseArray[count][0] = i;sparseArray[count][1] = j;sparseArray[count][2] = charArray[i][j];}}}for (int[] ints : sparseArray) {for (int anInt : ints) {System.out.printf("%d\t", anInt);}System.out.printf("\n");}// 稀疏數(shù)組反推到二維數(shù)組System.out.println("=======================");System.out.println("散列數(shù)組反推到二維數(shù)組");int thrustArray[][] = new int[sparseArray[0][0]][sparseArray[0][1]];for (int i = 1; i < sparseArray.length; i++) {thrustArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];}for (int[] ints : thrustArray) {for (int anInt : ints) {System.out.printf("%d\t",anInt);}System.out.printf("\n");}// 將稀疏數(shù)組保存到磁盤上// 將數(shù)據(jù)導入到磁盤中stream(thrustArray);// 將磁盤上的稀疏數(shù)組還原回來System.out.println("==================");System.out.println("磁盤中還原數(shù)據(jù)：");stream();}// 保存數(shù)據(jù)到文件中public static void stream(int[][] ob) throws IOException {FileOutputStream fos = new FileOutputStream("c:\\javas\\map.data");//字節(jié)流ObjectOutputStream oos = new ObjectOutputStream(fos);//對象輸出流oos.writeObject(ob);//存到磁盤上，序列化 // FileInputStream fis = new FileInputStream("c:\\javas\\map.data"); // ObjectInputStream ois = new ObjectInputStream(fis);//對象輸入流 // System.out.println(ois.readObject());//讀的時候，反序列化}// 從文件中獲取數(shù)據(jù)public static void stream() throws IOException, ClassNotFoundException {FileInputStream fis = new FileInputStream("c:\\javas\\map.data");ObjectInputStream ois = new ObjectInputStream(fis);//對象輸入流int[][] ints = (int[][]) ois.readObject(); //讀的時候，反序列化for (int[] anInt : ints) {for (int i : anInt) {System.out.printf("%d\t" , i);}System.out.printf("\n");}}}

1.2、隊列

1.2.1 數(shù)組模擬隊列之— 隊列圖解

1.2.2 數(shù)組模擬隊列之二：環(huán)形數(shù)組

1.2.2.1 環(huán)形數(shù)組實現(xiàn)原理

1.2.2.2 實現(xiàn)代碼

package com.bear.隊列;import java.util.Scanner;/*** <簡述> 環(huán)形數(shù)組模擬隊列* <詳細描述>** @author LiuShanshan* @version $Id$*/ public class QueueTest{public static void main(String[] args) {// 測試System.out.println("測試數(shù)組模擬環(huán)形隊列的案例~~~");//創(chuàng)建一個環(huán)形隊列CirciQueue queue=new CirciQueue(5);// 說明設置4,其隊列的有效數(shù)據(jù)最大是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):添加數(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.show();break;case'a':System.out.println("輸出一個數(shù)");int value=scanner.nextInt();queue.add(value);break;case'g'://取出數(shù)據(jù)try{int res=queue.get();System.out.printf("取出的數(shù)據(jù)是%d\n",res);}catch(Exception e){//TODO:handleexceptionSystem.out.println(e.getMessage());}break;case'e':scanner.close();loop = false;break;default:break;}}System.out.println("程序退出");} }// 環(huán)形隊列 class CirciQueue{// 最大容量private int maxSize ;// 最下面數(shù)據(jù)的下標（包含開始元素），從0開始private int front;// 最上面數(shù)據(jù)的上標 + 1（不包含結束元素）， 從0開始private int real;// 環(huán)形數(shù)組private int[] queueArray;// 1、構造函數(shù)，賦值初始值CirciQueue(int maxSize){this.maxSize = maxSize;this.queueArray = new int[this.maxSize];}// 2、判斷容器是否為空private boolean notEmpty(){return this.real == this.front;}// 3、容量是否已滿private boolean notFull(){return (real + 1)% maxSize == front;}// 4、將數(shù)據(jù)放入環(huán)形數(shù)組中public void add(int i){if(notFull()){System.out.println("容器已滿，請先消費");}else{// 數(shù)據(jù)放入this.queueArray[real] =i;// real向后移動，這里需要考慮取模(余)（如果real正好在最上面，而front不等于0,并且可以放值，那么就需要將real放在最下面）this.real = (real +1) % maxSize; // 取模}}// 5、拿取數(shù)據(jù) 從下往上拿public int get(){// 是否容器為空if(notEmpty()){System.out.println("容器為空，請?zhí)砑訑?shù)據(jù)");return -1;}int i = queueArray[front];front = (front +1) % maxSize; // 取模return i;}// 顯示環(huán)形隊列中的值public void show(){// 是否容器為空if(notEmpty()){System.out.println("容器為空，請?zhí)砑訑?shù)據(jù)");}else{// 循環(huán)次數(shù)為真實的有值的數(shù)據(jù)長度for(int i = front; i < front + getRealLength(); i ++){// 當前值，要取模int i1 = queueArray[i % maxSize]; // 取模System.out.printf("queueArray[%s]的值為:%s", queueArray[i % maxSize], i1);}}}// 獲取真實的長度private int getRealLength(){// real在front上面 todo 這一部分重點看 取模return (maxSize + real - front)% maxSize;}}

1.2.2.3 總結

環(huán)形數(shù)組組成隊列，重要是觀察3個值：maxSize(最大容量)，real(尾部數(shù)據(jù)+1的索引)，front（開頭數(shù)據(jù)的索引），不管是算容器是否滿，計算真實的數(shù)據(jù)長度，顯示容器中的值，將數(shù)據(jù)放在容器中等都需要使用到取模，需要取模之后計算。

1.3 單項鏈表

1.3.1 鏈表實現(xiàn)原理講解

1.3.2 鏈表實現(xiàn)代碼（添加和顯示所有—刪除和更新簡單沒有寫）

package com.bear.線性結構.單鏈表;/*** <簡述>* <詳細描述>** @author LiuShanshan* @version $Id$*/ public class SingleLinkedListDemo {public static void main(String[] args) {// 測試SingleLinked singleLinked = new SingleLinked();singleLinked.addByNo(new HeroNode(1, "宋江"));singleLinked.addByNo(new HeroNode(4, "林沖"));singleLinked.addByNo(new HeroNode(2, "盧俊義"));singleLinked.addByNo(new HeroNode(3, "吳用"));singleLinked.addByNo(new HeroNode(3, "吳用2"));singleLinked.show();} } // 單鏈表 處理類 class SingleLinked{// head信息，在鏈表的第一個，不能變動private HeroNode heroNodeHeard = new HeroNode(0, "");// 添加public void addByNo(HeroNode heroNode){// 添加輔助節(jié)點HeroNode temp = heroNodeHeard;boolean isRep = false;while (true){// 當前節(jié)點next為null,退出if(temp.next == null){break;}// 當前節(jié)點next值的no值大于傳入進來的heroNode中的no值（因為是從小到大排序），則退出if(temp.next.no > heroNode.no){break;}else if (temp.next.no == heroNode.no){isRep = true;}temp = temp.next;}if(isRep){System.out.println("有重復數(shù)據(jù)，報錯.");}else{// 到了這里，temp中的next就應該放入?yún)eroNodeheroNode.next = temp.next;temp.next = heroNode;}}//顯示public void show(){if(heroNodeHeard.next == null){System.out.println("沒有添加數(shù)據(jù)");}else{// 頭信息不能動HeroNode temp = heroNodeHeard.next;while (true){System.out.println(temp);if(temp.next == null){break;}temp = temp.next;}}}}// 類 class HeroNode{// 編號public int no;// 名稱public String name;// 指向下一個元素的對象public HeroNode next;HeroNode(int no, String name){this.no = no;this.name = name;}@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +'}';} }

1.3.3 面試題

1.3.3.1 查找出有效個數(shù)

// 顯示長度 heroNodeHeard 為頭節(jié)點public int getLength() {// next沒值返回0if(heroNodeHeard.next == null){return 0;}// next有值進行循環(huán)int size = 0;HeroNode temp = heroNodeHeard.next;while (true){size ++;if(temp.next != null){temp = temp.next;}else{break;}}return size;}

1.3.3.2 查找單鏈表中的倒數(shù)第k個結點

// 查找單鏈表中的倒數(shù)第k個結點public HeroNode selectReciIndex(int index){// index是否合理 // index不能比長度大if(index <= 0 || index > getLength()){return null;}// 用長度減去index，得到應該查詢第幾條數(shù)據(jù)int shouldSelectLength = getLength() - index + 1;// 進行循環(huán)，查找到數(shù)據(jù)HeroNode temp = heroNodeHeard.next;for (int i = 1; i < shouldSelectLength; i++){temp = temp.next;}return temp;}

1.3.3.3 單鏈表的反轉（騰訊面試題）

思路：單項鏈表倒轉，實現(xiàn)原理：創(chuàng)建一個單鏈表倒敘數(shù)據(jù)，將鏈表循環(huán)，每一次循環(huán)的數(shù)據(jù)作為倒轉鏈表的next值，倒敘鏈表的next值作為傳過來的數(shù)據(jù)的next值

// 倒轉鏈表public void reverse(){// 定義一個輔助變量，幫助我們遍歷原來的鏈表HeroNode cur = heroNodeHeard.next;HeroNode next = null; // 指向當前節(jié)點[cur]的下一個節(jié)點// 倒轉數(shù)組HeroNode reverseHead = new HeroNode(0, "");// 遍歷原來的鏈表，每遍歷一個節(jié)點，就將其取出，并放在新的鏈表reverseHead的最前端while(cur != null){next = cur.next;// 將倒轉數(shù)據(jù)下面的next給cur,因為cur將會成為倒轉數(shù)組里面的第一個數(shù)據(jù)cur.next = reverseHead.next;reverseHead.next = cur;cur = next;}// 賦值，將revers中的next放入head的next中, head.next = reverse.nextheroNodeHeard.next = reverseHead.next;}

1.3.3.4 從頭到尾打印單鏈表（百度面試題）

1、可以使用1.3.3.3的方式（不推薦）
2、使用stack（棧）的方式（先進后出）

// 鏈表倒敘輸出 方法1：使用倒轉鏈表的方法；方法2：使用棧的方式stackpublic void stack(){Stack<HeroNode> heroNodeStack = new Stack<HeroNode>();HeroNode next = heroNodeHeard.next;while(next != null){heroNodeStack.push(next);next = next.next;}while (heroNodeStack.size()>0){System.out.println(heroNodeStack.pop());}}

1.4 雙向鏈表（根據(jù)單項鏈表，增加pre）

1.4.1 思路講解

1.4.2 代碼實現(xiàn)

package com.bear.線性結構.單鏈表;import java.util.Stack;/*** <簡述>* <詳細描述>** @author LiuShanshan* @version $Id$*/ public class SingleLinkedListDemo {public static void main(String[] args) {// 測試SingleLinked singleLinked = new SingleLinked();singleLinked.addByNo(new HeroNode(1, "宋江"));singleLinked.addByNo(new HeroNode(4, "林沖"));singleLinked.addByNo(new HeroNode(2, "盧俊義"));singleLinked.addByNo(new HeroNode(3, "吳用"));singleLinked.addByNo(new HeroNode(3, "吳用2"));singleLinked.show();// 顯示長度int length = singleLinked.getLength();System.out.println(length);// 查詢出倒數(shù)第2個元素的數(shù)據(jù)HeroNode heroNode = singleLinked.selectReciIndex(4);System.out.println(heroNode);// ================================================將鏈表倒轉===============System.out.println("================================================將鏈表倒轉===============");// 單項鏈表倒轉，實現(xiàn)原理：創(chuàng)建一個單鏈表倒敘數(shù)據(jù)，將鏈表循環(huán)，每一次循環(huán)的數(shù)據(jù)作為倒轉鏈表的next值，// 倒敘鏈表的next值作為傳過來的數(shù)據(jù)的next值singleLinked.reverse();singleLinked.show();//============================鏈表倒敘打印=================System.out.println("============================鏈表倒敘打印=================");singleLinked.stack();} } // 單鏈表 處理類 class SingleLinked{// head信息，在鏈表的第一個，不能變動private HeroNode heroNodeHeard = new HeroNode(0, "");// 添加public void addByNo(HeroNode heroNode){// 添加輔助節(jié)點HeroNode temp = heroNodeHeard;boolean isRep = false;while (true){// 當前節(jié)點next為null,退出if(temp.next == null){break;}// 當前節(jié)點next值的no值大于傳入進來的heroNode中的no值（因為是從小到大排序），則退出if(temp.next.no > heroNode.no){break;}else if (temp.next.no == heroNode.no){isRep = true;}temp = temp.next;}if(isRep){System.out.println("有重復數(shù)據(jù)，報錯.");}else{// 到了這里，temp中的next就應該放入?yún)eroNodeheroNode.next = temp.next;temp.next = heroNode;}}//顯示public void show(){if(heroNodeHeard.next == null){System.out.println("沒有添加數(shù)據(jù)");}else{// 頭信息不能動HeroNode temp = heroNodeHeard.next;while (true){System.out.println(temp);if(temp.next == null){break;}temp = temp.next;}}}// 顯示長度 heroNodeHeard 為頭節(jié)點public int getLength() {// next沒值返回0if(heroNodeHeard.next == null){return 0;}// next有值進行循環(huán)int size = 0;HeroNode temp = heroNodeHeard.next;while (true){size ++;if(temp.next != null){temp = temp.next;}else{break;}}return size;}// 查找單鏈表中的倒數(shù)第k個結點public HeroNode selectReciIndex(int index){// index是否合理 // index不能比長度大if(index <= 0 || index > getLength()){return null;}// 用長度減去index，得到應該查詢第幾條數(shù)據(jù)int shouldSelectLength = getLength() - index + 1;// 進行循環(huán)，查找到數(shù)據(jù)HeroNode temp = heroNodeHeard.next;for (int i = 1; i < shouldSelectLength; i++){temp = temp.next;}return temp;}// 倒轉鏈表public void reverse(){// 定義一個輔助變量，幫助我們遍歷原來的鏈表HeroNode cur = heroNodeHeard.next;HeroNode next = null; // 指向當前節(jié)點[cur]的下一個節(jié)點// 倒轉數(shù)組HeroNode reverseHead = new HeroNode(0, "");// 遍歷原來的鏈表，每遍歷一個節(jié)點，就將其取出，并放在新的鏈表reverseHead的最前端while(cur != null){next = cur.next;// 將倒轉數(shù)據(jù)下面的next給cur,因為cur將會成為倒轉數(shù)組里面的第一個數(shù)據(jù)cur.next = reverseHead.next;reverseHead.next = cur;cur = next;}// 賦值，將revers中的next放入head的next中, head.next = reverse.nextheroNodeHeard.next = reverseHead.next;}// 鏈表倒敘輸出 方法1：使用倒轉鏈表的方法；方法2：使用棧的方式stackpublic void stack(){Stack<HeroNode> heroNodeStack = new Stack<HeroNode>();HeroNode next = heroNodeHeard.next;while(next != null){heroNodeStack.push(next);next = next.next;}while (heroNodeStack.size()>0){System.out.println(heroNodeStack.pop());}}}// 類 class HeroNode{// 編號public int no;// 名稱public String name;// 指向下一個元素的對象public HeroNode next;// 指向上一個元素的對象public HeroNode pre;HeroNode(int no, String name){this.no = no;this.name = name;}@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +'}';} }

1.5 單項環(huán)形表----約瑟夫問題

1.5.1 原型思路圖

1.5.2 代碼實現(xiàn)

package com.bear.線性結構.單項環(huán)形表;import java.beans.beancontext.BeanContext; import java.lang.invoke.LambdaConversionException;/** 單項環(huán)形表----約瑟夫問題* <簡述> 一個對象賦值給另一個對象，另一個對象可以改變自己的結構，但是如果改變自己的值，那么一個對象也會改變，這是因為* 他們指向內(nèi)存的值的內(nèi)存地址是同一個* <詳細描述>** @author LiuShanshan* @version $Id$*/ public class Josepfu {public static void main(String[] args) {CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();// 添加afor(int i = 1; i<=4; i++){circleSingleLinkedList.add(new Boy(i));}// ==============查詢=============System.out.println(" ==============查詢=============");circleSingleLinkedList.show();// =============取出數(shù)據(jù)===============System.out.println("=============取出數(shù)據(jù)===============");circleSingleLinkedList.delete(1,2);} }class CircleSingleLinkedList{private Boy first = null;// 增public void add(Boy needBoy){if(first == null){first = needBoy;first.next = first;}// 給first后面增加數(shù)據(jù)Boy cusboy = first.next;while (true){if(cusboy.next == first){needBoy.next = first;cusboy.next = needBoy;break;}cusboy = cusboy.next;}System.out.println("添加成功");}// 出圈/***<簡述>*<詳細描述>* @author Liushanshan* @param startNo 從哪條數(shù)據(jù)開始* @param nums 間隔幾個數(shù)據(jù)進行取出* @return void*/public void delete(int startNo, int nums){// 判斷當前first是否為空// 開始取出，需要cub(當前輔助節(jié)點); later（cub只有的一個節(jié)點）Boy later = first;// 給later賦值為first的最后一個值while(true){if(later.next == first){break;}later = later.next;}// 開始位置為nums-1 ,確認開始循環(huán)的位置for (int i = 0; i < startNo - 1; i++){first = first.next;later = later.next;}// 開始循環(huán)，每次循環(huán)次數(shù)為nums-1while (true){// 退出if(later == first){break;}for(int j = 0; j < nums -1; j++){first = first.next;later = later.next;}// 要出圈的小孩System.out.printf("\n要出去的數(shù)據(jù)：%s", first);// 因為已經(jīng)出圈了，所以將later里面的next設置為first.nextfirst = first.next;later.next = first;}System.out.printf("\n最后一個數(shù)據(jù)為：%s", later);}// 改 改變里面的數(shù)據(jù)最簡單，不實現(xiàn)//查public void show(){// 判斷first是否為空if(first == null){System.out.println("數(shù)據(jù)為空，請?zhí)砑訑?shù)據(jù)");return;}// 循環(huán)查詢，結束語句為cub.next = firstBoy cub = first;while (true){if(first.next == first){System.out.printf("當前只有一個數(shù)據(jù)為：%s", first);break;}if(cub.next == first){break;}System.out.printf("\n開始打印數(shù)據(jù)：%s", cub);cub = cub.next;}System.out.printf("\n最后一個數(shù)據(jù)為：%s", cub);}}class Boy{public int no;public Boy next;Boy(int no){this.no = no;}@Overridepublic String toString() {return "Boy{" +"no=" + no +'}';} }

1.6 棧

1.6.1 棧的原理

棧的原理遵循先進后出的原理，所以可以用數(shù)組進行模擬

• 1)棧的英文為(stack)
• 2)棧是一個先入后出(FILO-FirstInLastOut)的有序列表。
• 3)棧(stack)是限制線性表中元素的插入和刪除只能在線性表的同一端進行的一種特殊線性表。允許插入和刪除的一端，為變化的一端，稱為棧頂(Top)，另一端為固定的一端，稱為棧底(Bottom)。
• 4)根據(jù)棧的定義可知，最先放入棧中元素在棧底，最后放入的元素在棧頂，而刪除元素剛好相反，最后放入的元素最先刪除，最先放入的元素最后刪除
• 5)圖解方式說明出棧(pop)和入棧(push)的概念
  

1.6.2 代碼

package com.bear.線性結構.棧;/** 棧的實現(xiàn)使用數(shù)組的方式，遵循先進后出的原則* <簡述>* <詳細描述>** @author LiuShanshan* @version $Id$*/ public class StackTest {public static void main(String[] args) {Stack stack = new Stack(3);stack.show();System.out.println("===============添加數(shù)據(jù)==================");stack.add(1);stack.add(2);stack.add(3);stack.show();} }class Stack {// 數(shù)組private int[] arry ;// topprivate int top;// 放入的值private int value;Stack(int length){this.arry = new int[length];this.top = -1;}//是否滿private boolean isFull(){return arry.length == top + 1;}// 是否為空private boolean isEntity(){return top == -1;}// 添加public void add (int value){// 判斷是否已滿if(isFull()){System.out.println("容量已滿");return;}// 放入值，top+1this.value = value;top ++;arry[top] = this.value;}// 查，顯示public void show(){// 是否為空if(isEntity()){System.out.println("容器為空，請先添加數(shù)據(jù)");return;}// 顯示for(int i = top; i>= 0; i--){System.out.printf("\n輸出數(shù)據(jù):%s", arry[i]);}}}

1.7 逆波蘭表達式

1.7.1逆波蘭表達式原理

1.7.2 逆波蘭表達式寫計算器()

package com.bear.線性結構.后綴表達式;import java.util.ArrayList; import java.util.List; import java.util.Stack;/*** <簡述> 后綴表達式（逆波蘭表達式）* <詳細描述>1、逆波蘭表達式計算 2、中綴表達式轉后綴表達式（逆波蘭表達式）** @author LiuShanshan* @version $Id$*/ public class PolandNotation {public static void main(String[] args) {// (3+4)×5-6對應的后綴表達式就是3 4 + 5 × 6 -// 2.逆波蘭表達式計算List<String> exp = new ArrayList<>();exp.add("3");exp.add("4");exp.add("+");exp.add("5");exp.add("*");exp.add("6");exp.add("-");System.out.printf("計算出來的值為：%s", calculate(exp));// 1.中綴表達式轉后綴表達式}// 逆波蘭表達式，計算出值public static int calculate(List<String> exp){Stack<Integer> integerStack = new Stack<>();if(exp.size() == 0){System.out.println("沒有需要計算的數(shù)據(jù)");}// 加入棧，并且計算，計算邏輯為：壓入數(shù)據(jù)，遇到運算符的時候，取出最上面的2個數(shù)據(jù)，進行計算，將計算出來的值放回棧，直到運算到// 棧中只剩下一個值為止for (String s : exp) {// 如果是數(shù)字，則直接放入棧if(s.matches("\\d+")){integerStack.push(Integer.valueOf(s));}else{// 如果是符號，則從棧中取出2個數(shù)據(jù)進行計算，然后再放回棧Integer pop2 = integerStack.pop();Integer pop1 = integerStack.pop();//判斷當前是 + - * / 哪一個if("+".equals(s)){integerStack.push(pop1 + pop2);}else if ("-".equals(s)){integerStack.push(pop1 - pop2);}else if("*".equals(s)){integerStack.push(pop1 * pop2);}else if("/".equals(s)){integerStack.push(pop1/pop2);}}}return integerStack.pop();}}

1.7.3 中綴轉后綴表達式（逆波蘭表達式）

todo 后面再寫

1.8 遞歸

1.8.1 遞歸的原理和圖解

總結：遞歸總的來說是將遞歸的方法，放在棧里面，每一個方法都是獨立開來的，因為是棧，所以先放后拿，從最上面方法開始計算。

1.8.2 遞歸遵守的重要原則

• 1)執(zhí)行一個方法時，就創(chuàng)建一個新的受保護的獨立空間(棧空間)
• 2)方法的局部變量是獨立的，不會相互影響,比如n變量
• 3)如果方法中使用的是引用類型變量(比如數(shù)組)，就會共享該引用類型的數(shù)據(jù).
• 4)遞歸必須向退出遞歸的條件逼近，否則就是無限遞歸,出現(xiàn)StackOverflowError，死龜了:)
• 5)當一個方法執(zhí)行完畢，或者遇到return，就會返回，遵守誰調(diào)用，就將結果返回給誰，同時當方法執(zhí)行完畢或者返回時，該方法也就執(zhí)行完畢

1.8.3 遞歸解決迷宮問題

代碼：

package com.bear.線性結構.遞歸;/** 迷宮問題（小球找路）* <簡述>* <詳細描述>** @author LiuShanshan* @version $Id$*/ public class Maze {public static void main(String[] args) {// 定義規(guī)則，定義一個二維數(shù)組，給里面的增加1代表墻int[][] map = new int[8][7];for(int i = 0; i<8; i++){map[i][0] = 1;map[i][6] = 1;}for(int j = 0; j< 7; j++){map[0][j] = 1;map[7][j] = 1;}// 第4行，第二列，第三列為1map[3][1] = 1;map[3][2] = 1; // // 循環(huán)打印，看是不是組成了一個墻 // 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("===========開始走迷宮===========");Way way = new Way();way.getOutLet(map, 1, 1);System.out.println("============迷宮map圖=========");for(int i = 0; i< 8; i++){for(int j = 0; j<7; j++){System.out.print(map[i][j] + " ");}System.out.println();}}}class Way{/***<簡述> 注意：1）需要指定規(guī)則，這個地圖該如何走，這里指定 下->右->左->上 的規(guī)則；* 2）1為墻，0為可以走，2為已經(jīng)走過得地方，3為不能走*<詳細描述>* @author Liushanshan* @param map 地圖 注意：不需要返回map，因為這里的數(shù)組是引入數(shù)據(jù)類型，用的地址是同一個* @param i 行* @param j 列* @return void*/public boolean getOutLet(int[][] map, int i ,int j){if(map[6][5] == 2){return true;}else if(map[i][j] == 0){ // 當為0時map[i][j] = 2;if(getOutLet(map, i+1, j)){// 往下走可以走return true;}else if(getOutLet(map, i, j+1)){// 往右走可以走return true;}else if(getOutLet(map,i, j-1)){// 往左邊走可以走return true;}else if(getOutLet(map, i-1, j)){// 往上邊走可以走return true;}else{map[i][j] = 3;return false;}}else {return false;}} }

1.8.4 八皇后問題解決—回溯算法

1.8.4.1 八皇后問題解析

1.8.4.2 代碼

package com.bear.線性結構.遞歸;import com.bear.線性結構.稀疏數(shù)組.SparsearryTest;/*** <簡述> 8皇后問題* <詳細描述>** @author LiuShanshan* @version $Id$*/ public class Queue8 {public static void main(String[] args) {QueueTest queueTest = new QueueTest();queueTest.check(0);System.out.printf("一共有%d種解法:", QueueTest.count);} }class QueueTest{private int[] array;private int max;public static int count;QueueTest(){this.max = 8;array = new int[max];}// 開始計算public void check(int n){// 當循環(huán)到第9行，索引為8的時候，直接放回true，并且打印出arry里面的值 (這是退出條件)if(n == max){print();return;}// lien代表行，這里的循環(huán)代表把行里面的8個點都執(zhí)行一次 todo 循環(huán)行for(int i = 0; i<max; i++){//先把當前這個皇后n,放到該行的第1列array[n] = i;// 判斷是否沖突if(judge(n)){check(n +1);}}}// 判斷是否滿足8皇后的條件private boolean judge(int n ){ //判斷這一行數(shù)據(jù)跟之前的數(shù)據(jù)有沒有沖突，不滿足條件的for (int i = 0; i < n; i++){ // todo 循環(huán)行，保證行里面的列與8皇后滿足條件保持一致if(array[n] == array[i] /* 判斷在不在一條豎線上**/|| Math.abs(array[n] - array[i]) == Math.abs(n - i) /* 判斷在不在一條斜線上**/){return false;}}return true;}// 打印數(shù)組里面的值private void print(){count++;for (int i : array) {System.out.print(i +" ");}System.out.println("\n");}}

2、非線性結構

非線性結構包括：二維數(shù)組，多維數(shù)組，廣義表，樹結構，圖結構

算法

1、排序算法

1.1 排序算法的種類

1.2 時間復雜度

時間復雜度是根據(jù)時間頻度來的，如果時間頻度是T(n) = 2n+20，則他的時間復雜度是O(n)
說明：去掉次項（去掉不重要的，留下關于n的東西），就是時間復雜度
如T(n)=n2+7n+6的時間復雜度是n2

時間復雜度的官方說明：一般情況下，算法中的基本操作語句的重復執(zhí)行次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n)，使得當n趨近于無窮大時，T(n) / f(n) 的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作 T(n)=Ｏ( f(n) )，稱Ｏ( f(n) ) 為算法的漸進時間復雜度，簡稱時間復雜度。（說人話就是：時間頻度去掉常數(shù)，去掉低次項，去掉系數(shù)，就是時間復雜度，表示為Ｏ( f(n) ) ）

1.3 常見的時間復雜度

注釋：1-8是推薦指數(shù)從高到底，最推薦的是1），最不推薦的是8）

1.4 各個的排序算法和時間復雜度的具體關系圖

1.5冒泡排序

1.5.1 冒泡排序思路網(wǎng)站

https://www.w3cschool.cn/article/49755893.html

1.5.2 代碼

package com.bear.排序算法.冒泡排序;import sun.plugin2.os.windows.FLASHWINFO;/** 冒泡排序* <簡述>* <詳細描述>** @author LiuShanshan* @version $Id$*/ public class BubblingDemo {public static void main(String[] args) {int[] arrayInt = {-1, 0 ,34, 23, 90, -5};// 問題：將數(shù)組從小到大排序int temp;boolean flag = true;// todo：解決思路:每次循環(huán)將最大/最小的數(shù)據(jù)找到，然后下一次循環(huán)-1次數(shù)for(int i = 0; i< arrayInt.length -1; i++){ // todo 循環(huán)次數(shù)for(int j = 0; j< arrayInt.length-1 - i; j++){ // todo 實際工作的循環(huán)次數(shù)if(arrayInt[j] > arrayInt[j+1]){flag = false;temp = arrayInt[j];arrayInt[j] = arrayInt[j+1];arrayInt[j+1] = temp;}}if(flag){break;}}for (int i : arrayInt) {System.out.println(i);}} }

1.6 選擇排序

1.6.1 思路

假設一個長度為4的數(shù)組，循環(huán)遍歷 4次，設置每一次循環(huán)的索引為n，當n =0 時，根據(jù)循環(huán)排序的規(guī)則，需要遍歷后面的n=1,2,3數(shù)據(jù)相比較，如果比n=0小，則調(diào)換2者位置；當n=1時，遍歷后面的n=2,3數(shù)據(jù)相比較，如果比n=1小，則交換2者位置…，一直到循環(huán)排序完，實際上循環(huán)了n-1次，因為最后一次不用循環(huán)。

1.6.2代碼

package com.bear.排序算法.選擇排序;import com.bear.線性結構.稀疏數(shù)組.SparsearryTest;/*** <簡述> 選擇排序* <詳細描述>** @author LiuShanshan* @version $Id$*/ public class SelectSort {public static void main(String[] args) {int[] ints = {12, 1, -1, 34, -89};sort(ints);}// 選擇排序public static void sort(int[] array){// 這里的for代表循環(huán)次數(shù)for(int i = 0; i< array.length -1 ; i++){int minIndex = i;int min = array[i];for(int j = 1 + i; j<array.length; j++){// 查詢到滿足條件的數(shù)據(jù)if(array[j] < min){minIndex = j;min = array[j];}}// 如果發(fā)生變化，則將位置互換if(minIndex != i){array[minIndex] = array[i];array[i] = min;}}// 打印數(shù)據(jù)for (int i : array) {System.out.print(i + " ");}} }

1.6.3 測試速度（比冒泡排序塊）

80000條數(shù)據(jù)，使用選擇排序只需要4s，冒泡排序則需要很長時。

1.7 插入排序

1.7.1、思路

17.2、代碼

int insertVal = 0;int insertIndex = 0;for(int i = 1; i < arr.length; i++) {insertVal = arr[i]; // 從第二個值開始循環(huán)往后，第一個值獲取不到insertIndex = i - 1; // 從第一個索引循環(huán)玩往后，最后一個索引獲取不到；索引在值的前面，默認是在值的前面第一位while (insertIndex >= 0 && insertVal < arr[insertIndex]) {arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]insertIndex--;}if(insertIndex + 1 != i) {arr[insertIndex + 1] = insertVal;}}for (Integer integer : arr) {System.out.println(integer);}

2、查找算法

2.1、查找算法定義

2.2、順序線性查找 (就是普通的for循環(huán)的去找有沒有數(shù)據(jù))

2.3、二分查找法

public static void main(String[] args) {// 需要 左索引，右索引，需要查找的值int[] arr = {1,45,50,60,99,120};int test = test(arr, 0, arr.length - 1, 99);System.out.println("當前值的索引為：" + test);}public static int test(int[] arr, int leftIndex, int rightIndex, int valueof){if(leftIndex > rightIndex){return -1;}int midIndex = (leftIndex + rightIndex)/2;if(arr[midIndex] < valueof){// 往右找return test(arr, midIndex, rightIndex, valueof);}else if(arr[midIndex] > valueof){// 往左找return test(arr, leftIndex, midIndex, valueof);}else {return midIndex;}}

2.3.1、二分查找法查詢多條重復數(shù)據(jù)

package com.bear.查找算法.二分查找法;import java.util.ArrayList; import java.util.List;/** 二分查找法* 二分查找法的前提就是列表需要先排好序* @author LiuShanshan* @version V1.0* @Description*/ public class BinaryTest {public static void main(String[] args) {// 需要 左索引，右索引，需要查找的值int[] arr = {1,45,50,60,99,99,120};List<Integer> objects = new ArrayList<>();test(arr, 0, arr.length - 1, 99, objects);System.out.println("當前值的索引為：" + objects);}public static void test(int[] arr, int leftIndex, int rightIndex, int valueof, List<Integer> valudofIndexArr){if(leftIndex > rightIndex){return ;}int midIndex = (leftIndex + rightIndex)/2;if(arr[midIndex] < valueof){// 往右找test(arr, midIndex, rightIndex, valueof, valudofIndexArr);}else if(arr[midIndex] > valueof){// 往左找test(arr, leftIndex, midIndex, valueof, valudofIndexArr);}else {valudofIndexArr.add(midIndex);// 往左移動int temp = midIndex -1;while (true){if(temp <0 || arr[temp] != arr[midIndex]){break;}valudofIndexArr.add(temp);temp = temp -1;}// 往右移動int temp2 = midIndex + 1;while (true){if(temp2 > arr.length -1 || arr[temp2] != arr[midIndex]){break;}valudofIndexArr.add(temp2);temp2 = temp2 + 1;}}} }

2.4、插值查找算法 （與二分查找算法的區(qū)別在于midindex的算法不同）

package com.bear.查找算法.插入查找法;import com.sun.org.glassfish.gmbal.Description;import java.util.ArrayList; import java.util.List;/** 插值查找算法和二分查找法的區(qū)別在于 ：midIndex 的算法不同* @author LiuShanshan* @version V1.0* @Description*/ public class CharRuBinaryTest {public static void main(String[] args) {// 需要 左索引，右索引，需要查找的值int[] arr = {1,45,50,60,99,99,120};List<Integer> objects = new ArrayList<>();test(arr, 0, arr.length - 1, 99, objects);System.out.println("當前值的索引為：" + objects);}public static void test(int[] arr, int leftIndex, int rightIndex, int valueof, List<Integer> valudofIndexArr){if(leftIndex > rightIndex){return ;}int midIndex = leftIndex + (rightIndex - leftIndex) * (valueof - arr[leftIndex]) / (arr[rightIndex] - arr[leftIndex]);if(arr[midIndex] < valueof){// 往右找test(arr, midIndex, rightIndex, valueof, valudofIndexArr);}else if(arr[midIndex] > valueof){// 往左找test(arr, leftIndex, midIndex, valueof, valudofIndexArr);}else {valudofIndexArr.add(midIndex);// 往左移動int temp = midIndex -1;while (true){if(temp <0 || arr[temp] != arr[midIndex]){break;}valudofIndexArr.add(temp);temp = temp -1;}// 往右移動int temp2 = midIndex + 1;while (true){if(temp2 > arr.length -1 || arr[temp2] != arr[midIndex]){break;}valudofIndexArr.add(temp2);temp2 = temp2 + 1;}}} }

最后

碼云代碼地址：

在這里插入代碼片

總結

以上是生活随笔為你收集整理的算法和数据结构(b站尚硅谷韩老师教程学习笔记)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。