【CS61B】Lec18-Red Black Trees

发表于 2025-08-05 分类于 CS61B
本文字数： 1.3k 阅读时长 ≈ 2 分钟

CS61B的第18讲，在B树的基础上介绍了树的旋转、红黑树的插入原理

阅读全文 »

【C++】概念与约束

发表于 2025-08-01 分类于 C/C++
本文字数： 1.6k 阅读时长 ≈ 3 分钟

C++20最新引入的语言特性，指定了对模板实参的要求

阅读全文 »

【C++】模块

发表于 2025-08-01 分类于 C/C++
本文字数： 1.2k 阅读时长 ≈ 2 分钟

C++20引入的模块化特性，是一种新的组织代码的形式

阅读全文 »

【CS61B】Lec17-B-Trees

发表于 2025-07-31 更新于 2025-08-05 分类于 CS61B
本文字数： 904 阅读时长 ≈ 2 分钟

CS61B的第17讲，介绍了B树，2-3-4树等的构成原理

阅读全文 »

【算法】排序

发表于 2025-07-31 更新于 2025-12-17 分类于算法与数据结构， (或许是)基础算法
本文字数： 2.3k 阅读时长 ≈ 4 分钟

介绍了一些基础排序算法

阅读全文 »

【字符串】字符串哈希

发表于 2025-07-31 更新于 2025-12-18 分类于算法与数据结构，字符串
本文字数： 1.9k 阅读时长 ≈ 3 分钟

介绍了字符串哈希的用法

阅读全文 »

【算法】IDDFS与IDA*

发表于 2025-07-31 更新于 2025-12-17 分类于算法与数据结构，搜索
本文字数： 1.5k 阅读时长 ≈ 3 分钟

介绍了IDDFS与IDA*，对于DFS与BFS的进一步优化

阅读全文 »

【算法】双向搜索

发表于 2025-07-31 更新于 2025-12-17 分类于算法与数据结构，搜索
本文字数： 1.8k 阅读时长 ≈ 3 分钟

介绍了双向搜索与meet-in-the-middle，是对BFS与DFS的进一步优化

阅读全文 »

【CS61B】Project1A-Linked List Deque 61B

发表于 2025-07-31 分类于 CS61B
本文字数： 3.9k 阅读时长 ≈ 7 分钟

Project1A-Linked List Deque 61B

这个项目要求我们用链表实现双端队列(Deque)

Javadoc comment

/** ...
 * @param index index to get
 * @return element at {@code index} in the deque
 */
T get(int index);

如以上注释，该形式的注释为java文档注释

@param表示方法的变量
@return表示方法的返回值类型
@code 用于格式化文本为代码风格

步骤

创建文件

我们希望创建的类可以接受多种数据类型，故需要实现泛型，在声明类时：

public class LinkedListDeque61B<T>

另外需要指定LinkedListDeque61B是Deque61B的子类，并且实现所有接口中的方法：

import java.util.List;

public class LinkedListDeque61B<T> implements Deque61B<T>{
    @Override
    public void addFirst(T x) {
        
    }

    @Override
    public void addLast(T x) {

    }

