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