题目描述
考察vector和hash的应用。
此题中对于某学生,其课程数目不一定,故可使用vector建立变长数组存放课程号
对任意一个学生来说,其姓名唯一,可建立hash规则为string匹配唯一id,大大提高效率
C++ 代码
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
//学生名hash函数,得到其名字的唯一表示数: A-Z看作26进制数字,id*26+[字母-'A']; 末尾0-9数字直接尾接
int hashfunc(string name) {
int id=0;
for(int i=0;i<name.length()-1;i++) {
id=id*26+(name[i]-'A');
}
id=id*10+(name[name.length()-1]-'0');
return id;
}
int main()
{
int stuNum,claNum;
cin>>stuNum>>claNum;
vector<int> vec[26*26*26*10];//三个字母+一个数字,共 26*26*26*10种情况 。行:学生id ; 列:变长int数组存放该生的课程号
//读入各课数据
for(int i=1;i<=claNum;i++){
int claNo,selectStuNo;//课程号,此课学生数
cin>>claNo>>selectStuNo;
for(int j=1;j<=selectStuNo;j++){//读入此课学生名单
string s;
cin>>s;
vec[hashfunc(s)].push_back(claNo);//将课程号claNo插入 对应的vec[id]
}
}
//读取最后一行学生名单 ,边读边输出该生结果
for(int i=0;i<stuNum;i++) {
string s;
cin>>s;
//输出 姓名和该生课程总数
cout<<s<<" "<<vec[hashfunc(s)].size();
//该生vec排序(sort默认增序)
sort(vec[hashfunc(s)].begin(),vec[hashfunc(s)].end());
//按序输出课程号
for(int j=0;j<vec[hashfunc(s)].size();j++){
cout<<" "<<vec[hashfunc(s)][j];
}
cout<<endl;
}
return 0;
}