数据结构程设计--教学计划编制问题

1、精选优质文档-倾情为你奉上数据结构课程设计报告 题目：教学计划编制 一. 需求分析（1）实验内容和实验目的：1.大学的每个专业都要编制教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限都相等。每个专业开设的课程都是确定的，而且课程的开设时间的安排必须满足先修关系。每个课程的先修关系都是确定的，可以有任意多门，也可以没有。每一门课程恰好一个学期。试在这样的情况下设置一个教学计划编制程序。2.在大学的某个专业中选取几个课程作为顶点,通过各门课的先修关系来构建个图,该图用邻接表来存储,邻接表的头结点存储每门课的信息.3.本程序的目的是为用户编排课程,根据用户输入的信

2、息来编排出每学期要学的课程.（2）测试数据：学期总数：6；学分上限：10；该专业共开设12门课，课程号从01到12，学分顺序为2，3，4，3，2，3，4，4，7，5，2，3。先修关系见教科书图726。（3）测试结果（包含正确和错误的）：正确测试结果：错误测试结果：二. 概要设计1. 抽象数据类型图的定义如下: ADT Graph数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据关系R: R=VR VR=(v,w)|v,wV,(v,w)表示v和w之间存在直接先修关系基本操作P:void CreatGraph(ALGraph *);void FindInDegree(ALGraph ,

3、 int * );void TopologicalSort_1(ALGraph G,int numterm,int maxcredit);void TopologicalSort_2(ALGraph G,int numterm,int maxcredit);ADT Graph栈的定义:ADT Stack数据对象:D=ai|aiElemSet,i=1,2,n,n=0 数据关系:R1=ai-1 ai|ai-1,aiD,i=2,n基本操作:void InitStack (SqStack *S);int StackEmpty(SqStack S);void Push(SqStack *S, int )

4、;int Pop(SqStack *S, int *e);ADT Stack2. 主程序 int main() /主函数 int numterm; /学期总数 int uplcredit; /一个学期的学分上限 int selectway; ALGraph G; printf(请输入学期总数:n); scanf(%d,&numterm); printf(请输入一个学期的学分上限:n); scanf(%d,&uplcredit); CreatGraph(&G); printf(请选择编排策略:1.课程尽可能集中到前几个学期；2.课程尽量均匀分布n);scanf(%d,&selectway); i

5、f(selectway=1) TopologicalSort_1(G,numterm,uplcredit); if(selectway=2) TopologicalSort_2(G,numterm,uplcredit); system(pause); return 0;3. 本程序只有两个模块,调用关系简单. 主程序模块 拓扑排序模块三详细设计1头结点，表结点，邻接表的定义#define MAX_VERTEX_NUM 100 /最大课程总数typedef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode;typedef st

6、ruct VNode char name24; /课程名 int classid; /课程号 int credit; /课程的学分 int indegree; /该结点的入度 int state; /该节点的状态 ArcNode *firstarc; /指向第一条依附该顶点的弧的指针 VNode,AdjListMAX_VEXTEX_NUM;typedef struct AdjList vertices; int vexnum, arcnum; ALGraph;邻接表的基本操作：void CreatGraph(ALGraph *);创建邻接表void FindInDegree(ALGraph ,

7、 int * );求一个结点的入度void TopologicalSort_1(ALGraph G,int numterm,int maxcredit);拓扑排序来编排课程void TopologicalSort_2(ALGraph G,int numterm,int maxcredit);拓扑排序来编排课程2栈的定义：#define STACk_INIT_SIZE 100 /存储空间的初时分配量#define STACKINCREMENT 10 /存储空间的分配增量typedef int ElemType;typedef struct AdjList vertices; int vexnum

