数据结构大型实验任务书使用班级：软件工程、计算机、网络工程、数字媒体
[大型实验基本要求]
1） 原则上可以２－３位同学组成实验小组，进行分工合作，但必需保证每位组员都充分
参与实验过程，每位组员应对实验程序的结构、算法、主要技术完全掌握，方可参加实验
验收，在验收时可指定某位组员回答问题，若没回答正确，则会影响整组成绩。
2） 每组可参考下面大型实验题目和要求，确定一道实验题目，共同设计开发。
3）大型实验时间从第8周开始至16周，要求在考试之前全部验收结束。原则上，申请大
型实验验收后，若实验没有达到规定的要求，不可再次申请验收，故请大家务必确认程序
正确（程序代码和运行结果）后，再申请验收。
[报告规范] 实习报告的开头应该给出题目、班级、姓名、学号、和完成日期，并包括以
下五个内容：
1． 实验内容分析：
明确实验题目目的，设计实验的基本数据结构、类、以及程序的基本流程，程序流程要求以程序流程图明确表示，类及类间关系需明确图示，并给出各函数之间的调用关系。
2．实验验证分析：
（1）输入的形式和输入值的范围；
（2）输出的形式；
（3）程序所能达到的功能；
（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。
３．调试分析
（1）讨论分析调试过程中的主要技术问题以及具体的解决方法（至少３个）；
（2）技术难点分析（至少３个）；
（3）印象最深刻的３个调试错误，及修正方法；
４．测试结果：
（1）展示程序的运行结果，包括输入和输出，分析数据的正确性；
（2）应用边界数据、或极端数据测试系统，分析结果的正确性。
５．提交的源代码需带注释，可提交电子版本。
[题目]
一、离散事件模拟
①银行业务模拟
【问题描述】客户业务分为两种，第一种是申请从银行得到一笔资金，即取款或者借款。第
二种是向银行投入一笔资金，即存款或者还款。银行有两个服务窗口，相应的有两个队列。
客户到达银行后先排第一个队。处理每个客户业务时，如果属于第一种，且申请额超出银行
现存资金总额而得不到满足，则立即排入第二个队等候，直至满足时才离开银行；否则业务
处理完后立即离开银行。每接待完一个第二种业务的客户，则顺序检查和处理（如果可能）
第二个队列中的客户，对能满足的申请者予以满足，不能满足的者重新排到第二个队列的队
尾。
注意：在此检查过程中，一旦银行的资金总额少于或者等于刚才第一个队列中最后一个客户
（第二种业务）被接待之前的数额，或者本次已将第二个队列检查或处理了一遍，就停止检
查（因为此时已不可能还有能满足者）转而继续接待第一个队列客户。任何时刻都只开一个
窗口。假设检查不需要时间。营业时间结束时所有客户立即离开银行。
【基本要求】利用动态存储结构实现模拟。
【测试数据】一天营业开始时银行拥有的款额为10000（元），营业时间为600（分钟）。其
他模拟参量自定，注意测定两种极端的情况：一是两个到达事件之间的间隔时间很短，而客
户的交易时间很长，另一个恰好相反，设置两个到达事件的间隔时间很长，而客户的交易时
间很短。
【实现提示】事件有两类：到达银行的和离开银行。初始时银行现存资金总额为total。开始
营业后的第一个事件是客户到达，营业时间从0到closetime。到达事件发生时随机地设置
此客户的交易时间和距下一到达事件之间的时间间隔。每一个客户要办理的款额也是随机确
定的，用负值和正值分别表示第一类和第二类业务。变量total，closetime以及上述两个随
机量的上下界均交互地从终端读入，作为模拟参数。
两个队列和一个事件表均要用动态存储结构实现。需考虑设置离开事件，以及如何设
计第二个队列的存储结构以获得较高的效率。注意：事件表是按时间顺序有序的。
②航空客运订票系统
【问题描述】航空客运订票的业务活动包括：查询航线、客票预订和办理退票等。试设计一
个航空客运订票系统，以使上述业务可以借助计算机来完成。
【基本要求】（1）每条航线所涉及的信息有：终点站名、航班号、飞机号、飞行周日（星期
几）、乘员定额、余票量、已订票的客户名单（包括姓名、订票量、舱位等级1，2或3）以
及等候替补的客户名单（包括姓名、所需的票量）；
（2）全部数据应保存在外部文件中，可方便读取、更新；
（3）系统能实现的操作和功能如下：a-查询航线：根据旅客提出的终点站名输
出下列信息：航班号、飞机号、星期几飞行、最近一天航班的日期和余票；b-承办订票业务：
根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若尚有余票，则为客户办
理订票手续，输出座位号；若已满员或余票额少于订票额，则需重新询问客户要求。若需要，
可登记排队候补；c-承办退票业务：根据客户提供的情况（日期、航班），为客户办理退票
手续，后人内查询该航班时候有人排队候补，首先询问排在第一的客户，若所退票额能满足
他的要求，则为他办理订票手续，否则依次询问其他排队候补的客户。当客户订票要求不能
满足时，系统可向客户提供到达同一目的地的其他航线的情况，需适当增加系统的功能。
【测试数据】自行拟定。
【实现提示】两个客户名单可分别由线性表和队列实现。为查找方便，已订票客户的线性表
应按客户的身份证号码排序，并且，为插入和删除方便，应以链表作存储结构。由于预约人
数无法预计，队列也应以链表作存储结构。整个系统需汇总各条航线的情况登录在一张线性
表上，由于航线基本不变，可采用顺序存储结构，并按航班有序或按终点站名有序。每条航
线是这张表上的一个记录，包含上述8个域，其中乘员名单域为指向乘员名单链表的头指针，
等候替补的客户名单域为分别指向队头和队尾的指针。
③机场航空管制模拟
【问题描述】假设机场有一条跑道，每架飞机需花费一定时间着陆，花费一定时间起飞，飞
机的起降满足一定的概率。一般来讲，机场存在两个队列，一个等待着陆的飞机队列和一个
等待起飞的飞机队列，同样等待时间下，等待着陆的飞机比准备起飞的飞机具有更高的优先
级。试编写程序模拟这个机场的运行。
【基本要求】使用队列和优先队列实现；要求可以变换起飞和着陆频率来模拟一天中的飞行
高峰期和空闲期；要求可以改变着陆和起飞时间以模拟不同的效果。
【实现提示】可以假设有一个每次前景一分钟的模拟时钟，对于每一分钟，产生两个随机数：
如果第一个随机数小于landingRate/60，那么一个“着陆到达”将发生并被添加到着陆队列
中；如果第二个随机数小于takeOffRate/60，那么一个“起飞到达”将发生并被添加到起飞
队列中。接着，检查跑道是否空闲。若空闲，首先检查着陆队列是否为非空，如果是，允许
第一架飞机着陆；否则，处理起飞队列。使程序能够计算平均队列长度及每架飞机花费在一
个队列中的平均时间。
*
二、图书管理系统
【问题描述】建立一个图书管理系统，所有图书信息需保存在外部文件中。要求能够实现基
本的图书信息数据检索，插入，删除，更新和排序等功能。要求系统具有良好的交互界面，
图书检索功能可以提供多种方式检索：书名检索，作者名检索，出版社检索，ＩＳＢＮ信息
检索，已经组合检索，如作者名＋出版社。图书信息包括：作者、书名、出版社、出版时间、
ＩＳＢＮ、库存数量、已借出数量；学生可查阅自己的借阅情况，每个学生限制借阅５本图
书；学生可通过选择具体的图书实现还书功能。
【基本要求】实现图书信息管理和学生借阅管理
【实现提示】（１）可选择非线性结构二叉搜索树（Binary Search Tree）实现
（２）可选择非线性结构AVL树实现
（３）可选择哈希表（散列）Hashtable实现
* 注：本题目难度较大，完成实验的同学成绩会有一定的加分。
