数据结构

作者: 朴炯文 | 来源:发表于2019-04-11 16:32 被阅读0次

1 线性表

1.1 顺序存储结构

1.1.1 特点

查找的性能高

1.1.2 代表

ArrayList(java)，vector(java)，stack(java)

1.2 链式存储结构

1.2.1 特点

插入、删除的性能高

1.2.2 分类

单项链表、双向链表、单项循环链表、双向循环链表

1.2.3 代表

LinkedList(java)，Queue(java)

2 Map

3 Tree

3.1 二叉树

3.1.1 斜树

3.1.2 满二叉树

3.1.3 完全二叉树

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

3.1.4 二叉树（视频）

package com.dn.binarytree;

import java.util.*;

public class BinaryTree {
    
    public static void main(String[] args) {
        BinaryTree binaryTree=new BinaryTree();
//      binaryTree.createBinaryTreeNor();
//      int height=binaryTree.getHeight();
//      System.out.println("treeHeight:"+height);
//      int size=binaryTree.getSize();
//      System.out.println("treeSize:"+size);
//      binaryTree.preOrder(binaryTree.root);
//      binaryTree.midOrder(binaryTree.root);
//      binaryTree.postOrder(binaryTree.root);
    
        ArrayList<String> data=new ArrayList<>();
        String[] dataArray=new String[]{"A","B","D","#","#","E","#","#","C","#","F","#","#"};
        for (String string : dataArray) {
            data.add(string);
        }
        binaryTree.createBinaryTreePre(data);
        binaryTree.preOrder(binaryTree.root);
    }

    public class TreeNode{  
        private int index;
        

        private String data;
        private TreeNode leftChild;
        private TreeNode rightChild;
    
        
        public TreeNode(int index,String data){
            this.index=index;
            this.data=data;
            this.leftChild=null;
            this.rightChild=null;
            
        }
        
        public int getIndex() {
            return index;
        }

        public void setIndex(int index) {
            this.index = index;
        }

        public String getData() {
            return data;
        }

        public void setData(String data) {
            this.data = data;
        }

    }
    
    private TreeNode root=null;
    
    public BinaryTree(){
        root=new TreeNode(1,"A");
    }
    
//构建查找二叉树
    
    
    
    
//  构建二叉树
//      A 
//    /   \
//   B      C
//  / \      \
// D   E      F 
    public void createBinaryTreeNor(){
        createBinaryTree();
    }
    public void createBinaryTree(){
        TreeNode nodeB=new TreeNode(2,"B");
        TreeNode nodeC=new TreeNode(3,"C");
        TreeNode nodeD=new TreeNode(4,"D");
        TreeNode nodeE=new TreeNode(5,"E");
        TreeNode nodeF=new TreeNode(6,"F");
        root.leftChild=nodeB;
        root.rightChild=nodeC;
        nodeB.leftChild=nodeD;
        nodeB.rightChild=nodeE;
        nodeC.rightChild=nodeF;
    }
    //求深度
    public int getHeight(){
        return getHeight(root);
    }
    
    private int getHeight(TreeNode node){
        if(node==null){
            return 0;
        }else{
            int i=getHeight(node.leftChild);
            int j=getHeight(node.rightChild);
            return (i<j)?j+1:i+1;
        }
    }
    
    //求节点总数
    public int getSize(){
        return getSize(root);
    }
    
    private int getSize(TreeNode node){
        if(node==null){
            return 0;
        }else{
            return 1+getSize(node.leftChild)+getSize(node.rightChild);
        }
    }
    
    //前序遍历-迭代
    public void preOrder(TreeNode node){
        if(node==null){
            return;
        }else{
            System.out.println("preOrder data:"+node.getData());
            preOrder(node.leftChild);
            preOrder(node.rightChild);
        }
    }
    
