PTA数据结构刷题笔记：用C语言手撕奥运排行榜（附完整代码与避坑指南）

从零实现奥运排行榜：C语言数据结构实战与PTA解题精要

当我在PTA上第一次遇到这道奥运排行榜题目时，那种既熟悉又陌生的感觉让我印象深刻——熟悉的是排序算法的基本框架，陌生的是如何将多个排序逻辑优雅地整合并处理实际业务中的边界条件。这道题完美融合了结构体设计、快速排序实现和实际业务逻辑处理，是检验C语言数据结构掌握程度的绝佳试金石。

1. 问题分析与数据结构设计

奥运排行榜问题的核心在于根据四种不同的排序规则（金牌数、奖牌数、人均金牌数、人均奖牌数）动态计算每个国家的最有利排名。我们需要设计一个能够容纳这些信息的数据结构。

typedef struct { int id; // 国家编号 int gold; // 金牌数 int medal; // 奖牌数 int population; // 人口数（百万） double gold_per_capita; // 人均金牌数 double medal_per_capita; // 人均奖牌数 } Country;

关键设计考虑：

• 使用id字段保持原始国家编号，避免排序后丢失原始信息
• 将人均计算字段设计为double类型以确保精度
• 在输入阶段就计算好人均值，避免后续重复计算

提示：结构体字段命名要清晰表达业务含义，避免使用缩写如"Gold"而应使用"gold_count"这样的完整形式，这在复杂系统中尤为重要。

2. 四种排序算法的实现策略

题目要求实现四种排序方式，但直接写四个排序函数会导致大量重复代码。更优雅的方式是使用函数指针和比较回调：

int compare_gold(const void *a, const void *b) { const Country *ca = (const Country *)a; const Country *cb = (const Country *)b; return cb->gold - ca->gold; // 降序排列 } // 其他三种比较函数类似... void quick_sort(Country arr[], int low, int high, int (*compare)(const void *, const void *)) { if (low >= high) return; Country pivot = arr[low]; int i = low, j = high; while (i < j) { while (i < j && compare(&arr[j], &pivot) >= 0) j--; arr[i] = arr[j]; while (i < j && compare(&arr[i], &pivot) <= 0) i++; arr[j] = arr[i]; } arr[i] = pivot; quick_sort(arr, low, i - 1, compare); quick_sort(arr, i + 1, high, compare); }

性能优化点：

• 使用函数指针实现策略模式，避免代码重复
• 在原数组上操作，减少内存占用
• 采用经典的Hoare分区方案提升效率

3. 并列排名处理的精妙之处

实际奥运排行榜中，成绩相同的国家应该获得相同名次，这是许多初学者容易忽略的细节。我们需要在排序后正确处理并列情况：

void process_ranking(Country countries[], int n) { for (int i = 1; i < n; i++) { if (countries[i].gold == countries[i-1].gold) { // 处理金牌数相同的情况 // 实际排名应该与前一个国家相同 } } }

并列处理算法步骤：

1. 对数组进行降序排序
2. 初始化第一个元素的排名为1
3. 遍历后续元素：
   • 如果当前元素与前一元素比较值相同，则排名相同
   • 否则排名为当前索引+1
4. 记录每个国家在每种排序方式下的排名

4. 查询优化与最终解决方案

最初的直觉可能是预先计算所有排名方式然后缓存结果，但题目要求"对每个前来咨询的国家按照对其最有利的方式计算它的排名"，这意味着我们需要为每个查询动态计算：

void process_query(Country countries[], int n, int query_id) { int best_rank = n + 1; // 初始化为最差排名 int best_method = 0; // 尝试四种排序方式 for (int method = 1; method <= 4; method++) { sort_by_method(countries, n, method); int current_rank = calculate_rank(countries, n, query_id, method); if (current_rank < best_rank || (current_rank == best_rank && method < best_method)) { best_rank = current_rank; best_method = method; } } printf("%d:%d", best_rank, best_method); }

关键突破点：

• 每次查询都需要重新排序，不能依赖缓存
• 四种排序是独立的，需要分别处理
• 当排名相同时选择编号小的计算方式

5. 实战中的坑与调试技巧

在PTA提交时，我遇到了两个监测点无法通过的情况，经过仔细排查发现：

1. 人口为零的处理：当人口数据为零时，人均计算会导致除零错误。解决方案：

   if (country[i].population == 0) { country[i].gold_per_capita = 0; country[i].medal_per_capita = 0; } else { country[i].gold_per_capita = (double)country[i].gold / country[i].population; country[i].medal_per_capita = (double)country[i].medal / country[i].population; }

2. 排名输出格式：PTA对输出格式要求严格，最后一个结果后不能有空格。解决方案：

   for (int i = 0; i < m; i++) { process_query(countries, n, queries[i]); if (i < m - 1) printf(" "); // 非最后一个元素添加空格 }

调试建议：

• 使用小规模测试数据验证边界条件
• 打印中间结果检查排序是否正确
• 对每个函数进行单元测试

6. 完整代码实现与架构分析

将上述各部分组合起来，我们得到完整的解决方案：

#include <stdio.h> #include <stdlib.h> typedef struct { int id; int gold; int medal; int population; double gold_per_capita; double medal_per_capita; } Country; // 四种比较函数 int compare_gold(const void *a, const void *b) { /* 实现略 */ } // 其他比较函数... void sort_countries(Country arr[], int n, int method) { switch (method) { case 1: qsort(arr, n, sizeof(Country), compare_gold); break; // 其他case... } } int get_rank(Country arr[], int n, int id, int method) { /* 实现略 */ } int main() { int n, m; scanf("%d %d", &n, &m); Country countries[n]; // 初始化countries数组... int queries[m]; // 读取查询... for (int i = 0; i < m; i++) { int best_rank = n + 1; int best_method = 0; for (int method = 1; method <= 4; method++) { sort_countries(countries, n, method); int current_rank = get_rank(countries, n, queries[i], method); if (current_rank < best_rank || (current_rank == best_rank && method < best_method)) { best_rank = current_rank; best_method = method; } } printf("%d:%d", best_rank, best_method); if (i < m - 1) printf(" "); } return 0; }

代码架构亮点：

1. 清晰的模块划分：数据结构、排序、排名计算各司其职
2. 使用标准库的qsort替代手写快排，减少出错概率
3. 主逻辑简洁明了，易于理解和维护

7. 算法优化与进阶思考

虽然上述方案能够AC题目，但从算法角度仍有优化空间：

1. 排序优化：四种排序有大量重复操作，可以考虑：

   • 预先计算并存储四种排序结果
   • 使用更高效的排序算法如归并排序

2. 查询优化：当查询次数M很大时（接近N），可以考虑：

   • 建立倒排索引，预先计算每个国家在四种排序中的位置
   • 使用更高效的数据结构如跳表

3. 并行计算：四种排序相互独立，可以并行处理：

   #pragma omp parallel for for (int method = 1; method <= 4; method++) { sort_countries(countries_copy[method-1], n, method); }

复杂度分析：

• 时间复杂度：O(M*NlogN) （M次查询，每次4次排序）
• 空间复杂度：O(N) （存储国家数据）

在实际开发中遇到类似问题时，这种权衡时间与空间、代码复杂度与运行效率的思考方式，比单纯解出题目更有价值。