数据结构与算法学习笔记

文章目录

文章介绍

我将会在这篇博客中记录所有的数据结构与算法的所有学习内容

稀疏数组学习

稀疏数组就是使用n*3二维数组去更加简洁的保存数据

// An highlighted block
public class SparseArray {
    public static void main() {
        int[][] mapArr = new int[11][11];
        mapArr[0][1] = 1;
        mapArr[2][3] = 2;
        int y = mapArr.length;
        int x = mapArr[1].length;
        int sum = 0;
        for (int[] ints : mapArr) {
            for (int value : ints) {
                if (value > 0) {
                    sum++;
                }
            }
        }
        System.out.println("============================");
        System.out.println(Arrays.deepToString(mapArr));
        int[][] sparseArr = new int[sum + 1][3];
        sparseArr[0][0] = y;
        sparseArr[0][1] = x;
        sparseArr[0][2] = sum;
        int count = 1;
        for (int i = 0; i < y; i++) {
            for (int i1 = 0; i1 < x; i1++) {
                if (mapArr[i][i1] > 0) {
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = i1;
                    sparseArr[count][2] = mapArr[i][i1];
                    count++;
                }
            }
        }
        System.out.println(Arrays.deepToString(sparseArr));
    }

}

环形列队学习

适用场景排队

	public class CircleArrayQueue {
    private int maxSize;//最大值
    private int front;//第一个数位置
    private int rear;//最后一个位置
    private int[] arr;//数组

    public CircleArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        arr=new int[maxSize];
    }
    public boolean isFull(){

            return (rear+1)%maxSize==front;

    }
    public boolean isEmpty(){
        return front==rear;
    }
    public boolean addQueue(int value){
        if (isFull()){
            return false;
        }else {
            arr[rear]=value;
            rear=(rear+1)%maxSize;
            return true;
        }
    }
    //front模拟>> 上移类似于消费,相当于arr[front]已被移除
    public int getQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列为空");
        }
        int value = arr[front];
        front=(front+1)%maxSize;
        return value;
    }
    public void showQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列为空");
        }
        for (int i = front; i < front+size(); i++) {
            System.out.println(i%maxSize+"AA"+arr[i%maxSize]);
        }
    }
    public int size(){
        //rear=1 front=2 maxsize =4
        return (rear+maxSize-front)%maxSize;
    }
    public int headQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列为空");
        }else {
            return arr[front];
        }
    }
}

自己画的图帮助自己记忆

单链表的使用与创建

public class MyLinkList<Type> {
    //用于代理,虚拟链表
    private MyNode temp;
    private MyNode head = new MyNode(null);
    //添加到尾部
    public void add(Type o) {
        temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = new MyNode(o);
    }
    //定义一个按照tostring长度排序的添加规则方法
    public void addOfOrder(Type o) {
        temp=head;
        while (true){
            if (temp.next==null){
                break;
            }
            if (temp.next.o.toString().length()>o.toString().length()){
                break;
            }
            temp=temp.next;
        }
        MyNode myNode = new MyNode(o);
        myNode.next=temp.next;
        temp.next=myNode;
    }
    //修改没考虑重新排序
    public boolean update(Type o,Type o2){
        temp=head;
        while (true){
            if (temp.next==null){
                return false;
            }
            if (temp.next.o==o){
                temp.next.o=o2;
                return true;
            }
            temp=temp.next;
        }
    }
    //删除
    public boolean delete(Type o){
        temp=head;
        while (true){
            if (temp.next==null){
                return false;
            }
            if (temp.next.o==o){
                temp.next=temp.next.next;
                return true;
            }
            temp=temp.next;
        }
    }
    //获得第index个节点
    public MyNode getNode(int index){
        if (head.next==null||!(getLength()>index)){
            return null;
        }
        temp=head.next;
        for (int i = 0; i < index; i++) {
            temp=temp.next;
        }
        return temp;
    }
    //链表反转
    public boolean reverseSelf(){
        //用于存储反转过程的节点
        MyNode reverseTemp=new MyNode(null);
        //用于记住下一个节点
        MyNode reverseTempTemp;
        if (getLength()<2){
            return false;
        }
        temp=head.next;
        while (true){
            if (temp.next==null){
                break;
            }
            /**
             * // 举例子:
             *   temp=1->2->3->null
             *   reverseTemp.next=null
             *   第一步 reverseTempTemp=2->3->null
             *   第二步 temp=1->null
             *   第三步 reverseTemp.next=1->null
             *   第四步 temp=2->3->null
             *   重复
             */
            //保存temp下一个节点
            reverseTempTemp=temp.next;
            //当前节点的下一个变为reverseTemp的下一个,也就是说把原来已经反转或者null赋值给temp的下一个节点
            // (上一步就是这不的伏笔,不然后面的节点找不到了)
            temp.next=reverseTemp.next;
            reverseTemp.next=temp;
            temp=reverseTempTemp;
        }
        head.next=reverseTemp.next;
        return true;

    }
    //使用栈反向打印
    public void reversePrint(){
        if (head.next==null){
            return;
        }
        Stack<MyNode> myNodes = new Stack<>();
        temp=head.next;
        while (temp!= null) {
            myNodes.add(temp);
            temp=temp.next;
        }
        while (!myNodes.empty()) {
            System.out.println(myNodes.pop());
        }
    }
    //获得长度
    public int getLength(){
        int length=0;
        temp=head;
        while (temp.next != null) {
            length++;
            temp=temp.next;
        }
        return length;
    }
    //显示
    public void showList() {
        if (head.next == null) {
            return;
        }
        temp = head.next;
        while (true) {
            System.out.println(temp);
            temp = temp.next;
            if (temp == null) {
                break;
            }
        }
    }

