数据结构大作业(2010级)

数据构造大作业提交时间:2012年6月3日前提交方式:各班同学在提交时间以前将压缩文件分别提交给本班的学习委员，学委按班级名称成立文件夹，而后一致刻盘（两个班能够刻到一张光盘上），交给助教老师，联系方式(qq:0)提交内容:源程序、文档提交方式：每一个人独立达成一个选题，每一个人所有的文件放到一个文件夹中，压缩成.rar文件，文件名为:姓名_学号_班级文档要求：1．对问题的剖析、所采纳的数据构造及原因、所选方法的长处及问题。2．程序模块的组成及功能、特别技巧的说明。3．程序运转结果及结果剖析。4．交互式程序需说明使用方法；输入的参数个数、种类及实例。代码要求：一致用C++语言编写，尽量不要调用C++语言供给的库函数（如栈、行列），也不同意用数据库软件来实现。说明：“数据构造课程设计（大作业）”是与“数据构造”课程配套的实践性课程。其目的是让学生运用所学的“数据构造”课程知识，编写一个解决实质问题的大型或中等规模的计算机程序，使学生掌握综合运用数据构造与算法的知识和方法。这里选择4个题目列出，详细作业只需求选择一个达成，基本要求必作，扩展要乞降加强要求为选作。数据构造大作业跟数据构造课程是分开的，拥有独立的1个学分，请同学们准时提交，不要延缓时间，不然影响该独立学分的成绩。（一）、图书信息管理系统1．问题论述：某校图书室需要一套图书信息管理系统，图书管理员用此系统记录和办理图书、作者和第一版社信息。（注：一本图书能够有多个作者，一个作者能够编写多本图书）。需储存的信息包含：图书号、图书名；作者号、作者姓名；第一版社号、第一版社名；现存量和总库存量。2．基本要求基本业务活动包含：对一本书进行采编入库、消除库存、借阅、和送还等。采编入库：新购入一种书，经分类和确立书号以后登记到图书帐目中去。假如这类书在帐中已有，则只将总库存量增添。消除库存：某种书已无保存价值，将它从图书帐目中注销。借阅：假如一种书的现存量大于零，则借出一本，登记借阅者的图书证号和送还限期，改变该书的现存量。送还：注销对借阅者的登记，改变该书的现存量。查问图书信息：按书名查问：如查找所有书名为“数据构造”的图书。按作者姓名查问：如查找所有“张三”编写的图书。按第一版社名查问：如查找所有“机械工业第一版社”第一版的图书。以上条件的各样组合查问：如查找所有“张三”编写的、由“机械工业第一版社”第一版的图书。（二）泊车场管理系统1．问题描绘设泊车场内只有一个能够停放n俩汽车的狭长通道，且只有一个大门可供汽车出入。汽车在泊车场内按车辆抵达时间的先后次序，挨次由北向南摆列（大门在最南端，最初抵达的第一辆车停放在车场的最北端），若车场内已停满n辆车，则以后的汽车只好在门外的便道上等待，一旦有车开走，则排在便道上的第一辆车即可开入。当泊车场内某辆车要走开时，在它以后进入的车辆一定退出车场为它让路，待该车辆开出大门外，其余车辆再按原序次进入车场，每辆停放在车场的车在它走开泊车场时一定按它逗留的时间长短缴纳花费。整个泊车场的示企图以以下图所示。要求设计一个程序，为泊车场编制按上述要求进行管理的程序。进出北候车场泊车场南2.基本要求以栈模拟泊车场，以行列模拟车场外便道，依据从终端读入的输入数据序列进行模拟管理。每一组输入数据包含三个数据项：汽车“抵达”（用1表示）或“走开”（用2表示）的信息、汽车牌照号码以及抵达或离开的时刻。对每一组输入数据进行操作后的输出信息为：假如车辆抵达，则输出汽车在泊车场内或便道上的泊车地点；假如车辆离开，则输出汽车在泊车场内逗留的时间和应缴纳的花费（在便道上逗留的时间不收费）。栈以次序构造实现，行列以次序循环构造实现。此外还需要设一个暂时栈，用于暂时寄存为要给离开的汽车让路而从泊车场退出来的汽车，也用次序构造实现。用户输入的命令有以下5种：汽车抵达汽车离开输出泊车场中所有汽车牌号输出便道上所有汽车牌号退出系统运转。（三）家谱管理系统设计与实现1．问题论述：家谱用于记录某家族历代家族成员的状况与关系。本课程设计要求设计并实现一个计算机软件，支持对家谱的储存、更新、查问、统计等操作。2．基本要求内部要求：要求将家谱信息看作树形构造办理，并可储存在外存。数据可一次读入内存；外面要求：这一级要求系统具备以下基本功能：1）家庭成员信息储存：将每个家庭成员的基本信息储存在计算机中（可永久保存）。家庭成员的基本信息起码应包含：（姓名，出生地，出诞辰期，死亡日期，性别，身高，学历，职业，最高职务/职称，）；2）家族关系储存：将各家庭成员之间的关系，储存在计算机中（可永远保存）；3）更新：家谱数据的更新（改正、删除、加入）；D）输出：将家谱以较友善的格式输出（显示）；4）查问：按基本信息查问成员，按亲戚关系查问；3．加强要求A)统计：统计并打印（显示）结果，统计的项目有：均匀寿命、均匀身高、男女比率、家庭均匀人口、均匀（最高/低）学历、4．扩展要求内部要求：数据较大时，不一次读入内存，采纳分块读入；外面要求：这一级要求系统具备以下基本功能：屏幕显示树形（近似Windows目录）、全屏可视化操作、支持鼠标；5．设计提示家庭成员基本信息用线性表表示，程序结束后储存在磁盘上，程序开始是从磁盘读出；家庭成员之间的关系，用树形构造（家族树）表示；家族树在程序结束后储存在磁盘上，程序开始是从磁盘读出；树在内存中的储存构造：毗邻表或孩子兄弟链，带父指示器；家庭成员基本信息设置数字编号，用于独一地表记记录；树结点用家庭成员的编号表记。经过编号，成立家庭成员的基本信息与树结点的联系；树在磁盘文件中的储存构造：储存串行化结果，如“根-叶序列”；所谓“根-叶序列”，是指，从树根到每个叶子结点的路径。路径的摆列序次表示兄弟的序次。比如，以下图表示的树的“根-叶序列”为2,451,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)．系统能实现的操作和功能以下：查问航线：依据游客提出的终点站名输出以下信息：航班号、飞机号、礼拜几飞翔，近来一天航班的日期和余票额；包办订票业务：依据客户提出的要求（航班号、订票数额）查问该航班票额状况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于定票额，则需从头咨询客户要求。若需要，可登