2021CS61BWeek1and2

希望能坚持下去，下面这个链接给我坚持的兴趣。

怎样学习数据结构？ 伯克利神课CS61B 总结感悟，学习指南和避坑建议

http://t.csdnimg.cn/6egG4

目前策略是这样

优先看完https://www.bilibili.com/video/BV1Ri421o7dS/?spm_id_from=333.999.0.0&vd_source=d84f08a0531e04d6d41c38180cce9fb5

如果有不清楚的在看英文原版

https://www.bilibili.com/video/BV1QP4y1u7jv/?spm_id_from=333.337.search-card.all.click&vd_source=d84f08a0531e04d6d41c38180cce9fb5

怎么实验室lab和家庭作业homework还不一样呢

目前进度windows安装git搞完了

这两个视频都是一样的，都是UCB CS 61B: Data Structures, Spring 2024

L1-Introduction

package org.example;


public class Main {
    public static class Car {
        public String model;
        public int wheels;

        public Car(String m) {
            this.model = m;
            this.wheels = 4;
        }

        public void drive() {
            if (this.wheels < 4) {
                System.out.println(this.model + "no go vroom");
                return;
            }
            System.out.println(this.model + "go vroom");
        }

        public int getWheels() {
            return this.wheels;
        }

        public void driveIntoDitch(int wheelsLost) {
            this.wheels -= wheelsLost;
        }
    }

    public static void main(String[] args) {
        Car c1 = new Car("baoshijie");
        Car c2 = new Car("falali");
        c1.drive();
        c1.driveIntoDitch(1);
        c1.drive();
        System.out.println(c2.getWheels());
    }
}

L2 - Defining and Using Classes

Classes in Java

Dog.java

package org.example;

public class Dog {
    public static void makeNoise(){
        System.out.println("Bark!");
    }
}

DogLauncher.java

package org.example;

public class DogLauncher {
    public static void main(String[] args) {
        Dog.makeNoise();
    }
}

static是静态修饰符，什么叫静态修饰符呢？大家都知道，在程序中任何变量或者代码都是在编译时由系统自动分配内存来存储的，而所谓静态就是指在编译后所分配的内存会一直存在，直到程序退出内存才会释放这个空间，也就是只要程序在运行，那么这块内存就会一直存在。这样做有什么意义呢？在Java程序里面，所有的东西都是对象，而对象的抽象就是类，对于一个类而言，如果要使用他的成员，那么普通情况下必须先实例化对象后，通过对象的引用才能够访问这些成员，但是用static修饰的成员可以通过类名加“.”进行直接访问。也就是你不用实例化对象，对这整个类都是通用的，CS61B原话：用static修饰，对所有的Dog都是通用的。直接通过类名加“.”进行直接访问。

Dog.java

package org.example;

public class Dog {
    public int weightInPounds;
    public Dog(int w){
        weightInPounds = w;
    }
    public  void makeNoise() {
        if (weightInPounds < 10)
            System.out.println("yipyipyip!");
        else if (weightInPounds < 30){
            System.out.println("Bark!");
        }else {
            System.out.println("arooooooo!");
        }
    }
}

DogLauncher.java

package org.example;

public class DogLauncher {
    public static void main(String[] args) {
        Dog d1 = new Dog(100);
        d1.makeNoise();
    }
}

哇，一开始觉得他们讲Dog的例子很难理解，但是听到后面豁然开朗，这个例子贯彻讲解始终，生动的比喻脱离了干涩难懂的术语，好记好懂好理解

这两种语法上都是对的，但是用那个取决于你。

你是喜欢有一个公正的观察者，还是喜欢特定的狗做把戏并将自己与其他狗进行比较

//所有的狗都有相同的通用的学名，那就用static关键字
// 这是所有狗的学名，是整个类通用的东西，而不是一个变量。对于我创建的每一只狗，他都是常数
// 不是某一特定狗的学名.

public static String binomen = "Canis familiaris";

Dog.java

package org.example;

public class Dog {
    public int weightInPounds;
    //所有的狗都有相同的通用的学名，那就用static关键字
    // 这是所有狗的学名，是整个类通用的东西，而不是一个变量。对于我创建的每一只狗，他都是常数
    // 不是某一特定狗的学名.

    public static String binomen = "Canis familiaris";

    public Dog(int w) {
        weightInPounds = w;
    }

