基于C++的教学编制排课系统

#include <stdio.h> #include <stdlib.h>//用于调用system函数，文件的输入输出 #include <string.h> #include <malloc.h> #define Max 100 //定义顶点表结点 struct VertexNode { char vertex[4]; //顶点的名称 int score; //学分 struct ArcNode *firstedge; //边表的头指针 }; //定义弧表结点 struct ArcNode { char adjvex[4]; //邻接点域 struct ArcNode *next; //指向下一个边结点的指针 }; typedef struct { struct VertexNode vexs[Max];//结点类型的vexs数组 int vexnum, arcnum; //记录AOV网的顶点数和边数 }AdjList; //创建AOV网 void CreateGraph(AdjList *Graph) { int i, j, k1, k2, flag; char ch1[4], ch2[4]; struct ArcNode *p1, *p2;//p1,p2是结点类型的指针 printf("请输入依次%d个课程号(每个学号占三个字母,以空格间隔):\n", Graph->vexnum); //输入全部的课程号 for(i = 0; i < Graph->vexnum; i++) { //先从键盘输入各个顶点，先将各个顶点初始化，使每个顶点都不相关 scanf("%s", &((Graph->vexs[i]).vertex)); (Graph->vexs[i]).firstedge = NULL; } printf("请输入依次%d个课程的学分:\n", Graph->vexnum); //输入全部的课程学分 for(i = 0; i < Graph->vexnum; i++) { scanf("%d", &((Graph->vexs[i]).score));//从键盘输入各个顶点的学分信息 } printf("请输入存在先修关系的课程组数: "); //输入存在先修关系的课程数 scanf("%d", &(Graph->arcnum)); //输入全部的先修关系 for(i = 0; i < Graph->arcnum; i++) { flag = 1;//flag是用来标注下列程序是否实现的标识 while(flag) //输入数据正确flag=0循环跳出 { printf("请输入存在先修关系的两个课程的课程号(以空格间隔): "); //从键盘按照先后顺序输入顶点，从而确定其关联(ch1 ch2存放的是顶点信息-课程号) scanf("%s %s", &ch1, &ch2); k1 = k2 = -1; //查找到输入的两个课程号在邻接表中的位置 for(j = 0; j < Graph->vexnum; j++) { //先判断ch1数组中的存储的内容存在于图G中，如果存在就用k1返回其在图中的位置 if(strcmp((Graph->vexs[j]).vertex, ch1) == 0) k1 = j; //否则，再判断ch2数组中的存储的内容存在于图G中，如果存在就用k2返回其在图中的位置 else if(strcmp((Graph->vexs[j]).vertex, ch2) == 0) k2 = j; } //输入课程号有误处理 //如果k1，k2的值都不发生改变，则表示输入的信息都不在图G中，无法进行下列操作 if(k1 ==-1 && k2 == -1) printf("输入的课程号有误，请重新输入!\n"); else flag = 0;//输入信息满足要求，键盘输入的顶点信息人为的设定了关系 } //创建新节点等待插入邻接表的顶点链尾 //动态分配，将新空间的首地址赋给p2 p2 = (struct ArcNode *)malloc(sizeof(struct ArcNode)); strcpy(p2->adjvex, Graph->vexs[k2].vertex);//将图G中vexs[k2]拷贝到p2 p2->next = NULL; p1 = Graph->vexs[k1].firstedge;//与k1（ch1）第一条有关的弧 if(p1 != NULL) //顶点链表尾已插入过（如果不为空的话，即有与其他点相关的弧） { //找到链尾 while(p1->next != NULL) { p1 = p1->next; } //p2指向表结点中的首位置，通过指针p1遍历图G中的所有顶点， //将没有出度的顶点插入到p2前面，从而使先修的课程排在末尾 p1->next = p2; } else { //插入到头结点 Graph->vexs[k1].firstedge = p2; } } } //求AOV网的各顶点入度 void GetInDegree(AdjList Graph, int indegree[])//获得入度的值 { int i, j; struct ArcNode *p;//p为结点类型的指针 for(i = 0; i < Graph.vexnum; i++) { p = Graph.vexs[i].firstedge;//p是指第一个与它相关的弧 while(p != NULL) { //找到入度的点 for(j = 0; j < Graph.vexnum; j++) { //遍历所有的图G中的所有定点，直到找到与p->adjvex所指向的内容相一致的时候跳出循环 // p->adjvex是弧头位置，如果Graph.vexs[j].vertex与弧头位置相匹配，则Graph.vexs[j].vertex有入度 if(strcmp(Graph.vexs[j].vertex, p->adjvex) == 0) break; } //该点入度加1 indegree[j]++; p = p->next; } } } //按策略1 拓扑排序编排课程 void TopologicalSort_1(AdjList Graph, int total, int limit) { int stack[Max]; //顺序栈辅助拓扑排序 int indegree[Max]; //存储AOV网中各节点入度 int i, j, top = -1; int CourseAver; //记录平均每学期的课程数 int count = 0; //记录被编排的个数 int CurScoreTotal = 0; //当前编排学期的学分总数 int CurCourse = 0; //当前编排课程总数 int CourseNum = 0; //当前学期数 int flag; //(标记辅助)flag是用来标注下列程序是否实现的标识 struct ArcNode *p; FILE *fp; //文件指针 fp = fopen("result.txt","w");//fp指针指向只读的result.txt文件 //计算每学期平均课程数 CourseAver = Graph.vexnum / total; if(Graph.vexnum % total != 0) //因为课程数只能为整数，当不能整除时要取上界 CourseAver++; //初始化个顶点入度 for(i = 0; i < Graph.vexnum; i++) { indegree[i] = 0; } //求各顶点入度 GetInDegree(Graph,indegree); //将入度为0的顶点存储到栈中 for(i = 0; i < Graph.vexnum; i++) { if(indegree[i] == 0) stack[++top] = i; } //输出编排结构，并保存在文档中 printf("使学生在各学期中的学习负担尽量均匀来编排 :\n"); fprintf(fp,"使学生在各学期中的学习负担尽量均匀来编排 :\n"); while(top >= 0)//不为空栈 { i = stack[top--]; // 出栈 count++;//课程数加1 //算出最后当前所要修的课程的总学分 CurScoreTotal += Graph.vexs[i].score; flag = 1; while(flag) { //当前学分不超上限并且小于平均课程数 if(CurScoreTotal <= limit && CourseAver > CurCourse) { if(CurCourse == 0)//当前编排课程总数 { CourseNum++;//(学期数)进入每学期的课程编排 printf("第%d学期课程安排顺序为: ", CourseNum); fprintf(fp,"第%d学期课程安排顺序为: ", CourseNum); //屏幕上输出排课结果，并存入fp指针所指向的文件 } //把当前的课程输出，并存储到文件中 printf("%s, ", Graph.vexs[i].vertex); fprintf(fp,"%s, ", Graph.vexs[i].vertex); flag = 0;//flag的值发生改变，排课成功 CurCourse++;//显示最后每个学期的课程安排总数 } else //一切重新置为0，进入排课系统 { CurCourse = 0; CurScoreTotal = 0; printf("\n"); fprintf(fp,"\n"); } } //p为Graph.vexs[i]与其第一相关的指针 p = Graph.vexs[i].firstedge; while(p != NULL) { for(j = 0; j < Graph.vexnum; j++) { //这两个都是代表弧头的顶点，如果匹配的话跳出循环 if(strcmp(Graph.vexs[j].vertex, p->adjvex) == 0) break; } //删除该点所出发的所有与它有关的有向边，由它发出的弧头所在的点的入度减1 indegree[j]--; if(indegree[j] == 0) stack[++top] = j;//将删除后入度为0的点入栈 p = p->next; } } //课程是否全部被编排进去 if(count == Graph.vexnum) { printf("\n编排成功!\n"); printf("结果保存在当前路径下的result.txt文件下!\n"); fprintf(fp,"\n编排成功!\n"); } else { printf("\n编排失败!\n"); fprintf(fp,"\n编排失败!\n"); } fclose(fp); } //按策略2 拓扑排序编排课程 void TopologicalSort_2(AdjList Graph, int total, int limit) { int stack[Max]; //顺序栈辅助拓扑排序 int indegree[Max]; //存储AOV网中各节点入度 int i, j, top = -1; int count = 0; //记录被编排的个数 int CurScoreTotal = 0;//当前编排学期的学分总数 int CurCourse = 0;//当前编排课程总数 int CourseNum = 0;//当前学期数 int flag;//(标记辅助)flag是用来标注下列程序是否实现的标识 struct ArcNode *p; FILE *fp;//文件类型的指针 fp = fopen("result.txt","w");//fp指针指向只读的result.txt文件 //计算每学期平均课程数 for(i = 0; i < Graph.vexnum; i++) { indegree[i] = 0;//初始化将所有顶点的入度都设为0 } GetInDegree(Graph,indegree);//获得所有顶点的入度 //将入度为0 的顶点入栈 for(i = 0; i < Graph.vexnum; i++) { if(indegree[i] == 0) stack[++top] = i; } printf("使课程尽可能地集中在前几个学期中来编排 :\n"); fprintf(fp,"使课程尽可能地集中在前几个学期中来编排 :\n"); while(top >= 0) //栈非空 { i = stack[top--]; count++;//出栈，课程数加1 CurScoreTotal += Graph.vexs[i].score; //计算当前学期的排课中学分 flag = 1; while(flag) { if(CurScoreTotal <= limit)//当学分总数小于上限 { if(CurCourse == 0) { CourseNum++;//(学期数)进入每学期的课程编排 printf("第%d学期课程安排顺序为: ", CourseNum); fprintf(fp,"第%d学期课程安排顺序为: ", CourseNum); //屏幕上输出排课结果，并存入fp指针所指向的文件 } printf("%s, ", Graph.