2022年数据结构实训指导书 .pdf

《2022年数据结构实训指导书 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实训指导书 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计指导书一、课程设计的目的、要求和任务本课程设计是为了配合数据结构课程的开设， 通过设计完整的程序，使学生掌握数据结构的应用、算法的编写、类C 语言的算法转换成程序并用上机调试的基本方法。1.课程的目的（1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。（2）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。（3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力；2.课程的基本要求与任务（1）巩固和加深对数据结构基本知识的理解，提高综合运用课程知识的能力。（2

2、）培养学生自学参考书籍，查阅手册、图表和文献资料的能力。（3）通过实际课程设计，初步掌握简单软件的分析方法和设计方法。（4）了解与课程有关的工程技术规范，能正确解释和分析实验结果。（5）题目具有足够的工作量。二、课程设计的一般步骤：1. 选题与搜集资料：每人选择一题，进行课程设计课题的资料搜集。2. 分析与概要设计：根据搜集的资料，进行程序功能与数据结构分析，并选择合适的数据结构、并在此基础上进行实现程序功能的算法设计。3. 程序设计：运用掌握C/C+语言编写程序，实现各个模块功能。4. 调试与测试：调试程序，并记录测试情况。5. 完成课程设计报告。6. 验收与评分：指导教师对每个同学的开发的

3、系统进行综合验收，评分。三、课程设计报告的规范课程设计报告要求规范书写，应当包括如下6 个部分：1 问题描述2 基本要求3 系统分析与设计4 测试数据及结果5 总结6 附录：源程序清单四、成绩评定标准学生成绩由以下几个方面进行评定：1. 学生编写的实际软件和运行结果，占总成绩40%；2. 设计报告，占总成绩40% 3. 答辩，占总成绩10% 4. 出勤，占总成绩10% 五、实习过程名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - -

4、项目实训过程分为六个阶段，各阶段如下：1、 立项（ 0.25 天）2、 需求分析（ 0.75 天）3、 软件设计（ 1 天）4、 编码（ 2 天）5、 测试修订（ 0.5 天）6、 交付（ 0.25 天）7、 结项（ 0.25 天）合计 5 天。六、备注：1. 选题：（1）以下给出的课程设计题目分为三类，学生可以从任何一类中选择一个题目，并做好相关准备（注意每一题限报人数）；（2）时间安排：第 19 周周三上午和周五一天2. 功能完成及检测（1）要求独立完成规定的工作任务，不得弄虚作假，不准抄袭他人内容，否则成绩以不及格计。（2）鼓励同学们充分发挥主观能动性，结合所选课题，独立思考，努力钻研，

5、勤于实践， 勇于创新， 在完成题目的基本要求外，尽量完善程序， 提高程序的可读性、健壮性等，完成好的同学，给以适当加分。六、课程设计题目类型一：应用系统类题目一、 火车票订票系统难度：易问题描述：设计一个火车票订票系统，提供查询路线；承办订票业务；承办退票业务；登记旅客情况及统计等功能。基本要求：（1）查询路线：两个子选项，对应两种方式查询：l 根据旅客提出的车次输出起点站和终点站名；2 根据旅客输入站名，查询车次情况。（2）承办订票业务：根据客户提出的情况（车次、时间）查询该车次票额的情况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于订票额，则需重新查询客户要求，若需要

6、可登记排队候补。（3）承办退票业务：根据客户提供的情况（车次、时间、座位号）为客户办理退票手续，然后查询该车次是否有人排队候补， 首先询问排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其他排队候补的客户。（4）登记旅客情况：包括旅客姓名，性别，年龄，家庭住址，联系方式等。（5）统计功能：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 将每次车的订票，退票结果统计出来。（6）管理功能： (选) 列车管理

7、员可以查看车票及其用户情况. 注：每条线路所涉及的信息有：起点、终点、站名、车次、票价、时间、座位号。项目要求：1人机交互界面友好，对用户的非法输入要有一定的判断及提示；2可根据项目完成情况，在数据输入部分，添加利用文件导入的功能；在数据输出部分，添加数据导出到文件的功能；3在很好完成必做模块的前提下，如又实现了选做模块，将给团队和相应个人加分；主要技术点：数组，队列，链表。团队配置：3 人题目二、学生信息管理系统难度：中问题描述：设计一个学生信息管理系统，实现对学生基本信息的添加、删除、修改和查询等操作。基本要求：（1） 多种方式建立学生信息每个学生信息由学号、姓名、数学、英语和语文组成；可