    public void makeNoise() {
        if (weightInPounds < 10)
            System.out.println("yipyipyip!");
        else if (weightInPounds < 30) {
            System.out.println("Bark!");
        } else {
            System.out.println("arooooooo!");
        }
    }

    public static Dog maxDog(Dog d1, Dog d2) {
        if (d1.weightInPounds > d2.weightInPounds)
            return d1;
        else return d2;
    }

    public Dog maxDog(Dog d2) {
        if (this.weightInPounds > d2.weightInPounds)
            return this;
        else return d2;
    }
}

DogLauncher.java

package org.example;

public class DogLauncher {
    public static void main(String[] args) {
        Dog chester = new Dog(100);
        Dog yusuf = new Dog(17);
        Dog larger = Dog.maxDog(yusuf, chester);
        larger.makeNoise();

        Dog huya = new Dog(10);
        Dog jaja = new Dog(170);
        Dog larger2 = huya.maxDog(jaja);
        larger2.makeNoise();

        System.out.println(Dog.binomen);
    }
}

Interactive Debugging

讲得很好，代码细节不重要，重要的是与调试器交互。就不贴代码了

L3 - Lists I:References Recursion and Lists

引用递归和列表，，是不是少了一章递归的视频

Primitive Types ,Reference Types, Parameter Passing

Java可视化网站https://cscircles.cemc.uwaterloo.ca/java_visualize/#mode=display

不是八种基本类型之一的任何东西都被称为引用类型（reference type）

当你实例化一个对象的时候，实际上是创建了对该对象的引用

new Walrus(1000, 8.3)返回内存中为海象结构体分配的空间的首地址。你可以把new关键字想象成返回一个数字，这个数字是在内存中的编号位，也就是地址

Walrus someWalrus;
someWalrus = null;

someWalrus 是一个指针类型的变量，存放了地址，我们根据这个地址找到海象的在的位置。

这里赋值为NULL就类似于C语言里面 int *p = NULL;一样

someWalrus并没有存放海象，相反，这个空间实际上存放着我的海象在内存中的位置

盒子和指针表示法

八种类型直接放内存盒子里面，因为他们是原始类型

其余类型都是引用类型

Instantiation of Arrays

数据不是八种原始类型之一

停下来，，往前找作业左了

下面是2021Spring的课程笔记

Week1

24OUT表示以后24的视频非特殊情况，例如21讲的自己不懂，除非特殊情况都不看24的讲课视频

VideoName	Done	warning
sp24 1.intro	Done
1.intro	Done
Discussion	Done
Lab1	Done
Project 0.intro	Done
sp24 2.Defin	Done	24OUT
2.Defining	Done
2.live Q&A	Done	快速扫过
Week1Over

理清课程资料的使用思路

懂了，如下面的图。有特地标出来的就是24年的课，没有特地标出来就是21年的课。链接是这个

【2024 双语字幕🎉 | UCB CS 61B: Data Structures, Spring 2024】 https://www.bilibili.com/video/BV1QP4y1u7jv/?p=5&share_source=copy_web&vd_source=82180e49f17daecf14bb6f246fc29cd0

但是呢，他很多21的课没做双语字幕，自动翻译的中文字幕差太多了。所以看21的课还是用这个视频

【【双语字幕】CS 61B 数据结构 | 整合版 | UCB Data Structure Spring 2021 | 转码必看 Java 算法 Leetcode】 https://www.bilibili.com/video/BV1q3411V7rS/?p=2&share_source=copy_web&vd_source=82180e49f17daecf14bb6f246fc29cd0

但是目录和检查各个作业等等还是用第一个视频的标题把。

Project 0.intro

有人带着看Proj 0的文档帮你在旁边讲解还是好很多，边看文档边听他讲吧。

看完了，每一个都尝试五分钟，如果不会就去看别人的讲解。

2.Defining

非静态变量记忆成实例变量

Week2

24OUT表示以后24的视频非特殊情况，例如21讲的自己不懂，除非特殊情况都不看24的讲课视频。翻译成中文的视频的标题为我下面的VideoName，也尝试过写成官方网站上英文的样子，但是对学习的效率有较大的影响，所以还是写成中文。

VideoName	Done	warning
sp24 6.测试	24OUT
3.测试	Done
3.现场问答	扫过
sp24 3.列表1	24OUT
4.列表1	Done
4.现场问答	扫过
sp24 4.列表2	24OUT
5.列表2	Done
5.现场问答	扫过
sp24	24OUT
6.清单3	ing
6.现场问答	扫过

