//简化版高校自动排课系统//排课任务简化后包含：年级专业（教学班级，如计科13）、课程名称、任课教师、上课地点和时间//教学班级简化为不分人数，不分专业方向。

//上课教室简化为不分理论课、实验课，不分教室容纳人数，不分是否多媒体。

//上课时段简化为：一周五天，周一到周五，白天上课，上午四节，下午四节，//1~2(8:00~9:400)、3~4(10:00~11:40)、5~6(14:00~15:40)、7~8(16:00~17:40)//为了便于处理，将五天的所有上课时段用数字0~19表示//上课地点和时间组合成一个整数数组（位集，bitset），每20个为1组为一个教室的上课时段安排//约束条件：1、教学班级的上课时间不能冲突//2、每个教室不能同时安排多个教学班级上课//3、任课教师的上课时间不能冲突//#include <iostream>#include <fstream>#include <sstream>#include <string>#include <vector>#include <bitset>#include <random>#include <iomanip>using namespace std;//原始数据文件中的每一行数据的数据结构struct schedule {string grade_special; //年级专业string course; //课程名称string teacher; //任课教师string total_hour; //总学时string teach_hour; //讲课学时string experiment_hour; //实验学时string practice_hour; //课程实践学时string credit; //学分string week_hour; //周学时string start_stop; //起止周string speciality_orientation; //专业方向string person_num; //人数};//排课任务的数据结构struct arrange {arrange(string gs, string c, string t, int ct = -1) : grade_special(gs), course(c), teacher(t),classroom_time(ct) {}string grade_special;//年级专业string course;//课程名称string teacher;//任课教师//string classroom;//上课地点//string time;//上课时间int classroom_time;//上课地点、时间};//教师倒排表数据结构，通过教师姓名找到该教师的排课情况struct teacher_inverted {teacher_inverted(string tea, int cl = -1, int ar = -1) : teacher(tea), class_loc(cl), arrange_loc(ar) {}string teacher;int class_loc;int arrange_loc;};//教室倒排表数据结构，通过教室名称查找该教室的排课情况struct classroom_inverted {classroom_inverted(string cr, int cl = -1, int ar = -1) : classroom(cr), class_loc(cl), arrange_loc(ar) {}string classroom;int class_loc;int arrange_loc;};int main(int argc, char** argv) {if (argc != 3) {cout << "程序调用格式错误!\n调用格式：csp 排课计划文件可用教室文件\n";return 0;}ifstream infile(argv[1]);vector<schedule> plan;string s;getline(infile, s);while (getline(infile, s)) {schedule sch;istringstream record(s);record >> sch.grade_special >> sch.course >> sch.teacher >> sch.total_hour >> sch.teach_hour>> sch.experiment_hour >> sch.practice_hour >> sch.credit >> sch.week_hour >> sch.start_stop>> sch.speciality_orientation >> sch.person_num;plan.push_back(sch);}infile.close();vector<vector<arrange>> arranges; //整个系的排课安排vector<arrange> arr; //一个班的排课安排string gs(""); //教学班级for (auto it = plan.begin(); it != plan.end(); ++it) {if (gs != it->grade_special) {if (!arr.empty()) {arranges.push_back(arr); //教学计划按教学班级顺序排列arr.clear();}gs = it->grade_special;}arr.push_back(arrange(it->grade_special, it->course, it->teacher));}arranges.push_back(arr);vector<vector<teacher_inverted>> teachers; //教师数组for (unsigned i = 0; i < arranges.size(); ++i) {for (unsigned j = 0; j < arranges[i].size(); ++j) {string tea = arranges[i][j].teacher;if (tea == "未定") continue;unsigned k = 0;for (; k < teachers.size(); ++k) {if (teachers[k][0].teacher == tea) {teachers[k].push_back(teacher_inverted(tea, i, j));break;}}if (k == teachers.size()) {vector<teacher_inverted> ti; //一个教师的排课信息倒排表ti.push_back(teacher_inverted(tea, i, j));teachers.push_back(ti);}}}const int N = 256;bitset<N> ct; //教室时段的分配状况infile.open(argv[2]);;vector<string> classrooms;//教室数组while (getline(infile, s)) {classrooms.push_back(s);}infile.close();unsigned arrange_num = plan.size(); //待排课数目unsigned class_num = arranges.size(); //教学班级数目unsigned classroom_num = classrooms.size(); //教室数目uniform_int_distribution<unsigned> u(0, classroom_num * 20 - 1); //为教室时段分配随机数default_random_engine e(time(0));vector<unsigned> class_loc(class_num, 0); //教学班级已分配状况unsigned class_cur = 0; //待分配的教学班级序号，轮流为每个班级排课，一次安排一个班的一门课for (unsigned n = 0; n < arrange_num; ++n) {unsigned k = u(e);//如果某个班级的排课任务已经分配完成，则选择下一个班级继续排课while (class_loc[class_cur] == arranges[class_cur].size()) {class_cur = (class_cur + 1) % class_num;}//找到待排课任务的对应教师string tea = arranges[class_cur][class_loc[class_cur]].teacher;unsigned i = 0;for (; i < teachers.size(); ++i) {if (tea == teachers[i][0].teacher) break;}//找出与该教师无时间冲突的时段do {do {while (ct.test(k)) { k = (k + 1) % (classroom_num * 20); }unsigned m = 0;for (; m < class_loc[class_cur]; ++m) {if (arranges[class_cur][m].classroom_time % 20 == k % 20) break;}if (m == class_loc[class_cur]) break; //如果与前面已安排的该班级时间无冲突，则k可用k = (k + 1) % (classroom_num * 20); //如果有冲突则检查下一个教室时段是否可用} while (1);if (i == teachers.size()) break; //教师未定unsigned j = 0;for (; j < teachers[i].size(); ++j) {int m = arranges[teachers[i][j].class_loc][teachers[i][j].arrange_loc].classroom_time;if (m != -1 && (m % 20 == k % 20)) break;}if (j == teachers[i].size()) break; //如果与该教师的时间无冲突，则k可用k = (k + 1) % (classroom_num * 20); //如果有冲突则检查下一个教室时段是否可用} while (1);//排课arranges[class_cur][class_loc[class_cur]].classroom_time = k;ct.set(k);//将当前班级的排课号+1++class_loc[class_cur];//将待排课班级号+1class_cur = (class_cur + 1) % class_num;}loop: //输出cout << "\t\t高校自动排课系统\n";cout << "选择查询条件：1. 按班级2. 按教师3. 按教室\n";cout << "请输入查询序号：(输入-1退出系统)";unsigned choice = 0;cin >> choice;if (-1 == choice) {cout << "正常退出系统\n";return 0;}else if (1 == choice) {unsigned i = 0, j = 0;for (; i < arranges.size(); ++i) {cout << i << ". " << arranges[i][0].grade_special << "\t";if ((i + 1) % 4 == 0) cout << "\n";}cout << "\n";do {cout << "\n请输入待查询班级的序号：（输入-1结束查询）";cin >> i;if (i == -1) {break;}else if (i >= arranges.size()) {cout << "非法选择\n";continue;}int class_table[4][5];for (unsigned m = 0; m < 4; ++m)for (unsigned n = 0; n < 5; ++n)class_table[m][n] = -1;for (j = 0; j < arranges[i].size(); ++j) {unsigned m = arranges[i][j].classroom_time % 20;class_table[m / 5][m % 5] = j;}string time_slot[4] = { "8:00-9:40", "10:00-11:40", "14:00-15:40", "16:00-17:40" };cout << setiosflags(ios_base::left);cout << setw(54) << " " << arranges[i][0].grade_special << "班级课程表\n";cout << "============================================================================== ======================================================\n";cout << setw(12) << " " << setw(24) << "星期一" << setw(24) << "星期二" << setw(24) << "星期三" << setw(24) << "星期四" << setw(24) << "星期五" << "\n";for (unsigned m = 0; m < 4; ++m) {if (m % 2 == 0)cout << "============================================================================== ======================================================\n";elsecout << "------------------------------------------------------------------------------------------------------------------------------------\n";for (unsigned m1 = 0; m1 < 3; ++m1) {if (m1 == 1)cout << setw(12) << time_slot[m];elsecout << setw(12) << "";for (unsigned n = 0; n < 5; ++n) {if (class_table[m][n] != -1) {j = class_table[m][n];if (m1 == 0)cout << setw(24) << arranges[i][j].course;else if (m1 == 1)cout << setw(24) << classrooms[arranges[i][j].classroom_time / 20];elsecout << setw(24) << arranges[i][j].teacher;}elsecout << setw(24) << " ";}cout << "\n";}}cout << "============================================================================== ======================================================\n";cout << resetiosflags(ios_base::left);} while (1);}else if (2 == choice) {unsigned i = 0, j = 0;for (; i < teachers.size(); ++i) {cout << i << ". " << teachers[i][0].teacher << "\t";if ((i + 1) % 4 == 0) cout << "\n";}cout << "\n";do {cout << "\n请输入待查询教师的序号：（输入-1结束查询）";cin >> i;if (i == -1) {break;}else if (i >= teachers.size()) {cout << "非法选择\n";continue;}int class_table[4][5];for (unsigned m = 0; m < 4; ++m)for (unsigned n = 0; n < 5; ++n)class_table[m][n] = -1;for (j = 0; j < teachers[i].size(); ++j) {unsigned m = arranges[teachers[i][j].class_loc][teachers[i][j].arrange_loc].classroom_time / 20;class_table[m / 5][m % 5] = j;}string time_slot[4] = { "8:00-9:40", "10:00-11:40", "14:00-15:40", "16:00-17:40" };cout << setiosflags(ios_base::left);cout << setw(54) << " " << teachers[i][0].teacher << "老师课程表\n";cout << "============================================================================== ======================================================\n";cout << setw(12) << " " << setw(24) << "星期一" << setw(24) << "星期二" << setw(24) << "星期三" << setw(24) << "星期四" << setw(24) << "星期五" << "\n";for (unsigned m = 0; m < 4; ++m) {if (m % 2 == 0)cout << "============================================================================== ======================================================\n";elsecout << "------------------------------------------------------------------------------------------------------------------------------------\n";for (unsigned m1 = 0; m1 < 3; ++m1) {if (m1 == 1)cout << setw(12) << time_slot[m];elsecout << setw(12) << "";for (unsigned n = 0; n < 5; ++n) {if (class_table[m][n] != -1) {j = class_table[m][n];if (m1 == 0)cout << setw(24) << arranges[teachers[i][j].class_loc][teachers[i][j].arrange_loc].course;else if (m1 == 1)cout << setw(24) << classrooms[arranges[teachers[i][j].class_loc][teachers[i][j].arrange_loc].classroom_time / 20];elsecout << setw(24) << arranges[teachers[i][j].class_loc][teachers[i][j].arrange_loc].grade_special;}elsecout << setw(24) << " ";}cout << "\n";}}cout << "============================================================================== ======================================================\n";cout << resetiosflags(ios_base::left);} while (1);} else if (3 == choice) {vector<vector<classroom_inverted>> classroomes;for (unsigned i = 0; i < classrooms.size(); ++i) {classroom_inverted cr(classrooms[i]);vector<classroom_inverted> crs;crs.push_back(cr);classroomes.push_back(crs);}unsigned i = 0, j = 0;for (i = 0; i < arranges.size(); ++i) {for (j = 0; j < arranges[i].size(); ++j) {unsigned m = arranges[i][j].classroom_time;if (classroomes[m / 20][0].class_loc == -1) {classroomes[m / 20][0].class_loc = i;classroomes[m / 20][0].arrange_loc = j;}else {classroomes[m / 20].push_back(classroom_inverted(classroomes[m / 20][0].classroom, i, j));}}}for (i = 0; i < classrooms.size(); ++i) {cout << i << ". " << classrooms[i] << "\t";if ((i + 1) % 4 == 0) cout << "\n";}cout << "\n";do {cout << "\n请输入待查询教室的序号：（输入-1结束查询）";cin >> i;if (i == -1) {break;}else if (i >= classrooms.size()) {cout << "非法选择\n";continue;}int class_table[4][5];for (unsigned m = 0; m < 4; ++m)for (unsigned n = 0; n < 5; ++n)class_table[m][n] = -1;for (j = 0; j < classroomes[i].size(); ++j) {unsigned m = arranges[classroomes[i][j].class_loc][classroomes[i][j].arrange_loc].classroom_time % 20;class_table[m / 5][m % 5] = j;}string time_slot[4] = { "8:00-9:40", "10:00-11:40", "14:00-15:40", "16:00-17:40" };cout << setiosflags(ios_base::left);cout << setw(54) << " " << classrooms[i] << "教室课程表\n";cout << "============================================================================== ======================================================\n";cout << setw(12) << " " << setw(24) << "星期一" << setw(24) << "星期二" << setw(24) << "星期三" << setw(24) << "星期四" << setw(24) << "星期五" << "\n";for (unsigned m = 0; m < 4; ++m) {if (m % 2 == 0)cout << "============================================================================== ======================================================\n";elsecout << "------------------------------------------------------------------------------------------------------------------------------------\n";for (unsigned m1 = 0; m1 < 3; ++m1) {if (m1 == 1)cout << setw(12) << time_slot[m];elsecout << setw(12) << "";for (unsigned n = 0; n < 5; ++n) {if (class_table[m][n] != -1) {j = class_table[m][n];if (m1 == 0)cout << setw(24) << arranges[classroomes[i][j].class_loc][classroomes[i][j].arrange_loc].course;else if (m1 == 1)cout << setw(24) << arranges[classroomes[i][j].class_loc][classroomes[i][j].arrange_loc].teacher;elsecout << setw(24) << arranges[classroomes[i][j].class_loc][classroomes[i][j].arrange_loc].grade_special;}elsecout << setw(24) << " ";}cout << "\n";}}cout << "============================================================================== ======================================================\n";cout << resetiosflags(ios_base::left);} while (1);}else {cout << "非法选择\n";}goto loop;}。