教学计划编制问题课程设计报告.doc

中北大学数据结构与算法课程设计说明书 学院、系:软件学院专业:软件工程学生姓名:学号:设计题目:教学计划编制问题起迄日期:2013年12月9日-2013年12月20日指导教师:   ,通过各门课的先修关系来构建个图,该图用邻接表来存储,,:学期总数:6;学分上限:9;本专业共开设12门课,课程号从C00到C11,学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。:ADTGraph{数据对象V:V是具有相同特性的数据元素的集合,:R={VR}VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在直接先修关系}基本操作P:voidCreatGraph(ALGraph*);voidFindInDegree(ALGraph,int*);intTopologicalOrder(ALGraphG,AdjListR,structNamename[])intLocateVex(ALGraphG,VertexTypeu)/*查找图中某个顶点位置*/}:ADTStack{数据对象:D={ai|ai∈ElemSet,i=1,2,…n,n>=0}数据关系:R1={﹤ai-1ai﹥|ai-1,ai∈D,i=2,…,n}基本操作:voidInitStack(SqStack*S);intStackEmpty(SqStackS);voidPush(SqStack*S,int);intPop(SqStack*S,int*e);},调用关系简单:主程序模块 →拓扑排序模块3系统完成功能及功能框图end采用第二种策略:使课程尽可能地集中在前几个学期中根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体创建图CreateGraph():结合先修关系的AOV网,采用邻接链表存储菜单OUTPUT():显示代号所对应课程及课程的先修课程前插法main拓扑排序TopoSort(G):将课程排序后并决定出每学期所学课程输出图G的信息Display(G):^5^11^111067^6^4^72^1134^9^1C22C33C44C55C66C7^7C8^8C99C1010C1111C12^,并存入数组InDegree[i]中(i=0…n)初始化栈Stack,Counter=0ReturnOKReturnERROR依次将入度为0的顶点存入栈中对以i号顶点为尾弧的每个邻接点的入度减1,并将入度减1后为零的顶点号压入栈中,输出i,计数器加1(Counter++)推出栈顶的一个元素(入度为零的顶点号)至i,输出i,计数器加1(Counter++)堆栈是否为空?,即结构体的定义:ode{ intAdjOfV;//该弧所指向的顶点的位置 ode*next;//指向下一条弧的指针}ode;typedefcharVertexType[MAXOfNAME];typedefstruct//链接表{ VertexTypedata;//顶点信息 intgrades;//存储学分信息 ode*first;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VER];//头结点typedefstruct{ AdjListver;//vertices存储课程名 intvexnum,um;//图的当前顶点数和弧数}ALGraph;:printf("请输入下列课程的先修课程(无先修课程输入0结束后也输入0)\n");for(h=0;h<;++h)//构造表结点链表,利用前插法{printf("%s的先修课程:",[h].data);scanf("%s",va);getchar();while(va[0]!='0'){i=LocateVex(G,va);//弧头j=h;//弧尾p=(ode*)malloc(sizeof(ode));p->AdjOfV=j;p->next=[i].first;//[i].first=p;scanf("%s",va);getchar();}:printf("%d个顶点",);for(i=0;i<