8、, arcnum; ALGraph;基本操作：void InitStack (SqStack *S);栈的初始化int StackEmpty(SqStack S);判断栈是否为空void Push(SqStack *S, int );入栈操作int Pop(SqStack *S, int *e);出栈操作3主程序和其他算法int main() /主函数 int numterm; /学期总数 int uplcredit; /一个学期的学分上限 int selectway; ALGraph G; printf(请输入学期总数:n); scanf(%d,&numterm); printf(请输入一个

9、学期的学分上限:n); scanf(%d,&uplcredit);CreatGraph(&G);printf(请选择编排策略:1.课程尽可能集中到前几个学期；2.课程尽量均匀分布n); scanf(%d,&selectway); if(selectway=1) TopologicalSort_1(G,numterm,uplcredit); if(selectway=2) TopologicalSort_2(G,numterm,uplcredit); system(pause); return 0;void CreatGraph(ALGraph *G)/构件图int i, m, n; ArcNo

10、de *p; printf(请输入需要编排课程总数:n); scanf(%d,&G-vexnum); for( i=1;ivexnum;i+) printf(请输入课程名n); scanf(%s,&G-); printf(请输入课程号n); scanf(%d,&G-verticesi.classid); printf(请输入该课程的学分n); scanf(%d,&G-verticesi.credit); G-verticesi.indegree=0; G-vertices i.state=NOTSTUDY; G-verticesi.firstarc=NULL; pr

