赛事信息"/>
数构课设——管理赛事信息
预习目标:Day1
完成第一小问题:
能够管理各参赛队的基本信息(包含参赛队编号,参赛作品名称,参赛学校,赛事类别,参赛者,指导老师),赛事类别共11项(参见大赛官网jsjds.blcu.edu);包括增加、删除、修改参赛队伍的信息。
预习内容:
- 参赛队基本信息可以使用结构体(S)来表示
- 新增参赛队伍
- 删除参赛队伍的信息
- 修改参赛队伍的信息
- 二叉排序树查找参赛队伍信息
具体预习过程:
- 参赛队基本信息可以使用结构体(S)来表示,其中包含参赛队编号、参赛作品名称、参赛学校、赛事类别、参赛者和指导老师。以下是使用C++编写的参赛队基本信息的结构体代码:
struct Team {string id;// 参赛队编号string name; // 参赛作品名称string school; // 参赛学校string category; // 赛事类别string members; // 参赛者string coach; // 指导老师
};
上述代码中,Team
结构体包含了参赛队的信息,其中id
表示参赛队编号,name
表示参赛作品名称,school
表示参赛学校,category
表示赛事类别,members
表示参赛成员名单,coach
表示指导老师。在实际使用中,可以通过设置构造函数和成员函数等方法来实现对Team
结构体实例的初始化和访问。
- 新增参赛队伍
// 新增参赛队伍
void Event::addTeam(const string& id, const string& name, const string& school, const string& category, const string& member, const string& coach) {teams.push_back(Team{ id, name, school, category, member, coach }); // 将新的参赛队伍信息添加到队伍列表中
}
一定要记得在每次增删改后要“保存所变动后的信息”(后面会有saveToFile()函数)
- 删除参赛队伍的信息
//删除参赛队伍的信息
void Event::removeTeam(string id) {// 使用STL算法查找要删除的参赛队伍auto it = find_if(teams.begin(), teams.end(), [&](const Team& t) { return t.id == id; });if (it != teams.end()) {// 从队列中删除该参赛队伍teams.erase(it); }}
- 修改参赛队伍的信息
//修改参赛队伍的信息
void Event::updateTeam(const string& id, const string& name, const string& school, const string& category, const string& member, const string& coach) {// 使用STL算法查找要修改的参赛队伍auto it = find_if(teams.begin(), teams.end(), [&](const Team& t) { return t.id == id; });if (it != teams.end()) {// 修改参赛队伍信息it->name = name;it->school = school;it->category = category;it->member = member;it->coach = coach;}
}
- STL算法
STL(Standard Template Library)是C++标准库的一部分,它提供了一系列高效的通用数据结构和算法,可以大大提高C++程序的开发效率和运行速度。其中的算法部分涵盖了各种排序、查找、遍历、重排、合并等常见操作,这些算法通常被归为以下几类:
1. 排序算法:如sort(), stable_sort()等,可以对一个序列进行排序,其中sort()默认使用快速排序算法,而stable_sort()使用归并排序算法。
2. 查找和查找算法:如find(), find_if(), binary_search()等,可以根据指定条件在一个序列中查找想要的元素。
3. 算术算法:如accumulate(), inner_product(), partial_sum()等,可以对数字序列执行各种算术操作,如求和、求积、求部分和等。
4. 重排算法:如reverse(), rotate(), shuffle()等,可以对一个序列进行各种重排操作,如翻转、旋转、洗牌等。
5. 合并算法:如merge(), set_union(), set_intersection()等,可以将两个有序序列合并成一个,或者对两个有序序列执行交集、并集操作。
6. 访问算法:如for_each(), transform()等,可以对一个序列中的每个元素进行操作,如输出、转换等。
7. 堆和堆算法:如make_heap(), push_heap(), pop_heap()等,可以将一个序列转换为堆,并对堆进行各种操作,如插入、弹出等。
STL算法非常强大和灵活,每个算法都有适用的场景,可以大大增强开发者的编码能力。不仅如此,STL算法的优秀性能和易用性也帮助C++在业界得到广泛应用,并成为高性能系统的首选开发语言之一。
- saveToFile()函数
在删除一个队伍信息后,需要调用程序中的saveToFile()函数将更新后的teams向量重新写入team.txt文件中,以便后续可以从这个文件中正确地读取和操作队伍信息。
// 将队列中的队伍信息写入到文件中
void Event::saveToFile(const string& filename) {ofstream outfile(filename);if (outfile) {for (const auto& team : teams) {outfile << team.id << "#" << team.name << "#" << team.school << "#" << team.category << "#" << team.member << "#" << team.coach << endl;}cout << "保存成功!" << endl;}else {cout << "保存文件 " << filename << " 失败!" << endl;}
}
在该代码片段中,调用saveToFile()函数将更新后的信息写回文件中,这样就可以直接在team.txt文件中查看到更新后的参赛队伍信息了。
2.二叉排序树查找参赛队伍信息
二叉排序树(Binary Search Tree,BST)是一种特殊的二叉树,它具有以下性质:
1. 若左子树非空,则左子树上所有节点的值均小于根节点的值;
2. 若右子树非空,则右子树上所有节点的值均大于根节点的值;
3. 左右子树也分别为二叉排序树;
4. 没有键值相等的节点。
由于二叉排序树具有上述性质,我们可以利用它进行非常高效的查找、插入和删除操作。例如,对于一个有n个节点的二叉排序树,在平均和最坏情况下,查找、插入和删除操作的时间复杂度都为 O(log n)。
- 插入操作:将新节点插入二叉排序树的过程,需要从根节点出发,比较要插入节点的键值与当前节点的键值的大小关系,依次向左或右子树递归,直到空节点位置。
- 删除操作:删除指定节点的过程,需要涉及改变英文二叉树的结构,涉及两个场景:要删除的节点没有子节点和要删除的节点有一个子节点,或者要删除的节点有两个子节点。
- 查找操作:从根节点开始遍历BST,与当前节点的值进行比较大小,递归查找到要查找的节点。
总之,二叉排序树是一种非常实用的数据结构,在C++中可以很容易地通过构建节点结构和利用递归算法来实现。
void BST::searchHelper(TeamNode* current, string id, int depth) {if (current == nullptr) {cout << "查找失败!" << endl;return;}if (id == current->id) {cout << "基本信息:" << endl;cout << "作品名称:" << current->name << endl;cout << "参赛学校:" << current->school << endl;cout << "赛事类别:" << current->category << endl;cout << "参赛者:" << current->member << endl;cout << "指导老师:" << current->coach << endl;cout << "平均查找长度ASL:" << avgSearchLen() << endl;return;}else if (id < current->id) {searchHelper(current->left, id, depth + 1);}else {searchHelper(current->right, id, depth + 1);}
}
以上是以二叉链表为存储结构的查找参赛队伍信息的代码,平均查找长度ASL,直接return static_cast<double>(totalDepth) / size就行。
预习小结:
- 预习中的问题及思考:
- 目前删除,修改 程序只能删除,修改我新存入的信息,不能删除team.txt文件中原本的信息。
- 对于原本存放在team.txt文件中的信息不能进行查找,只能查找新录入的信息。
- 使用STL算法更加方便快捷的进行查找到指定元素在进行修改,删除等操作。
- 完成了对查找,删除,增加,修改的初步函数构建,需要再进一步调试。
- 对于“参赛编号”,先开始我是使用的int类型,但后面发现改为string类型也更为方便。两者均可。
解决预习中的问题:
- 删除操作:
//删除参赛队伍的信息 void Event::removeTeam(string id) {// 使用STL算法查找要删除的参赛队伍auto it = find_if(teams.begin(), teams.end(), [&](const Team& t) { return t.id == id; });if (it != teams.end()) {// 从队列中删除该参赛队伍teams.erase(it);}
贴出的代码只是将内存中的指定队伍信息从队列中删除,并没有更新文件中的内容。为了从文件中删除队伍信息,需要进行以下操作:
// 删除参赛队伍的信息 void Event::removeTeam(string id) {// 打开文件,读取所有数据到容器中ifstream fin(filename, ios::in);if (!fin.is_open()) {cout << "Failed to open file " << filename << "!" << endl;return;}vector<Team> teams; // 存储所有参赛队伍信息的容器string line;while (getline(fin, line)) {Team team;// 根据文件格式解析数据并存储至队列中if (parseTeamString(line, team)) {if (team.id != id) {teams.push_back(team);}}}fin.close(); // 关闭文件// 将容器中的数据重新写入到文件中ofstream fout(filename, ios::out);if (!fout.is_open()) {cout << "Failed to open file " << filename << "!" << endl;return;}for (auto it = teams.begin(); it != teams.end(); ++it) {fout << formatTeamString(*it) << endl; // 格式化输出到文件中}fout.close(); // 关闭文件 }
这样就可以进行删除工作了,这里再详细讲解一下为什么需要这样做:
例如我现在有一个本地文件,我想删除其中的某一行内容,在C++中,似乎没有对文本的行删除的功能,但是我们可以通过一个长字符串(存储容器)来解决这个问题:
思路如下:新建一个空字符串,将文本文件一行行读取,不需要删除的就按原来的顺序保存到字符串中,等读到需要删除的行的时候,将新的行保存到字符串中,原来的数据舍弃。然后继续保存后面的内容,直到整个文本读取完成。然后将文本清空,将新字符串保存进去。这样子就完成了某一行的删除。
- 修改也是同理
- 后续发现id还是改回int类型,这样就不会将“编号\t”中的“\t”读入了,否则无法比较“t.id==id”(会有\t扰乱计算机对其进行的比较,结果会输出!=),解决方法是调用stoi()函数(将string类型转换成int类型的函数)。
Day2
- 完善进行查找任务
学习计划:
- 解决输出乱码的问题
- 根据赛事学校等来查找相关信息
学习内容:
- 根据编号进行查询
- 以下是输出结果:
- 可以看出输出全为乱码
2.根据参赛学校或者参赛类别来查找
- 实验要求:C++编写代码实现能够提供按参赛学校查询参赛团队(或根据赛事类别查询参赛团队),即,根据提示输入参赛学校名称(赛事类别),若查找成功,输出该学校参赛的(该赛事类别的)所有团队的基本信息,输出的参赛团队按赛事类别有序输出。排序算法使用归并排序。
- 选用归并排序:归并排序是一种分治算法,它将待排序的序列分成若干个子序列,每个子序列都是有序的,然后再将这些有序的子序列合并成一个有序的序列。归并排序的时间复杂度为O(nlogn),因此它适用于处理大规模的数据集合。
- 代码实现:
// 按照赛事类别进行归并排序(使用模板函数) template <typename T> void merge_sort(vector<T>& data, int left, int right, bool compare(T, T)) {if (left < right) {int mid = (left + right) / 2;merge_sort(data, left, mid, compare);merge_sort(data, mid + 1, right, compare);// 合并两个有序序列int i = left, j = mid + 1;vector<T> temp;while (i <= mid && j <= right) {if (compare(data[i], data[j])) {temp.push_back(data[i++]);}else {temp.push_back(data[j++]);}}while (i <= mid) {temp.push_back(data[i++]);}while (j <= right) {temp.push_back(data[j++]);}for (int k = 0; k < temp.size(); k++) {data[left + k] = temp[k];}} }
- 编写思路:其中,归并排序的实现使用了模板函数,使得可以在同一函数体内处理不同类型的数据。在search_teams函数中,先对所有符合条件的团队按照赛事类别进行排序,然后再输出结果。如果查找失败,则输出提示信息。
- 核心代码:
// 按照学校名称或赛事类别查询参赛团队,并输出结果 void search_teams(vector<Team>& teams, string school, string category) {cout << "查询结果:" << endl;// 存储符合条件的团队信息vector<Team> result;// 遍历所有参赛团队,寻找学校名称或赛事类别符合条件的团队,并存储到result中for (int i = 0; i < teams.size(); i++) {if (teams[i].school == school || teams[i].category == category) {result.push_back(teams[i]);}}// 如果result不为空,按照赛事类别进行排序,并输出结果if (!result.empty()) {merge_sort(result, 0, result.size() - 1, compare_by_category);for (int i = 0; i < result.size(); i++) {cout << result[i].id<<" " << result[i].name << " " << result[i].school << " " << result[i].category << " " << result[i].member << " " << result[i].coach << endl;}}else {cout << "未查找到符合条件的参赛团队。" << endl;} }
预习小结:
可以使用C++语言内置的各种库函数和数据结构,fstream库读取team.txt文件中的数据,vector和map容器存储和处理数据,sort算法对数据进行排序。
无法查询到已存在文本中的信息,我认为是读取文本没成功,或者是没能正确的格式将每行数据存储到Team结构体中。
解决预习中的问题 :
- 个人感觉txt文本中的格式容易乱,比如一个空格\t都有可能让“==”“不相等”,不利于对数据的操作,现在尝试用excel表格来进行任务的完成。
- 在项目中添加Excel操作库,例如libxl,以支持对Excel文件的读写操作。下面的这篇博文把配置写的很清楚了。(84条消息) VS2019下第三方库libxl库环境配置(利用C++读写excel表格)_vs2019读写excel_李科笙不写作业的博客-CSDN博客
day3:
实验过程:
发现问题:
- 在转为excel表格后,此时book->load(filename.c_str())发生了报错,在进行自己搜查后发现是无法将参数1从“const _Elem *”转换为“const TCHAR *”。
在代码文件D:\vs2019 project\用excel进行增删改\用excel进行增删改\源.cpp的第22行中,string类型的变量filename通过调用c_str()方法转换成了const _Elem类型的指针,然后被传递给了libxl::IBookT<wchar_t>::load()函数,该函数的参数类型为const TCHAR,此时编译器无法将const _Elem隐式转换为const TCHAR类型,因此产生了C2664错误。
- 这是一个应用程序崩溃的错误信息。错误代码0xC0000005表示访问违规,程序试图读取位置0x00000000,导致访问冲突。该异常是由ucrtbased.dll文件中的代码在应用程序“用excel进行增删改.exe”中引发的,该文件可能是与应用程序相关的标准C库。
- 在将数据复制到excel中时,参赛队编号仍然以文本的形式存在,导致输出编号全为0,再将编号全转为数字后输出正常。
- “请输入新的参赛作品名称:请输入新的参赛学校:”连着一起输出
提醒:
- 要将excel 表放入Debug文件夹中,才能成功进行增删改等操作
- libxl库功能很强大,但此实验不可直接借助库本身的便利直接来增删改,故本实验设置了 vector<Team>这个容器来间接的实现增删改而不借助库自带的功能,才有助于本实验实现的目的。
解决问题:
- 为了解决这个错误,可以使用TCHAR宏,将string类型转换为TCHAR类型。或者使用TCHAR类型定义字符串变量,这样就不需要在代码中进行这种类型的转换,避免了产生这种类型的错误。方法一:
if (book->load(_T(filename.c_str())))
在filename.c_str()返回的const char*前面添加_T()宏,将字符串类型转换为TCHAR类型
方法二:
TCHAR tszFilename[_MAX_PATH];
_tcscpy_s(tszFilename, _countof(tszFilename), _T("C:\\test.xls"));
if (book->load(tszFilename))
可是还是不行,还是要报错。
终于看到了一篇文章在(84条消息) C++中 出现C2664错误代码 从“const char [29]”转换为“const wchar_t *”_c++c2664_eason_wjz的博客-CSDN博客
直接在属性页面将字符集修改为:使用多字节字符集就可以了。
- 开始设断点查找到底是哪里出了问题:
"i<=sheet->lastRow()"应该改为"i<sheet->lastRow()"不然会读取400行数据为空,就会报错。
- 这个问题可能是由于之前调用
cin
时未将多余的字符从输入缓存中清除导致的。您可以在每次调用getline
之前,使用cin.ignore()
清除输入缓存中的多余字符
// 修改队伍信息
cout << "请输入新的参赛作品名称:";
cin.ignore();
getline(cin, it->projectName);cout << "请输入新的参赛学校:";
cin.ignore();
getline(cin, it->school);cout << "请输入新的赛事类别:";
cin.ignore();
getline(cin, it->category);cout << "请输入新的参赛者:";
cin.ignore();
getline(cin, it->members);cout << "请输入新的指导老师:";
cin.ignore();
getline(cin, it->teacher);
实验结果:
- 添加参赛队:
2.删除参赛队:
实验验证:
3.修改参赛队:
实验验证:
4.用二叉排序树根据参赛编号查找参赛队伍
实验验证:
5.根据参赛学校查找参赛队伍
按照"school"进行排序,那么会按照队伍(Team)中的school成员变量的字符串值进行比较排序。在C++中,对于两个字符串的比较,可以使用string类的"<"操作符,该操作符会根据字符串的字典序进行比较大小,即比较两个字符串的ASCII码值。比如,"abc" < "def" 将返回true,因为'a'的ASCII码是97,而'd'的ASCII码是100,所以"abc"的ASCII码值小于"def"。
具体来说,对于字符串"江苏科技大学"和"江苏大学",首先比较它们的第一个字符'江'和'江',由于相等,继续比较第二个字符'苏'和'苏',仍然相等,继续比较第三个字符'科'和'大',此时发现'科'的ASCII码值是[234],而'大'的ASCII码值是[228],因此"江苏科技大学"的school值比"江苏大学"的school值大,即"江苏科技大学"排在"江苏大学"的前面。
(队伍过多,只展示一部分)
6.决赛叫号系统
首先将参赛队伍按照赛事类型分配到17个决赛室中。然后按照顺序逐个决赛室叫号,输出被叫号的参赛队的信息,并将该参赛队从该决赛室中取出。整个循环过程共进行rowCount-1轮比赛,比赛结束时,所有参赛队都已经从各个决赛室中取出。为了增加比赛的真实感,通过std::this_thread::sleep_for()函数模拟了输出信息的延迟。
最初的想法是:17个决赛室同时开始叫号,老师说如果要这样的话就得进行多线程来输出,所以目前按照各决赛室依次顺序叫号已经可以了。
7.校园导游:
将代号和对应的建筑物的名称都显示出来,以便参赛者直观方便查看。
经过老师建议后:
将每个代号的建筑物的名称也输出出来
实验代码:
说明:要由存储参赛队伍的向量 vector<Team> teams; 不然就会依赖于libxls库自带的填删改的功能。就失去了实验的意义。
- 添加参赛队:
void addTeam(vector<Team>& teams, Book* book) {Sheet* sheet = book->getSheet(0);if (sheet == nullptr) {cout << "无法获取第一个工作表!" << endl;return;}int rowIndex = sheet->lastRow();Team team;int id;cout << "请输入参赛队编号:";cin >> id;team.teamNo = id;cin.ignore();cout << "请输入参赛作品名称:";getline(cin, team.projectName);cout << "请输入参赛学校:";getline(cin, team.school);cout << "请输入赛事类别:";getline(cin, team.category);cout << "请输入参赛者:";getline(cin, team.members);cout << "请输入指导老师:";getline(cin, team.teacher);sheet->writeNum(rowIndex, 0, team.teamNo);sheet->writeStr(rowIndex, 1, team.projectName.c_str());sheet->writeStr(rowIndex, 2, team.school.c_str());sheet->writeStr(rowIndex, 3, team.category.c_str());sheet->writeStr(rowIndex, 4, team.members.c_str());sheet->writeStr(rowIndex, 5, team.teacher.c_str());teams.push_back(team);book->save("C:/Users/vincy/Desktop/teamtable.xls");cout << "\n参赛队伍信息已添加!\n" << endl; }
2.删除参赛队:
bool deleteTeam(vector<Team>& teams, Book* book, int teamNo) {Sheet* sheet = book->getSheet(0);if (sheet == nullptr) {cout << "无法获取第一个工作表!" << endl;return false;}int rowIndex = -1;// 查找要删除的队伍在 Excel 文件中的行号for (int i = 1; i < sheet->lastRow(); i++) {if (sheet->readNum(i, 0) == teamNo) {rowIndex = i;break;}}if (rowIndex == -1) {cout << "错误:未找到指定的参赛队伍。" << endl;return false;}// 删除 Excel 文件中的记录sheet->removeRow(rowIndex,rowIndex);book->save("C:/Users/vincy/Desktop/teamtable.xls");// 删除 vector 中的记录for (auto it = teams.begin(); it != teams.end(); ++it) {if (it->teamNo == teamNo) {teams.erase(it);break;}}for (int i = 0; i < teams.size(); i++) {Team& team = teams[i];sheet->writeNum(i + 1, 0, team.teamNo);sheet->writeStr(i + 1, 1, team.projectName.c_str());sheet->writeStr(i + 1, 2, team.school.c_str());sheet->writeStr(i + 1, 3, team.category.c_str());sheet->writeStr(i + 1, 4, team.members.c_str());sheet->writeStr(i + 1, 5, team.teacher.c_str());}book->save("C:/Users/vincy/Desktop/teamtable.xls");cout << "\n参赛队伍信息已删除!\n" << endl;return true; }
一定要注意将reams中修改后的数据重新写入excel中,具体实现是删除中的for循环:
for (int i = 0; i < teams.size(); i++) {Team& team = teams[i];sheet->writeNum(i + 1, 0, team.teamNo);sheet->writeStr(i + 1, 1, team.projectName.c_str());sheet->writeStr(i + 1, 2, team.school.c_str());sheet->writeStr(i + 1, 3, team.category.c_str());sheet->writeStr(i + 1, 4, team.members.c_str());sheet->writeStr(i + 1, 5, team.teacher.c_str());}
3.修改参赛队:
void updateTeam(vector<Team>& teams, Book* book, int teamNo) {Sheet* sheet = book->getSheet(0);if (sheet == nullptr) {cout << "无法获取第一个工作表!" << endl;return;}int rowIndex = -1;// 查找要更新的队伍在 Excel 文件中的行号for (int i = 1; i < sheet->lastRow(); i++) {if (sheet->readNum(i, 0) == teamNo) {rowIndex = i;break;}}if (rowIndex == -1) {cout << "错误:未找到指定的参赛队伍。" << endl;return;}//重新添加Team& team = teams[rowIndex-1];cout << "请输入新的参赛作品名称:";getline(cin, team.projectName);cout << "请输入新的参赛学校:";getline(cin, team.school);cout << "请输入新的赛事类别:";getline(cin, team.category);cout << "请输入新的参赛者:";getline(cin, team.members);cout << "请输入新的指导老师:";getline(cin, team.teacher);//将修改后的数据写入excel中sheet->writeNum(rowIndex, 0, team.teamNo);sheet->writeStr(rowIndex, 1, team.projectName.c_str());sheet->writeStr(rowIndex, 2, team.school.c_str());sheet->writeStr(rowIndex, 3, team.category.c_str());sheet->writeStr(rowIndex, 4, team.members.c_str());sheet->writeStr(rowIndex, 5, team.teacher.c_str());book->save("C:/Users/vincy/Desktop/teamtable.xls");cout << "\n参赛队伍信息已修改!\n" << endl; }
同上面的删除一样也是要将teams中的数据重新写入excel中。
4.用二叉排序树根据参赛编号查找参赛队伍
// 在二叉排序树中查找节点
bool search(Node* root, int id, int& depth, Team& result) {while (root) {depth++;if (root->entry.teamNo == id) {result = root->entry;return true;}else if (id < root->entry.teamNo) {root = root->left;}else {root = root->right;}}return false;
}
search函数实现了根据参赛队编号查找参赛队信息的功能,传入参数为根节点root、要查找的参赛队编号id、查询深度depth、存放查询结果result。遍历二叉排序树,如果查找到了编号为id的参赛队,则将查询结果存入result中,返回true表示查找成功;否则如果要查找的编号小于当前节点的编号,则继续向当前节点的左子树中查找;否则则递归向当前节点的右子树中查找,直至遍历完整颗二叉树。
5.根据参赛学校查找参赛队伍
/ 归并排序
vector<Team> mergeSort(vector<Team> v, string key) {int n = v.size();if (n <= 1) {return v;}int mid = n / 2;vector<Team> v1 = vector<Team>(v.begin(), v.begin() + mid);vector<Team> v2 = vector<Team>(v.begin() + mid, v.end());v1 = mergeSort(v1, key);v2 = mergeSort(v2, key);vector<Team> result;int i = 0;int j = 0;// 按照指定key进行排序while (i < v1.size() && j < v2.size()) {if (key == "school") {if (v1[i].school < v2[j].school) {result.push_back(v1[i++]);}else {result.push_back(v2[j++]);}}else if (key == "category") {if (v1[i].category < v2[j].category) {result.push_back(v1[i++]);}else {result.push_back(v2[j++]);}}}while (i < v1.size()) {result.push_back(v1[i++]);}while (j < v2.size()) {result.push_back(v2[j++]);}return result;
}
这段代码实现了归并排序(Merge Sort)的算法过程。传入参数为一个待排序的vector容器v和一个排序关键字key,返回值为排序后的vector容器。
归并排序的基本思想是将待排序序列递归地拆分成越来越小的子序列,直到每个子序列只有一个元素,然后将相邻的子序列两两合并,并按照指定的排序关键字key进行比较排序,最终形成一个有序的序列。
在这段代码中,首先判断传入的原始vector容器v的大小是否小于或等于1,如果是,则直接将其返回,因为只有一个元素或为空时已经是有序的了。
如果原始v容器的大小大于1,则将其分为左右两个子序列v1和v2,通过递归调用mergeSort函数,对左右两个子序列分别进行排序。然后将排好序的两个子序列v1和v2进行合并排序,按照指定的排序关键字key进行比较排序,依次取出子序列v1和v2中的元素,将较小的元素放入结果容器result中,并将对应的索引i或j加1。
最后,将任何一个子序列中剩余的所有元素添加到结果容器result中,形成一个有序的序列,将该序列返回即可。
6.决赛叫号系统
// 输出被叫号参赛队的信息
void printContestant(const Contestant& c) {std::cout << "参赛队 " << c.name << " (" << c.id << ") 进入决赛室 " << c.room << std::endl;std::this_thread::sleep_for(std::chrono::seconds(1)); // 显示屏显示比赛队伍,
}// 按照赛事类型将参赛队分配到各个决赛室const int numRooms = 17;std::vector<std::queue<Contestant>> rooms(numRooms);for (const auto& c : contestants) {int room = (c.eventType - 1) % numRooms;rooms[room].push({ c });}// 按照顺序叫号,比赛开始for (int i = 1; i <= rowCount - 1; ++i) { // 共进行rowCount-1轮比赛for (int j = 0; j < numRooms; ++j) {if (rooms[j].empty()) {continue;}Contestant c = rooms[j].front();c.room = j + 1; // 决赛室编号从1开始rooms[j].pop();printContestant(c);}}
这一句是将各个赛事类型分入各个决赛室,因为我将每个赛事类别用数字进行了编号所以-1再对决赛室数求余即可。
int room = (c.eventType - 1) % numRooms;
7.校园导游:
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>using namespace std;// 建筑物结构体
struct Building {string name; // 建筑物名称string info; // 建筑物相关信息int id; // 建筑物 ID
};// 边结构体
struct Edge {int to; // 边目标顶点 IDint weight; // 边权重(距离)Edge(int to, int weight) : to(to), weight(weight) {}
};// 顶点结构体
struct Vertex {int id; // 顶点 IDvector<Edge> edges; // 顶点的边集合string name;string info;Vertex(int id) : id(id) {}Vertex() : id(0) {}
};class Graph {
public:Graph() : id_counter_(0) {}// 添加建筑物到图中int AddBuilding(string name, string info);// 添加路径到图中void AddPath(int from, int to, int weight);// 查询建筑物信息void QueryBuildingInfo(int id);// 查询两个建筑物之间的最短路径void QueryShortestPath(int from, int to);private:void Dijkstra(int start, int end);// 顶点集合unordered_map<int, Vertex> vertices_;// 建筑物 ID 计数器,用于给新建的建筑物分配唯一的 IDint id_counter_;
};int Graph::AddBuilding(string name, string info) {int id = ++id_counter_;Building building = { name, info, id };Vertex new_vertex;new_vertex.id = id;new_vertex.name = name;new_vertex.info = info;vertices_[id] = new_vertex;return id;
}// 添加一条路劲到图中
void Graph::AddPath(int from, int to, int weight) {vertices_[from].edges.emplace_back(to, weight);vertices_[to].edges.emplace_back(from, weight);
}// 查询建筑物信息
void Graph::QueryBuildingInfo(int id) {if (vertices_.count(id) == 0) {cout << "错误:没有找到该建筑物!" << endl;return;}cout << "建筑物名称: " << vertices_[id].name << endl;cout << "建筑物相关信息: " << vertices_[id].info << endl;
}// 查询两个建筑物之间的最短路径
void Graph::QueryShortestPath(int from, int to) {if (vertices_.count(from) == 0 || vertices_.count(to) == 0) {cout << "错误:没有找到该建筑物!" << endl;return;}Dijkstra(from, to);
}// Dijkstra 算法,用于计算最短路径
void Graph::Dijkstra(int start, int end) {unordered_map<int, int> distance;unordered_map<int, int> prev;priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;for (auto& p : vertices_) {int id = p.second.id;distance[id] = INT_MAX;prev[id] = -1;}distance[start] = 0;pq.emplace(0, start);while (!pq.empty()) {int cur = pq.top().second;pq.pop();for (auto& edge : vertices_[cur].edges) {int to = edge.to;int weight = edge.weight;if (distance[to] > distance[cur] + weight) {distance[to] = distance[cur] + weight;prev[to] = cur;pq.emplace(distance[to], to);}}}if (prev[end] == -1) {cout << "错误:找不到路经,从 " << start << " 到 " << end << endl;return;}vector<int> path;for (int cur = end; cur != -1; cur = prev[cur]) {path.push_back(cur);}cout << "最短的路经从 " << start << " 到 " << end << " : " << endl;for (auto it = path.rbegin(); it != path.rend(); it++) {cout << vertices_[*it].id <<"." << vertices_[*it].name << " ";}cout << endl << "总共的距离是: " << distance[end] << endl;
}
以上代码实现的是图(Graph)数据结构,可以添加建筑物(Building)和路径(Path),并且使用 Dijkstra 算法计算两个建筑物之间的最短路径。其中,Building 结构体包含建筑物名称、相关信息和 ID,Vertex 结构体包含顶点 ID、相邻边集合、建筑物名称和相关信息,Edge 结构体包含边的目标顶点 ID 和边的权重。Graph 类包含 AddBuilding 方法,用于添加建筑物;AddPath 方法,用于添加路径;QueryBuildingInfo 方法,用于查询建筑物信息;QueryShortestPath 方法,用于查询两个建筑物之间的最短路径。Dijkstra 方法是一个私有方法,用于实现 Dijkstra 算法。
Dijkstra 算法是一种用于求解带权图中单源最短路径的算法,其中“单源”指的是只求解从一个顶点出发到其他顶点的最短路径,而不涉及其他顶点之间的路径。Dijkstra 算法的基本思想是从起点开始,逐步扩展到邻接顶点,然后迭代地遍历所有顶点,直到到达目标顶点。在遍历的过程中,对于每个未确定最短路径的顶点,计算它到起点的距离(dis)和到起点的最短路径上的前一个顶点(prev),并将其保存在两个哈希表中。在计算邻接顶点的 dis 和 prev 时,根据公式 dis[next] = dis[cur] + weight,其中 next 是邻接顶点,cur 是当前顶点,weight 是当前顶点到邻接顶点的边权重。在遍历所有顶点后,dis 和 prev 中保存的就是起点到其他顶点的最短路径和路径信息。最后可以根据 prev 哈希表回溯得到起点到目标顶点的最短路径。
以下是源码:
#include <iostream>
#include <vector>
#include "libxl.h"
#include <string>
#include <chrono> // for sleep
#include <thread>
#include <windows.h>#include "distance.h"
using namespace std;
using namespace libxl;struct Team {int teamNo;string projectName;string school;string category;string members;string teacher;bool deleted = true;
};// 定义二叉排序树节点
struct Node {Team entry;Node* left;Node* right;
};// 定义参赛队结构体
struct Contestant {std::string name; // 参赛队名称int id; // 参赛队编号int eventType; // 赛事类型int room; // 决赛室编号
};// 输出被叫号参赛队的信息
void printContestant(const Contestant& c) {std::cout << "参赛队 " << c.name << " (" << c.id << ") 进入决赛室 " << c.room << std::endl;std::this_thread::sleep_for(std::chrono::seconds(1)); // 显示屏显示比赛队伍,
}// 插入节点到二叉排序树中
void insert(Node** root, Team entry) {if (!*root) {*root = new Node{ entry, nullptr, nullptr };return;}if (entry.teamNo < (*root)->entry.teamNo) {insert(&(*root)->left, entry);}else {insert(&(*root)->right, entry);}
}// 在二叉排序树中查找节点
bool search(Node* root, int id, int& depth, Team& result) {while (root) {depth++;if (root->entry.teamNo == id) {result = root->entry;return true;}else if (id < root->entry.teamNo) {root = root->left;}else {root = root->right;}}return false;
}// 归并排序
vector<Team> mergeSort(vector<Team> v, string key) {int n = v.size();if (n <= 1) {return v;}int mid = n / 2;vector<Team> v1 = vector<Team>(v.begin(), v.begin() + mid);vector<Team> v2 = vector<Team>(v.begin() + mid, v.end());v1 = mergeSort(v1, key);v2 = mergeSort(v2, key);vector<Team> result;int i = 0;int j = 0;// 按照指定key进行排序while (i < v1.size() && j < v2.size()) {if (key == "school") {if (v1[i].school < v2[j].school) {result.push_back(v1[i++]);}else {result.push_back(v2[j++]);}}else if (key == "category") {if (v1[i].category < v2[j].category) {result.push_back(v1[i++]);}else {result.push_back(v2[j++]);}}}while (i < v1.size()) {result.push_back(v1[i++]);}while (j < v2.size()) {result.push_back(v2[j++]);}return result;
}void addTeam(vector<Team>& teams, Book* book) {Sheet* sheet = book->getSheet(0);if (sheet == nullptr) {cout << "无法获取第一个工作表!" << endl;return;}int rowIndex = sheet->lastRow();Team team;int id;cout << "请输入参赛队编号:";cin >> id;team.teamNo = id;cin.ignore();cout << "请输入参赛作品名称:";getline(cin, team.projectName);cout << "请输入参赛学校:";getline(cin, team.school);cout << "请输入赛事类别:";getline(cin, team.category);cout << "请输入参赛者:";getline(cin, team.members);cout << "请输入指导老师:";getline(cin, team.teacher);sheet->writeNum(rowIndex, 0, team.teamNo);sheet->writeStr(rowIndex, 1, team.projectName.c_str());sheet->writeStr(rowIndex, 2, team.school.c_str());sheet->writeStr(rowIndex, 3, team.category.c_str());sheet->writeStr(rowIndex, 4, team.members.c_str());sheet->writeStr(rowIndex, 5, team.teacher.c_str());teams.push_back(team);book->save("D:/vs2019 project/CurriculumDesign/Debug/teamtable.xls");cout << "\n参赛队伍信息已添加!\n" << endl;
}bool deleteTeam(vector<Team>& teams, Book* book, int teamNo) {Sheet* sheet = book->getSheet(0);if (sheet == nullptr) {cout << "无法获取第一个工作表!" << endl;return false;}int rowIndex = -1;// 查找要删除的队伍在 Excel 文件中的行号for (int i = 1; i < sheet->lastRow(); i++) {if (sheet->readNum(i, 0) == teamNo) {rowIndex = i;break;}}if (rowIndex == -1) {cout << "错误:未找到指定的参赛队伍。" << endl;return false;}// 删除 Excel 文件中的记录sheet->removeRow(rowIndex, rowIndex);book->save("D:/vs2019 project/CurriculumDesign/Debug/teamtable.xls");// 删除 vector 中的记录for (auto it = teams.begin(); it != teams.end(); ++it) {if (it->teamNo == teamNo) {teams.erase(it);break;}}if (sheet != nullptr) {for (int i = 0; i < teams.size(); i++) {Team& team = teams[i];sheet->writeNum(i + 1, 0, team.teamNo);sheet->writeStr(i + 1, 1, team.projectName.c_str());sheet->writeStr(i + 1, 2, team.school.c_str());sheet->writeStr(i + 1, 3, team.category.c_str());sheet->writeStr(i + 1, 4, team.members.c_str());sheet->writeStr(i + 1, 5, team.teacher.c_str());}}book->save("D:/vs2019 project/CurriculumDesign/Debug/teamtable.xls");//"D:/vs2019 project/CurriculumDesign/Debug/teamtable.xls"cout << "\n参赛队伍信息已删除!\n" << endl;return true;
}void updateTeam(vector<Team>& teams, Book* book, int teamNo) {// 显式声明迭代器类型为 vector<Team>::iteratorvector<Team>::iterator it = find_if(teams.begin(), teams.end(), [teamNo](const Team& team) {return team.teamNo == teamNo;});if (it == teams.end()) {cout << "错误:未找到指定的参赛队伍。" << endl;return;}// 修改队伍信息cout << "请输入新的参赛作品名称:";string projectName;getline(cin, projectName);it->projectName = projectName;cin.ignore();cout << "请输入新的参赛学校:";string school;getline(cin, school);it->school = school;cin.ignore();cout << "请输入新的赛事类别:";string category;getline(cin, category);it->category = category;cin.ignore();cout << "请输入新的参赛者:";string members;getline(cin, members);it->members = members;cin.ignore();cout << "请输入新的指导老师:";string teacher;getline(cin, teacher);it->teacher = teacher;cin.ignore();// 更新 Excel 文件Sheet* sheet = book->getSheet(0);if (sheet == nullptr) {cout << "无法获取第一个工作表!" << endl;return;}for (int i = 0; i < teams.size(); i++) {const Team& team = teams[i];sheet->writeNum(i + 1, 0, team.teamNo);sheet->writeStr(i + 1, 1, team.projectName.c_str());sheet->writeStr(i + 1, 2, team.school.c_str());sheet->writeStr(i + 1, 3, team.category.c_str());sheet->writeStr(i + 1, 4, team.members.c_str());sheet->writeStr(i + 1, 5, team.teacher.c_str());}book->save("D:/vs2019 project/CurriculumDesign/Debug/teamtable.xls");cout << "\n参赛队伍信息已修改!\n" << endl;
}int main() {// 打开 Excel 文件Book* book = xlCreateBook();book->load("D:/vs2019 project/CurriculumDesign/Debug/teamtable.xls");if (book == nullptr) {cout << "打开teamtable.xls文件失败!" << endl;return 0;}// 从 Excel 文件中读取数据,填充teamsvector<Team> teams; Node* root = nullptr;Sheet* sheet = book->getSheet(0);int a = sheet->lastRow();//从 Excel 文件中读取数据,填充contestantsconst int rowCount = sheet->lastRow();std::vector<Contestant> contestants;if (sheet != nullptr) {// 遍历所有数据行,读取参赛队信息for (int i = 1; i < rowCount; ++i) { // 从第2行开始读取(第1行为标题行)Contestant c;c.name = sheet->readStr(i, 1);c.id = sheet->readNum(i, 0);c.eventType = sheet->readNum(i, 6);contestants.push_back(c);}for (int i = 1; i < sheet->lastRow(); i++) {Team team;team.teamNo = sheet->readNum(i, 0);team.projectName = sheet->readStr(i, 1);team.school = sheet->readStr(i, 2);team.category = sheet->readStr(i, 3);team.members = sheet->readStr(i, 4);team.teacher = sheet->readStr(i, 5);teams.push_back(team);// 将数据插入到二叉排序树中Team entry{ team.teamNo, team.projectName, team.school, team.category, team.members, team.teacher };insert(&root, entry);}}// 开始界面while (true) {cout << "===== 比赛参赛队管理系统 =====" << endl;cout << "\n1. 增加参赛队伍信息\n" << endl;cout << "2. 删除参赛队伍信息\n" << endl;cout << "3. 修改参赛队伍信息\n" << endl;cout << "4. 查找参赛队伍信息(根据参赛编号)\n" << endl;cout << "5. 查找参赛队伍信息(根据参赛学校)\n" << endl;cout << "6. 决赛叫号系统\n" << endl;cout << "7. 校园导游\n" << endl;cout << "0. 退出程序\n" << endl;cout << "请选择操作:";int choice = 0;cin >> choice;cin.ignore();if (choice == 1) {addTeam(teams, book);}else if (choice == 2) {int teamNo = 0;cout << "请输入要删除的参赛队伍编号:";cin >> teamNo;deleteTeam(teams, book, teamNo);}else if (choice == 3) {int teamNo = 0;cout << "请输入要修改的参赛队伍编号:";cin >> teamNo;updateTeam(teams, book, teamNo);}else if(choice == 4){// 查询数据int totalCount = 0;int totalDepth = 0;int id;Team result;int depth = 0;cout << "请输入要查找的参赛队的编号:";cin >> id;cout << endl;if (search(root, id, depth, result)) {cout << "参赛队编号: " << result.teamNo << endl;cout << "参赛作品名称: " << result.projectName << endl;cout << "参赛学校: " << result.school << endl;cout << "赛事类别: " << result.category << endl;cout << "参赛者: " << result.members << endl;cout << "指导老师: " << result.teacher << endl;totalCount++;totalDepth += depth;}// 输出平均查找长度double avgDepth = (double)totalDepth / totalCount;cout << "平均查找长度: " << avgDepth << endl;}else if (choice == 5) {// 根据参赛学校或赛事类别进行排序和查询string key = "school"; // 可根据需要修改排序的key,这里假定按照参赛学校排序teams = mergeSort(teams, key);string query; // 可根据需要修改查询的参赛学校或赛事类别,cout << "请输入要查找的参赛队学校:";cin >> query;cout << endl;int totalCount = 0;double totalDepth = 0;for (Team entry : teams) {if (entry.school == query) {cout << "参赛队编号: " << entry.teamNo << endl;cout << "参赛作品名称: " << entry.projectName << endl;cout << "参赛学校: " << entry.school << endl;cout << "赛事类别: " << entry.category << endl;cout << "参赛者: " << entry.members << endl;cout << "指导老师: " << entry.teacher << endl;cout << "==================================================" << endl;totalCount++;totalDepth += totalCount;}}}else if (choice == 6) {// 按照赛事类型将参赛队分配到各个决赛室const int numRooms = 17;std::vector<std::queue<Contestant>> rooms(numRooms);for (const auto& c : contestants) {int room = (c.eventType - 1) % numRooms;rooms[room].push({ c });}// 按照顺序叫号,比赛开始for (int i = 1; i <= rowCount - 1; ++i) { // 共进行rowCount-1轮比赛for (int j = 0; j < numRooms; ++j) {if (rooms[j].empty()) {continue;}Contestant c = rooms[j].front();c.room = j + 1; // 决赛室编号从1开始rooms[j].pop();printContestant(c);}}}else if (choice == 7) {Graph g;// 添加建筑物到图中int building1 = g.AddBuilding("学生宿舍49栋", "即3号组团D楼");int building2 = g.AddBuilding("西苑食堂", "西区食堂,共有三楼,三楼主要是面食类");int building3 = g.AddBuilding("明德园", "可供休憩(靠近经世楼)");int building4 = g.AddBuilding("文体中心A", "主要为学生社团办事点");int building5 = g.AddBuilding("足球场—西", "西区操场,可供踢足球等(体育馆对面)");int building6 = g.AddBuilding("文理大楼", "赛事地点");int building7 = g.AddBuilding("海韵湖(行政大楼)", "学校的大型湖泊(靠近北门)");int building8 = g.AddBuilding("求索园", "可供休憩(靠近笃学楼)");int building9 = g.AddBuilding("东苑食堂", "东区食堂,共有三楼,可自行选择楼层就餐,三楼主要是教职工就餐楼层");int building10 = g.AddBuilding("图书馆", "共有六楼,3-6楼为自习室,5,6楼主要为藏书楼层");// 添加路径到图中g.AddPath(building1, building2, 100);g.AddPath(building1, building4, 200);g.AddPath(building2, building4, 150);g.AddPath(building2, building3, 80);g.AddPath(building3, building5, 120);g.AddPath(building3, building6, 110);g.AddPath(building4, building5, 50);g.AddPath(building5, building8, 150);g.AddPath(building5, building9, 230);g.AddPath(building6, building8, 60);g.AddPath(building8, building9, 90);g.AddPath(building8, building10, 70);g.AddPath(building9, building10, 50);g.AddPath(building7, building10, 100);cout << "1.学生宿舍49栋" << endl;cout << "2.西苑食堂" << endl;cout << "3.明德园" << endl;cout << "4.文体中心A" << endl;cout << "5.足球场—西" << endl;cout << "6.文理大楼" << endl;cout << "7.海韵湖(行政大楼)" << endl;cout << "8.求索园" << endl;cout << "9.东苑食堂" << endl;cout << "10.图书馆" << endl;int b, b1, b2;cout << "请输入你要查询的建筑物的代号:";cin >> b;cout << endl;// 查询某一建筑物信息g.QueryBuildingInfo(b);cout << "请输入你要查询的两个建筑物之间的最短路径:" << endl;cout << "建筑物1:";cin >> b1;cout << endl;cout << "建筑物2:";cin >> b2;// 查询两个建筑物之间的最短路径g.QueryShortestPath(b1, b2);}else if (choice == 0) {break;}else {cout << "\n无效的操作,请重新选择!\n" << endl;}cout << endl;}// 关闭 Excel 文件book->release();return 0;
}
diatance.h:
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>using namespace std;// 建筑物结构体
struct Building {string name; // 建筑物名称string info; // 建筑物相关信息int id; // 建筑物 ID
};// 边结构体
struct Edge {int to; // 边目标顶点 IDint weight; // 边权重(距离)Edge(int to, int weight) : to(to), weight(weight) {}
};// 顶点结构体
struct Vertex {int id; // 顶点 IDvector<Edge> edges; // 顶点的边集合string name;string info;Vertex(int id) : id(id) {}Vertex() : id(0) {}
};class Graph {
public:Graph() : id_counter_(0) {}// 添加建筑物到图中int AddBuilding(string name, string info);// 添加路径到图中void AddPath(int from, int to, int weight);// 查询建筑物信息void QueryBuildingInfo(int id);// 查询两个建筑物之间的最短路径void QueryShortestPath(int from, int to);private:void Dijkstra(int start, int end);// 顶点集合unordered_map<int, Vertex> vertices_;// 建筑物 ID 计数器,用于给新建的建筑物分配唯一的 IDint id_counter_;
};int Graph::AddBuilding(string name, string info) {int id = ++id_counter_;Building building = { name, info, id };Vertex new_vertex;new_vertex.id = id;new_vertex.name = name;new_vertex.info = info;vertices_[id] = new_vertex;return id;
}// 添加一条路劲到图中
void Graph::AddPath(int from, int to, int weight) {vertices_[from].edges.emplace_back(to, weight);vertices_[to].edges.emplace_back(from, weight);
}// 查询建筑物信息
void Graph::QueryBuildingInfo(int id) {if (vertices_.count(id) == 0) {cout << "错误:没有找到该建筑物!" << endl;return;}cout << "建筑物名称: " << vertices_[id].name << endl;cout << "建筑物相关信息: " << vertices_[id].info << endl;
}// 查询两个建筑物之间的最短路径
void Graph::QueryShortestPath(int from, int to) {if (vertices_.count(from) == 0 || vertices_.count(to) == 0) {cout << "错误:没有找到该建筑物!" << endl;return;}Dijkstra(from, to);
}// Dijkstra 算法,用于计算最短路径
void Graph::Dijkstra(int start, int end) {unordered_map<int, int> distance;unordered_map<int, int> prev;priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;for (auto& p : vertices_) {int id = p.second.id;distance[id] = INT_MAX;prev[id] = -1;}distance[start] = 0;pq.emplace(0, start);while (!pq.empty()) {int cur = pq.top().second;pq.pop();for (auto& edge : vertices_[cur].edges) {int to = edge.to;int weight = edge.weight;if (distance[to] > distance[cur] + weight) {distance[to] = distance[cur] + weight;prev[to] = cur;pq.emplace(distance[to], to);}}}if (prev[end] == -1) {cout << "错误:找不到路经,从 " << start << " 到 " << end << endl;return;}vector<int> path;for (int cur = end; cur != -1; cur = prev[cur]) {path.push_back(cur);}cout << "最短的路经从 " << start << " 到 " << end << " : " << endl;for (auto it = path.rbegin(); it != path.rend(); it++) {cout << vertices_[*it].id <<"." << vertices_[*it].name << " ";}cout << endl;cout<< "总共的距离是: " << distance[end] << endl;
}
更多推荐
数构课设——管理赛事信息
发布评论