计算机科学与工程学院计算机2006级6班《数据结构》课程设计任务书课程设计周数：4周指导老师：张顺香一、课程设计的目的《数据结构》主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。二、课程设计的基本要求1.问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？2.逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图；3.详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；4.程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；5.程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；三、课程设计内容（四者选其一）（1）数据结构排序算法演示系统功能要求：界面友好，易与操作。可采用菜单或其它人机对话方式进行选择。实现各种内部排序。包括直接插入排序，冒泡排序，直接选择排序，希尔排序，快速排序，堆排序，归并排序。待排序的元素的关键字为整数或（字符）。可用随机数据和用户输入数据作测试比较。比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换以3次计)。演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标值的列表，以便比较各种排序的优劣。（2）二叉树遍历算法集成功能要求：界面友好，易与操作。可采用菜单或其它人机对话方式进行选择。实现各种二叉树的遍历。包括先序遍历、中序遍历、后序遍历的递归和非递归算法。演示程序以人机对话的形式进行。每次测试完毕正确显示各种遍历序列。在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；（3）电梯模拟系统功能要求：界面友好，易与操作。可采用菜单或其它人机对话方式进行选择。实现电梯的正常运行。利用队列、定时器等知识加以实现。演示程序以人机对话的形式进行。每次测试完毕正确显示电梯上行、下行停靠楼层序列。(4)异质链表的实现功能要求：（1）类层次设计要求：采用面向对象的方法设计，构建一个基类和若干个派生类。（提示：需应用到虚函数、静态指针以及友元类等）（2）构建异质链表，链表中的节点为各种类型的派生类对象。（3）链表中的节点数据由指定文件读取，经过处理后村入指定文件。（4）异质链表应具有对节点的插入、删除及修改等基本功能。注：最好在可视化界面中实现。四、其它选做内容1、一元多项式计算任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入；在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；2、订票系统任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，