《数据结构教学计划编制问题课程设计.doc》由会员分享，可在线阅读，更多相关《数据结构教学计划编制问题课程设计.doc（26页珍藏版）》请在三一办公上搜索。
1、课程设计(论文)题 目 名 称 教学计划编制问题 课 程 名 称 数据结构 学 生 姓 名 杨满平 学 号 1041302054 系 、专 业 信息工程系、2010级计算机科学与技术 指 导 教 师 黄同成 2011年 12 月 25 日摘要数据结构是计算机科学与技术专业的专业基础课，是一门十分重要的核心课程。数据结构的知识为后续专业课程的学习提供必要的知识和技能准备，学好“数据结构”这门课程，对于学习计算机专业的其他课程，如操作系统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益的，而且所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际
2、问题，仅掌握几种计算机程序设计语言是难以应付众多复杂的课题的，要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。例如本次程序设计题目大学的每个专业都要制订教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序AbstractData structures in computer science and technology profe
3、ssional courses, is a very important core curriculum. The data structure knowledge for the following courses to provide the knowledge and skills necessary to prepare, learn data structure of the course, for learning other computer science courses, such as operating system, compiler theory, database
4、management system, software engineering, artificial intelligence, are very useful, and all of the computer system software and the application of software to use various types of data structure. Therefore, in order to better use the computer to solve practical problems, only to grasp some computer p
5、rogramming language is hard to cope with the many complex issues, in order to effectively use computers, give full play to the computers performance, also must learn and master some knowledge about data structure. For example, the program design of University of each professional should develop teac
6、hing plans. The assumption that any profession has a fixed length, each school year with two semesters, each semester and the length of time equal to the credit limit are. Each professional courses are determined, and the creation of curriculum time arrangements must meet prevocational relations. Ea
7、ch course which is a pre-determined curriculum, can have any number of doors, there will be No. Each class just for a semester. Test this premise in the design of a teaching plan programming目录一、课题的主要功11.1程序的功能11.2.输入输出的要求11.3运行环境11.4开发工具1二、概要设计22.1程序的模块组成22.2模块的层次结构及调用关系22.3模块的主要功能32.4数据结构和数据库结构3三主要
8、功能的实现33.1采用C语言定义相关的数据类型。33.2主要函数的流程图43.3画出各函数的调用关系图11四、程序调试124.1测试数据：124.2使用说明13五总结145.1 致谢145.1 程序调试中遇到的问题以及解决问题的方法。145.2 课程设计过程经验教训、心得体会。14六、附录156.1参考书目156.2源程序清单（带注释）16一、课题的主要功1.1程序的功能大学的每个专业都要制订教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任
9、意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。本程序针对本科的学期内容，通过输入实际的课程及先后关系。结合每学期的学分及课程数，制定好学习计划。在输入相关数据后，程序会安排好每学期的课程。1.2.输入输出的要求输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。输出要求输出各门课程所对应的学分，以及每学期各门课程的安排。1.3运行环境1. WINDOWS 7系统2. TurboC2.0编译环境1.4开发工具 C语言二、概要设计2.1程序的模块组成LocateVex（）：图的邻接表存储的基本操作Cre
10、ateGraph（）：构造生成树Display（）：输出图的邻接矩阵FindInDegree（）：求顶点的入度InitStack（）：构造一个空栈ClearStack（）：清空栈StackEmpty（）：判断是否为空栈Pop（）：出栈Push（）：入栈TopologicalSort（）：输出G顶点的拓扑排序结果2.2模块的层次结构及调用关系Main()函数TopologicalSort（）输出G顶点的拓扑排序结果Display（）输出图的邻接矩阵CreateGraph（）生成图2.3模块的主要功能见“详细设计”“主要函数流程图”2.4数据结构和数据库结构储存的数据为结构体类型数组，以及结构体单
11、链表结点类型。1 typedef struct ArcNode弧所指定点位置指向下一条弧的指针网的权值指针intstructInfoType2 typedef struct顶点信息第一个表结点的地址VertexTypeArcNode三主要功能的实现3.1采用C语言定义相关的数据类型。其中包括字符常量，整型，字符型，字符串型，typedef 定义的类型，结构体型，单链表节点类型，结构体数组。3.2主要函数的流程图1.LocateVex（）：图的邻接表存储的基本操作。由初始条件: 图G存在,u和G中顶点有相同特征转而进行判断，若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。int ii=0
12、iG.vexnumreturn i+ireturn -12.CreateGraph（）：构造生成图。采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造种图)。int i,j,k;i=0i(*G).vexnumscanf(%s,(*G).verticesi.data);+iprintf(请输入%d个课程的学分值”)i=0i(*G).vexnumscanf(%s,(*G).verticestwoi.data);+imulti3.Display（）：输出图的邻接矩阵。采用循环设置输出图的邻接矩阵。int i;G.kind=DGprintf(%d个顶点：n,G.vexnum);i=0iG ve
13、xnum+imulti4.FindInDegree（）：求顶点的入度。int ii=0iG.vexnumi+i=0iadjvex+;i+;5.InitStack（）：构造一个空栈。(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);!(*S).base(*S).top=(*S).base;returnOK;6.ClearStack（）：清空栈。S-top=S-base;7.StackEmpty（）：判断栈是否为空。若栈S为空栈，则返回TRUE，否则返回FALSE。S.top=S.basereturnFALSE;8.Pop
14、（）：出栈。若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR。returnOK;*e=*-(*S).top;(*S).top=(*S).base9.Push（）：入栈。插入元素e为新的栈顶元素。(*S).base=(SElemType*)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeofreturnOK;*(*S).top)+=e;(*S).top=(*S).base+(*S).stacksize;!(*S).base(*S).top-(*S).base=(*S).stacksize10.Topological
15、Sort（）：输出G顶点的拓扑排序结果。有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK, 否则返回ERROR。inti,k,j=0,count,indegreeMAX_VERTEX_NUM;multiiG.vexnumcount=0multi!StackEmpty(S)+iPush(&S,i);i=03.3画出各函数的调用关系图StackEmpty( )ClearStack( )FindInDegree( )Push （ ）StackEmpty（ ）Pop( )FindInDgree( )Push （ ）InitStack( )Tolopogicalsort(
16、)Main函数Display( )CreatGraph( )四、程序调试4.1测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。数据如下：学期总数：6；学分上限：10；该专业共开设课数：12课程号：从C01到C12；学分顺序：2，3，4，3，2，3，4，4，7，5，2，3。19421221011365788先修顺序(有向图表示)： 4.2使用说明输入学期总数，学分上限，课程数，先修关系边数，课程代表符号，相对学分值输入完成后执行可得到每个学期的课程结果五总结5.1 致谢
17、本次的课程设计，并不是我自己一个人设计出来的。 首先，我要感谢我的数据结构老师黄同成老师，同时黄老师也是我们本次课程设计的指导老师，更是我在大一的C语言老师，黄老师你在上课的时候每次在我遇到问题的时候都会给我耐心的解答，让我去理解并解决这个问题，虽然本次课程设计黄老师因为比较忙没有能像其他的老师那样经常的指导，但帮助了我们不少，所以在这里我致以最诚挚的谢意，老师，谢谢您！ 另外，我还要感谢在我这次课程设计中帮助过我的同学，谢谢你们一直以来对我的帮助，没有你们也没有我此次的成果，谢谢。5.1 程序调试中遇到的问题以及解决问题的方法。由于程序十分的复杂，遇到了很多常见的语法错误，及逻辑错误。这需要
18、我们不断的调试分析。符号的格式之类，指针的用法，判断输入输出的条件都是十分容易出错的地方。在逐条排除，向同学老师请教后，程序终于得以完成。这让我明白了，解决问题，要细心认真，集思广益，这样才能把问题解决。5.2 课程设计过程经验教训、心得体会。虽然在大一我们已经学习了C语言，但是，直到本期我们才开设了数据结构这一门课程。这门课程让我从C语言那基础再深入的了解了软件开发的复杂性。对以往模糊的经验，起了总结提升的作用。在学习了这门课程后，我们进行了2个星期的课程设计，来实践我们所学这门课的内容。这次实验，我进行了大量的资料查阅，包括向老师请求帮助解释题目要求，对所学知识进行复习。通过这些努力，我对
19、数据结构这门课程有了新的认识，对编程的步骤，有了具体的体会。通过和同学的广泛交流，我体会到了合作的必要性及合作的优势。更重要的是，这个课题完全脱离于只限于书本上的问题，多用在实际生活当中，让我对计算机行业，充满了信心和自豪。以往我们学的计算机知识一般停留在理论上，这让我们不太理解计算机的应用和前景，而较少注重我们对算法的实践锻炼。而这一次的实习既需要我们去联系理论，又需要我们去实践方法，很多东西看上去都学过，但是和实际联系才知道变通的艰难。书上得来的并不是一切，大多还是需要在其它方面去吸收的，这是我这次实习的最大收获。这次的实验让我们知道该如何跨过实际和理论之间的鸿沟。六、附录6.1参考书目1
20、 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，20082 董建寅，黄俊民，黄同成数据结构实验指导与题解M北京：中国电力出版社，2008 3 严蔚敏，吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，20024 唐策善，李龙澍，黄刘生数据结构用C语言描述M北京：高等教育出版社，20016.2源程序清单（带注释）#include #include #include / malloc()等 #include / INT_MAX等 #include / EOF(=Z或F6),NULL #include / atoi()52 #include / eof() #include / fl
21、oor(),ceil(),abs() #include / exit() #include / cout,cin / 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; / Boolean是布尔类型,其值是TRUE或FALSE #define MAX_NAME 10 /* 顶点字符串的最大长度*/ #define MAXC
22、LASS 100 int Z=0; int X=0; int xqzs,q=1,xfsx; typedef int InfoType; typedef char VertexTypeMAX_NAME; /* 字符串类型*/ /* 图的邻接表存储表示*/ #define MAX_VERTEX_NUM 100 typedef enumDGGraphKind; /* 有向图,有向网,无向图,无向网 */ typedef struct ArcNode int adjvex; /* 该弧所指向的顶点的位置*/ struct ArcNode *nextarc; /* 指向下一条弧的指针*/ InfoTyp
23、e *info; /* 网的权值指针）*/ ArcNode; /* 表结点*/ typedef struct VertexType data; /* 顶点信息*/ ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针*/ VNode,AdjListMAX_VERTEX_NUM; /* 头结点*/ typedef struct AdjList vertices,verticestwo; int vexnum,arcnum; /* 图的当前顶点数和弧数*/ int kind; /* 图的种类标志*/ ALGraph;/* 图的邻接表存储的基本操作*/ in
24、t LocateVex(ALGraph G,VertexType u) /* 初始条件: 图G存在,u和G中顶点有相同特征*/ /* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ int i; for(i=0;iG.vexnum;+i) if(strcmp(u,G.verticesi.data)=0) return i; return -1;Status CreateGraph(ALGraph *G) /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造种图) */ int i,j,k; VertexType va,vb; ArcNode *p; pri
25、ntf(请输入教学计划的课程数: ); scanf(%d,&(*G).vexnum); printf(请输入拓扑排序所形成的课程先修关系的边数: ); scanf(%d,&(*G).arcnum); printf(请输入%d个课程的代表值(%d个字符):n,(*G).vexnum,MAX_NAME); for(i=0;i(*G).vexnum;+i) /* 构造顶点向量*/ scanf(%s,(*G).verticesi.data); (*G).verticesi.firstarc=NULL; printf(请输入%d个课程的学分值(%d个字符):n,(*G).vexnum,MAX_NAME)
26、; for(i=0;i(*G).vexnum;+i) /* 构造顶点向量*/ scanf(%s,(*G).verticestwoi.data); printf(请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):n); for(k=0;kadjvex=j; p-info=NULL; /* 图*/ p-nextarc=(*G).verticesi.firstarc; /* 插在表头*/ (*G).verticesi.firstarc=p; return OK; void Display(ALGraph G) /* 输出图的邻接矩阵G */ int i; ArcNode *p; switch(G
27、.kind) case DG: printf(有向图n); printf(%d个顶点：n,G.vexnum); for(i=0;iG.vexnum;+i) printf(%s ,G.verticesi.data); printf(n%d条弧(边):n,G.arcnum); for(i=0;iadjvex.data); p=p-nextarc; printf(n); void FindInDegree(ALGraph G,int indegree) /* 求顶点的入度，算法调用*/ int i; ArcNode *p; for(i=0;iG.vexnum;i+) indegreei=0; /*
28、赋初值*/ for(i=0;iadjvex+; p=p-nextarc; typedef int SElemType; /* 栈类型*/ /*栈的顺序存储表示*/ #define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间，以元素为单位*/ SqS
29、tack; /* 顺序栈*/ /* 顺序栈的基本操作*/ Status InitStack(SqStack *S) /* 构造一个空栈S */ (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!(*S).base) exit(OVERFLOW); /* 存储分配失败*/ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return OK;void ClearStack(SqStack *S) /清空栈的操作S-top=S-base;Status Sta
30、ckEmpty(SqStack S) /* 若栈S为空栈，则返回TRUE，否则返回FALSE */ if(S.top=S.base) return TRUE; else return FALSE; Status Pop(SqStack *S,SElemType *e) /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */ if(*S).top=(*S).base) return ERROR; *e=*-(*S).top; return OK; Status Push(SqStack *S,SElemType e) /* 插入元素e为新的栈顶元素*/ if(*S
31、).top-(*S).base=(*S).stacksize) /* 栈满，追加存储空间*/ (*S).base=(SElemType *)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(SElemType); if(!(*S).base) exit(OVERFLOW); /* 存储分配失败*/ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; *(*S).top)+=e; return OK; typedef int pathoneMAXCLASS
32、;typedef int pathtwoMAXCLASS;Status TopologicalSort(ALGraph G) /* 有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK, */ /* 否则返回ERROR。*/ int i,k,j=0,count,indegreeMAX_VERTEX_NUM; bool has=false; SqStack S; pathone a; pathtwo b; ArcNode *p; FindInDegree(G,indegree); /* 对各顶点求入度indegree0.vernum-1 */ InitStack(&S)
33、; /* 初始化栈*/ for(i=0;iG.vexnum;+i) /* 建零入度顶点栈S */ if(!indegreei) Push(&S,i); /cout*G.verticesi.datanextarc) /* 对i号顶点的每个邻接点的入度减*/ k=p-adjvex; if(!(-indegreek) /* 若入度减为,则入栈*/ Push(&S,k);/cout*G.verticesi.dataendl; if(countG.vexnum) printf(此有向图有回路n); return ERROR; else printf(为一个拓扑序列。n);has=true; FindIn
34、Degree(G,indegree); /* 对各顶点求入度indegree0.vernum-1 */ ClearStack(&S); cout=课程计划如下=endl; int qq=1; /学期数 int xxf; while(qq=xqzs) int result20; int rtop=0; int nn=0; /int ccount=0; / 学期学分计算 xxf=0; for(i=0;ixfsx)break;indegreei-;for(p=G.verticesi.firstarc;p;p=p-nextarc) /* 对i号顶点的每个邻接点的入度减*/k=p-adjvex;inde
35、greek-;/* if(!(-indegreek) 若入度减为,则入栈Push(&S,k);*/resultrtop=i;rtop+; cout第qq个学期的课程为：endl; for(nn=0;nnrtop;nn+) cout课程G.verticesresultnn.dataendl; qq+; return OK;void main() ALGraph f; printf(教学计划编制问题的数据模型为拓扑排序AOV-网结构。n); printf(以下为教学计划编制问题的求解过程:n); printf(请输入学期总数:); scanf(%d,&xqzs); printf(请输入学期的学分上限:); scanf(%d,&xfsx); CreateGraph(&f); Display(f); TopologicalSort(f);
