CStudy

CS106L Assignments & Solutions

Assignment 1

题目概述

补写 main.cpp 代码使得代码能在 course.csv 文件中找出今年开设的课程和不开设的课程，并分别写入 student_output/courses_offered.csv 和 student_output/courses_not_offered.csv 两个文件中。

作业包中包含两个文件：

  • main.cpp ：你的代码应该补写在此。
  • utils.cpp ：包含作业过程中需要使用的函数，不需要修改。

Part 0：补写结构体元素类型 & 修改函数声明

  • 阅读代码，补写结构体 Courses 中三个元素的数据类型；
  • 阅读代码，修改主文件中三个函数的声明，使得能够正常运行。

Part 1：完成 parse.csv 函数

该函数的功能是：从 courses.csv 文件中读取课程信息，读取至由结构体 Courses 构成的 vector 容器里。

Part 2：完成 write_courses_offered 函数

该函数的功能是：将储存在 vector 容器里的课程中在本学期开设的课程（即该课程的 quarter 不为 null ）输出至文件 student_output/courses_offered.csv 中，并删除这些已输出的课程。

Part 3：完成 write_courses_not_offered 函数

该函数的功能是：将已删除已输出的课程的 vector 容器里的课程（即不会在本学期开设的课程）输出至文件 student_output/courses_not_offered.csv 中。

Solutions

Part 0.

所有元素的数据类型都应该是 std::string 。

三个函数都会对主函数的 courses 参数进行修改，因此三个函数的变量都应该加引用负号。

Part 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void parse_csv(std::string filename, std::vector<Course>& courses) {
  /* (STUDENT TODO) Your code goes here... */
  std::ifstream ifs(filename);
  if (!ifs.is_open()) {
    std::cout << "File couldn't be opened.";
    return;
  }
  std::string s;
  std::getline(ifs, s);
  while (std::getline(ifs, s)) {
    std::vector<std::string> cnt_course = split(s, ',');
    Course cnt;
    cnt.title = cnt_course[0];
    cnt.number_of_units = cnt_course[1];
    cnt.quarter = cnt_course[2];
    courses.push_back(cnt);
  }
  ifs.close();
  return;
}

Part 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void write_courses_offered(std::vector<Course>& all_courses) {
  /* (STUDENT TODO) Your code goes here... */
  std::ofstream ofs("student_output/courses_offered.csv", std::ios::trunc);
  if (!ofs.is_open()) {
    std::cout << "Cannot open the file.";
    return;
  }
  ofs << "Title,Number of Units,Quarter\n";
  std::vector<Course> output_courses;
  for (auto course : all_courses) {
    if (course.quarter != "null") {
      ofs << course.title << "," << course.number_of_units << "," 
          << course.quarter << "\n";
      output_courses.push_back(course);
    }
  }
  for (auto course : output_courses) {
    delete_elem_from_vector(all_courses, course);
  }
  ofs.close();
  return;
}

Part 3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void write_courses_not_offered(std::vector<Course>& unlisted_courses) {
  /* (STUDENT TODO) Your code goes here... */
  std::ofstream ofs("student_output/courses_not_offered.csv", std::ios::trunc);
  if (!ofs.is_open()) {
    std::cout << "Cannot open the file.";
    return;
  }
  ofs << "Title,Number of Units,Quarter\n";
  for (auto course : unlisted_courses) {
    ofs << course.title << "," << course.number_of_units << "," 
        << course.quarter << "\n";
  }
  ofs.close();
  return;
}

Assignment 2

题目概述

补写 main.cpp 代码，模拟 Stanford Marriage Pact 匹配流程：从 students.txt 中读取所有报名学生姓名，找出与自己姓名首字母相同的候选匹配对象，并从中选出最终匹配结果。

作业包中主要包含两个需要关注的文件：

  • main.cpp：你的代码应该补写在此。
  • short_answer.txt：用于回答作业中的简答题。

Part 0：修改个人姓名

  • 将 main.cpp 顶部的常量 kYourName 从默认值修改为自己的英文全名；
  • 姓名应包含 first name 和 last name，并用空格分隔。

Part 1：完成 get_applicants 函数

该函数的功能是：从 students.txt 文件中读取所有报名学生的姓名，并将这些姓名储存在 std::set 或 std::unordered_set 容器中。

同时需要在 short_answer.txt 中回答：std::set 和 std::unordered_set 的区别、取舍，以及如何为学生姓名设计一个合法的哈希函数。

Part 2：完成 find_matches 函数

该函数的功能是：遍历学生姓名集合，找出所有与给定姓名拥有相同首字母缩写的学生，并将这些学生姓名的指针存入一个 std::queue 队列中。