8、以通过手工录入每个学生信息，并在C 盘下以 StudentFile.txt 保存；也可以导入某个路径下存放学生信息的文本文件。（选）（2） 浏览所有学生信息。（3） 按照学号对所有学生信息进行升序、降序排列，并输出可选用冒泡、选择、快速排序等算法；不仅输出屏幕显示，还需要写入存放学生信息的文件。（4）按姓名、学号等方式，实现对学生信息精确查询、模糊查询，并输出屏幕显示精确查询结果演示查询“姓名是刘梅”同学信息，则输出学号姓名数学英语语文,. 2004112011 刘梅88 90 78 ,. 模糊查询结果演示查询“姓刘”的同学信息，则输出学号姓名数学英语语文,. 2004112011 刘梅88

9、90 78 ,. 2004112011 刘强87 80 98 ,. 2004112011 刘星86 70 58 ,. 能够实现连续多次查询（5） 学生信息的插入、删除、修改。通过插入、删除和修改后，保持所有学生信息的有序性；插入、删除和修改后，对存放所有学生信息的文件及时更新。（选）（6） 数据的统计功能名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 统计每个学生的平均分和总分；统计每个科目的平均分和最高分、最低分；将上述统计结

10、果，写入存放学生信息的文件。（选）项目要求：1人机交互界面友好，对用户的非法输入要有一定的判断及提示；2可根据项目完成情况，在数据输入部分，添加利用文件导入的功能；在数据输出部分，添加数据导出到文件的功能；3在很好完成必做模块的前提下，如又实现了选做模块，将给团队和相应个人加分；主要技术点：数组，链表。团队配置：4 人题目三、停车场管理系统难度：难问题描述：设计一个停车场管理系统，模拟停车场的运作。基本要求：（1） 要求以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理；（2） 要求处理的数据元素包括如下数据项：汽车“到达” 或“离去” 信息、汽车牌照及 “到达”或“离去”的时刻

11、；（3） 车辆到达，首先判断停车场是否满l 若有空位置，停车，并输出汽车在停车场内停车位置，并记录停车时间。l 若没有空位，请用户选择离开还是在便道上等待i. 若离开，不做任何操作，ii. 若等待，加入便道上等待队列（若队列满，回到i） ，并记录便道上的停车位置；（4） 车辆离去l 若在停车场内离开，就输出汽车在停车场内停留的时间和应交纳的费用，并允许便道上队列前面的汽车进入停车场；l 若是便道上的车辆离开，则不收费。（5） 完成该停车场的一些信息统计功能（如每天到达/离开的车次，停车总时数、每天的停车费用等） 。项目要求：1人机交互界面友好，对用户的非法输入要有一定的判断及提示；2可根据基本

12、要求，对系统的功能作进一步的完善；3在很好完成必做模块的前提下，如又实现了选做模块，将给团队和相应个人加分；主要技术点：数组，链表，队列。团队配置：4 人类型二、算法类题目四、哈夫曼树编码/译码系统难度：中问题描述：哈夫曼编码在通讯、网络、数据压缩、图像处理中的得到广泛应用，在一个通讯系统中，采用图形界面设计m 叉哈夫曼树 (m2)，对通讯信息进行编码和解码。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 基本要求：（1） 从终

13、端读入字符集大小n，以及 n 个字符和n 个权值， 建立 m 叉哈夫曼树， 并将哈夫曼树以直观的方式（如树形）显示在终端上；（2） 利用已经建好的哈夫曼树，对终端输入的字符串或者文件ToBeTran 中的正文进行编码，然后将结果存入文件CodeFile 中，并输出结果，将文件CodeFile 以紧凑格式显示在终端上，每行50 个代码。同时将此字符串形式的编码文件写入文件CodePrint 中。（3） 利用已建好的哈夫曼树将文件CodeFile 中的代码进行译码，结果存入文件TextFile中，并输出结果。项目要求：1. 对控制台的输入需要一定的容错能力，给出一定的提示信息；2. 对输出的结果进

14、行一定的美化，做到内容清晰、易懂；主要技术点：哈夫曼编码、文件的输入、文件的输出。团队配置：3 人。题目五、 .校园导游系统难度：难问题描述： 设计一个校园导游程序，完成校园信息的维护以及为来访的客人提供信息查询等服务功能。基本要求：（1）设计学校的校园平面图，所含景点不少于10 个，以图中顶点表示校内各景点，顶点的信息包括：景点名称、代号、简介等，以边表示道路，边上信息包括：两点距离、所需时间等相关信息。 （注：数据的输入可以是键盘输入或文件输入两种方式）（2）提供对校园景点信息的编辑（如：添加、删除、修改等）的功能；（3）为来访客人提供图中任意景点相关信息的查询（可提供多种查询方式）；（4

