2022年62《数据结构》课程设计任务书.docx

《2022年62《数据结构》课程设计任务书.docx》由会员分享，可在线阅读，更多相关《2022年62《数据结构》课程设计任务书.docx（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、精品学习资源1006402 数据结构课程设计任务书一、 设计目的1. 明白并把握数据结构与算法的设计方法，具备初步的独立分析和设计才能；2. 初步把握软件开发过程的问题分析、系统设计、程序编码测试等基本方法和技能；3. 提高综合运用所学的理论学问和方法独立分析和解决问题的才能；4. 训练用系统的观点和软件开发一般规范进行软件开发，培育软件工作者所应具备的科学的工作方法和作风；数据结构是一门实践性较强的软件基础课程，为了学好这门课程，必需在把握理论学问的同时，加强上机实践；本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够依据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题

2、在运算机内部表示出来，并培育基本的、良好的程序设计技能；二、 设计地点湖南城市学院试验楼运算机房 407三、 设计时间2021 年 6 月 4 日 6 月 8 日四、 设计分组 54 人五、指导老师： 陈强 莫照六、设计课题：1表达式翻译要求：编写完整程序 ,将不包含括号的算术中缀表达式翻译成后缀表达式.输入 :中缀表达式,80 个字符以内 .输出: 转换后的后缀表达式 .要求 :界面友好 ,函数功能要划分好2超市选址问题设计要求：对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同；请为超市选址，要求实现总体最优；3. 串的查找和替换输入或打开一篇英文文章，在该文章中

3、找出全部给定的单词，然后对全部给定的单词替换为另外一个单词；4. 地图着色问题设计要求：已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少；5. 二叉排序树的实现用次序和二叉链表作储备结构1以回车 n为输入终止标志 ,输入数列 L，生成一棵二叉排序树T；2对二叉排序树 T 作中序遍历，输出结果；3输入元素 x, 查找二叉排序树 T,如存在含 x 的结点 ,就删除该结点 ,并作中序遍历 执行操作2；否就输出信息 “无 x ”；6. 二叉树的遍历问题二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现， 应包含建树的实现；要求：遍历的内容应是

4、千姿百态的；7. 飞机售票系统任务：通过此系统可以实现如下功能： 录入：欢迎下载精品学习资源可以录入航班情形数据可以储备在一个数据文件中，数据结构、详细数据自定） 查询：可以查询某个航线的情形如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情形；订票： 订票情形可以存在一个数据文件中，结构自己设定） 可以订票，假如该航班已经无票，可以供应相关可挑选航班； 退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情形，订单要有编号；修改航班信息：当航班信息转变可以修改航班数据文件要求：依据以上功能说明，设计

5、航班信息，订票信息的储备结构，设计程序完胜利能；8. 敢死队问题有 M 个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长打算用轮回数数的方法来打算哪个战士去执行任务；假如前一个战士没完成任务，就要再派一个战士上去；现给每个战士编一个号，大家围坐成一圈，任凭从某一个战士开头计数，当数到5 时，对应的战士就去执行任务，且此战士不再参与下一轮计数；假如此战士没完成任务，再从下一个战士开头数数，被数到第5 时，此战士接着去执行任务；以此类推，直到任务完成为止；排长是不情愿去的，假设排长为1 号，请你设计一程序，求出从第几号战士开头计数才能让排长最终一个留下来而不去执行任务；要求：至少采纳两种不同的数据结

6、构的方法实现；假如采纳三种以上的方法者，可加分；9. 哈夫曼编码转码器利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本；但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码 复原）；对于双工信道即可以双向传输信息的信道），每端都需要一个完整的编 /译码系统；试为这样的信息收发站写一个哈夫曼编/译码系统； 基本要求 一个完整的系统应具有以下功能：1） I：初始化 Initialization ）；从终端读入字符集大小n，以及 n个字符和 n 个权值，建立哈夫曼树，并将它存于文件hfmTree 中；2） E：编码 Encoding ）

