数据结构-有向图及其应用-教学计划编制系统

内容：

项目名称：教学计划编制系统 项目内容：大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学 年包含两个学期，每个学期的时间长度和学分上限均相等。每个专业开设的课程都是确定的， 而且课程在开设时间的安排上必须满足先修关系。每门课程有哪些先修课程是确定的，可以 有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编 制系统， 该系统需要满足以下功能。 （1） 完成课程进修目录信息的读取。 （2） 完成课程进修目录信息的编辑，包括课程的增加，删除，信息修改等。 （3） 学生的教学计划学期为 6，每个学期的学分上限为 10 分，允许用户指定下列编排策 略进行教学计划的输出 （1） 使学生在各个学期中的负担尽量均匀； （2）使课程尽可能地集中在前几个学期中 若根据给定的条件问题无解，则报告适当信息；否则将教学计划输出到用户指定的 文件中。计划的表格格式自行设计

代码实现：

mian函数的实现：

#include<iostream> #include<string> #include"ALGraph.hpp" using namespace std; void setClassMassage(ALGraph<classMassage>* myGraph) { VNode<classMassage> data[14]; ArcInfo<VNode<classMassage>>arcList[19]; data[0].date.index = 1; data[0].date.classname = "程序设计基础"; data[0].date.wight = 2; data[1].date.index = 2; data[1].date.classname = "离散数学"; data[1].date.wight = 3; data[2].date.index = 3; data[2].date.classname = "数据结构"; data[2].date.wight = 4; data[3].date.index = 4; data[3].date.classname = "汇编语言"; data[3].date.wight = 3; data[4].date.index = 5; data[4].date.classname = "程序设计与分析"; data[4].date.wight = 2; data[5].date.index = 6; data[5].date.classname = "计算机原理"; data[5].date.wight = 3; data[6].date.index = 7; data[6].date.classname = "编译原理"; data[6].date.wight = 4; data[7].date.index = 8; data[7].date.classname = "操作系统"; data[7].date.wight = 4; data[8].date.index = 9; data[8].date.classname = "高等数学"; data[8].date.wight = 7; data[9].date.index = 10; data[9].date.classname = "线性代数"; data[9].date.wight = 5; data[10].date.index = 11; data[10].date.classname = "普通物理"; data[10].date.wight = 2; data[11].date.index = 12; data[11].date.classname = "数值分析"; data[11].date.wight = 3; data[12].date.index = 13; data[12].date.classname = "软件工程"; data[12].date.wight = 3; data[13].date.index = 14; data[13].date.classname = "数据库原理"; data[13].date.wight = 3; arcList[0].From = data[0]; arcList[0].To = data[1]; arcList[0].weight = 2; arcList[1].From = data[0]; arcList[1].To = data[2]; arcList[1].weight = 2; arcList[2].From = data[0]; arcList[2].To = data[3]; arcList[2].weight = 2; arcList[3].From = data[0]; arcList[3].To = data[11]; arcList[3].weight = 2; arcList[4].From = data[1]; arcList[4].To = data[2]; arcList[4].weight = 3; arcList[5].From = data[2]; arcList[5].To = data[4]; arcList[5].weight = 4; arcList[6].From = data[2]; arcList[6].To = data[6]; arcList[6].weight = 4; arcList[7].From = data[2]; arcList[7].To = data[7]; arcList[7].weight = 4; arcList[8].From = data[3]; arcList[8].To = data[4]; arcList[8].weight = 3; arcList[9].From = data[4]; arcList[9].To = data[12]; arcList[9].weight = 2; arcList[10].From = data[4]; arcList[10].To = data[6]; arcList[10].weight = 2; arcList[11].From = data[5]; arcList[11].To = data[7]; arcList[11].weight = 3; arcList[12].From = data[6]; arcList[12].To = data[13]; arcList[12].weight = 4; arcList[13].From = data[7]; arcList[13].To = data[13]; arcList[13].weight = 4; arcList[14].From = data[8]; arcList[14].To = data[9]; arcList[14].weight = 7; arcList[15].From = data[8]; arcList[15].To = data[10]; arcList[15].weight = 7; arcList[16].From = data[8]; arcList[16].To = data[11]; arcList[16].weight = 7; arcList[17].From = data[9]; arcList[17].To = data[11]; arcList[17].weight = 5; arcList[18].From = data[10]; arcList[18].To = data[5]; arcList[18].weight = 2; myGraph->CreateGrah(14, 19, data, arcList); cout << "添加成功" << endl; } void showMenu() { cout << "1.添加测试数据" << endl; cout << "2.添加课程" << endl; cout << "3.删除课程" << endl; cout << "4.修改课程" << endl; cout << "5.添加有向边信息" << endl; cout << "6.删除有向边信息" << endl; cout << "7.修改有向边信息" << endl; cout << "8.判断数据，输出合理的课程排版" << endl; cout << "9.展现图" << endl; cout << "10.退出" << endl; } void addClass(ALGraph<classMassage>* myGraph) { VNode<classMassage> data; data.firstarc = NULL; data.in = 0; cout << "输入课程编号" << endl; cin >> data.date.index; cout << "输入课程名称" << endl; cin >> data.date.classname; cout << "输入课程学分" << endl; cin >> data.date.wight; myGraph->addVex(data); } void deleteClass(ALGraph<classMassage>* myGraph) { VNode<classMassage> data; data.firstarc = NULL; data.in = 0; cout << "输入课程编号" << endl; cin >> data.date.index; myGraph->deleteVex(data); } void changeClass(ALGraph<classMassage>* myGraph) { VNode<classMassage> data; data.firstarc = NULL; data.in = 0; cout << "输入要更新的课程编号" << endl; cin >> data.date.index; cout << "输入课程名称" << endl; cin >> data.date.classname; cout << "输入课程学分" << endl; cin >> data.date.wight; myGraph->changeVex(data); } void addArcList(ALGraph<classMassage>* myGraph) { ArcInfo<VNode<classMassage>>arc; cout << "输入起始边的节点编号" << endl; cin >> arc.From.date.index; cout << "输入结束的节点编号" << endl; cin >> arc.To.date.index; cout << "输入边的权值" << endl; cin >> arc.weight; myGraph->addArc(arc); } void deleteArcList(ALGraph<classMassage>* myGraph) { ArcInfo<VNode<classMassage>>arc; cout << "输入要删除的起始边的节点编号" << endl; cin >> arc.From.date.index; cout << "输入要删除的结束的节点编号" << endl; cin >> arc.To.date.index; myGraph->deleteArc(arc); } void changeArcList(ALGraph<classMassage>* myGraph) { ArcInfo<VNode<classMassage>>arc; cout << "输入要更新的起始边的节点编号" << endl; cin >> arc.From.date.index; cout << "输入要更新的结束的节点编号" << endl; cin >> arc.To.date.index; cout << "输入要更新的边的权值" << endl; cin >> arc.weight; myGraph->changeArc(arc); } void outputFormat(ALGraph<classMassage>* myGraph) { int a = 0; cout << "1.负担均匀课表" << endl; cout << "2.课程集中在前几个学期" << endl; cin >> a; if (a == 1) myGraph->TopOrder1(); else if (a == 2) myGraph->TopOrder2(); cout << "请到桌面查看" << endl; } int main(void) { ALGraph<classMassage>* myGraph = new ALGraph<classMassage>(); while (true) { system("cls"); showMenu(); int a; cin >> a; switch (a) { case 1: setClassMassage(myGraph); break; case 2: addClass(myGraph); break; case 3: deleteClass(myGraph); break; case 4: changeClass(myGraph); break; case 5: addArcList(myGraph); break; case 6: deleteArcList(myGraph); break; case 7: changeArcList(myGraph); break; case 8: outputFormat(myGraph); break; case 9: myGraph->DispGraph(); break; case 10: return 0; break; } system("pause"); } return 0; }