    private class MyNode {
        public Object o;

        public MyNode(Object o) {
            this.o = o;
        }

        public MyNode next;

        @Override
        public String toString() {
            return "MyNode{" +
                    "o=" + o +
                    '}';
        }
    }
}

public static void main(String[] args) {

        MyLinkList<String> myLinkList=new MyLinkList<String>();
        myLinkList.addOfOrder("AAAA1");
        myLinkList.addOfOrder("AAAA2a");
        myLinkList.addOfOrder("AAAA3");
        myLinkList.addOfOrder("AAAA4");
        myLinkList.showList();
        System.out.println("=======测试更新删除=======");
        myLinkList.update("AAAA1","啊啊啊啊啊啊啊啊");
        myLinkList.delete("AAAA4");
        myLinkList.showList();
        System.out.println("=========测试长度&&获得节点========");
        System.out.println(myLinkList.getLength());
        System.out.println(myLinkList.getNode(4));
        System.out.println("========反转测试=========");
        System.out.println(myLinkList.reverseSelf());
        myLinkList.showList();
        System.out.println("========使用stack反打印测试=========");
        myLinkList.reversePrint();

    }

打印结果

MyNode{o=AAAA1}
MyNode{o=AAAA3}
MyNode{o=AAAA4}
MyNode{o=AAAA2a}
测试更新删除
MyNode{o=啊啊啊啊啊啊啊啊}
MyNode{o=AAAA3}
MyNode{o=AAAA2a}
测试长度&&获得节点
3
null
反转测试
true
MyNode{o=AAAA3}
MyNode{o=啊啊啊啊啊啊啊啊}
使用stack反打印测试
MyNode{o=啊啊啊啊啊啊啊啊}
MyNode{o=AAAA3}

双向链表实现

public class MyDoubleLinkList<Type> {
    //用于代理,虚拟链表
    private MyNode temp;
    private MyNode head = new MyNode(null);
    //添加到尾部
    public void add(Type o) {
        temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = new MyNode(o);
        temp.next.pre=temp;
    }

    //修改没考虑重新排序
    public boolean update(Type o,Type o2){
        temp=head;
        while (true){
            if (temp.next==null){
                return false;
            }
            if (temp.next.o==o){
                temp.next.o=o2;
                return true;
            }
            temp=temp.next;
        }
    }
    //删除
    public boolean delete(Type o){
        temp=head.next;
        while (true){
            if (temp==null){
                return false;
            }
            if (temp.o==o){
                temp.pre.next=temp.next;
                if (temp.next!=null){
                    temp.next.pre=temp.pre;
                }
                return true;
            }
            temp=temp.next;
        }
    }
    //获得第index个节点
    public MyNode getNode(int index){
        if (head.next==null||!(getLength()>index)){
            return null;
        }
        temp=head.next;
        for (int i = 0; i < index; i++) {
            temp=temp.next;
        }
        return temp;
    }

    //获得长度
    public int getLength(){
        int length=0;
        temp=head;
        while (temp.next != null) {
            length++;
            temp=temp.next;
        }
        return length;
    }
    //显示
    public void showList() {
        if (head.next == null) {
            return;
        }
        temp = head.next;
        while (true) {
            System.out.println(temp);
            temp = temp.next;
            if (temp == null) {
                break;
            }
        }
    }

    private class MyNode {
        public Object o;

        public MyNode(Object o) {
            this.o = o;
        }

        public MyNode next;
        public MyNode pre;
        @Override
        public String toString() {
            return "MyNode{" +
                    "o=" + o +
                    '}';
        }
    }
}

本文地址：https://blog.csdn.net/Tang2468/article/details/111924536