CS61B 课程笔记（Lecture 40 Summary, Fun)

1. 重要数据结构

  • 数组：

    • 定义：固定大小的元素集合。
    • 优点：支持随机访问，时间复杂度为 \(O(1)\) 。
    • 缺点：插入和删除操作需要移动元素，时间复杂度为 $O(n) $。
    1
    2
    3
    // 数组示例
    int[] arr = {1, 2, 3, 4, 5};
    int element = arr[2]; // 随机访问

  • 链表：

    • 定义：由节点组成的集合，每个节点包含数据和指向下一个节点的指针。
    • 优点：插入和删除操作的时间复杂度为 \(O(1)\) （在已知节点的情况下）。
    • 缺点：随机访问的时间复杂度为 $ O(n) $。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // 创建链表
    Node head = new Node(1);
    head.next = new Node(2);
    head.next.next = new Node(3);

  • 栈：

    • 定义：后进先出（\(LIFO\)）结构。
    • 操作：
      • push：将元素压入栈。
      • pop：将元素弹出栈。
    1
    2
    3
    4
    5
    6
    7
    import java.util.Stack;

    // 栈示例
    Stack<Integer> stack = new Stack<>();
    stack.push(1);
    stack.push(2);
    int top = stack.pop(); // 返回2

  • 队列：

    • 定义：先进先出（FIFO）结构。
    • 操作：
      • enqueue：将元素加入队列。
      • dequeue：将元素从队列移除。
    1
    2
    3
    4
    5
    6
    7
    import java.util.LinkedList;

    // 队列示例
    LinkedList<Integer> queue = new LinkedList<>();
    queue.add(1); // enqueue
    queue.add(2);
    int first = queue.remove(); // dequeue，返回1

  • 树：

    • 定义：层级数据结构，常见的有二叉树、红黑树和B树。
    • 例子：二叉搜索树的插入和查找。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class TreeNode {
        int value;
        TreeNode left, right;
        
        TreeNode(int value) {
            this.value = value;
            left = right = null;
        }
    }

    // 插入节点
    TreeNode insert(TreeNode root, int value) {
        if (root == null) return new TreeNode(value);
        if (value < root.value) root.left = insert(root.left, value);
        else root.right = insert(root.right, value);
        return root;
    }

  • 图：

    • 定义：节点和边的集合，表示复杂关系。
    • 表示方式：邻接表和邻接矩阵。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    import java.util.ArrayList;
    import java.util.HashMap;

    // 图的邻接表表示
    class Graph {
        HashMap<Integer, ArrayList<Integer>> adjList = new HashMap<>();
        
        void addEdge(int src, int dest) {
            adjList.putIfAbsent(src, new ArrayList<>());
            adjList.putIfAbsent(dest, new ArrayList<>());
            adjList.get(src).add(dest);
            adjList.get(dest).add(src); // 无向图
        }
    }

2. 数据结构的性能分析

  • 时间复杂度：
    • 数组：查找 $O(1) $，插入/删除 $O(n) $。
    • 链表：查找 $O(n) $，插入/删除 \(O(1)\) （在已知节点的情况下）。
    • 栈和队列：均为 $O(1) $。
    • 树：平衡树查找、插入、删除均为 $ O(n) $，未平衡树可能为 \(O(n)\) 。
  • 空间复杂度：
    • 数组 \(O(n)\) 。
    • 链表 $ O(n) $。
    • 树的空间复杂度通常也是 \(O(n)\) ，但取决于树的深度。

3. 有趣的话题

  • 程序设计的实践：

    • 重要性：实际编程可以帮助我们理解理论，并提高问题解决能力。

  • 算法的怪异性：

    • 例如，冒泡排序在某些情况下性能反而较好，如数据几乎有序时。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break; // 提前结束
        }
    }

4. 数学分析

  • 算法性能的数学分析：
    • 使用极限、积分分析复杂性。
  • 概率论在算法中的应用：
    • 随机算法，例如随机快速排序，能够在平均情况下提供良好的性能。

1. 面向对象编程 (OOP)

面向对象编程以对象为中心，对象可以包含数据和方法。下面是一个简单的Java示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 定义一个名为'Dog'的类
class Dog {
    // 实例变量
    String name;

    // 构造函数
    Dog(String name) {
        this.name = name;
    }

    // 显示狗的名字的方法
    void bark() {
        System.out.println(name + " says: Woof!");
    }
}

public class Main {
    public static void main(String[] args) {
        Dog myDog = new Dog("Rex");
        myDog.bark(); // 输出: Rex says: Woof!
    }
}

2. 数据结构：数组与链表

基于数组的数据结构（如ArrayList）：

  • 使用连续的内存位置。
  • 通过索引快速访问，但扩展代价昂贵。

链表：

  • 由包含数据和对下一个节点引用的节点组成。
  • 在大小上更灵活，但访问元素的速度较慢。

链表实现示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    // 添加新节点到末尾的方法
    void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // 打印链表的方法
    void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

public class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.printList(); // 输出: 1 -> 2 -> 3 -> null
    }
}

3. Java中的泛型

泛型允许你定义类和方法，并使用占位符类型，从而实现代码的重用。例如，创建一个泛型的ArrayList：

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<String> stringList = new ArrayList<>();
        stringList.add("Hello");
        stringList.add("World");

        for (String s : stringList) {
            System.out.println(s); // 输出: Hello World
        }
    }
}

4. 算法分析

渐近分析帮助你理解算法的性能。以下是简要说明：

  • \(O(n)\)：上界（最坏情况）。
  • \(Ω(n)\)：下界（最好情况）。
  • \(Θ(n)\)：紧界（平均情况）。

冒泡排序分析示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 交换arr[j]和arr[j + 1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        for (int num : arr) {
            System.out.print(num + " "); // 输出: 11 12 22 25 34 64 90
        }
    }
}

5. 树结构

树是一种层次数据结构。下面是一个简单的二叉树实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class TreeNode {
    int value;
    TreeNode left, right;

    TreeNode(int item) {
        value = item;
        left = right = null;
    }
}

class BinaryTree {
    TreeNode root;

    // 中序遍历
    void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.left);
            System.out.print(node.value + " ");
            inOrder(node.right);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        
        System.out.print("中序遍历: ");
        tree.inOrder(tree.root); // 输出: 2 1 3
    }
}