    //通过前序遍历的结果反向生成二叉树
//          A
//        /   \
//      B       C
//     / \     / \ 
//    D   E   #   F
//   / \  /\     / \    
//  #  # # #    #   #
//  
//  A B D # # E # # C # F # #   
    public void createBinaryTreePre(ArrayList<String> data){
        createBinaryTree(data.size(),data);
    }
    
    public TreeNode createBinaryTree(int size,ArrayList<String> data){
        if(data.size()==0){
            return null;
        }
        String d=data.get(0);
        TreeNode node;
        int index=size-data.size();
        if(d.equals("#")){
            node=null;
            data.remove(0);
            return node;
        }
        node=new TreeNode(index,d);
        if(index==0){
            root=node;
            
        }
        data.remove(0);
        node.leftChild=createBinaryTree(size,data);
        node.rightChild=createBinaryTree(size,data);
            
        
        return node;
    }
    
    
    
    //中序遍历-迭代
    public void midOrder(TreeNode node){
        if(node==null){
            return;
        }else{
            midOrder(node.leftChild);
            System.out.println("midOrder data"+node.getData());
            midOrder(node.rightChild);
        }
    }
    
    //后序遍历-迭代
    public void postOrder(TreeNode node){
        if(node==null){
            return;
        }else{
            postOrder(node.leftChild);
            postOrder(node.rightChild);
            System.out.println("preOrder data:"+node.getData());
        }
    }
}

3.1.5 查找二叉树（视频）

package com.pjw.sw;

public class SearchBinaryTree {
    private TreeNode root;
    
    public SearchBinaryTree(){
        
    }
    
    public static void main(String[] args) {
        
        SearchBinaryTree binaryTree=new SearchBinaryTree();
        int[] datas=new int[]{50,30,20,44,88,33,87,16,7,77};
        for (int i : datas) {
            binaryTree.put(i);
        }
        binaryTree.midOrder(binaryTree.root);
        binaryTree.deleteNode(16);
        System.out.println("##############");
        binaryTree.midOrder(binaryTree.root);
    }
    
    //中序遍历-迭代
    public void midOrder(TreeNode node){
        if(node==null){
            return;
        }else{
            midOrder(node.leftChild);
            System.out.println("midOrder data"+node.getData());
            midOrder(node.rightChild);
        }
    }
    
    
    //创建查找二叉树，添加节点
    public TreeNode put(int data){
        TreeNode node=null;
        TreeNode parent=null;
        
        if(root==null){
            node=new TreeNode(0,data);
            root=node;
            return node;
        }
        node=root;
        while(node!=null){
            parent=node;
            if(data>node.data){
                node=node.rightChild;
            }else if(data<node.data){
                node=node.leftChild;
            }else{
                return node;
            }
        }
        node=new TreeNode(0,data);
        if(data<parent.data){
            parent.leftChild=node;
        }else{
            parent.rightChild=node;
        }
        node.parent=parent;
        return node;
    }
    
    //删除节点
    public void deleteNode(int key){
        TreeNode node=searchNode(key);
        if(node==null){
            System.out.println("该节点无法找到");
        }else{
            delete(node);
        }
    }
    
    
    public void delete(TreeNode node) {
        if(node==null){
            System.out.println("该节点无法找到");
        }else{
            TreeNode parent=node.parent;
            //被删除的节点没有孩子
            if(node.leftChild==null&&node.rightChild==null){
                if(parent.leftChild==node){
                    parent.leftChild=null;
                }else{
                    parent.rightChild=null;
                }
                return;
            }
            
            
            //被删除的只有左儿子
            if(node.leftChild!=null&&node.rightChild==null){
                if(parent.leftChild==node){
                    parent.leftChild=node.leftChild;
                }else{
                    parent.rightChild=node.leftChild;
                }
                return;
            }
            
            
            //被删除的只有右儿子
            if(node.leftChild==null&&node.rightChild!=null){
                if(parent.leftChild==node){
                    parent.leftChild=node.rightChild;
                }else{
                    parent.rightChild=node.rightChild;
                }
                return;
            }
            
            //被删除的有左儿子和右儿子
            TreeNode next=getNextNode(node);
            delete(next);
            node.data=next.data;
            
            
            
            
        }
        
    }

    
    //找该节点的后继节点
    private TreeNode getNextNode(TreeNode node) {
        if(node==null){
            return null;
        }else{
            if(node.rightChild!=null){
                return getMinTreeNode(node.rightChild);
            }else{
                TreeNode parent=node.parent;
                while(parent!=null&&node==parent.rightChild){
                    node=parent;
                    parent=parent.parent;
                }
                return parent;
            }
        }
    }

