无敌是多么寂寞

无敌是多么寂寞

兄弟们仁至义尽了，直接把实训的东西放网上了

 二叉树的遍历

import ds.queue.linkQueue;
import ds.tree.linkBiTree;
import ds.tree.linkNode;

import java.util.Scanner;

public class Main3 {
    public static void main(String[] args) {
        linkBiTree tree =new linkBiTree();
        linkBiTree.create(tree);
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String[] s1 = s.split(" ");
        for (String n : s1) {
            bianli(Integer.parseInt(n),tree);
        }
    }
    static  void bianli(int i,linkBiTree tree){
        switch (i){
            case 1:
                PreOrder(tree.root);
                System.out.println();
                break;
            case 2:
                InOrder(tree.root);
                System.out.println();
                break;
            case 3:
                PostOrder(tree.root);
                System.out.println();
                break;
            case 4:
                levelOrder(tree.root);
                System.out.println();
                break;
        }
    }
    static void PreOrder(linkNode root){ //先序遍历
        if(root == null) return ;
        System.out.print(root.data + " ");
        PreOrder(root.lchild);
        PreOrder(root.rchild);
    }

    static void InOrder(linkNode root){ //中序遍历
        if(root == null) return ;
        InOrder(root.lchild);
        System.out.print(root.data + " ");
        InOrder(root.rchild);

    }

    static void PostOrder(linkNode root){ //后序遍历
        if(root == null) return ;
        PostOrder(root.lchild);
        PostOrder(root.rchild);
        System.out.print(root.data + " ");
    }

    static void levelOrder(linkNode root){//层次遍历
        if(root == null) return ;
        linkQueue queue = new linkQueue();
        linkNode p = root;
        queue.enqueue(p);
        while(!queue.isEmpty()){
            p = queue.dequeue();
            System.out.print(p.data + " ");
            if(p.lchild != null){
                queue.enqueue(p.lchild);
            }
            if(p.rchild != null){
                queue.enqueue(p.rchild);
            }
        }
    }
}

哈夫曼树的实现

import java.util.Scanner;


public class Main6 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        HFMTreeNode[] hfmTree = new HFMTreeNode[2*n-1];
        for(int i = 0 ; i < hfmTree.length ; i++){
            hfmTree[i] = new HFMTreeNode();
        }

        for(int i =0 ; i < n; i++){
            hfmTree[i].weight = in.nextInt();
        }
        in.nextLine();
        String s = in.nextLine();
        char[] chars = s.toCharArray();
        HFMTool.create_HFMTree(hfmTree,n);

        HFMCodeNode[] hfmCode = new HFMCodeNode[n];
        for(int i = 0 ; i < hfmCode.length ; i++){
            hfmCode[i] = new HFMCodeNode(n);
        }

        HFMTool.HFMCode(hfmTree,hfmCode);

        for(int i = 0 ; i < chars.length ; i++){
            System.out.print(chars[i]+":");
            for(int j = hfmCode[i].start ; j < n ; j++){
                if(hfmCode[i].bit[j] == 0 ){
                    System.out.print("l ");
                } else {
                    System.out.print("r ");
                }
            }
            System.out.println();
        }

        in.close();
    }
}

class HFMTool {
    public static void create_HFMTree (HFMTreeNode[] hfmTree,int n){
        int min1,min2;
        int m1,m2;
        for(int i = 0 ; i < n-1 ; i++){
            min1 = min2 = Integer.MAX_VALUE;
            m1 = m2 = 0;
            for(int j = 0 ; j < n + i ; j++){
                if(hfmTree[j].parent == -1 && hfmTree[j].weight < min1){
                    min2 = min1;
                    m2 = m1;
                    min1 = hfmTree[j].weight;
                    m1 = j;
                } else if(hfmTree[j].parent == -1 && hfmTree[j].weight < min2) {
                    m2 = j;
                    min2 = hfmTree[j].weight;
                }
            }
            hfmTree[n+i].weight = min1 + min2;
            hfmTree[n+i].lchild = m1;
            hfmTree[n+i].rchild = m2;
            hfmTree[m1].parent = hfmTree[m2].parent = n + i;
        }
    }

    public static void HFMCode(HFMTreeNode[] hfmTree , HFMCodeNode[] code){
        for(int i = 0 ; i < code.length ; i++){
            int c = i;
            int p = hfmTree[i].parent;
            while(p != -1){
                if(hfmTree[p].lchild == c){
                    code[i].bit[--code[i].start] = 0;
                } else {
                    code[i].bit[--code[i].start] = 1;
                }
                c = p;
                p = hfmTree[p].parent;
            }
        }
    }
}

class HFMTreeNode {
    int parent,lchild,rchild,weight;
    public HFMTreeNode(){
        weight = 0;
        parent = lchild = rchild = -1;
    }
}

class HFMCodeNode {
    int start;
    int[] bit ;
    public HFMCodeNode(int n){
        start = n ;
        bit = new int[start];
    }
}

图的存储实现

import ds.graphic.ALGraph;
import ds.graphic.EdgeNode;
import ds.graphic.MGraph;
import ds.graphic.VexNode;

