12数据结构课程设计

数据结构课程设计任务书使用班级：091113-16,17-20使用时间：2010-2011学年第2学期一、课程设计目的本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。二、课程设计题目共10题，每个学生一题，单独完成。（选法为根据学生所在班级名册的自然顺序，第1-10名同学分别做第1到第10题，然后循环，第11-20名同学分别做第1到第10题，依次类推。）1、运动会分数统计系统任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前前三名积分；前三名的积分分别为：5、3、2。（m、w=20,n=10）功能要求：1).可以输入各个学校、各项目、以及各项目前三名的数据信息；2)．能统计各学校总分、男子项目和女子项目总分；3)．可以按学校编号（或学校名称）、学校总分、男女团体总分排序输出；4).可以按学校编号（或学校名称）查询学校某个项目的情况；可以按项目编号查询取得前三的学校。规定：输入数据形式和范围：10以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计。请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；2、航班订票系统任务：通过此系统可以实现如下功能：1）、录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）2）、查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；3）、订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；4）、退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。5）、修改航班信息：当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计。请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；3、迷宫问题非递归求解任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；4、文本编辑和串查找统计任务：输入一页文字，程序可以统计出文字、数字、空格和其它标点符号的个数。静态存储一页文章，每行最多不超过80个字符，共N行；功能要求：1）、分别统计出其中英文字母数、空格数、标点符号及整篇文章总字数；2）、统计某一字符串在文章中出现的次数，并输出该次数；3）、删除某一子串，并将后面的字符前移。要求用菜单选择操作，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分5行输出全部字母数、数字个数、空格个数、“标点符号个数”文章总字数（3）输出删除某一字符串后的文章；5、各种内部排序性能比较任务：用程序实现插入法排序、起泡法、选择法、快速法、合并法排序；输入的数据形式为任何一个正整数，大小不限。输出的形式：数字大小逐个递增的数列。功能要求：给出多组不同元素个数的输入数据(可考虑用随机函数生成整数，而不用人工输入)，并用列表打印出每种排序下的各趟排序结果。每个排序法结束时应打印出其元素比较的次数和交换的次数。此程序需将结果用列表打印，一定要将其打印结果排列好。6、校园导航问题任务：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。7、题目：哈夫曼树和编码应用任务和功能：（1）从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树的存储结构；（2）利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对给定的n个字符正文进行编码，并输出每个字符的编码。（3）利用已建好的哈夫曼树，对给定的一个哈夫曼编码进行译码，判断此编码对应的字符序列，并输出结果。8、题目：散列表的设计与实现【问题描述】设计散列表实现电话号码查找系统。【基本要求】1)设每个记录有下列数据项：电话号码、用户名、地址；2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3)采用一定的方法解决冲突；4)查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。【进一步完成内容】1)系统功能的完善；2)设计不同的散列函数，比较冲突率；3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。9、利用栈求表达式的值，可供小学生作业，并能给出分数要求：建立试题库文件，随机产生n个题目；题目涉及加减乘除，带括弧的混合运算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价10、学校超市选址问题（带权有向图的中心点）设计要求：对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。三、课程设计要求：1、每人一题，且需独立完成。2、每人的设计程序必须为可执行的exe文件，且需指导教师验收合格。学生程序必须在课程设计的最后一天交由指导教师验收合格。过期不再验收程序，如程序验收不合格或在规定时间内未经指导教师验收，则视为该生程序没有完成。3、每人必须在规定时间内到机房做程序，指导老师将严格考勤，上机期间严禁做与课程设计无关的事情。指导教师将随时抽查。4、每人必须撰写课程设计报告并上交纸质稿（格式附后）。并上交报告电子稿和程序代码电子稿（每位同学先建立一个文件夹，取名规则为“学号姓名”，文件夹里存放上交电子内容，分别是“学号姓名报告”和“学号姓名程序”，每班取一文件夹名，取名规则为班级号，内放该班同学上交内容，每班学习委员统一收齐后拷贝给指导老师。特别注意，上交的程序必须是在相应的编程环境下存在的文件，不能是*.txt或*.doc文件等。四、课程设计评分标准：1．程序设计质量（占40%）2．课程设计报告质量（占40%）3．平时表现（占20%）五、上机时间安排表课程设计的时间及教师安排专业班级周次机房安排上机时间指导老师软件工程091113-6第17周201/204/208周一、周三5-8节周二、周四1-4节邹国华/许志文/汪雪元软件工程091117-20第18周201/204/208周一、周五5-8节周二、周四1-4节邹国华/许志文/汪雪元附：课程设计报告格式。1.需求分析说明（说明为何做该题目，程序最终需要完成的功能，从其需求上说明。）2.总体设计（从总体上说明该题目的框架，用文字和图表说明）3.详细设计（对数据结构进行详细的描述，设计好相应数据结构以及其操作功能，要求用C++设计成类；用文字详细描述每个功能实现的算法及思路。）4.实现部分（主要描述程序调试过程，报告中只要贴入核心代码）5.程序测试（给出各测试数据及其对应的测试结果，和程序运行图贴于此处。并能对程序运行结果分析之，且需提出改进算法。）6.总结7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.数据结构与算法设计课程设计报告题目：学生姓名：学号：班级：指导教师：2011年月日东华理工大学软件学院软件工程系