数据结构 教学计划编制

1、软 件 学 院课程设计报告书课程名称 数据结构 设计题目 教学计划编制 2011年 1 月目 录1 设计时间12 设计目的13设计任务14 设计内容14.1需求分析14.2总体设计24.3详细设计54.4测试与分析12测试124.4.2分析154.5 附录155 总结与展望26参考文献27成绩评定281 设计时间 2011年1月3日至2011年1月6日2 设计目的 1）通过课程设计，加深对数据结构这一课程所学内容的进一步理解与巩固。2）通过课程设计，提高程序开发能力，能运用合理的控制流程编写清晰高效的程序。3）通过课程设计，提高C程序调试能力，加强实践能力。4）通过课程设计，培养分析问题、解决

2、实际问题的能力。5）通过课程设计，培养软件设计能力和开发能力。6）通过课程设计，培养交流、团结协作精神。7）通过课程设计，加强个人程序设计能力。3设计任务大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。4 设计内容4.1需求分析 1、程序所能达到的功能(1)数据结构使用有向图和栈。 (2)课程先修关系（图7.26）课程编号课程名称先决

3、条件课程学分01程序设计基础无202离散数学01303数据结构01,02404汇编语言01305语言的设计和分析03,04206计算机原理11307编译原理05，03408操作系统03，06409高等数学无710线性代数09511普通物理09212数值分析09，10，013 (3)如果输入的先修课程号不在该专业开设的课程序列内，则作为错误处理。2、输入的形式和输入值的范围输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。3、输出的形式每学期课程安排4、测试数据： 学期总数6，一学期的学分上限10，该专业共开课程数目12，按照图7.26

4、输入课程名，课程号，课程学分。输出正确的课程编排结果。4.2总体设计1、说明本程序中用到的所有抽象数据类型的定义ADT Graph数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据关系R: R=VRVR=(v,w)|v,wV,(v,w)表示v和w之间存在直接先修关系基本操作P:void CreatGraph(ALGraph *G)操作结果：创造图Gvoid InitStack(SqSttack *S)操作结果：构造一个空栈Svoid StackEmpty(SqStack *S)初始条件：栈S已存在操作结果：若栈S为空栈，则返回TRUE，否则FALSEvoid Push（S

5、qStack *S，int e）初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素void Pop（SqStack *S，int *e）初始条件：栈S已存在且非空操作结果：删除S的栈顶元素，并用e返回其值void FindInDegree(ALGraph G, int indegree)初始条件：拓扑排序完成操作结果：构造关键路径的先修关系网void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)初始条件：图G已存在操作结构：进行拓扑排序，并完成关系网的构造，使课程尽可能集中在前几个学期void TopologicalSort_

6、2(ALGraph G,int numterm,int uplcredit)初始条件：图G已存在操作结果：进行拓扑排序，并完成关系网的构造，使课程尽量均匀分布ADT Graph2、说明主程序的流程开始输入学期总数，一学期学分上限输出编排结果结束构造图表G选择编排方式拓扑排序2课程尽量均匀分布拓扑排序1课程尽可能集中到前几个学期选择1选择2图4.2-2 主程序流程图3、说明各程序模块之间的层次（调用）关系（图4.2-3）主程序模块拓扑排序模块顺序栈SqStack模块图4.2-3各程序模块之间的层次（调用）关系4.3详细设计1、实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法1）采用

7、邻接表存储结构,构造没有相关信息的图G,并储存键入的相关信息 void CreatGraph(ALGraph *G) 通过循环语句完成对键入的课程名称，课程号，学分的存储，并课程先修关系建立邻接表 for (i = 1; i <= G->arcnum; i+) /* 构造顶点向量 */ printf("n请输入存在先修关系的两个课程的序号:"); scanf(&n,&m); while (课程号不在编入范围) printf("输入的顶点序号不正确 请重新输入:"); scanf(&n,&m); 分配头结点的存储

