2022年数据结构实训任务书 .pdf

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

1、数据结构课程实训任务书学期： 20122013 年第二学期班级：计科 11、软工 11时间：十九 -二十周机房：博学楼， 70X 实验室名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 10 页 - - - - - - - - - 一、目的和要求1、进一步掌握常用算法的思想及实现；2、进一步理解和运用结构化程序设计的思想和方法3、初步掌握开发一个小型实用系统的基本方法4、掌握调试中小程序的基本方法5、掌握流程图的表示方法6、掌握书写程序设计开发文档的能力7、锻炼和提高查找资

2、料和自学能力8、从 “ 二、设计任务” 中选择一个项目来完成，用C 语言实现，系统的各个功能模块要求用函数的形式实现。以小组为单位进行。小组人数以34 人为宜。9、强调独立完成，强调实际成果；重视软件测试，重视文档写作。10、课程实训结束后，每人要求提供以下电子文档：1） 每组提交一份源程序文件2） 没人提交一份实训报告。实训报告的具体格式参考“ 三、课程设计报告格式” 。每组同学根据自己在小组中的任务不同，完成自己的模块的相关任务书。3） 每组一个演示文稿，答辩使用。11、答辩以小组为单位，按照提交次序按组答辩。二、设计任务课题一：宿舍管理查询系统1)任务：为宿舍管理员编写一个宿舍管理查询系

3、统2) 程序要求A、采用交互工作方式（键盘、鼠标均可，控制台或者图形界面均可）B、建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序（冒泡、选择、插入、快速排序任选一种）C、用二分查找实现以下操作：按姓名查询、按房号查询、按学号查询D、打印任一查询结果课题二：各种排序算法时间性能的比较1) 问题描述对各种排序方法（直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序）的时间性能进行比较。2) 基本要求(1) 设计并实现上述各种排序算法；(2) 产生正序和逆序的初始排列分别调用上述排序算法，并比较时间性能；(3) 产生随机的初始排列分别调用上述排序算法，并比较时间性

4、能。3) 设计思想上述各种排序方法都是基于比较的内排序，其时间主要消耗在排序过程中进行的记录的比较次数和移动次数，因此，统计在相同数据状态下不同排序算法的比较次数和移动次数，即可实现比较各种排序算法的目的。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 10 页 - - - - - - - - - 直接插入排序、起泡排序、直接选择排序在教材中已经实现，请仿照教材中的方法在其他排序算法中的适当位置插入计数器统计元素的比较次数和移动次数。【思考题】 如果测算每种排序算法所用实

5、际的时间，应如何修改排序算法？课题三：哈夫曼编码1) 问题描述设某编码系统共有n 个字符，使用频率分别为w1, w2, , wn，设计一个不等长的编码方案，使得该编码系统的空间效率最好。2) 基本要求(1) 在文件中存储一系列字符代码；(2) 编写程序分析文件中各个字符以及每个字符出现的频率；(3) 将各个字符及其频率分析成结点以及结点的权值，构造哈弗曼树。(4) 分析构造的哈夫曼树，列出相应的哈弗曼编码(5) 把生成的编码替换原文件中的字符，并将结果存储到文件中3) 设计思想可参考树章节例题haffuman.c 课题四：文章编辑1)问题描述输入一页文字，程序可以统计出文字、数字、空格的个数。

6、2) 基本要求静态存储一页文章，每行最多不超过80 个字符，共N 行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。（4）替换字符串（5）可以保存到文件中，也可以在文件中打开3) 设计思想定义一个串，可使用顺序串或者链表串。实现串的插入、删除、修改、替换、遍历等功能。并能够把串保存在文件中。可以通过打开文件和保存文件，将文件中的信息载入到串中，或者将串中的信息保存到文件中。具体可参考线性表的操作实例。以及书上串章节。课题五：校园导游程序1)问题描述名师资料总结 - - -精品资料欢迎下载

7、 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 10 页 - - - - - - - - - 用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。2)基本要求（1） 查询各景点的相关信息；（2） 查询图中任意两个景点间的最短路径。（3） 能够将图的信息保存到文件中，并指定文件打开。（4） 增加、删除、更新有关景点和道路的信息。附加难度：有余力的同学可以考虑用图形界面实现寻址的过程3

8、) 设计思想核心数据结构定义一个图，将图保存后，对图进行面向指定节点到各个节点的最短路径的操作。可以再文件中保存多个导游图，例如保存学校图、芜湖市图等文件。开始时选择文件，将指定文件中的信息导入到内存的图中。课题六：宾馆订房系统1）问题描述一般宾馆日常业务包括：订房、退房、改房间号、续房等操作；2）基本要求拟定出相应的需求；设计出相应的数据结构，需要考虑房间的增减；需考虑押金的收取和退还；需考存储订房用户的基本信息；需考虑房间类型的不同，价格的不同；课题七：宿舍管理软件1)问题描述设某宿舍有四层楼，每层楼有30 个房间，每个房间有4 个床位。每个房间还有四张床、四个书桌、四个凳子、两个灯、两个