7、；利用已建好的哈夫曼树如不在内存，就从文件htmTree 中读入），对文件 ToBeTran 中的正文进行编码，然后将结果存入文件CodeFile 中；3） D：译码 Decoding ）；利用已建好的哈夫曼树将文件CodeFile 中的代码进行译码，结果存入文件 TextFile 中；4） P：印代码文件 Print ）；将文件 CodeFile 以紧凑格式显示在终端上，每行50 个代码；同时将此字符形式的编码写入文件CodePrint 中；5） T：印哈夫曼树 TreePrinting ）；将已在内存中的哈夫曼树以直观的方式树或凹入表欢迎下载精品学习资源形式）显示在终端上，同时将此字符形式

8、的哈夫曼树写入文件TreePrint 中； 测试数据 1）数据一：已知某系统在通信联络中只可能显现8 种字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11, 以此设计哈夫曼编码；利用此数据对程序进行调试；2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码： “THISPROGRAMISMYFAVORITE” ； 实现提示 1）文件 CodeFile 的基类型可以设为子界型bit=0.1 ；2）用户界面可以设计为 “菜单 ”方式：显示上述功能符号，再加上 “ Q，”表示运行 Quit；请用户键入一个先把功能符，些功能执

9、行完毕后再经菜单，直至某次用户先把了 “E”为止；能比较快速地找到储户的帐户，以实现存款、取款记账；2能比较简洁，快速地实现插入和删除，以实现开户和销户的需要；12. 简洁的职工治理系统1. 问题描述对单位的职工进行治理，包括插入、删除、查找、排序等功能；2. 要求职工对象包括姓名、性别、诞生年月、工作年月、学历、职务、住址、电话等信息；1）新增一名职工：将新增职工对象按姓名以字典方式职工治理文件中；2）删除一名职工：从职工治理文件中删除一名职工对象；3）查询：从职工治理文件中查询符合某些条件的职工；4）修改：检索某个职工对象，对其某些属性进行修改；5）排序：按某种需要对职工对象文件进行排序；

10、3.实现提示职工对象数不必许多，便于一次读入内存，全部操作不经过内外存交换；1）由键盘输入职工对象，以文件方式储存；程序执行时先将文件读入内存；2）对职工对象中的 姓名 按字典次序进行排序；具有图形菜单界面；2查找，替换 等长，不等长），插入 插串，文本块的插入）、块移动可正确存盘、取盘；4正确显示总行数；14. 教案方案编制问题高校的每个专业都要制定教案方案；假设任何专业都有固定的学习年限，每学年含两学欢迎下载精品学习资源期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设时间的支配必需满意先修关系；每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有；

11、每门课恰好占一个学期；试在这样的前提下设计一个教案方案编制程 序； 基本要求 、学分和直接先修课的课程号；2）答应用户指定以下两种编排策略之一：一是使同学在各学期中的学习负担尽量匀称； 二是使课程尽可能地集中在前几个学期中；老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；2迷宫的墙足够牢固，老鼠不能穿墙而过；3正确检测结果，如老鼠在规定时间内走到粮仓处，提示胜利，否就提示失败；4添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；5找出走出迷宫的全部路径，以及最短路径；利用序列化功能实现迷宫地图文件的存盘和读出等功能17. 利用栈求表达式的值编写程序实现表达式求值，即验证某算术表达式的正

12、确性，如正确，就运算该算术表达式的值；主要功能描述如下：1、从键盘上输入表达式；2、分析该表达式是否合法：1）是数字，就判定该数字的合法性；如合法，就压入数据到堆栈中；2）是规定的运算符，就依据规章进行处理；在处理过程中，将运算该表达式的值； ：初始化堆栈intMake_str ：语法检查并运算intpush_operateintoperate ：将操作码压入堆栈intpush_numdoublenum ：将操作数压入堆栈intprocedeintoperate ：处理操作码intchange_opndintoperate ：将字符型操作码转换成优先级intpush_opndintoperat

13、e ：将操作码压入堆栈intpop_opnd ：将操作码弹出堆栈intcaculateintcur_opnd ：简洁运算 +，- ，* ， / doublepop_num ：弹出操作数18. 利用栈求表达式的值随机产生 n 个题目，题目涉及加减乘除和带括号的混合运算；要求：有交互菜单；指定键随时终止练习；将全部的练习题和答案及对错评判输出到文件备查；按对错的比例，给出“优”、“良”、“中”、“仍需努力”的评判；19. 排序综合利用随机函数产生N 个随机整数 至少采纳三种方法实现上述问题求解统计每一种排序方法的性能假如采纳 4 种或 4 种以上的方法者，可适当加分；20. 任意长的整数加法设计一