8、空间 if (p为空) printf("分配失败"); 建立邻接表 printf("建立的邻接表);for(i=1;i<=G->vexnum;i+) printf("%d:->",G->verticesi.classid); for(p=G->verticesi.firstarc;p!=NULL;p=p->nextarc) printf("%d->",p->adjvex); printf("NULL"); printf("n"); 2）构

9、造一个空栈Svoid InitStack(SqStack *S) 赋予顺序栈足够的存储空间 if (!S->base) printf(存储分配失败) exit(1); top=base初始栈为空，存储空间为所分配的足够的存储空间3）判断是否为空栈int StackEmpty(SqStack *S) if(栈S为空栈) return OK; else return ERROR;4）入栈操作void Push(SqStack *S,int e) 插入元素e为新的栈顶元素 if(栈满)为栈重新分配存储空间 if(!S->base) printf(存储分配失败) exit(1); top=

10、base初始栈为空，存储空间为所分配的足够的存储空间 栈顶指针上移5. 取栈顶操作int Pop(SqStack *S, int *e) 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if(栈顶元素为空) exit(1); 栈顶指针下移并将其值返回给*e6）求图中各节点的入度void FindInDegree(ALGraph G, int indegree) for (i = 1; i <= G.vexnum; i+) indegreei = 0; for (i = 1; i <= G.vexnum; i+) while (G.verticesi.fi

11、rstarc) indegreeG.verticesi.firstarc->adjvex+; G.verticesi.firstarc = G.verticesi.firstarc->nextarc; 7）有向图G采用邻接表存储结构void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则返回ERROR。 int indegreeM;存放各节点的入度 int count; 课程编排数目计数器 int sumcredit;每个学期的课程学分累加器 FindInDegre

12、e(G, indegree);对各顶点求入度indegree0.vernum-1 for (i = 1; i <= G.vexnum; i+) G.verticesi.indegree=indegreei; 初始化栈 while(count!=G.vexnum && k<=numterm) sumcredit=0; for(无先修的课程入栈) if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY) Push(&S,i); G.verticesi.state = STUDY;避免入度为零

13、节点重复入栈 if(栈非空且学分计数器小于学分上限) k= k+1; printf("第%d个学期学得课程有:n",k); for(i=1;i<=G.vexnum;i+)入度为零的节点入栈，即无先修的课程入栈 if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY) Push(&S,i); while(栈非空&&学分总数小于学分上限) Pop(&S,&j); sumcredit = sumcredit + G.verticesj.credit; if(学分计

14、数器小于等于学分上限) printf(" %s ",G.); 课程数目累加 对j号顶点每个邻接点的入度减一 将未输出的节点重新压入栈 if(被编排课程<编排课程总数) printf(课程编排出错); else printf(课程编排成功); 8) 有向图G采用邻接表存储结构若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则返回ERRORvoid TopologicalSort_2(ALGraph G,int numterm,int uplcredit) 头结点指针P调用栈S FindInDegree(G, indegree); for

15、 (i = 1; i <= G.vexnum; i+) G.verticesi.indegree = indegreei; InitStack(&S); 课程编排计数器赋值为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)

16、 Push(&S,i); G.verticesi.state = STUDY; if(栈非空，学分计数器小于学分上限) k= k+1; 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(栈非空&&学分总数小于学分上限&&

17、学期课程数目小于学期最大数目) 出栈 积分器累加 sumnum = sumnum+1; if(sumcredit <= uplcredit)&&(sumnum <= maxnum) printf(" %s ",G.); 编排计数器累加 for(对j号顶点每个邻接点的入度减一) G.verticesp->adjvex.indegree-; else Push(&S,j); if(课程未全部编排，有剩余) printf(课程编排出错) else printf(课程编排成功) 2、对主程序和其它主要函数写出伪码

18、算法int main() int numterm; /*学期总数*/ int uplcredit; /*一个学期的学分上限*/ int selectway; 建立邻接表 scanf("%d",&numterm); 输入学期总数 scanf("%d",&uplcredit); 输入一个学期的学分上限 printf("选择编排策略:1.课程尽可能集中到前几个学期；2.课程尽量均匀分布"); if(选择1) TopologicalSort_1(G,numterm,uplcredit); if(选择2) Topological

