广工 数据结构 课程设计 教学计划编制问题

序号：

《数据结构》课程设计

题 目 _教学计划编制问题___ 学 院 计算机 专 业 年级班别 学 号 学生姓名 指导教师 杨劲涛

思路

2013 年 6 月 29 日 理论 答辩

难度系数 代码 总成绩 建议的报告结构和所需要包含的内容，仅供参考：

一、 课程设计任务要求

设计任务：

大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。 设计要求：

(1)输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。 (2)允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽量可能地集中在前几个学期中。 (3)若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到屏幕。计划的表格格式自行设定。

二、已完成的项目及完成程度

能进行相关数据的输入，调用，但不能选择编排策略，输出课程有错误。

三、理论依据

图：

typedef struct {

AdjList vertices,verticestwo;

int vexnum,arcnum; /* 图的当前顶点数和弧数 */ int kind; /* 图的种类标志 */ }ALGraph; 链表

typedef struct {

VertexType data; /* 顶点信息 */

ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */ }VNode,AdjList[MAX_VERTEX_NUM]; 堆栈

typedef struct SqStack {

SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */

SElemType *top; /* 栈顶指针 */

int stacksize; /* 当前已分配的存储空间，以元素为单位 */ }SqStack; /* 顺序栈 */

四、主要算法流程图

开始 输入学期总数 输入学分上限 输入拓扑排序形成的课程先修关系的边数 输入课程的学分值 输入课程数 输入课程代表值 输入每条弧(边)的弧尾和弧头 构造图的邻接表 输出图 建堆栈 将符合条件的课程代表值pop入堆栈 将结果push出堆栈并输出 五、主要代码

Status CreateGraph(ALGraph *G)

{ /* 采用邻接表存储结构,构造没有相关信息的图G*/ int i,j,k;

VertexType va,vb; ArcNode *p;

printf(\请输入教学计划的课程数: \ scanf(\

printf(\请输入拓扑排序所形成的课程先修关系的边数: \ scanf(\

printf(\请输入%d个课程的代表值(<%d个字符):\\n\ for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */ { scanf(\ //printf(\ (*G).vertices[i].firstarc=NULL; }

printf(\请输入%d个课程的学分值(<%d个字符):\\n\ for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量 */ {scanf(\ }

printf(\请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\\n\ for(k=0;k<(*G).arcnum;++k) /* 构造表结点链表 */ { scanf(\

i=LocateVex(*G,va); /* 弧尾 */ j=LocateVex(*G,vb); /* 弧头 */

p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j;

p->info=NULL; /* 图 */

p->nextarc=(*G).vertices[i].firstarc; /* 插在表头 */ (*G).vertices[i].firstarc=p;

//printf(\ }

return OK; }

void Display(ALGraph G) { /* 输出图的邻接矩阵G */ int i;

ArcNode *p; switch(G.kind)

{case DG: printf(\有向图\\n\ }

printf(\个顶点：\\n\.vexnum); for(i=0;i

printf(\.vertices[i].data); printf(\条弧(边):\\n\.arcnum); for(i=0;i

p=G.vertices[i].firstarc; while(p)

{printf(\→%s \.vertices[i].data,G.vertices[p->adjvex].data); p=p->nextarc; }

printf(\ } }

Status TopologicalSort(ALGraph G)

{ /* 有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK, */

/* 否则返回ERROR。 */

int i,k,j=0,count,indegree[MAX_VERTEX_NUM]; SqStack S; pathone a; pathtwo b; ArcNode *p;

FindInDegree(G,indegree); /* 对各顶点求入度indegree[0..vernum-1] */ InitStack(&S); /* 初始化栈 */

for(i=0;i

Push(&S,i); /* 入度为0者进栈 */ count=0; /* 对输出顶点计数 */ while(!StackEmpty(S)) { /* 栈不空 */ Pop(&S,&i);

a[i]=*G.vertices[i].data; b[i]=*G.verticestwo[i].data;

printf(\课程%s→学分%s \.vertices[i].data,G.verticestwo[i].data); /* 输出i号顶点并计数 */ ++count;

for(p=G.vertices[i].firstarc;p;p=p->nextarc) { /* 对i号顶点的每个邻接点的入度减1 */ k=p->adjvex;

if(!(--indegree[k])) /* 若入度减为0,则入栈 */ Push(&S,k); } }

if(count

{printf(\此有向图有回路\\n\ return ERROR; } else

{printf(\为一个拓扑序列。\\n\ }

while(q<=xqzs) { int C=0;

if(X<=G.arcnum)

{ while(C<=xfsx)

{C+=*G.verticestwo[Z].data; ++Z; }

printf(\第%d个学期应学课程:\ while(X<=Z)

{cout<<*G.vertices[X].data<<\ ++X; }

cout<

{cout<<\课程编制已经完成！\ return OK; } }

return OK; }

六、实验截图

1. 测试用例

学期总数：6

一学期的学分上限：10

开12门课，分别为c01到c12

学分顺序为：2，3，4，3，2，3，4，4，7，5，2，3 先修关系：

2. 程序截图

3. 实验结果分析

课程->学分输出无误，然而教学计划却只能输出一个字符，弄了好一个晚上都无解……

七、小结

第一次做这种较复杂的数据结构，颇感压力，c语言的不熟练使得这次课程设计困难重重，最后参考了网上的答案才勉强做出一个东西，但有一个致命的bug始终没能修复，留下了遗憾。