Part 3：完成 get_match 函数

该函数的功能是：从 find_matches 得到的候选匹配队列中选出一个最终匹配对象。如果队列为空，则返回或输出 "NO MATCHES FOUND."。

同时需要在 short_answer.txt 中回答：为什么这里保存的是姓名的指针而不是姓名本身，以及如果原来的姓名集合失效后继续使用这些指针会发生什么。

Solutions

Part 1.

1
2
3
4
5
6
7
8
9
10
11
12
std::set<std::string> get_applicants(std::string filename) {
  // STUDENT TODO: Implement this function.
  std::ifstream ifs(filename);
  std::set<std::string> applicants;
  std::string s;
  while (std::getline(ifs, s)) {
    if (!s.empty()) {
      applicants.insert(s);
    }
  }
  return applicants;
}

Q1：可以选择使用有序集合或无序集合。请用几句话说明二者之间的取舍。另外，请举一个课上没有讲过的、可以用于学生姓名的合法哈希函数例子。

std::set 会按照顺序储存元素，通常底层使用平衡二叉搜索树实现。因此，它的插入、删除和查找操作的时间复杂度是 O(log n)，但遍历时可以按照字母顺序得到元素。std::unordered_set 使用哈希表储存元素，因此插入、删除和查找操作在平均情况下是 O(1)，但元素没有固定的顺序。因此，如果需要有序遍历，std::set 更合适；如果更重视平均情况下更快的查找速度，std::unordered_set 更合适。

一种可行的学生姓名哈希函数是：将字符串中每个字符的 ASCII 值乘以它在字符串中的位置，然后把这些结果加起来。例如，对于一个姓名字符串 s，可以计算：

1
hash = s[0] * 1 + s[1] * 2 + s[2] * 3 + ...

这是一个合法的哈希函数，因为它能确定性地把同一个字符串转换成同一个数字。

Part 2.

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
bool get_initials(const std::string& full_name, char& first_initial, char& last_initial) {
  std::string::size_type first_pos = full_name.find_first_not_of(' ');
  if (first_pos == std::string::npos) {
    return false;
  }
  first_initial = full_name[first_pos];
  std::string::size_type space_pos = full_name.find(' ', first_pos);
  if (space_pos == std::string::npos) {
    return false;
  }
  std::string::size_type last_pos = full_name.find_first_not_of(' ', space_pos);
  if (last_pos == std::string::npos) {
    return false;
  }
  last_initial = full_name[last_pos];
  return true;
}
std::queue<const std::string*> find_matches(std::string name, 
                                            std::set<std::string>& students) {
  std::queue<const std::string*> matched;
  char my_first_initial;
  char my_last_initial;
  if (!get_initials(name, my_first_initial, my_last_initial)) {
    return matched;
  }
  for (const auto& str : students) {
    char curr_first_initial;
    char curr_last_initial;
    if (!get_initials(str, curr_first_initial, curr_last_initial)) {
      continue;
    }
    if (curr_first_initial == my_first_initial && 
        curr_last_initial == my_last_initial) {
      matched.push(&str);
    }
  }
  return matched;
}

Part 3.

1
2
3
4
5
6
std::string get_match(std::queue<const std::string*>& matches) {
  if (matches.empty()) {
    return "NO MATCHES FOUND.";
  }
  return *(matches.front()); //懒得想算法了先这样吧
}

Q2：注意，我们在队列中保存的是指向姓名的指针，而不是姓名本身。为什么在这个问题中这样做可能更合适？如果原来储存姓名的集合失效之后，再访问这些指针会发生什么？

保存指针而不是完整的字符串，可以避免把学生姓名再次复制到队列中。因为这些姓名已经储存在原来的集合里了，所以队列中只需要保存指向这些已有字符串的地址即可。这样在姓名较长或匹配人数较多时，可以节省一定的内存和复制开销。

但是，这种做法只有在原来的集合仍然存在时才是安全的。如果这个集合离开了作用域，集合中的所有字符串都会被销毁，队列中保存的指针就会变成悬空指针。之后如果继续访问这些指针，就会产生未定义行为，因为它们已经不再指向有效的字符串对象。

Assignment 3

题目概述

本作业要求我们自定义一个 C++ 类，并分别在头文件和源文件中完成类的声明与实现。该类可以表示任意对象，但需要满足若干基本要求：包含默认构造函数和带参数的自定义构造函数，具有私有成员变量和私有成员函数，并至少提供一个用于访问私有成员的 getter 函数和一个用于修改私有成员的 setter 函数。

