欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构与算法学习笔记

程序员文章站 2022-03-06 18:35:46
数据结构与算法学习笔记才开始学习数据结构,这也将会是我的第一篇博客文章介绍我将会在这篇博客中记录所有的数据结构与算法的所有学习内容稀疏数组学习稀疏数组就是使用n*3二维数组去更加简洁的保存数据// An highlighted blockpublic class SparseArray { public static void main() { int[][] mapArr = new int[11][11]; mapArr[0][1] = 1;...

文章介绍

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

稀疏数组学习

稀疏数组就是使用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