    private TreeNode getMinTreeNode(TreeNode node) {
        if(node==null){
            return null;
        }else{
            while(node.leftChild!=null){
                node=node.leftChild;
            }
        }
        return node;
    }

    public TreeNode searchNode(int key) {
        TreeNode node=root;
        if(node==null){
            return null;
        }else{
            while(node!=null&&key!=node.data){
                if(key<node.data){
                    node=node.leftChild;
                }else{
                    node=node.rightChild; 
                }
            }
        }
        return null;
    }


    public class TreeNode{
        private int key;
        private TreeNode leftChild;
        private TreeNode rightChild;
        private TreeNode parent;
        private int data;
        public TreeNode(int key, int data) {
            super();
            this.key = key;
            this.data = data;
            this.leftChild=null;
            this.rightChild=null;
            this.parent=null;
        }
        public int getKey() {
            return key;
        }
        public void setKey(int key) {
            this.key = key;
        }
        public TreeNode getLeftChild() {
            return leftChild;
        }
        public void setLeftChild(TreeNode leftChild) {
            this.leftChild = leftChild;
        }
        public TreeNode getRightChild() {
            return rightChild;
        }
        public void setRightChild(TreeNode rightChild) {
            this.rightChild = rightChild;
        }
        public TreeNode getParent() {
            return parent;
        }
        public void setParent(TreeNode parent) {
            this.parent = parent;
        }
        public int getData() {
            return data;
        }
        public void setData(int data) {
            this.data = data;
        }
        
    }
}

3.1.6 我的二叉树

前序遍历.png

mid.png

后.png

import java.util.*;
public class MyTree {
    public static void main(String[] args) {


     

    }

    //已知节点总数，求树的层数
    public static int 求树的层数(int 节点总数){
        if(节点总数>0){
            int 临时变量=2;
            int 返回值=1;
            while(临时变量<=节点总数){
                临时变量=临时变量*2;
                返回值++;
            }
            return 返回值;
        }else{
            return -1;
        }

    }

    //已知树的层树，求树的左侧索引
    public static ArrayList<Integer> 求树的左侧索引(int 树的层树){
        ArrayList<Integer> 返回值=new ArrayList<>();
        if(树的层树>0){

            int 临时变量=0;
            for (int i = 0; i < 树的层树; i++) {
                返回值.add(临时变量);
                临时变量=临时变量*2+1;
            }

            return 返回值;
        }else{
            返回值.add(-1);
            return 返回值;
        }

    }

    //求父节点索引
    public static int 求父节点索引(int 自己的索引){
        if(自己的索引==0){
            return -1;
        }
        if(自己的索引>0){
            return (自己的索引+1)/2-1;
        }else{
            return -1;
        }

    }

    //求左儿子节点索引
    public static int 求左儿子节点索引(int 自己的索引,int 节点总数){
        if(自己的索引*2+1>节点总数-1){
            return -1;
        }else{
            return 自己的索引*2+1;
        }
    }

    //求右儿子节点索引
    public static int 求右儿子节点索引(int 自己的索引,int 节点总数){
        if(自己的索引*2+2>节点总数-1){
            return -1;
        }else{
            return 自己的索引*2+2;
        }
    }

