版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、 吉 首 大 学 信息科学与工程学院 数据结构课程设计 课程设计名称: 教学计划编制问题 专 业 班 级 : 10级 计科二班 学 生 姓 名 : 熊海燕 朱敏 刘思 学 号 : 20104042026/28/22 指 导 教 师 : 周铁老师 课程序设计时间: 2012.11.24-2012.12.05 前 言 数据结构是一门综合性较强的计算机软件、程序设计理论和技术相结合的重要基础课程。它主要讨论抽象数据关系和算法在计算机中的表示与实现,涉及到的数据在计算机中的表示、组织和处理,以及相应结构上的算法设计和算法性能上的分析技术。它所包含的知识与提倡的技术方法,无论对大家进一步学习计算机领域里
2、的其他课程,还是对今后从事理论研究、应用开发及技术管理工作都起着重要的作用。如何合理地组织数据、有效地存储和处理数据,正确地设计算法以及对算法的分析和评价。通过学习数据结构这门理论性强、思维抽象、难度较大的课程后,大家就更深入透彻地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法,培养了基本的、良好的程序设计技能,大家就能编制高效可靠的程序,更重要的也培养大家解决实际问题的能力,提高分析设计能力和编程能力,为大家后续课程的学习及实践也打下了良好的基础。 因此,学校开设了数据结构(c语言版),通过学习数据结构,大家对编程有了更多的了解,为了让大家将自己所学的知识应用到实际当中,学校开设了数
3、据结构课程设计,通过这次课程设计大家可以更好地将c语言应用到实际当中,而且可以更好的掌握算法与数据结构,将数据结构和c语言有效的结合起来,使大家的编程能力得到更大的提高。关键字:c语言 数据结构 目 录前 言 - 2一、课题内容和设计要求 - 41.1 课题内容 - 41.2 设计要求 - 4二、课题需求分析 - 6三、课题实现模块设计 - 63.1 程序模块设计 - 63.2 函数的调用关系 - 7四、模块的功能实现 - 74.1相关数据类型的定义 - 74.2主要函数的流程图- 8五、程序调试 - 10 5.1 测试数据 - 10 5.2 调试过程 - 10六程序设计总结 - 13七、附录
4、 - 157.1致谢 - 157.2参考书目- 157.3源程序清单 - 15一、课程内容与要求1.1课题内容 问题描述 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限,每学年含两学期,每学期的时间长度和学分上限值均相等,每个专业开设的课程都是确定的,而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的,可以有任意多门,也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。 基本要求 (1)输入参数包括:学期总数,一学期的学分上限,每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。(2)允许用户指定下列两种编排策略之一
5、:一是使学生在各学期中的学习负担尽量均匀;二是使课程尽可能地集中在前几个学期中。(3)若根据给定的条件问题无解,则报告适当的信息;否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。1.2 设计要求(1)按照需求分析和内容要求实现每个模块的功能以及对输入输出的要求。(2)概要设计a、程序是由哪几个大模块构成,模块下又是由哪几个子程序组成,子程序与子程序、模块与模块之间的层次结构、调用关系以及功能的实现。b、课题要求用的数据结构和数据,它们之间具有怎样的内部联系,数据该怎样存储,数据又该存在哪。(3)具体设计 a、采用c语言书实现整个程序 b、利用有向图的一个拓扑序列及其应用问题的算法
6、实现程序,图的邻接表来存储相关数据。 c、画出主函数的流程图和子程序间的调用关系图。 (4)测试分析 a、应采用课题内容要求的数据,并且输出结果能很好的满足要求 b、输入数据是应注意其输入的格式 c、输入的数据应包括正确的输入、输出数据和错误的 输入、输出数据,以便对数据和模块的功能有很好的分析与调整。 d、遇到问题应及时作出修改和调整。 (5)后续工作 a、及时的总结设计中遇到的问题及解决的办法。写下得到的经验教训和心得。b、编制整个设计的目录,记录下大体流程。正文后附带相关参考文件。c、正文书写格式采用四号宋体字。二、需求分析根据问题描述及要求,可知设计中需求定义先修关系的aov网图中的顶
7、点及弧边的结构体,在运行结果中将图的信息显示出来,利用先修关系将课程排序,最后解决问题输出每学期的课程。(1) 采用第二种策略:使课程尽可能地集中在前几学期中。(2) 根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体。(3) 创建图creategraph():结合先修关系的aov图,采用邻接表存储。(4) 菜单output():显示代码所对应课程及课程的先修课程。(5) 拓扑排序topogicalsort():将课程排序后并决定出每学期所学课程。(6) 输出图g大的信息display():将图的顶点和弧边输出。三、课题实现模块设计3.1程序模块设计locatevex(): 图的邻接表
8、存储的基本操作creategraph(): 构造生成树display(): 输出图的邻接矩阵findindegree(): 求顶点的入度initstack(): 构造一个空栈stackempty(): 判断是否为空栈pop(): 出栈push(): 入栈clearstack(): 清空栈judge(): 判断课程号对应的课程序号topologicalsort():输出g顶点的拓扑排序结果output(): 图形输出函数3.2 函数的调用关系void main( )topologicalsort ( )display ( )creatgraph ( )output ( )四、模块的功能实现 4.
9、1相关数据类型的定义 a、程序的实现采用了c语言定义相关的数据类型。其中包括字符常量,整型,字符型,字符串型,typedef 定义的类型,结构体型,单链表节点类型,结构体数组。 b、储存的数据为结构体类型数组,以及结构体单链表结点类型,例如:typedef struct、 arcnodetypedef struct。4.2 主要函数的流程图 begin creategraph() printf(“请输入教学计划的课程数:”) scanf(“%d”,&(*g).vexnum)printf(“先修关系的边数:”)scanf(“%d”,&(g).arcnum)printf(“输入%d课程号.”,(*
10、g).vexnum,max_name) i+ i(*g).vexnum scanf(“%s”,(*g).vertices(i).data) (*g).verticesi.firstarc=nulli+ printf(“输入每条弧.”) k+kadjvex=jp-info=null+kreturn 0 end 五、程序调试5.1测试数据:准备典型的测试数据和测试方案,包括输入及输出结果。 数据如下:学期总数:6; 学分上限:10; 该专业共开设课数:12 课程号:从c01到c12; 学分顺序:2,3,4,3,2,3,4,4,7,5,2,3。 先修顺序:19421221011365788(其中c1
11、c12分别代表:程序设计基础、离散数学、数据结构、汇编语言、语言的设计和分析、计算机原理、编译原理、操作系统、高等数学、线性代数、普通物理、数值分析)5.2调试过程依照提示依次输入:学期总数、每学期的学分上限、教学计划的课程数、按拓扑排序所形成的课程纤秀关系的边数、输入课程的课程号、输入课程的学分值、输入每条弧的弧尾和弧头输出的结果如图:六、程序设计总结 在几天的共同努力中,我们这组在周老师的指导下终于完成了关于教学计划编制问题的课程设计。其中用到了大二学到的数据结构和大一学到的c。因为是前面学的知识,遗忘了不少,但通过这次的课程设计,让我们进一步学习了解了数据结构和c语言,并将我们当初零散的
12、知识点串联起来,可谓是收获颇多。 在课程设计中遇到不少问题,最关键的便是课程的安排。每门课程在时间安排上既要满足先修课的关系,又有学分的限制,虽然学过了很多排序的方法,却没办法把学过的知识转换过来。通过在网上查询资料,参考别人的相关设计,然后又翻阅相关教材,最后在老师的指导下,根据每门课程的先修课以及学分的多少,编写了一个拓扑排序,终于确定了每学期该上什么课。 其实对于拓扑排序我们是学过的,可是却没办法把学过的东西运用其中,当然并不只是拓扑排序,很多东西都学过,看上去很简单,但却没办法与实际联系起来,或许是因为遗忘,或许是对理论掌握的不熟练,所以关键的时候不记得了,但从中可知实践与理论结合之重
13、要。毕竟纸上得来终觉浅,在今后的学习中要注重把理论和实际联系起来。 通过这次课程设计我们认识到以下几点,首先是合作的重要性。一开始我们是各自分工,然后各做各的,但当我们开始工作的时候发现行不通了。专门有人负责需求分析,然后写代码的又是另外一个人,可写代码的时候一样需要知道需求分析,而且一段长长的代码光靠一个人是不行的,于是我们集体分析需求,然后整合出了程序的框架,分析该用到哪些子程序及其各自的功能,最后留一个人填代码就行。当然不能忘了,指导老师也是我们的成员。只有把握团队的力量才能事半功倍! 其次便是学习。一切的知识来源于书本,只有掌握了一定的理论基础才能厚积薄,才能把理论跟实际联系起来。一开
14、始由于课程设计相关知识都是前一个学年学习的,大部分都忘记了(这只能说明我们当初学的就不太好!),只能重翻书本再次学习,而这浪费了我们不少时间。不得不感叹:如果当初认真学,现在恐怕我们已经开始写需求分析了。可世上没有如果,但是有以后。所以我们认识到学习的重要,扎实的理论基础是一切的开始! 最后便是耐心。编程肯定不会一蹴而就,定会出现大大小小的错误,这时就需要极好的的耐心,没有耐心,看着看着就厌烦了,肯定没办法完成。为了不出现太多的错误,在编程的时候就应该按常规的格式的编写程序,这样即使错了也方便寻找。 这次的课程设计让我们学到了不少,不仅拓展了我们的专业知识,更是加强了团队合作的意识,亦锻炼了我
15、们的思维能力,对我们今后的学习有一个引导作用。在以后的学习中注重理论和实践的结合,积累专业知识,学好算法,为以后的工作打下基础!七、附录7.1致谢致谢首先感谢我们的指导老师周铁老师,他在我们的课程设计过程中提出了指导性的方案和架构,并指引我们阅读相关的资料和书籍,使我们在不熟悉的领域中仍能迅速掌握新的技术。在此感谢他为我们打下良好的基础,这是我们这次课程设计能够顺利完成的前提。 另外,刘思在此次课程设计中认真完成的需求分析,朱敏负责的代码,熊海燕在设计完成后对程序的测试,都是不可多得的,在此一并表示感谢。7.2 参考书目1. 数据结构(c语言版) 严蔚敏等編著2. 数据结构题集(c语言版) 严
16、蔚敏等編著3. c语言程序设计(第三版) 谭浩强编著 7.3 源程序清单 /* 输出有向图的一个拓扑序列及其应用问题的算法实现程序 */ #include #include #include #include #include #include #include #include #include #include /* 函数结果状态代码宏定义*/ #define true 1 #define false 0 #define ok 1 #define error 0 #define infeasible -1 typedef int status; typedef int boolean; #
17、define max_name 10 #define maxclass 100 /* 顶点字符串的最大长度 */ #define max_vertex_num 100 int z=0; int x=0; int xlz1,q=1,xlz2; /*xlz1为学期总数,xlz2为学分上限*/ typedef int infotype; typedef char vertextypemax_name; /* 字符串类型 */ typedef enumdggraphkind; /* 有向图,有向网,无向图,无向网 */ /* 图的邻接表存储表示 */ typedef struct arcnode in
18、t adjvex; /* 该弧所指向的顶点的位置 */ struct arcnode *nextarc; /* 指向下一条弧的指针 */ infotype *info; /* 网的权值指针*/ arcnode; /* 表结点 */ typedef struct vertextype data; /* 顶点信息 */ arcnode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */ vnode,adjlistmax_vertex_num; /* 头结点 */ typedef struct adjlist vertices,verticestwo; /*vert
19、ices 存储课程名*/ int vexnum,arcnum; /* 图的当前顶点数和弧数 */ int kind; /* 图的种类标志 */ algraph;/* 图的邻接表存储的基本操作 */ int locatevex(algraph g,vertextype u) /* 初始条件: 图g存在,u和g中顶点有相同特征 */ int i; for(i=0;ig.vexnum;+i) if(strcmp(u,g.verticesi.data)=0) return i; return -1; /* 采用邻接表存储结构,构造设有相关信息的图g*/status creategraph(algrap
20、h *g) int i,j,k; vertextype va,vb; arcnode *p; printf(请输入教学计划的课程数: ); scanf(%d,&(*g).vexnum); printf(n); printf(请输入拓扑排序所形成的课程先修关系的边数: ); scanf(%d,&(*g).arcnum); printf(n); printf(请输入%d个课程的课程号(字母+数字且小于%d个字符):n,(*g).vexnum,max_name); for(i=0;i(*g).vexnum;+i) /* 构造顶点向量 */ scanf(%s,(*g).verticesi.data);
21、 (*g).verticesi.firstarc=null; printf(n); printf(请输入%d个课程的学分值(数字)以空格隔开:n,(*g).vexnum,max_name); for(i=0;i(*g).vexnum;+i) /* 构造顶点向量 */ scanf(%s,(*g).verticestwoi.data); printf(n); printf(请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):n); for(k=0;kadjvex=j; p-info=null; /* 图 */ p-nextarc=(*g).verticesi.firstarc; /* 插在表头
22、*/ (*g).verticesi.firstarc=p; printf(n); return ok; /* 输出图的邻接矩阵g */void display(algraph g) int i; arcnode *p; switch(g.kind) case dg: printf(有向图n); printf(%d个顶点:n,g.vexnum); for(i=0;ig.vexnum;+i) printf(%s ,g.verticesi.data); printf(n); printf(n%d条弧(边):n,g.arcnum); for(i=0;iadjvex.data); p=p-nextarc
23、; printf(n); /* 求顶点的入度 */void findindegree(algraph g,int indegree) int i; arcnode *p; for(i=0;ig.vexnum;i+) indegreei=0; for(i=0;iadjvex+; p=p-nextarc; /*栈的顺序存储表示 */ typedef int selemtype; /* 栈类型 */ #define stack_init_size 10 /* 存储空间初始分配量 */ #define stackincrement 2 /* 存储空间分配增量 */ typedef struct sqs
24、tack selemtype *base; /* 在栈构造之前和销毁之后,base的值为null */ selemtype *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间,以元素为单位 */ sqstack; /* 顺序栈 */ /* 顺序栈的基本操作函数,构造一个空栈s */ status initstack(sqstack *s) (*s).base=(selemtype*)malloc(stack_init_size*sizeof(selemtype); if(!(*s).base) exit(overflow); /* 存储分配失败 */ (
25、*s).top=(*s).base; (*s).stacksize=stack_init_size; return ok; /*判栈空:若栈s为空栈,则返回true,否则返回false*/status stackempty(sqstack s) if(s.top=s.base) return true; else return false;/*出栈操作:若栈不空,则删除s的栈顶元素,用e返回其值,并返回ok;否则返回error*/ status pop(sqstack *s,selemtype *e) if(*s).top=(*s).base) return error; *e=*-(*s).
26、top; return ok; /* 入栈操作:插入元素e为新的栈顶元素 */ status push(sqstack *s,selemtype e) if(*s).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; (*
27、s).stacksize+=stackincrement; *(*s).top)+=e; return ok; /*清空栈的操作*/ void clearstack(sqstack *s) s-top=s-base;/*判断课程编号对应int型号数*/int judge(char str)if(strcmp(c1, str) = 0 | strcmp(c1, str) = 0)return 1;if(strcmp(c2, str) = 0 | strcmp(c2, str) = 0)return 2;if(strcmp(c3, str) = 0 | strcmp(c3, str) = 0)re
28、turn 3;if(strcmp(c4, str) = 0 | strcmp(c4, str) = 0)return 4;if(strcmp(c5, str) = 0 | strcmp(c5, str) = 0)return 5;if(strcmp(c6, str) = 0 | strcmp(c6, str) = 0)return 6;if(strcmp(c7, str) = 0 | strcmp(c7, str) = 0)return 7;if(strcmp(c8, str) = 0 | strcmp(c8, str) = 0)return 8;if(strcmp(c9, str) = 0
29、| strcmp(c9, str) = 0)return 9;if(strcmp(c10, str) = 0 | strcmp(c10, str) = 0)return 10;if(strcmp(c11, str) = 0 | strcmp(c11, str) = 0)return 11;if(strcmp(c12, str) = 0 | strcmp(c12, str) = 0)return 12;待添加的隐藏文字内容2return 0;typedef int pathonemaxclass;typedef int pathtwomaxclass;/* 有向图g采用邻接表存储结构,若g无回路
30、,则输出g的顶点的一个拓扑序列并返回ok, 否则返回error*/status topologicalsort(algraph g) int i,k,j=0,count,indegreemax_vertex_num; bool has=false; sqstack s; pathone a; pathtwo b; arcnode *p; findindegree(g,indegree); /* 对各顶点求入度*/ initstack(&s); /* 初始化栈*/ for(i=0;inextarc) k=p-adjvex; if(!(-indegreek) /* 若入度减为0,则入栈*/ pus
31、h(&s,k); if(countg.vexnum) printf(此有向图有回路。nnn); return error; else printf(为一个拓扑序列。nnn); has=true; findindegree(g,indegree); /* 对各顶点求入度 */ clearstack(&s); printf(*课程计划如下*nn); int qq=1; int xxf; while(qq=xlz1) int result20; int rtop=0; int nn=0; xxf=0; for(i=0;ixlz2)break;indegreei-;for(p=g.verticesi.
32、firstarc;p;p=p-nextarc) k=p-adjvex;indegreek-;resultrtop=i;rtop+; printf(第%d个学期的课程为: ,qq); for(nn=0;nnrtop;nn+) switch(judge(g.verticesresultnn.data)case 1:printf(%s ,程序设计基础);break;case 2:printf(%s ,离散数学);break;case 3:printf(%s ,数据结构);break;case 4:printf(%s ,汇编语言);break;case 5:printf(%s ,语言的设计和分析);break;case 6:pr
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年重庆考客运资格证
- 2024成品采购合同范文
- 2024技术开发合同模板
- 2024物业保洁员工用工合同
- 2024工程装饰合同范文
- 垃圾分类培训会议记录三篇
- 2024标准产品买卖合同书
- 2024建行外汇借款合同范本
- 深圳大学《油料与谷物科学原理》2022-2023学年第一学期期末试卷
- 艾草委托代工合同范本(2篇)
- 《后羿射日故事》PPT课件.ppt
- 马克思的资本有机构成理论与当代中国的经济发展
- 《电工学》试题库及答案(考试必备)
- 如何构建生态班级
- GB∕T 4942-2021 旋转电机整体结构的防护等级(IP代码) 分级
- 食品加工企业安全设计设施专篇
- 高中政治校本课程——趣味哲学1
- 海南省建设工程施工阶段监理服务费计费规则
- 创建五星级班组PPT课件
- TBJWA001-2021健康直饮水水质标准
- 监理日报模板
评论
0/150
提交评论