14、个程序实现两个任意长的整数的求和运算；要求：利用双向循环链表，设计一个实现任意长的整数进行加法运算的程序，要求输入和输出每四位一 组，组间用逗号隔开；如1,0000,0000,0000,0000 ；21. 散列表的设计与实现欢迎下载精品学习资源设计散列表实现电话号码查找系统；【基本要求】1设每个记录有以下数据项：电话号码、用户名、地址；2从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3采纳肯定的方法解决冲突；4查找并显示给定电话号码的记录；5查找并显示给定用户名的记录；【进一步完成内容】1系统功能的完善；2设计不同的散列函数，比较冲突率；3在散列函数确定的前提下，尝试各种不同类型

15、处理冲突的方法，考察平均查找长度的变化；22. 散列法的试验讨论散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同；两者是影响查询算法性能的关键因素；对于几种典型的散列函数构造方法，做试验观看，不同的解决冲突方法对查询性能的影响；23. 树的应用实现树与二叉树的转换的实现；以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现；24. 树与二叉树的转换的实现树与二叉树的转换的实现，以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现；多种遍历可以只实现一个 ；25. 数制转换问题任意给定一个 M 进制的

16、数 x，请实现如下要求1求出此数 x 的 10 进制值 实现对 x 向任意的一个非 M 进制的数的转换；3至少用两种或两种以上的方法实现上述要求 和 Bnx.Amx=A0+A1x1+A2x2+A3x3+ +Amxm Bnx=B0+B1x1+B2x2+B3x3+ +Bnxn请实现求 Mx=Amx+Bnx、Mx=Amx-Bnx和 Mx=Amx Bnx ；要求：1第一判定多项式是否稀疏2分别采纳次序和动态储备结构实现；3结果 Mx 中无重复阶项和无零系数项；4要求输出结果的升幂和降幂两种排列情形27. 宿舍治理查询软1任务：为宿舍治理人员编写一个宿舍治理查询软件,程序设计要求：A. 采纳交互工作方式

17、B. 建立数据文件，数据文件按关键字欢迎下载精品学习资源2查询菜单 : 用二分查找实现以下操作A. 按姓名查询B. 按学号查询C. 按房号查询3打印任一查询结果 排序的功能，并分别用冒泡、选择、插入排序实现；实现查找按姓名、学号、房号，采纳二分查找算法实现；有交互菜单，用户不挑选退出时可以连续操作；29. 通讯录的制作模块要求：第一个模块 主函数 main 的功能是：依据选单的选项调用各函数，并完成相应的功能；其次个模块 Menu 的功能是：显示英文提示选单；第三个模块 Quit 的功能是：退出选单；第四个模块 Create的功能是：创建新的通讯录；第五个模块 Add 的功能是：在通讯录的末尾

18、，写入新的信息，并返回选单；第六个模块 Find 的功能是：查询某人的信息，假如找到了，就显示该人的信息，假如未找到，就提示通讯录中没有此人的信息，并返回选单；第七个模块 Alter 的功能是：修改某人的信息，假如未找到要修改的人，就提示通讯录中没有此人的信息，并返回选单；第八个模块 Delete 的功能是：删除某人的信息，假如未找到要删除的人，就提示通讯录中没有此人的信息，并返回选单；第九个模块 List 的功能是：显示通讯录中的全部记录；设计要求：1每条信息至包含：姓名 、电话 TEL ）、城市 CITY ）邮编作为一个完整的系统，应具有友好的界面和较强的容错才能30. 图的遍历和最小生成

19、树求解实现要求：1先任意创建一个图；2图的 DFS,BFS 的递归和非递归算法的实现3最小生成树 要求用邻接矩阵、邻接表、十字链表多种结构储备实现31. 图书治理系统设计一个运算机治理系统完成图书治理基本业务；【基本要求】1每种书的登记内容包括书号、书名、著作者、现存量和库存量；2对书号建立索引表 系统主要功能如下：欢迎下载精品学习资源* 采编入库：新购一种书，确定书号后，登记到图书帐目表中，假如表中已有，就只将库存量增加；* 借阅：假如一种书的现存量大于0，就借出一本，登记借阅者的书证号和归仍期限，转变现存量；* 归仍：注销对借阅者的登记，转变该书的现存量；【进一步完成内容】1系统功能的进一