    //返回最近的有右兄弟的祖宗
    public static int 返回最近的有右兄弟的祖宗(int 自己的索引){
        if(自己的索引==0){
            return -1;
        }
        int 临时变量=自己的索引;
        for(;;){
            临时变量=求父节点索引(临时变量);
            if(临时变量%2==1){
                return 临时变量;
            }else if(临时变量==0){
                临时变量=-1;
                return 临时变量;
            }

        }
    }

    //求最远左子孙
    public static int 求最远左子孙(int 自己的索引,int 节点总数){
        if(自己的索引*2+1>节点总数){
            return -1;
        }
        int 返回值=自己的索引;
        while(返回值*2+1<=节点总数-1){
            返回值=返回值*2+1;
        }

        return 返回值;
    }

    //求自己的右兄弟
    public static int 求自己的右兄弟(int 自己的索引,int 节点总数){
        if(自己的索引%2==0){
            return -1;
        }
        if(自己的索引+1<=节点总数-1){
            return 自己的索引+1;
        }else {
            return -1;
        }
    }

    //前序遍历二叉树
    public static LinkedList<Integer> 前序遍历二叉树(int 节点总数){
        LinkedList<Integer> 前序遍历索引=new LinkedList<>();
        int 当前索引=0;
        前序遍历索引.add(当前索引);
        for(;;){


            //有没有左儿子
            if(求左儿子节点索引(当前索引,节点总数)>0){  //有
                当前索引=求左儿子节点索引(当前索引,节点总数);
                前序遍历索引.add(当前索引);
            }else{  //没有

                //有没有右兄弟

                if(当前索引%2==1&&当前索引!=节点总数-1){        //有

                    //移动到右兄弟
                    当前索引++;
                    前序遍历索引.add(当前索引);

                    //查看它的祖宗有没有右兄弟
                    if(返回最近的有右兄弟的祖宗(当前索引)>0){ //有

                        当前索引=返回最近的有右兄弟的祖宗(当前索引)+1;
                        前序遍历索引.add(当前索引);
                    }else{  //没有

                        break;
                    }


                }else{  //没有

                    //有没有父亲
                    if(当前索引==0){    //没有
                        break;
                    }else{  //有

                        //查看它的祖宗有没有右兄弟
                        if(返回最近的有右兄弟的祖宗(当前索引)>0){ //有
                            当前索引=返回最近的有右兄弟的祖宗(当前索引)+1;

                            前序遍历索引.add(当前索引);
                        }else{  //没有

                            break;
                        }
                    }
                }

            }
        }

        return 前序遍历索引;
    }

    //中序遍历二叉树
    public static LinkedList<Integer> 中序遍历二叉树(int 节点总数) {
        LinkedList<Integer> 中序遍历索引 = new LinkedList<>();
        int 当前索引=求最远左子孙(0,节点总数);
        中序遍历索引.add(当前索引);
        a:for(;;){

            //是否有父亲
            if(求父节点索引(当前索引)>=0){    //有
                当前索引=求父节点索引(当前索引);
                中序遍历索引.add(当前索引);

                b:for(;;){
                    //有没有右儿子
                    if(求右儿子节点索引(当前索引,节点总数)>0){  //有
                        int 右儿子节点=求右儿子节点索引(当前索引,节点总数);

                        //右孩子有没有子孙
                        if(求左儿子节点索引(右儿子节点,节点总数)>0){   //有
                            当前索引=求最远左子孙(右儿子节点,节点总数);
                            中序遍历索引.add(当前索引);
                            continue a;
                        }else{  //没有
                            当前索引=右儿子节点;
                            中序遍历索引.add(当前索引);

                            //有没有最近的有右兄弟的祖宗
                            if(返回最近的有右兄弟的祖宗(当前索引)==-1){ //没有
                                break a;
                            }else{  //有
                                当前索引=求父节点索引(返回最近的有右兄弟的祖宗(当前索引));
                                中序遍历索引.add(当前索引);
                                continue b;
                            }
                        }
                    }else{  //没有

                      //自己有没有有兄弟
                        if(求自己的右兄弟(当前索引,节点总数)>0){   //有
                            continue a;
                        }else{  //没有

                            //有没有最近的有右兄弟的祖宗
                            if(返回最近的有右兄弟的祖宗(当前索引)==-1){ //没有
                                break a;
                            }else{  //有
                                当前索引=求父节点索引(返回最近的有右兄弟的祖宗(当前索引));
                                中序遍历索引.add(当前索引);
                                continue b;
                            }

                        }
                    }
                }

            }else{  //没有
                break a;
            }
        }

        return 中序遍历索引;
    }

