62《数据结构》课程设计任务书

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

2、机内部表示出来，并培养基本的、良好的程序设计技能。二、设计地点 湖南城市学院实验楼计算机房 407三、设计时间2018年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二叉树的遍历问题 二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现， 应包含建树的实现。要求：遍历的内容应是千姿百态的。7飞机售票系统 任务：通过此系统

4、可以实现如下功能： 录入：1 / 12 可以录入航班情况 数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况 如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票 价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票： 订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；&敢

5、死队问题有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪 个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士 编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始 数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。要求：至少采用两种不同的数据结构的方法实现。如果采用三种以上的方法者，可加分。9 哈夫曼编

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

7、文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。宇符ACDEFGHIJ氏L频度186641322M210321154767153320N0FQPSTUVWXYZ频度57631514861eo2281811513） D：译码Decoding ）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。4） P:印代码文件Print ）。将文件 CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。5） T：印哈夫曼树TreePrinting ）。将已在内存中的哈夫曼树以直观的方式

8、树或凹入表2 / 12TreePrint 中。形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件 测试数据 1）数据一：已知某系统在通信联络中只可能出现8 种字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11, 以此设计哈夫曼编码。利用此数据对程序进行调试。 2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和 译码： “THIS PROGRAM IS MY FAVORITE” 。 实现提示 1）文件 CodeFile 的基类型可以设为子界型 bit=0.1 。2）用户界面可以设计为菜单”方式：显示上述功能符号，再加上

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

10、属性进行修改。5）排序：按某种需要对职工对象文件进行排序。3. 实现提示职工对象数不必很多，便于一次读入内存，所有操作不经过内外存交换。1）由键盘输入职工对象，以文件方式保存。程序执行时先将文件读入内存。 2）对职工对象中的 姓名 按字典顺序进行排序。具有图形菜单界面； 2查找，替换 等长，不等长） ，插入 插串，文本块的插入）、块移动 可正确存盘、取盘； 4正确显示总行数。14教案计划编制问题 大学的每个专业都要制定教案计划。假设任何专业都有固定的学习年限，每学年含两学3 / 12 期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程 在开设时间的安排必须满足先修关

11、系。每门课程有哪些先修课程是确定的，可以有任意多 门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教案计划编制程 序。基本要求、学分和直接先修课的课程号。2 ）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。老鼠形象可辨认，可用键盘操纵老鼠上下左右移动； 2迷宫的墙足够结实，老鼠不能穿墙而过； 3正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败； 4添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙； 5找出走出迷宫的所有路径，以及最短路径。 利用序列化功能实现迷宫地图文件的存盘和读出等功能