还是尽量模拟他们的表格，来一个一个完成任务吧

Reading	Lecture	Discussion
3.1正在看， Optional不看	\3. Testing [video]不看 ‌[slides]看了 ‌[guide] ‌[live Q&A] ‌ ‌
2.1	\4. References, Recursion, and Lists [video] ‌[slides] ‌[guide] ‌[live Q&A] ‌
2.2	\5. SLLists, Nested Classes, Sentinel Nodes [video] ‌[slides] ‌[guide] ‌[live Q&A] ‌
Discussion

3_Testing

Important note: You may be asking “Why are you looping through the entire array? Why don’t you just check if the arrays are equal using ==? “. The reason is, when we test for equality of two objects, we cannot simply use the == operator. The == operator compares the literal bits in the memory boxes, e.g. input == expected would test whether or not the addresses of input and expected are the same, not whether the values in the arrays are the same. Instead, we used a loop in testSort, and print out the first mismatch. You could also use the built-in method java.util.Arrays.equals instead of a loop.

TestSort.java

public class TestSort {
    public static void testSort() {
        String[] input = {"i", "have", "an", "egg"};
        String[] expected = {"an", "egg", "have", "i"};

        Sort.sort(input);
        for (int i = 0; i < input.length; i++) {
            if (!input[i].equals(expected[i])) {
                System.out.println("Mismatch in position " + i + ", expected: " + expected[i] + ", but got :" + input[i]);
                return;
            }
        }
    }

    public static void main(String[] args) {
        testSort();
    }
}

Intellij IDEA junit 使用之org.junit爆红

参考这篇博客https://blog.csdn.net/qq_31424825/article/details/84873575

public class TestSort {
    public static void testSort() {
        String[] input = {"i", "have", "an", "egg"};
        String[] expected = {"an", "egg", "have", "i"};

        Sort.sort(input);

        org.junit.Assert.assertArrayEquals(expected, input);

    }

    public static void main(String[] args) {
        testSort();
    }
}

一个伟大的事情，他这个再查看递归里面的堆栈的可视化，，真是一个伟大的插件

每一层的start和smallestIndex都显示出来。这样子递归就清楚多了。

虽然IDEA有调试的图形化插件Visualizer但是Clion好像没有

在windows下有vistual studio，针对opencv有image watch，在ubuntu下用Clion插件Image Watch要收费，遂研究OpenImageDebugger与CLion问题及在Clion中调试方法

搜了一搜，，感觉Clion是真没有，不过无所谓了。及时止损。

用

import org.junit.Test;

import static org.junit.Assert.*;

来简化代码

事实上，这种方法帮助你省略了，main函数，你不必自己在main函数里面依次调用每一个testXXX测试方法。

import org.junit.Test;

import static org.junit.Assert.*;

public class TestSort {
    @Test
    public void testSort() {
        String[] input = {"i", "have", "an", "egg"};
        String[] expected = {"an", "egg", "have", "i"};

        Sort.sort(input);

        assertArrayEquals(expected, input);

    }

    /* Test the Sort.findSmallest method.*/
    @Test
    public void testfindSmallest() {
        String[] input = {"i", "have", "an", "egg"};
        int expected = 2;

        int actual = Sort.findSmallest(input, 0);

        assertEquals(expected, actual);
        String[] input2 = {"there", "are", "many", "pigs"};
        int expected2 = 2;

        int actual2 = Sort.findSmallest(input2, 2);

        assertEquals(expected2, actual2);
    }

    /*
    Test the Sort.swap method.
     */
    @Test

    public void testSwap() {
        String[] input = {"i", "have", "an", "egg"};
        int a = 0;
        int b = 2;
        String[] expected = {"an", "have", "i", "egg"};

        Sort.swap(input, a, b);

        assertArrayEquals(expected, input);

    }


}

4_References, Recursion, and Lists

Primitive Types

前半部分看过，就在上面24年的笔记上面

想起来一件事情， 如果自己还觉得无法理解，或者觉得字幕翻译的不够好的话，，可以在看对应章节的24的中文ai配音视频。它的字幕是精心翻译校对过的，同时有中文声音让人也更加专注

Parameter Passing

Java Visualizer (uwaterloo.ca)