19、Sort_2(G,numterm,uplcredit); return 0;3、画出函数的调用关系图（图4.3-3）main( )GreatGraph（）InitStack（）FindInDegree（）图4.3-3函数的调用关系图FindInDegree（）InitStack（）Topologicalsort_1（）Topologicalsort_2（）4.4测试与分析测试学期总数: 6 一学期的学分上限: 10 该专业共开课程数目: 121.键入学期总数，学分上限，比安排课程总数2.输入课程名，课程号及相应学分3. 输入课程先修关系总数 4. 顺序输入先修关系 5.输出邻接表6.选择编排策

20、略1，输出编排结果7. 选择编排策略2，输出编排结果8.错误运行：当输入两个相同课程号的不同课程9.运行结果4.4.2分析1、调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析在实验过程中遇到的最大难题是两个课程排序算法的编写。刚开始的时候没有任何的思路，网上也只有拓扑排序的算法，对于课程设计要求的排序算法没有任何头绪。经过请教老师和同学以及翻阅了一些相关书籍，并在网上的搜索有了排序算法的大体思路。经过三天的修改，终于写出了符合要求的排序算法。2、算法的时间复杂度和空间复杂度的分析本程序算法的时间复杂度为O(n)，空间复杂度为O(2n) 4.5 附录源程序代码及必要注释/* No

21、te:Your choice is C IDE */#include "stdio.h"#include "string.h"#include "malloc.h"#include "stdlib.h"/* 图的邻接表存储表示 */#define MAX_VERTEX_NUM 100 /*最大课程总数*/#define STACK_INIT_SIZE 100 /*存储空间的初时分配量*/#define STACKINCREMENT 10 /*存储空间的分配增量*/#define OK 1#define ERROR

22、0#define M 100#define NOTSTUDY -1#define STUDY 1typedef struct ArcNode int adjvex; /* 该弧所指向的顶点的位置 */ struct ArcNode *nextarc; /* 指向下一条弧的指针 */ ArcNode;typedef struct VNode char name24; /*课程名*/ int classid; /*课程号*/ int credit; /*课程的学分*/ int indegree; /*该结点的入度*/ int state; /*该节点的状态*/ ArcNode *firstarc;

23、 /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */VNode,AdjList100;typedef int ElemType;typedef struct AdjList vertices; int vexnum, arcnum; /* 图的当前顶点数和弧数 */ ALGraph;typedef structElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */ ElemType *top; /*栈顶指针*/ int stacksize; /* 当前已分配的存储空间，以元素为单位 */ SqStack; /* 顺序栈 */ void Creat

