精华内容
下载资源
问答
  • 一、树、森林和二叉树之间的转换 树或森林与二叉树之间存在一一对应的关系。任何一棵树或一个森林可唯一地对应到一棵二叉树;反之,任何一棵二叉树也能唯一地对应到一个森林或一棵树。 2.1 将树转化为二叉树 树中...

    一、树、森林和二叉树之间的转换

    树或森林与二叉树之间存在一一对应的关系。任何一棵树或一个森林可唯一地对应到一棵二叉树;反之,任何一棵二叉树也能唯一地对应到一个森林或一棵树。

    1.1 将树转化为二叉树

    树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树,具体步骤是:
    1)在所有兄弟结点之间加一连线;
    2)对每个结点,除了保留与其长子的连线外,去掉该结点与其他孩子的连线。
    示例:将图2.1所示的树转换为二叉树。

    在这里插入图片描述

    根据树转二叉树的规则:第一步,加线;第二步:抹线;第三步:旋转。具体过程如图2.2所示。

    在这里插入图片描述

    注意:由于树根没有兄弟,故树转化为二叉树后,二叉树的根结点的右子树必为空。

    1.2 将一个森林转换为二叉树

    具体方法:
    1)将森林中的每棵树变为二叉树;
    2)因为转换所得的二叉树的根结点的右树均为空,故将各二叉树的根结点视为兄弟从左至右连在一起,就形成了一棵二叉树。

    示例:将如图2.3所示的森林转化为二叉树
    在这里插入图片描述

    1.3 二叉树到树、森林的转换

    把二叉树转换成树和森林的方式是:若结点x是双亲y的左孩子。则把x的右孩子。右孩子的右孩子,…,都与y用连线连起来,最后去掉所有双亲到右孩子的连线。

    示例:将图2.4所示的二叉树转换为树。
    在这里插入图片描述

    二、树、森林的遍历

    2.1 树的遍历

    树的遍历通常有先根遍历和后根遍历两种方式。
    1)先根遍历
    先根遍历的定义为:
    1、访问根结点;
    2、按照从左到右的顺序先根遍历根结点的每一棵子树。
    2)后根遍历
    后根遍历的定义为:
    1、按照从左到右的顺序后根遍历根结点的每一棵子树;
    2、访问根结点。

    示例:
    先根和后根遍历如图2.1(a)所示的树,及先根和中根遍历图2.1(b)所示的二叉树。
    在这里插入图片描述

    根据树的遍历规则,如图2.1(a)所示的树的先根遍历结果是:A,B,C,D,E,F,I,J,D,H;后根遍历结果是:E,C,I,F,J,B,D,H,A。
    根据二叉树的遍历规则:图2.1(a)所示的二叉树的先根遍历结果是:A,B,C,E,F,I,J,D,H;中根遍历结果是:E,C,I,F,J,B,D,H,A。
    2.1(b)所示的二叉树其实是图2.1(a)`所示的树转换而来的,又示例的遍历结果可知:
    1)前序遍历一棵树恰好等价于前序遍历该树对应的二叉树。
    2)后序遍历树恰好等价于中序遍历该树对应的二叉树。

    2.2 森林的遍历

    森林的遍历右前序遍历和后序遍历两种方式。
    1)前序遍历
    前序遍历的定义为:
    1、访问森林中第一棵树的根结点;
    2、前序遍历第一棵树的根结点的子树;
    3、前序遍历去掉第一棵树后的子森林。
    2)后序遍历
    后序遍历的定义为:
    1、后序遍历第一棵树的根结点的子树;
    2、访问森林中第一棵树的根结点;
    3、后序遍历去掉第一棵树后的子森林。

    示例:
    先根和后根遍历如图2.2(a)所示的森林,及先根和中根遍历图2.2(b)所示的二叉树。
    在这里插入图片描述

    根据森林的遍历规则,图2.2(a)所示的树的先根遍历结果是:A,B,C,D,E,F,G,H,I,J,K,L;后根遍历的结果是:B,A,C,F,G,E,D,J,K,I,L,H。
    根据二叉树的遍历规则,图2.2(b)所示的二叉树的先根遍历结果是:A,B,C,D,E,F,G,H,I,J,K,L;中根遍历结果是:B,A,C,F,G,E,D,J,K,L,H。
    图2.2(b)所示的二叉树其实是图2.2(a)所示的森林转换而来的,由示例的遍历结果可推知:
    1、前序遍历一个森林恰好等价于前序遍历该森林对应的二叉树。
    2、后序遍历森林恰好等价于中序遍历该森林对应的二叉树。

    展开全文
  • 评价:整个教程的数据结构部分讲的挺好的,知识点全都覆盖了,而且每个数据结构都有代码解释,但是最后20节算法部分讲的有点乱,算法部分我决定直接刷leetcode了 数组 稀疏数组: 二维数组的省内存的保存方法,一般...

    前言

    视频地址:https://www.bilibili.com/video/BV1E4411H73v?from=search&seid=13120683720695451628

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

    数组

    稀疏数组:

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

    二维数组转稀疏数组:

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

    稀疏数组转二维数组:

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

    2. 读取稀疏数组后几行数据,插入二维数组中

    代码实现:

    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];
        }
    
        //showQueue
        public 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新的元素进去了。

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

    使用数组模拟环形队列

    思路:

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

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

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

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

    1. 队列空时,rear = front。

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

    1. 队列中有效数字的个数为(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;
        }
    
        //showQueue
        public 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类,先创建一个头节点

    遍历思路:

    通过一个辅助变量来遍历

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

    添加内容思路:

    1. 直接添加到尾部:直接加到最后面(遍历找到最后面,再添加)

    2. 按顺序添加:找到要添加的位置,新节点.next = temp.next,temp.next = 新节点。

    修改节点的思路:

    1. 先找到这个节点(遍历)

    2. 修改数值

    删除节点的思路:

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

    2. Node.next = node.next.next;

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

    循环要注意的点!!!

    一般来说,写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;
        }
    
        @Override
        public 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;
                }
            }
    
        }
    }
    
    

    单链表的反转

    思路:

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

    2. 从头到尾遍历原来的表,依次取出节点,并将它放在revertHead的最前端(head后面)

    3. 原来的链表的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;
        }
        @Override
        public 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. 可以实现自我删除,不需要像单链表一样寻找要删除节点的前一个节点

    思路分析:

    遍历:和单向链表一致,可以前向,也可以后向。

    添加元素到链表最后: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;
        }
        @Override
        public 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;
        }
    
        @Override
        public 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());
        }
    }
    
    

    中缀表达式转后缀表达式

    思路:

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

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

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

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

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

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

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

    c) 遇到括号时

    ​ i. 如果是左括号( ,直接压入s1

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

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

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

    递归

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

    递归调用规则:

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

    \2. 每个空间的数据(局部变量),是独立的

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

    递归迷宫问题

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

    思路分析:

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

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

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

    a) 判断是否到达终点

    ​ i. 到达,返回true

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

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

    2. 不能走的话直接返回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;
            //打印一下map
            for (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);
            //打印一下之后的map
            System.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)可以忽略常数项,忽略低次项,忽略系数。

    时间复杂度

    1. 常数阶O(1)

      只要没有循环等复杂结构,都是O(1)。

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

    2. 对数阶O(log2N)

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

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

    3. 线性阶O(n)

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

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

    4. 线性对数阶O(nlogN)

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

      for(int j = 1;j<=n;j++){
      
      int i = 1
      while(i<n){
      	i = i*2;
      }
      
      }
      
    5. 平方阶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来判断元素是否进行过交换,从而减少不必要的比较。

    一般来说,会进行

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

    代码实现:

    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();
    
            //bubble
            bubbleSort 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次,实现排序。

    思路:

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

    代码

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

    归并排序

    利用分治策略,将大问题分为小问题递归进行求解。在这里插入图片描述

    基本思想:

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

    在这里插入图片描述

    思路分析:

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

    分解函数

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

    合并函数

    1. 把左右两边的数据按照规则填充到temp数组,直到有一边序列填充完毕了。
      1. i<mid,j<right的前提下:左右进行比较,小的移动到temp中
      2. 移动之后,被移动的数组中的索引加一,temp的索引加一
    2. 把有剩余的序列全部填充到temp数组中。
    3. 将temp数组拷贝到原数组中
      1. 因为每次传入的数组并不是最后一个完整的数组,所以创立一个临时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++;
    
                }
            }
        }
    }
    
    

    基数排序

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

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

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

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

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

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

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

    代码实现:

    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++;
                        }
                    }
    
                }
    
                //清空bucketIndex
                for (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)来增加访问速度,除此之外,我们还可以在缓存层自己写出一个哈希表来增加访问速度。

    在这里插入图片描述

    哈希表:

    1. 数组+链表
    2. 数组+二叉树

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

    思路分析:

    在这里插入图片描述

    至少要创建3个类

    1. Emp雇员类,表示链表中的结点
    2. EmpLinkedList类,表示链表,链表类需要包含对雇员的操作(add,list,find,del)
    3. 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为层数,称为满二叉树。

    在这里插入图片描述

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

    在这里插入图片描述

    写一个二叉树的思路

    1. 创建两个类:heroNode,BinaryTree
    2. heroNode本身要包含前序中序后序遍历的代码,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;
        }
    
        @Override
        public 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();
        }
    }
    
    

    二叉树查找指定节点

    中序查找思路:

    1. 判断当前节点的子节点是否为空,如果不为空,则递归中序查找。
    2. 如果找到,则返回;
    3. 如果没找到,和当前节点进行比较,如果是则返回当前节点,如果不是,继续进行右递归的中序查找。
    4. 如果找到则返回,没找到,返回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一个节点的情况

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

    代码:

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

    //节点类下面加入如下方法
    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时,仍然可以实现前序中序后序遍历。

    特点:

    1. 只考虑完全二叉树
    2. 第n个元素的左子节点为2*n+1
    3. 第n个元素的右子节点为2*n+2
    4. 第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

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

    遍历线索化二叉树

    思路:

    1. 定义一个变量,存储当前遍历的节点
    2. node不为空的情况下:
      1. 当lefttype = 0时,node = node.left
      2. 打印这个节点
      3. 若当前节点右指针指向后继节点,就一直输出
      4. 不指向后继节点时替换遍历的点(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开始编号的:

    在这里插入图片描述

    在这里插入图片描述

    基本思想:

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

    代码思想:

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

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

    代码思路:

    1. 将数组传入函数中,并遍历数组,将数组的每个元素构成一个Node,组成一个ArrayList nodes,
    2. while循环,当nodes.size>1时:
      1. 将nodes排序
      2. 取出根节点权值最小的两个树
      3. 构建一个新的二叉树(要记得设置新的二叉树的指针指向上面取出的两个二叉树)
      4. 从ArrayList中删除处理过的两个节点
      5. 将新的树加入nodes中
    3. 返回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;
        }
    
        @Override
        public String toString() {
            return "Node[value=" + value + "]";
        }
    
        @Override
        public int compareTo(Node o) {
            return this.value - o.value;
        }
    
    }
    
    

    huffman编码

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

    步骤:

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

    在这里插入图片描述

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

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

    代码思路:

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

    二叉排序树

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

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

    排序树增加节点的思想:

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

    排序树删除节点的思想:

    删除节点有三种情况

    1. 删除叶子节点
    2. 删除只有一颗子树的节点
    3. 删除有两颗子树的节点

    思路分析:

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

    代码思路分析:

    需要添加的函数:

    在Node类

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

      • 使用递归调用的思路,首先判断当前节点是否为目标节点
      • 如果不是,就向左遍历,向右遍历
    • 添加searchParent方法,返回要删除节点的父节点

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

    在二叉排序树类

    • 创建search方法,调用search方法
    • 创建searchParent方法,调用searchParent方法
    • 创建删除二叉排序树的最小节点的方法,并返回最小节点的值
      • 使用循环查找的方法,找到最左端的子树
    • 创建删除节点的方法
      • 首先取出要找到的节点(如果没找到则return,如果二叉树只有一个节点,则删除后return)
      • 找到targetNode的父节点
      • 判断 1. 如果删除的是叶子节点——判断这个节点是左子节点还是右子节点,删除
      • 判断 2. 如果删除的是有两颗子树的节点——找到要删除节点的右子树的最小子节点,并使targetNode = 删去节点的值
      • 判断 3. 如果删除只有一颗子树的节点——判断targetnodeParent的左子节点是targetNode还是右子节点是targetNode
        1. 如果targetnode是parent的左子节点且targetnode有左子节点,parent.left = targetnode.left
        2. 如果targetnode是parent的左子节点且targetnode有右子节点,parent.left = targetnode.right
        3. 如果targetnode是parent的右子节点且targetnode有左子节点,parent.right = targetnode.left
        4. 如果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);
                }
            }
    
            //调用searchParent
            public 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还是右子节点是targetNode
                    if (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树了

      思路:

      1. 创建一个新的节点,值等于当前节点的值
      2. 将新节点的左子树设置为当前节点的左子树
      3. 将新节点的右子树设置为当前节点的右子树的左子树
      4. 把当前节点的值设置为右子节点的值
      5. 把当前节点的右子树设置为右子树的右子树
      6. 把当前节点的左节点设置为新节点
    • 右旋转

      思路和左旋转相同。

    • 双旋转

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

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

    代码实现:

    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);
                }
            }
    
            //调用searchParent
            public 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还是右子节点是targetNode
                    if (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);
                    }
                }
                //判断是否满足AVLtree
                if(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;
            }
        }
    

    多路查找树

    二叉树的问题分析:

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

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

    一个多叉树的例子
    在这里插入图片描述

    B树:

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

    在这里插入图片描述

    2-3树

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

    在这里插入图片描述

    1. 所有叶子节点在同一层(B树都满足这个条件)
    2. 有两个节点的节点叫做二节点,二节点要么没有子节点,要么有两个子节点
    3. 有三个节点的节点叫做三节点,三节点要么没有子节点,要么有三个子节点
    4. 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. 遍历所有广播电台,找到一个覆盖了最多未覆盖地区的电台
    2. 将这个电台放入一个集合中,将这个电台覆盖了的区域从所有广播台中去掉
    3. 再次重复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表示每次遍历中能覆盖最大未覆盖区域的电台key
            String 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指向的广播站还多的地区,更新maxKey
                    if(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
    		//测试图是否创建ok
    		char[] 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循环查找当前中间节点的连通节点,并进行距离的计算,如果距离小于直接连接的距离,那么更新距离,同时还要更新前去关系表,以记录如何找到最短的路径。

    核心代码

    在这里插入图片描述

    展开全文
  • GitHub源码分享项目主页:https://github.com/gozhuyinglong/blog-demos本文源码:https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures1. 前言我们前面讲到了数组和链表两种数据结构,其...

    GitHub源码分享

    项目主页:https://github.com/gozhuyinglong/blog-demos

    本文源码:https://github.com/gozhuyinglong/blog-demos/tree/main/java-data-structures

    1. 前言

    我们前面讲到了数组和链表两种数据结构,其各自有自己的优缺点,我们来回顾一下。

    数组(Array)

    优点:通过下标访问速度非常快。

    缺点:需要检索具体某个值时,或者插入值时(会整体移动)效率较低

    链表(Linked List)

    优点:在插入某个值时,效率比数组高

    缺点:检索某个值时效率仍然较低

    我们本篇讲到的树,便能提高数据的存储和读取效率。

    2. 树(Tree)

    树是一种非线性的数据结构,它包含n(n>=1)个节点,(n-1)条边的有穷集合。把它叫做“树”是因为它看起来像一个倒挂的树,也就是说它是根朝上,叶子朝下的。

    3. 树结构的特点

    树结构的每个元素称为节点(node)

    每个节点都有零个或多个子节点

    没有父节点的节点叫做根节点(root)

    每一个非根结点有且只有一个父结点

    除了根结点外,每个子结点可以分为多个不相交的子树

    父子节点由一条有向的边(edgeo)相连结。

    1460000038332826

    4. 树的常用术语

    结合上图了解树的常用术语,加深对树的理解。

    节点(node)

    树结构中的每一个元素称为一个节点,如上图中的ABC……M

    根节点(root)

    没有父节点的节点叫做根节点,如上图中的A

    父节点(parent)

    一个节点的上级节点叫做它的父节点,一个节点最多只能有一个父节点,如上图中C是F的父节点

    子节点(child)

    一个节点的下级节点叫做它的子节点,一个节点的子节点可以有多个,如上图中的IJK是E的子节点

    兄弟节点(siblings)

    拥有相同父节点的节点叫做兄弟节点,如上图中的L和M是兄弟节点

    叶子节点(leaf)

    没有子节点的节点叫做叶子节点,如图中的BFGLMIJK

    边(dege)

    父子节点间的连接称为边,一棵树的边数为(n-1)

    节点的权(weight)

    节点上的元素值

    路径(path)

    从root节点找到该节点的路线,如上图中L的路径为A-D-H-L。路径的长为该路径上边的条数,L路径的长为3(n-1)。

    层(layer)

    距离根节点相等的路径长度为一层,如上图中A为第一层;BCDE为第二层;FGHIJK为第三层;LM为第四层

    子树(child tree)

    以某一节点(非root)做为根的树称为子树,如以E为根的树称为A的子树

    树的高度(height)

    树的最大层数,上图中树的高度为4

    森林(words)

    多棵子树构成树林

    5. 代码实现

    我们将第3章中的树结构图通过Java代码进行实现。

    TreeNode类为树的一个节点,其中:

    element:存储当前节点的元素数据

    firstChild:指向当前节点的第一个子节点(如:A的firstChild为B;D的firstChild为G;G的firstChild为空)

    nextSibling:指向当前节点的下一个兄弟节点(如:B的nextSibling为C;G的nextSibling为H;H的nextSibling为空)

    Tree类实现了一棵树的初始化和遍历,listAll遍历算法的核心是递归。具体内容见代码

    public class TreeDemo {

    public static void main(String[] args) {

    new Tree().initTree().listAll();

    }

    private static class Tree {

    private TreeNode root; // 树根

    /**

    * 初始化一棵树

    */

    private Tree initTree() {

    TreeNode a = new TreeNode("A");

    TreeNode b = new TreeNode("B");

    TreeNode c = new TreeNode("C");

    TreeNode d = new TreeNode("D");

    TreeNode e = new TreeNode("E");

    TreeNode f = new TreeNode("F");

    TreeNode g = new TreeNode("G");

    TreeNode h = new TreeNode("H");

    TreeNode i = new TreeNode("I");

    TreeNode j = new TreeNode("J");

    TreeNode k = new TreeNode("K");

    TreeNode l = new TreeNode("L");

    TreeNode m = new TreeNode("M");

    root = a;

    a.firstChild = b;

    b.nextSibling = c;

    c.nextSibling = d;

    c.firstChild = f;

    d.nextSibling = e;

    d.firstChild = g;

    e.firstChild = i;

    g.nextSibling = h;

    h.firstChild = l;

    i.nextSibling = j;

    j.nextSibling = k;

    l.nextSibling = m;

    return this;

    }

    /**

    * 遍历一棵树,从root开始

    */

    public void listAll() {

    listAll(root, 0);

    }

    /**

    * 遍历一棵树

    *

    * @param node 树节点

    * @param depth 层级(用于辅助输出)

    */

    public void listAll(TreeNode node, int depth) {

    StringBuilder t = new StringBuilder();

    for (int i = 0; i < depth; i++) {

    t.append("t");

    }

    System.out.printf("%s%sn", t.toString(), node.element);

    // 先遍历子节点,子节点的层级需要+1

    if (node.firstChild != null) {

    listAll(node.firstChild, depth + 1);

    }

    // 后遍历兄弟节点,兄弟节点的层级不变

    if (node.nextSibling != null) {

    listAll(node.nextSibling, depth);

    }

    }

    }

    private static class TreeNode {

    private final Object element; // 当前节点数据

    private TreeNode firstChild; // 当前节点的第一个子节点

    private TreeNode nextSibling; // 当前节点的下一个兄弟节点

    public TreeNode(Object element) {

    this.element = element;

    }

    }

    }

    输出结果:

    A

    B

    C

    F

    D

    G

    H

    L

    M

    E

    I

    J

    K

    程序员灯塔

    转载请注明原文链接:Java数据结构与算法分析 | 树

    展开全文
  • 课程目录:数据结构-Java版(20集)|____第20讲 - 图的最小生成树.avi|____第19讲 - 图的搜索.avi|____第18讲 - 图的基本概念.avi|____第17讲 - 链地址法.avi|____第16讲 - 开放地址法.avi|____第15讲 - 哈希表.avi|__...

    课程目录:

    数据结构-Java版(20集)

    |____第20讲 - 图的最小生成树.avi

    |____第19讲 - 图的搜索.avi

    |____第18讲 - 图的基本概念.avi

    |____第17讲 - 链地址法.avi

    |____第16讲 - 开放地址法.avi

    |____第15讲 - 哈希表.avi

    |____第14讲 - 红黑树.avi

    |____第13讲 - 删除二叉树节点.avi

    |____第12讲 - 遍历二叉树.avi

    |____第11讲 - 二叉树的基本操作.avi

    |____第10讲 - 二叉树的基本概念.avi

    |____第09讲 - 快速排序.avi

    |____第08讲 - 希尔排序.avi

    |____第07讲 - 递归的高级应用.avi

    |____第06讲 - 递归的应用.avi

    |____第05讲 - 双端链表和双向链表.avi

    |____第04讲 - 链表.avi

    |____第03讲 - 栈和队列.avi

    |____第02讲 - 简单排序.avi

    |____第01讲 - 数组.avi

    |____JavaData.rar

    |____小甲鱼数据结构与算法更新——————第四部等多个文件

    |____小甲鱼数据结构与算法更新——————第四部

    |____小甲鱼 数据结构与算法————————第四部

    |____小甲鱼 数据结构与算法————————第四部

    |____69_关键路径(代码讲解).mp4

    |____68_关键路径.mp4

    |____67_拓扑排序.mp4

    |____66_最短路径(弗洛伊德算法).mp4

    |____65_最短路径(迪杰斯特拉算法).mp4

    |____64_最小生成树(克鲁斯卡尔算法).mp4

    |____63_最小生成树(普里姆算法).mp4

    |____62_图的遍历(广度优先遍历).mp4

    |____61_马踏棋盘算法(骑士周游问题).mp4

    |____60_图的遍历(深度优先遍历).mp4

    |____59_图的存储结构(十字链表、邻接多重表、边集数组).mp4

    |____58_图的存储结构(邻接表).mp4

    |____57_图的存储结构.mp4

    |____56_图的定义与术语2.mp4

    |____55_图.mp4

    |____54_赫夫曼编码C语言实现.mp4

    |____53_赫夫曼编码.mp4

    |____52_赫夫曼树.mp4

    |____51_树、森林及二叉树的相互转换.mp4

    |____50_线索二叉树代码实现.mp4

    |____49_线索二叉树.mp4

    |____48_二叉树的建立和遍历算法.mp4

    |____47_二叉树的遍历.mp4

    |____46_二叉树的存数结构.mp4

    |____45_二叉树2.mp4

    |____44_二叉树.mp4

    |____43_树的存储结构2.mp4

    |____42_树的存储结构.mp4

    |____41_树.mp4

    |____40_KMP算法之实现及优化.mp4

    |____39_KMP算法之NEXT数组代码原理分析.mp4

    |____38_KMP算法2.mp4

    |____37_KMP算法.mp4

    |____36_字符串.mp4

    |____35_八皇后问题.mp4

    |____34_汉诺塔.mp4

    |____33_递归和分治思想2.mp4

    |____32_递归和分治思想.mp4

    |____31_栈和队列8.mp4

    |____30_栈和队列7.mp4

    |____29_中缀表达式转换为后缀表达式02.mp4

    |____28_中缀表达式转换为后缀表达式01.mp4

    |____27_逆波兰计算器.mp4

    |____26_栈和队列4.mp4

    |____25_进制转换.mp4

    |____24_栈和队列2.mp4

    |____23_栈和队列.mp4

    |____22_线性表17.mp4

    |____21_线性表16.mp4

    |____20_魔术师发牌问题.mp4

    |____19_线性表14.mp4

    |____18_约瑟夫问题.mp4

    |____17_线性表12.mp4

    |____16_单链表小结:腾讯面试题.mp4

    |____15_线性表10.mp4

    |____14_线性表9.mp4

    |____13_线性表8.mp4

    |____12_线性表7.mp4

    |____11_线性表6.mp4

    |____10_线性表5.mp4

    |____09_线性表4.mp4

    |____08_线性表3.mp4

    |____07_线性表2.mp4

    |____06_线性表.mp4

    |____05_时间复杂度和空间复杂度3.mp4

    |____04_时间复杂度和空间复杂度2.mp4

    |____03_时间复杂度和空间复杂度.mp4

    |____02_谈谈算法.mp4

    |____01_数据结构和算法绪论.mp4

    展开全文
  • 5.9 森林 5.10 不相交集合的表示 5.11 二叉树的计数 5.12 参考文献和选读材料 第6章 图 6.1 图的抽象数据类型 6.2 图的基本操作 6.3 最小代价生成树 6.4 最短路径和迁移闭包 6.5 活动网络 6.6 参考文献和...
  • 计算机科学中的树在计算机科学中,树(英语:tree)是一种抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。把它...
  • 前言仿佛一下子,2017年就快过去一半了,研一马上就要...亦即总结常见的的数据结构,以及在Java中相应的实现方法,务求理论与实践一步总结到位。首先给出Java集合框架的基本接口/类层次结构:java.util.Collection...
  • P28-4.1树结构概述 P29-4.2二叉树的概述 P30-4.3创建二叉树 P31-4.4遍历二叉树 P32-4.5二叉树中节点的查找 P33-4.6删除二叉树的子树 1、BinaryTree.java 2、Node.java 3、TestBinaryTree.java
  • 把图中的n个顶点看成独立的n棵树组成的森林; 按权值从小到大选择边,若形成环,不选,所选的边连接的两个顶点ui,vi,应属于两颗不同的树,则成为最小生成树的一条边,并将这两颗树合并作为一颗树。 重复(3),直到...
  • 部分 知识提炼与实例解析章 绪论1.1 数据结构的基本概念1.1.1 知识提炼1.1.2 典型实例解析1.1.3 实例练习1.2 算法与算法分析1.2.1 知识提炼1.2.2 典型实例解析1.2.3 实例练习1.3 实例练习解答1.3.1...
  • 第1章绪论11.1学习数据结构的意义11.1.1引言11.1.2数据结构研究什么21.2数据结构的基本概念31.3算法及其描述41.3.1算法的概念和特性41.3.2算法设计的要求51.3.3算法的分析51.4小结71.5习题7第2章线性表92.1线性表的...
  • 初入数据结构的树(Tree)以及Java代码实现 树的定义 为什么叫树? 树型结构的元素具有一对多关系 树的定义 树的一些基本概念 树的结点 后代,祖先 子树、空树 树的度与高(深度),结点的度与层次 有序树,无序...
  • 原标题:Java关于数据结构的实现:树文章目录一、树的概念与应用场景1.1 二叉查找树1.2 AVL树1.3 红黑树1.4 B树二、树的操作与源码实现2.1 TreeMap/TreeSet实现原理写在前面之前在网上看到过很多关于Java集合框架...
  • Java数据结构课程设计(fntp开源)

    千次阅读 2020-01-17 19:18:31
    java数据结构课程设计(哈夫曼树压缩实现) 开源作者:fntp QQ358566760欢迎读者与笔者交流沟通 使用java数据结构与算法,来实现哈夫曼树压缩文本数据,如何实现呢? 哈夫曼树简单介绍: 在计算机数据处理中,哈夫曼...
  • 数据结构JAVA语言描述习题答案(刘小晶等主编)pdf总复习纵咎链侈蹬苏鞠看去送你行肌棋革初霉滦岭食恶桐潭嗅凳讥嚣祷茵妒陕两数据结构JAVA语言描述习题答案(刘小晶等主编)pdf总复习数据结构JAVA语言描述习题答案(刘小...
  • 三、哈夫曼编码 在数据通信中,需要将传送的文字转化成二进制的字符串,用0,1码的不同排序来表示字符。最简单的二进制编码方式时等长编码,第2节示例中通信的电文用固定3位二进制。可分别用000、001、010、011、100...
  • 二叉树Java数据结构

    2021-07-22 16:18:08
    许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树,且有左右之...
  • 由于二叉堆逻辑结构上是一个完全二叉树,节点之间是按照顺序排列的,在存储之上可以采用数组的形式来存储节点。 数组索引的规律 (n 代表着数组的索引) 0 位置的元素是根节点 n > 0 节点的父节点 floor ( (i - 1 )...
  • 1.数据结构基础2.线性表(顺序存储、链式存储)元素之间是有顺序的:第一个元素无前驱,最后一个元素无后继,其他元素都有前驱和后继顺序存储结构:用一段地址连续的存储单元一次存储线性表的数据元素(存取时间复杂度...
  • 数据结构:存储数据的结构 算法:操作数据的方法 如何操作数据效率高,更节约资源 数据结构 可分为 线性结构、树形结构、图 动画效果 线性表 数据像线一样排列 主要有:数组、链表、队列、栈等 数组 线性表...
  • JAVA数据结构——树

    2021-10-30 15:44:07
    数据结构-——树为什么需要树这种数据结构?树的基本概念树的术语二叉树的概念前序后续中序遍历二叉树 为什么需要树这种数据结构? 数组存储方式:增删效率慢 链式存储方式:改查效率慢 树能提高数据存储,读取的...
  • 详细介绍了树这种数据结构的基本概念,以及通用的树的Java实现方式,为后面各种树的深入学习打好基础。
  • 它和一般的线性结构相比更具有层次性,它的功能比线性数据结构的功能更强大。因此作者这篇文章介绍一下怎样用数组实现一个自由树。 先从网上搜集一下树的相关定义和属性特点: 解释 树状图是一种数据结构,它是由...
  • ~9 S' r7 iJ# _数据结构-Java版(20集)7 {2 h5 w' i9 C' }& }$ J|____第20讲 - 图的最小生成树.avi" L* ^+ u" y3 g3 S- W0 t" g! v|____第19讲 - 图的搜索.avi# n3 x2 Y( }: w# x, G|____第18讲 - 图的基本概念....
  • java算法与数据结构

    2012-04-14 12:34:38
    算法与数据结构基本概念 (1)数据、数据对象和数据结构 (2)抽象数据类型 (3)算法的特征及评价的标准 (4)数据的存储结构类型 2.线形结构 (1)顺序表的特点及存储结构 (2)链表的特点及存储结构 (3)栈的...
  • 树的定义:n(n>=0)个节点的有限集。...树的一些基本术语:树的结点:由一个数据元素和若干个指向其子树的分支组成。结点的度:结点所拥有的子树的个数(即分支数)称为该结点的度。叶子结点:度为0的结点称为...
  • 一、树的定义 树(Tree)是 n(n≥0) 个结点的有限集T,并且当 n>0 时满足下列条件: 有且仅有一个特定的称为根(Root)的结点; 当 n>1 时,其余结点可以划分为 m(m>0) 个互不相交的...如下是一棵树的结构: ...
  • java数据结构与算法【数据结构篇】 算法是程序的灵魂,是面试的大考 数据结构是编程语言的衍生物,使得代码更漂亮 数据结构是算法的基础 一、概要 (一)线性结构 1、最常用,特点为数据元素间存在一对一的线性关系...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,762
精华内容 3,104
关键字:

java森林数据结构

java 订阅
数据结构 订阅