15、）为来访客人提供从校门口到图中任意景点的问路查询（最短路径）；（5）为来访客人提供图中任意景点间的问路查询。项目要求：1 对于控制台界面的输入需要增加容错能力，对于输入给出完整的提示信息，使得操作者能够轻松操作；2 对输出的结果进行一定的美化，做到内容清晰、易懂；3 对于一个团队的人员要根据个人情况进行分模块合作；4 可以发挥自己的想象空间，增加基本要求的内容。有新内容的增加，而且实现完好，整个团队都加分。主要技术点：图建立、图的遍历。团队配置：团队配置：4 人。题目六、最小生成树问题难度：易问题描述： 已知一个无向连通网表示n 个城市以及城市间可能设置的通信线路，其中网的顶点表示城市， 边表

16、示两个城市之间的线路，赋于边上的权值表示相应的代价。对于 n 个点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在， 我们要选择这样一棵生成树，使总的耗费最小。即构造连通网的最小生成树的问题。基本要求：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - （1）建立城市交通网的存储结构。（注：数据输入可以是键盘输入或文件输入两种方式）（2）分别用Prim 算法和 Kruskal 算法构造最小生成树，并输出最小生成

17、树的代价及生成树的边。 （注：结果的输出可以是屏幕输出和文件输出两种方式）项目要求：1此项目是属于比较容易的项目，需要每个人独立完成。2 对于控制台界面的输入需要增加容错能力，对于输入给出完整的提示信息，使得操作者能够轻松操作；3 对输出的结果进行一定的美化，做到内容清晰、易懂；主要技术点：最小生成树、Prim 算法、 Kruskal 算法。团队配置：1 人。题目七、关键路径问题难度：易问题描述： 当一项工程划分为若干个子任务或活动后，人们不仅需要确定这些活动的先后次序，而且需要进一步计算完成整个工程的时间，确定哪些活动是影响工程进度的关键活动，以便合理地组织人力、物力、财力，加快这些活动的进

18、度，为按时或提前完成整个工程提供保证，这就是关键路径问题。关键路径问题相应的网称为AOE 网，其中：顶点表示事件，边表示活动，边上的权表示活动持续的时间。基本要求：（1）对一个描述工程的AOE 网，建立其存储结构； （注：数据的输入可以是键盘输入或文件输入两种方式）（2）判断该AOE 网是否能够顺利进行。（3）若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。（注：结果的输出可以是屏幕输出和文件输出两种方式）项目要求：1对于控制台界面的输入需要增加容错能力，对于输入给出完整的提示信息，使得操作者能够轻松操作；2对输出的结果进行

19、一定的美化，做到内容清晰、易懂；主要技术点：AOE 网、关键活动的最早发生时间、最迟发生时间。团队配置：2 人。三、游戏类题目八、 .迷宫问题难度：难问题描述：用一个字符类型的二维数组表示迷宫，数组中的每个元素表示一个小方格，取值“0” （通道）或“ 1” （阻塞物）。设计一个模拟小老鼠走迷宫的程序，为小老鼠寻找一条从迷宫入口到迷宫出口的途径小方格最少的最短通路。基本要求：（1）用随机函数设置迷宫；（2）选择合适的数据结构表示迷宫。（3）迷宫入口处的下标是（x0，y0） ，出口处的下标是（x1,y1） ，由键盘输入。（4）输出从入口到出口的最短通路（如存在）或不存在通路的信息。名师资料总结 -

20、 - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 项目要求：1人机交互界面友好，对用户的非法输入要有一定的判断及提示；2在很好完成必做模块的前提下，如又实现了选做模块，将给团队和相应个人加分；主要技术点：数组，队列，链表。团队配置：3 人题目九、 .马踏棋盘问题难度：难问题描述：将马随机放在国际象棋的8*8 棋盘 Board88 的某个方格中， 马按走棋规则进行移动，要求每个方格上只进入一次，走遍棋盘上全部64 个方格。基本要求：（1）采用图形界

21、面实现该游戏。（2）从键盘输入马的初始位置。（3）编制程序，求出马的行走路线，并按求出的行走路线，将数字1， 2，, ， 64依次填入一个8* 8 的方阵，并输出之。实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋 )使用。项目要求：1人机交互界面友好，对用户的非法输入要有一定的判断及提示；2在很好完成必做模块的前提下，如又实现了选做模块，将给团队和相应个人加分；主要技术点：数组，队列，链表。团队配置：3人题目十、连同成分标记问题难度：难问题描述：在一个只有0 和 1 的二维数组中， 实现自动标定出连接在一起的1 对应的区域， 给出区域编号并计算出这样的区域的数量。基本要求：（1）采用图形界面实现该游戏。（2）采用随机或文件的方式设置0,1 的位置。（3）编制程序，给出求解中的每一步的演示。项目要求：1人机交互界面友好，对用户的非法输入要有一定的判断及提示；2在很好完成必做模块的前提下，如又实现一些功能的扩展，将给团队和相应个人加分；主要技术点：数组，队列，文件。团队配置：3 人名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -