[数据结构与算法]【记录数据结构复习day3(java)】

续未完的基数排序

基数排序(桶排序

	//基数排序(桶排序)
    public static void barrelSort(int[] arr) {
        int n = arr.length;
        //创建10个桶，每个桶的维数都是数组的长度
        int[][] barrelEle = new int[10][n];
        //创建一个给每个桶计数的一维数组
        int[] barrelCount = new int[10];
        //拿到数组中最大的数
        int max = arr[0];
        for (int i = 1; i < n; i++) {
            if(arr[i] > max) max = arr[i];
        }
        int len = (max + "").length(); // 为需要进行桶排序的轮数
        for (int i = 0, k = 1; i < len; i++, k *= 10) {
            for (int j = 0; j < n; j++) { // 遍历数组中的每一个元素，取出其中的个位
                int bit = arr[j] / k % 10; // 根据这个bit的数放到对应的桶中
                barrelEle[bit][barrelCount[bit] ++] = arr[j];
            }
            //每一轮结束后需要取出桶中相应的数放入原数组中
            int index = 0;
            for (int j = 0; j < 10; j++) {
                for (int l = 0; l < barrelCount[j]; l++) {
                    arr[index ++] = barrelEle[j][l];
                }
                barrelCount[j] = 0; // 将桶的计数置为0，进行下一轮桶排序
            }
        }
    }

二分查找(递归和循环

另外还有插值查找和斐波那契查找，原理即是更改了mid的取法

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = new int[]{1,6,26,34,67,99,156,246,250,298};
        binarySearch(arr, 15);
    }
    public static void binarySearch(int[] arr, int value) {
//        int res = binarySearch(arr, value, 0, arr.length - 1);
        int res = binarySearch1(arr, value);
        System.out.printf("找到了 %d 这个数，在该数组中下标为 %d", value, res);
    }
    public static int binarySearch(int[] arr, int value, int left,int right) { // 递归实现
        if(left > right) throw new RuntimeException("在该数组中没有找到该数~~");
        int mid = (left + right) / 2;
        if(arr[mid] > value) {
            return binarySearch(arr, value, left, mid - 1);
        }
        else if(arr[mid] < value) {
            return binarySearch(arr, value, mid + 1, right);
        }
        else return mid;
    }
    public static int binarySearch1(int[] arr, int value) {
        int left = 0, right = arr.length - 1;
        int res = -1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(arr[mid] < value) left = mid + 1;
            else if(arr[mid] > value) right = mid - 1;
            else {
                res = mid;
                break;
            }
        }
        if(res == -1) throw new RuntimeException("在该数组中没有找到该数~~");
        return res;
    }
}

模拟哈希表

public class HashTabDemo {
    public static void main(String[] args) {
        HashTab hashTab = new HashTab(9);
        Scanner scanner = new Scanner(System.in);
        String key = "";
        boolean loop = true;
        while (loop) {
            System.out.println("add:(添加节点");
            System.out.println("show:(显示哈希表");
            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();
                    System.out.println("请输入该员工的age:");
                    int age = scanner.nextInt();
                    Node node = new Node(id, name, age);
                    hashTab.addNode(node);
                    break;
                case "show":
                    hashTab.showTab();
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
    }
}
class HashTab {
    private NodeList[] nodeLists;
    private int size;

    public HashTab(int size) {
        this.size = size;
        this.nodeLists = new NodeList[size];
        for (int i = 0; i < size; i++) {
            nodeLists[i] = new NodeList();
        }
    }
    public void addNode(Node node) {
        nodeLists[getLoc(node.getId())].addNode(node);
    }
    public int getLoc(int id) {
        return id % size - 1;
    }

    public void showTab() {
        for (int i = 0; i < size; i++) {
            if(nodeLists[i].getHead() == null) {
                System.out.printf("第 %d 条链表内容为空~~", i + 1);
                System.out.println();
                continue;
            }
            nodeLists[i].showList();
        }
    }
}
@Data
class NodeList {
    private Node head;
    public NodeList() {
        this.head = null;
    }
    public void addNode(Node node) { // 按照年龄大小排序
        if(head == null) {
            head = node;
            return;
        }
        //如果插入在头节点之前
        if(node.getAge() < head.getAge()) {
            node.setNext(head);
            head = node;
            return;
        }
        Node cur = head;
        while(cur.getNext() != null && cur.getNext().getAge() < node.getAge()) {
            cur = cur.getNext();
        }
        Node next = cur.getNext();
        cur.setNext(node);
        node.setNext(next);
    }

    public void showList() {
        if(head == null) {
            System.out.println("此链表为空，无法遍历~~");
            return;
        }
        Node cur = head;
        while(cur != null) {
            System.out.print(cur + "-->");
            cur = cur.getNext();
        }
        System.out.println();
    }
}
@Data
class Node {
    private int id;
    private String name;
    private int age;
    private Node next;
    public Node(int id, String name, int age) {
        this.id = id;
        this.name = name;
        this.age = age;
    }
    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

数组用二叉树的前序中序后序遍历再输出

public class BinaryTreeArrayDemo {
    public static void main(String[] args) {
        int[] arr = new int[]{8,9,4,5,2,6,0,7};
//        int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
        BinaryTreeArray binaryTreeArray = new BinaryTreeArray(arr);
        binaryTreeArray.preList();
    }
}
class BinaryTreeArray {
    private int[] arr;
    public BinaryTreeArray(int[] arr) {
        this.arr = arr;
    }
    public void preList() {
        preList(0);
    }
    public void infixList() {
        infixList(0);
    }
    public void suffixList() {
        suffixList(0);
    }
    public void preList(int index) {
        if(arr == null || arr.length == 0) return;
        System.out.print(arr[index] + " ");
        if((index * 2 + 1) < arr.length) this.preList(index * 2 + 1);
        if((index * 2 + 2) < arr.length) this.preList(index * 2 + 2);
    }
    public void infixList(int index) {
        if(arr == null || arr.length == 0) return;
        if((index * 2 + 1) < arr.length) this.infixList(index * 2 + 1);
        System.out.print(arr[index] + " ");
        if((index * 2 + 2) < arr.length) this.infixList(index * 2 + 2);
    }
    public void suffixList(int index) {
        if(arr == null || arr.length == 0) return;
        if((index * 2 + 1) < arr.length) this.suffixList(index * 2 + 1);
        if((index * 2 + 2) < arr.length) this.suffixList(index * 2 + 2);
        System.out.print(arr[index] + " ");
    }
}

二叉排序树的各种操作

1. 添加节点
2. 前序中序后序遍历
3. 前序中序后序查找
4. 前序中序后序的线索化
前序中序后序的各种操作区别都不大，琢磨一下即可写出

import lombok.Data;

@SuppressWarnings({"all"})
public class BinaryTreeDemo {
    public static void main(String[] args) {
        int[] arr = new int[]{8, 10, 5, 7, 2, 4, 9};
//        int[] arr = produceRandomArr(15);
        BinarySortTree bst = initialTree(arr);
//        bst.suffixList();
        bst.suffixThreaded();
        System.out.println(123);
    }
    public static int[] produceRandomArr(int n) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = (int)(Math.random() * n * 10);
        }
        return arr;
    }
    public static BinarySortTree initialTree(int[] arr) {
        BinarySortTree bst = new BinarySortTree();
        SNode[] sNodes = createSNodes(arr);
        for (int i = 0; i < arr.length; i++) {
            bst.addSNode(sNodes[i]);
        }
        return bst;
    }
    public static SNode[] createSNodes(int[] arr) {
        SNode[] sNodes = new SNode[arr.length];
        for (int i = 0; i < arr.length; i++) {
            sNodes[i] = new SNode(arr[i]);
        }
        return sNodes;
    }
}
@Data
class BinarySortTree {
    private SNode root;
    private SNode pre;
    public void addSNode(SNode sNode) {
        if(root == null) {
            root = sNode;
            return;
        }
        this.root.addSNode(sNode);
    }

    public void preList() {
        if(root == null) {
            System.out.println("该二叉排序树为空~~无法遍历");
            return;
        }
        this.root.preList();
    }
    public void infixList() {
        if(root == null) {
            System.out.println("该二叉排序树为空~~无法遍历");
            return;
        }
        this.root.infixList();
    }
    public void suffixList() {
        if(root == null) {
            System.out.println("该二叉排序树为空~~无法遍历");
            return;
        }
        this.root.suffixList();
    }

    public SNode preSearch(int val) {
        if(root == null) throw new RuntimeException("二叉树为空，没有可查找的节点~~");
        return this.root.preSearch(val);
    }
    public SNode infixSearch(int val) {
        if(root == null) throw new RuntimeException("二叉树为空，没有可查找的节点~~");
        return this.root.infixSearch(val);
    }
    public SNode postSearch(int val) {
        if(root == null) throw new RuntimeException("二叉树为空，没有可查找的节点~~");
        return this.root.postSearch(val);
    }

