前言

视频地址：/video/BV1E4411H73v?from=search&seid=13120683720695451628

评价：整个教程的数据结构部分讲的挺好的，知识点全都覆盖了，而且每个数据结构都有代码解释，但是最后20节算法部分讲的有点乱，算法部分我决定直接刷leetcode了

数组

稀疏数组：

二维数组的省内存的保存方法，一般是n行3列，三列分别为行，列，值。

二维数组转稀疏数组：

遍历整个二维数组，查看有多少个有效数字根据有效数字的个数，创建稀疏数组遍历二维数组，将有效的数字放入稀疏数组中

稀疏数组转二维数组：

根据稀疏数组第一行建立空二维数组

读取稀疏数组后几行数据，插入二维数组中

代码实现：

package com.dataStructure;public class sparseArray {public static void main(String[] args){//新建数组int Arr [][] = new int[11][11];Arr[1][2] = 1;Arr[2][3] = 2;Arr[3][4] = 3;//输出初始数组for(int[] row : Arr){for(int data : row){System.out.printf("%d\t",data);}System.out.print("\n");}//将二维数组转换为稀疏数组//1 遍历，得到非0个数int sum = 0;for (int i = 0; i < 11; i++){for (int j = 0; j < 11; j++){if (Arr[i][j] != 0){sum++;}}}//2 创建稀疏数组int[][] sparsArr = new int[sum+1][3];//第一行sparsArr[0][0] = 11;sparsArr[0][1] = 11;sparsArr[0][2] = sum;//输入值int count = 1;//用于记录sparseArr的行for (int i = 0; i < 11; i++){for (int j = 0; j < 11; j++){if (Arr[i][j] != 0){sparsArr[count][0] = i;sparsArr[count][1] = j;sparsArr[count][2] = Arr[i][j];count++;}}}//3 输出稀疏数组System.out.println();System.out.println("得到的稀疏数组为～～～");for(int i = 0 ;i< sparsArr.length ;i++){System.out.printf("%d\t%d\t%d\t\n",sparsArr[i][0],sparsArr[i][1],sparsArr[i][2]);}//将二维数组转换回稀疏数组//1 新建数组int[][] Arr_back = new int[sparsArr[0][0]][sparsArr[0][1]];//2 将有值的位置安回原来的位置for (int i = 1; i<sparsArr.length;i++){Arr_back[sparsArr[i][0]][sparsArr[i][1]] = sparsArr[i][2];}//输出数组System.out.println();System.out.print("Arr_back输出为～～～\n");for(int i = 0;i<sparsArr[0][0];i++){for(int j = 0;j<sparsArr[0][1];j++){System.out.print(Arr_back[i][j]+" ");}System.out.println();}}}

队列

队列是一个有序列表，可能用数组或链表来实现。

先进入的数据先取出，后进入的数组后取出。

数组模拟队列的思路：

队列本身就是一个有序列表，maxSize来记录该数组最大容量；front和rear分别记录队列前后端的下标，front随着数据输出而改变，rear随着数据输入而改变。

加入数据：若队列不为满，尾部指针后移：rear+1

拿出数据：若队列不为空，前端指针后移：front+1

代码：

package com.dataStructure;import java.util.Scanner;public class arrayQueue {public static void main(String[] args) {Queue arrayQueue = new Queue(3);String key = "";Scanner scanner = new Scanner(System.in);boolean loop = true;while (loop) {//输出一个菜单System.out.println("press s to show Queue");System.out.println("press e to exit program");System.out.println("press a to add element");System.out.println("press g to get data");key = scanner.next();switch (key) {case "s":arrayQueue.showQueue();break;case "e":scanner.close();loop = false;break;case"a":System.out.println("Input a word:");int value = scanner.nextInt();arrayQueue.addQueue(value);break;case"g":System.out.println(arrayQueue.getQueue());break;}}}}class Queue {//装入👴需要的私有变量private int rear = -1;private int front = -1;private int maxSize;private int[] que;//设置Queue的规格public Queue(int size) {maxSize = size;que = new int[size];}//判断Queue是否为空public boolean isEmpty() {return rear == front;}//判断Queue满了没public boolean isFull() {return rear == maxSize - 1;}//加入一个新元素public void addQueue(int n) {if (isFull()) {System.out.println("Queue is full! can not add!");return;}rear++;que[rear] = n;}//删除一个元素public int getQueue() {if (isEmpty()) {throw new RuntimeException("Queue is empty! can not delete!");}front++;return que[front];}//showQueuepublic void showQueue() {if (isEmpty()) {System.out.println("队列空，无数据，无法showQueue");} else {for (int i = 0; i < que.length; i++) {System.out.printf("Queue[%d] = %d\n", i, que[i]);}}}}

这时候存在一个问题，数组使用一次之后就不能用了，没有达到复用的效果，例如，我将位置填满后再全部删去，这时候我就没办法再add新的元素进去了。

使用数组模拟形成一个环形队列，利用取模的方式实现。

使用数组模拟环形队列

思路：

Front作为队列第一个元素的引用，初始front = 0

Rear作为队列最后一个元素的后一个元素的引用，初始rear = 0

队列满时，条件为(rear+1)%maxSize = front。

这里要注意的是，虽然maxSize是5，但是我们实际可以使用的只有4个。当总共有5个格子时，分别为0，1，2，3，4，满了的时候，rear = 4，front = 0，maxSize = 5；带入公示4+1模除5 = front = 0。

队列空时，rear = front。

当rear-1=front时，实际上只有一个元素，就是front所在的位置；当rear = front的时候，最后一个元素rear-1在最初的元素front之前，所以这种情况不存在。

队列中有效数字的个数为（rear-front+maxSize）% maxSize。

综合4来理解，rear-1 = front时候，存在一个元素，rear = front的时候，不存在元素，maxSize%maxSize永远为0，所以很显然（rear-front）% maxSize就是存在有效数字的个数。这里一定要加maxSize再取模，因为rear-front可能是负数，所以必加。

代码：

package com.dataStructure;import java.util.Scanner;public class arrayCircleQueue {public static void main(String[] args) {CircleQueue arrayQueue = new CircleQueue(4);String key = "";Scanner scanner = new Scanner(System.in);boolean loop = true;while (loop) {//输出一个菜单System.out.println("press s to show Queue");System.out.println("press e to exit program");System.out.println("press a to add element");System.out.println("press g to get data");key = scanner.next();switch (key) {case "s":arrayQueue.showQueue();break;case "e":scanner.close();loop = false;break;case"a":System.out.println("Input a word:");int value = scanner.nextInt();arrayQueue.addQueue(value);break;case"g":System.out.println(arrayQueue.getQueue());break;}}}}class CircleQueue {//装入👴需要的私有变量private int rear = 0;private int front = 0;private int maxSize;private int[] que;//设置Queue的规格public CircleQueue(int size) {maxSize = size;que = new int[size];}//判断Queue是否为空public boolean isEmpty() {return rear == front;}//判断Queue满了没public boolean isFull() {return (rear+1)%maxSize == front;}//加入一个新元素public void addQueue(int n) {if (isFull()) {System.out.println("Queue is full! can not add!");return;}que[rear] = n;rear = (rear+1)%maxSize;}//删除一个元素public int getQueue() {if (isEmpty()) {throw new RuntimeException("Queue is empty! can not delete!");}int value = que[front];front = (front+1)%maxSize;return value;}//showQueuepublic void showQueue() {if (isEmpty()) {System.out.println("队列空，无数据，无法showQueue");} else {for (int i = front; i < front+(rear+maxSize-front)%maxSize; i++) {System.out.printf("Queue[%d] = %d\n", i%maxSize, que[i%maxSize]);}}}}

链表

单链表

链表每个节点包含data域，next域：指向下一个节点

创建HeroNode类，其中包含HeroNode next；

创建LinkedList类，先创建一个头节点

遍历思路：

通过一个辅助变量来遍历

一般来说，展示链表中所有数据要先判断链表是否为空。

添加内容思路：

直接添加到尾部：直接加到最后面（遍历找到最后面，再添加）

按顺序添加：找到要添加的位置，新节点.next = temp.next，temp.next = 新节点。

修改节点的思路：

先找到这个节点（遍历）

修改数值

删除节点的思路：

找到要删除节点的前一个节点

Node.next = node.next.next;

被删除的节点将没有其他引用指向它，会被垃圾回收机制回收

循环要注意的点！！！

一般来说，写while循环的时候，内容的顺序是：1）输出，2）if边界的break测试，3）指针后移

循环代码：

void show(){NodeStack temp = head.next;while(true){System.out.println("栈中的值为"+temp.value);if(temp.next == null){break;}temp = temp.next;}}

单链表代码：

package com.dataStructure;public class linkedList {public static void main(String[] args){HeroNode heroNode1 = new HeroNode(1,"阿毛","amao");HeroNode heroNode2 = new HeroNode(2,"阿狗","agou");HeroNode heroNode3 = new HeroNode(3,"阿缺","aque");singleLinkedList list_test = new singleLinkedList();//乱序输入结果list_test.addSpecial(heroNode1);list_test.addSpecial(heroNode3);list_test.addSpecial(heroNode2);list_test.show();//测试修改HeroNode heroNode4 = new HeroNode(3,"阿","a");list_test.update(heroNode4);System.out.println("修改后的结果～～～");list_test.show();//删除测试int test_num = 1;list_test.del(test_num);System.out.println("删除后的结果");list_test.show();}}class HeroNode{int no;String name;String nickName;HeroNode next;public HeroNode(int no,String name,String nickName){this.no = no;this.name = name;this.nickName = nickName;}@Overridepublic String toString(){return "Hero_no = "+no+" Hero_name = "+name+" Hero_nickname = "+nickName ;}}class singleLinkedList{private HeroNode head = new HeroNode(0,"","");public void add(HeroNode heroNode){HeroNode temp = head;while(true){if(temp.next == null){break;}temp = temp.next;}temp.next = heroNode;}public void addSpecial(HeroNode heroNode){HeroNode temp = head;boolean label = false;while(true){if(temp.next == null){break;}if(heroNode.no<temp.next.no){break;}if(heroNode.no == temp.next.no){label = true;break;}temp = temp.next;}if(label){System.out.println("没位置了！爬！");}else {heroNode.next = temp.next;temp.next = heroNode;}}public void update(HeroNode newNode) {HeroNode temp = head;boolean flag = false;while (true) {if (temp == null) {break;}if (temp.no == newNode.no) {flag = true;break;}temp = temp.next;}if(flag) {temp.name = newNode.name;temp.nickName = newNode.nickName;}else{System.out.println("can not find this no!");}}public void del(int num){HeroNode temp = head;boolean flag = false;while(true){if(temp.next == null){break;}if(temp.next.no == num){flag = true;break;}temp = temp.next;}if(flag){temp.next = temp.next.next;}else{System.out.println("没找到要删除的啊？");}}public void show(){if(head.next == null){System.out.println("列表为空，输出个犊子");}else{HeroNode temp = head.next;while(true){if(temp == null){break;}System.out.println(temp);temp = temp.next;}}}}

单链表的反转

思路：

先定义一个revertHead = new Node();

从头到尾遍历原来的表，依次取出节点，并将它放在revertHead的最前端（head后面）

原来的链表的head.next = revertHead.next，将除了head以外的内容还给原来的head

难点：

实现从原来的链表中遍历，并将元素挨个放到新链表的头部，需要多次调整两个链表的指向问题。

代码：

public void reverse(Node head) {if(head.next == null || head.next.next == null){return;}Node cur = head.next;Node next = null;Node revertHead = new Node(0);while(cur!=null){next = cur.next; //将cur后面的值暂时存储在next中cur.next = revertHead.next;//让cur指向原来revertHead数组的第一个元素revertHead.next = cur;//让revertHead指向cur，这样就实现了一种类似中间插入的操作（revertHead列表头处插入）cur = next;//更新cur}head.next = revertHead.next; //将一大串列表还给原来的head}

倒叙打印单链表

思路1: 先反转链表，再打印链表

思路2: 利用栈，将单链表压入栈，再打印输出

思路2代码：

public void revertPrint(){Stack<Integer> stack = new Stack();if (head.next == null) {System.out.println("列表为空，输出个犊子");} else {Node temp = head.next;while (true) {if (temp == null) {break;}stack.add(temp.value);temp = temp.next;}}while(stack.size()>0) {System.out.println(stack.pop());}}

单链表所有功能代码

包含测试各种刚才提到的功能

package com.dataStructure;import java.util.Scanner;import java.util.Stack;public class linkedList_test {public static void main(String[] args){Node node1 = new Node(1);Node node2 = new Node(2);Node node3 = new Node(3);linkedList_test1 test1 = new linkedList_test1();test1.add(node1);test1.add(node2);test1.add(node3);//展示目前的情况System.out.println("目前链表的情况～～～");test1.show();//统计元素个数System.out.println("链表总数～～～");int res = test1.count();System.out.println(res);//输入一个数k，输出列表中倒数第k个数// System.out.println("please input a value");// Scanner scanner = new Scanner(System.in);// int k = scanner.nextInt();// System.out.println("倒数第 "+k+" 个数是 "+test1.find(test1,k));//翻转单链表// System.out.println("链表翻转结果～～～");// test1.reverse(test1.head);// test1.show();//逆序输出System.out.println("链表翻转输出结果为～～～");test1.revertPrint();}}class Node{int value;Node next;public Node(int value){this.value = value;}@Overridepublic String toString(){return "my value is "+value;}}class linkedList_test1 {Node head = new Node(0);//加入一个元素public void add(Node nodeIn) {Node temp = head;while (true) {if (temp.next == null) {break;}temp = temp.next;}temp.next = nodeIn;}//打印所有元素public void show() {if (head.next == null) {System.out.println("列表为空，输出个犊子");} else {Node temp = head.next;while (true) {if (temp == null) {break;}System.out.println(temp);temp = temp.next;}}}//计算一共多少个数public int count() {int counting = 0;Node temp = head.next;if (temp == null) {System.out.println("啥也没有，共0个元素");} else {while (true) {counting++;if (temp.next == null) {break;}temp = temp.next;}}return counting;}//在test1中寻找倒数第k个数是多少public int find(linkedList_test1 test1, int k) {if((k>test1.count()) || (k<=0)){throw new RuntimeException("input error!");}else{Node temp = head;int sum = test1.count();int need = sum - k+1; //我们需要正着数到第need个数int value = 0;//作为一个判定条件while (true) {temp = temp.next;value++;if (value == need) {break;}}return temp.value;}}//反转链表public void reverse(Node head) {if(head.next == null || head.next.next == null){return;}Node cur = head.next;Node next = null;Node revertHead = new Node(0);while(cur!=null){next = cur.next; //将cur后面的值暂时存储在next中cur.next = revertHead.next;//让cur指向原来revertHead数组的第一个元素revertHead.next = cur;//让revertHead指向cur，这样就实现了一种类似中间插入的操作（revertHead列表头处插入）cur = next;//更新cur}head.next = revertHead.next; //将一大串列表还给原来的head}//利用栈倒序输出链表public void revertPrint(){Stack<Integer> stack = new Stack();if (head.next == null) {System.out.println("列表为空，输出个犊子");} else {Node temp = head.next;while (true) {if (temp == null) {break;}stack.add(temp.value);temp = temp.next;}}while(stack.size()>0) {System.out.println(stack.pop());}}

双向链表

双向链表相对于单链表来说：

查找的方向不止是一个方向

可以实现自我删除，不需要像单链表一样寻找要删除节点的前一个节点

思路分析：

遍历：和单向链表一致，可以前向，也可以后向。

添加元素到链表最后：1） 先遍历到这个链表的最后

​ 2） temp.next = newNode; newNode.pre = temp;

按照编号添加元素：1） 找到要添加的位置的前一个元素temp

​ 2） heroNode.next = temp.next;

​ 3） temp.next = heroNode;

​ 4） heroNode.next.pre = heroNode;

​ 5） heroNode.pre = temp; //这些步骤本质上就是将原来的两根指针变成四根

修改：找到这个节点直接修改就可以

自我删除：

1） 找到这个节点

​ 2） temp.pre.next = temp.next;

temp.next.pre. = temp.pre;

（当删除的节点是最后一个时，后面句话不需要，否则会出现空指针）

代码：

//构建一个双向列表的节点class Node{int value;Node next;Node pre;public Node(int value){this.value = value;}@Overridepublic String toString(){return "my value is "+value;}}

//加入一个元素public void add(Node nodeIn) {Node temp = head;while (true) {if (temp.next == null) {break;}temp = temp.next;}temp.next = nodeIn;nodeIn.pre = temp;}//按序号加入元素public void addSpecial(Node heroNode){Node temp = head;boolean label = false;while(true){if(temp.next == null){break;}if(heroNode.value<temp.next.value){break;}if(heroNode.value == temp.next.value){label = true;break;}temp = temp.next;}if(label){System.out.println("没位置了！爬！");}else {heroNode.next = temp.next;temp.next = heroNode;heroNode.next.pre = heroNode;heroNode.pre = temp;}}

单向环形链表 joseph环问题

Joseph问题：n个小孩坐成一圈，编号为k的小孩从1开始报数，数到m的小孩出列，下一个小孩再从1开始报数，数到m出列，直到所有人出列为止，求出列的编号队列。

单向环形链表构建思路：

构建：

1） 先创建第一个节点，用first指向它，与自己形成环形队列。

2） 每创建一个新的节点，就把该节点加入到已有的环形列表中。

遍历：

1） 让辅助指针cur指向first

2） 通过while循环直到cur.next = first结束

约瑟夫问题：

1） 创建一个helper指针，指向first的前一个节点

2） 小孩报数前，移动k-1次helper和first

3） 开始数数，数m-1次，将first出列（first = first.next; helper.next = first），持续循环这个过程

4） 直到链表中剩余一个元素时退出循环（此时first = helper）

代码：

package com.dataStructure;public class circleSingleLinkedList {public static void main(String[] args){CircleList circleList = new CircleList();circleList.add(5);circleList.show(circleList);//测试circleList.out(1,2,5);}}class Boy{private int value;private Boy next;public Boy(int value){this.value = value;}public int getValue() {return value;}public Boy getNext() {return next;}public void setNext(Boy next) {this.next = next;}public void setValue(int value) {this.value = value;}}class CircleList{Boy first = null;Boy cur = null;public void add(int size){if(size<1){return;}else{for(int i = 1;i<=size;i++){Boy newBoy = new Boy(i);if (i == 1){first = newBoy;newBoy.setNext(first);cur = newBoy;}else{cur.setNext(newBoy);newBoy.setNext(first);cur = cur.getNext();}}}}public void show(CircleList list){if (list.first == null){System.out.println("小孩都被吃光了！！！");return;}if(list.first.getNext() == list.first){System.out.printf("只有一个小孩%d",list.first.getValue());}else{Boy temp = list.first;while(true){System.out.printf("第%d个小孩",temp.getValue());System.out.println();if (temp.getNext() == list.first){break;}temp = temp.getNext();}}}public void out(int startNo, int count, int nums){//startno:开始的序号 count：数几下 nums：总数if(startNo>nums || startNo < 1 || first == null){return;}//让helper到达初始位置Boy helper = first;while(true){helper = helper.getNext();if (helper.getNext() == first){break;};}//让first和helper找到开始数数的位置for(int i = 0; i < startNo-1; i++){helper = helper.getNext();first = first.getNext();}//开始数数，并且排除掉要拍出的数字，最终留下一个在链表中while(true){if (first == helper){break;}for (int j = 0; j < count-1; j++){helper = helper.getNext();first = first.getNext();}System.out.print(first.getValue()+" -> ");first = first.getNext();helper.setNext(first);}System.out.print(first.getValue());}}

栈（stack）

一个先入后出的有序列表

允许插入删除的一端为栈顶，固定的另一端为栈底

应用场景：

子程序的调用

处理递归调用

表达式的转换（中缀表达式转后缀表达式）与求值

二叉树的遍历

图形的深度优先搜索法

数组实现栈的思路：

1） 定义一个top表示栈顶，初始化为-1

2） 入栈：top++; stack[top] = data

3） 出栈：int value = stack[top]; top–; return value;

用单链表来实现栈的模拟：

package com.dataStructure;import java.util.Scanner;public class stack {public static void main(String[] args){ListStack listStack = new ListStack();listStack.setMaxSize(3);boolean loop = true;Scanner scanner = new Scanner(System.in);while(loop){System.out.println("push为入栈");System.out.println("pop为出栈");System.out.println("show为展示栈内容");System.out.println("exit为退出程序");System.out.println("输入你的选择！");String key = scanner.next();switch(key){case "push":System.out.println("输入一个数");int value = scanner.nextInt();NodeStack inputNode = new NodeStack(value);listStack.push(inputNode);break;case "pop":listStack.pop();break;case "show":listStack.show();break;case "exit":loop = false;scanner.close();break;}}}}class NodeStack{int value;NodeStack next;public NodeStack(int i){this.value = i;}@Overridepublic String toString(){return "Node's value is "+value;}}class ListStack{NodeStack head = new NodeStack(0);int MaxSize;void setMaxSize(int i){this.MaxSize = i;}boolean isMax(){NodeStack temp = head;int count = 0;while(true){if (temp.next == null){break;}temp = temp.next; //找到要加入的位置count++;}if (MaxSize>count){return false;}else {return true;}}boolean isEmpty(){if(head.next == null){return true;}else{return false;}}void push(NodeStack input) {NodeStack temp = head;if (isMax()) {System.out.println("栈满，请爬！");return;} else {while (true) {if (temp.next == null) {break;}temp = temp.next;}temp.next = input;}}void pop(){//出栈只能从最尾部出NodeStack temp = head;if(isEmpty()){return;}while(true){if(temp.next.next == null){break;}temp = temp.next; //找到要加入的位置}System.out.println("出栈的元素是"+ temp.next.value);temp.next = null;}void show(){NodeStack temp = head.next;while(true){System.out.println("栈中的值为"+temp.value);if(temp.next == null){break;}temp = temp.next;}}}

用栈实现综合计算器（加减乘除）

输入一串字符串，输出这一串算式的计算结果。例如输入“3 + 1 * 4 % 4“；输出：4

思路：

1） 创建两个栈

2） 按顺序遍历输入，如果是数字

a) 将数字存在一个字符串中b) 查看下一个字符是不是数字，是的话继续存在这个字符串中c) 遇到字符了，将拼接好的字符串push入数字栈，将临时字符串清空

3） 如果是字符

a) 字符栈为空，直接入栈；b) 字符栈已有字符，则进行比较i.新操作符优先级小于等于旧操作符，从数栈中pop出两个数，与用旧操作符进行运算，并将得到的结果入数栈，将新操作符入符号栈。ii.新操作符优先级大于旧操作符，直接入符号栈。

4） 表达式扫描完毕，顺序pop数字和运算符，并运行

5） 最后栈中的数字就是结果

前缀，中缀，后缀表达式

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

运算符位于操作数之前，（3+4）*5-6对应的是- * + 3 4 5 6

计算机求值：从右向左扫描表达式，遇到数字时，将数字压入栈；遇到运算符时，弹出栈顶两个元素（先弹出的-后弹出的），用运算符对他们进行运算，并将结果入栈，直至过程到达表达式最左端。

中缀表达式：

最常见的运算表达式

计算机操作时，一般会将其转换为后缀表达式来操作。

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

运算符位于操作符号之后，（3+4）*5-6对应的是3 4 + 5 * 6 –

计算机求值：从左向右扫描表达式，遇到数字时，将数字压入栈；遇到运算符时，弹出栈顶的两个数，用运算符对他们进行计算（后弹出的-先弹出的），并将结果入栈，直到扫描完毕整个表达式。

逆波兰表达式计算器：

使用栈来进行计算

package com.dataStructure;import java.util.ArrayList;import java.util.List;import java.util.Stack;public class stackPoland {public static void main(String[] args){String inputPoland = "30 4 + 5 * 6 -";System.out.println("当前list为：");System.out.println(list(inputPoland));System.out.println("运算结果为：");System.out.println(calculate(list(inputPoland)));}public static List<String> list (String inputPoland){String[] split = inputPoland.split(" ");List<String> tempList = new ArrayList<String>();for(String ele:split){tempList.add(ele);}return tempList;}public static int calculate(List<String> inputPoland){Stack<String> stack = new Stack<String>();for(String ele: inputPoland) {if (ele.matches("\\d+")) {//匹配的是多位数stack.push(ele);} else {int num1 = Integer.parseInt(stack.pop());int num2 = Integer.parseInt(stack.pop());int res = 0;if (ele.equals("+")){res = num1+num2;}else if(ele.equals("-")){res = num2-num1;}else if(ele.equals("*")){res = num1*num2;}else if(ele.equals("/")){res = num2/num1;}else{throw new RuntimeException("输入有误！");}stack.push(res+"");//遍历栈，查看当前情况}}return Integer.parseInt(stack.pop());}}

中缀表达式转后缀表达式

思路：

初始化两个栈，储存运算符的栈s1和储存中间结果的栈s2

从左至右扫描中缀表达式，直到表达式的最右边

a) 遇到操作数时，将其压入s2.

b) 遇到运算符时，比较其与s1栈顶的运算符优先级

​ i. 如果s1为空，或者栈顶运算符为左括号（，直接将此运算符入栈

​ ii. 否则，如果优先级比栈顶运算符高，也将运算符压入s1

​ iii. 否则，将s1栈顶的运算符弹出压入s2中，再次将新运算符送至2-b-i步骤，与栈顶运算符相比较

c） 遇到括号时

​ i. 如果是左括号（ ，直接压入s1

​ ii. 如果是右括号 ），则一次弹出s1栈顶的运算符，并压入s1，直到遇到左括号为止，并将这一对括号丢弃

将s1中剩余的运算符依次弹出并压入s2

S2中的逆序输出就是后缀表达式

递归

本质上就是自己调用自己，每次调用的时候传入不同的变量。

递归调用规则：

\1. 程序每执行到一个方法时，就会开辟一个独立的空间（栈）

\2. 每个空间的数据（局部变量），是独立的

\3. 一个方法执行完毕之后，或者遇到return，就会返回，谁调用，结果返回给谁。

递归迷宫问题

我们要使用递归的方法将下列map[1] [1]走到map[5] [4]。

思路分析：

数组中，1代表墙，2代表走过的路径，3代表死胡同，不要走

1） 创建一个二维数组作为map

2） 创建一个boolean类型的递归

a) 判断是否到达终点

​ i. 到达，返回true

​ ii. 未到达，判断当前点是否为可以走的，map = 0

可以走的话，将该点设置为2，用if-else尝试四个方向的走，用if来调用原函数，函数都返回true，如果四个方向都不能走，设置该点为3，返回false

不能走的话直接返回false

代码：

package com.dataStructure;public class puzzleBackTracking {public static void main(String[] args) {int[][] map = new int[8][7];for (int i = 0; i <= 7; i++) {map[i][0] = 1;map[i][5] = 1;}for (int j = 1; j < 6; j++) {map[0][j] = 1;map[6][j] = 1;}map[3][1] = 1;map[3][2] = 1;//打印一下mapfor (int i = 0; i < 7; i++) {for (int j = 0; j < 6; j++) {System.out.print(map[i][j] + " ");}System.out.println();}solving(map, 1, 1);//打印一下之后的mapSystem.out.println("解puzzle后～～～");for (int i = 0; i < 7; i++) {for (int j = 0; j < 6; j++) {System.out.print(map[i][j] + " ");}System.out.println();}}public static boolean solving(int[][] map, int i, int j) {if (map[5][4] == 2) {return true;//如果到达终点，直接return} else {if (map[i][j] == 0) {map[i][j] = 2;//事实上，这个函数定义为boolean类型，纯粹是为了这里的判断//判断是否可以继续按照这种方法走下去if (solving(map, i + 1, j)) {//先向下走return true;}else if (solving(map, i, j + 1)) {//向右走return true;}else if (solving(map, i - 1, j)) {//向上走return true;}else if (solving(map, i, j - 1)) {//向左走return true;} else {map[i][j] = 3;return false;}} else {return false; //这里return false的原因主要是想尝试另一种走法让//if-else继续下去。}}}}

递归-解决八皇后问题

在8*8的二维数组上放置8个棋子，每个棋子之间不在同一行，不在同一列，不在同一斜线，求有多少种摆法。

思路：

1） 第一行棋子从第一列开始摆放

2） 第二行棋子从第二行第一列开始摆放，分别判断是否可行，不可行的话，就继续尝试第二行第二列，第三列，第四列……

3） 继续摆放第三行的皇后，重复这个过程

4） 得到一个正确的解，继续这个过程，知道第一行第一列的棋子的所有正确解都得到

5） 移动第一个皇后，直至将所有列遍历

package com.dataStructure;import java.util.List;public class QueenN {static int count = 0;int size = 8;int[] array = new int[size];public static void main(String[] args){QueenN queenN = new QueenN();queenN.check(0);System.out.println("解法的数量为"+count);}public void check(int n){if(n == 8){print();return;}for (int i = 0; i<8; i++){array[n] = i;if(judge(n)){//如果满足条件check(n+1);}}}//判断是否符合规则public boolean judge(int n) {for (int i = 0; i < n; i++) {if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {return false;}}return true;}//打印输出public void print(){for(int i = 0;i<array.length ;i++){System.out.print(array[i]+" ");}System.out.println();count++;}}

排序算法

内部排序：直接使用内存的排序

直接插入排序，希尔排序，简单选择排序，堆排序，冒泡排序，快速排序，归并排序，基数排序

测试算法运行的时间

这里是用的是输出算法执行前的时间，和算法执行之后的时间，来查看算法实际花费的时间。

代码：

import java.text.SimpleDateFormat;import java.util.Date;//排序前的时间输出Date date = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String Date1 = simpleDateFormat.format(date);System.out.println("排序前的时间为"+Date1);//排序之后的时间的输出Date date_after = new Date();String Date2 = simpleDateFormat.format(date_after);System.out.println("排序前的时间为"+Date2);

时间频度

一个算法中的语句执行次数称为语句频度和时间频度，记为T（n）。

一般来说，T（n）可以忽略常数项，忽略低次项，忽略系数。

时间复杂度

常数阶O（1）

只要没有循环等复杂结构，都是O（1）。

所消耗的时间并不会随着某个变量的增长而增长。

对数阶O（log2N）

int i = 1;while(i<n){i = i*2;}

这段代码就是循环log2N次，结束循环。

线性阶O（n）

for(int i = 0;i<n;i++)

单层的for循环就是线性阶。

线性对数阶O（nlogN）

实际上就是对数阶循环了n遍

for(int j = 1;j<=n;j++){int i = 1while(i<n){i = i*2;}}

平方阶O（n^ 2）

实际上就是两个for循环嵌套

for(i = 1;i<=n;i++){for(j = 1;j<=n;j++){}}

常见时间复杂度排序：

O(1) < O(log2N) < O(n) < O(nlog2n) < O(n^2) < O(2^n)

算法的空间复杂度

定义为该算法所耗费的存储空间，有的算法需要占用的临时工作单元数与解决问题的规模n有关，随着n的增大，占用的存储单元也增大。

一般来说，从用户体验来说，更看重时间复杂度，一些缓存产品和算法本质上就是空间换时间。

冒泡排序

按照排序序列从前向后，依次比较相邻元素的值，若发现逆序则交换，使较大的元素移动到序列的尾部。

优化：如果发现某次排序没有进行过交换，则证明当前为排序完成的序列，设置一个flag来判断元素是否进行过交换，从而减少不必要的比较。

一般来说，会进行

n-1次大的循环每一趟排序的次数从n-1次开始减小发现某次循环中序列的顺序没有发生变化，则直接退出程序

代码实现：

package com.sortAlgorithm;public class bubbleSort {public static void main(String[] args){int list[] = {3,9,11,10,4};//打印之前的列表for(int i = 0; i<list.length; i++) {System.out.print(list[i]+" ");}System.out.println();//bubblebubbleSort bubbleSort = new bubbleSort();bubbleSort.bubble(list);//打印之后的列表for(int i = 0; i<list.length; i++) {System.out.print(list[i]+" ");}System.out.println();}public void bubble(int list[]){int count = 0;int size = list.length;for (int i = 0; i<size-1; i++) {for (int j = 0; j < size - 1; j++) {if (list[j] > list[j + 1]) {count++;int temp;temp = list[j + 1];list[j + 1] = list[j];list[j] = temp;}}if (count == 0) {System.out.println("提前结束了");return;} else {count = 0;}}}}

选择排序法

介绍：

从长度为n的序列中，找到最小的数字，将这个数字放到指定的位置，执行n-1次，实现排序。

思路：

一共有n-1轮排序（数组大小为n）每一轮排序都是一个循环 假定当前数字为最小值这个数与后面的数进行比较，如果有更小的数，则用更小的数替代当前的数作为最小值遍历结束，将最小值与序列中未排序位置的数字进行交换

代码

package com.sortAlgorithm;public class selectionSort {public static void main(String[] args){int list[] = {3,9,11,10,4};selectionSort selectionsort = new selectionSort();selectionsort.select(list);//输出排序之后的序列for (int i = 0; i<list.length; i++){System.out.println(list[i]);}}public void select(int list[]){for (int i = 0; i< list.length-1;i++){int mini = list[i];int tempj = i;for(int j = i+1;j<list.length;j++){if (mini>list[j]){mini = list[j];tempj = j;}}if (tempj != i) {list[tempj] = list[i];list[i] = mini;}}}}

插入排序法

属于内部排序法，是对于欲排序的元素以插入的方式寻找元素的适当位置，以达到排序的目的。

排序方法为把n个待排序的元素看成一个有序列表和一个无序表，开始时有序表中只包含1个元素，无序表中包含n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的序码依次与有序元素的排序码相比较，将它插入到有序码中适当位置，使之成为新的有序表。

代码实现：

package com.sortAlgorithm;public class insertSort {public static void main(String[] args) {int[] arr = {101, 34, 119, 1};insertSort insertSort = new insertSort();//排序insertSort.insert(arr);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}}//从小到大插入排序public void insert(int[] arr) {int insertVal = 0;int insertIndex = 0;for (int i = 1; i < arr.length; i++) {insertIndex = i - 1; //要插入的数字的前一个数字的索引insertVal = arr[i];//要插入数字的值while (insertIndex >= 0 && insertVal < arr[insertIndex]) {arr[insertIndex + 1] = arr[insertIndex];insertIndex--;}arr[insertIndex + 1] = insertVal;}}}

希尔排序

快速排序

通过一趟排序将要排序的数字分割成独立的两部分，其中一部分的数据比另一部分所有数据都小，然后再对这两组数据进行排序，整个排序过程递归进行。

package com.sortAlgorithm;import java.util.Arrays;public class quickSort {public static void main(String[] args){int[] arr = {-9,78,0,23,-567,70,-1,900,4561};quickSort quickSort = new quickSort();quickSort.quick(arr,arr.length-1,0);System.out.println(Arrays.toString(arr));}public void quick(int[] arr,int right, int left){int l = left;int r = right;int middle = arr[(left+right)/2];int temp = 0; //作交换使用//将比middle小的值放在middle左侧，大的放在右侧while(l<r){//寻找到不符合规范的值while(arr[l]<middle){l++;}while(arr[r]>middle){r--;}//判断是否已经实现了左右两端数字的排序功能if(l>=r){break;}//交换temp = arr[l];arr[l] = arr[r];arr[r] = temp;//如果有一端已经到达了middle的位置，要做一下另一端的处理if(arr[r] == middle){l++;}if(arr[l] == middle){r--;}}//如果l==r，要自增自减if(l==r){l++;r--;}//递归的过程if(l<right){quick(arr,right,l);}if(r>left){quick(arr,r,left);}}}

归并排序

利用分治策略，将大问题分为小问题递归进行求解。

基本思想：

合并相邻有序子序列的过程

思路分析：

一般来说先写一个分解的函数，再写一个合并的函数。

分解函数

判断是否left<right，如果是的话进行计算mid操作之后，完成左边的分解和右边的分解。在完成分解之后进行一次合并

合并函数

把左右两边的数据按照规则填充到temp数组，直到有一边序列填充完毕了。 i<mid,j<right的前提下：左右进行比较，小的移动到temp中移动之后，被移动的数组中的索引加一，temp的索引加一 把有剩余的序列全部填充到temp数组中。将temp数组拷贝到原数组中 因为每次传入的数组并不是最后一个完整的数组，所以创立一个临时left，因为之前移动过temp的指针，所以这里也要把temp置为0。当left小于right，依次将temp值移入arr中。

代码实现：

package com.sortAlgorithm;import java.util.Arrays;public class mergeSort {public static void main(String[] args) {int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};int[] temp = {0, 0, 0, 0, 0, 0, 0, 0};mergeSort mergeSort = new mergeSort();mergeSort.divide(arr, 0, 7, temp);System.out.println("排序后：" + Arrays.toString(arr));}public void divide(int[] arr, int left, int right, int[] temp) {int mid = (left + right) / 2;if (left < right) {System.out.println("分组中···");divide(arr, left, mid, temp);divide(arr, mid + 1, right, temp);merge(arr, left, right, mid, temp);}}public void merge(int[] arr, int left, int right, int mid, int[] temp) {//把左右两边的数据按照规则填充到temp数组，直到有一边序列填充完毕了。////1. 左右进行比较，小的移动到temp中//2. 移动之后，被移动的数组中的索引加一，temp的索引加一int i = left;int j = mid + 1;int tempIndex = 0;while (i <= mid && j <= right) {if (arr[i] < arr[j]) {System.out.println("右侧大于左侧！移动右侧进入temp数组中");temp[tempIndex] = arr[i];tempIndex++;i++;} else {System.out.println("左侧大于右侧！移动左侧进入temp数组中");temp[tempIndex] = arr[j];tempIndex++;j++;}//把有剩余的序列全部填充到temp数组中。while (j <= right) {System.out.println("加入右侧剩余数字中···");temp[tempIndex] = arr[j];tempIndex++;j++;}while (i <= mid) {System.out.println("加入左侧剩余数字中···");temp[tempIndex] = arr[i];tempIndex++;i++;}//将temp数组拷贝到原数组中//1. 创立一个临时left，当left小于right，依次将temp值移入arr中。tempIndex = 0;int templeft = left;while (templeft <= right) {arr[templeft] = temp[tempIndex];tempIndex++;templeft++;}}}}

基数排序

将整数按照位数切割成不同的数字，按每个位数分别比较。

基数排序是稳定的（大小相同的两个数，排序完成之后靠前的那一个仍然在前面）

思想：基数排序是依靠空间来交换时间的一种排序，一般我们会设置数据桶为一个二维数组。

找到数组中最大的数并查看它的位数

按照个位，十位，百位这样for循环，分别进行排序

将序列中每个元素取出，放入对应的桶中

遍历每个桶，将桶中的数据放入到原数组。统计完成后，要将桶清空。

代码实现：

package com.sortAlgorithm;import java.util.Arrays;public class radixSorting {public static void main(String[] args) {int[] arr = {53,3,542,748,14,214};int max = arr[0];for(int i = 1;i<arr.length;i++){if(arr[i]>arr[0]){max = arr[i];}}//查看max的位数int maxlength = (max+"").length();radixSorting radixSorting = new radixSorting();radixSorting.radix(arr,maxlength);System.out.println(Arrays.toString(arr));}public void radix(int[] arr,int maxlength){int[][] bucket = new int[10][arr.length];int[] bucketIndex = new int[10]; //表示第几个桶中包含了几个数字//找到数组中最大的数并查看它的位数for(int i = 0,n = 1;i<maxlength;i++,n *= 10){for(int j = 0;j<arr.length;j++){int need = (arr[j]/n)%10;bucket[need][bucketIndex[need]] = arr[j];bucketIndex[need]++;}//遍历每个桶，将数据放入原数组int temp = 0;for(int q = 0; q<10;q++){if(bucketIndex[q] != 0){for(int w = 0;w<bucketIndex[q];w++){arr[temp] = bucket[q][w];temp++;}}}//清空bucketIndexfor (int o = 0; o<10;o++){bucketIndex[o] = 0;}}}}

排序算法时间复杂度比较

O（n^2）：冒泡排序，选择排序，插入排序

O（nlogn）：希尔排序，归并排序，快速排序，堆排序

O（n*k）：基数排序（计数排序，桶排序）

__稳定__的：冒泡排序，插入排序，归并排序，基数排序（计数，桶）

__空间复杂度__有需求：快速排序O（logn），归并排序O（n），基数排序O（n*k）

只有__归并排序__和__基数排序__是外排序

哈希表

散列表（Hash Table，哈希表）是根据关键码值（key value）而直接进行访问的数据结构。

它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散函数，存放记录的数组叫做散列表。

一般来说，java程序直接访问数据库的速度较慢，这时候会加一个缓存层（缓存产品：redis，memcache）来增加访问速度，除此之外，我们还可以在缓存层自己写出一个哈希表来增加访问速度。

哈希表：

数组+链表数组+二叉树

一道题：有一个公司，当有新员工来的时候，要求将该员工信息加入，当输入该员工的id时，要求查找该员工的所有信息。（不使用数据库，速度越快越好==>哈希表）

思路分析：

至少要创建3个类

Emp雇员类，表示链表中的结点EmpLinkedList类，表示链表，链表类需要包含对雇员的操作（add，list，find，del）HashTab类，创建一个数组，表示HashTab，数组中包含一个链表；HashTab中仍然需要包含对雇员操作的函数，除此之外，还要包含一个散列函数，通过散列函数来找到对应的链表

代码实现：

package com.dataStructure;import java.util.Scanner;public class HashTab {public static void main(String[] args){HashTable hashTab = new HashTable();//菜单String key = "";Scanner scanner = new Scanner(System.in);while(true){System.out.println("add");System.out.println("list");System.out.println("find");System.out.println("exit");key = scanner.next();switch(key){case"add":System.out.println("id: ");int id = scanner.nextInt();System.out.println("name: ");String name = scanner.next();Emp emp = new Emp(id,name);hashTab.add(emp);break;case"list":hashTab.list();break;case"find":System.out.println("输入你想查找的id" );int idd = scanner.nextInt();hashTab.find(idd);break;case"exit":scanner.close();System.exit(0);default:break;}}}}class Emp{int id;String name;Emp next;public Emp(int id,String name){this.id = id;this.name = name;}}class EmpLinkedList{Emp head = null;public void add(Emp emp){Emp temp = head;while(true) {if (temp == null) {head = emp;break;}if(temp.next == null){temp.next = emp;break;}temp = temp.next;}}public void list(){if(head == null){System.out.println("list is null!!!");return;}Emp temp = head;while(true){System.out.println("第"+temp.id+"个雇员的名字为"+temp.name);if(temp.next == null){break;}temp = temp.next;}}public void find(int id){if(head == null){System.out.println("List is null！cannot find！");return;}Emp temp = head;while(true){if(id == temp.id){System.out.println("第"+temp.id+"个雇员的名字为"+temp.name);break;}if(temp.next == null){System.out.println("这里没有这个人的信息～");return;}temp = temp.next;}}}class HashTable{EmpLinkedList[] EmpLinkedListArr ;public HashTable(){EmpLinkedListArr = new EmpLinkedList[7];//这里必须初始化，否则出现空指针错误for (int i = 0; i<7 ;i++){EmpLinkedListArr[i] = new EmpLinkedList();}}public void add(Emp emp){int id = hash(emp.id);EmpLinkedListArr[id].add(emp);}public void list(){for(int i = 0;i<EmpLinkedListArr.length;i++){System.out.println("第"+i+"组：");EmpLinkedListArr[i].list();}}public void find(int id){int real_id = hash(id);EmpLinkedListArr[real_id].find(id);}public int hash(int id){return id%7;}}

树结构

树的数据结构

数组：用下标方式访问元素，查找速度快，插入和删除速度慢

链表：插入和删除的速度较快，在检索时效率较低

树存储：存储和读取效率很高，插入，删除，修改的速度也可以保证

常用术语：

树的高度：最大层数

森林：多棵子树构成森林

二叉树的概念

每个节点最多有两个子节点的树叫做二叉树，它的子节点分为左子节点和右子节点。

二叉树所有叶子节点都在最后一层，节点总数为2^n-1，n为层数，称为满二叉树。

二叉树所有叶子节点都在最后一层或倒数第二层，最后一层叶子节点在左边连续，倒数第二层叶子节点在右边连续，我们称为完全二叉树。

写一个二叉树的思路

创建两个类：heroNode，BinaryTreeheroNode本身要包含前序中序后序遍历的代码，BinaryTree中要包含一个root节点作为树的根，在初始化的时候就要加入进去，还要包含实现遍历的代码（调用heroNode中的）

二叉树的遍历

前序遍历：输出顺序父节点-左子树-右子树

中序遍历：输出顺序 左子树-父节点-右子树

后序遍历：输出顺序 左子树-右子树-父节点

看父节点的输出顺序决定是哪种遍历

代码实现：

package com.tree;public class binaryTree {public static void main(String[] args){heroNode heroNode1 = new heroNode(1,"nancy1");heroNode heroNode2 = new heroNode(2,"nancy2");heroNode heroNode3 = new heroNode(3,"nancy3");heroNode heroNode4 = new heroNode(4,"nancy4");heroNode heroNode5 = new heroNode(5,"nancy5");heroNode1.left = heroNode2;heroNode1.right = heroNode3;heroNode3.left = heroNode4;heroNode3.right = heroNode5;binaryTreeDemo binaryTreeDemo = new binaryTreeDemo(heroNode1);System.out.println("前序遍历：");binaryTreeDemo.preorderTraversal();System.out.println("中序遍历：");binaryTreeDemo.inorderTraversal();System.out.println("后序遍历：");binaryTreeDemo.postorderTraversal();}}class heroNode{int id;String name;heroNode left;heroNode right;public heroNode(int id,String name){this.id = id;this.name = name;}@Overridepublic String toString(){return "HeroNode:"+id+" name: "+name;}//前序遍历public void preorderTraversal(){System.out.println(this);if(left!=null){this.left.preorderTraversal();}if(right!=null){this.right.preorderTraversal();}}//中序遍历public void inorderTraversal(){if(left!=null){this.left.inorderTraversal();}System.out.println(this);if(right!=null){this.right.inorderTraversal();}}//后序遍历public void postorderTraversal(){if(left!=null){this.left.postorderTraversal();}if(right!=null){this.right.postorderTraversal();}System.out.println(this);}}class binaryTreeDemo{heroNode root;public binaryTreeDemo(heroNode root){this.root = root;}public void preorderTraversal(){root.preorderTraversal();}public void inorderTraversal(){root.inorderTraversal();}public void postorderTraversal(){root.postorderTraversal();}}

二叉树查找指定节点

中序查找思路：

判断当前节点的子节点是否为空，如果不为空，则递归中序查找。如果找到，则返回；如果没找到，和当前节点进行比较，如果是则返回当前节点，如果不是，继续进行右递归的中序查找。如果找到则返回，没找到，返回null

比较核心的想法就是仍然是在遍历整个过程，但是将输出的过程转换为对比的过程，res的赋值是在递归中实现的，当查找到了的时候，递归函数返回一个heroNode，这样就实现了给res赋值HeroNode，实现了查找的功能。

代码：

//中序查找public heroNode inorderSearch(int no){heroNode res = null;if(left!=null){res = this.left.inorderSearch(no);}if(res != null){return res;}//要在进入到对比这里，才需要进行计数System.out.println("进行了一次对比～～～");if(this.id == no){return this;}if(right!=null){res = this.right.inorderSearch(no);}if(res != null){return res;}return null;}

二叉树删除节点

如果删除的是叶子节点，则直接删除；如果是非叶子节点，则删除该子树。

思路分析：

首先处理树为空和只有root一个节点的情况

删除树上节点时，需要找到某个节点的子节点为要删除的节点，而不能直接去寻找某个节点是不是要删除的点当前节点的左子节点不为空且为目标节点，this.left = null;当前节点的右子节点不为空且为目标节点，this.right = null;如果节点还没有被删除，且左子树不为空，递归左子树如果还没有被删除，且右子树不为空，递归右子树

代码：

这段代码是在上一段的修改下完成的

//节点类下面加入如下方法public void del(int no){if(this.left != null && this.left.id == no){this.left = null;return;}if (this.right != null && this.right.id == no) {this.right = null;return;}if (this.left != null) {this.left.del(no);}if (this.right != null) {this.right.del(no);}}//树类下面加入如下函数public void del(int no){if(root == null){System.out.println("当前树为空～～～");return;}if(root.id == no){root = null;System.out.println("root已被删除～～～");return;}root.del(no);}

顺序存储二叉树

要求：

遍历数组arr时，仍然可以实现前序中序后序遍历。

特点：

只考虑完全二叉树第n个元素的左子节点为2*n+1第n个元素的右子节点为2*n+2第n个元素的父节点为（n-1）/2

代码

package com.tree;public class arrBinaryTree {public static void main(String[] args){int[] arr = {1,2,3,4,5,6};arrBianary arrBianary = new arrBianary(arr);arrBianary.postOrder();}}class arrBianary{private int[] arr;public arrBianary(int[] arr){this.arr = arr;}public void preOrder(int index){if(arr.length<0 || arr == null){System.out.println("nothing to print!");return;}System.out.println(arr[index]);if(index*2+1<arr.length){preOrder(index*2+1);}if(index*2+2<arr.length){preOrder(index*2+2);}}public void postOrder(){if(arr.length==0 || arr == null){System.out.println("nothing to print!");return;}postOrder(0);}private void postOrder(int index){if(index*2+1<arr.length){int left = index*2+1;postOrder(left);}if(index*2+2<arr.length){int right = index*2+2;postOrder(right);}System.out.println(arr[index]);}}

线索化二叉树

希望充分利用各个节点的左右指针，让各个节点可以指向自己的前后节点。

基本介绍：

二叉链表中的空指针域，存放指向该节点在某种遍历次序下的前驱和后继点的指针。

线索二叉树之后，Node节点的属性有left和right，left可能指向左子树或者前驱节点，right可能指向右子树或者后继节点。

中序线索二叉树基本思路：

在二叉树类中要定义一个pre指针，作为保留的前一个节点。

在node类中创建类型leftType, rightType

1. leftType = 0，指向左子树，leftType = 1，指向前驱节点。2. rightType = 0，指向右子树，rightType = 1，指向后继节点。

创建函数，传入参数node

判断node是否为空，为空则不能线索化先线索化左子树（递归node.left）线索化当前节点 当node的左后继节点为空时，将当前节点左指针指向pre，并设置为左指针类型。当当前node的pre不为空且pre.right指针为空时，让前驱节点的右指针指向当前节点，并设置pre的右指针类型。每处理一个节点后，让当前节点是下一个节点的前驱节点。（pre = node） 线索化右子树（递归node.right）

遍历线索化二叉树

思路：

定义一个变量，存储当前遍历的节点node不为空的情况下： 当lefttype = 0时，node = node.left打印这个节点若当前节点右指针指向后继节点，就一直输出不指向后继节点时替换遍历的点（node = node.right）

树的应用

堆排序

时间复杂度O（nlogn），不稳定排序。

堆是具有一下性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆；每个节点的值都小于或等于左右孩子节点的值，称为小顶堆。（不要求左右孩子节点的大小关系）

大顶堆特点：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆特点：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

升序使用大顶堆，降序使用小顶堆

i是从0开始编号的：

基本思想：

将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆将堆顶元素与末尾元素交换，将最大元素沉到数组末端将剩余n-1个元素重新构造成一个堆，会得到n个元素的次小值，如此反复执行，能得到一个有序序列

代码思想：

先写一个函数adjust：将一个数组（二叉树）调整成一个大顶堆 参数为 1⃣️数组，2⃣️非叶子节点在数组中的索引i，3⃣️表示对多少个元素进行调整首先将当前非叶子节点的值存入temp写一个for循环，k设置为左子节点，k<length时停止循环，每次循环k=k的左子节点 查看当前非叶子节点左右子节点哪个大(且满足k+1<num，防止已经放到结尾的数字再被拿出来)，取较大值的索引为k若子节点大于父节点，把较大的值赋值给函数的索引节点i，将k赋值给i，继续循环比较；否则，break当前for循环。 循环结束，将temp的值赋值给arr[i]，表示将temp值放到调整后的位置。 创建for循环，循环调用adjust，for(int i = arr.length/2-1; i>=0; i--)，for循环完成时，大顶堆就构造完成了创建for循环，将堆顶元素与末尾元素进行交换，将最大的元素沉到数组末端；将剩余元素进行adjust，

代码：

package com.sortAlgorithm;import java.util.Arrays;public class heapSort {public static void main(String[] args){int[] arr = {4,6,8,5,9};for(int i = arr.length/2-1; i>=0; i--){adjust(arr,i,arr.length);}for(int j = arr.length-1; j>0; j--){int temp = arr[j];arr[j] = arr[0];arr[0] = temp;adjust(arr,0,j);}System.out.println(Arrays.toString(arr));}/*** 构建大顶堆的函数* @param arr 传入的数组* @param i 非叶子节点在数组中的索引* @param num 对多少个元素进行调整*/public static void adjust(int[] arr, int i, int num){int temp = arr[i];for(int k = i*2+1; k< num; k = k*2+1){if(arr[k]<arr[k+1]&&k+1<num){k++;}if(arr[k]>temp){arr[i] = arr[k];i = k;}else{break;}}arr[i] = temp;}}

huffman树

huffman树是带权路径长度最短的树，权值较大的节点离根很近。

路径长度：根节点层数为1，从根节点到第L层节点的路径长度为L-1

带权路径长度：从根节点到该节点之间的路径长度与该节点

__树的带权路径长度__为所有叶子节点的带权路径长度之和，称为WPL（weighted path length），WPL最小就是huffman树。

权值越大的节点离根节点越近的二叉树才是最优二叉树。

huffmanTree思路分析

从小到大进行排序，每个节点可以看成是一颗最简单的二叉树取出根节点权值最小的两个二叉树，组成一颗新二叉树，新二叉树的根节点是两个二叉树根节点权的和将新的二叉树以根节点的权值大小，再次排序。不断重复上述过程，直到所有数据都被处理，即可得到huffmanTree

代码思路：

将数组传入函数中，并遍历数组，将数组的每个元素构成一个Node，组成一个ArrayList nodes，while循环，当nodes.size>1时： 将nodes排序取出根节点权值最小的两个树构建一个新的二叉树（要记得设置新的二叉树的指针指向上面取出的两个二叉树）从ArrayList中删除处理过的两个节点将新的树加入nodes中 返回huffman树的root节点

package com.tree;import java.util.Collection;import java.util.Collections;import java.util.List;import java.util.ArrayList;public class huffmanTree {public static void main(String[] args) {int[] arr = {13, 7, 8, 3, 29, 6, 1};Node root = createHuffmanTree(arr);preOrder(root);}public static void preOrder(Node root) {if (root != null) {root.preOrder();} else {System.out.println("null root!");}}public static Node createHuffmanTree(int[] arr) {List<Node> nodes = new ArrayList<Node>();for (int value : arr) {nodes.add(new Node(value));}while (nodes.size() > 1) {Collections.sort(nodes);Node newLeft = nodes.get(0);Node newright = nodes.get(1);Node parent = new Node(newLeft.value + newright.value);parent.left = newLeft;parent.right = newright;nodes.remove(newLeft);nodes.remove(newright);nodes.add(parent);}//这时候，nodes中仅剩一个元素return nodes.get(0);}}class Node implements Comparable<Node> {int value;Node left;Node right;//前序遍历public void preOrder() {System.out.println(this.value);if (this.left != null) {this.left.preOrder();}if (this.right != null) {this.right.preOrder();}}public Node(int value) {this.value = value;}@Overridepublic String toString() {return "Node[value=" + value + "]";}@Overridepublic int compareTo(Node o) {return this.value - o.value;}}

huffman编码

属于一种算法，在通信领域应用广泛，并且应用于数据文件压缩中。

步骤：

将传输的字符串按照出现的次数构建一个huffman树，出现的次数作为权重

根据huffman树，给各个字符规定编码，向左的路径为0向右为1。

这其中可能存在权重相同的字符，无论何种方式构建的huffman树，WPL都是相通的，都拥有相同的压缩率。

代码思路：

创建一个函数，参数设置为节点，节点的路径（左为0，右为1），StringBuilder stringBuilder用于拼接路径使用StringBuilder新创建一个stringbuilder2，将节点的路径apped进去。若node不为空，则判断是否当前节点为非叶子节点，如果是非叶子节点的话，使用StringBuilder2向左递归，向右递归。

二叉排序树

binary sort tree，对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。

这个函数写在Node类中，但是需要使用Tree的类来调用

排序树增加节点的思想：

如果新加入node的值比当前节点小 当前节点的left为空，node设置为left当前节点的left不为空，使用当前节点的left递归调用 如果新加入node的值比当前节点大 当前节点的right为空，node设置为right当前节点的right不为空，使用当前节点的right递归调用

排序树删除节点的思想：

删除节点有三种情况

删除叶子节点删除只有一颗子树的节点删除有两颗子树的节点

思路分析：

删除叶子节点 先找到要删除的节点找到要删除节点的parent确定要删除的是parent的左子节点还是右子节点，进行parent.left = null或parent.right = null 删除只有一颗子树的节点 找到要删除的节点找到要删除节点的父节点确定要删除的targetnode是左子节点还是右子节点判断targetnode有左子节点还是有右子节点 如果targetnode是parent的左子节点且targetnode有左子节点，parent.left = targetnode.left如果targetnode是parent的左子节点且targetnode有右子节点，parent.left = targetnode.right如果targetnode是parent的右子节点且targetnode有左子节点，parent.right = targetnode.left如果targetnode是parent的右子节点且targetnode有右子节点，parent.right = targetnode.right 删除有两颗子树的节点 找到要删除的点找到要删除点的parent从targetnode的右子树找到最小的节点用一个临时temp将最小节点保存，并删除最小节点targetNode.value = temp;

代码思路分析：

需要添加的函数：

在Node类

添加search方法，返回要删除的节点

使用递归调用的思路，首先判断当前节点是否为目标节点如果不是，就向左遍历，向右遍历

添加searchParent方法，返回要删除节点的父节点

使用递归调用的思路，首先判断是否为目标节点（左子节点不为空且左子节点的值为value 或者 右子节点不为空且右子节点的值为value）如果不是，向左遍历，向右遍历，如果还找不到，返回null

在二叉排序树类

创建search方法，调用search方法创建searchParent方法，调用searchParent方法创建删除二叉排序树的最小节点的方法，并返回最小节点的值 使用循环查找的方法，找到最左端的子树 创建删除节点的方法 首先取出要找到的节点（如果没找到则return，如果二叉树只有一个节点，则删除后return）找到targetNode的父节点判断 1. 如果删除的是叶子节点——判断这个节点是左子节点还是右子节点，删除判断 2. 如果删除的是有两颗子树的节点——找到要删除节点的右子树的最小子节点，并使targetNode = 删去节点的值判断 3. 如果删除只有一颗子树的节点——判断targetnodeParent的左子节点是targetNode还是右子节点是targetNode 如果targetnode是parent的左子节点且targetnode有左子节点，parent.left = targetnode.left如果targetnode是parent的左子节点且targetnode有右子节点，parent.left = targetnode.right如果targetnode是parent的右子节点且targetnode有左子节点，parent.right = targetnode.left如果targetnode是parent的右子节点且targetnode有右子节点，parent.right = targetnode.right

代码

package com.tree;public class binarySortTree {public static void main(String[] args) {int[] arr = {7, 3, 10, 12, 5, 1, 9};SortTree Sorttree = new SortTree();for (int i = 0; i < arr.length; i++) {Sorttree.add(new Node_(arr[i]));}Sorttree.middleOrder();//删除测试System.out.println("删除测试～～～");Sorttree.del(1);Sorttree.middleOrder();}//创建树static class SortTree {private Node_ root;public void add(Node_ node) {if (root == null) {root = node;} else {root.add(node);}}//中序遍历public void middleOrder() {if (root != null) {root.middleOrder();} else {System.out.println("null!!!");}}//调用search方法public Node_ search(int value) {if (root == null) {return null;} else {return root.search(value);}}//调用searchParentpublic Node_ searchParent(int value) {if (root == null) {return null;} else {return root.searchParent(value);}}//寻找并删除最小子节点，返回最小子节点的值public int delMin(Node_ node) {Node_ target = node;while (target.left != null) {target = target.left;}del(target.value);return target.value;}//删除节点public void del(int value) {Node_ targetNode = search(value);if (targetNode == null) {return;}if (root.left == null && root.right == null) {root = null;return;}Node_ targetNodeParent = searchParent(value);//判断 1. 如果删除的是叶子节点——判断这个节点是左子节点还是右子节点，删除if (targetNode.left == null && targetNode.right == null) {if (targetNodeParent.left != null && targetNodeParent.left.value == value) {targetNodeParent.left = null;} else {targetNodeParent.right = null;}} else if (targetNode.left != null && targetNode.right != null) {//判断 2. 如果删除的是有两颗子树的节点——找到要删除节点的右子树的最小子节点，并使targetNode = 删去节点的值int min = delMin(targetNode.right);targetNode.value = min;} else {//判断 3. 如果删除只有一颗子树的节点——判断targetnodeParent的左子节点是targetNode还是右子节点是targetNodeif (targetNodeParent.left.value == targetNode.value) {//目标节点是其父节点的左子节点if (targetNode.left != null) {targetNodeParent.left = targetNode.left;} else {targetNodeParent.left = targetNode.right;}} else {//目标节点是其父节点的右子节点if (targetNode.right != null) {targetNodeParent.right = targetNode.right;} else {targetNodeParent.right = targetNode.left;}}}}}//创建节点static class Node_ {int value;Node_ left;Node_ right;public Node_(int value) {this.value = value;}public void add(Node_ node) {if (node.value < this.value) {if (this.left == null) {this.left = node;} else {this.left.add(node);}} else {if (this.right == null) {this.right = node;} else {this.right.add(node);}}}//找到要删去的节点public Node_ search(int value) {if (this.value == value) {return this;} else if (value < this.value) {if (this.left == null) {return null;}return this.left.search(value);} else {if (this.right == null) {return null;}return this.right.search(value);}}//找到要删除节点的父节点public Node_ searchParent(int value) {if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {return this;} else {if (value < this.value && this.left != null) {return this.left.searchParent(value);} else if (value > this.value && this.right != null) {return this.right.searchParent(value);} else {return null;}}}//中序遍历public void middleOrder() {if (this.left != null) {this.left.middleOrder();}System.out.println(this.value);if (this.right != null) {this.right.middleOrder();}}}}

平衡二叉树（AVL树）

创建二叉排序树{1，2，3，4，5}时，左子树全部为空，查询速度明显降低，无法发挥二叉排序树的优势，所以需要平衡二叉树

平衡二叉树它的左右两个子树的高度差绝对值不超过1，并且它的左右两个子树也都是平衡二叉树。

当需要创建一颗AVL树的时候，往往需要__左旋转，右旋转，双旋转__

旋转方法添加在Node类中的add方法中

左旋转

当数列{4，3，6，5，7}加入8时，rightHight()-leftHight() > 1成立， 树就不是一个AVL树了

思路：

创建一个新的节点，值等于当前节点的值将新节点的左子树设置为当前节点的左子树将新节点的右子树设置为当前节点的右子树的左子树把当前节点的值设置为右子节点的值把当前节点的右子树设置为右子树的右子树把当前节点的左节点设置为新节点

右旋转

思路和左旋转相同。

双旋转

有时不能实现一次单旋转完成二叉树的转换，需要双旋转。

当需要进行右旋转时，如果它的左子树的右子树高度大于左子树的左子树高度时，先对这个节点的左节点进行左旋转，在对当前节点进行右旋转。

代码实现：

package com.tree.AVL;public class AVL_Tree {public static void main(String[] args) {AVLTree avlTree = new AVLTree();// int[] arr = {4,3,6,5,7,8};int[] arr = {10,11,7,6,8,9};for (int i = 0; i < arr.length; i++) {avlTree.add(new Node_(arr[i]));}System.out.println("树高度：");System.out.println(avlTree.root.hight());System.out.println("左右子树高度：");System.out.println(avlTree.root.leftHight());System.out.println(avlTree.root.rightHight());//}}//创建树class AVLTree {Node_ root;public void add(Node_ node) {if (root == null) {root = node;} else {root.add(node);}}//中序遍历public void middleOrder() {if (root != null) {root.middleOrder();} else {System.out.println("null!!!");}}//调用search方法public Node_ search(int value) {if (root == null) {return null;} else {return root.search(value);}}//调用searchParentpublic Node_ searchParent(int value) {if (root == null) {return null;} else {return root.searchParent(value);}}//寻找并删除最小子节点，返回最小子节点的值public int delMin(Node_ node) {Node_ target = node;while (target.left != null) {target = target.left;}del(target.value);return target.value;}//删除节点public void del(int value) {Node_ targetNode = search(value);if (targetNode == null) {return;}if (root.left == null && root.right == null) {root = null;return;}Node_ targetNodeParent = searchParent(value);//判断 1. 如果删除的是叶子节点——判断这个节点是左子节点还是右子节点，删除if (targetNode.left == null && targetNode.right == null) {if (targetNodeParent.left != null && targetNodeParent.left.value == value) {targetNodeParent.left = null;} else {targetNodeParent.right = null;}} else if (targetNode.left != null && targetNode.right != null) {//判断 2. 如果删除的是有两颗子树的节点——找到要删除节点的右子树的最小子节点，并使targetNode = 删去节点的值int min = delMin(targetNode.right);targetNode.value = min;} else {//判断 3. 如果删除只有一颗子树的节点——判断targetnodeParent的左子节点是targetNode还是右子节点是targetNodeif (targetNodeParent.left.value == targetNode.value) {//目标节点是其父节点的左子节点if (targetNode.left != null) {targetNodeParent.left = targetNode.left;} else {targetNodeParent.left = targetNode.right;}} else {//目标节点是其父节点的右子节点if (targetNode.right != null) {targetNodeParent.right = targetNode.right;} else {targetNodeParent.right = targetNode.left;}}}}}//创建节点class Node_ {int value;Node_ left;Node_ right;public Node_(int value) {this.value = value;}public void add(Node_ node) {if (node.value < this.value) {if (this.left == null) {this.left = node;} else {this.left.add(node);}} else {if (this.right == null) {this.right = node;} else {this.right.add(node);}}//判断是否满足AVLtreeif(this.rightHight()-this.leftHight()>1){if(right.leftHight()>right.rightHight()){left.rightRotate();}leftRotate();}if(this.leftHight()-this.rightHight()>1){if(left.rightHight()>left.leftHight()){left.leftRotate();}rightRotate();}}//计算以当前节点为根节点的树的高度public int hight(){return Math.max(left == null?0:left.hight(),right == null?0:right.hight())+1;}//左子树的高度public int leftHight(){if(left == null){return 0;}return left.hight();}//右子树的高度public int rightHight(){if(right == null){return 0;}return right.hight();}//找到要删去的节点public Node_ search(int value) {if (this.value == value) {return this;} else if (value < this.value) {if (this.left == null) {return null;}return this.left.search(value);} else {if (this.right == null) {return null;}return this.right.search(value);}}//找到要删除节点的父节点public Node_ searchParent(int value) {if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {return this;} else {if (value < this.value && this.left != null) {return this.left.searchParent(value);} else if (value > this.value && this.right != null) {return this.right.searchParent(value);} else {return null;}}}//中序遍历public void middleOrder() {if (this.left != null) {this.left.middleOrder();}System.out.println(this.value);if (this.right != null) {this.right.middleOrder();}}//左旋转public void leftRotate(){Node_ newNode = new Node_(value);newNode.left = left;newNode.right = right.left;value = right.value;right = right.right;left = newNode;}//右旋转public void rightRotate(){Node_ newNode = new Node_(value);newNode.right = right;newNode.left = left.right;value = left.value;left = left.left;right = newNode;}}

多路查找树

二叉树的问题分析：

二叉树在构建时，需要进行多次i/o操作（海量数据存在数据库或文件中），节点很多的话，构建速度会有影响。节点很多，会造成二叉树过高，降低操作速度

我们就可以引入多叉树，多叉树每个节点可以有更多的数据项和更多的子节点。

一个多叉树的例子

B树：

通过重新组织节点，降低树的高度，并且减少i/o读写次数来提升效率。

2-3树

2-3树是最简单的B树结构

所有叶子节点在同一层（B树都满足这个条件）有两个节点的节点叫做二节点，二节点要么没有子节点，要么有两个子节点有三个节点的节点叫做三节点，三节点要么没有子节点，要么有三个子节点2-3树是由二节点和三节点构成的树

插入规则：

所有叶子节点都在同一层，且符合B树结构。

除2-3树以外，还有234树等等

B树，B+树，B*树

B树的每个节点都存储数据，搜索可能在非叶子节点结束

B+树只有叶子节点可以存储数据，它的叶子节点是一个链表，链表中的关键字是有序的；在B+树上增加了顺序访问指针，也就是每个叶子节点增加一个指向相邻叶子节点的指针，这样一棵树成了数据库系统实现索引的首选数据结构。

B+树改进了B树, 让内结点只作索引使用, 去掉了其中指向data record的指针, 使得每个结点中能够存放更多的key, 因此能有更大的出度. 这有什么用? 这样就意味着存放同样多的key, 树的层高能进一步被压缩, 使得检索的时间更短.

B*树在B+树的非根和非叶子节点再增加指向兄弟的指针

图

当表示多对多的关系的时候，我们需要使用图

图的表示方式一般有两种：二维数组（邻接矩阵），链表（邻接表）

创建一个图

思路分析：

添加一个graph类，包含

初始化矩阵和vertexList：边，节点信息（节点集合：private ArrayList<String> vertexList），边的数量

插入节点

插入边

返回节点的个数

返回边的个数

返回某亮点之间的权值

返回节点对应的数据

显示图对应的矩阵

代码：

package com.graph;import java.util.ArrayList;import java.util.Arrays;public class basicGraph {public static void main(String[] args){graph graph = new graph(8);//添加点String vertexs[] = {"A","B","C"};for(String vertex:vertexs){graph.insertVertex(vertex);}//添加边graph.insertEdge(0,1,1);graph.insertEdge(1,2,2);graph.insertEdge(2,3,3);//查询System.out.println(graph.getValueByIndex(0));graph.showGraph();}}class graph{private ArrayList<String> vertexList;private int[][] edges;private int numOfNodes;private int numOfEdges;public graph (int n){edges = new int[n][n];vertexList = new ArrayList<String>(n);numOfEdges = 0;numOfNodes = 0;}//返回节点的个数public int getNumOfNodes(){return vertexList.size();}//显示图对应的矩阵public void showGraph(){for(int[] link:edges){System.out.println(Arrays.toString(link));}}//得到边的个数public int getNumOfEdges(){return numOfEdges;}//返回节点i对应的数据public String getValueByIndex(int i){return vertexList.get(i);}//返回v1，v2之间的权值public int getWight(int v1,int v2){return edges[v1][v2];}//插入节点public void insertVertex(String vertex){vertexList.add(vertex);}//添加边public void insertEdge(int v1,int v2, int weight){edges[v1][v2] = weight;edges[v2][v1] = weight;numOfEdges++;}}

图的深度优先算法（DFS）

深度优先遍历，从初始结点出发，首先访问第一个临接点，然后用被访问的结点再去访问它的下一个临接点

用上图举例，第一行，初始结点是A，它的邻接结点就是B，然后这时候就从第二行开始寻找，B访问到C是自己的下一个临接点，这时候就从第三行开始寻找，C除了AB就没有临接结点了；这时候返回B，也就是第二行，发现B的下一个临接结点是D，这时候就去从第四行开始寻找，没有找到；继续返回B…

代码思路：

首先需要创建一个找到当前行中第一个为1的函数（getFirstNeibour）

再创建一个找到当前行中下一个为1的函数(getNextNeibour)

循环判断一个checklist，是否这一个点检查过，如果没检查过就执行dfs算法

dfs的思路：先打印出当前扫描的结点本身，然后更改checklist，然后寻找当前结点的FirstNeibour，存在的话继续递归FirstNeibour，否则寻找后面有没有NextNeibour

dfs完整代码：

package com.graph;import java.util.ArrayList;import java.util.Arrays;import java.util.LinkedList;public class basicGraph {public static void main(String[] args){graph graph = new graph(5);//添加点String vertexs[] = {"A","B","C","D","E"};for(String vertex:vertexs){graph.insertVertex(vertex);}//添加边graph.insertEdge(0,1,1);graph.insertEdge(0,2,1);graph.insertEdge(1,2,1);graph.insertEdge(1,3,1);graph.insertEdge(1,4,1);graph.insertEdge(1,2,1);//查询graph.showGraph();graph.dfs();}}class graph {private ArrayList<String> vertexList;private int[][] edges;private int numOfNodes;private int numOfEdges;private boolean[] checkList;public graph(int n) {edges = new int[n][n];vertexList = new ArrayList<String>(n);numOfEdges = 0;numOfNodes = 0;}//返回节点的个数public int getNumOfNodes() {return vertexList.size();}//显示图对应的矩阵public void showGraph() {for (int[] link : edges) {System.out.println(Arrays.toString(link));}}//得到边的个数public int getNumOfEdges() {return numOfEdges;}//返回节点i对应的数据public String getValueByIndex(int i) {return vertexList.get(i);}//返回v1，v2之间的权值public int getWight(int v1, int v2) {return edges[v1][v2];}//插入节点public void insertVertex(String vertex) {vertexList.add(vertex);}//添加边public void insertEdge(int v1, int v2, int weight) {edges[v1][v2] = weight;edges[v2][v1] = weight;numOfEdges++;}//DFS部分public int getFirstNeibour(int i) {for (int k = 0; k < 5; k++) {if (edges[i][k] > 0) {return k;}}return -1;}public int getNextNeibour(int a, int b) {for (int k = b+1; k < 5; k++) {if (edges[a][k] > 0) {return k;}}return -1;}public void dfs() {checkList = new boolean[5];for (int i = 0;i<5;i++){if(!checkList[i]){dfs(i,checkList);}}}public void dfs(int a,boolean[] checklist){System.out.println(getValueByIndex(a)+"->");checklist[a] = true;int w = getFirstNeibour(a);while(w!=-1){if(checklist[w] == false){dfs(w,checklist);}w = getNextNeibour(a,w);}}}

图的广度优先算法

广度优先算法类似于一种分层搜索的概念

用这张图举例来说，先搜索A这个点，发现B是临接的，然后继续搜索A的临接，发现C也是，这时访问B的临接结点…

代码思路：

因为是一行一行搜索，我们使用两个while循环。

第一个while循环判断是否每一行都进行搜索了，第二个while循环判断是否每一行都详尽的搜索了；所以设置了linkedList作为while的判断条件，来存储当前还未搜索的行号

完整代码：

package com.graph;import java.util.ArrayList;import java.util.Arrays;import java.util.LinkedList;public class basicGraph {public static void main(String[] args){graph graph = new graph(5);//添加点String vertexs[] = {"A","B","C","D","E"};for(String vertex:vertexs){graph.insertVertex(vertex);}//添加边graph.insertEdge(0,1,1);graph.insertEdge(0,2,1);graph.insertEdge(1,2,1);graph.insertEdge(1,3,1);graph.insertEdge(1,4,1);graph.insertEdge(1,2,1);//查询graph.showGraph();boolean[] checkList = new boolean[5];graph.bfs(0,checkList);}}class graph {private ArrayList<String> vertexList;private int[][] edges;private int numOfNodes;private int numOfEdges;private boolean[] checkList;public graph(int n) {edges = new int[n][n];vertexList = new ArrayList<String>(n);numOfEdges = 0;numOfNodes = 0;}//返回节点的个数public int getNumOfNodes() {return vertexList.size();}//显示图对应的矩阵public void showGraph() {for (int[] link : edges) {System.out.println(Arrays.toString(link));}}//得到边的个数public int getNumOfEdges() {return numOfEdges;}//返回节点i对应的数据public String getValueByIndex(int i) {return vertexList.get(i);}//返回v1，v2之间的权值public int getWight(int v1, int v2) {return edges[v1][v2];}//插入节点public void insertVertex(String vertex) {vertexList.add(vertex);}//添加边public void insertEdge(int v1, int v2, int weight) {edges[v1][v2] = weight;edges[v2][v1] = weight;numOfEdges++;}//DFS部分public int getFirstNeibour(int i) {for (int k = 0; k < 5; k++) {if (edges[i][k] > 0) {return k;}}return -1;}public int getNextNeibour(int a, int b) {for (int k = b+1; k < 5; k++) {if (edges[a][k] > 0) {return k;}}return -1;}public void dfs() {checkList = new boolean[5];for (int i = 0;i<5;i++){if(!checkList[i]){dfs(i,checkList);}}}public void dfs(int a,boolean[] checklist){System.out.println(getValueByIndex(a)+"->");checklist[a] = true;int w = getFirstNeibour(a);while(w!=-1){if(checklist[w] == false){dfs(w,checklist);}w = getNextNeibour(a,w);}}public void bfs(int a, boolean[] checkList){int u; //当前的列表下标int w; //临接结点的下标LinkedList linkedList = new LinkedList();System.out.println(getValueByIndex(a)+"->");checkList[a] = true;linkedList.add(a);while(linkedList != null){u = (Integer) linkedList.removeFirst();w = getFirstNeibour(u);while(w!=-1){if(checkList[w] == false){System.out.println(getValueByIndex(w)+"->");checkList[w] = true;linkedList.add(w);}w = getNextNeibour(u,w);}}}}

常用10种算法

二分查找 非递归

二分查找主要要注意的点在于非递归版本while的条件要设置为（left<=right），这个可以通过边界条件来判断，mid要等于（left+right）/2

上代码，递归版本和非递归版本

package algorithm;public class binarySearch {public static void main(String[] args) {int[] arr = {1,4,6,15,64,299};int index = binarySearchNoRecur(arr,299) ;System.out.println(index);int index1 = binarySearchRecur(arr,299,0,5) ;System.out.println(index1);}public static int binarySearchNoRecur(int[] arr, int target){int length = arr.length;int left = 0;int right = length-1;int mid = 0;while(left<=right){mid = (left+right)/2;if(arr[mid] == target){return mid;}else if(arr[mid]<target){left = mid+1;}else{right = mid-1;}}return -1;}public static int binarySearchRecur(int[] arr,int target,int left,int right){int mid = (left+right)/2 ;if (arr[mid] ==target) {return mid;}if(arr[mid]<target){return (binarySearchRecur(arr,target,mid+1,right));}else if(arr[mid]>target){return (binarySearchRecur(arr, target, left, mid - 1));}else{return -1;}}}

分治算法

利用分而治之的思想，将一个大问题分解为小微体，然后将小问题进行解决，再将小问题的解合并为原问题的解

汉诺塔问题，可以将问题分解为两个场景，第一个场景只有一个盘，直接a-c移动就可以，第二个场景多余两个盘，先将除了最下面的盘以外的盘移动到b，然后将最下面的盘移动到c，再把b上的一堆移动到c

代码：

package algorithm;public class hanoiTower {public static void main(String[] args) {hanoi(5,'A','B','C');}public static void hanoi(int num,char a, char b, char c){if (num == 1){System.out.println(a+"-"+c);}else {hanoi(num-1,a,c,b);System.out.println(a+"-"+c);hanoi(num-1,b,a,c);}}}

动态规划算法

背包问题：背包容量为4磅，有以下物品

要求装入的背包物品价值最大，重量不超出限制，物品不能重复

主要的思路就是类似于遍历的思想，最重要生成一个val[i][j]，以记录第i个物品 能够装入 容量为j的背包 中的最大价值。

所以每次做判断的时候，就直接判断当前背包容量j是否可以装下想要装进去的物品i，如果不行，则使用上一行数据（也就是想要装入i-1物品时候，背包容量为j时的val值）来作为当前val；如果可以的话，则判断max{上一行数据，放入当前物品}

上代码：

package algorithm;public class danamic_programming {public static void main(String[] args) {int[] v = {1500,3000,2000};int[] w = {1,4,3};int[][] val = new int[4][5]; //val[i][j] 表示 第i个物品 能够装入 容量为j的背包 中的最大价值for(int i = 1;i<val.length;i++){//i表示当前尝试装入的物品编号for(int j = 1;j<val[i].length;j++){//j表示当前尝试的背包容量if(j<w[i-1]){val[i][j] = val[i-1][j];}else{val[i][j] = Math.max(val[i-1][j],v[i-1]+val[i-1][j-w[i-1]]);}}}//遍历for(int i = 0;i<4;i++){for (int j = 0;j<5;j++){System.out.print(val[i][j]+" ");}System.out.println();}}}

KMP

解决字符串匹配问题。

代码思路：首先构建一个next数组，用来记录遇到不匹配时候减少移动的步骤，然后完成代码

kmp算法和next数组计算函数格式差不多

用一个for循环进行遍历，先使用while判断字符串不相等且j>0，更新j；在使用if判断是否字符串相等，

package algorithm;import java.util.Arrays;public class KMP {public static void main(String[] args) {String str1 = "BBC ABCDAB ABCDABCDABDE";String str2 = "ABCDABD";int[] next = kmpNext("ABCDABD");System.out.println(Arrays.toString(next));System.out.println(kmp(next,str1,str2));}public static int kmp(int[] next,String str1,String str2){for(int i = 0,j=0;i<str1.length();i++){while(j>0 && str1.charAt(i)!=str2.charAt(j)){j = next[j-1];}if(str1.charAt(i) == str2.charAt(j)){j++;}if(j == str2.length()){return i-j+1;}}return -1;}public static int[] kmpNext(String dest){int[] next = new int[dest.length()];next[0] = 0;for(int i = 1,j = 0;i<dest.length();i++){while(j>0 && dest.charAt(i)!=dest.charAt(j)){j = next[j-1];}if(dest.charAt(i)==dest.charAt(j)){j++;}next[i] = j;}return next;}}

贪心算法

贪婪算法步骤：

遍历所有广播电台，找到一个覆盖了最多未覆盖地区的电台将这个电台放入一个集合中，将这个电台覆盖了的区域从所有广播台中去掉再次重复1

代码的思路：

最外层做一个while循环，当仍然有地区没有被覆盖的时候，进入循环。

内层用for循环遍历所有的广播基站，寻找覆盖了最多未覆盖区域的广播基站

实现：

package algorithm;import java.util.ArrayList;import java.util.HashMap;import java.util.HashSet;public class greedyAlgorithm {public static void main(String[] args) {//broadcast表示广播站HashMap<String, HashSet<String>> broadcast = new HashMap<String,HashSet<String>>();HashSet<String> hash1 = new HashSet<String>();hash1.add("北京");hash1.add("上海");hash1.add("天津");HashSet<String> hash2 = new HashSet<String>();hash2.add("广州");hash2.add("北京");hash2.add("深圳");HashSet<String> hash3 = new HashSet<String>();hash3.add("成都");hash3.add("上海");hash3.add("杭州");HashSet<String> hash4 = new HashSet<String>();hash4.add("上海");hash4.add("天津");HashSet<String> hash5 = new HashSet<String>();hash5.add("杭州");hash5.add("大连");broadcast.put("k1",hash1);broadcast.put("k2",hash2);broadcast.put("k3",hash3);broadcast.put("k4",hash4);broadcast.put("k5",hash5);//allAreas存放所有的地区,每次遍历都会更新allAreas，为0则表示覆盖了所有的地区HashSet<String> allAreas = new HashSet<String>();allAreas.add("北京");allAreas.add("上海");allAreas.add("天津");allAreas.add("广州");allAreas.add("大连");allAreas.add("深圳");allAreas.add("成都");allAreas.add("杭州");//selects存放选择了的电台集合ArrayList<String> selects = new ArrayList<String>();//tempSet存放当前电台覆盖范围和还没有覆盖的地区的交集HashSet<String> tempSet = new HashSet<String>();//maxKey表示每次遍历中能覆盖最大未覆盖区域的电台keyString maxKey = null;//临时maxKeySet用来存放在遍历过程中,maxKey覆盖的地区和当前还没有覆盖的地区的交集HashSet<String> tempMaxKeySet = new HashSet<String>();while(allAreas.size()!=0){maxKey = null;tempMaxKeySet.clear();for(String key : broadcast.keySet()){tempSet.clear();//areas表示当前广播站可以覆盖的范围HashSet<String> areas = broadcast.get(key);//求tempSet当前广播站可以覆盖的区域和剩余需要覆盖地区的交集tempSet.addAll(areas);tempSet.retainAll(allAreas);//如果当前广播站可以覆盖比maxKey指向的广播站还多的地区，更新maxKeyif(tempSet.size() > 0 && (maxKey == null || tempSet.size() > tempMaxKeySet.size())){//清空,防止数据间影响tempMaxKeySet.clear();maxKey = key;//maxKey覆盖的地区和当前还没有覆盖的地区的交集HashSet<String> area2 = broadcast.get(maxKey);tempMaxKeySet.addAll(area2);tempMaxKeySet.retainAll(allAreas);}}if(maxKey!=null){selects.add(maxKey);allAreas.removeAll(broadcast.get(maxKey));}}System.out.println("results:"+selects);}}

普里姆算法

实际上就是计算当前图的最小生成树，包含所有的点，边的数量为点数量-1，

算法代码思路就是三重for循环

最外层for循环表示点数量-1次循环，创建数量-1条边；

内层表示寻找所有访问过的节点和所有没访问过的节点，使用if判断，结点连通且权值最小

package Algorithm;public class Prim {public static void main(String[] args) {// TODO Auto-generated method stub//测试图是否创建okchar[] data = new char[] {'A','B','C','D','E','F','G'};int verxs =data.length;int[][] weight = new int[][] {{10000,5,7,10000,10000,10000,2},{5,10000,10000,9,10000,10000,3},{7,10000,10000,10000,8,10000,10000},{10000,9,10000,10000,10000,4,10000},{10000,10000,8,10000,10000,5,4},{10000,10000,10000,4,5,10000,6},{2,3,10000,10000,4,6,10000}};//创建MGraph对象MGraph graph = new MGraph(verxs);//创建一个MinTree对象MinTree minTree = new MinTree();minTree.createGraph(graph, verxs, data, weight);minTree.showGraph(graph);minTree.prim(graph, 0);}static class MinTree{public void createGraph(MGraph graph,int verxs,char data[],int[][] weight) {int i, j;for(i = 0; i < verxs; i++) {graph.data[i] = data[i];for(j = 0; j < verxs; j++) {graph.weight[i][j] = weight[i][j];}}}//最小生成树public void prim(MGraph graph, int v) {//visited[] 标记结点（原点）是否被访问过int visited[] = new int[graph.verxs];visited[v] = 1;int h1 = -1;int h2 = -1;int minWeight = 10000;for(int k = 1; k < graph.verxs; k++) {for(int i = 0; i < graph.verxs; i++) {for(int j = 0; j < graph.verxs; j++) {if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {minWeight = graph.weight[i][j];h1 = i;h2 = j;}}}//找到一条边是最小System.out.println("边<" + graph.data[h1] + graph.data[h2] + "权值:" + minWeight);visited[h2] = 1;minWeight = 10000;}}//显示图的方法public void showGraph(MGraph graph) {for(int i = 0; i < graph.verxs; i++) {for(int j = 0; j < graph.verxs; j++){System.out.printf(graph.weight[i][j] + " ");}System.out.println();}}}static class MGraph{int verxs;//表示图的结点个数char[] data;//存放结点数量int[][] weight;//存放边，就是我们的邻接矩阵public MGraph(int verxs) {this.verxs = verxs;this.data = new char[verxs];weight = new int[verxs][verxs];}}}

克鲁斯卡尔算法

问题描述是有很多公交车站，需要创建一条最短的线路将所有的公交车站都连接起来，本质上也是最小生成树问题

基本思想：先找到所有可连接边的排序，然后从小到大选取n-1条边，并保证n-1条边不构成回路

判断构成回路与否只需要查看新加入的边的两个端点，这两个端点的终点是否相同（每个端点原来的终点是自己），如果相同则说明有回路。

核心代码：

狄杰斯特拉算法

目标是计算某个点出发，到达其他点的最短路径

按照下图的思路，寻找到当前出发点可以到达的点，然后选择最小的那个作为可访问点；然后通过这两个点作为出发点，寻找最小的可访问点，持续下去直到所有点都可以访问

Floyd算法

弗洛伊德算法也是寻找有权图中两点间最短距离的算法，它与狄杰斯特拉不同的地方在于它计算了所有点与其他点之间的最短距离

算法思路就是3个for循环，第一层for循环将所有点作为中间结点，第二，三层for循环查找当前中间节点的连通节点，并进行距离的计算，如果距离小于直接连接的距离，那么更新距离，同时还要更新前去关系表，以记录如何找到最短的路径。

核心代码