CS50 Runoff问题中vote()与tabulate()函数运行逻辑答疑

先理清楚题目预先定义的两个核心数据结构，这是理解逻辑的前提：

• candidates是结构体数组，每个元素对应一个候选人，包含三个属性：name（姓名）、votes（当前轮次得票数）、eliminated（是否已被淘汰的布尔标记），数组的下标就是对应候选人的唯一ID
• preferences是全局二维整型数组，维度为[voter_count][candidate_count]，存储所有选民的完整偏好排序，是排序复选制能支持多轮计票的核心

核心疑问解答 #

1. preferences二维数组如何与candidates结构体关联协同？ #

两者靠**候选人索引（ID）**做关联：preferences数组里不存候选人名字，也不存直接的票数，只存候选人在candidates数组里的下标值。拿到preferences里存储的整数后，直接把它当数组下标访问candidates，就能拿到对应候选人的全部状态（是否淘汰、当前得票等）。
两者分工完全独立：

• preferences是静态原始数据：所有选民的选票收集完成后，这个数组的内容就固定不变，不管后续多少轮淘汰、计票，每个人的偏好排序都不会修改
• candidates是动态计数据：每一轮计票前会先把所有候选人的votes清零，eliminated标记会随着淘汰流程逐轮更新，用来记录每一轮的实时计票结果和淘汰状态

2. preferences数组中voter、rank两个维度的作用逻辑是什么？ #

两个维度分别对应「选民身份」和「偏好优先级」：

• 第一维索引voter：对应选民编号，范围从0到voter_count-1，每个编号代表一个独立的投票人
• 第二维索引rank：对应偏好顺位，0代表最高优先级的第一选择，1代表第二选择，数字越大优先级越低
  举个实际例子：preferences[2][0] = 3的含义是：编号为2的选民，第一选择是编号为3的候选人；preferences[2][1] = 1就是同一个选民，第二选择是编号为1的候选人。

3. 为何vote()函数中要将候选人索引i赋值给preferences[voter][rank]，而非直接为votes计数、或是对preferences[i][j]做自增操作？ #

完全是排序复选制的规则要求：

• 首先vote()运行时还处于收集选票的阶段，根本没进入多轮计票环节，这时候直接计数毫无意义。排序复选制需要等所有选票全部收齐，才会从第一轮开始逐轮淘汰得票最低的候选人、转移被淘汰者的选票，不可能收一张票就计一次。
• 要是在vote()里直接给对应候选人的votes加一，后续轮次有候选人被淘汰时，你根本找不到哪些选民投了这个被淘汰的人、这些人的下一个选择是谁，完全没法完成选票转移的核心流程。
• 要是对preferences[i][j]做自增操作，存的内容就变成了「把i号候选人当第j选择的总人数」，这种结构下你没法定位单个选民的完整偏好链，转移选票时根本找不到哪些票需要流转，逻辑冗余、效率极低还容易出错。
  直接存储候选人索引的设计最简洁：给每个选民存好完整的偏好排序清单，原始数据收票后就固定不动，后面不管淘汰多少候选人，顺着每个人的偏好清单往下找第一个没被淘汰的候选人计票即可，逻辑通顺且不容易出bug。

逐段代码逻辑拆解 #

vote() 函数：登记单张选票的单条偏好 #

这个函数的调用时机是选票收集阶段：对每个选民填写的每个顺位的候选人名字，都会调用一次这个函数。三个入参分别是：当前处理的是第几个选民、当前填写的是第几顺位、当前顺位填写的候选人名字。

// 选票有效则记录偏好，返回true；无效返回false
bool vote(int voter, int rank, string name)
{
    // 遍历全部候选人，匹配传入的姓名
    for (int i = 0; i < candidate_count; i++)
    {
        if (strcmp(candidates[i].name, name) == 0)
        {
            // 姓名匹配成功：将当前候选人的索引i，存入对应选民、对应顺位的偏好位置
            preferences[voter][rank] = i;
            return true;
        }
    }
    // 遍历完所有候选人都没匹配到姓名，说明选票无效
    return false;
}

举个实际调用的例子：0号选民填写的第一顺位候选人名字是"Alice"，遍历后发现Alice在candidates数组的下标是2，就会执行preferences[0][0] = 2，代表0号选民的第一选择是2号候选人。

tabulate() 函数：当前轮次计票 #

这个函数的调用时机是每一轮淘汰候选人之后，用来重新统计当前轮次的有效票数。注意调用这个函数之前，代码会先把所有候选人的votes清零，避免上一轮的票数干扰当前轮次结果。

// 为未被淘汰的候选人统计当前轮次票数
void tabulate(void)
{
    // 第一层循环：遍历每一位选民
    for (int i = 0; i < voter_count; i++)
    {
        // 第二层循环：从最高顺位（rank=0）开始，查找该选民本轮的有效投票对象
        for (int j = 0; j < candidate_count; j++)
        {
            // 取出当前顺位对应的候选人索引
            int vote = preferences[i][j];
            // 如果该候选人未被淘汰，这张票就计给他
            if (!candidates[vote].eliminated)
            {
                candidates[vote].votes += 1;
                // 计票完成后跳出循环，不再统计该选民更低顺位的选择
                break;
            }
            // 如果当前顺位的候选人已被淘汰，自动进入下一轮循环，检查更低一级的顺位
        }
    }
    return;
}

举个计票例子：0号选民的偏好排序是[2,1,3]（第一选择2号、第二1号、第三3号），当前轮次2号候选人已经被淘汰，就会跳过j=0的位置，检查j=1对应的1号候选人，如果1号未被淘汰，就把这张票计给1号，不再检查j=2的3号候选人。 #

内容的提问来源于stack exchange，提问作者DinoNyte