    //前序线索化二 叉排序树
    public void preThreaded() {
        if(this.root == null) return;
        preThreaded(this.root);
    }
    public void preThreaded(SNode sNode) { // 用到了双指针
        if(sNode == null) return;
        //先设置左边的线索化
        if(sNode.getLeft() == null) {
            sNode.setLeft(pre);
            sNode.setLTag(1);
        }
        if(pre != null && pre.getRight() == null) {
            pre.setRight(sNode);
            pre.setRTag(1);
        }
        pre = sNode;
        if(sNode.getLTag() == 0) preThreaded(sNode.getLeft());
        if(sNode.getRTag() == 0) preThreaded(sNode.getRight());
    }
    //中序线索化二 叉排序树
    public void infixThreaded() {
        if(this.root == null) return;
        infixThreaded(this.root);
    }
    public void infixThreaded(SNode sNode) {
        if(sNode == null) return;
        if(sNode.getLTag() == 0) infixThreaded(sNode.getLeft());
        //先设置左边的线索化
        if(sNode.getLeft() == null) {
            sNode.setLeft(pre);
            sNode.setLTag(1);
        }
        if(pre != null && pre.getRight() == null) {
            pre.setRight(sNode);
            pre.setRTag(1);
        }
        pre = sNode;
        if(sNode.getRTag() == 0) infixThreaded(sNode.getRight());
    }
    public void suffixThreaded() {
        if(this.root == null) return;
        suffixThreaded(this.root);
    }
    public void suffixThreaded(SNode sNode) {
        if(sNode == null) return;
        if(sNode.getLTag() == 0) suffixThreaded(sNode.getLeft());
        if(sNode.getRTag() == 0) suffixThreaded(sNode.getRight());
        //先设置左边的线索化
        if(sNode.getLeft() == null) {
            sNode.setLeft(pre);
            sNode.setLTag(1);
        }
        if(pre != null && pre.getRight() == null) {
            pre.setRight(sNode);
            pre.setRTag(1);
        }
        pre = sNode;
    }
    //前序线索化后的遍历
    public void preThreadedList() {
        if(this.root == null) return;
        preThreadedList(this.root);
    }
    public void preThreadedList(SNode sNode) {
        if(sNode == null) return;
        System.out.println(sNode);
        if(sNode.getLTag() == 0) preThreadedList(sNode.getLeft());
        if(sNode.getRTag() == 0) preThreadedList(sNode.getRight());
    }
    public void infixThreadedList() {
        if(this.root == null) return;
        infixThreadedList(this.root);
    }
    public void infixThreadedList(SNode sNode) {
        if(sNode == null) return;
        if(sNode.getLTag() == 0) infixThreadedList(sNode.getLeft());
        System.out.println(sNode);
        if(sNode.getRTag() == 0) infixThreadedList(sNode.getRight());
    }
    public void suffixThreadedList() {
        if(this.root == null) return;
        suffixThreadedList(this.root);
    }
    public void suffixThreadedList(SNode sNode) {
        if(sNode == null) return;
        if(sNode.getLTag() == 0) suffixThreadedList(sNode.getLeft());
        if(sNode.getRTag() == 0) suffixThreadedList(sNode.getRight());
        System.out.println(sNode);
    }
}
@Data
class SNode {
    private int val;
    private SNode left;
    private SNode right;
    private int lTag;
    private int rTag;
    public SNode(int val) {
        this.val = val;
        this.lTag = 0;
        this.rTag = 0;
    }
    public void addSNode(SNode sNode) {
        if(sNode.getVal() < this.val) {
            if(this.getLeft() != null) this.left.addSNode(sNode);
            else this.left = sNode;
        }
        else {
            if(this.getRight() != null) this.right.addSNode(sNode);
            else this.right = sNode;
        }
    }
    //前序中序后序查找
    public SNode preSearch(int val) {
        if(this.val == val) return this;
        SNode resNode = null;
//        System.out.println(this);
        if(this.left != null) resNode = this.left.preSearch(val);
        if(resNode == null && this.right != null) {
            resNode = this.right.preSearch(val);
        }
        return resNode;
    }
    public SNode infixSearch(int val) {
        SNode resNode = null;
        if(this.left != null) resNode = this.left.infixSearch(val);
        if(resNode != null) return resNode;
//        System.out.println(this);
        if(this.val == val) return this;
        if(this.right != null) resNode = this.right.infixSearch(val);
        return resNode;
    }
    public SNode postSearch(int val) {
        SNode resNode = null;
        if(this.left != null) resNode = this.left.postSearch(val);
        if(resNode != null) return resNode;
        if(this.right != null) resNode = this.right.postSearch(val);
        if(resNode != null) return resNode;
        System.out.println(this);
        if(this.val == val) return this;
        return null;
    }
    //前序中序后序遍历
    public void preList() {
        System.out.println(this);
        if(this.left != null) this.getLeft().preList();
        if(this.right != null) this.getRight().preList();
    }
    public void infixList() {
        if(this.left != null) this.getLeft().infixList();
        System.out.println(this);
        if(this.right != null) this.getRight().infixList();
    }
    public void suffixList() {
        if(this.left != null) this.getLeft().suffixList();
        if(this.right != null) this.getRight().suffixList();
        System.out.println(this);
    }
    @Override
    public String toString() {
        return "SNode{" +
                "val=" + val +
                '}';
    }
}

等晚上来完成线索化二叉树后的遍历操作，有时间再完成删除节点的操作(叶子/非叶子)

3-16更新，已增加前序中序后序线索化的遍历操作，在BinarySortTree这个类中~~