《1006402《数据结构》课程设计任务书》由会员分享，可在线阅读，更多相关《1006402《数据结构》课程设计任务书（12页珍藏版）》请在金锄头文库上搜索。
1、1006402数据结构课程设计任务书一、 设计目的1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码测试等基本方法和技能;3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力;4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 数据结构是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来
2、，并培养基本的、良好的程序设计技能。二、 设计地点湖南城市学院实验楼计算机房 407三、 设计时间2012 年 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、可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓） ；可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；8敢死队问题有 M
5、个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到 5 时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第 5 时，此战士接着去执行任务。以此类推，直到任务完成为止。排长是不愿意去的，假设排长为 1 号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。要求：至少采用两种不同的数据结构的方法实现。如果采用三种以上的方法者，可加分。9哈夫曼编码转码器
6、利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原） 。对于双工信道（即可以双向传输信息的信道） ，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编 /译码系统。基本要求一个完整的系统应具有以下功能：（1）I：初始化（Initialization） 。从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树，并将它存于文件 hfmTree 中。（2）E：编码（Encoding） 。利用已建好的哈夫曼树（如不在内存，则从文件 htmTree
7、中读入） ，对文件 ToBeTran 中的正文进行编码，然后将结果存入文件 CodeFile 中。（3）D：译码（Decoding） 。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件 TextFile 中。（4）P：印代码文件（Print ） 。将文件 CodeFile 以紧凑格式显示在终端上，每行 50 个代码。同时将此字符形式的编码写入文件 CodePrint 中。（5）T：印哈夫曼树（TreePrinting） 。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件 TreePrint 中。测试数据（1）数据一
8、：已知某系统在通信联络中只可能出现 8 种字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,以此设计哈夫曼编码。利用此数据对程序进行调试。（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THISPROGRAM ISMYFAVORITE”。实现提示（1）文件 CodeFile 的基类型可以设为子界型 bit=0.1。（2）用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示运行 Quit。请用户键入一个先把功能符，些功能执行完毕后再经菜单，直至某次用户先把了“E”为止。（3）在程序的一次执行过
9、程中，第一次执行 I、D 或 C 命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行 I 命令，因为文件 hfmTree 可能早已建好。10猴子吃桃问题有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半再多吃一个，到了第 10 天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。11活期储蓄账目管理活期储蓄处理中，储户开户、销户、存入、支出活动频繁，系统设计要求：1)能比较迅速地找到储户的帐户，以实现存款、取款记账；2)能比较简单，迅速地实现插入和删除，以实现开户和销户的需要。12简单的职工管理系统1.问题描述对单位的职工进行管理，包括插入、删除、查找、排序等功能
10、。2.要求职工对象包括姓名、性别、出生年月、工作年月、学历、职务、住址、电话等信息。（1）新增一名职工：将新增职工对象按姓名以字典方式职工管理文件中。（2）删除一名职工：从职工管理文件中删除一名职工对象。（3）查询：从职工管理文件中查询符合某些条件的职工。（4）修改：检索某个职工对象，对其某些属性进行修改。（5）排序：按某种需要对职工对象文件进行排序。3.实现提示职工对象数不必很多，便于一次读入内存，所有操作不经过内外存交换。（1）由键盘输入职工对象，以文件方式保存。程序执行时先将文件读入内存。（2）对职工对象中的姓名按字典顺序进行排序。（3）对排序后的职工对象进行增、删、查询、修改、排序等操
11、作。4.选做内容将职工对象按散列法存储，并设计解决冲突的方法。在此基础上实现增、删、查询、修改、排序等操作。13简易文本编辑器 要求：1)具有图形菜单界面；2)查找，替换（等长，不等长） ，插入（插串，文本块的插入） 、块移动（行块，列块移动） ，删除3)可正确存盘、取盘；4)正确显示总行数。14教学计划编制问题大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下
12、设计一个教学计划编制程序。基本要求（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占 3 位的字母数字串)、学分和直接先修课的课程号。（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。测试数据学期总数：6；学分上限：10；该专业共开设 12 门课，课程号从 C01 到 C12，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系如下：实现提示可设学期总数不超过 12，课程总数不超过
13、100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程序号与课程号之间的对应关系。15客户消费积分管理系统针对客户的消费情况，进行客户管理，根据客户的消费积分对客户实行不同程度的打折优惠。基本要求：1采用一定的存储结构进行客户信息的存储；2对客户的信息可以进行修改、删除、添加；3能够根据消费情况进行客户积分的计算；4根据积分情况实行不同程序的打折优惠。16老鼠走迷宫程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。要求：1)老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；2)
14、迷宫的墙足够结实，老鼠不能穿墙而过；3)正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；4)添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；5)找出走出迷宫的所有路径，以及最短路径。利用序列化功能实现迷宫地图文件的存盘和读出等功能17利用栈求表达式的值编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。主要功能描述如下：1、从键盘上输入表达式。2、分析该表达式是否合法：（1）是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。（2）是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。（3）若是其它字符，则返
15、回错误信息。3、若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。程序中应主要包含下面几个功能函数：voidinitstack()：初始化堆栈intMake_str()：语法检查并计算intpush_operate(intoperate)：将操作码压入堆栈intpush_num(doublenum)：将操作数压入堆栈intprocede(intoperate)：处理操作码intchange_opnd(intoperate)：将字符型操作码转换成优先级intpush_opnd(intoperate)：将操作码压入堆栈intpop_opnd()：将操作码弹出堆栈intcaculat
16、e(intcur_opnd)：简单计算+ ，-，*，/doublepop_num()：弹出操作数18利用栈求表达式的值随机产生 n 个题目，题目涉及加减乘除和带括号的混合运算。要求：有交互菜单；指定键随时终止练习；将所有的练习题和答案及对错评价输出到文件备查；按对错的比例，给出“优” 、 “良” 、 “中” 、 “还需努力”的评价。19排序综合利用随机函数产生 N 个随机整数（ 20000 以上） ，对这些数进行多种方法进行排序。要求：1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序） 。并把排序后的结果保存在不同的文件中。2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比） ，找出其中两种较快的方法。3)如果采用 4 种或 4 种以上的方法者，可适当加分。20任意长的整数加法设计一个程序实现两个任意长的整数的求和运算。要求
