拓扑排序实习报告拓扑排序实习报告.docVIP

拓扑排序实习报告 题目：给定课程先修关系，用拓扑排序的方法制订教学计划 完成日期：2012-12-16 需求分析 本题目中，输入学期总数，一学期的学分上限，每门课的课程号，学分和直接先修课程号，允许用户选择2种编排方式：1.使学生个学期中的学习负担尽量均匀。2.使课程尽可能集中在前几个学期中。 若根据给定的条件无解，则报告适当的信息，否则将教学计划输出到用户指定的文件中去。计划的表格自行设计。 概要设计 定义“课程”类型： //“节点”类作用----用于记录每个输入的字符所对应的各种信息 struct node { char name[namelen];//该课程的名称 int point;//该课程的学分 }course[maxn];//定义存储课程的数组 2、本程序包含三个模块: 主程序模块，其中主函数为： int main(){ 输入课程，学期的相应信息 根据先修关系进行拓扑排序 选择课程安排方式 输出课程安排结果； } 插入模块----判断课程名是否出现过，如果出现过则返回对应数组下标，否则使用新的地址作为改课程的存储位置。 查找模块----根据课程名找到存储该课程的数组下标。 拓扑排序模块----根据课程关系获取入度信息后进行拓扑排序。 详细设计 #includeiostream #includevector #define maxn 200 //课程数量 #define namelen 100 //最大名字长度 using namespace std; int n,term,maxpoint,allnum,indegree[maxn],ans[maxn]; char allname[maxn][namelen]; vectorintroad[maxn]; struct node { char name[namelen]; int point; }course[maxn]; int findID(char ch[])//插入模块，有课程名则返回存储位置，没有则开辟新的位置存储该课程并返回-1 { for(int i=0;iallnum;i++) { if(strcmp(allname[i],ch)==0) return i; } strcpy(allname[allnum++],ch); return allnum-1; } int topsort()//对计算好入度的课程进行拓扑排序 { int now=1;//记录当前排列好的个数 while(now=n)//拓扑的最终结果要有n个 { for(int i=0;iallnum;i++) { if(indegree[i]==0) { indegree[i]=-1; ans[now++]=i; int size=(int)road[i].size(); for(int j=0;jsize;j++) { indegree[road[i][j]]--; } break; } } if(i==allnum)//如果找不到新的入度为0的元素则返回-1，代表条件不符合要求 return -1; } return 1;//排序成功则返回1 } int findro(char ch[])//找到该课程名对应的存储位置 { for(int i=1;i=n;i++) { if(strcmp(ch,course[i].name)==0) return i; } return -1; } void solve()//解答函数，拓扑排序后调用该函数，根据用户选择的安排方式安排最终的课程序列 { int option; printf(请输入编排策略\n); printf(平均编排策略请输入1，紧凑编排策略请输入2\n); scanf(%d,option); if(option==1)//如果是平均编排策略 { int sum=0; for(int i=1;i=n;i++) { sum+=course[findro(allname[ans[i]])].point;//算出和学分 } int ave=sum/term+1;//算出平均一个学期应有的学分 int temp=0,nowterm=1,classnum=0; printf(第1学期的课程:\n); for(i=1;i=n;i++) { if(temp+course[findro(allname[ans[i]])].point=maxpointtemp+course[findro(all