12、 17利用栈求表达式的值编写程序实现表达式求值，即验证某算术表达式的正确性，若正 确，则计算该算术表达式的值。主要功能描述如下：1、从键盘上输入表达式。2、分析该表达式是否合法： 1)是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。 2)是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。 ：初始化堆栈 intMake_str( ：语法检查并计算 intpush_operate(intoperate ：将操作码压入堆栈 intpush_num(doublenum ：将操作数压入堆栈 intprocede(intoperate ：处理操作码 intchange_opn

13、d(intoperate ：将字符型操作码转换成优先级 intpush_opnd(intoperate ：将操作码压入堆栈 intpop_opnd( ：将操作码弹出堆栈 intcaculate(intcur_opnd ：简单计算 +，-，*， / doublepop_num( ：弹出操作数 18利用栈求表达式的值随机产生n个题目，题目涉及加减乘除和带括号的混合运算。要求：有交互菜单；指 定键随时终止练习；将所有的练习题和答案及对错评价输出到文件备查；按对错的比 例，给出“优”、“良”、“中”、“还需努力”的评价。19排序综合利用随机函数产生 N 个随机整数 至少采用三种方法实现上述问题求解 统

14、计每一种排序方法的性能 如果采用 4种或 4 种以上的方法者，可适当加分。 20任意长的整数加法设计一个程序实现两个任意长的整数的求和运算。要求：利用双向 循环链表，设计一个实现任意长的整数进行加法运算的程序，要求输入和输出每四位一 组，组间用逗号隔开。如 1,0000,0000,0000,0000 。21散列表的设计与实现5 / 12 设计散列表实现电话号码查找系统。【基本要求】1设每个记录有下列数据项：电话号码、用户名、地址； 2从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表； 3采用一定的方法解决冲突；4查找并显示给定电话号码的记录； 5查找并显示给定用户名的记录。【进一步完

15、成内容】1系统功能的完善； 2设计不同的散列函数，比较冲突率； 3在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变 化。22散列法的实验研究 散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不 同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法，做实验观 察，不同的解决冲突方法对查询性能的影响。23树的应用 实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递 归算法的实现，应包含建树的实现。24树与二叉树的转换的实现树与二叉树的转换的实现，以及树的前序、后序的递归、非 递归遍历算法，层次序的非

16、递归遍历算法的实现，应包含建树的实现。(多种遍历可以只实现一个 。25数制转换问题任意给定一个 M进制的数x,请实现如下要求1求出此数x的10进制值 用MD表示)2实现对x向任意的一个非M进制的数的转换。3至少用两种或两种以上的方法实现上述要求用栈解决,用数组解决,其它方法解决)。26顺序结构, ,动态链表结构下的一元多项式的加、减、乘法的实现 设有一元多项式 Am(x 和 Bn(x.Am(x=A0+A1x1+A2x2+A3x3+ +AmxmBn (x=B0+B1x1+B2x2+B3x3+ +Bnxn请实现求 M(x=Am(x+Bn(x 、M(x=Am(x-Bn(x 和 M(x=Am(xX B

17、n(x。 要求：1 首先判定多项式是否稀疏 2分别采用顺序和动态存储结构实现； 3结果 M(x 中无重复阶项和无零系数项； 4要求输出结果的升幂和降幂两种排列情况27宿舍管理查询软1 任务：为宿舍管理人员编写一个宿舍管理查询软件,程序设计要求：A. 采用交互工作方式B. 建立数据文件，数据文件按关键字 姓名、学号、房号)进行排序(冒泡、选择、插入排序等任选一种 6 / 122查询菜单 :（ 用二分查找实现以下操作 A. 按姓名查询B.按学号查询C .按房号查询3打印任一查询结果 可以连续操作） 28宿舍管理查询软件 为宿舍管理人员编写一个宿舍管理查询软件，程序要求采用交互工作方式，并建立相应的

18、 数据文件。要求：实现按关键字（姓名、学号、房号 排序的功能，并分别用冒泡、选择、插入排序实现；实现查找（按姓名、学号、房号 ，采用二分查找算法实现；有交互菜单，用户不选择退出时可以连续操作。29通讯录的制作模块要求：第一个模块一一主函数ma in （的功能是：根据选单的选项调用各函数，并完成相应的功 能。第二个模块 Menu（ 的功能是：显示英文提示选单。 第三个模块 Quit（ 的功能是：退出选单。第四个模块Create（的功能是：创建新的通讯录。第五个模块 Add（ 的功能是：在通讯录的末尾，写入新的信息，并返回选单。第六个模块一一Find（的功能是：查询某人的信息，如果找到了，则显示该

19、人的信 息，如果未找到，则提示通讯录中没有此人的信息，并返回选单。第七个模块 Alter（ 的功能是：修改某人的信息，如果未找到要修改的人，则提示 通讯录中没有此人的信息，并返回选单。第八个模块一一Delete（的功能是：删除某人的信息，如果未找到要删除的人，则提示 通讯录中没有此人的信息，并返回选单。第九个模块 List（ 的功能是：显示通讯录中的所有记录。设计要求：1每条信息至包含：姓名 NAME ）、性别（GENDER、电话TEL ）、城市CITY ）邮编 EIP ）几项。2作为一个完整的系统，应具有友好的界面和较强的容错能力 30图的遍历和最小生成树求解实现要求：1先任意创建一个图；2

20、图的 DFS,BFS 的递归和非递归算法的实现 3最小生成树 两个算法）的实现，求连通分量的实现 4要求用邻接矩阵、邻接表、十字链表多种结构存储实现31 图书管理系统 设计一个计算机管理系统完成图书管理基本业务。【基本要求】 1每种书的登记内容包括书号、书名、著作者、现存量和库存量； 2对书号建立索引表 线性表）以提高查找效率；3系统主要功能如下：7 / 12*采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存 量增加；*借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；*归还：注销对借阅者的登记，改变该书的现存量。【进一步完成内

21、容】1系统功能的进一步完善；2索引表采用树表。3设计内容4程序流程图5源程序6软件测试报告 包括所用到的数据及结果）32. 图书借阅管理系统 主要分为两大功能：1图书管理（增加图书、查询图书、删除图书、图书借阅、还书;2会员管理（增加会员、查询会员、删除会员、借书信息 ;33. 文章编辑功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求1）分别统计出其中英文字母数和空格数及整篇文章总字数；2）统计某一字符串在文章中出现的次数，并输出该次数；3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输

22、入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：1）分行输出用户输入的各行字符；2 ）分4行输出全部字母数、”数字个数、空格个数、”文章总字数3 ）输出删除某一字符串后的文章；34. 稀疏矩阵的实现和应用基本功能要求：稀疏矩阵采用三元组表示，求两个具有相同行列数的稀疏矩阵 A和B的相加矩阵C,并输出C。求出A的转置矩阵D，输出D。测试数据:35. 稀疏矩阵实现与应用要求：实现三元组、十字链表下的稀疏矩阵的加、转、乘的实现。36. 线索二叉树的应用要求实现线索树建立、插入、删除、恢复线索的实现。37校园导航问题设计要求：设计你的学校的平面图，至少包括10个以上的场

23、所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径最短路径）。1、基本要求：1）设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放8 / 12 景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。2) 为来访客人提供图中任意景点相关信息的查询。3) 为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。 2、实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。 顶点和边均含有相关信息。38学生成绩管理 实现功能：输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、

24、索 引、分类合计、退出。39学生搭配问题一班有 m 个女生 ,有 n 个男生 (m 不等于 n, 现要开一个舞会 .男女生分别编号坐在舞池的两边 的椅子上 .每曲开始时 ,依次从男生和女生中各出一人配对跳舞,本曲没成功配对者坐着等待下一曲找舞伴 .请设计一系统模拟动态地显示出上述过程,要求如下 :1输出每曲配对情况2计算出任何一个男生(编号为X和任意女生(编号为Y,在第K曲配对跳舞的情况至少求 出 K 的两个值 .3尽量设计出多种算法及程序 ,可视情况适当加分提示 :用队列来解决比较方便40学校超市选址问题 设计要求：对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频 度也不同。请为超市选址，要求实现总体最优。41一元多项式的四则运算的实现 顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。设有一元多项式 Am(x和Bn(x.A