Week 2 Exercises: Ownership and structs

练习目的：

本周的练习旨在进一步帮助你熟悉 Rust 编程语言。
练习将专注于以下内容：
- 处理所有权（ownership）和引用（references）。
- 使用 Option 和 Result 类型。
- 轻微接触 Rust 的面向对象编程特性。
主要练习包括实现一个简单版本的 diff 工具，用于比较两个文件的差异。

Part 1: Ownership short-answer exercises

第1部分：所有权短答案练习

示例 1：

fn main() {
    let mut s = String::from("hello");
    let ref1 = &s;
    let ref2 = &ref1;
    let ref3 = &ref2;
    s = String::from("goodbye");
    println!("{}", ref3.to_uppercase());
}

答案：

代码无法编译。原因是 ref1, ref2 和 ref3 都是对 s 的引用，而在 s 被重新赋值为 "goodbye" 时，原来的 s 的所有权被转移，导致之前的引用变得无效。
解决方案：可以将 s 的类型改为不可变引用，或者在使用 ref3 之前不要对 s 重新赋值。

示例 2：

fn drip_drop() -> &String {
    let s = String::from("hello world!");
    return &s;
}

答案：

代码无法编译。原因是在函数中创建的 s 是一个局部变量，当函数结束时，局部变量 s 的所有权被释放，返回对它的引用将导致悬空引用（dangling reference）。
解决方案：可以返回 String 的所有权，修改返回类型为 String，即：fn drip_drop() -> String { let s = String::from("hello world!"); s }。

示例 3：

fn main() {
    let s1 = String::from("hello");
    let mut v = Vec::new();
    v.push(s1);
    let s2: String = v[0];
    println!("{}", s2);
}

答案：

代码无法编译。原因是 s1 的所有权在调用 v.push(s1) 时被转移到 v，所以 s1 在 push 后无法再被使用。尝试使用 v[0] 会导致编译错误，因为 v 中的元素拥有 s1 的所有权。
解决方案：可以将 v 的类型更改为 Vec<String>，并使用 v[0].clone() 来获取 s1 的一个克隆。例如：let s2: String = v[0].clone();。

Part 2: rdiff 实现

里程碑 1：读取两个文件的行到向量中

在这一里程碑中，你需要实现 read_file_lines 函数，它接受一个文件路径并返回该文件的行向量。

步骤：

导入所需的库：

1
2
3

use std::fs::File;
use std::io::{self, BufRead};
use std::path::Path;

实现 read_file_lines 函数：

打开文件：使用 File::open(filename)?; 处理潜在的错误。
读取行：通过 io::BufReader 创建一个缓冲读取器，然后循环读取每一行，将其添加到向量中。

fn read_file_lines<P>(filename: P) -> Result<Vec<String>, io::Error>
where
    P: AsRef<Path>,
{
    let file = File::open(filename)?;
    let reader = io::BufReader::new(file);
    let mut lines = Vec::new();
    
    for line in reader.lines() {
        lines.push(line?);
    }
    Ok(lines)
}

测试实现：运行 cargo test test_read_file_lines。

里程碑 2：实现 Grid 接口

在这个里程碑中，你需要创建一个 Grid 结构体，用于存储二维数据，并实现 get 和 set 方法。

步骤：

创建 Grid 结构体，包含行数和列数以及一个向量。
实现 get 和 set 方法：
- get 方法根据传入的行和列索引返回某个值或 None。
- set 方法则根据索引设置值，并在出界时返回错误。

struct Grid {
    num_rows: usize,
    num_cols: usize,
    data: Vec<i32>, // 这里可以根据需要选择类型
}

impl Grid {
    fn new(num_rows: usize, num_cols: usize) -> Self {
        let data = vec![0; num_rows * num_cols];
        Grid { num_rows, num_cols, data }
    }

    fn get(&self, row: usize, col: usize) -> Option<i32> {
        if row < self.num_rows && col < self.num_cols {
            Some(self.data[row * self.num_cols + col])
        } else {
            None
        }
    }

    fn set(&mut self, row: usize, col: usize, value: i32) -> Result<(), String> {
        if row < self.num_rows && col < self.num_cols {
            self.data[row * self.num_cols + col] = value;
            Ok(())
        } else {
            Err(format!("Index out of bounds: ({}, {})", row, col))
        }
    }
}

测试实现：运行 cargo test test_grid -- --nocapture。

里程碑 3：实现最长公共子序列（LCS）