11、intf(请输入课程先修关系总数：); scanf(%d,&G-arcnum); printf(请顺序输入每个课程先修关系(先修课程在前并以逗号作为间隔):n); for (i = 1; i arcnum; i+) printf(n请输入存在先修关系的两个课程的序号:); scanf(%d,%d,&n,&m); while (n G-vexnum | m G-vexnum) printf(输入的顶点序号不正确 请重新输入:); scanf(%d,%d,&n,&m); p = (ArcNode*)malloc(sizeof(ArcNode); if (p = NULL) printf(memor

12、y allocation failed,goodbey); exit(1); p-adjvex = m; p-nextarc = G-verticesn.firstarc; G-verticesn.firstarc = p; printf(n建立的邻接表为:n); /输出建立好的邻接表 for(i=1;ivexnum;i+) printf(%d:-,G-verticesi.classid); for(p=G-verticesi.firstarc;p!=NULL;p=p-nextarc) printf(%d-,p-adjvex); printf(NULL); printf(n); void In

13、itStack(SqStack *S) S-base=(int *)malloc(STACK_INIT_SIZE *sizeof(int); if (!S-base) printf(ERROR); exit(1); S-top=S-base; S-stacksize=STACK_INIT_SIZE;int StackEmpty(SqStack *S) if(S-top=S-base) return OK; else return ERROR;void Push(SqStack *S,int e) if(S-top - S-base = S-stacksize) S-base = (int *)

14、 realloc (S-base , (S-stacksize + STACKINCREMENT) * sizeof(int); if(!S-base) printf(ERROR); exit(1); S-top = S-base + S-stacksize; S-stacksize += STACKINCREMENT; *S-top+ = e;int Pop(SqStack *S, int *e) if(S-top = S-base) exit(1); *e = * -S-top; return 0;void FindInDegree(ALGraph G, int indegree)/求图中

15、各节点的入度 int i; for (i = 1; i = G.vexnum; i+) indegreei = 0; for (i = 1; i adjvex+; G.verticesi.firstarc = G.verticesi.firstarc-nextarc; void TopologicalSort_1(ALGraph G,int numterm,int uplcredit) FILE *fp; fp=fopen(bianpai.txt,w); ArcNode *p; SqStack S; int indegreeM;/存放各节点的入度 int i,j, k, m,n; int co

16、unt; /课程编排数目计数器 int sumcredit;/每个学期的课程学分累加器 FindInDegree(G, indegree); for (i = 1; i = G.vexnum; i+) G.verticesi.indegree=indegreei; InitStack(&S); count=0; k=0; while(count!=G.vexnum & k=numterm) sumcredit=0; for(i=1;i=G.vexnum;i+) /入度为零的节点入栈，即无先修的课程入栈 if(G.verticesi.indegree=0)&(G.verticesi.state=

17、NOTSTUDY) Push(&S,i); G.verticesi.state = STUDY;/避免入度为零节点重复入栈 if(!StackEmpty(&S)&(sumcredit=uplcredit) k= k+1; printf(n); printf(第%d个学期学得课程有:n,k); sumcredit = 0; for(i=1;i=G.vexnum;i+)/入度为零的节点入栈，即无先修的课程入栈 if(G.verticesi.indegree=0)&(G.verticesi.state=NOTSTUDY) Push(&S,i); while(!StackEmpty(&S)&(sumc

18、redituplcredit)/栈非空&学分总数小于学分上限 Pop(&S,&j); sumcredit = sumcredit + G.verticesj.credit; if(sumcredit nextarc)/对j号顶点每个邻接点的入度减一 G.verticesp-adjvex.indegree-; else Push(&S,j);/将未输出的节点重新压入栈 fprintf(fp,n); printf(n); if(countG.vexnum) printf(n课程编排出错n); else printf(n课程编排成功n); fclose(fp);void TopologicalSor

19、t_2(ALGraph G,int numterm,int uplcredit) FILE *fp; fp=fopen(bianpai.txt,w); ArcNode *p; SqStack S; int indegreeM; int i,j, k, m,n; int maxnum; int sumnum; int count; /课程编排数目计数器 int sumcredit;/每个学期的课程学分累加器 FindInDegree(G, indegree); for (i = 1; i = G.vexnum; i+) G.verticesi.indegree = indegreei; Init

20、Stack(&S); count=0; k=0; maxnum = G.vexnum/numterm+1; sumnum = 0; while(count!=G.vexnum & k=numterm) for(i=1;i=G.vexnum;i+) /入度为零的节点入栈，即无先修的课程入栈 if(G.verticesi.indegree=0)&(G.verticesi.state=NOTSTUDY) Push(&S,i); G.verticesi.state = STUDY; if(!StackEmpty(&S)&(sumcredit=uplcredit)&(sumnum=maxnum) k=

21、k+1; printf(n); printf(第%d个学期学得课程有:,k); sumcredit = 0; sumnum = 0; for(i=1;i=G.vexnum;i+)/入度为零的节点入栈，即无先修的课程入栈 if(G.verticesi.indegree=0)&(G.verticesi.state=NOTSTUDY) Push(&S,i); while(!StackEmpty(&S)&(sumcredituplcredit)&(sumnummaxnum) /栈非空&学分总数小于学分上限&学期课程数目小于学期最大数目 Pop(&S,&j);/出栈 sumcredit = sumcre

22、dit + G.verticesj.credit; sumnum = sumnum+1; if(sumcredit = uplcredit)&(sumnum nextarc)/对j号顶点每个邻接点的入度减一 G.verticesp-adjvex.indegree-; else Push(&S,j); fprintf(fp,n); printf(n); if(countG.vexnum) printf(课程编排出错n); else printf(课程编排成功n); fclose(fp);流程图如下所示：void FindInDegree(ALGraph G, int indegree)/求图中各

23、节点的入度（如下左图）void CreatGraph(ALGraph *G)/构件图（如下右图） void TopologicalSort_1(ALGraph G,int numterm,int uplcredit) /有向图G采用邻接表存储结构(如下左图)void TopologicalSort_2(ALGraph G,int numterm,int uplcredit) /有向图G采用邻接表存储结构（如下右图）主函数：void main()四调试分析：（1）实验过程中出现的问题及解决方法我们在实验过程中遇到的最大难题是两个课程排序算法的编写。刚开始的时候没有任何的思路，网上也只有拓扑排序的算法，对于课程设计要求的排序算法没有任何头绪。经过请教老师和同学以及翻阅了一些相关书籍，并在网上的搜索有了排序算法的大体思路。经过三天的修改，终于写出了符合要求的排序算法。（2