public class PollQuestions {
2	   public static void main(String[] args) {
3	      Walrus walrus = new Walrus(3500, 10.5);
4	      int x = 9;
5	      
6	      doStuff(walrus, x);
7	      System.out.println(walrus);
8	      System.out.println(x);
9	   }
10	   
11	   public static void doStuff(Walrus W, int x) {
12	      W.weight = W.weight - 100;
13	      x = x - 5;
14	   }
15	   
16	   public static class Walrus {
17	      public int weight;
18	      public double tuskSize;
19	      
20	      public Walrus(int w, double ts) {
21	         weight = w;
22	         tuskSize = ts;
23	      }
24	
25	      public String toString() {
26	         return String.format("weight: %d, tusk size: %.2f", weight, tuskSize);
27	      }
28	   }
29	}

Instantiation of Arrays

数组也属于非八种原始变量，因此数组名里面放着第一个数组元素的地址。

IniList and Linked Data Structures(See webcast or code directory)

public class IntList {
    public int first;
    public IntList rest;

    public IntList(int f, IntList r) {
        this.first = f;
        this.rest = r;
    }

    public static void main(String[] args) {
        //这好像相当于链表的头插法
        IntList L = new IntList(15, null);
        L = new IntList(10, L);
        L = new IntList(5, L);
    }
}

t这课堂作业要不要做，是课上直接在自己的电脑上面做呢，，还是git clone他的课程代码呢？？

课上做得了。自己又不是不会，之前写过好多类似的代码，这个不用太严肃 的。

public static IntList incrList(IntList L, int x) {
        //用dummyNode处理尾插法可以避免分类讨论
        //Q用尾插法，事实上Q就是dummyNode.rest,L从前往后遍历
        IntList dummyNode = new IntList(-1, null);
        IntList tailQ = dummyNode;
        IntList cur = L;
        while (cur != null) {
            IntList newNode = new IntList(cur.first + x, null);
            tailQ.rest = newNode;
            tailQ = newNode;
            cur = cur.rest;
        }
        return dummyNode.rest;
    }

public static IntList dincrList(IntList L, int x) {
        IntList cur = L;
        while (cur != null) {
            cur.first += x;
            cur = cur.rest;
        }
        return  L;
    }

5_SLLists, Nested Classes, Sentinel Notes

nest，嵌套的意思

SLList: A Singly-Linked List.单链表

IntNode.java

public class IntNode {
    public int item;
    public IntNode next;

    public IntNode(int i, IntNode n) {
        this.item = i;
        this.next = n;
    }
}

SLList.java

import javax.naming.InsufficientResourcesException;

public class SLList {
    //理解成L链表只存放着第一个结点的地址，也就是L链表里面的元素就是一个指针变量，放着第一个结点的地址
    // 这就是C++49那个花生老师的写法，一模一样，，运气太好了。自己越是学习，感觉运气就越好
    public IntNode first;

    public SLList(int x) {
        first = new IntNode(x, null);
    }


    /* Adds x to the front of the list*/
    public void addFirst(int x) {
//        IntNode newNode = new IntNode(x, null);
//        newNode.next = first;
//        first = newNode;
        //上面三行在Java里面可以写成一行代码，真的难绷
        first = new IntNode(x, first);
    }
    public int getFirst(){
        return this.first.item;
    }
    public static void main(String[] args) {
        SLList L = new SLList(15);
        L.addFirst(10);
        L.addFirst(5);
        System.out.println(L.getFirst());
        return;
    }
}

Naked Linked Lists (IntList) VS SLLists

肯定是下面的 好，，大家都约定俗成了、

吓死我了，，还以为自己写错 了。。原来只是同一事物的另一种可视化

原来私有静态结构是这样用的 。private static

为了递归的求他的大小，不得不采用这种新的编程。创建private static类型，它使用神的语言（就是说采用裸露的数据结构，naked Linked Lists)

贴上我的代码

import javax.naming.InsufficientResourcesException;

public class SLList {
    public class IntNode {
        public int item;
        public IntNode next;

        public IntNode(int i, IntNode n) {
            this.item = i;
            this.next = n;
        }
    }

    //理解成L链表只存放着第一个结点的地址，也就是L链表里面的元素就是一个指针变量，放着第一个结点的地址
    // 这就是C++49那个花生老师的写法，一模一样，，运气太好了。自己越是学习，感觉运气就越好
    private IntNode first;

