一个星期的任务。。

《数据结构与算法》课程设计

一． 课程设计的目的

学习数据结构与算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题。课程设计要求同学独立完成一个较为完整的应用需求分析，在完成设计和编程大型作业的过程中，深化对数据结构与算法课程中基本概念、理论和方法的理解；训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念；使同学的程序设计与调试水平有一个明显的提高。

经过查找参考资料、技术手册和撰写文档的实践，进一步培养软件工程师的综合素质。

课程设计所安排的题目，在难度和深度方面都大于课内的上机训练。

二． 课程设计的技术要求

同学们在处理每一个题目的时候，要从分析题目的需求入手，按设计抽象数据类型、构思算法、通过类的设计实现抽象数据类型、编制上机程序代码并调试的步骤完成题目，最终写出完整的分析报告。见到题目，案头工作准备不足，忙于上机敲程序不是优秀程序员的工作风格。注意设计与实现过程的经验积累，编码应尽量利用前阶段的成熟数据结构包，加大代码的重用率。

本次课程设计的具体技术要求包括：

1． 每个题目均要求有图形界面版本。

2． 有自学能力的同学可以运用 “多线程”技术，多线程会使图形界面的动画效果更逼真。

3． 数据的输入输出应有手动键盘和文件读写两种工作方式。

4． 在课程设计过程中，要进行中期检查和最终版程序的测试，设计文档的撰写必须提前进行，以保证使文档与程序同步提交。

三． 课程设计的需求分析步骤与文档格式

课程设计必须强化面向对象的思想方法，其设计的过程与步骤，就是撰写文档的主要脉络。主要设计步骤应包括：

  分析问题归纳算法模型

  设计ADT

  类的细化设计与实现

  类的调试与总体算法程序调试

  算法分析

  收获体会

四． 验收标准

验收包括程序测试结果、类设计的合理性和文档质量三部分。程序测试分标准数据样本测试、随机输入数据测试、查看源代码和变更问题需求条件的随机数据测试（对疑似相同的代码和文档将单独严格测试考核）。

在程序正确性的前提下，要兼顾界面设计和代码可重用性的质量，注重面向对象设计理念的考核。

　上交的成果的内容必须由以下四个部分组成，缺一不可

　　1． 上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）；

2． 上交程序的说明文件：（保存在.txt中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明；

3． 课程设计报告：（保存在word 文档中，文件名要求 按照"姓名-学号-课程设计报告"起名，如文件名为"张三-001-课程设计报告".doc ）按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成；

其中包括:

a)需求分析
　　在该部分中叙述每个模块的功能要求
　　b)概要设计

在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）。

c）详细设计
　　即各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）。

源程序要规范编写：结构要清晰，注释要清楚。重点函数的重点变量和重点功能部分要加上清楚的程序注释。

d）调试分析
　　测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。

4. 课设总结： （保存在word 文档中）总结可以包括 : 课程设计 过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容。字数要求1500字及以上。

验收分两次进行：第一周的周六和周日，第二周的周六和周日。第一周验收通过的同学，成绩按照实际分数乘以1.2的系数后计算，第二周验收通过的同学，成绩按照实际分数计算。

课程设计过程中遇到问题需要协助时，请联系相应的指导老师。

五、课程设计题目

       四个系统任选其一。

<!--[if !supportLists]-->1.         <!--[endif]-->订票系统
任务：通过此系统可以实现如下功能：

录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）

查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；

可以输入起飞抵达城市，查询飞机航班情况；

订票：（订票情况可以存在一个数据文件中，结构自己设定）　可以订票，如果该航班已经无票，可以提供相关可选择航班；

退票： 可退票，退票后修改相关数据文件；

客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。

修改航班信息：　当航班信息改变可以修改航班数据文件
　　要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；

