数据结构课程设计(软件工程)

《数据结构课程设计》

指导书软件学院软件工程（娱乐软件）2015年06月《数据结构课程设计》指导书一、课程设计题目与要求根据课程设计题目规模，要求每个题目可分组完成（不超过3个人）。一经确定不得随意调换，题目由各组选派代表抽签确定，设计题目不得更换。运动会分数统计任务：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20）功能要求：1） 可以输入各个项目的前三名或前五名的成绩；2） 能统计各学校总分，3） 可以按学校编号或名称、学校总分、男女团体总分排序输出；4） 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。5） 数据存入文件并能随时查询6） 规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。请在最后的上交资料中指明用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；飞机订票系统任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；宿舍管理查询系统1） 任务：为宿舍管理人员编写一个宿舍管理查询软件，程序设计要求：采用交互工作方式建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序（冒泡、选择、插入排序等任选两种方法实现）2） 查询菜单:（用二分查找实现以下操作）按姓名查询按学号查询按房号查询打印任一查询结果(可以连续操作)简易银行卡管理系统主要功能与要求：开户：创建一个新的账户，接受用户输入的身份证号，以及账户密码，判断用户输入的身份证号是否唯一且账户密码是否符合要求，如验证成功则为该用户生成一个唯一的帐号。存款：在用户输入正确的帐号和密码的情况下，接受用户输入的存款金额，并对该帐号的存款信息进行更新。取款：在用户输入正确的帐号和密码的情况下，接受用户输入的取款金额。取款金额不应该大于当前帐号存款金额，当取款金额不大于当前帐号存款金额时，执行取款操作，并对该帐户的存款信息进行更新。挂失：在用户输入正确的帐号和密码的情况下，接受用户挂失操作。当帐号挂失后，与该帐号相关的操作都将被禁止。销户：在用户输入正确的帐号和密码的情况下，接受用户销户。当用户销户后，该帐号将被永久删除。转帐：在用户输入正确的帐号和密码的情况下，接受用户转账操作，转帐金额不应该大于当前帐号存款金额，当转帐金额不大于当前帐号存款金额时，执行转帐操作，并对该帐户的存款信息及转帐的接受账户的存款信息进行更新。修改账户密码：在用户输入正确的帐号和密码的情况下，接受用户修改密码操作，用户输入的原密码，若用户输入的密码与原密码匹配，则接受用户输入的新密码，若用户两个输入的密码相同，则修改账户密码，并对数据文件进行更新操作。查看余额：在用户输入正确的帐号和密码的情况下，接受用户查看余额操作，该模块只涉及数据查询，并不涉及数据文件更新操作。查看用户交易历史：在用户输入正确的帐号和密码的情况下，接受用户查看用户交易历史操作，系统将显示当前账户的最近的存、取款操作记录，该模块只涉及数据查询，并不涉及数据文件更新操作。校园导航设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径(最短路径)。基本要求：设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。为来访客人提供图中任意景点相关信息的查询。为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。通讯录管理系统模块要求：第一个模块一一主函数main()的功能是：根据选单的选项调用各函数，并完成相应的功能。第二个模块——Menu()的功能是：显示英文提示选单。第三个模块——Quit()的功能是：退出选单。第四个模块 Create()的功能是：创建新的通讯录。第五个模块——Add()的功能是：在通讯录的末尾，写入新的信息，并返回选单。第六个模块——Find()的功能是：查询某人的信息，如果找到了，则显示该人的信息，如果未找到，则提示通讯录中没有此人的信息，并返回选单。第七个模块——Alter()的功能是：修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。第八个模块——Delete()的功能是：删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。第九个模块 List()的功能是：显示通讯录中的所有记录。；设计要求：每条信息至包含：姓名(NAME)、性别(GENDER)、电话(TEL)、城市(CITY)由^编(EIP)几项。通讯录采用文件保存。作为一个完整的系统，应具有友好的界面和较强的容错能力。职工管理系统问题描述：对单位的职工进行管理，包括插入、删除、查找、排序等功能。要求：职工对象包括姓名、性别、出生年月、工作年月、学历、职务、住址、电话等信息。新增一名职工：将新增职工对象存入职工数据文件中。删除一名职工：从职工数据文件中删除一名职工对象。查询：从职工数据文件中查询符合某些条件的职工。修改：检索某个职工对象，对其某些属性进行修改。排序：按某种需要对职工对象文件进行排序(冒泡、选择、插入排序等任选两种方法实现)。实现提示：职工对象数不必很多，便于一次读入内存，所有操作不经过内外存交换。由键盘输入职工对象，以文件方式保存。程序执行时先将文件读入内存。(2)对职工对象中的”姓名”按字典顺序进行排序。(3)对排序后的职工对象进行增、删、查询、修改、排序等操作。选做内容：将职工对象按散列法存储，并设计解决冲突的方法。在此基础上实现增、删、查询、修改、排序等操作。全国交通资讯系统问题描述：设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方案：时间最短费用最小中转次数最少。需求分析：该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。在程序中输入城市名称时，需输入10个字母以内的字母串；输入列车或飞机编号时需输入一个整型数据；输入列车或飞机的费用时需输入一个实型数据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据(以hh：mm的形式)；在选择功能时，应输入与所选功能对应的一个整型数据。程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达。附录：测试数据航班时刻表