9、风扇等基础设置。要求设计一个宿舍管理软件。实现对宿舍人员和基本设施的管理工作。2) 基本要求学生管理部分：(1) 学生的入住处理；(2) 学生退房处理；(3) 输出所有学生入住信息(按房间号和床号有序)；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 10 页 - - - - - - - - - 搜索并输出单个学生的基本信息(学号，姓名，班级，年龄，宿舍等信息)。搜索并输出某个宿舍的所有同学的基本信息(4) 修改学生基本信息(班级，年龄等 )；(5) 学生调换宿舍或床位处

10、理（在查询两个宿舍的基本设备没有故障的前提下，才准许调换宿舍）；宿舍设备管理部分：(1) 基本设备的保修以及修理信息（2）根据宿舍查询基本设施(3) 根据宿舍查询基本设施是否完备(4) 可以搜索查询所有的故障设备3) 设计思想可以建立两组线性表，分别是学生信息和宿舍信息。信息表的内容均存于文件中。当程序运行最初，需要对宿舍进行全面初始化，也就是宿舍的所有基础设施完备。然后在使用过程中，可以对学生和对基本设施进行操作和管理。课题八：机票管理系统1)问题描述一机场每天有n 个航班，每个班次都有一班次号（1、2、3n ），固定的起飞时间，固定的路线（起始站、终点站），大致的飞行车时间，固定的额定载客

11、量。如班次起飞时间起点站终点站飞行时间额定载量已定票人数是否起飞1 8:00 天津汉口2 145 130 未2 6:30 天津成都0.5 140 140 已3 7:00 天津成都0.5 140 120 已4 10:00 天津成都0.5 140 120 未试设计一个机票管理系统，对机场的售票情况进行管理。2) 基本要求功能要求：（1）录入班次信息(信息用文件保存),可不定时地增加班次数据；（2）浏览班次信息,可显示出所有班次当前状况(如果当前系统时间超过了某班次的起飞时间 ,则显示 “ 此班已发出 ” 的提示信息 )。（3）查询路线：可按班次号查询,可按终点站查询；（4）售票和退票功能A：当查询

12、出已定票人数小于额定载量且当前系统时间小于起飞时间时才能售票，自动更新已售票人数名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - - - - - - B：退票时，输入退票的班次，当本航班飞机未发出时才能退票，自动更新已售票人数。（5）订票和退票都可提前十天的操作（6）由于数据量较大，要再文件中保存3) 设计思想定义一组线性表，专门存储航班的基本信息，包括航班号、起点、终点、时间、总人数等信息。课题九：学生成绩系统1) 问题描述使用下面的数据，设计一

13、个简单的成绩管理系统，实现出最基本的功能。学生基本信息文件(A.TXT) 及其内容： A.TXT 文件不需要编程录入数据，可用文本编辑工具直接生成学号姓名性别宿舍号码电话号码01 张成成男501 87732111 02 李成华女101 87723112 03 王成凤女101 87723112 04 张明明男502 87734333 . . .学生成绩基本信息文件(B.TXT) 及其内容：学号课程编号课程名称学分平时成绩实验成绩卷面成绩综合成绩实得学分01 A01 大学物理3 66 78 82 02 B03 高等数学4 78 -1 90 01 B03 高等数学4 45 -1 88 02 C01

14、VF 3 65 76 66 . . . . 2) 基本要求功能要求及说明：(1) 数据录入功能: 对 B.TXT 进行数据录入 ,只录入每个学生的学号、课程编号、课程名称、学分、平时成绩、实验成绩、卷面成绩共7 个数据 . 综合成绩、学分由程序根据条件自动运算。综合成绩的计算:如果本课程的实验成绩为-1，则表示无实验，综合成绩=平时成绩*30%+ 卷面成绩 *70%; 如果实验成绩不为-1,表示本课程有实验,综合成绩 =平时成绩 *15%+实验成绩 *.15%+ 卷面成绩 *70% . 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

15、 - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - - - - - - 实得学分的计算: 采用等级学分制. 综合成绩在90-100 之间,应得学分 =学分 *100% 综合成绩在70-90 之间 ,应得学分 =学分 *80% 综合成绩在60-70 之间 ,应得学分 =学分 *65% 综合成绩在60 以下,应得学分 =学分 *0% （2）删除功能：当在A.TXT 中删除一个学生时，自动地在B.TXT 中删除此人所有信息。（3）排序功能：能实现选择按综合成绩或实得学分升序或降序排序并显示数据。（4）查询功能：分为学生基本情况查询和成绩查询两种A：学生基本情况查

16、询：A1- 输入一个学号或姓名（可实现选择），查出此生的基本信息并显示输出。A2- 输入一个宿舍号码，可查询出本室所有的学生的基本信息并显示输出。B：成绩查询：B1：输入一个学号时，查询出此生的所有课程情况，格式如下：学号： xx 姓名： xxxxx 课程编号： xxx 课程名称： xxxxx 综合成绩： xxxx 实得学分 : xx 课程编号： xxx 课程名称： xxxxx 综合成绩： xxxx 实得学分 : xx 课程编号： xxx 课程名称： xxxxx 综合成绩： xxxx 实得学分 : xx 共修： xx 科，实得总学分为: xxx 课题十：单项选择题标准化考试系统1)问题描述设计

