数据结构大作业级

1、提交时间：2012年6月3日前提交方式：各班同学在提交时间之前将压缩文件分别提交给本 班的学习委员，学委按班级名称建立文件夹，然后统一刻盘（两 个班可以刻到一张光盘上），交给助教老师，联系方式（qq： 0） 提交内容：源程序、文档提交方式每个人独立完成一个选题，每个人所有的文件放到一 个文件夹中，压缩成.rar文件，文件名为：姓名学 号班级文档要求：1. 对问题的分析、所选用的数据结构及理由、所选方法的优点及问题。2. 程序模块的构成及功能、特殊技巧的说明。3. 程序运行结果及结果分析。4. 交互式程序需说明使用方法；输入的参数个数、类型及实例。代码要求：统一用C卄语言编写，尽量不要调用C+语

2、言提供的 库函数（如栈、队列），也不允许用数据库软件来实现。说明：数据结构课程设计（大作业）”是与“数据结构”课程配套的实践性课程。 其目的是让学生运用所学的“数据结构”课程知识，编写一个解决实际问题的大 型或中等规模的计算机程序，使学生掌握综合运用数据结构与算法的知识和方 法。这里选择4个题目列出，具体作业只要求选择一个完成，基本要求必作，扩 展要求和增强要求为选作。数据结构大作业跟数据结构课程是分开的，具有独立 的1个学分，请同学们按时提交，不要延迟时间，否则影响该独立 学分的成绩。（一）、图书信息管理系统1. 问题阐述：某校图书馆需要一套图书信息管理系统，图书管理员用此系统记录和处理图

3、书、作者和出版社信息。（注：一本图书可以有多个作者，一个作者可以编写多 本图书）。需存储的信息包括：图书号、图书名；作者号、作者姓名；出版社号、 出版社名；现存量和总库存量。2. 基本要求基本业务活动包括：1）对一本书进行采编入库、清除库存、借阅、和归还等。1. 采编入库：新购入一种书，经分类和确定书号之后登记到图书帐目中去。如果 这种书在帐中已有，则只将总库存量增加。ii. 清除库存：某种书已无保留价值，将它从图书帐目中注销。iii. 借阅：如果一种书的现存量大于零，则借出一本，登记借阅者的图书证号 和归还期限，改变该书的现存量。iv. 归还：注销对借阅者的登记，改变该书的现存量。2）查询图

4、书信息：i. 按书名查询：如查找所有书名为“数据结构”的图书。ii. 按作者姓名查询：如查找所有张三”编写的图书。iii. 按出版社名查询：如查找所有机械工业出版社”出版的图书。iv. 以上条件的各种组合查询：如查找所有张三”编写的、由“机械工业出版社”出版的图书。（二）停车场管理系统1. 问题描述设停车场内只有一个可以停放n俩汽车的狭长通道，且只有一个大门可供 汽车进出。汽车在停车场內按车辆到达时间的先后顺序，依次由北向南排列（大 门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆 车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第 一辆车即可开入。当

5、停车场内某辆车要离开时，在它之后进入的车辆必须退出车 场为它让路，待该车辆开出大门外，其他车辆再按原次序进入车场，每辆停放在 车场的车在它离开停车场时必须按它停留的时间长短交纳费用。整个停车场的示 意图如下图所示。要求设计一个程序，为停车场编制按上述要求进行管理的程序。2. 基本要求1）以栈模拟停车场，以队列模拟车场外便道，按照从终端读入的输入数据 序列进行模拟管理。2）每一组输入数据包括三个数据项：汽车到达”（用1表示）或“离开” （用2表示）的信息、汽车牌照号码以及到达或离去的时刻。3）对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽 车在停车场内或便道上的停车位置；若是车辆

6、离去，则输出汽车在停车场内停留 的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队 列以顺序循环结构实现。4）另外还需要设一个临时栈，用于临时存放为要给离去的汽车让路而从停 车场退出来的汽车，也用顺序结构实现。5）用户输入的命令有以下5种：a. 汽车到达b. 汽车离去c. 输出停车场中所有汽车牌号d. 输岀便道上所有汽车牌号e.退出系统运行。（三）家谱管理系统设计与实现1. 问题阐述：家谱用于记录某家族历代家族成员的情况与关系。本课程设计要求设计并实 现一个计算机软件，支持对家谱的存储、更新、查询、统计等操作。2. 基本要求内部要求：要求将家谱信息看作树形结构处理，并可存储

7、在外存。数据可一次读 入内存；外部要求：这一级要求系统具备下列基本功能：1）家庭成员信息存储：将每个家庭成员的基本信息存储在计算机中（可永 久保存）。家庭成员的基本信息至少应包括：（姓名，出生地，出生日期，死亡日期，性别，身高，学历，职业，最髙职 务/职称，）；2）家族关系存储：将各家庭成员之间的关系，存储在计算机中（可永久保 存）；3）更新：家谱数据的更新（修改、删除、加入）；D）输出：将家谱以较友 好的格式输出（显示）；4）查询：按基本信息查询成员，按亲戚关系查询；3. 增强要求A）统计：统计并打印（显示）结果，统计的项目有：平均寿命、平均身高、 男女比例、家庭平均人口、平均（最高/低）学

8、历、4. 扩展要求内部要求：数据较大时，不一次读入内存，采用分块读入；外部要求：这一级要求系统具备下列基本功能：屏幕显示树形（类似Windows目 录）、全屏可视化操作、支持鼠标；5. 设计提示家庭成员基本信息用线性表表示，程序结束后存储在磁盘上，程序开始是从 磁盘读出；家庭成员之间的关系，用树形结构（家族树）表示；家族树在程序结束后存储在磁盘上，程序开始是从磁盘读出；树在内存中的存储结构：邻接表或孩子兄弟链，带父指示器；家庭成员基本信息设置数字编号，用于唯一地标识记录；树结点用家庭成员的编号标识。通过编号，建立家庭成员的基本信息与树结 点的联系；树在磁盘文件中的存储结构：存储串行化结果，如根

9、-叶序列”；所谓根-叶序列”，是指，从树根到每个叶子结点的路径。路径的排列次序 表示兄弟的次序。例如，下图表示的树的“根-叶序列”为：1, 2, 41, 2, 61, 2, 8, 5 （这三行的次序，表示4,6,8的次序，即4,6,8分别是2的第1,2,3个孩子）1, 71, 3, 91, 3, 10（四）航空客运订票系统1. 问题描述航空客运订票的业务活动包括：查询航线、客票预订和办理退票等。试设计 一个航空客运订票系统，以使上述业务可以借助计算机来完成。2. 基本要求1）.每条航线所涉及的信息有：终点站名、航班号、飞机号、飞行日（星期几）、乘员定额、余票量、已订票的客户名单（包括姓名、订票量、舱位 等级1, 2或3）以及等候替补的客户名单（包括姓名、所需票量）；2）.全部数据可以只放在内存中；3）.系统能实现的操作和功能如下：a）查询航线：根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行,最近一天航班的日期和余票额;b）承办订票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若尚 有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于定票 额，则需重新询问客户要求。若需要，可登记