数据结构课程设计教学计划编制问题.doc-资料库

aaddb213-3d51-4816-b347-9c1708009fad.doc.pdf-第1页.png

第1页 / 共21页

aaddb213-3d51-4816-b347-9c1708009fad.doc.pdf-第2页.png

第2页 / 共21页

aaddb213-3d51-4816-b347-9c1708009fad.doc.pdf-第3页.png

第3页 / 共21页

aaddb213-3d51-4816-b347-9c1708009fad.doc.pdf-第4页.png

第4页 / 共21页

aaddb213-3d51-4816-b347-9c1708009fad.doc.pdf-第5页.png

第5页 / 共21页

aaddb213-3d51-4816-b347-9c1708009fad.doc.pdf-第6页.png

第6页 / 共21页

aaddb213-3d51-4816-b347-9c1708009fad.doc.pdf-第7页.png

第7页 / 共21页

aaddb213-3d51-4816-b347-9c1708009fad.doc.pdf-第8页.png

第8页 / 共21页

石家庄经济学院本科生课程设计报告书题姓学学专目名号院业教学计划编制系统马立杰 411100000000000 信息工程学院计算机专业指导教师张有华完成日期： 2013-06-30

目录 1 需求分析.................................................................................................1 2 概要设计.................................................................................................1 3 详细设计.................................................................................................3 3.1 图的存储表示................................................................................3 3.2 图的相关算法.................................................................................4 3.3 栈的存储.........................................................................................7 3.4 栈的相关算法.................................................................................8 3.5 主函数.............................................................................................9 4 编码调试...............................................................................................10 5 设计体会...............................................................................................17 6 致谢....................................................................................................... 19 7 参考文献...............................................................................................19 8 附录（源程序清单）...........................................................................19 I

教学计划编制系统 1 需求分析 1）问题描述大学的每个专业都要制订教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。 2）功能分析 a．解决教学计划课程编制的问题，据用户输入的信息来编排出每学期要学的课程； b．允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀，二是使课程尽可能地集中在前几个学期中； c. 将教学计划输出到用户指定的文件中，若根据给定的条件问题无解，则报告适当的信息。 3）数据要求 a.输入参数：学期总数，一学期的学分上限，每门课的课程号（固定占 3 位的字母数字串）、学分和直接先修课的课程号； b．输出数据：输出各门课程所对应的学分，以及每学期各门课程的安排。 2 概要设计 1) ADT Graph{ 数据对象 V:V 是具有相同特性的数据元素的集合,称为顶点集. 数据关系 R: R={VR} VR={(v,w)|v,w∈V,(v,w)表示 v 和 w 之间存在直接先修关系} 基本操作 P: void CreatGraph70310(ALGraph *G); 初始条件：V 是图的顶点集，VR 是图中弧的集合。操作结果：按 V 和 VR 的定义构造图 G。 1

void FindInDegree70310(ALGraph , int * ); 初始条件：图中的点 V 存在。操作结果：对图中各顶点求入度。 void TopologicalSort_1_70310(ALGraph G, int numterm, int maxcredit); 初始条件：若构造的图 G 中不存在回路。操作结果：按第一种拓扑排序来编排课程。 void TopologicalSort_2_70310(ALGraph G, int numterm, int maxcredit); 初始条件：若构造的图 G 中不存在回路。操作结果：按第二种拓扑排序来编排课程。 }ADT Graph 栈的定义: ADT Stack{ 数据对象:D={ai|ai∈ElemSet,i=1,2,…n,n>=0} 数据关系:R1={﹤ai-1 ai﹥|ai-1,ai∈D,i=2,…,n} 基本操作: void InitStack70310 (SqStack *S); 操作结果：构造一个空栈 S。 int StackEmpty70310(SqStack S); 初始条件：栈 S 已存在操作结果：若栈 S 为空，则返回 TRUE,否则 FALSE。 void Push70310(SqStack *S, int ); 初始条件：栈 S 已存在。操作结果：插入元素 e 新的栈顶元素。 int Pop70310(SqStack *S, int *e); 初始条件：栈存在并且非空。操作结果：删除 S 的栈顶元素，并用 e 返回其值。 }ADT Stack 2) 功能模块 2