20、步完善；2索引表采纳树表；3设计内容4程序流程图5源程序6软件测试报告 图书治理 增加图书、查询图书、删除图书、图书借阅、仍书；2会员治理 增加会员、查询会员、删除会员、借书信息；33. 文章编辑功能：输入一页文字，程序可以统计出文字、数字、空格的个数；静态储备一页文章，每行最多不超过80 个字符，共 N 行；要求 1）分别统计出其中英文字母数和空格数及整篇文章总字数；2）统计某一字符串在文章中显现的次数，并输出该 次数； 3）删除某一子串，并将后面的字符前移；储备结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范畴：可以输入大写、小写的英文字母、任何数字及标点符号；输出形式：

21、 1）分行输出用户输入的各行字符；2 ）分 4 行输出 全部字母数 、 数字个数 、 空格个数 、 文章总字数 3 ）输出删除某一字符串后的文章； 34稀疏矩阵的实现和应用基本功能要求：稀疏矩阵采纳三元组表示，求两个具有相同行列数的稀疏矩阵 A 和 B 的相加矩阵 C，并输出 C；求出 A 的转置矩阵 D，输出 D ；测试数据：35. 稀疏矩阵实现与应用要求：实现三元组、十字链表下的稀疏矩阵的加、转、乘的实现；36. 线索二叉树的应用要求实现线索树建立、插入、删除、复原线索的实现；37. 校内导航问题设计要求：设计你的学校的平面图，至少包括10 个以上的场所，每两个场所间可以有不同的路，且路长

22、也可能不同，找出从任意场所到达另一场所的正确路径,现要开一个舞会 .男女生分别编号坐在舞池的两边的椅子上 .每曲开头时 ,依次从男生和女生中各出一人配对跳舞,本曲没胜利配对者坐着等待下一曲找舞伴 .请设计一系统模拟动态地显示出上述过程,要求如下 :1输出每曲配对情形2运算出任何一个男生 编号为 X 和任意女生 编号为 Y, 在第 K 曲配对跳舞的情形.至少求出 K 的两个值 .3尽量设计出多种算法及程序,可视情形适当加分提示 :用队列来解决比较便利 40学校超市选址问题设计要求：对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同；请为超市选址，要求实现总体最优；41.

23、 一元多项式的四就运算的实现次序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现；设有一元多项式Amx 和 Bnx.Amx=A0+A1x1+A2x2+A3x3+ +AmxmBnx=B0+B1x1+B2x2+B3x3+ +Bnxn请实现求 Mx=Amx+Bnx、Mx=Amx-Bnx和 Mx=Amx Bnx ；要求：1第一判定多项式是否稀疏2分别采纳次序和动态储备结构实现；3结果 Mx 中无重复阶项和无零系数项；4要求输出结果的升幂和降幂两种排列情形42. 一元稀疏多项式运算器要求：设计一个一元多项式加法器.输入并建立多项式；两个多项式相加；输出多项式:n,c1,e1,c2,e2,cn,e

24、其n,中 ,n 是多项式项数 ,ci 和 ei 分别是第 i 项的系数和指数 ,序列按指数降序排列 .运算多项式在 x 处的值43. 约瑟夫环编号为 1，2， n；的 n 个人按顺时针方向围坐一圈，每人持有一个密码正整数）；一开头任意给定一个正整教作为报数上限值m，从第一个人开头按顺时针方向自1 开头次序报数，报到 m 时停止报教；报m 的人出列；将他的密码作为新的m 值从他在顺时针方向上的下一个人开头重新从1 报数，如此下去，直至全部人全部出列为止；设计一个程序求出出列次序；44. 运动会分数统计欢迎下载精品学习资源任务：参与运动会有n 个学校，学校编号为1n；竞赛分成 m 个男子工程，和