    //后序遍历二叉树
    public static LinkedList<Integer> 后序遍历二叉树(int 节点总数) {
        LinkedList<Integer> 后序遍历索引 = new LinkedList<>();
        int 当前索引=求最远左子孙(0,节点总数);
        后序遍历索引.add(当前索引);
        for (;;){
            //有没有右兄弟？
            if(求自己的右兄弟(当前索引,节点总数)>0){   //有
                int 自己的右兄弟=求自己的右兄弟(当前索引,节点总数);

                //右兄弟有没有子孙？
                if(求左儿子节点索引(自己的右兄弟,节点总数)>0){    //有
                    当前索引=求最远左子孙(自己的右兄弟,节点总数);
                    后序遍历索引.add(当前索引);
                    continue;
                }else{  //没有
                    当前索引=自己的右兄弟;
                    后序遍历索引.add(当前索引);
                    continue;
                }

            }else{  //没有

                //有没有父亲？
                if(求父节点索引(当前索引)>=0){    //有
                    当前索引=求父节点索引(当前索引);
                    后序遍历索引.add(当前索引);
                    continue;

                }else{  //没有
                    break;
                }
            }


        }

        return 后序遍历索引;
    }
}

4 Graph

4.1

dfs.png


import java.util.*;

public class Graph {
    public static void main(String[] args) {
        Integer[] guanxi={
              //0,1,2,3,4,5,6,7,8
                0,1,5,0,0,0,0,0,0,   //0

                1,0,3,7,5,0,0,0,0,    //1

                5,3,0,0,1,7,0,0,0,    //2

                0,7,0,0,2,0,3,0,0,   //3

                0,5,1,2,0,3,6,9,0,    //4

                0,0,7,0,3,0,0,5,0,    //5

                0,0,0,3,6,0,0,2,7,    //6

                0,0,0,0,9,5,2,0,4,    //7

                0,0,0,0,0,0,7,4,0,    //8

        };
        String[] hang={"0","1","2","3","4","5","6","7","8"};
        String[] lie={"0","1","2","3","4","5","6","7","8"};
        ArrayList<String> 行=new ArrayList<>(Arrays.asList(hang));
        ArrayList<String> 列=new ArrayList<>(Arrays.asList(lie));
        ArrayList<Integer> 关系=new ArrayList<>(Arrays.asList(guanxi));



        ///////////////////////////////////////////////////////////////////////

        //HashMap<Integer,ArrayList<HashMap<String,Object>>> 图=构建图2(行,列,关系,"6");
        迪杰斯特拉(行,列,关系,"4");
    }




