排序复选制

登录 cs50.dev, 点击你的终端窗口，然后执行 cd 本身。你应该发现你的终端窗口的提示符类似于下面所示:

$

接下来执行

wget https://cdn.cs50.net/2026/x/psets/3/runoff.zip

以下载一个名为 runoff.zip 的 ZIP 压缩包到你的 codespace 中.

然后执行

unzip runoff.zip

来创建一个名为 runoff 的文件夹。你不再需要这个 ZIP 文件了，所以你可以执行

rm runoff.zip

然后在提示符后输入 “y” 并按回车，以删除你下载的 ZIP 文件.

现在输入

cd runoff

然后按回车键，将你自己移至（即打开）该目录。你的提示符现在应类似于下面所示.

runoff/ $

如果一切顺利，你应该执行

ls

并看到一个名为 runoff.c 的文件。执行 code runoff.c 应该会打开一个文件，你将在其中输入本题的代码。如果没有，请回溯你的步骤，看看能否找出哪里出错了!

当你需要扩展现有代码的功能时，最好首先确保理解它当前的状态.

首先看 runoff.c 的顶部。定义了两个常量：MAX_CANDIDATES 表示选举中候选人的最大数量，MAX_VOTERS 表示选举中选民的最大数量.

// Max voters and candidates
#define MAX_VOTERS 100
#define MAX_CANDIDATES 9

注意 MAX_CANDIDATES 用于确定数组 candidates 的大小.

// Array of candidates
candidate candidates[MAX_CANDIDATES];

candidates 是一个 candidate 的数组。在 runoff.c 中，一个 candidate 是一个 struct。每个 candidate 都有一个 string 字段表示其 name，一个 int 表示他们当前拥有的 votes 数，以及一个名为 eliminated 的 bool 值，表示该候选人是否已被淘汰出选举。数组 candidates 将跟踪选举中的所有候选人.

// Candidates have name, vote count, eliminated status
typedef struct
{
    string name;
    int votes;
    bool eliminated;
}
candidate;

现在可以更好地理解 preferences，即二维数组。数组 preferences[i] 将表示选民编号 i 的所有偏好。整数 preferences[i][j] 将存储来自 candidates 数组中作为选民 i 的第 j 偏好候选人的索引.

// preferences[i][j] is jth preference for voter i
int preferences[MAX_VOTERS][MAX_CANDIDATES];

程序还有两个全局变量：voter_count 和 candidate_count.

// Numbers of voters and candidates
int voter_count;
int candidate_count;

现在来看 main。注意，在确定候选人的数量和选民的数量之后，主投票循环开始运行，给每位选民提供了投票机会。当选民输入他们的偏好时，vote 函数被调用以跟踪所有偏好。如果在任何时候选票被判定为无效，程序将退出.

一旦所有选票统计完毕，另一个循环开始：这个循环将持续执行排序复选制的过程——检查是否有获胜者并淘汰排名最后的候选人，直到产生获胜者.

这里第一个调用的是名为 tabulate 的函数，它应查看所有选民的偏好并计算当前投票总数，方法是查看每位选民尚未被淘汰的首选候选人。接下来，print_winner 函数应打印出获胜者（如果有的话）；如果有，程序就结束了。否则，程序需要确定仍在选举中的任何候选人获得的最少票数（通过调用 find_min）。如果结果是选举中的所有人都以相同的票数打平（由 is_tie 函数确定），则选举被宣布为平局；否则，排名最后的候选人（们）通过调用 eliminate 函数被淘汰.

如果你往文件更下方看，你会看到其余的函数——vote、tabulate、print_winner、find_min、is_tie 和 eliminate——都留给你来完成! 你应该只修改 runoff.c 中的这些函数，不过如果你想的话，可以在 runoff.c 顶部 #include 额外的头文件.

完成 vote 函数.

• 该函数接受三个参数：voter、rank 和 name.
• 如果 name 与某个有效候选人的名字匹配，那么你应该更新全局 preferences 数组，以表示选民 voter 将该候选人作为其第 rank 偏好。请记住 0 是第一偏好，1 是第二偏好，依此类推。你可以假设没有两个候选人会有相同的名字.
• 如果偏好被成功记录，函数应返回 true。否则函数应返回 false。例如，考虑当 name 不是其中一个候选人的名字时.

在编写代码时，请考虑以下提示:

• 回想一下 candidate_count 存储了选举中的候选人数量.
• 回想一下你可以使用 strcmp 来比较两个字符串.
• 回想一下 preferences[i][j] 存储了作为第 i 位选民第 j 排序偏好的候选人的索引.

完成 tabulate 函数.

• 该函数应更新每位候选人在排序复选当前阶段的 votes 数量.
• 回想一下，在排序复选的每个阶段，每位选民实际上是投票给他们尚未被淘汰的最偏好候选人.

在编写代码时，请考虑以下提示:

• 回想一下 voter_count 存储了选举中的选民数量，并且对于我们选举中的每位选民，我们要计算一张选票.
• 回想一下，对于选民 i，他们的首选候选人由 preferences[i][0] 表示，第二选择候选人由 preferences[i][1] 表示，依此类推.
• 回想一下 candidate struct 有一个名为 eliminated 的字段，如果候选人已被淘汰，该字段将为 true.
• 回想一下 candidate struct 有一个名为 votes 的字段，你可能需要为每位选民偏好的候选人更新该字段.
• 回想一下，一旦你为某位选民的首位未被淘汰的候选人投了票，你应该就此停止，而不继续往下检查他们的选票。你可以在条件语句中使用 break 来提前跳出循环.

完成 print_winner 函数.

• 如果任何候选人获得了超过半数的选票，应打印其名字，并且函数应返回 true.
• 如果还没有人赢得选举，函数应返回 false.

在编写代码时，请考虑这个提示:

• 回想一下 voter_count 存储了选举中的选民数量。鉴于此，你如何表示赢得选举所需的票数?

完成 find_min 函数.

• 该函数应返回仍在选举中的任何候选人的最低得票总数.

在编写代码时，请考虑这个提示:

• 你可能需要遍历候选人，找到一位既仍在选举中又得票最少的候选人。在遍历候选人时你应该跟踪哪些信息?

完成 is_tie 函数.

• 该函数接受一个参数 min，它将是选举中任何人当前拥有的最低票数.
• 如果选举中剩余的每位候选人都拥有相同数量的票数，该函数应返回 true，否则应返回 false.

在编写代码时，请考虑这个提示:

• 回想一下，当选举中仍在场的每位候选人拥有相同数量的票数时，就会发生平局。还要注意，is_tie 函数接受一个参数 min，这是任何候选人当前拥有的最低票数。你如何使用 min 来判断选举是否为平局（或者，反过来，不是平局）?

完成 eliminate 函数.

• 该函数接受一个参数 min，它将是选举中任何人当前拥有的最低票数.
• 该函数应淘汰拥有 min 票数的候选人（们）.