25、w 个女子工程；工程编号为男子1m，女子 m+1 m+w；不同的工程取前三名积分，积分分别为： 5、 3、2；m=20,n可以输入各个工程的前三名的成果；2能统计各学校总分，3可以按学校编号或名称、学校总分、男女团体总分排序输出；4可以按学校编号查询学校某个工程的情形；可以按工程编号查询取得前三名的学校；5数据存入文件并能随时查询6规定：输入数据形式和范畴：可以输入学校的名称，运动工程的名称输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，依据提示，可以完成相关的功能要求；储备结构：同学自己依据系统功能要求自己设计，但是要求运动会的相关数据要储备在数据文件中；

26、 老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；2迷宫的墙足够牢固，老鼠不能穿墙而过；3正确检测结果，如老鼠在规定时间内走到粮仓处，提示胜利，否就提示失败；4添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；5找出走出迷宫的全部路径，以及最短路径；利用序列化功能实现迷宫地图文件的存盘和读出等功能47. 最小生成树问题设计要求：在 n 个城市之间建设网络，只需保证连通即可，求最经济的架设方法；储备结构采纳多种；求解算法多种；48. 同学成果治理系统现有同学成果信息文件11.txt ），内容如下姓名学号语文数学英语张明明01677882 李成友 02789188 张辉灿 03688256

27、 王露 04564577陈东明 05673847.同学成果信息文件2实现对两个文件数据进行合并,生成新文件 3.txt2抽取出三科成果中有补考的同学并储存在一个新文件4.txt3对合并后的文件 3.txt 中的数据按总分降序排序至少采纳两种排序方法实现欢迎下载精品学习资源4输入一个同学姓名后 ,能查找到此同学的信息并输出结果 至少采纳两种查找方法实现5要求使用结构体,链或数组等实现上述要求.6采纳多种方法且算法正确者,可适当加分；49. 人事治理系统：每个员工的信息包括：编号、姓名、性别、诞生年月、学历、职务、电话、住址等；以二叉排序树形式储备员工信息，完成员工信息的查询、更新、插入、删除等功

28、能；功能要求： 1查询：按特定条件查找员工；2 更新：按编号对某个员工的某项信息进行修改；3 插入：加入新员工的信息；4 删除：按编号删除已离职的员工的信息50. 猴子选大王任务：一堆猴子都有编号，编号是1， 2，3 .m ,这群猴子 m 个）依据 1- m 的次序围坐一圈，从第1 开头数，每数到第N 个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最终一只猴子，就该猴子为大王；要求：输入数据：输入m,n； m,n为整数， n，最终输出为大王的猴子的编号；建立一个函数来实现此功能 51商店存货治理系统功能：建立一商店存货治理系统，要求每次出货时取进货时间最早且最接近保质期中止时间的货物；分

29、步实施：1.初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2.完成最低要求：建立一个文件，包括5 个种类的货物情形，能对商品信息进行扩充 字符串采纳数组储备，建立两个字符串String1 和String2 ；输出两个字符串； 2 将字符串 String2 的头 n 个字符添加到 String1 的尾部；输出结果； 3查找串 String3 在串 String1 中的位置，如String3 在 String1 中不存在，就插入String3在String1中的 m位 置 上 ； 输 出 结 果 ； 测 试数 据 ： 1String1:“typedefstructArcBox”St

30、ring2: String3:“ VertexTypedata“ data”n:6,m:72String1:String2:“structArcBox”“ VertexType”String3:“ Box”n:3,m:353. 利用 Hash 技术统计 C 源程序中关键字的频度扫描一个 C 源程序，用 Hash 表储备该程序中显现的关键字，并统计该程序中的关键字显现的频度；用线性探测法解决 Hash 冲突；设 Hash 函数为： HashKey=Key 的首字母序号 *100+Key 的尾字母序号 Mod 41；关键字 39 个，现要开一个舞会；男女生分别编号坐在舞池的两边的椅子上；每曲开头时，依次从男生和女生中各出一人配对跳舞，本曲没胜利配对者坐着等待下一曲找舞伴；请设计一系统模拟动态地显示出上述过程, 要求如下：输出每曲配对情形运算出任何一个男生编号为X 和任意女生 编号为Y ，在第 K 曲配对跳舞的情形；至少求出K 的两个值；尽量设计出多种算法及程序,可视情形适当加分； 提示:用队列来解决比较便利欢迎下载精品学习资源欢迎下载