    public static HashMap<Integer,ArrayList<HashMap<String,Object>>> 构建图2(ArrayList<String> 行,ArrayList<String> 列,
                                                                          ArrayList<Integer> 关系,String 顶点){

        HashMap<Integer,ArrayList<HashMap<String,Object>>> 返回值=new HashMap<>();
        int 元素个数=行.size();
        //获取根节点的连接节点
        int 当前层数=1;
        if(当前层数==1){
            ArrayList<HashMap<String,Object>> 每层集合=new ArrayList<>();
            ArrayList<String> 根节点的连接节点=new ArrayList<>();
            HashMap<String,Object> 每层的每个元素=new HashMap<>();
            每层的每个元素.put("元素", 顶点);

            int 关系里的起始索引=行.size()*列.indexOf(顶点);
            int 关系里的结束索引=行.size()*(列.indexOf(顶点)+1)-1;
            for (int j =关系里的起始索引; j <=关系里的结束索引 ; j++) {
                if(关系.get(j)!=0){
                    根节点的连接节点.add(行.get(j%元素个数));
                }
            }
            每层的每个元素.put("儿子",根节点的连接节点);
            每层集合.add(每层的每个元素);
            返回值.put(当前层数,每层集合 );
        }
        //第一层结束,进入下一层


        当前层数++;


        for(;;){

            //上一层是否有儿子？
            HashMap<String,ArrayList<String>> 上一层的儿子集合=new HashMap<>();

            for (HashMap<String,Object> 每层的每个元素 : 返回值.get(当前层数-1)) {
                for (String 每个儿子 : (ArrayList<String>)每层的每个元素.get("儿子")) {

                    //上一层的儿子集合里有没有每个儿子？
                    if(上一层的儿子集合.get(每个儿子)==null){   //没有

                        ArrayList<String> 临时数组=new ArrayList<>();
                        临时数组.add((String)每层的每个元素.get("元素"));
                        上一层的儿子集合.put(每个儿子,临时数组);
                    }else{  //有

                        上一层的儿子集合.get(每个儿子).add((String)每层的每个元素.get("元素"));
                    }


                }
            }



            if(上一层的儿子集合.size()==0){ //上一层没有儿子
                break;
            }else{  //上一层有儿子
                Set<String> 上一层的儿子集合所有键=上一层的儿子集合.keySet();

                ArrayList<HashMap<String,Object>> 每层集合=new ArrayList<>();
                for (String 上一层的每个儿子 : 上一层的儿子集合所有键) {
                    HashMap<String,Object> 每层的每个元素=new HashMap<>();
                    ArrayList<String> 兄弟=new ArrayList<>();
                    ArrayList<String> 儿子=new ArrayList<>();
                    每层的每个元素.put("元素",上一层的每个儿子);
                    每层的每个元素.put("父亲",上一层的儿子集合.get(上一层的每个儿子));
                    int 关系里的起始索引=元素个数*列.indexOf(上一层的每个儿子);
                    int 关系里的结束索引=元素个数*(列.indexOf(上一层的每个儿子)+1)-1;

                    for (int j =关系里的起始索引; j <=关系里的结束索引 ; j++) {

                        if(关系.get(j)!=0){
                            //System.out.println(行.get(j%元素个数));
                            if(上一层的儿子集合.get(上一层的每个儿子).contains(行.get(j%元素个数))){ //是父亲

                            }else if(上一层的儿子集合所有键.contains(行.get(j%元素个数))){  //是兄弟
                                兄弟.add(行.get(j%元素个数));
                            }else{  //是儿子
                                儿子.add(行.get(j%元素个数));
                            }

                        }
                    }
                    每层的每个元素.put("本层所有元素",上一层的儿子集合所有键);
                    每层的每个元素.put("儿子",儿子);
                    每层的每个元素.put("兄弟",兄弟);
                    每层集合.add(每层的每个元素);


                }
                返回值.put(当前层数,每层集合);
                当前层数++;
            }


        }


        return 返回值;
    }