17、一单项选择题标准化考试系统，实现考试的标准化管理。2) 基本要求功能要求：用文件保存试题库。（每个试题包括题干、4 个备选答案、标准答案）试题录入：可随时增加试题到试题库中试题抽取：每次从试题库中可以随机抽出N 道题（ N 由键盘输入）答题：用户可实现输入自己的答案自动判卷：系统可根据用户答案与标准答案的对比实现判卷并给出成绩。注意：在 C 语言中产生随机数的方法：使用随机数函数在使用随机数函数random()之前，应包含文件#include 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -

18、- 第 7 页，共 10 页 - - - - - - - - - 然后使用下述函数初始化：randomize();/* init the random number generator */ 以后就可以直接使用random()函数来产生需要的数据：如果需要产生10 以内的数，使用random(10) 就可以了；产生100 以内的数，使用random(100)就可以了。在 C+中，产生随机数：#include #include 然后srand(time(0); / 以当前时间当做随机种子rand(); /产生一个位于0-32767 之间的随机数课题十一：停车场模拟系统1)问题描述模拟一个停车场系

19、统。停车场根据停车的占地面积进行收费。我们假设一个停车场存在大、中、小三种车型的停车位。当有车辆进入停车场时，登记车的型号，车牌以及时间，并将车停放在停车场内。当取车时，输入车牌号，取出相应的车，并记录现在时间，根据停车时间收取费用。当停车场满时，在停车场外的一个长度为N 的候车道等待进入停车场停车。2) 基本要求数据结果推荐：1）推荐用二维数组描述停车场的结构2）推荐用队列描述候车道的结构功能要求：用文件保存停车场和候车道的基本数据停车：可选择车位，输入车牌号，将车的基本信息存入车位中取车：输入车牌，获取时间，计算费用查询：在停车时，可以查询停车场的整体情况空位提示：一旦取车后停车场出现空位

20、，需要将今夕传递给候车道。候车道队列出列满位提示：一旦停车厂位满，则需要再候车道停车，即候车道入队列。附加难度：有余力的同学可以考虑用图形界面实现停车场的状态显示课题十二：图书管理系统1)问题描述名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 10 页 - - - - - - - - - 设计一个系统，对图书信息进行管理，信息描述：有关该系统基本信息的描述，如：图书名称、图书编号、单价、作者、存在状态、借书人姓名、性别、学号等。2) 基本要求基本功能：1、新进图书基本信息

21、的输入。2、图书基本信息的查询。3、对撤消图书信息的删除。4、为借书人办理注册。5、办理借书手续（非注册会员不能借书）。6、办理还书手续。7、统计图书库存、已借出图书数量。课题十三：单词学习辅助系统1)问题描述设计一个系统，可以实现单词背诵辅助功能。系统提供单词的基本信息的输入，和管理功能，管理员用户可以对单词进行输入、删除、修改等操作，并将单词存储在文件中。普通用户进入系统后可以浏览单词，可以进行测试，然后根据输入与测试打分。在排行榜上记录分数前十名的成绩、姓名、时间等信息。2) 基本要求基本功能：1、单词的输入与管理2、单词的修改删除等操作3、单词的分组浏览与查询4、单词的抽题测验5、分值

22、排行榜的实现课题十四：数据结构管理程序1)问题描述请同学们为你们的数据结构老师制作一份课程分数管理软件。我们的课程一学期假设要留5 次作业，每次老师要进行批改，给出分数后还要进行登记。学期期末要根据每次作业的成绩计算出最终的平时成绩（满分100）。学期末期末考试结束后录入期末成绩，按后按照平时成绩与期末成绩的3:7 的比例计算最终成绩。2) 基本要求（该程序应该具有下列功能）：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 10 页 - - - - - - - - - (

23、1) 首先创建班级，并将班级的信息存入到文件中。(2) 当录入成绩时，首先录入平时成绩1，用户将同学们的平时成绩1逐个录入。(3) 给定某个班级的班号，显示该班所有学生的作业完成情况；(4) 给定某位学生的学号，修改该学生的作业完成信息；(5) 给定某位学生的学号，删除该学生的信息；(6) 查询所有作业为0 分的同学(7) 输入期末成绩后计算最终成绩(8) 按学生的最终成绩进行排序；(9) 可以分别输出所有优秀、良好、中等、及格、不及格的名单一、评分标准1、积极参与课程实训，按质按量完成课程实训要求。2、出勤情况，占20%. 3、在项目开发过程中完成的工作量，占30%. 4、对开发的项目涵盖的知识点的掌握情况，占40%。5、项目中有新功能或创意，占10%。二、报告格式另见模版文件名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 10 页 - - - - - - - - -