最长公共子序列（Longest Common Subsequence, LCS）是一个经典的动态规划问题，旨在找到两个序列（字符串、数组等）之间的最长公共子序列。公共子序列是指在不改变字符顺序的情况下，从两个序列中可以找到的相同元素的子序列。

定义子问题：

给定两个序列 $X$ 和 $Y$，其中 $X$ 的长度为 $m$，$Y$ 的长度为 $n$。我们需要计算它们的LCS长度。

使用二维数组 dp，其中 dp[i][j] 表示序列 $X[0..i-1]$ 和 $Y[0..j-1]$ 的最长公共子序列的长度。

状态转移方程：

当 $X[i-1] = Y[j-1]$（即当前字符相同）时： $ dp[i][j] = dp[i-1][j-1] + 1 $ 这表示当前字符可以被包含在LCS中，所以我们加1。

当 $X[i-1] \neq Y[j-1]$（即当前字符不同）时： $ dp[i][j] = (dp[i-1][j], dp[i][j-1]) $ 这表示我们需要在不包含当前字符的情况下继续查找LCS，即取上方或左方的较大值。

初始化：

初始化 dp 数组的第一行和第一列为0，因为任一序列与空序列的LCS长度为0： $ dp[0][j] = 0 j = 0 n $ $ dp[i][0] = 0 i = 0 m $

构建DP表：

通过嵌套循环填充整个 dp 数组，从 dp[1][1] 开始到 dp[m][n]。

结果：

最终的LCS长度存储在 dp[m][n] 中。

重建LCS（可选）：

通过 dp 表，可以反向重建LCS字符串。通过从 dp[m][n] 开始向上和向左回溯来找到参与构成LCS的字符。

此里程碑的目标是通过动态规划实现 LCS。

步骤：

创建一个函数 lcs，接收两个行的向量，并返回一个 Grid（用于存储 LCS 的长度）。

fn lcs(X: &[String], Y: &[String]) -> Grid {
    let m = X.len();
    let n = Y.len();
    let mut C = Grid::new(m + 1, n + 1);
    
    for i in 0..=m {
        C.set(i, 0, 0).unwrap();
    }
    for j in 0..=n {
        C.set(0, j, 0).unwrap();
    }

    for i in 0..m {
        for j in 0..n {
            if X[i] == Y[j] {
                C.set(i + 1, j + 1, C.get(i, j).unwrap() + 1).unwrap();
            } else {
                let val1 = C.get(i + 1, j).unwrap();
                let val2 = C.get(i, j + 1).unwrap();
                C.set(i + 1, j + 1, val1.max(val2)).unwrap();
            }
        }
    }
    C
}

测试实现：运行 cargo test test_lcs -- --nocapture。

unwrap()

unwrap() 是一个用于解包 Result 类型的方法。它将 Result 解包为内部的值。如果 Result 是 Err，它会引发恐慌（panic），即程序会崩溃并显示错误信息。

使用 unwrap() 时，开发者表示他们对该操作成功的信心，或是在开发和测试阶段希望快速捕获错误。

里程碑 4：使用 LCS 构建完整的 diff

在主函数中，将所有部分组合在一起。

步骤：

调用 read_file_lines 读取两个文件。
调用 lcs 计算 LCS 的 Grid。
实现 print_diff 函数，用于打印 diff 输出。

fn print_diff(C: &Grid, X: &[String], Y: &[String], i: usize, j: usize) {
    if i > 0 && j > 0 && X[i - 1] == Y[j - 1] {
        print_diff(C, X, Y, i - 1, j - 1);
        println!("  {}", X[i - 1]);
    } else if j > 0 && (i == 0 || C.get(i, j - 1).unwrap() >= C.get(i - 1, j).unwrap()) {
        print_diff(C, X, Y, i, j - 1);
        println!("> {}", Y[j - 1]);
    } else if i > 0 && (j == 0 || C.get(i, j - 1).unwrap() < C.get(i - 1, j).unwrap()) {
        print_diff(C, X, Y, i - 1, j);
        println!("< {}", X[i - 1]);
    }
}

// 主函数示例
fn main() {
    let file1 = read_file_lines("file1.txt").expect("无法读取文件1");
    let file2 = read_file_lines("file2.txt").expect("无法读取文件2");
    
    let C = lcs(&file1, &file2);
    print_diff(&C, &file1, &file2, file1.len(), file2.len());
}