    public static void 深度优先搜索(HashMap<Integer,ArrayList<HashMap<String,Object>>> 图){

        ArrayList<String> 返回值=new ArrayList<>();

        int 当前层数=1;
        String 根节点=(String)图.get(当前层数).get(0).get("元素");
        String 临时变量=根节点;
        返回值.add(临时变量);
        b:for (;;){

            //节点是否有未被遍历过的儿子，且该儿子的父亲列表中的第一个父亲为自己？
            boolean 前进条件1=false;
            ArrayList<String> 该节点的儿子列表=new ArrayList<>();
            d:for (HashMap<String,Object> 每层的每个元素: 图.get(当前层数)) {
                if((String)每层的每个元素.get("元素")==临时变量){
                    该节点的儿子列表=(ArrayList<String>)每层的每个元素.get("儿子");
                    break d;
                }
            }
            //ArrayList<String> 该节点的儿子列表=(ArrayList<String>)图.get(当前层数).get(0).get("儿子");
//            System.out.println("当前节点："+临时变量);
//            System.out.println("当前节点的儿子："+该节点的儿子列表);
            a:for (String 每个儿子: 该节点的儿子列表) {
                if(!返回值.contains(每个儿子)){

                    for (HashMap<String,Object> 每层的每个元素: 图.get(当前层数+1)) {
                        if((String)每层的每个元素.get("元素")==每个儿子&&
                                ((ArrayList<String>)每层的每个元素.get("父亲")).get(0)==临时变量){
                            前进条件1=true;
                            临时变量=每个儿子;
                            break a;
                        }
                    }
                }
            }

            if(前进条件1){  //有
                返回值.add(临时变量);
                当前层数++;
                continue b;
            }else { //没有

                //该节点是否有父亲？
                boolean 前进条件2=false;
                if(当前层数!=1){
                    c:for (HashMap<String,Object> 每层的每个元素: 图.get(当前层数)) {
                        if((String)每层的每个元素.get("元素")==临时变量){
                            前进条件2=true;
                            临时变量=((ArrayList<String>)每层的每个元素.get("父亲")).get(0);
                            break c;
                        }
                    }
                }


                if(前进条件2){   //有
                    当前层数--;
                    continue b;
                }else{  //没有
                    break b;
                }
            }
        }
        System.out.println(返回值);
    }

    public static void 广度优先搜索(HashMap<Integer,ArrayList<HashMap<String,Object>>> 图){
        ArrayList<String> 返回值=new ArrayList<>();
        for (int i = 1; i <=图.size() ; i++) {
            if(i==1){
                返回值.add((String)图.get(i).get(0).get("元素"));
            }else{
                Set<String> 临时数组=new HashSet<>();
                临时数组=(Set<String>)图.get(i).get(0).get("本层所有元素");
                for (String str: 临时数组) {
                    返回值.add(str);
                }
            }
        }
        System.out.println(返回值);
    }

    public static HashMap<String,Integer> 求和某个节点连接的所有节点(ArrayList<String> 行,ArrayList<String> 列,
                                     ArrayList<Integer> 关系,String 节点){
        int 元素个数=行.size();
        HashMap<String,Integer> 返回值=new HashMap<>();
        int 关系里的起始索引=行.size()*列.indexOf(节点);
        int 关系里的结束索引=行.size()*(列.indexOf(节点)+1)-1;
        for (int j =关系里的起始索引; j <=关系里的结束索引 ; j++) {
            if(关系.get(j)!=0){
                返回值.put(行.get(j%元素个数),关系.get(j));
            }
        }
        return 返回值;
    }

    public static void 普里姆(ArrayList<String> 行,ArrayList<String> 列,
                           ArrayList<Integer> 关系,String 起始节点){

        HashMap<String,Integer> 返回值=new HashMap<>();
        ArrayList<String> 已使用的节点=new ArrayList<>();

        已使用的节点.add(起始节点);
        for(;;){
            String 哪个已使用节点=null;
            String 临时节点=null;
            int 目前最小权值=0;
            for (String 每个节点:已使用的节点) {
                HashMap<String,Integer> 和某个节点连接的所有节点=求和某个节点连接的所有节点(行, 列, 关系, 每个节点);
                Set<String> 所有节点=和某个节点连接的所有节点.keySet();
                for (String str: 所有节点) {
                    if(!已使用的节点.contains(str)){
                        if(目前最小权值==0){
                            目前最小权值=和某个节点连接的所有节点.get(str);
                            临时节点=str;
                            哪个已使用节点=每个节点;
                        }else{
                            if(目前最小权值>和某个节点连接的所有节点.get(str)){
                                目前最小权值=和某个节点连接的所有节点.get(str);
                                临时节点=str;
                                哪个已使用节点=每个节点;
                            }

                        }
                    }



                }
            }
            已使用的节点.add(临时节点);
            返回值.put(哪个已使用节点+"-"+临时节点,目前最小权值);
            if(已使用的节点.size()==行.size()){
                break;
            }
        }
        System.out.println(返回值);
    }