GraphInfo.h头文件的实现：

#pragma once struct classMassage { int index; string classname; int wight; }; //弧信息 template<class ElemType> struct ArcInfo { ElemType From; //起点 ElemType To; //终点 int weight; //权值 }; //弧节点 struct ArcNode { int adjvex; //邻接点位置 int weight; //权值 struct ArcNode* nextarc; }; //顶点节点 template<class ElemType> struct VNode { ElemType date; int in; ArcNode* firstarc; };

ALGraph.cpp有向图类的实现：

#pragma once #include<fstream> #include<iostream> using namespace std; #define MAX 1000 #define TERMNUMBER 6 #define CREDITMAX 10 #include"GraphInfo.h" #include"SqList.hpp" #include"stack.hpp" template<class ElemType> class ALGraph { public: int vexnum; //顶点数目 int arcnum; //弧数目 VNode<ElemType>vertices[MAX];//邻接表 public: ALGraph(); ~ALGraph(); void CreateGrah(int vnum, int anum, VNode<ElemType> data[], ArcInfo<VNode<ElemType> > arcList[]);//创建图 void DispGraph(); //展现图 int TopOrder1(); int TopOrder2(); void IndegreeCal(); //统计每个点的入度 void addVex(VNode<ElemType> data); //添加节点 void deleteVex(VNode<ElemType> data); //删除节点 void changeVex(VNode<ElemType> data); //更新节点 void addArc(ArcInfo<VNode<ElemType>>arc); //添加边 void deleteArc(ArcInfo<VNode<ElemType>>arc);//删除边 void changeArc(ArcInfo<VNode<ElemType>>arc);//更新边 private: int LocateVex(VNode<ElemType> v); //根据顶点信息，返回顶点坐标 }; //添加节点 template<class ElemType> void ALGraph<ElemType>::addVex(VNode<ElemType> data) { int sign = 0; for (int i = 0; i < this->vexnum; i++) { if (this->vertices[i].date.classname == data.date.classname) sign = 1; } if (sign == 1) cout << "节点重复" << endl; else { if (data.date.index != this->vexnum) cout << "节点编号不合理，已自动匹配" << endl; this->vertices[this->vexnum].date.index=this->vexnum+1; this->vertices[this->vexnum].date.classname =data.date.classname; this->vertices[this->vexnum].date.wight =data.date.wight; this->vexnum++; } } //删除节点 template<class ElemType> void ALGraph<ElemType>::deleteVex(VNode<ElemType> data) { int sign = 0; for (int i = 0; i < this->vexnum; i++) { if (this->vertices[i].date.index == data.date.index) { sign = 1; this->vertices[i].date.index = -1; break; } } if (sign == 1) cout << "删除成功" << endl; else cout << "没有找到" << endl; } //更新节点 template<class ElemType> void ALGraph<ElemType>::changeVex(VNode<ElemType> data) { int sign = 0; for (int i = 0; i < this->vexnum; i++) { if (this->vertices[i].date.index == data.date.index) { sign = 1; this->vertices[i].date.classname=data.date.classname; this->vertices[i].date.wight = data.date.wight; break; } } if (sign == 1) cout << "更新成功" << endl; else cout << "没有找到" << endl; } //添加边 template<class ElemType> void ALGraph<ElemType>::addArc(ArcInfo<VNode<ElemType>>arc) { ArcNode* a = new ArcNode(); a->adjvex = arc.To.date.index - 1; a->nextarc = NULL; a->weight = arc.weight; ArcNode* p = this->vertices[arc.From.date.index - 1].firstarc; int sign = 0; while (p != NULL) { if (p->adjvex == a->adjvex) { sign = 1; } p = p->nextarc; } if (sign == 1) cout << "边重复"; else { a->nextarc = this->vertices[arc.From.date.index - 1].firstarc; this->vertices[arc.From.date.index - 1].firstarc = a; this->vertices[arc.To.date.index - 1].in++; cout << "添加成功" << endl; } } //删除边 template<class ElemType> void ALGraph<ElemType>::deleteArc(ArcInfo<VNode<ElemType>>arc) { int sign = 0; if (arc.To.date.index <= this->vexnum) { ArcNode* p = this->vertices[arc.To.date.index - 1].firstarc; while (p != NULL) { if (p->adjvex == arc.From.date.index) { sign = 1; p = p->nextarc; } p = p->nextarc; } } if (sign == 1) cout << "删除成功" << endl; else cout << "没有找到边" << endl; } //更新边 template<class ElemType> void ALGraph<ElemType>::changeArc(ArcInfo<VNode<ElemType>>arc) { int sign = 0; if (arc.To.date.index <= this->vexnum) { ArcNode* p = this->vertices[arc.To.date.index - 1].firstarc; while (p != NULL) { if (p->adjvex == arc.From.date.index) { sign = 1; p->weight = arc.weight; } p = p->nextarc; } } if (sign == 1) cout << "更新成功" << endl; else cout << "没有找到边" << endl; } template<class ElemType> ALGraph<ElemType>::ALGraph() { this->arcnum = 0; this->vexnum = 0; for (int i = 0; i < MAX; i++) { this->vertices[i].in=0; this->vertices[i].firstarc = NULL; } } template<class ElemType> ALGraph<ElemType>::~ALGraph() { } //创建图 template<class ElemType> void ALGraph<ElemType>::CreateGrah(int vnum, int anum, VNode<ElemType> data[], ArcInfo<VNode<ElemType> > arcList[]) { this->arcnum = anum; this->vexnum = vnum; for (int i = 0; i < vnum; i++) { this->vertices[i].date = data[i].date; this->vertices[i].firstarc = NULL; this->vertices[i].in = 0; } for (int i = 0; i < anum; i++) { ArcNode* a = new ArcNode(); a->adjvex = arcList[i].To.date.index-1; a->nextarc = NULL; a->weight = arcList[i].weight; ArcNode* p = this->vertices[arcList[i].From.date.index-1].firstarc; int sign = 0; while (p != NULL) { if (p->adjvex == a->adjvex) { sign = 1; } p = p->nextarc; } if (sign == 1) cout << "边重复"; else { a->nextarc = this->vertices[arcList[i].From.date.index - 1].firstarc; this->vertices[arcList[i].From.date.index - 1].firstarc = a; this->vertices[arcList[i].To.date.index - 1].in++; } } } //展现图 template<class ElemType> void ALGraph<ElemType>::DispGraph() { for (int i = 0; i < this->vexnum; i++) { ArcNode*p = this->vertices[i].firstarc; if (this->vertices[i].date.index != -1) { cout << this->vertices[i].date.index << "连接的点有："; while (p != NULL) { cout << p->adjvex + 1 << " "; p = p->nextarc; } cout << endl; } } } template<class ElemType> int ALGraph<ElemType>::TopOrder1() { int signTrem = 1; //记录学期数 int sumCredit = 0; //记录学期总学分 for (int i = 0; i < this->vexnum; i++) { sumCredit += this->vertices[i].date.wight; } int average = sumCredit / TERMNUMBER; //记录平均每学期修的学分 int number = this->vexnum; //记录课程门数 int lastNumber = number; //记录输出课程门数 int a[1000]; //记录课程的入度 //初始化度 for (int i = 0; i < number; i++) a[i] = this->vertices[i].in; int everySum = 0; //记录每个学期的学分数 cout << "第 1 学期：" << endl; while (signTrem < 7) { //输出度为0的节点 for (int j = 0; j < number; j++) { int min = MAX; int mini; int signx = 0; for (int i = 0; i < number; i++) { if (a[i] == 0) { if (this->vertices[i].date.wight < min) { min = this->vertices[i].date.wight; mini = i; a[i] = -1; signx = 1; } } } if (signx == 1) { everySum += this->vertices[mini].date.wight; if (everySum > CREDITMAX|| everySum>average) { cout << endl; cout << "第 " << signTrem + 1 << " 学期：" << endl; signTrem++; everySum = 0; everySum += this->vertices[mini].date.wight; } cout << this->vertices[mini].date.classname << "：学分" << this->vertices[mini].date.wight << endl; lastNumber--; } } if (signTrem < 6) { cout << endl; cout << "第 " << signTrem + 1 << " 学期：" << endl; signTrem++; everySum = 0; } else signTrem++; for (int i = 0; i < number; i++) { ArcNode* p = this->vertices[i].firstarc; if (a[i] == -1) { a[i] = -2; while (p != NULL) { a[p->adjvex]--; p = p->nextarc; } } } } if (lastNumber != 0) { system("cls"); cout<<"不能生成"<<endl; } return 0; } template<class ElemType> int ALGraph<ElemType>::TopOrder2() { //输出到文件 ofstream save("C:\\Users\\HUANGYAOHUI\\Desktop\\class.txt"); int signTrem = 1; //记录学期数 int number = this->vexnum; //记录课程门数 int a[1000]; //记录课程的入度 //初始化度 for (int i = 0; i < number; i++) a[i] = this->vertices[i].in; int everySum = 0; //记录每个学期的学分数 save << "第 1 学期：" << endl; while (signTrem<7) { //输出度为0的节点 for (int j = 0; j < number; j++) { int min=MAX; int mini; int signx = 0; for (int i = 0; i < number; i++) { if (a[i] == 0) { if (this->vertices[i].date.wight < min) { min = this->vertices[i].date.wight; mini = i； signx = 1; } } } if (signx == 1) { a[i] = -1; everySum += this->vertices[mini].date.wight; if (everySum > CREDITMAX) { save << endl; save << "------------------------------------------------------------------------------------------" << endl; save << "第 " << signTrem + 1 << " 学期：" << endl; signTrem++; everySum = 0; everySum += this->vertices[mini].date.wight; } save << this->vertices[mini].date.classname << "：学分" << this->vertices[mini].date.wight << "|\t"; } } if (signTrem < 6) { save << endl; save << "------------------------------------------------------------------------------------------" << endl; save << "第 " << signTrem + 1 << " 学期：" << endl; signTrem++; everySum = 0; } else signTrem++; for (int i = 0; i < number; i++) { ArcNode* p = this->vertices[i].firstarc; if (a[i] == -1) { a[i] = -2; while (p != NULL) { a[p->adjvex]--; p = p->nextarc; } } } } save.close(); return 0; } //统计每个点的入度 template<class ElemType> void ALGraph<ElemType>::IndegreeCal() { for (int i = 0; i < this->vexnum; i++) { cout << this->vertices[i].date.index << "\t入度为:\t" << this->vertices[i].in << endl; } } //根据顶点信息，返回顶点坐标 template<class ElemType> int ALGraph<ElemType>::LocateVex(VNode<ElemType> v) { int sign = -1; for (int i = 0; i < this->vexnum; i++) { if (this->vertices[i].date.index == v.date.index && this->vertices[i].date.classname == v.date.classname && this->vertices[i].date.wight == v.date.wight) { sign=i; break; } } return sign; }