3) 系统界面图 2.1 功能模块图图 2.2 系统界面图 3 详细设计 3.1 图的存储表示 1)拓扑图 typedef struct{ AdjList vertices; //邻接表 int vexnum; int arcnum; //结点数目 //弧数目 }ALGraph; 2)弧 typedef struct ArcNode{ int adjvex; 3

struct ArcNode *nextarc; }ArcNode; 3）结点及邻接表： typedef struct VNode{ char name[24]; //课程名 int classid; //课程号 int credit; //课程的学分 int indegree; //该结点的入度 int state; //该节点的状态 ArcNode *firstarc; //指向第一条依附该顶点的弧的指针 }VNode,AdjList[MAX_VERTEX_NUM]; 3.2 图的相关算法 1）图的建立 void CreatGraph70310(ALGraph *G); int i, m, n; ArcNode *p; printf("请输入需要编排课程总数:\n"); for (k=0;kadjvex = j; p->nextarc = G.vertices[i].firstarc; // 插在表头 G.vertices[i].firstarc = p; scanf("%s",va); } } 1）通过键盘输入课程数量，每一门课程对应一个结点，图采用邻接表存储方式； 4

2)函数 CreatGraph 根据课程数量建立邻接表的表头，存入课程相关信息，如课程名，课程号，课程学分等； 3）建立好表头之后，通过键盘输入先修关系的数目； 4）然后根据先修关系的数目以表头为基础，创建邻接表的链表部分，将弧链接在相应的结点上。 2）入度的求取 void FindInDegree70310(ALGraph G, int indegree[])//求图中各节点的入度 { int i; for (i = 1; i <= G.vexnum; i++) indegree[i] = 0; //初始化为零 for (i = 1; i <= G.vexnum; i++) { while (G.vertices[i].firstarc) { //对每个结点求入度 indegree[G.vertices[i].firstarc->adjvex]++; G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc; } } } void TopologicalSort_1_70310(ALGraph G,int numterm,int uplcredit); void TopologicalSort_2_70310(ALGraph G,int numterm,int uplcredit); 1）根据图求每个结点的入度，遍历所有链， 2）如果某结点在链中，则将该节点的入度+1。 3）遍历之后每个结点的入度存放在第二个参数 indegree 数组中。 3）拓扑排序求课程编排（策略 1） void TopologicalSort_2_70310(ALGraph G,int numterm,int uplcredit) { FindInDegree(G, indegree); InitStack(S); for (i = 0;i < G.vexnum;++i) // 对各顶点求入度 // 初始化栈 //建零入度顶点栈 S if (!indegree[i]) Push(S, i); // 入度为 0 者进栈 // 对输出顶点计数 count = 0; while (!StackEmpty(S)) { Pop(S, i); printf("%s(%d 分),",G.vertices[i].data,G.vertices[i].grades); Temp[j++] = G.vertices[i]; //将当前的拓扑序列保存起来 ++count; for (p =G.vertices[i].firstarc; p; p=p->nextarc)// 对 i // 输出 i 号顶点并计数号顶点的每个邻接点的入度减 1 5

{ } k = p->adjvex; if (!(--indegree[k])) // 若入度减为 0,则入栈 Push(S, k); } if (count < G.vexnum) { printf("此有向图有回路无法完成拓扑排序"); return ERROR; } else printf( " 为一个拓扑序列"); printf("\n"); Return OK Return ERROR void TopologicalSort_2_70310(ALGraph G, int numterm, int maxcredit); 依次将入度为 0 的顶点存入 InDegree 中对每个顶点求入度，并存入数组 InDegree[i]中（i=0…n）初始化栈 Stack,Counter=0 对以 i 号顶点为尾弧的每个邻接点的入度减 1，并将入度减 1 后为零的顶点号压入栈中，输出 i，计数器加 1(Counter++) 推出栈顶的一个元素（入度为零的顶点号）至 i，输出 i，计数器加 1（Counter++）依次将入度为 0 的顶点存入 InDegree 中 a.在有向图中选一个没有前驱的顶点且输出之 b.从图中删除该顶点和所有以它为尾的弧 c.重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止 4）拓扑排序求课程编排（策略 2） void TopologicalSort_2_70310(ALGraph G,int numterm,int uplcredit) { FindInDegree(G, indegree); InitStack(S); for (i = 0;i < G.vexnum;++i) // 对各顶点求入度 // 初始化栈 //建零入度顶点栈 S if (!indegree[i]) Push(S, i); // 入度为 0 者进栈 // 对输出顶点计数 count = 0; while (!StackEmpty(S)) { Pop(S, i); printf("%s(%d 6

资料库

数据结构课程设计教学计划编制问题.doc

相关推荐

课程资源

热门标签

最新资料