public class Main1 {
    public static void main(String[] args) {
        MGraph mg=new MGraph();//创建邻接矩阵对象
        int vexnum = mg.vexnum;//获得顶点数目
        int edgenum = mg.edgenum;//获得边数目
        boolean isdirection =mg.isdirection;//是否为有向图
        ALGraph alg=new ALGraph(vexnum,edgenum,isdirection);//创建邻接表图对象
        //给顶点结点数组赋值
        for(int i = 0 ; i < vexnum ; i++){
            alg.vextex[i]=new VexNode(mg.vexs[i]);
        }
        EdgeNode p=null;
        //建立邻接表边链表
        for(int i=0;i0&&w<1000){
                    if(alg.vextex[i].firstedge == null){
                        alg.vextex[i].firstedge = new EdgeNode(j,w);
                    } else {
                        p = alg.vextex[i].firstedge;
                        while(p.next != null){
                            p = p.next;
                        }
                        p.next = new EdgeNode(j,w);
                    }
                }
            }
        }
        //输出邻接表图存储示例图
        alg.pntALGraph();
    }

}

图两点最短距离

import ds.graphic.MGraph;

import java.util.Scanner;
import java.util.Stack;

public class Main2 {
    private static int[] path;
    private static int[] distance;
    private static boolean[] selected;
    private static int n , m ,size;

    public static void main(String[] args) {
        //获取jar包已经定义好的图对象
        MGraph mg = new MGraph();
        size = mg.vexnum;
        path = new int[size];
        distance = new int[size];
        selected = new boolean[size];
        Scanner in = new Scanner(System.in);
        n = in.nextInt();       //源节点
        m = in.nextInt();       //目的节点
        //进行初始化同时更新源节点的临近节点
        for(int i = 0 ; i < size ; i++){
            path[i] = n;
            distance[i] = mg.edges[n][i];
        }
        //将源节点划入最短路径s
        selected[n] = true;
        path[n] = -1;
        distance[n] = 0;

        mpath(mg);

        System.out.print(mg.vexs[n].vname+"-->"+mg.vexs[m].vname + " distance " + distance[m] + " path:");
        Stack st = new Stack();
        int temp = m;
        while(temp != -1){
            st.push(temp);
            temp = path[temp];
        }
        if (!st.empty()) {
            System.out.print(mg.vexs[st.pop()].vname);
        }
        while(!st.empty()){
            System.out.print("-->"+mg.vexs[st.pop()].vname);
        }
    }

    public static void mpath(MGraph mg){
        while(true){
            int index = -1;
            int min = mg.MAXSIZE;
            //寻找距离出发点距离最短的点
            for(int i = 0 ; i < size ; i++){
                if(!selected[i] && distance[i] < min){
                    min = distance[i];
                    index = i;
                }
            }
            if(index == -1) break;      //未找到距离出发点距离最短的点，说明所有点都已经划到最短路径中了
            selected[index] = true;     //将寻找到的点选中
            //更新临近节点
            for(int i = 0 ; i < size ; i++){
                if(mg.edges[index][i] != mg.MAXSIZE  && min + mg.edges[index][i] < distance[i]){
                    distance[i] = min + mg.edges[index][i];
                    path[i] = index;
                }
            }
        }
    }

}

快速排序

import java.util.Scanner;

public class Main4 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0 ; i  < n ; i++){
            arr[i] = in.nextInt();
        }
        quickSort(arr);
        System.out.println();
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }
    public static void quickSort(int[] data){
        quickSort(data,0, data.length-1);
    }
    public static void quickSort(int[] data,int low,int high){
        int i = low;
        int j = high;
        int pivot = data[low];
        int temp;
        while(i < j){
            while(i < j && data[j] >= pivot){
                j--;
            }
            while(i < j && data[i] <= pivot){
                i++;
            }
            if(i < j){
                temp = data[j];
                data[j] = data[i];
                data[i] = temp;
            }
        }
        System.out.print(i+" ");
        if(data[i] < data[low]){
            temp = data[i];
            data[i] = data[low];
            data[low] = temp;
        }

        if(i - low > 1)
            quickSort(data,low,i-1);
        if(high - j > 1)
            quickSort(data,j+1, high);
    }

 折半查找

import java.util.Scanner;

public class Main5 {
    public static void main(String[] args) {
        Scanner in =new Scanner(System.in);
        int n = in.nextInt();
        int[] data = new int[n];
        for(int i = 0 ; i < n ; i++){
            data[i] = in.nextInt();
        }
        int m = in.nextInt();
        int search = search(data, m);
        System.out.println();
        if(search != -1){
            System.out.println(search+1);
        } else{
            System.out.println("NO");
        }
    }
    public static int search(int[] data,int m){
        int index = -1;
        int start = 0;
        int end = data.length -1;       //注意这里必须要减一，否则通不过
        while(start <= end){
            int mid = (start+end)/2;
            System.out.print(data[mid]+" ");
            if(data[mid] == m){
                index = mid;
                break;
            } else if(data[mid] >= m){
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return index;
    }
}