机号出发地到达地出发时间到达时间费用6320北京上海上海北京16：2018：0017：2519：05680元2104北京乌鲁木齐乌鲁木齐北京8：0010：459：5511：401150元201北京西安西安北京15：2512：3517：0014：15930元2323西安广州广州西安7：1510：159：3511：351320元173拉萨昆明昆明拉萨10：2012：3511：4514：00830元3304拉萨武汉武汉拉萨14：1516：2515：4517：55890元82乌鲁木齐昆明昆明乌鲁木齐9：3013：0512：1515：501480元4723武汉广州广州武汉7：0511：258：4513:05810元列车时刻表车次出发地到达地出发时间到达时间车费27北京郑州13：1521：1278元郑州西安21：2405：1382元西安郑州05：4113：3082元郑州北京13：4221：3978元41北京郑州7：1115：0890元郑州上海15：2000：13100元上海郑州00：3509：28100元郑州北京09：4017：3790元59上海广州08：2003：16182元广州上海03：3922：53134兰州北京03：5218：56162元北京兰州19：2410：28323广州昆明06：1816：14102元昆明广州16：3102：27873武汉昆明07：1321：17134元昆明武汉21：4211：46116武汉长沙9：3618：3298元长沙武汉18：5403：48373长沙广州13：1500：15116元广州长沙00：3511：35兰州武汉17：4114：47210元747武汉兰州15：1312：19371兰州乌鲁木齐乌鲁木齐兰州11：4200：3523：5411：23114元218武汉西安西安武汉18：5001：3411：5118：35178元停车场管理有一个两层的停车场，每层有6个车位，当第一层车停满后才允许使用第二层.（停车场可用一个二维数组实现，每个数组元素存放一个车牌号）每辆车的信息包括车牌号、层号、车位号、停车时间共4项，其中停车时间按分钟计算。假设停车场初始状态为第一层已经停有 4辆车，其车位号依次为1—4，停车时间依次为20,15,10,5。即先将这四辆车的信息存入文件"car.dat"+（数组的对应元素也要进行赋值）。停车操作：当一辆车进入停车场时，先输入其车牌号,再为它分配一个层号和一个车位号（分配前先查询车位的使用情况,如果第一层有空则必须停在第一层）,停车时间设为5,最后将新停入的汽车的信息添加文件”car.daf中,并将在此之前的所有车的停车时间加5。收费管理（取车）：当有车离开时，输入其车牌号，先按其停车时间计算费用，每5分钟0.2元.（停车费用可设置一个变量进行保存）,同时从文件”car.dat”中删除该车的信息，并将该车对应的车位设置为可使用状态（即二维数组对应元素清零）.按用户的选择来判断是否要输出停车收费的总计。输出停车场中全部车辆的信息。商品销售统计系统设计商品销售统计系统，实现定期对销售各商品的记录进行统计，可按商品的编号、单价、销售量或销售额做出排名并显示。选择合适的存储结构，建立商品信息表并存放在数据文件中。各商品的信息包括：商品编号、名称、单价、销出数量、销售额。对各商品的单价、销售量或销售额进行排序时，可采用多种排序方法，如直接插入排序、折半插入排序、冒泡排序，快速排序、选择排序等方法。功能设计：（1） 实现建立商品信息表功能（2） 实现分别使用不同的排序方法按商品单价、销售量、销售额进行排序功能（3） 实现显示排序结果功能图书管理系统设计一个计算机管理系统完成图书管理基本业务。基本要求：（1） 每种书的登记内容包括书号、书名、著作者、现存量和库存量；（2） 对书号建立索引表（线性表）以提高查找效率；（3） 系统主要功能如下：采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；借阅：如果一种书的现存量大于0,则借出一本，登记借阅者的书证号和归还期限，改变现存量；归还：注销对借阅者的登记，改变该书的现存量。文章编辑系统功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行。要求：（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能。输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出“全部字母数”、“数字个数”、“空格个数”、“文章总字数”；（3）输出删除某一字符串后的文章。学生成绩管理系统现有学生成绩信息文件1（1.txt）,内容如下：姓名学号语文数学英语张明明01677882李成友02789188张辉灿03688256王露04564577陈东明05673847学生成绩信息文件2（2.txt）,内容如下:姓名学号语文数学英语陈果31576882李华明32889068张明东33484256李明国34504587陈道亮35475877试编写一个管理系统，要求如下：1） 要求使用链表或数组等实现上述要求2） 实现对两个文件数据进行合并，生成新文件3.txt3） 可实现学生成绩信息的输入、修改、删除功能4） 抽取出三科成绩中有补考的学生并保存在一个新文件4.txt5） 对合并后的文件3.txt中的数据按总分降序排序（至少采用两种排序方法实现）6） 输入一个学生姓名后，能查找到此学生的信息并输出结果（至少采用两种查找方法实现）7） 统计输出各门课程的平均分，最高分、最低分8） 统计各门课程优秀、良好、中等、及格、不及格的人数及百分比客户消费积分管理系统问题描述：针对客户的消费情况进行客户管理，根据客户的消费积分对客户实行不同程度的打折优惠。基本要求：1） 采用一定的存储结构进行客户信息的存储2） 对客户的信息可以进行添加、修改、删除3） 可根据消费情况进行客户积分的计算4） 根据积分情况实行不同程度的打折优惠舞伴问题问题描述：一班有m个女生、n个男生（m不等于n）,举办一场舞会.男女生分别编号坐在舞池两边的椅子上，每曲开始时，依次从男生和女生中各出一人配对跳舞，本曲没成功配对者坐着等待下一曲找舞伴，设计一个程序模拟舞伴配对过程。基本要求：输入男、女学生的姓名、性别，由程序自动为男女生编号，可以顺序编号，也可以随机编号，输出每曲配对情况（包括男、女生的姓名、性别和编号〉原始数据和结果数据要保存到文件中。16.管道铺设施工的最佳方案问题描述:需要在某个城市的n个小区铺设管道，则在这n个小区之间铺设n-1条管道即可，假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费不同，选择最优的施工方案使总投资尽可能的少。基本要求：输入表示小区间关系的图及每条管道的权值，选择出n-1条管道，使总投资最小。图的信息输入一次后，保存到文件中，选择的n-1条管道输出到显示器的同时，也保存于文件中。（1） 设计良好的用户界面（2） 采用两种存储结构实现（3） 用两种算法找到最小生成树。（4） 输出原始图及选择n-1条管道后的图。测试用例：任意选择一个图，模拟小区间可能铺设的管道及费用。二、课程设计报告内容与要求课程设计报告主要内容应包括：1、 需求分析：根据题目要求，充分地分析和理解问题，描述系统的功能要求，分析系统所要处理的数据有哪些类型，它们之间存在哪些关系，采用何种数据结构描述。充分地分析和理解题目，明确要做什么（而不是怎么做，即设计的系统将要实现的功能），系统的输入与输出；系统的测试用例。（1） 问题描述（2） 基本要求输入的形式和输入值的范围输出的形式程序所能达到的功能2、 概要设计根据需求分析，完成数据模型及相关运算的定义，给出数据结构的ADT表示；设计系统的原型（操作界面）。说明本系统中用到的所有数据类型的定义及存储结构，主程序的流程以及各程序模块之间的调用关系。（1） 数据结构（2） 程序模块（3） 各模块之间的调用关系以及算法设计3、 详细设计实现概要设计中定义的所有数据类型，对主要操作写出实现算法，对主程序和其他模块写出算法，写出函数的调用关系。4、 编码调试：根据详细设计完成系统的编码、测试程序，要有给定的正确数据、错误数据和边界数据，要有不同的结果并进行结果分析，对于出现的错误，要进行错误分析，并进行改正。5、 总结（收获与体会，不少于500汉字）：主要内容包括：（1） 本次课程设计各阶段（需求分析、概要设计、详细设计、编码调试等）所遇到的问题，问题的现象描述，产生的原因，解决方案（措施），解决的结果等；（2） 测试结果分析，给出所采用的测试数据并对所得到的结果进行分析，分析算法的性能（时间与空间复杂度）。（3） 探讨更多解决问题的途径，给出改进算法的建议。（4）本次课程设计收获：存在的问题（不足之处）、感想、今后努力的方向等。参考文献附件：程序源代码（重点功能加上必要的注释）三、 设计报告的格式要求一律打印（A4纸张），简易装订。字体大小及格式可参照如下：标题题目用小二号黑体字书写，居中放置，并且距下文双倍行距；第一层次（章）题序和标题用小二号黑体字，第二层次（节）题序和标题用小三号黑体字，第三层次题序和标题用四号黑体字，第四层次及以下题序和标题用小四号黑体字，正文用小四号宋体字。正文章节序号均以阿拉伯数字连续编号，最多为4级，（如：1.1.1 1.1.1.1），章条编号一律左顶格，编号后空一'个字距，再写章条题名；之后先以括号为序（如（1）、（2）…），再以带圈字符为序（如1、2…），左空2个字距书写。正文正文文字内容一律采用小四号宋体字，正文中英文用四号'TimesNewRoman”字体;各级层次标题与上下文间均为1.5倍行距。公式图表图表和公式要按章编号。公式应另起一行书写，公式应尽量采用公式编辑器输入，选择默认格式，公式号右对齐；图表应有相对应的名称，图表标题均居中，用五号宋体字书写，且置于文章中首次提到处附近。参考文献凡引用本人或他人已公开或未公开发表文献中的学术思想、观点或研究方法、设计方案等，都应编入参考文献目录。参考文献的编写格式为：图书文献的格式：［编号］作者.书名.出版单位，年份，版次，页码。技术标准：［编号］标准名称.标准代号.标准顺序号-发布年.打印要求单面打印，上2.5cm，下2cm，左2.5cm，右2.0cm，页码用小五号宋体字下居中标明。四、 课程设计时间及地点周次日期设计内容具体要求设计教室指导时间段172015.6.29.(周一)安排分组，选择设计题目，查阅相关资料熟悉课题的相关资料［龙］计算中心(14:30-16:10)2015.6.30(周二)熟悉课题的任务和要求；系统分析、规划，划分功能模块，小组成员分配任务模块功能划分，任务分配［龙］计算中心(14:30-16:10)2015.7.1(周三)收集相关资料进行需求分析确定模块的功能要求［龙］计算中心(14:30-16:10)

2015.7.2（周四）不既要设计，说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）给出程序设计框架图和使用的数据结构［龙］计算中心（14: