1. 项目概述
这个C++编程练习题目来自东华OJ平台的基础题库,编号111。题目要求我们编写一个程序来统计多个候选人在选举中获得的票数。这类题目在编程初学者练习数组和字符串处理时非常典型,也是实际开发中常见的需求场景。
作为计算机专业学生或编程自学者,掌握这类基础算法题的解法非常重要。它不仅考察了基本的编程语法掌握程度,更能训练我们分析问题、设计算法的能力。在实际工作中,类似的统计功能在各种系统中都很常见,比如投票系统、问卷调查系统、用户偏好统计等。
2. 题目需求解析
2.1 题目具体要求
根据东华OJ平台的题目描述,我们需要实现以下功能:
-
输入部分:
- 第一行输入候选人人数n
- 接下来n行输入候选人姓名
- 然后输入投票人数m
- 接下来m行输入投票人选择的候选人姓名
-
输出部分:
- 按输入顺序输出每位候选人姓名及其得票数
- 最后一行输出无效票数(即投票给不存在的候选人的票数)
2.2 输入输出示例
假设输入:
code复制3
张三
李四
王五
5
张三
王五
李四
赵六
张三
预期输出:
code复制张三:2
李四:1
王五:1
Invalid:1
2.3 核心算法分析
这个题目主要考察以下几个编程知识点:
- 数组或结构体的使用(存储候选人信息)
- 字符串处理(比较候选人姓名)
- 循环结构(遍历投票记录)
- 条件判断(验证投票有效性)
3. 解决方案设计
3.1 数据结构选择
对于这种统计问题,我们需要选择合适的数据结构来存储候选人信息。常见的选择有:
-
结构体数组:
cpp复制struct Candidate { string name; int votes; }; Candidate candidates[100]; -
两个平行数组:
cpp复制string names[100]; int votes[100]; -
STL容器(如vector和map):
cpp复制vector<pair<string, int>> candidates; // 或 map<string, int> candidateMap;
对于初学者来说,结构体数组是最直观的选择。它把候选人姓名和票数绑定在一起,逻辑清晰,易于理解。
3.2 算法流程设计
完整的算法流程可以分为以下几个步骤:
- 读取候选人数量n
- 循环读取n个候选人姓名,初始化票数为0
- 读取投票人数m
- 循环处理m张选票:
a. 读取投票人选择的姓名
b. 在所有候选人中查找匹配的姓名
c. 如果找到,对应候选人票数+1
d. 如果未找到,无效票数+1 - 输出所有候选人姓名及其票数
- 输出无效票数
3.3 边界条件考虑
在实际编程中,我们需要考虑以下边界情况:
- 候选人数量n为0的情况
- 投票人数m为0的情况
- 候选人姓名包含空格的情况(题目通常说明姓名不包含空格)
- 候选人姓名区分大小写的情况(题目通常说明区分大小写)
- 大量数据时的性能问题(本题通常n和m不超过100)
4. 代码实现详解
4.1 基础版本实现
以下是使用结构体数组的基础实现代码:
cpp复制#include <iostream>
#include <string>
using namespace std;
struct Candidate {
string name;
int votes;
};
int main() {
int n, m;
Candidate candidates[100];
int invalid = 0;
// 读取候选人信息
cin >> n;
for (int i = 0; i < n; i++) {
cin >> candidates[i].name;
candidates[i].votes = 0;
}
// 处理投票
cin >> m;
for (int i = 0; i < m; i++) {
string vote;
cin >> vote;
bool found = false;
for (int j = 0; j < n; j++) {
if (candidates[j].name == vote) {
candidates[j].votes++;
found = true;
break;
}
}
if (!found) {
invalid++;
}
}
// 输出结果
for (int i = 0; i < n; i++) {
cout << candidates[i].name << ":" << candidates[i].votes << endl;
}
cout << "Invalid:" << invalid << endl;
return 0;
}
4.2 使用STL的优化版本
对于已经掌握STL的学习者,可以使用map来简化查找过程:
cpp复制#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;
int main() {
int n, m;
vector<string> names;
map<string, int> votesMap;
int invalid = 0;
// 读取候选人信息
cin >> n;
for (int i = 0; i < n; i++) {
string name;
cin >> name;
names.push_back(name);
votesMap[name] = 0;
}
// 处理投票
cin >> m;
for (int i = 0; i < m; i++) {
string vote;
cin >> vote;
if (votesMap.find(vote) != votesMap.end()) {
votesMap[vote]++;
} else {
invalid++;
}
}
// 输出结果
for (const auto& name : names) {
cout << name << ":" << votesMap[name] << endl;
}
cout << "Invalid:" << invalid << endl;
return 0;
}
这个版本利用了map的快速查找特性,时间复杂度从O(nm)降低到O(mlog n)。
4.3 关键代码解析
-
候选人信息存储:
- 基础版本使用结构体数组,保持输入顺序
- STL版本使用vector保持顺序,map存储票数
-
投票处理:
- 基础版本使用线性查找,适合数据量小的情况
- STL版本使用map的find方法,查找效率更高
-
无效票统计:
- 两种版本都使用一个计数器记录未匹配的投票
-
结果输出:
- 严格按照输入顺序输出,保持题目要求
5. 测试与验证
5.1 测试用例设计
为了确保程序的正确性,应该设计以下几类测试用例:
-
正常情况:
code复制
3 张三 李四 王五 5 张三 王五 李四 赵六 张三 -
无无效票:
code复制2 Alice Bob 3 Alice Bob Alice -
全部无效票:
code复制2 A B 3 C D E -
边界情况:
- 候选人数量为0
- 投票人数为0
- 候选人数量很大(接近100)
- 投票人数很多(接近100)
5.2 常见错误排查
在实现过程中,初学者常会遇到以下问题:
-
数组越界:
- 没有检查n和m的范围,可能导致数组访问越界
- 解决方法:确保数组大小足够(如题目说明n≤100)
-
字符串比较错误:
- 使用==比较字符串时,区分大小写
- 如果题目说明不区分大小写,需要统一转换大小写再比较
-
输出顺序错误:
- 使用map时,遍历map不会保持输入顺序
- 解决方法:额外维护一个vector保存原始顺序
-
未初始化变量:
- 忘记初始化票数为0
- 忘记初始化invalid计数器
6. 性能优化与扩展
6.1 算法复杂度分析
-
基础版本:
- 时间复杂度:O(n*m)(对于每张票,线性查找候选人)
- 空间复杂度:O(n)
-
STL版本:
- 时间复杂度:O(m*log n)(map查找为O(log n))
- 空间复杂度:O(n)
当n和m较小时(≤100),两种方法性能差异不大。但当数据量增大时,STL版本优势明显。
6.2 进一步优化方向
-
使用unordered_map:
- 平均查找时间为O(1),进一步优化性能
- 但需要处理可能的哈希冲突
-
并行处理:
- 对于极大数量的投票,可以考虑并行统计
- 需要��理线程安全问题
-
内存优化:
- 如果候选人姓名很长,可以考虑使用哈希值代替字符串比较
6.3 功能扩展思路
在实际应用中,可能需要扩展以下功能:
-
多轮投票:
- 支持多轮投票,统计每轮结果
- 需要增加时间维度数据
-
候选人信息扩展:
- 增加候选人年龄、性别、党派等信息
- 支持按不同条件统计
-
结果可视化:
- 生成柱状图或饼图展示投票结果
- 需要引入图形库
-
持久化存储:
- 将投票结果保存到文件或数据库
- 支持历史记录查询
7. 实际应用场景
虽然这是一个基础编程题目,但类似的统计功能在实际开发中非常常见:
-
在线投票系统:
- 论坛的帖子投票
- 活动的候选人投票
-
问卷调查系统:
- 统计各个选项的选择次数
- 分析用户偏好
-
电商平台:
- 统计商品被加入购物车的次数
- 分析用户行为
-
游戏开发:
- 统计玩家选择的角色或道具
- 平衡游戏设计
掌握这种基础的统计功能,是开发更复杂系统的基础。通过这个练习,可以培养以下实际开发能力:
- 数据建模能力(选择合适的数据结构)
- 业务逻辑实现能力(准确实现统计需求)
- 边界条件处理能力(考虑各种异常情况)
- 性能优化意识(选择更高效的算法)
8. 学习建议与进阶路径
对于想要进一步提升编程能力的学习者,建议:
-
同类题目练习:
- 统计字符串中各个字符出现的次数
- 统计一组数字中各个数字出现的频率
- 统计学生成绩分布
-
数据结构学习:
- 深入学习哈希表原理
- 了解各种容器的特点和使用场景
-
算法进阶:
- 学习更高效的查找算法
- 了解并行计算和分布式统计
-
实际项目实践:
- 开发一个简单的投票系统
- 实现一个问卷调查统计功能
这个题目虽然简单,但包含了编程中的许多基础概念。通过不断练习类似的题目,可以扎实掌握编程基础,为学习更复杂的内容做好准备。
