数据结构课程设计指导书.doc

数据结构课程设计 指导书 2014.9 一、实验目的 通过训练，实现以下三方面目标： 1．使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。 2．使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。 3．使学生初步掌握查阅参考资料的方法，提高学生进行程序设计等综合的应用能力。 二、涉及的基本理论 数据结构中关于“线性表、栈和队列、树和二叉树、图、查找和排序”等基本理论。 三、基本要求 1．巩固和加深对数据结构基本知识的理解，提高综合运用课程知识的能力。 2．培养学生自学参考书籍，查阅手册、图表和文献资料的能力。 3．通过训练，使学生初步掌握简单软件的分析方法和设计方法。 4．了解与课程有关的工程技术规范，能正确解释和分析实验结果。 5．题目具有足够的工作量。 6. 课程中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。 7. 做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。 8.趣味题除外， 按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成； 其中包括： 　　a）需求分析： 　　在该部分中叙述，每个模块的功能要求 　　b）概要设计 　　在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。 　　c）详细设计 　　各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现） 　　源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。 　　d）调试分析 测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。 课程设计总结：（保存在word文档中）总结可以包括：课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容； 9. 每组实现的结果必须进行检查和演示；程序源代码和程序的说明文件必须上交，作为考核内容的一部分；（上交时每人交一份，文件夹的取名规则为：“学号 姓名”，如“200413498 高魁”。该文件夹下至少包括：“源代码”、“课程设计报告”、“可执行文件”。由学习委员收集刻盘按规定时间统一上交）。 10. 课程设计报告可以附原代码，也可以只对对重点函数及结构进行说明。报告格式参照数据结构习题集或下面设计报告样例。 11. 报告提交（要求见大纲）。 四、训练内容：（每人完成3类题目中的各一道题即可）--详见大纲 三类题目： 第一类：趣味问题（如汉诺塔、约瑟夫环、八皇后问题、串的模式匹配等问题）； 第二类如下： 1．内部排序演示 【问题描述】 设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数。 【基本要求】 (1) 对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较；（可以选3种） (2) 待排序的元素的关键字为整数。其中的数据要用伪随机产生程序产生(如10000个)，至少用5组不同的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较。 (3) 演示程序以人机对话的形式进行。 (4) 界面友好，易与操作。采用菜单方式进行选择。 2．校园导游咨询 【问题描述】 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 【基本要求】 (1) 设计本校的校园平面图，所含景点不少于6个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 (2) 为来访客人提供图中任意景点相关信息的查询。 (3) 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。可以拓展。 3．建通讯录 【问题描述】 设计散列表实现通讯录查找系统。 【基本要求】 (1) 设每个记录有下列数据项：电话号码、用户名、地址； (2) 从键盘输入各记录，分别以电话号码为关键字建立散列表； (3) 采用线性探测再散列法解决冲突； (4) 查找并显示给定电话号码的记录； (5) 通讯录信息文件保存； (6) 要求人机界面友好，使用菜单方式进行选择。 【实现提示】 主函数：根据选单的选项调用各函数，并完成相应的功能。 Menu()的功能：显示英文提示选单。 Quit()的功能：退出选单。 Create()的功能：创建新的通讯录。 Ap