    @Override
    public List<T> toList() {
        return List.of();
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public T removeFirst() {
        return null;
    }

    @Override
    public T removeLast() {
        return null;
    }

    @Override
    public T get(int index) {
        return null;
    }

    @Override
    public T getRecursive(int index) {
        return null;
    }
}

最后加入构造函数：

public LinkedListDeque61B(){

}

JUnit Tests

打开LinkedListDeque61BTest文件，去除除最后一行的注释，就可以对编写代码进行本地测试

Writing and Verifying the Constructor

实现构造函数，更具体的，构造函数应传入0个参数，并在LinkedListDeque61B类中实现嵌套类Node

private class Node{
    public T item;
    public Node next;
    public Node previous;
    public Node(T i, Node p, Node n){
        item = i;
        next = n;
        previous = p;
    }
}

private Node sentinelFront;
private Node sentinelLast;
private int size;
public LinkedListDeque61B(){
    sentinelFront = new Node(null, null, null);
    sentinelLast = new Node(null, null, null);
    size = 0;
}

这里我们在类中嵌套实现了Node类用于定义每个节点，并且对双端队列设置了两个sentinel节点，方便双端操作，同时引入size记录大小

其中，Node类包括两个指针，同时指向前一个节点与后一个节点

构造函数中，对两个sentinel节点进行初始化，并设置size为0

Writing and Verifying `addFirst` and `addLast`

addFirst与addLast需要以常数时间实现

@Override
public void addFirst(T x) {
    Node newNode = new Node(x, sentinelFront, sentinelFront.next);
    sentinelFront.next.previous = newNode;
    sentinelFront.next = newNode;
    size++;
}

@Override
public void addLast(T x) {
   Node newNode = new Node(x, sentinelLast.previous, sentinelLast);
   sentinelLast.previous.next = newNode;
   sentinelLast.previous =  newNode;
    size++;
}

我们直接操作sentinel节点的next与previous来添加节点

Writing and Verifying `toList`

实现toList，当调用时会自动返回以列表形式表示的Deque61B

例如，如果Deque61B已经调用了addLast(5)、addLast(9)、addLast(10)，然后对其调用addFirst(3)，那么toList()的结果应该是一个以3开头，然后是5、9、10的列表。如果在Java中打印，它将显示为[3, 5, 9, 10]。

toList方法的第一行应该类似于List<T> returnList = new ArrayList<>()，标志着可以使用该结构的位置

@Override
public List<T> toList() {
    List<T> returnList = new ArrayList<>();
    for (Node p = sentinelFront.next; p!=sentinelLast; p = p.next){
        returnList.add(p.item);
    }
    return returnList;
}

Writing Tests

写测试例的模板：Arrange-Act-Assert

Arrange：组织测试样例，如初始化数据结构或往里面填充元素
Act：执行想要执行的操作
Assert：评估Act中的结果

在单个测试方法中通常有多个act与assert步骤

真值评估的模板：

格式：assertThat(actual).isEqualTo(expected);

添加信息：

assertWithMessage("actual is not expected")
    .that(actual)
    .isEqualTo(expected);

判断列表包含内容：

assertThat(actualList)
    .containsExactly(0, 1, 2, 3)
    .inOrder();

对于引用类型：

assertThat(actualList)
    .containsExactlyElementsIn(expected)  // `expected` is a List
    .inOrder();

注意：assert一个布尔值时，记得在后面使用.isTrue() 或者 .isFalse()判断正误

其余方法

isEmpty()与size()

要求常数时间实现

@Override
public boolean isEmpty() {
    return size==0;
}

@Override
public int size() {
    return size;
}

get()与getRecursive()

给予下标寻找下标对应元素

@Override
public T get(int index) {
    if (index<0||index>=size){
        return null;
    }
    Node p = sentinelFront.next;
    for (int i = 0; i<index; i++){
        p = p.next;
    }
    return p.item;
}

private T getRecursiveHelper(Node p, int index){
    if (index == 0) return p.item;
    return getRecursiveHelper(p.next, index-1);
}
@Override
public T getRecursive(int index) {
    if (index<0||index>=size){
        return null;
    }
    return getRecursiveHelper(sentinelFront.next, index);
}

写了一个辅助递归函数，可以接受当前节点与下标，进行节点的推进

removeFirst()与removeLast()

@Override
public T removeFirst() {
    if (isEmpty()){
        return null;
    }
   Node temp = sentinelFront.next;
    sentinelFront.next = temp.next;
    temp.next.previous = sentinelFront;
    size--;
    return temp.item;
}

@Override
public T removeLast() {
    if (isEmpty()){
        return null;
    }
    Node temp = sentinelLast.previous;
    sentinelLast.previous = temp.previous;
    temp.previous.next = sentinelLast;
    size--;
    return temp.item;
}

【CS61B】Project1B-ArrayDeque 61B

发表于 2025-07-31 分类于 CS61B
本文字数： 3.6k 阅读时长 ≈ 7 分钟

Project1B - ArrayDeque 61B

这个项目中，我们需要用数组实现循环双端队列

初始化

创建类文件，并修改类声明以让该类是Deque61B接口的一个实现，且支持泛型

package deque;

import java.util.List;

public class ArrayDeque61B<T> implements Deque61B<T> {
    @Override
    public void addFirst(T x) {
        
    }

    @Override
    public void addLast(T x) {

    }

