文章目录
- 一、题目
- 二、系统设计
-
- 2.1 功能模块图
- 2.2 “课程逻辑”即课程先修关系图
- 2.3 主要函数设计
- 三、问题分析
- 四、实验结果及分析
- 五、源码
- 总结
一、题目 ?大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。
具体要求如下：
(1) 输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。
(2) 允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。
(3) 若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。
二、系统设计 2.1 功能模块图
文章图片
2.2 “课程逻辑”即课程先修关系图
文章图片
?1 9为第一层 2 4 10 11为第二层 3 12 6为第三层 5 8为第四层 7为第五层
?最先输出的第一层节点不是入度为0，而应该最慢输出的节点入度为0，在这里我们可以采用栈，先将入度为0的节点输出到栈，最后弹出到结果数组。
2.3 主要函数设计
| 函数名 | 功能 |
|---|---|
| void mainmenu( ) | 打印文本界面 |
| void Read_file( ) | 读取课程信息 |
| void Print_message( ) | 输出信息 |
| void Adjust_message( ) | 修改信息 |
| void File_Update() | 更新文件信息 |
| void Arrange_Select | 用户选择策略 |
| void Arrange | 用户从排序结果中选择一种进行安排 |
| void Top_Sort | 拓扑排序，均匀安排策略和尽快安排策略，选提供多种安排结果并且尽量差异大 |
- 用户菜单：打印文本界面，从键盘获取字符，按字符选择对应操作，switch结束后再次调用mainmenu，直到switch中选择结束exit。
- 读取课程信息：图的message先开辟空间，然后由文件读取学期数，每学期最大学分，课程总数给图赋值；图的节点数组开辟空间并初始化，循环读取文件课程号，课程学分，邻接表头指针记得置空；检查有无邻接点，有的话循环挂到邻接链表上。
- 打印信息：打印 学期总数 每学期最大学分 必修课程数量；循环打印，课程号、学分、所有先修课程；打印完提示 “任意键回主菜单”，获取字符，然后调用主菜单、
- 修改信息：提示允许修改的信息，获取字符判断哪个信息需要修改；提示输入修改后的值，获取该值，判断是否合法；合法的话赋值给图的相应数据域，提示成功并更新文件内容；非法的话提示出错，按任意键回主菜单，获取字符后调用主菜单。
- 拓扑排序：最先输出的第一层节点不是入度为0，而应该最慢输出的节点入度为0，在这里我们可以采用栈，先将入度为0的节点输出到栈，最后弹出到结果数组。循环打印拓扑排序结果的数据。
- 策略选择：用户选择某种策略后，会调用该函数。该函数的功能首先是调用拓扑排序得到结果，然后显示所有结果给用户，通过用户的选择，使用那个选择的结果序列去调用安排函数。
接着，第一列为课程号，第二列为课程对应学分，第三列为先修课程。
实验结果如下：
主菜单界面
文章图片
课程信息界面
文章图片
信息修改界面
文章图片
文章图片
课程安排界面
文章图片
文章图片
分析：
如上图已完成题目要求，并设置了简单的界面。但由于不了解c++如何绘制图形化界面，总体界面非常简陋。另外，所使用数据也为书中数据，与真实教学中的课程相差甚大，因此只能算是完成了一个demo，还有很大修改提升的空间。
五、源码 strcture.h
#ifndef STRUCTURE_H_INCLUDED
#define STRUCTURE_H_INCLUDED#define AVERAGE1//均匀安排策略
#define QUICKLY0//尽快安排策略
#define MaxClass99//课程总数不超过99
#define MaxTerm12//学期总数不超过12
#define MaxCredit 30//每学期学分不超过30//邻接表表示
typedef struct AdjVexNode {
int AdjVex;
//邻接点位序
AdjVexNode * Next;
//指向下一个邻接点的指针
}AdjVexNode;
//邻接表结点typedef struct{//顶点表结点
char data[3];
//课程编号
int credit;
//节点学分（每门课学分）
AdjVexNode* FirstArc;
//指向邻接表第一个邻边节点的指针域
int In_degree;
//课程入度
}VexNode;
//图节点typedef struct{
int term_num;
//学期数
int max_credit;
//每学期学分上限
}Message;
//学期信息typedef struct{
VexNode* Vex;
//节点数组域
int VexNum;
//节点数
Message* mes;
//每学期的信息(允许修改)
}Class_arrange_Graph;
//图
#endif // STRUCTURE_H_INCLUDEDfunc.h
#ifndef FUNC_H_INCLUDED
#define FUNC_H_INCLUDED
#include "structure.h"void mainmenu();
int Locate(char* ch);
void Read_file();
void Print_message();
void Adjust_message();
void File_Update();
void Arrange_Select(int choice);
void Arrange(VexNode *result,int choice);
void Top_Sort(VexNode *result,int choice);
void Print_Top_Sort_Result();
#endif // FUNC_H_INCLUDEDfunc.cpp
#include "func.h"
#include
#include
#include
#include
#include
#include "string.h"
#include
using namespace std;
extern VexNode result1[100];
extern VexNode result2[100];
extern VexNode result3[100];
extern VexNode result4[100];
extern Class_arrange_Graph G;
void mainmenu()
{
char key;
printf("\n\n\n\n");
printf("欢迎使用课程编排系统\n\n\n");
printf("______________________________________________________________________\n");
printf("1. 查看课程信息\n");
printf("______________________________________________________________________\n");
printf("2. 修改课程信息\n");
printf("______________________________________________________________________\n");
printf("3. 均匀安排课程\n");
printf("______________________________________________________________________\n");
printf("4. 尽快安排课程\n");
printf("______________________________________________________________________\n");
printf("5. 关闭程序\n");
printf("______________________________________________________________________\n");
printf("\n\n\n\n\t ") ;
key=getch();
key=key-'0';
switch(key)
{
case 1:system("cls");
Print_message();
break;
case 2:system("cls");
Adjust_message();
break;
case 3:system("cls");
Arrange_Select(AVERAGE);
break;
case 4:system("cls");
Arrange_Select(QUICKLY);
break;
case 5:exit(0);
default :
cout << "该选项无效,请按任意键回主菜单" << endl;
key=getch();
system("cls");
break;
}mainmenu();
}int Locate(char* ch)//将C1C2C3……等 变为0 1 2...课程号对应的位序
{
return (2 == strlen(ch)) ? ch[1] - '1' : (ch[1] - '0') * 10 + ch[2] - '1';
}void Read_file()
{
FILE* fp = fopen("C:\\Users\\50580\\Desktop\\jiaocheng\\shuju.txt", "r");
if (NULL == fp)
{
printf("未找到文件,可能文件路径有误！！！");
exit(1);
}G.mes=(Message*)malloc(sizeof(Message));
fscanf(fp,"%d%d%d",&G.mes->term_num,&G.mes->max_credit,&G.VexNum);
//读取学期数，每学期最大学分，课程总数
if(G.VexNum > MaxClass || G.mes->term_num > MaxTerm || G.mes->max_credit > MaxCredit)
{
cout << "课程总数或学期数目或每学期最大学分超过上限" <= G.VexNum)//判断课程是否有错误
{
printf("%s课程错误，本专业无其先修课程！\n", G.Vex[i].data);
fclose(fp);
exit(1);
}
AdjVexNode* p = (AdjVexNode*)malloc(sizeof(AdjVexNode));
//更新邻接表结点
p->AdjVex = s;
p->Next = G.Vex[i].FirstArc;
G.Vex[i].FirstArc = p;
}
}
fclose(fp);
AdjVexNode * p;
for (i=0;
iAdjVex].In_degree++;
p=p->Next;
}
}
}void Print_message()
{
printf("学期总数 :%d \t",G.mes->term_num);
printf("每学期最大学分 ： %d \t",G.mes->max_credit);
printf("必修课程数量 ：%d \n",G.VexNum);
cout << "\n\t\t\t本专业提供课程：\n";
for(int i=0;
iNext)
printf("C%d",p->AdjVex+1);
printf("\n");
}cout << "\n\t\t\t按任意键回主菜单" < MaxTerm || term < 1)
{
cout << "\n输入的学期数不合法 (大于最大允许的学期数 或 小于1 或 不是正整数)\n" <term_num=term;
cout << "\n修改成功(注：如果输入 数字+字符 那么只读入数字)\n" < MaxCredit)
{
cout << "\n输入的学分数不合法 (小于1或大于30)\n" <max_credit=credit;
cout << "\n修改成功(如果输入 数字+字符 那么只读入数字)\n" <term_num << " "<< G.mes->max_credit << " " << G.VexNum << "\n" ;
ofs.close();
}void Arrange_Select(int choice)
{
Top_Sort(result1,1);
Top_Sort(result2,2);
//调用4种拓扑排序，存到result 1~4
Top_Sort(result3,3);
Top_Sort(result4,4);
Print_Top_Sort_Result();
cout << "\n\n\n请输入你选择的课程安排先后顺序：";
char key=getch();
if(key=='1')
Arrange(result1,choice);
//根据用户输入，确定使用哪种拓扑排序结果
else if(key=='2')
Arrange(result2,choice);
else if(key=='3')
Arrange(result3,choice);
else if(key=='4')
Arrange(result4,choice);
else
{
cout<<"\n\n选择有误，请按任意键回主菜单";
getch();
system("cls");
mainmenu();
}}void Arrange(VexNode *result,int choice)
{
system("cls");
FILE *fp=fopen("./各学期课程安排结果.txt","w");
int arranged_num=0;
//已经安排了的课程数
int j;
//控制循环的变量
int k;
//控制循环的变量
int course_num;
//本学期安排的课程总数
int per_max_num;
//每学期最大允许课程总数
int sumcredit;
//本学期已安排课程的总学分
int tag;
//标志，用来判断即将安排到本学期的课程 是否有先修课程在本学期
AdjVexNode* p;
//用来遍历 即将安排课程的邻接表 的指针if(choice==QUICKLY)
per_max_num=G.VexNum;
//计算不同情况下的每学期最大课程数。
else
{ if(G.VexNum % G.mes->term_num term_num/2 )
per_max_num = G.VexNum/G.mes->term_num;
else
per_max_num = (G.VexNum/G.mes->term_num+1);
}VexNode this_term_courses[per_max_num];
//存放本学期已经安排的课程for(k=0;
kmax_credit&& tag==0 && course_numAdjVex == Locate(this_term_courses[j].data) )
{
tag=1;
break;
}
}
p=p->Next;
}if(tag==1) break;
fprintf(fp, " %s ", result[arranged_num].data);
printf( " %s ", result[arranged_num].data);
sumcredit+=result[arranged_num].credit;
this_term_courses[course_num]=result[arranged_num];
if(arranged_num==G.VexNum) break;
arranged_num++;
course_num++;
p=result[arranged_num].FirstArc;
}}fclose(fp);
if(k>G.mes->term_num)
{
fp=fopen("./各学期课程安排结果.txt","w");
fprintf(fp,"%s%d","该课程安排先后顺序下，此策略无解,因为安排所需学期数超过学期总数",G.mes->term_num);
fclose(fp);
cout << "\n\n\n该课程安排先后顺序下，此策略无解,因为安排所需学期数超过学期总数"<< G.mes->term_num< S;
//用来存储已被排序完的节点
stack S1;
//用来存储每一层的节点的邻接表指针
Read_file();
//读文件更新入度
if(choice==1)while(tag==0)
{
tag=1;
for(i=G.VexNum-1;
i>=0;
i--)
if(G.Vex[i].In_degree==0)//将一个层次的节点入栈S，同时邻接表头入栈S1
{
S.push(G.Vex[i]);
G.Vex[i].In_degree--;
p=G.Vex[i].FirstArc;
S1.push(p);
tag=0;
}while(S1.empty()==false)//一个层次的邻接点入度减一
{ p=S1.top();
S1.pop();
while(p!=nullptr)
{
G.Vex[p->AdjVex].In_degree--;
p=p->Next;
}
}
}else if(choice==2)while(tag==0)
{
tag=1;
for(i=0;
iAdjVex].In_degree--;
p=p->Next;
}
}
}else if(choice==3)for(i=G.VexNum-1;
i>=0;
i--)
{
if(G.Vex[i].In_degree==0)//找到一个节点入度0就入栈并使邻接点入度减一
{
S.push(G.Vex[i]);
G.Vex[i].In_degree--;
p=G.Vex[i].FirstArc;
while(p!=nullptr)
{
G.Vex[p->AdjVex].In_degree--;
p=p->Next;
}i=G.VexNum;
}
}elsefor(i=0;
iAdjVex].In_degree--;
p=p->Next;
}i=-1;
}
}i=S.size();
if(i main.cpp
#include
#include "structure.h"
#include "func.h"
#include
#include
#include
#include
#include
#include "string.h"
#include
#include
using namespace std;
VexNode result1[100];
VexNode result2[100];
VexNode result3[100];
VexNode result4[100];
Class_arrange_Graph G;
int main()
{
Read_file();
mainmenu();
return 0;
} 总结 此为本人2022年大二下学期数据结构课设中的一道题目。特此记录。
推荐阅读
- java|刷透近200道数据结构与算法，成功加冕“题王”，挤进梦中的字节
- 高级数据结构
- Linux|Linux进程信号
- tree树状图表格的呈现，数据结构
- 高级数据结构（Ⅴ）单词查找树
- c++学习|17.7 单例设计模式共享数据分析、解决与call_once
- c++学习|17.8 condition_variable、wait、notify_one与notify_all
- c++学习|17.6 unique_lock详解
- c++学习|14.4 类内初始化、默认构造函数、“=default”和“=delete”