数据结构课程设计任务书_2011-09-05-08-42-00
- 格式:doc
- 大小:258.50 KB
- 文档页数:25
《数据结构》课程设计任务书一、设计题目1、约瑟夫环2、集合的并、交和差运算3、一元稀疏多项式计算器4、停车场管理5、车厢调度6、文学研究助手7、哈夫曼编/译码器8、图遍历的演示9、最小生成树问题10、哈希表设计二、设计目的数据结构课程设计是计算机专业的集中实践性环节之一,是学习完《数据结构》课程后进行的一次全面的综合练习。
其目的在于加深对数据结构的理解和掌握,使学生更好地掌握数据结构的特点、存储表示、运算方法及其应用,训练学生选用合适的数据结构编写质量高、风格好的应用程序的能力。
三、设计任务每班每人按照学号的顺序依次选择1-10号设计题目,独立完成课题。
(即1、11、21号学生完成1号课题,2、12、22号学生完成2号题,以此类推)四、时间安排五、设计内容1. 约瑟夫环【问题描述】约瑟夫(Joseph) 问题的一种描述是:编号为1,2,… ,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。
一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。
报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。
试设计一个程序求出出列顺序。
【基本要求】利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。
【测试数据】m的初值为20;n=7,7 个人的密码依次为:3,1,7,2,4,8,4,首先m值为6( 正确的出列顺序应为6,1,4,7,2,3,5) 。
【实现提示】程序运行后,首先要求用户指定初始报数上限值,然后读取各人的密码。
可设n≤30。
此题所用的循环链表中不需要“头结点”,请注意空表和非空表的界限。
【选作内容】向上述程序中添加在顺序结构上实现的部分。
2. 集合的并、交和差运算【问题描述】编制一个能演示执行集合的并、交和差运算的程序。
【基本要求】(1) 集合的元素限定为小写字母字符[‘a’..’z’] 。
《数据结构与算法》课程设计教学任务书一、课程设计的目的数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。
数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程,它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础,广泛的应用于信息学、系统工程等各种领域。
学习数据结构与算法是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。
通过课程设计可以提高学生的思维能力,促进学生的综合应用能力和专业素质的提高。
通过此次课程设计主要达到以下目的:了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力;初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;提高综合运用所学的理论知识和方法独立分析和解决问题的能力;训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的科学的工作方法和作风。
二、课程设计的基本要求1. 独立思考,独立完成:课程设计中各任务的设计和调试要求独立完成,遇到问题可以讨论,但不可以拷贝。
2. 做好上机准备:每次上机前,要事先编制好准备调试的程序,认真想好调试步骤和有关环境的设置方法,准备好有关的文件。
3. 按照课程设计的具体要求建立功能模块,要求按照如下几个内容认真完成:1)需求分析:在该部分中叙述,所选课题的功能要求。
2)概要设计:在此说明所选课题的功能模块,以及每个功能模块的算法设计(可以是描述算法的功能模块图),所选课题的的数据结构以及其存储结构设计说明等。
(如果指定存储结构请写出该存储结构的定义)3)详细设计:针对2)中的主要功能模块,画出流程图,给出主要功能模块的流程图、算法及必要的文字说明)4)编码实现:给出3)中主要功能模块的函数实现,重点是函数的声明,变量或参数的说明,以及程序的功能说明与注释,不必把所有代码都写上,主要写出其声明与注释等。
数据结构课程设计报告题目一:图遍历的演示题目二:平衡二叉树的操作演示班级:计算092姓名:魏连龙学号:200907086指导教师:张艳完成日期:2011年6 月29日题目一:图遍历的演示一、需求分析1.以邻接多重表为存储结构;2.实现连通和非连通的无向图的深度优先和广度优先遍历;3.以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和生成树的边集。
4.以教科书图7.33为测试数据。
暂时忽略里程,起点为北京。
二、概要设计1.定义程序中用到的抽象数据类型1)设定图的抽象数据类型:ADT Graph{数据对象V:V是具有相同特性的数据元素的集合,称为点集.数据关系R:R={VR}VR={(v,w)|v,w属于V,(v,w)表示v和w之间存在的路径} 基本操作P:CreatGraph(&G,V,VR)初始条件:V是图的顶点集,VR是图中弧的集合.操作结果:按V和VR是定义构造图G.LocateVex(G,u)初始条件: 图G存在,u和G中顶点有相同的特征操作结果:若图G中存在顶点u,则返回该顶点在图中的位置;否则返回其他信息FirstAjvex(G,v)初始条件: 图G存在,v是G中顶点操作结果:返回v的第一个邻接顶点,若顶在图中没有邻接顶点,则返回为空NextAjvex(G,v,w)初始条件: 图G存在,v是G中顶点,w是v的邻接顶点操作结果:返回v的下一个邻接顶点,若w是v的最后一个邻接顶点,则返回空DFSTraverse(G,visit())初始条件: 图G存在,visit的顶点的应用函数操作结果: 对图进行深度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败BFSTraverse(G,visit())初始条件: 图G存在,visit的顶点的应用函数操作结果:对图进行广度优先遍历,在遍历过程中对每个结点调用visit函数一次,一旦visit失败,则操作失败}ADT Graph2)设定队列的抽象数据类型:ADT Queue{数据对象:D={ai|ai属于Elemset,i=1,2….,n,n>=0}数据关系:R1={<ai-1,ai>|ai-1,ai属于D,i=1,2,…,n}约定ai为端为队列头,an为队列尾基本操作:InitQueue(&Q)操作结果:构造一个空队列QDestryoQueue(&Q)初始条件:队列Q已存在。
算法与数据结构课程设计任务书课程编号:2409080S 课程性质:专业实践课学时/学分:1周/1. 适用专业:计算机科学与技术(交通信息工程)教材:《数据结构》C语言版,严蔚敏、吴伟民编著,清华大学出版社课程设计目的:1.训练学生灵活应用所学数据结构知识,独立完成问题分析,结合数据结构理论知识,编写程序求解指定问题的能力。
2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;3.培养学生在分析问题和解决问题过程严谨的科学态度和良好的工作作风课程设计要求:1.18周周1至周5完成选题、问题分析、算法设计、程序编写、程序测试和程序验收。
2.按照课设格式提交课程设计报告(7月10日)。
3.分数=80%程序+20%报告课程设计题目课程设计题一:学生成绩管理系统设计目的:1.掌握线性链表的建立。
2.掌握线性链表的基本操作。
3.加深对线性链表及其基本操作的理解。
利用线性链表实现学生成绩管理系统。
具体功能:输入、输出、插入、删除、查找、追加、显示、分类合计,并能在屏幕上输出操作前后的结果。
设计要求:1.初始化线性链表。
可以通过键盘输入,进行学生信息的录入。
并根据命令,进行插入、删除、追加、遍历、分类合计等操作。
2.输出操作前后的结果。
3.如果有时间,可以添加保存功能。
即将链表中的学生记录保存到一个文本文件中。
课程设计题二:停车场管理系统设计目的:1.掌握栈和队列的建立。
2.掌握栈和队列的基本操作。
3.深入了解栈和队列的特性,以便在解决实际问题中灵活运用它们。
4.加深对栈和队列的理解和认识。
设计内容:设有一个可以停放n辆汽车的狭长停车场,它只有一个大门可以供车辆进出。
车辆按到达停车场时间的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。
如果停车场已放满n辆车,则后来的车辆只能在停车场大门外的便道上等待,一旦停车场内有车开走,则排在便道上的第一辆车就进入停车场。
《数据结构》课程设计任务书《数据结构》课程设计任务说明一、题目及选题规定1、课程设计题目1)航空客运订票系统2)用二叉树实现家谱的相关运算3)电话客户服务模拟2、选题规定数据结构课程设计需独立完成1个选题内容。
1)~3)选题中任选一个。
二、课程设计进度安排1.问题分析和任务定义(3学时)内容:根据设计题目的要求,充分分析和理解问题,明确问题要求做什么(不是怎么做?),限制条件是什么。
要求:掌握问题分析的方法,以无歧义的陈述说明程序设计的任务;了解以用例图来明确系统功能的方法。
重难点:以无歧义的陈述说明程序设计的任务;对问题作透彻分析,避免出现需求分析错误。
说明:本阶段是解决“做什么”的问题,就是要全面理解用户的各项要求,并准确表达所接受的用户需求。
2.逻辑设计和数据结构的选择(3学时)内容:为操作对象定义相应的数据结构,以结构化程序设计的思想方法为原则划分各个模块,定义数据的抽象数据类型。
要求:掌握逻辑设计和数据结构选择的方法。
重难点:逻辑设计和数据结构选择。
说明:本阶段的主要任务是把需求分析得到得数据流图转换为软件结构和数据结构。
设计软件结构的具体任务是:将一个负责系统按功能进行模块划分、建立模块的层次结构及调用关系、确定模块间的接口及人机界面等。
数据结构设计包括数据特征的描述、确定数据的结构特性、以及数据库的设计。
总体设计建立的是目标系统的逻辑模型,与计算机无关。
3.详细设计和编码(5个学时)内容:算法的具体描述和代码的书写要求:掌握在逻辑设计基础上作详细设计的方法把详细设计的结果进一步求精为程序设计语言程序。
同时加入一些注解和断言,使程序中逻辑概念清楚。
重难点:在逻辑设计基础上作详细设计并编码实现。
说明:本阶段主要任务是设计每个模块的实现算法、所需的局部数据结构。
详细设计的目标有两个:实现模块功能的算法要逻辑上正确和算法描述要简明易懂。
4.上机调试(4个学时)内容:源程序的输入和代码的调试要求:能够熟练掌握调试工具的各种功能,设计测试数据确定疑点,通过修改程序来证实它或绕过它。
1006602《数据结构》课程设计任务书一、设计目的《数据结构》是一门实践性较强的软件基础课程,为了学好这门课程,必须在掌握理论知识的同时,加强上机实践。
本课程设计的目的就是要达到理论与实际应用相结合,使同学们能够根据数据对象的特性,学会数据组织的方法,能把现实世界中的实际问题在计算机内部表示出来,并培养基本的、良好的程序设计技能。
二、设计地点湖南城市学院实验楼计算机房403三、设计时间2011年11月26日——11月30日四、设计分组(43人)五、指导教师:陈强莫照六、设计课题:1.学生搭配问题一班有m个女生,有n个男生(m不等于n),现要开一个舞会.男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞,本曲没成功配对者坐着等待下一曲找舞伴.请设计一系统模拟动态地显示出上述过程,要求如下:1)输出每曲配对情况2)计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值.3)尽量设计出多种算法及程序,可视情况适当加分提示:用队列来解决比较方便.2.飞机订票系统任务:通过此系统可以实现如下功能:录入:可以录入航班情况(数据可以存储在一个数据文件中,数据结构、具体数据自定)查询:可以查询某个航线的情况(如,输入航班号,查询起降时间,起飞抵达城市,航班票价,票价折扣,确定航班是否满仓);可以输入起飞抵达城市,查询飞机航班情况;订票:(订票情况可以存在一个数据文件中,结构自己设定)可以订票,如果该航班已经无票,可以提供相关可选择航班;退票:可退票,退票后修改相关数据文件;客户资料有姓名,证件号,订票数量及航班情况,订单要有编号。
修改航班信息:当航班信息改变可以修改航班数据文件要求:根据以上功能说明,设计航班信息,订票信息的存储结构,设计程序完成功能;3.文章编辑功能:输入一页文字,程序可以统计出文字、数字、空格的个数。
静态存储一页文章,每行最多不超过80个字符,共N行;要求(1)分别统计出其中英文字母数和空格数及整篇文章总字数;(2)统计某一字符串在文章中出现的次数,并输出该次数;(3)删除某一子串,并将后面的字符前移。
数据结构课程设计任务书(2)《数据结构》课程设计任务书年学期: - 第三学期专业班级:14软件(工程技术)指导教师:林开标设计时间: -7-6至 -7-10学时周数:1周一、设计目的1、培养学生运用算法与数据结构的基本知识解决实际编程中的数据结构设计和算法设计问题。
2、培养学生独立设计程序与解决问题的能力,培养学生团队协作集成程序模块及调试能力。
3、培养学生初步的软件设计及软件测试的能力。
二、设计任务及要求基本要求:学生必须仔细阅读《数据结构》课程设计指导书,认真主动完成课程设计的要求。
有问题及时主动经过各种方式与教师联系沟通。
学生要发挥自主学习的能力,充分利用时间,安排好课设的时间计划,并在课程设计过程中不断检测自己的计划完成情况,有困难及时向教师汇报。
课程设计按照教学要求需要一周时间完成,一周中每天(按每周5天)上机调试程序时间不少于4小时,总共至少要上机调试程序15小时。
根据设计报告要求编写设计报告,主要内容包括目的、意义、原理和实现方法简介、过程分析及说明、实验结果情况说明、结论。
每位同学必须有可运行的程序,学生能清楚解释各自编写的程序,并回答教师的提问,学生回答的问题和程序运行的结果作为评分的主要衡量标准;(周三开始逐一检查)。
内容:本次课程设计完成如下模块(共10个模块,学生能够在其中至少挑选3个功能块完成,但有**号的模块是必须要选择的,多做能够加分)(1-2必须选做1题)**1.航班查询系统飞机航班信息包括:航班号、起点站、终点站、起飞时间、到达时间、机型以及票价,实例如下:设计航班查询系统要求能对飞机航班信息进行增加、删除、排序和查找。
可按航班的航班号、起点站、终点站、起飞时间以及到达时间进行查询。
2.停车场管理系统某停车场能够停放n辆汽车,该停车场只有一个大门,每辆汽车离开停车场都要求之前的汽车必须先退出停车场为它让道,而后让道的汽车再次驶入停车场,停车场示意图如下:要求设计停车管理系统,实现车辆的进入、离开并根据停车时间计费。
数据结构与数据处理应用训练课程名称:数据结构与数据处理应用训练计划学时:32学时(1周)一、课程目的1.培养运用数据结构的基本知识解决实际问题的能力;2.加深对数据结构基本知识的理解;3.发挥各人的想象能力和分析能力,拓展思维空间;4.掌握应用程序设计的基本方法;5.培养书写课程设计报告的能力。
二、课程设计内容与要求具体见附录I,每位学生任选一题。
三、考核形式考核办法:结合课程设计作品、课程设计报告和平时情况评定。
评分标准:程序运行及答辩占60%,课程设计报告占20%,平时占20%。
评分等级为优秀、良好、中等、及格、不及格五个级别。
实现难度不同的课程设计,给不同的分数。
若完成项目指定功能,按对应的标准给分;若在完成指定功能的基础上,还添加扩展功能、有创意,给予一定的加分;若减少指定功能的实现或运行有错误,酌情减分。
课程设计要求独立完成,严禁抄袭,如发现雷同,一经证实,相关人都按作弊处理,没有成绩,并且上报学院。
四、应提交材料1、课程设计报告(实习报告)不少于3000字。
格式参见附录II的模板。
内容主要包括:(1) 封面。
(2) 课程设计题目。
(3) 内容与要求(说明课程设计题目的具体内容、需实现的功能及要求,若自己对系统的功能做了增减,按实际完成的功能写)。
(4) 总体设计(说明算法总体思路及由哪几大功能模块组成、各功能模块的功能介绍)。
(5) 详细设计(说明各功能模块的具体实现算法----流程图、存储结构描述、及各功能模块的参数说明)。
(6) 程序测试(给出程序运行结果截图,需包括若干组测试用例以实现对各种情况的测试)。
(7) 总结(说明调试过程中遇到的问题是如何解决的;对设计与实现的回顾讨论与分析、改进设想;收获与体会等)。
(8) 附录(包含源程序)。
2、程序提交完整的工程文件。
在统一答辩完成后,每个教学班交一张光盘,包含所有学生的资料(课程设计报告与程序),每个学生的资料放在以“学号姓名”命名的文件夹中。
《数据结构》课程设计任务书一、设计目的《数据结构》是一门实践性较强的软件基础课程,为了学好这门课程,必须在掌握理论知识的同时,加强上机实践。
本课程设计的目的就是要达到理论与实际应用相结合,使同学们能够根据数据对象的特性,学会数据组织的方法,能把现实世界中的实际问题在计算机内部表示出来,并培养基本的、良好的程序设计技能。
二、设计要求1.通过这次设计,要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。
同时,在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
2.学生必须仔细研读《数据结构》课程设计要求,以学生自学为主、指导教师指导为辅,认真、独立地完成课程设计的任务,有问题及时主动与指导教师沟通。
3.本次课程设计按照教学要求需要在一周时间内独立完成,学生要发挥自主学习的能力,充分利用时间,安排好课程设计的时间计划,并在课程设计过程中不断检测自己的计划完成情况,及时地向指导教师汇报。
4.编程语言任选。
三、设计选题选题说明:前面6个为基础题(必选一题,可达60分),后面题目*越多难度越大,根据实际选做题目的难度和数量以及实现程序的完善性可以适当加减分;同学们在选题时,要结合个人实际情况,确保及格,力争多做。
1.集合的并、交和差运算任务:编制一个能演示执行集合的并、交和差运算的程序。
要求:(1) 集合的元素限定为小写字母字符[‘a’..’z’] 。
(2) 演示程序以用户和计算机的对话方式执行。
实现提示:以链表表示集合。
选作内容:(1) 集合的元素判定和子集判定运算。
(2) 求集合的补集。
(3) 集合的混合运算表达式求值。
(4) 集合的元素类型推广到其他类型,甚至任意类型。
2.停车场管理任务:设停车场是一个可以停放n辆汽车的狭长通道,且只有一个大门可供汽车进出。
汽车在停车场内按车辆到达时间的先后顺序,依次有北向南排列(大门在最南端,最先到达的第一车停放在车场的最北端),若车场内已停满n辆车,那么后来的车只能在门外的便道上等候,一旦有车开走,则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时,在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其他车辆再按原次序进入车场,每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。
1006402《数据结构》课程设计任务书一、设计目的1.了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力;2.初步掌握软件开发过程的问题分析、系统设计、程序编码测试等基本方法和技能;3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力;4.训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的科学的工作方法和作风。
《数据结构》是一门实践性较强的软件基础课程,为了学好这门课程,必须在掌握理论知识的同时,加强上机实践。
本课程设计的目的就是要达到理论与实际应用相结合,使同学们能够根据数据对象的特性,学会数据组织的方法,能把现实世界中的实际问题在计算机内部表示出来,并培养基本的、良好的程序设计技能。
二、设计地点湖南城市学院实验楼计算机房407三、设计时间2012年6月4日——6月8日四、设计分组(54人)五、指导教师:陈强莫照六、设计课题:1.表达式翻译要求:编写完整程序,将不包含括号的算术中缀表达式翻译成后缀表达式.输入:中缀表达式,80个字符以内.输出:转换后的后缀表达式.要求:界面友好,函数功能要划分好2.超市选址问题设计要求:对于某一学校超市,其他各单位到其的距离不同,同时各单位人员去超市的频度也不同。
请为超市选址,要求实现总体最优。
3.串的查找和替换输入或打开一篇英文文章,在该文章中找出所有给定的单词,然后对所有给定的单词替换为另外一个单词。
4.地图着色问题设计要求:已知中国地图,对各省进行着色,要求相邻省所使用的颜色不同,并保证使用的颜色总数最少。
5.二叉排序树的实现用顺序和二叉链表作存储结构1)以回车('\n')为输入结束标志,输入数列L,生成一棵二叉排序树T;2)对二叉排序树T作中序遍历,输出结果;3)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则输出信息“无x”;6.二叉树的遍历问题二叉树的中序、前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现,应包含建树的实现。