    public SLList(int x) {
        first = new IntNode(x, null);
    }

    /* Adds x to the front of the list*/
    public void addFirst(int x) {
//        IntNode newNode = new IntNode(x, null);
//        newNode.next = first;
//        first = newNode;
        //上面三行在Java里面可以写成一行代码，真的难绷
        first = new IntNode(x, first);
    }

    public int getFirst() {
        return this.first.item;
    }

    public void addLast(int x) {
        if (this.first == null) {
            //空表
            this.addFirst(x);

        } else {
            IntNode tail = this.first;
            while (tail.next != null) {
                tail = tail.next;
            }
            tail.next = new IntNode(x, null);
//tail = tail.next;
        }
        return;
    }

    /* Returns the size of the list that starts at IntNode p.*/
    private static int size(IntNode p) {
        if (p.next == null) return 1;
        return 1 + size(p.next);
    }

    public int size() {
        return size(this.first);
    }

    public int sizeNoRecursion() {
        int cnt = 0;
        IntNode p = this.first;
        while (p != null) {
            cnt++;
            p = p.next;
        }
        return cnt;
    }


    public static void main(String[] args) {
        SLList L = new SLList(15);
        L.addFirst(10);
        L.addFirst(5);
        L.addLast(20);
        System.out.println(L.getFirst());
        System.out.println(L.size());
        return;
    }
}

加一个size变量，求size的时候，时间复杂度最低。

这个教授说SSList的优势是能够实例化一个空列表，是吗？？

他最终还是将了，，他又要写创建空表，，又要写尾插法还不带判断空表的情况，果然他还是讲了这部分的内容。

代码如下

public void addLast(int x) {
        if (this.first == null) {
            //空表
            //不能再调用addFirst()函数，因为size在这儿函数里面也会++，，最终会导致size＋2
//            this.addFirst(x);
            this.first =  new IntNode(x, null);

        } else {
            IntNode tail = this.first;
            while (tail.next != null) {
                tail = tail.next;
            }
            tail.next = new IntNode(x, null);
//tail = tail.next;
        }
        size++;
        return;
    }

然后开始讲dummyNode，他这里了叫sentinel Nodes，哨兵结点

import javax.naming.InsufficientResourcesException;

public class SLList {
    public class IntNode {
        public int item;
        public IntNode next;

        public IntNode(int i, IntNode n) {
            this.item = i;
            this.next = n;
        }
    }

    //理解成L链表只存放着第一个结点的地址，也就是L链表里面的元素就是一个指针变量，放着第一个结点的地址
    // 这就是C++49那个花生老师的写法，一模一样，，运气太好了。自己越是学习，感觉运气就越好
//    private IntNode first;
    private IntNode sentinel;
    private int size;

    //Create an empty SLList
    public SLList() {

        sentinel = new IntNode(63, null);
        size = 0;
    }

    public SLList(int x) {
        sentinel = new IntNode(63, null);
        sentinel.next = new IntNode(x, null);
        size = 1;
    }

    /* Adds x to the front of the list*/
    public void addFirst(int x) {
//        IntNode newNode = new IntNode(x, null);
//        newNode.next = first;
//        first = newNode;
        //上面三行在Java里面可以写成一行代码，真的难绷
        sentinel.next = new IntNode(x, sentinel.next);
        size++;
    }

    public int getFirst() {
        return this.sentinel.next.item;
    }

    public void addLast(int x) {
        IntNode p = sentinel;
        while (p.next != null) {
            p = p.next;
        }
        p.next = new IntNode(x, null);
        size++;
        return;
    }

    /* Returns the size of the list that starts at IntNode p.*/
//    private static int size(IntNode p) {
//        if (p.next == null) return 1;
//        return 1 + size(p.next);
//    }

    public int size() {
        return this.size;
    }

//    public int sizeNoRecursion() {
//        int cnt = 0;
//        IntNode p = this.first;
//        while (p != null) {
//            cnt++;
//            p = p.next;
//        }
//        return cnt;
//    }
//

    public static void main(String[] args) {
        SLList L = new SLList();
//        L.addFirst(10);
//        L.addFirst(5);
        L.addLast(20);
//        System.out.println(L.getFirst());
        System.out.println(L.size());
        return;
    }
}

不变量的好处。例如sentinel就是一种不变量，保证永远不为空