    public static void 克鲁斯卡尔(ArrayList<String> 行,ArrayList<String> 列,
                             ArrayList<Integer> 关系,String 起始节点){
        
    }

    public static void 迪杰斯特拉(ArrayList<String> 行,ArrayList<String> 列,
                             ArrayList<Integer> 关系,String 起始节点){


        LinkedList<String> 未遍历=new LinkedList<>();
        HashMap<String,Integer> 最短路径权值=new HashMap<>();
        最短路径权值.put(起始节点,0);
        HashMap<String,ArrayList<String>> 最短路径路程=new HashMap<>();
        ArrayList<String> 初始最短路径路程值=new ArrayList<>();
        初始最短路径路程值.add(起始节点);
        最短路径路程.put(起始节点,初始最短路径路程值);
        LinkedList<String> 临时数组外部=new LinkedList<>();
        临时数组外部.add(起始节点);

        //初始化未遍历对象
        for (String str: 行) {

                未遍历.add(str);

        }



        while(未遍历.size()!=0){
            System.out.println("临时数组外部"+临时数组外部);
            ArrayList<String> 临时数组内部=new ArrayList<>();

            //临时数组内部需要排序

            for (String str: 临时数组外部) {

                未遍历.remove(str);

                //111111111111111111111
                HashMap<String,Integer> 关系表=求和某个节点连接的所有节点(行,列,关系,str);
                Set<String> 关系表键集合=关系表.keySet();
                System.out.println("str"+str);
                System.out.println("关系表键集合"+关系表键集合);

                //22222222222222222222
                Set<String> 最短路径权值键集合=最短路径权值.keySet();
                for (String str2: 关系表键集合) {
                    System.out.println("aaaaa:"+str2);
                    System.out.println(最短路径权值键集合);
                    //3333333333333333
                    if(最短路径权值键集合.contains(str2)){

                        //55555555555555555555555555555
                        int 上面的值=最短路径权值.get(str)+关系表.get(str2);
                        int 下面的值=最短路径权值.get(str2);

                        //777777777777777777777
                        if(上面的值>下面的值){

                        }
                        //8888888888888888888888
                        else{
                            最短路径权值.put(str2,最短路径权值.get(str)+关系表.get(str2));
                            ArrayList<String> linshi=new ArrayList<>();
                            for (String str3:最短路径路程.get(str)) {
                                linshi.add(str3);
                            }
                            linshi.add(str2);
                            最短路径路程.put(str2,linshi);
                        }

                    }
                    //4444444444444444
                    else{

                        //66666666666666666
                        最短路径权值.put(str2,最短路径权值.get(str)+关系表.get(str2));
                        ArrayList<String> linshi=new ArrayList<>();
                        for (String str3:最短路径路程.get(str)) {
                            linshi.add(str3);
                        }
                        linshi.add(str2);
                        最短路径路程.put(str2,linshi);
                        临时数组内部.add(str2);
                    }
                }

            }


                临时数组外部.clear();
                for (String str4:临时数组内部) {
                    临时数组外部.add(str4);
                }



        }
        System.out.println(最短路径权值);
        System.out.println(最短路径路程);

    }

}

5 排序

5.1 插入排序

5.1.1 直接插入排序

O( (N+1)*(N/2))

5.1.2 二分法插入排序

O(nlgn)

5.1.3 希尔排序

不稳定的排序

5.2 选择排序

5.2.1 简单选择排序

O( (N+1)*(N/2))

5.2.2 堆排序

大堆：二叉树里父节点比左右孩子节点都大
小堆：二叉树里父节点比左右孩子节点都小
O(nlgn)