    @Override
    public List<T> toList() {
        return List.of();
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public T removeFirst() {
        return null;
    }

    @Override
    public T removeLast() {
        return null;
    }

    @Override
    public T get(int index) {
        return null;
    }

    @Override
    public T getRecursive(int index) {
        return null;
    }
}

构造函数

使用到的成员有

size：确定数组目前容量
capacity：确定数组最大容量
items：使用java内置数组存储数据
nextFirst：指向队首（第一个空位置）
nextLast：指向队尾（最后一个空位置）

public ArrayDeque61B(){
    size = 0;
    capacity = 8;
    items = (T[])new Object[capacity];
    nextFirst = 0;
    nextLast = 0;
}

addFirst() & addLast()

@Override
public void addFirst(T x) {
    if (size==capacity){
        resize(size*2);
    }
    items[nextFirst] = x;
    size++;
    nextFirst = floorMod(nextFirst-1, capacity);
}

@Override
public void addLast(T x) {
    if (size==capacity){
        resize(size*2);
    }
    items[nextLast] = x;
    size++;
    nextLast = floorMod(nextLast+1, capacity);
}

这里在添加时要考虑循环，若到队头了要转到队尾加

另外，当队列满了需要手动扩容，一般可以扩到原来都两倍，防止过多调用

get()

按下标获得元素，若无效返回null

@Override
public T get(int index) {
    if (index<0||index>=size){
        return null;
    }
    int realIndex = floorMod(index+nextFirst+1, capacity);
    return items[realIndex];
}

这里注意，get获得的是相对下标，我们需要转换成真实下标（即元素不一定是从0开始的，需要添加nextFirst偏移量）

getRecursive()没有什么必要，可以直接抛出一个异常

@Override
public T getRecursive(int index) {
    throw new UnsupportedOperationException("No need to implement getRecursive for proj 1b");
}

toList()

@Override
public List<T> toList() {
    List<T> show = new ArrayList<>(size);
    int cnt = 0;
    for (int i = 0; i<size;i++){
        show.add(get(i));
    }
    return show;
}

结合get方法会更加方便

removeFirst() & removeLast()

@Override
public T removeFirst() {
    if (isEmpty()){
        return null;
    }
    nextFirst = floorMod(nextFirst+1,capacity);
    size--;
    return items[nextFirst];
}

@Override
public T removeLast() {
    if (isEmpty()){
        return null;
    }
    nextLast = floorMod(nextLast-1,capacity);
    size--;
    return items[nextLast];
}

不要忘记判空以及减小size

resize()

作为数组大小不够时的方案，一次扩容两倍使用

private void resize(int newCapacity){
    T[] a = (T[]) new Object[newCapacity];
    int cur = floorMod(nextFirst+1,capacity);
    for(int i = 0; i<size;i++){
        a[i] = items[cur];
        cur = floorMod(cur+1, capacity);
    }
    items = a;
    capacity = newCapacity;
    nextFirst = newCapacity -1;
    nextLast = size;

}

这里要将原数组复制到一个新容量的数组中使用

采用的方法是将原数组元素按从0开始的下标复制到新数组，再用新数组覆盖

同时调整nextFirst与nextLast

iterator()

实现迭代器，让我们的双端队列可以迭代

即在内部嵌套一个Iterator类的实现

@Override
public Iterator<T> iterator() {
    return new ArrayDequeIterator();
}

public class ArrayDequeIterator implements Iterator<T>{
    private int pos;
    ArrayDequeIterator(){
        pos = 0;
    }
    @Override
    public boolean hasNext() {
        return pos < size;
    }

    @Override
    public T next() {
        T returnItems = get(pos);
        pos++;
        return returnItems;
    }
}

注意：接口不允许提供覆盖Object方法的默认方法，故无法在接口中提供默认方法

equals()

重写equals方法，让该方法仅比较元素相等

@Override
public boolean equals(Object o){
    if (o instanceof ArrayDeque61B<?> uAD){
        if (this.size!=uAD.size){
            return false;
        }
        for (int i = 0; i<size;i++){
            if (!Objects.equals(this.get(i), uAD.get(i))){
                return false;
            }
        }
        return true;
    }
    return false;
}

若想在instanceof中使用泛型，需要使用<?>通配符

toString()

返回自定义的string输出表示双端队列

@Override
public String toString(){
    StringBuilder stringToReturn = new StringBuilder("[");
    for (T x: this){
        stringToReturn.append(x);
        stringToReturn.append(", ");
    }
    stringToReturn.delete(stringToReturn.length()-2,stringToReturn.length());
    stringToReturn.append("]");
    return stringToReturn.toString();
}

Project1A-Linked List Deque 61B

Javadoc comment

步骤

创建文件

JUnit Tests

Writing and Verifying the Constructor

Writing and Verifying addFirst and addLast

Writing and Verifying toList

Writing Tests

其余方法

isEmpty()与size()

get()与getRecursive()

removeFirst()与removeLast()

Project1B - ArrayDeque 61B

初始化

构造函数

addFirst() & addLast()

get()

toList()

removeFirst() & removeLast()

resize()

iterator()

equals()

toString()

Writing and Verifying `addFirst` and `addLast`

Writing and Verifying `toList`