作业包中主要包含四个需要修改或完成的文件：

  • class.h：用于编写自定义类的声明，包括成员变量、成员函数以及构造函数的声明。
  • class.cpp：用于编写类成员函数的具体实现，包括构造函数、getter、setter 和私有辅助函数等。
  • sandbox.cpp：用于在 sandbox 函数中创建该类的实例，测试类是否能够被正常构造和使用。
  • short_answer.txt：用于回答与 const 正确性相关的简答题。

Part 1：完成自定义类的声明与实现

该部分要求在 class.h 和 class.cpp 中设计并实现一个自定义类。类中需要包含至少一个私有成员变量、一个私有成员函数、一个默认构造函数、一个带参数的构造函数、一个 getter 函数和一个 setter 函数。其中，getter 函数应当被声明为 const 成员函数，以保证它只读取对象状态而不会修改对象内容。

Part 2：在 sandbox.cpp 中创建类的实例

该部分要求在 sandbox 函数中构造一个自定义类的对象实例。可以使用默认构造函数创建对象，也可以使用带参数的构造函数创建对象。该步骤用于确认类能够被正常实例化，并能够通过编译和运行测试。

Part 3：完成简答题

该部分要求在 short_answer.txt 中回答两个与 const 正确性有关的问题：一是解释什么是 const-correctness 以及它为什么重要；二是说明自己编写的类是否满足 const-correctness，并给出判断依据。

Solutions

Part 1.

以下是 class.h 的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector>

class Album {
private:
  std::string title;
  std::string artist;
  std::string genre;
  std::string release_time;
  std::vector<std::string> tracklist;
  std::string findTrack(int num) const;
public:
  Album();
  Album(std::string title, std::string artist, std::string genre, 
    std::string release_time, std::vector<std::string> tracklist);
  std::string getTitle() const;
  std::string getTrack(int num) const;
  void setTrack(int num, std::string trackname);
};

以下是 class.cpp 的代码：

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <vector>
#include "class.h"

Album::Album() {
    title = "Detour";
    artist = "Kim Petras";
    genre = "Pop";
    release_time = "29/05/2026";
    tracklist.push_back("Detour");
    tracklist.push_back("DTLA");
    tracklist.push_back("I Like Ur Look");
    tracklist.push_back("Check it");
    tracklist.push_back("Polo");
    tracklist.push_back("Brutalist");
    tracklist.push_back("Need for Speed");
    tracklist.push_back("Jeep");
    tracklist.push_back("101");
    tracklist.push_back("Basketball");
    tracklist.push_back("Bitch Ball Out");
    tracklist.push_back("Korea");
    tracklist.push_back("Freak it");
}

Album::Album(std::string title, std::string artist, std::string genre, 
             std::string release_time,std::vector<std::string> tracklist) 
{
    this->title = title;
    this->artist = artist;
    this->genre = genre;
    this->release_time = release_time;
    this->tracklist.clear();
    for (auto track : tracklist) {
        this->tracklist.push_back(track);
    }
}

std::string Album::findTrack(int num) const {
    if (num <= 0) return "NULL";
    int count = 0;
    for (auto it = tracklist.begin(); it != tracklist.end(); ++it) {
        count++;
        if (count == num) {
            return *it;
        }
    }
    return "NULL";
}

std::string Album::getTitle() const {
    return title;
}

std::string Album::getTrack(int num) const {
    return findTrack(num);
}

void Album::setTrack(int num, std::string trackname) {
    int count = 0;
    for (auto it = tracklist.begin(); it != tracklist.end(); ++it) {
        count++;
        if (count == num) {
            *it = trackname;
            return;
        }
    }
}

Part 2.

以下是 sandbox.cpp 的代码：

1
2
3
4
5
6
7
#include <iostream>
#include <vector>
#include "class.h"

void sandbox() {
  Album detour;
}

Part 3.

Q1：什么是 const-correctness？它为什么重要？

Const-correctness 指的是：当某个函数或对象不应该修改数据时，就用 const 对它进行标记。它很重要，因为这样可以让代码更加安全、清晰：其他程序员可以直接看出哪些函数只是读取对象内容，而编译器也可以帮助我们避免意外修改数据。

Q2：你的类满足 const-correctness 吗？你怎么知道？

是的，我的类满足 const-correctness，因为我的 getter 函数被标记为了 const，所以它们可以在不修改对象内容的情况下返回专辑信息。例如，getTitle() 和 getTrack() 只会读取私有成员变量，而 setTrack() 这样的 setter 函数才负责修改曲目列表。

About this Post

This post is written by Ezra Yang, licensed under CC BY-NC 4.0.

#C++ #solutions

Comments