24、Graph(ALGraph *G) /* 采用邻接表存储结构,构造没有相关信息的图G,并储存键入的相关信息 */ int i, m, n; ArcNode *p; printf("请输入需要编排课程总数:n"); scanf("%d",&G->vexnum); for(i=1;i<=G->vexnum;i+) /* 构造顶点向量 */ printf("请输入课程名n"); scanf("%s",&G->); printf("请输入课程号n

25、"); scanf("%d",&G->verticesi.classid); printf("请输入该课程的学分n"); scanf("%d",&G->verticesi.credit); G->verticesi.indegree=G->vertices i.state=NOTSTUDY; G->verticesi.firstarc=NULL; printf("请输入课程先修关系总数："); scanf("%d",&G->a

26、rcnum); printf("请顺序输入每个课程先修关系(先修课程在前并以逗号作为间隔):n"); for (i = 1; i <= G->arcnum; i+) /* 构造顶点向量 */ printf("n请输入存在先修关系的两个课程的序号:"); scanf("%d,%d",&n,&m); while (n < 0 | n > G->vexnum | m < 0 | m > G->vexnum) printf("输入的顶点序号不正确 请重新输入:"

27、;); scanf("%d,%d",&n,&m); p = (ArcNode*)malloc(sizeof(ArcNode); if (p = NULL) printf("memory allocation failed,goodbey"); exit(1); p->adjvex = m; p->nextarc = G->verticesn.firstarc; G->verticesn.firstarc = p; printf("n建立的邻接表为:n"); /*输出建立好的邻接表*/ for(i

28、=1;i<=G->vexnum;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 InitStack(SqStack *S) /* 构造一个空栈S */S->base=(int *)

29、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) /* 若栈S为空栈，则返回TRUE，否则 返回FALSE */ if(S->top=S->base) return OK; else return ERROR;void Push(SqStack *S,int e) /*

30、 插入元素e为新的栈顶元素 */ if(S->top - S->base >= S->stacksize) S->base = (int *) realloc (S->base , (S->stacksize + STACKINCREMENT) * sizeof(int); if(!S->base) printf("ERROR");/* 存储分配失败 */ exit(1); S->top = S->base + S->stacksize; S->stacksize += STACKINCREMENT;

31、*S->top+ = e;int Pop(SqStack *S, int *e)/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ if(S->top = S->base) exit(1); *e = * -S->top; return 0;void FindInDegree(ALGraph G, int indegree)/*求图中各节点的入度*/ int i; for (i = 1; i <= G.vexnum; i+) indegreei = 0; for (i = 1; i <= G.vexnum; i+) whi

32、le (G.verticesi.firstarc) indegreeG.verticesi.firstarc->adjvex+; G.verticesi.firstarc = G.verticesi.firstarc->nextarc; void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)/* 有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK,否则返回ERROR。*/ int i=0,j, k; ArcNode *p; SqStack S; int indegreeM;/*存放各节点的入

33、度*/ int count; /*课程编排数目计数器*/ int sumcredit;/*每个学期的课程学分累加器*/ FindInDegree(G, indegree); /* 对各顶点求入度indegree0.vernum-1 */ 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&

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

35、 = 0; for(i=1;i<=G.vexnum;i+)/*入度为零的节点入栈，即无先修的课程入栈*/ if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY) Push(&S,i); while(!StackEmpty(&S)&&(sumcredit<uplcredit)/*栈非空&&学分总数小于学分上限*/ Pop(&S,&j); sumcredit = sumcredit + G.verticesj.credit; if(sumcredit

36、 <= uplcredit) printf(" %s ",G.); count+; for(p=G.verticesj.firstarc;p;p=p->nextarc)/*对j号顶点每个邻接点的入度减一*/ G.verticesp->adjvex.indegree-; else Push(&S,j);/*将未输出的节点重新压入栈*/ printf("n"); if(count<G.vexnum) printf("n课程编排出错n"); else printf("n课

37、程编排成功n"); void TopologicalSort_2(ALGraph G,int numterm,int uplcredit) FILE *fp; int indegreeM; int i,j, k; int maxnum; int sumnum; int count; /*课程编排数目计数器*/ int sumcredit=0;/*每个学期的课程学分累加器*/ ArcNode *p; SqStack S; FindInDegree(G, indegree); for (i = 1; i <= G.vexnum; i+) G.verticesi.indegree =

38、 indegreei; InitStack(&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(!Stac

39、kEmpty(&S)&&(sumcredit<=uplcredit)&&(sumnum<=maxnum) k= 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,

40、i); while(!StackEmpty(&S)&&(sumcredit<uplcredit)&&(sumnum<maxnum) /*栈非空&&学分总数小于学分上限&&学期课程数目小于学期最大数目*/ Pop(&S,&j);/*出栈*/ sumcredit = sumcredit + G.verticesj.credit; sumnum = sumnum+1; if(sumcredit <= uplcredit)&&(sumnum <= maxnum) printf(" %s ",G.); count+; for(p=G.verticesj.firstarc;p;p=p->nextarc)/*对j号顶点每个邻接点的入度减一*/ G.verticesp->adjvex.indegree-; else Push(&S,j); printf("n"); if(count<G.vexnum) printf("课程编排出错n&