CS61C Lab 攻略：从入门到升天

一、简介

CS61C 主要内容为计算机组成原理，重难点是实验（Lab）和项目（Project），当然课程的精华也是实验和项目。
本文是对 CS61C 的实验进行分析思考和总结，为项目做好铺垫。

二、Lab 0：整装待发

2.1 配置开发环境

git clone https://github.com/61c-teach/sp23-lab-starter/
cd sp23-lab-starter/lab0

首先是配置开发环境，我们不是 Berkeley 学生，很多环境是无法配置的，比如 gradescope 自动评分。
但课程代码全开源，我们只要把代码克隆下来，就能开始愉快地练习了。

2.2 小试牛刀

def fizzbuzz(num):
    if multiple of 15: # edit this line
    # print num: fizzbuzz
    elif multiple of 3: # edit this line
    # print num: fizz
    elif multiple of 5: # edit this line
    # print num: buzz

for i in range(1, 20):
  fizzbuzz(i)

课程提供了一个 Python 伪代码文件，修改它输出正确结果即通关，帮助大家快速上手。

def fizzbuzz(num):
    if num % 15 == 0:
        print(f"{num}: fizzbuzz")
    elif num % 3 == 0:
        print(f"{num}: fizz")
    elif num % 5 == 0:
        print(f"{num}: buzz")

for i in range(1, 20):
    fizzbuzz(i)

我们使用了取余运算符 % 来判断一个数字是否是另一个数字的倍数。

如果一个数字能被 3 和 5 同时整除（即能被 15 整除），则打印 “fizzbuzz”；

如果一个数字能被 3 整除，则打印 “fizz”；

如果一个数字能被 5 整除，则打印 “buzz”。

2.3 小结

至此，预热阶段正式结束，即将开启 C 语言大门。值得注意的是，CS61C 不会再练习 C 语言编程基础，而是深入到指针、内存等偏底层的技术中。

三、Lab 1：进击 C 语言

3.1 编译 hello world C

#include <stdio.h>

int main() {
  printf("Hello World\n");

  return 0;
}

cd lab01
gcc -o ex1 ex1_hello.c
./ex1

这串命令使用 gcc 编译运行了 C 代码，输出了"Hello World"。这里我们加入了一个 -o ex1 参数，表示输出文件名为 ex1 。./ex1 表示这执行这个程序。

我们平常大多用 IDE 去点击按钮编译运行，CS61C 却选择命令行编译运行，这主要是因为命令行占用资源少。

3.2 遇见指针

#include <stdio.h>

int main() {
  // Assign x (an integer) to 5
  int x = 5;

  // TODO: create a pointer to x
  // Hint: the first blank should be a variable type
  //       the second blank should be the address of x
  int* pointer_to_x = &x;

  // This line should print 5
  printf("%d\n", *pointer_to_x);

  return 0;
}

这段代码中要注意指针类型 int * 和取地址操作 &x 、和取值操作 *pointer_to_x。

3.3 堆和栈上的指针

#include <stdio.h>
#include <stdlib.h>

int* int_on_stack() {
  // Allocates memory on the stack for an integer
  int x = 5;

  // Returns a pointer that points to the number 5
  return &x;
}

int* int_on_heap() {
  // TODO: allocate memory on the heap for an integer
  int* ptr_to_5 = malloc(sizeof(int));

  // TODO: store the number 5 in memory you just allocated
  *ptr_to_5 = 5;

  // Returns a pointer that points to the number 5
  return ptr_to_5;
}

int main() {
  int* ptr_to_stack = int_on_stack();
  int* ptr_to_heap = int_on_heap();

  printf("ptr_to_stack is the address %p\n", ptr_to_stack);
  printf("ptr_to_heap is the address %p\n", ptr_to_heap);

  return 0;
}

不难发现，栈上的指针不需要malloc申请空间，堆上的指针需要申请空间。

双重指针

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int id;
    char* name;
} Student;

Student* create_student_1(int id) {
  // TODO: allocate memory to store a Student struct
  Student* student_ptr = malloc(sizeof(Student));

  // TODO: set student_ptr's id to the id argument of this function
  student_ptr->id = id;

  return student_ptr;
}

void create_student_2(Student** student_double_ptr, int id) {
  // TODO: fill the space that student_double_ptr points to with the address of
  //       some memory large enough for a Student struct
  // Hint: you may need to use the dereference operator here
  *student_double_ptr = malloc(sizeof(Student));

  // TODO: set student_double_ptr's id to the id argument of this function
  (*student_double_ptr)->id=id;
}


int main() {
  // TODO: use create_student_1 to create a pointer to a Student struct
  //       where the student has id of 5
  Student* student1_ptr = create_student_1(5);

  // TODO: print the id of the student that student1_ptr points to
  printf("Student 1's ID: %d\n", student1_ptr->id);

  // TODO: create a pointer that can point to a Student struct
  //       do not allocate any memory
  Student* student2_ptr;

  // TODO: use create_student_2 to populate the student2_ptr
  //       where the student has id of 6
  // Hint: compare the type of student2_ptr with the type of
  //       the argument for create_student_2
  create_student_2(&student2_ptr, 6);

  // TODO: print the id of the student that student2_ptr points to
  printf("Student 2's ID: %d\n", student2_ptr->id);

  return 0;
}

双指针即指向指针的指针，可以直接改变原指针指向的数据结构。
为什么需要双重指针，我们来看一个例子。
程序1

void change(char* p)  
{
    p = "bbb";
}
int main(int argc, char* argv[])
{
    char *v = "aaa";
    change(v);
    printf("%s",v);
    return 0;
}

我们发现输出的结果仍然是aaa。

对它进行修改：

程序2

void change(char** p)
{
    *p = "bbb";
}
 
int main(int argc, char* argv[])
{
    char *v = "aaa";
    change(&v);
   printf("%s",v);    
   return 0;
}

此时输出的结果为bbb.

分析：
出现以上现象的原因是因为这个函数调用的时候，这个指针作为参数传递问题。程序1中，实际上，当我们调用函数change，把指针charv，当做参数传入的时候，这里还隐藏了一个赋值的操作，也就是说，传入到change函数中的是另外某个参数char x，x=v；所以说最后改变的只不过是x，v指向的东西并没有改变，所以输出来，还是aaa。如下图所示：

在程序2,操作过程中，指针v本身的地址值始终没有改变，改变的是指针v所指向的地址变化了。它不再指向”aaa”所在的地址，而是”bbb”所在的地址。如下图所示：

总结：
当指针作为函数参数传递的时候，如果想改变指针所指向的地址，比如想把char*v，从指向“aaa”转到指向“bbb”，那么需要采用双重指针传递的方式。或者说想通过调用函数的方式，给指针用malloc 分配新的地址的时候，也需要采用双重指针，才能实现真正的分配，否则是分配不成功的。

而如果只是想改变，指针所指向的地址里面的内容的时候，则采用单重指针就可以了，比如想把“aaa”改成“aab”，那么直接用单重指针传递就ok了，因为指针指向的地址不需要改变。代码就应该写成，如下：

程序3

void change(char* p)  
{
    *(p+2) = 'b';
}
int main(int argc, char* argv[])
{
    char *v = "aaa";
    change(v);
    printf("%s",v);
    return 0;
}

如下图：