15周数据结构课程设计任务书.doc

数据结构课程设计任务书1 课程设计的目的数据结构课程设计是信息与计算科学专业集中实践性环节之一，是学习完数据结构课程后进行的一次全面的综合练习。其目的是： （1）要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。 （2）在实践中认识为什么要学习数据结构，掌握数据结构、程序设计语言、程序设计技术之间的关系，是前面所学知识的综合和回顾。2 课程设计的基本要求（1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；（2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；（3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；（4）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。（5）设计的题目要求达到一定工作量，并具有一定的深度和难度。（6）编写课程设计说明书。3 课程设计内容及安排（1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ （2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图；（3）详细设计：定义相应的存储结构并写出各函数的伪代码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作进行进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；（4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；（5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；（6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；（7）撰写课程设计报告；4 课程设计报告的内容设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，排版及图、表要清楚、工整，内容及要求详见“课程设计报告规范”， 其中“课程设计报告内容”中一般应包括以下内容：4.1 需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：(1) 输入的形式和输入值的范围；(2) 输出的形式；(3) 程序所能达到的功能；(4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。4.2 概要设计说明本程序中用到的所有类的定义、主程序的流程以及各程序模块之间的层次（调用）关系。4.3 详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪代码算法；对主程序和其他模块也都需要写出伪代码算法（伪代码算法达到的详细程度建议为：按照伪代码算法可以在计算机键盘直接输入高级程序设计语言程序）)；可采用流程图、活动图进行描述，画出函数和过程的调用关系图。4.4 调试分析内容包括：调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；4.5 测试结果列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。4.6 用户手册说明如何使用你编写的程序，详细列出每一步的操作步骤。5 课程设计考核方法及成绩评定课程设计结束时，要求学生写出课程设计报告（可不附源程序），可运行的软件系统（包括源程序，在数字大学城提交电子版，同时提交纸质版）。学委在2012.12.31前按照实验的格式收齐电子版及打印的报告、交实验室肖老师处。课程设计成绩分4部分，（1） 设计报告35%；（2） 程序质量占30；（3） 集中上机考勤20；（4） 提问及团队合作15%6 进度安排演示软件和答辩另行安排7 课程设计题目以下题目供参考，最多三人一组，各班学委相互协调好不要重复。学生可以根据自己的实际，可以自己另行选择课程设计题目，选好题后必须经指导老师同意。7.1 集合的并、交和差运算【间题描述】 编制一个能演示执行集合的并、交和差运算的程序。【基本要求】 (1)集合的元素限定为小写字母字符a，z (2)演示程序以用户和计算机的对话方式执行。【测试数据】 【实现提示】 以有序链表表示集合。【选作内容】 (1)集合的元素判定和子集判定运算。 (2)求集合的补集。 (3)集合的混合运算表达式求值。 (4)集合的元素类型推广到其他类墩，甚至任意类型。7.2 任意长的整数加法运算【问题描述】设计一个程序实现两个任意长的整数的求和运算。【基本要求】设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。【实现说明】可以用顺序表、单链表、循环单链表、双向链表、循环双向链表或者各种栈去表示长整数，其中每个元素可以是字符、1位整数或分组的整数（4位一组），用单向链表表示时，可以采用低位在前，输出时再用栈，进行输出。【测试数据】7.3 任意长的整数乘法运算【问题描述】设计一个程序实现两个任意长的整数的乘法运算。【基本要求】设计一个实现任意长的整数进行乘法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。【实现说明】可以用顺序表、单链表、循环单链表、双向链表、循环双向链表或者各种栈去表示长整数，其中 每个元素可以是字符、1位整数或分组的整数（4位一组），用单向链表表示时，可以采用低位在前，输出时再用栈进行输出。7.4 任意长的整数除法运算【问题描述】设计一个程序实现两个任意长的整数的除法运算。【基本要求】设计一个实现任意长的整数进行除法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。【实现说明】可以用顺序表、单链表、循环单链表、双向链表、循环双向链表或者各种栈去表示长整数，其中 每个元素可以是字符、1位整数或分组的整数（4位一组），用单向链表表示时，可以采用低位在前，输出时再用栈进行输出。7.5 停车场管理【问题描述】设停车场是一个可停放，辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列(大门在最南端，最先到达的第一辆车停放在车场的最北端)，若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用，试为停车场编制按上述要求进行管理的模拟程序。【基本要求1以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输人数据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为:若是车辆到达，则输出汽车在停车场内或便道上的停车位置;若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费)。栈以顺序结构实现，队列以链表结构实现。【测试数据】 【实现提示】需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项:汽车的牌照号码和进入停车场的时刻。7.6 代码分析器【问题描述】 读入一个JAVA源文件，统计文件中的代码、注释和空行的行数以及函数的个数和平均行数，并利用统计信息分析评价该程序的风格.【基本要求】(1)把e程序文件按字符顺序读入源程序;（2）边读入程序，边识别统计代码行、注释行和空行，同时还要识别函数的开始和结束，以便统计其个数和平均行数。(3)程序的风格评价分为代码、注释和空行三个方面。每个方面分为A，B，C:和D四个等级。等级的划分标准如下：【测试数据】 先对较小的程序进行分析。当你的程序能正确运行时，对你的程序本身进行分析。【实现提示】为了实现的方便，可作以下约定:（1）头两个字符是/的行称为注释行(该行不含语句)。除了空行和注释行外，其余均为代码行(包括类型定义、变量定义和函数头)。（2）每个函数代码行数(除去空行和注释行)称为该函数的长度。（3)每行最多只有一个 、”,“switch”，“class”（便于识别函数的结束行）。7.7 哈夫曼编码译码器【问题描述】设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（压缩文件，后缀名.cod）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)。【基本要求】1.输入一个待压缩的英文文本文件，统计文本文件中各字符的个数作为权值，生成哈夫曼树；2.将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod） 3.输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码；【实现说明】1.在构造哈夫曼树时，可以利用不同的线性表存放二叉树：用顺序表、单链表、循环单链表、双向链表、循环双链表；2.在构造哈夫曼树时，可以利用优先队列存放二叉树：顺序队列、链队列（可以是单链表、双链表等，还可以用静态结构去实现），可以分别在入队列或出队列时实现优先级；3.二叉树本身也可以用静态数组模拟；7.8 一元稀硫多项式计算器【问题描述】 设计一个一元稀疏多项式简单计算器。【基本要求】一元稀疏多项式简单计算器的基本功能是:(1)输入并建立多项式;(2)输出多项式，输出形式为整数序列:n,c1,e1,c2,e2,. . .，cn,en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列;(3)多项式a和b相加，建立多项式a +b(4)多项式a和b相减，建立多项式a-b【测试数据】 【实现提示】用链表存储多项式。7.9 约瑟夫环【问题描述】编号为1，2 n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从某一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。 【基本要求】由键盘输入总人数，再依次输入每个人的姓名和密码建立人员表，再输入开始报数人的位置及初始报数上限，按照出列顺序输出各人的姓名。【实现说明】可以利用顺序表、单循环链表、双循环链表（其中链表可以带或不带附加表头结点，还可用静态结构实现链表）作为存储结构模拟此过程。【测试数据】M的初值为20，n=7，7个人的密码依次为3，1，7，2，4，8，4。首先m值为6（正确的出列顺序应为6，1，4，7，2，3，5）。【实现提示】程序运行后.首先要求用户指定初始报数上限值，然后读取各人的密码。可设n=30。7.10 哈希表的设计与实现(需要查阅教材chapter11 hash table的内容)【问题描述】 设计哈希表实现电话号码查询系统。【基本要求】1、设每个记录有下列数据项：电话号码、用户名、地址；2、从键盘输入各记录，以电话号码为关键字建立哈希表；3、查找并显示给定电话号码的记录；4、查找并显示给定用户名的记录。【实现说明】可以用不同的哈希函数、不同的解决冲突的策略。7.11 表达式求值问题【问题描述】设计一个程序，求解算术表达式的值。【基本要求】以字符序列的形式从键盘输入语法正确的、不含变量的整数（或实数）表达式，实现对算术四则混合运算表达式的求值。【实现说明】可以用不同生长方向的顺序栈、链栈【测试数据】7.12 学生成绩管理系统【问题描述】设计一个计算机管理系统对学生成绩进行管理【基本要求】一个学生包括：学号、姓名、数据结构、操作系统、数值计算和总成绩。要求能够：录入班级的学生成绩（按学号），保存到文件（或者从文件中调出），修改记录，删除记录，按学号输出、按单科成绩从高到低输出、按总成绩从高到低输出。对成绩，可能通过建立索引表来提高数据的可访问性。【实现说明】可以用不同的排序方式：（插入、希尔排序、冒泡排序、选择、快速排序等）7.13 班级通讯录【问题描述】设计一个计算机管理系统对班组通讯录进行管理【基本要求】一个学生的数据包括：学号、姓名、电话号码、手机、QQ号。要求能够：录入、修改、删除、查找和输出所有记录。为提高数据的可访问性，电话号码、手机、QQ号建立索引表，索引表可以在维护数据时动态维护，也可能最后一次建立。【实现说明】建立索引表时采用不同的排序方式：直接插入、希尔排序、冒泡排序、直接选择、堆排序；查找数据时可采用不同的查找方式：顺序查找、二分查找、黄金分割查找。7.14 数制转换问题【问题描述】实现不同数制数据间的转换，包括整数和小数。【基本要求】输入一种数的数据及数制，输出这个数的其他数制表示，要求包括二、八、十和十六进制。要求程序要有一个可供用户选择的简单操作界面。操作前要有简单的提示。【实现说明】可以用不同生长方向的顺序栈及链栈7.15 图书管理系统【问题描述】设计一个计算机管理系统完成图书管理基本业务。【基本要求】1.每种书的登记内容包括书号、书名、著作者、现存量和库存量；2. 对书号建立索引表（线性表）以提高查找效率，对新增的书，采用不同的排序算法建立索引表，再把2个索引表合并；3.系统主要功能如下：采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；查找：根据书号快速度查找书；借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；归还：注销对借阅者的登记，改变该书的现存量。【实现说明】可以采用不同的排序算法建立索引表，采用不同的查找算法根据书号快速度查找书目7.16 运动会分数统计【问题描述】参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。每个的项目取前3名积分（或者前5名），积分分别为：5、3、2（或者7、5、3、2、1）；（m=20,n=20）【基本要求】1.可以输入各个项目的前3名（或者前5名）的成绩；2.能统计各学校总分，3.可以按学校编号、学校总分、男女团体总分排序输出；4.可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前3（或者前5）的学校。【实现说明】可以用不同的排序算法进行排序输出7.17 航空客运订票系统【间题描述】 航空客运订票的业务活动包括:查询航线、客票预订和办理退票等。试设计一个航空客运订票系统，以使上述业务可以借助计算机来完成。【基本要求】 (1)每条航线所涉及的信息有:终点站名、航班号、飞机号、飞行周日(星期几)、乘员定额、余票量、已订票的客户名单(包括姓名、订票量、舱位等级1,2或3)以及等候替补的客户名单(包括姓名、所需票量); (2)作为示意系统，全部数据可以只放在内存中; (3)系统能实现的操作和功能如下: 查询航线。根据旅客提出的终点站名输出下列信息:航班号、飞机号、星期几飞行.最近一天航班的日期和余票额; 承办订票业务:根据客户提出的要求(航班号、订票数额)查询该航班票额情况.若尚有余票，则为客户办理订票手续，输出座位号，若已满员或余票额少于订票额.则需重新询间客户要求。若需要，可登记排队候补; 承办退票业务:根据客户提供的情况(日期、航班)，为客户办理退票手续.然后查询该航班是否有人排队候补，首先询间排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询间其他排队候补的客户。【测试数据】 由读者指定。【实现提示】两个客户名单可分别由线性表和队列实现。为查找方便，已订票客户的线性表应按客户姓名有序，并且，为插入和删除方便，应以链表作存储结构。由于预约人数无法预计。队列也应以链表作存储结构。整个系统需汇总各条航线的情况登录在一张线性表上，由于航线基本不变，可采用顺序存储结构，并按航班有序或按终点站名有序。每条航线是这张表上的一个记录，包含上述8个fields、其中乘员名单域为指向乘员名单链表的头引用，等候替补的客户名单域为分别指向队头和队尾的引用。【选作内容】 当客户订票要求不能满足时。系统可向客户提供到达同一目的地的其他航线情况。读者还可充分发挥自己的想象力，增加你的系统的功能和其他服务项目。7.18 校园导游咨询【间题描述】 设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】 (1)设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息。以边表示路径，存放路径长度等相关信息。 (2)为来访客人提供图中任意景点相关信息的查询。 (3)为来访客人提供图中任意景点的问路查询.即查询任意两个景点之间的一条最短的简单路径。【测试数据】由读者根据实际情况指定。【实现提示】一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。【选作内容】(1)求校园图的关节点。(2)提供图中任意景点间路查询，即求任意两个景点之间的所有路径;(3)提供校园图中多个景点的最佳访间路线查询。即求途经这多个景点的最佳(短)路径。(4)校园导游图的景点和道路的修改扩充功能。7.19 论文管理系统【间题描述】系里的老师们每年都在国内外刊物上发表论文。系办教务员、和各类项目的申报经常要对全系老师科研论文进行管理。请设计一个程序对这些信息进行管理。【基本要求】 实现以下功能：（1） 能添加论文信息；（2） 能按作者、年份或期刊等条件进行查询或统计，并显示查询结果（或输出到文本文件）；（3） 能对论文信息进行修改；（4） 能对论文记录进行删除；根据以上功能说明，设计具体的存储结构，要求程序要有一个可供用户选择的简单操作界面。操作前要有简单的提示。【测试数据】 由读者根据实际情况指定。【实现提示】论文的信息包括有（1） 篇名（2） 作者（3） 刊物名称（4） 期卷号（5） 页码（6） 刊物档次（一般刊物、核心刊物、国外刊物）（7） 是否EI收录（8） 是否SCI收录【选作内容】考虑多用户登录的情况，对程序进行权限管理（例如管理员可以进行信息的修改、添加或删除，一般用户只能做查询）。7.20 校园收发室管理系统【间题描述】学校收发室每天都收到寄给全校师生的信件、包裹和汇款单（统称为邮件），目前的管理手段是人工进行，费时而且容易出错。请设计一个程序对这些信息进行管理。【基本要求】 实现以下功能：（1） 能添加新邮件信息；（2） 能按姓名、日期间隔或单位进行查询，并显示查询结果（或输出到文本文件）；（3） 能对邮件信息进行修改；（4） 能对邮件记录进行删除；根据以上功能说明，设计具体的存储结构，要求程序要有一个可供用户选择的简单操作界面。操作前要有简单的提示。【测试数据】 根据实际情况指定。【实现提示】论文的信息包括有（1） 收件人姓名（2） 发件人（3） 邮件类型（普通/特快/汇款/包裹/）（4） 收件日期（5） 是否已经签收（6） 备注【选作内容】考虑多用户登录的情况，对程序进行权限管理（例如管理员可以进行信息的修改、添加或删除，一般用户只能做查询）。多条件进行联合查询，例如根据院系和日期进行查询。7.21 实验室预约管理系统【间题描述】某校多个实验室对全体学生开放。实验室共提供三种实验项目，分别在上午、下午和晚上进行。同一时间段只进行一种实验项目，每次接待的人数也有限制（例如最多30人）。现在要求设计一个预约管理系统对实验室的使用进行管理。【基本要求】 实现以下功能：（1） 根据学生的申请查找最早的可用的时间和实验室；并返回给申请者。（2） 能取消预约的申请，再次提供给预约使用；（3） 能对指定时间段实验室预约情况进行查询；根据以上功能说明，设计具体的存储结构，要求程序要有一个可供用户选择的简单操作界面。操作前要有简单的提示。【测试数据】 根据实际情况指定。【实现提示】可运用队列方式管理申请者。【选作内容】考虑多用户登录的情况，对程序进行权限管理（例如管理员可以进行开放实验室的添加、删除的修改，一般用户只能做查询，）。多条件进行联合查询，例如根据院系和日期进行查询。7.22 排序算法演示系统【间题描述】设计一个测试程序比较几种排序算法的关键字比较次数和移动次数以取得直观感受。【基本要求】（1）对冒泡排序、直接插入排序、简单选择排序、归并排序、快速排序、希尔排序算法进行比较；（2）待排序的元素的关键字为整数。其中的数据要用伪随机产生程序产生（如10000个），至少用5组不同的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较；（3）演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标值的列表，用条形图（星号表示）进行表示，以便比较各种排序的优劣。（4）每次测试结果设计为一个类，包括有算法名称，数据个数，时间等信息。并且要记录要存储到文件中，【测试数据】由随机数产生器生成。【实现提示】主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。程序还可以考虑几组数据的典型性，如：正序、逆序和不同程度的乱序。注意采用分块调试的方法。【选作内容】（1）对不同表长进行比较；（2）验证各算法的稳定性。7.23 个人理财管理系统【间题描述】该系统记录某人每月的全部收入及各项开支情况，包括食品消费，房租，子女教育费用，水电费，医疗费，储蓄等。进入系统后可以输入、和删除修改某月的收支情况，可以对每月的开支从小到大进行排序，可以根据输入的月份查询每月的收支情况。【基本要求】1）界面友好，类的职责要划分好；2）总体设计应画流程图；3）程序要加必要的注释；4）提供程序测试方案。【测试数据】 至少提供3个月、每月不少于10笔开支的模拟数据。【实现提示】无【选作内容】对查询结果进行分类统计（例如按开支类别或时间段）7.24 库存管理系统【间题描述】编写一个库存货品信息管理程序，要求能实现库存货品信息的输入、插入、删除、查找等功能，并能建立和更新的库存信息保存于文件供输出或打印。对于查找、删除等功能要求能按货品名、货品号分别进行。每个货品的相关信息包括：货品号、货品名、货品库存量、进货日期、货品生产厂家及供应商等。【基本要求】1）界面友好，类的职责要划分好；2）总体设计应画流程图；3）程序要加必要的注释；4）提供程序测试方案。【测试数据】 至少提供少于10种货物的模拟数据。【实现提示】无【选作内容】对查询结果进行分类统计（例如按开支类别或时间段）7.25 报刊订阅管理系统【间题描述】某企业每年都进行包括订阅，通过对某企业的报刊订阅业务进行分析、调查，设计该企业的报刊订阅管理系统。主要实现以下功能：录入功能：录入订阅人员信息（工号、所属部门）、报刊基本信息（刊名、订价）；订阅功能：订阅人员订阅报刊（并计算出其金额）；查询功能：按人员查询、按报刊查询、按部门查询有关订阅信息，对查询结果能进行预览和打印；统计功能：按报刊统计、按人员统计、按部门统计，对统计结果能进行预览和打印。【基本要求】1）界面友好，类的职责要划分好；2）总体设计应画流程图；3）程序要加必要的注释；4）提供程序测试方案。【测试数据】 订阅人员不少于10个、企业不少于5个部门，报刊种类不少于10种的模拟数据。【实现提示】无【选作内容】系统维护：如数据安全管理（含备份与恢复）、操作员管理、权限设置等。7.26 宾馆客房管理系统【间题描述】具体考察本市的宾馆，设计客房管理系统，要求具有：（1）数据录入功能在本系统中提供客人信息登记功能。可以录入客人的姓名、性别、年龄、身份证号码、家庭住址、工作单位、来自地的地名、入住时间、预计入住天数、客房类别、客房号、离店时间以及缴纳押金金额信息。在客人退房时，系统根据输入的离店时间及客房单价自动计算客人住宿费金额。（2）数据查询功能系统需要提供以下查询功能：1）查某类客房的入住情况及空房情况，显示所有该类客房空房数目和客房号。2）根据客人姓名、来自地的地名、工作单位或家庭等信息查询客人信息；根据客房号查询入住客人的信息。3）查询某个客人住宿费用情况，显示客人缴纳押金金额、实际入住天数、客房价格、实际住宿费、住宿费差额及余额等信息。4）查询所有入住时间达到或超过预计入住天数的客人。（3）数据统计功能1）统计一段时间内各类客房的入住情况2）统计全年各月份的客房收入3）统计一段时间内各类客房的入住率【基本要求】1）界面友好，类的职责要划分好；2）总体设计应画流程图；3）程序要加必要的注释；4）提供程序测试方案。【测试数据】 房间类型不少于3种、每种房间数不少于10间。【实现提示】需要建立三个表1）客人信息表（序号、姓名、性别、年龄、身份证号码、家庭住址、工作单位、来自地的地名、入住时间、预计入住天数、客房号、离店时间、押金金额、住宿费）。2）客房信息表（客房号、客房状态、客房类型编号、入住客人序号）3）客房类型数据表（客房类型编号、客房类型名称、该类型客房价格）【选作内容】系统维护：如数据安全管理（含备份与恢复）、操作员管理、权限设置等。7.27 通讯网络构造问题【间题描述】如果以无向网表示n个城市之间通信网络的建设计划，顶点表示城市，边上的权表示该线路的造价，设计一个方案，使这个通讯网的总造价最低。【基本要求】1）能添加、删除城市、添加、修改两城市之间线路造价；2）能输出通讯网的方案。 3）能查询按通讯网方案实施后，两城市之间线路造价。【测试数据】 城市不少于5个。【实现提示】这是一个求最小生成树的问题。n个城市名和各边的权值由用户输入，建立图的邻接矩阵，然后以Prim算法来求最小生成树，然后输出方案。【选作内容】系统维护：如数据安全管理（含备份与恢复）、操作员管理、权限设置等。7.28 电梯模拟【问题描述】1、电梯运行电梯从一楼开始运行，如果没有呼叫，则原地停止；如果电梯空闲时间超过一定时间，而且整个大楼无乘客等待，则电梯回到一楼待命；装载乘客的方式为先下后上，如果超重则不装载；如果乘客已满，则在中间层无人下来时，将直接到达目的层；如果电梯无人乘坐向某个方向运行时，其反方向有呼叫时，电梯应当立即掉头。2乘客排队等待的乘客可以采用先来先进电梯，也可以赋予一定优先级（如：老幼优先），但是乘客等待的时间超过某个设定值时，将会放弃。【基本要求】设置信息1电梯基本信息最大载重、最大装载人数、上下每一层的时间。2楼层信息楼层号可能是负值（地库），每一层楼有一个呼叫点，包括呼叫的状态。3乘客基本信息包括体重、目标楼层、所处楼层、可以容忍的等待时间，如果乘客需要按优先级排队，则需要包括一些附加信息来确定优先级（包括姓名）。【实现提示】每层楼都包括上下各一个等待队列，自行设定乘客的等待策略；电梯处于三种状态：上行、下行和空闲。【注意事项】1顾客基本信息尽量采用随机生成，但是要有数量的限制；2电梯上下运行过程中应当保证既不超过重量与人数，也不漏载。【选作】1为电梯增加自动与人工操作方式，在人工操作时，可能会强制设定某些楼层不停。2增加开门与关门以及进出电梯的时间控制。3增加乘客携带货物的功能，电梯则需要增加总空间尺寸限制。4完全模拟一栋楼房从早到晚的电梯运行过程。7.29 员工管理系统【问题描述】对单位的员工进行管理，包括插入、删除、查找、排序等功能。【要求】职工对象包括姓名、性别、出生年月、工作年月、学历、职务、住址、电话等信息。（1）新增一名职工：将新增职工对象按姓名以字典方式职工管理文件中。（2）删除一名职工：从职工管理文件中删除一名职工对象。（3）查询：从职工管理文件中查询符合某些条件的职工。（4）修改：检索某个职工对象，对其某些属性进行修改。（5）排序：按某种需要对职工对象文件进行排序。【实现提示】职工对象数不必很多，便于一次读入内存，所有操作不经过内外存交换。（1）由键盘输入职工对象，以文件方式保存。程序执行时先将文件读入内存。（2）对职工对象中的姓名按字典顺序进行排序。（3）对排序后的职工对象进行增、删、查询、修改、排序等操作。【选做内容】将职工对象按散列法存储，并设计解决冲突的方法。在此基础上实现增、删、查询、修改、排序等操作。7.30 餐饮管理系统【问题描述】参照餐馆点菜、埋单业务。设计一个程序对餐馆的订餐业务进行管理。【要求】菜谱中的菜包括类别、菜名、菜量（加量、例牌等）、菜价等信息。食客信息包括，座号，已点菜肴，是否持有折扣卡，是否已经埋单,入座时间、结账时间等、已经消费金额。系统具备如下功能：（1）新增、删除、修改菜的信息。（2）新增、删除、修改食客信息。（3）查询食客已点菜单，并进行结账。（4）查询某时间段营业额。要求程序要有一个可供用户选择的简单操作界面。操作前要有简单的提示。【实现提示】可采用数组来存储菜谱、链表存储食客信息。【选做内容】查询指定时间段某个菜的被点次数，并按次数排序。7.31 工资管理系统【问题描述】X公司的出纳员小王的任务是统计每位员工的工资。但该公司的老板反复无常，经常调整员工的工资，如果心情好，就给所有的员工涨相同的量，反之就扣除相同的量。有的员工因此离开了公司，每位员工的工资下界是统一规定的。设计一个工资程序，帮小王进行管理。【要求】1）插入：招聘新员工时，将其加入到系统中。 2）删除：某位员工离开时，将其删除。 3）修改：修改每位员工的工资时（包括涨工资和减工资两种情况） 4）查询：帮助老板查询某位员工的工资。 5）统计：统计员工的最高，最低，平均工资，工资总额。要求程序要有一个可供用户选择的简单操作界面。操作前要有简单的提示。【实现提示】无【选做内容】存储每个员工工资调整的历史，并提供查询。7.32 文档工具【问题描述】 功能：读入一个文本文件，程序可以统计出文字、数字、空格的个数。读入数据后，按行存储文章，每行最多不超过80个字符，共N行；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出文本文件的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文档总字数（3）输出删除某一字符串后的文档。【实现要求】 要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。【实现提示】 建立一个Document类，内部有一个链表，每个链表元素均为为数组，代表文本的一行。然后在Document类中分别实现各种方法（统计，操作等）。Document类在main函数中供界面代码调用。【选作内容】文本的查找、替换功能。7.33 话费管理系统【问题描述】 为某移动通信服务公司建立一个话费管理系统,假设该公司的用户号码为188*。每个号码有自己的客户资料，以及各自的通话记录表（请拟出一个话费清单记录各用户每天的通话记录）。请拟出一个话费计价标准，并根据各用户每天的通话记录，计算出每个用户的话费余额。【实现要求】 用户可以输入号码查询话费余额读入每天话费清单计算当天的话费。【实现提示】 建立一个Account类，用来记录号码账户信息（包含号码、客户姓名、余额等），该类的对象与一个话费清单对应。【选作内容】（1）允许对计费标准进行替换，比如开展优惠活动，某时段话费打折；（2）话费充值等功能。7.34 水电费计费系统【问题描述】 为某大学物业管理公司建立一个水电费计费系统。每个学生宿舍为单独计费单位。每个宿舍有自己的客户资料，以及各自的每月的水电用量表。请拟出一个水电费计价标准，并根据各用户每月的水电用量，计算出每个用户的水电费余额。【实现要求】 用户可以输入宿舍号码查询水电费余额读入每月水电费度数清单计算出应缴水电费。【实现提示】 建立一个Account类，用来记录号码账户信息（包含宿舍号、联系电话、余额等），该类的对象与一个水电清单对应。【选作内容】允许对计费标准进行替换，比如开展会员卡优惠活动，按时缴交累计多少月可享受优惠等7.35 论坛管理系统【问题描述】 为某网站模拟一个论坛管理系统,管理对象为:用户（user）,主题（thread），回复（reply）。要求能够对这三种对象进行查询、删除。【实现要求】 （1） 初始数据可以在程序中给出；（2） 要求提供界面以供管理员查询、删除。【实现提示】 分析清楚三类对象之间的数量关系。分别用数组或者链表对数据集合进行建模。【选作内容】 能够对主题进行更改、加精、置顶等操作。7.36 综合测评管理系统（文体分、学业分、思想分各算一个题）【问题描述】 设计一个用于综合测评分管理系统，可用于每学年的综合测评。【实现要求】 学生信息可以由静态数据提供，比如从一个文本文件读入。通过录入学生学号，然后逐项显示各项内容，录入分数。给出合计分，班级排名或者年纪排名。【实现提示】 每个学生信息内部包含一个单项分对象。【选作内容】 GUI界面实现7.37 创新学分管理系统【问题描述】 根据学校对创新学分的要求，设计一个用于创新学分管理的系统。【实现要求】 学生信息可以由静态数据提供，比如从一个文本文件读入。通过录入学生学号，然后逐项显示各项内容，录入分数。给出合计分，班级排名或者年纪排名。【实现提示】 每个学生信息内部包含一个单项分对象。【选作内容】 GUI界面实现7.38 游戏玩家装备管理系统【问题描述】 设计一个用于管理游戏中玩家装备的系统。【实现要求】 玩家信息可以由静态数据提供，比如从一个文本文件读入。通过录入装备名称，然后逐项显示装备的各项属性，录入装备信息。玩家可以在界面选购装备，并计算出各自的各项属性。【实现提示】 每个学生信息内部包含一个单项分对象。【选作内容】 GUI界面实现袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿蚇蒂膇肈莇螇肃肇葿薀罿肆薂螆袅肅芁薈螁膅莃螄聿膄蒆薇羅膃蚈螂羁膂莈蚅袇膁蒀袀螃膀薂蚃肂腿节衿羈腿莄蚂袄芈蒇袇螀芇蕿蚀聿芆艿蒃肅芅蒁螈羁芄薃薁袆芃芃螆螂芃莅蕿肁节蒈螅羇莁薀薈袃莀艿螃蝿荿莂薆膈莈薄袁肄莇蚆蚄羀莇莆袀袆羃蒈蚂螂羂薁袈肀肁芀蚁羆肁莃袆袂肀薅虿袈聿