《数据结构》课程大作业题目列表
《数据结构》课程大作业要求：
每3~4名同学一组，每组任选作业题目中的一题，组内同学一起进行分析，每个人负责题目中的一个模块进行设计和实现。最后一次上机时，在上机实验室现场，每组分别演示自己的程序，每个同学讲解自己设计的部分，由老师打分。该分数与平时作业和平时上机一起计算进总成绩中。
1. 航空客运订票系统 ................................................................................................................... 2 2. 全国交通咨询模拟 ................................................................................................................... 4 3. 五子棋的设计与实现 ............................................................................................................... 6 4. 学生成绩管理系统 ................................................................................................................... 7 5. 城市导游咨询 ........................................................................................................................... 9 6. 图书管理系统 ......................................................................................................................... 11 7. 简单文本编辑器 ..................................................................................................................... 14 8. 排课软件 ................................................................................................................................. 15
1. 航空客运订票系统
1.1. 问题描述
航空客运订票的业务活动包括：查询航线、客票预定和办理退票等。
每条航线所涉及的信息有：起点站名、终点站名、航班号、起降时间、飞机号、飞行周日（星期几）、票价、票价折扣、乘员定额、余票量、已订票的客户名单（包括姓名、证件类型、证件号码、订票数量、航班情况、舱位等级1，2或3，订单要有编号）以及等候替补的客户名单（包括姓名、所需票量）。
1.2. 功能描述
1. 录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具
体数据自定）
2. 对飞机航班信息进行排序和查询：可按航班的航班号、起点站、到达站、起
飞时间以及到达时间等信息查询某个航线的情况。（可以输入一个或多个信息进行查询。设计中，要求采用基数排序方法对一组具有结构特征的飞机航班号进行排序，利用二分查找的方法对排好序的航班记录按照航班号实现快速查找，而其他次关键字的查找则采用最简单的顺序查找方法进行。当然也可以使用其它的排序方法）
假设每个航班记录包括8项，分别是：航班号，起点站，到达战，班期，起飞时间，到达时间，飞机型号以及票价等，假设的航班信息表（8条记录）入下表所示：
航班信息表 航班号 CA1544 MU5341 CZ3869 MU3682 HU1836 CZ3528 MU4594 K0 C 起点站 合肥 上海 重庆 桂林 上海 成都 昆明 K1 Z 终点站 北京 广州 深圳 南京 北京 厦门 西安 K2 3 班期 1.2.4.5 每日 2.4.6 2.3.4.6.7 每日 1.3.4.5.7 1.3.5.6 起飞时间 到达时间 机型 1055 1420 0855 2050 0940 1510 1015 K3 8 1240 1615 1035 2215 1120 1650 1140 K4 6 733 M90 733 M90 738 CRJ 328 K5 9 票价 960 1280 1010 1380 1250 1060 1160 其中航班号的格式为： 其中k0和k1的输入值是航空公司的名称，用2个大写字母表示，后4位为航班编号，这种航班号关键字可未成2段，即字母和数字。其余7项输入内容因不涉及本设计的核心，因此除了票价为数值型外，均定义为字符型即可。
3. 订票：可以订票，如果该航班已经无票，可以提供相关可选择航班（订票情
况可以存在一个数据文件中，结构自己设定。相关可选择航班可包括进行中转的航班，比如输入西安－杭州，相关可选择航班包括西安－重庆－杭州） 4. 退票：可退票，退票后修改相关数据文件；（若有等候替补的客户名单，则
要及时通知这些客户并修改已订票客户名单）
5. 修改航班信息：当航班信息改变可以修改航班数据文件
6. 当客户不清楚航班的信息情况时，能通过输入起点站和终点站，输出费用最
小的航线。『若无直达航线，可输出中转航线。若有直达航线，但费用并不是最小，则同时输出费用最小的直达航线（在直达航线中费用最小的航线）和费用最小的中转航线（在所有的航线中费用最小的航线）』
1.3. 设计要求
1. 根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；
2. 对以上每一个功能，都要输出一个例子进行相关的说明； 3. 上述功能的完成涉及到线性表、队列，查找和图 4. 上述系统的设计不可过于小，适中即可。
5. 可以为程序增加简单的界面，但是不要过多注重界面，而忽略程序功能的实
现。
1.4. 设计报告格式及主要内容
(1)需求分析说明文档
(2)概要设计（系统的总体结构、功能模块之间接口） (3)详细设计（模块功能说明，主要数据结构的说明）
(4)测试计划与报告：调试方法，测试结果的分析与讨论，测试过程中遇到的主要问题及采取的解决措施。
(5)源程序清单和执行结果：源程序清单中每个类和方法都应有足够的注释。
2. 全国交通咨询模拟
2.1. 问题描述
出于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则期望旅费尽可能的少，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供最优决策的交通咨询。
2.2. 功能描述
（1）提供对城市信息进行编辑（如：添加功删除）的功能
（2）城市之间有目前种交通工具：火车和飞机。提供对列车时间表和飞机航班进行编辑（增设或删除）的功能。
（3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。 （4）旅途中耗费的总时间应该包括中转站的等候时间。
（5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时坐哪一趟列车哪一次班机到何地。
2.3. 设计要求
提供对全国城市交通图和列车时刻表及飞机航班表的编辑（键盘输入）。 学生可以上网查找相关的算法，但是严禁不加思考和修改，直接拷贝使用，最后的文档中必须包含对本程序使用的核心数据结构的评价（优缺点等），若有，应包含改进的地方。
2.4. 实现提示
（1）飞机航班表的信息包括：起始站台票出发时间、终点站的到达时间和票价；列车时刻表则根据交通图给出各个路段的详细信息。
（2）以邻接表作交通图的存储结构，表示边的结点内除了含有邻接点的信息外，还应包括交通工具、路程中消耗的时间和花费以及出发和到达的时间等多项属性。
2.5. 选作要求
对全国城市交通图和列车时刻表及飞机航班表的编辑，使用文件形式输入； 可以为旅客提供两种以上的最优决策选择；
可以为程序增加简单的界面，但是不要因为界面，而延误了程序基本的功能实现。
（参考数据结构题集（C语言版）P 153）
2.6. 设计报告格式及主要内容
(1)需求分析说明文档
(2)概要设计（系统的总体结构、功能模块之间接口） (3)详细设计（模块功能说明，主要数据结构的说明）
(4)测试计划与报告：调试方法，测试结果的分析与讨论，测试过程中遇到的主要问题及采取的解决措施。
(5)源程序清单和执行结果：源程序清单中每个类和方法都应有足够的注释。