<!--[if !supportLists]-->2.         <!--[endif]-->迷宫游戏设计与实现
任务：设计一个小型游戏，该游戏主界面为含有10×10个小方块的正方形，游戏中含有红、橙、蓝、绿、紫、黄等六种颜色的棋子，每个小方块中可以放入一粒棋子。游戏规则为：系统每次随机的产生三粒棋子并随机放入棋盘中空的小方格中，如果棋盘小方格A中存在棋子，棋盘小方格B中为空，并且存在一条从A到B的路径，该路径所经过的所有小方格中都没有棋子，则A中棋子可以移到B中。当同一颜色的棋子有5颗或超过5颗紧邻并且在同一方向则可以消去，并且玩家得分（前面5颗棋子每消去一颗得2分，后面每消去一颗的得分是前面一颗得分的两倍，如消去5颗得10分，消去6颗得14分，消去7颗得22分…），游戏记录前10名的成绩。

界面要求：棋子在小方格A中移到B中要动态显示移动的全过程。

要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度；

3.  学生成绩管理系统

任务：建立一个简单的学生信息管理系统，该系统为注册学生保存基本信息、选课信息以及课程成绩。系统要方便基本信息、选课信息、成绩的增加、删除、修改及查询。为实现快速查询，要求对基本信息、选课信息和成绩建立相应的索引，学生成绩采用平衡二叉树建索引，对学生姓名采用Hash建立索引，对学号实现折半查找。

要求：

<!--[if !supportLists]-->1)        <!--[endif]-->可以按成绩高低输出所有成绩；

<!--[if !supportLists]-->2)        <!--[endif]-->可以按区间段查询成绩；

<!--[if !supportLists]-->3)        <!--[endif]-->可以按区间段统计成绩。

<!--[if !supportLists]-->4)        <!--[endif]-->可以按成绩、姓名、学号等信息查询。

<!--[if !supportLists]-->5)        <!--[endif]-->二叉树的各种操作要求写出递归和非递归两种方式。

 

4.   封锁管理子系统模拟实现

封锁管理子系统通过加锁来控制用户对系统资源的并发使用。用户使用系统资源前必须申请封锁，即给出申请封锁的对象资源号、封锁方式和用户名。其中资源号是取值为1~999 999的正整数，封锁方式为S（共享）或X（排他）。两种封锁方式的相容矩阵如图所示：

	S	X
S	OK	NO
X	NO	NO

相容矩阵

子系统受封锁请求，根据所保存的封锁状态信息决定请求是否能够获得封锁，进行相应处理，并向用户反馈处理结果。如果获得封锁，则赋给该请求一个批准号，可以使用该资源；否则需要进入等待队列（赋给该请求一个批准号）。

用户结束对某资源的使用后，应释放封锁（给出封锁对象的资源号和封锁批准号）。系统受理解锁请求时必须能迅速找到有关对象的封锁状况信息，以进行相应处理。为满足此要求，可采用散列表加链表的数据结构，如图所示：

封锁管理子系统示意图

其中散列表的元素对应为封锁对象，以对象的资源号为散列函数的自变量（即关键码值）。散列表中元素仅为一个指向封锁对象链表的指针。LO为封锁对象结点，对应于同一散列地址的封锁对象链接到一个链表中。LR为封锁请求结点。每个封锁对象结点带两个封锁请求队列：活动队列中为当前持有对该对象的封锁请求，等待队列中为正在等待对该对象进行封锁的封锁请求。LO结点和LR结点均向子系统自己管理的可利用空间表申请。

请设计并实现散列表、LO链表、LR活动队列、LR等待队列、可利用空间表的结构和基本运算。在此基础上使封锁管理子系统能提供以下功能：

<!--[if !supportLists]-->（1）       <!--[endif]-->受理用户从中断输入的封锁请求进行相应处理，并给出反馈信息；

<!--[if !supportLists]-->（2）       <!--[endif]-->受理用户从终端输入的解锁请求，进行相应处理；

<!--[if !supportLists]-->（3）       <!--[endif]-->显示封锁状况信息（用户从终端输入资源号名子系统显示该对象的LR活动队列和LR等待队列）。