《数据结构课程设计任务书软件.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计任务书软件.doc（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2013/2014学年第2学期数据结构 课程设计任务书指导教师： 耿晓中、毛应爽班级：软件1242班 地点： 9209一、 课程设计目的数据结构是计算机专业的专业基础课，是一门实践性很强的课程，学生通过理论学习，并在完成每章后面的一些小程序后，理解了数据结构的基本概念，掌握了一些基本的编程技术，但仅有这一方面的训练还是很不够的。全面、严格的训练，是学好该课程的一个不可缺少的组成部分。课程设计对于提高学生用学到的书本知识解决实际问题，培养实际工作所需要的动手能力，对于提高以科学理论和工程上的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用。通过课程设计的实践，学生可以在程序设
2、计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。二、 课程设计内容（包括技术指标）数据结构课程设计则要培养、训练学生选用合适的数据结构并运用程序设计语言（C/C+）编写质量高的应用程序。并建立初步评价算法程序的能力。为编译技术、操作系统、数据库及算法设计与分析等后继课程的学习以及为应用软件特别是非数值应用软件的开发打下良好的理论基础和实践基础重点和难点： 1. 针对具体问题如何选择或设计合适的数据结构； 2. 如何根据一定的存储策略实现数据的存储表示； 3. 基于上述数据结构设计并实现完成具体要求的算法； 4. 对算法的时间性能进行分析。 手段和方法： 1. 给出具体示例和设
3、计方法示例； 2. 上机前的预习及检查； 3. 分组讨论，团队合作； 4. 每天上机后总结。三、课程设计题目、内容及学时分配具体设计题目：（每个同学用自己的学号除以23取余，对应的序号就是的设计题目序号，其中学号23对应第23题）1、通讯录的制作 设计目的：用数据结构中的双向链表作数据结构，结合语言基本知识。编写一个通讯录管理系统。以把所学数据结构知识应用到实际软件开发中去。 设计内容：本系统应完成一下几方面的功能： 输入信息 enter(); 显示信息 display( ); 查找以姓名作为关键字 search( ); 删除信息 delete( ); 存盘 save ( ); 装入 load
4、( ) ; 设计要求： 每条信息至包含 ：姓名（NAME ）街道（STREET）城市（CITY）邮编（EIP）国家（ STATE）几项 作为一个完整的系统，应具有友好的界面和较强的容错能力 上机能正常运行，并写出课程设计报告 2、全国交通咨询模拟 问题描述：处于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能的短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。 设计要求： 提供对城市信息进行编辑（如：添加或删除）的功能。 城市之间有两种交通工具：火车和飞机。提供对列车时
5、刻表和飞机航班进行编辑（增设或删除）的功能。 提供两种最优决策：最快到达和最省钱到达。全程只考虑一种交通工具。 旅途中耗费的总时间应该包括中转站的等候时间。 咨询以用户和计算机的对话方式进行。由拥护输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。 测试数据：自行设计列车时刻表和飞机航班。 实现提示： （ 1） 对全国城市交通图和列车时刻表及飞机航班表进行编辑，应该提供文件形式输入和键盘输入两种方式。飞机航班表的信息应包括：起始站的出发时间、终点站的到达时间和票价；列车时刻表则需根据
6、交通图给出各个路段的详细信息，（ 2） 以邻接表作交通图的存储结构，表示边的结构内除含有邻接点的信息外，还应包括交通工具、路程中耗费的时间和花费以及出发和到达的时间等多种属性。 选作内容：增加旅途中转次数最少的最优决策。 3、运动会分数统计任务：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）功能要求：1).可以输入各个项目的前三名或前五名的成绩；2)能统计各学校总分
7、，3)可以按学校编号、学校总分、男女团体总分排序输出；4).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数
8、据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；4、 一元多项式计算任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加减、相乘，并将结果输入；在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；5、 订票系统任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可
9、以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能； 6、 文章编辑功能要求：输入一页文字，程序可以统计出文字、数字、空格的个数。（1）静态存储一页文章，每行最多不超过80个字符，共N行；要求 分别统计出其中英文字母数和空格数及整篇文章总字数； 统计某一字符串在文章中出现的次数，并输
10、出该次数； 删除某一子串，并将后面的字符前移。（2）存储结构使用线性表，分别用几个子函数实现相应的功能；（3）输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。（4）输出形式：1) 分行输出用户输入的各行字符；2) 分4行输出全部字母数、数字个数、空格个数、文章总字数输出删除某一字符串后的文章。7、设计题目joseph环 任务：编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重
11、新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 8、Channel AllocationWhen a radio station is broadcasting over a very large area, repeaters are used to retransmit the signal so that every receiver has a strong signal. However, the channels used by each repeater must be care
12、fully chosen so that nearby repeaters do not interfere with one another. This condition is satisfied if adjacent repeaters use different channels. Since the radio frequency spectrum is a precious resource, the number of channels required by a given network of repeaters should be minimised. You have
13、to write a program that reads in a description of a repeater network and determines the minimum number of channels required.INPUTThe input consists of a number of maps of repeater networks. Each map begins with a line containing the number of repeaters. This is between 1 and 26, and the repeaters ar
14、e referred to by consecutive upper-case letters of the alphabet starting with A. For example, ten repeaters would have the names A,B,C,.,I and J. A network with zero repeaters indicates the end of input. Following the number of repeaters is a list of adjacency relationships. Each line has the form:
15、A:BCDH which indicates that the repeaters B, C, D and H are adjacent to the repeater A. The first line describes those adjacent to repeater A, the second those adjacent to B, and so on for all of the repeaters. If a repeater is not adjacent to any other, its line has the form A: The repeaters are li
16、sted in alphabetical order. Note that the adjacency is a symmetric relationship; if A is adjacent to B, then B is necessarily adjacent to A. Also, since the repeaters lie in a plane, the graph formed by connecting adjacent repeaters does not have any line segments that cross.OUTPUTFor each map (exce
17、pt the final one with no repeaters), print a line containing the minumum number of channels needed so that no adjacent channels interfere. The sample output shows the format of this line. Take care that channels is in the singular form when only one channel is required.SAMPLE INPUT2A:B:4A:BCB:ACDC:A
18、BDD:BC4A:BCDB:ACDC:ABDD:ABC0SAMPLE OUTPUT1 channel needed.3 channels needed.4 channels needed.提示：此题中借助图论中四色猜想问题解决 repeater :中继器，网络设备 Channel 信道9、求回文串Given a character string, determine if it is a palindrome. A palindrome is a word or phrase that reads the same forwards and backwards, like mom or noo
19、n. For our purposes, palindromes are case insensitive, so Bob and Anna are palindromes. Also, we are only concerned with alphabetic characters, so punctuation and other non-alphabetic characters may be ignored.InputA positive integer denoting the number of cases. Each case will consist of a string o
20、f characters, including blanks and non-alphabetic characters. Each case will be on a separate line.OutputThe sentence “ is a palindrome.” if the word is a palindrome, or the sentence “ is not a palindrome.” if it is not, where is the input string.Sample Input5Allen AldaasdffdsaRace carGo hang a sala
21、mi, Im a lasagna hog!HannaSample OutputAllen Alda is not a palindrome.asdffdsa is a palindrome.Race car is a palindrome.Go hang a salami, Im a lasagna hog! is a palindrome.Hanna is not a palindrome.回文串的判断，利用栈10、Degrees of separationFind out how many people separate one person from another.The number
22、 of people will be no more than 20.InputA positive integer representing the number of people in the following list. Each line in the list contains the name of a person, followed by the number of people that person knows, followed by the names of those people. Following this list is a positive intege
23、r denoting the number of cases. Each case consists of a starting name and a goal name. Names will not contain any blanks or non-alphabetic characters.OutputThe phrase “ has no connection to .” or the phrase “ is separated from by degrees.”, where is the starting name, is the goal name, and is the nu
24、mber of degrees of separation between the two.Sample Input5Bob 3 Tom John JimSam 2 Bob JohnJohn 2 Tom BobTom 1 SamJim 03Jim SamSam JohnJohn SamSample OutputJim has no connection to Sam.Sam is separated from John by 0 degrees.John is separated from Sam by 1 degrees.提示：有向图求路径长度11、MarriageNow, a lot of
25、 persons holding their marriages together are in fashion. One day, a lot of people hold their marriages together. They are all happy, so they want to play a game. They stand in two lines, one faces one. The men are in one line, the women are in another. They stand arbitrarily. Then, there will be so
26、me red lines to link each couple. So can you calculate how many pairs of the red lines are overlaped（交叉）.InputThere are several cases in the input, each case begin with a postive integer N(N=B, C=A 输入后，你应该判断出本题中的结论矛盾。输入：4 （代表将有4个结论）A=BC=A输出：YES (说明有冲突)提示：本题是利用有向图中是否存在回路的方法，来解题#include stdio.h#includ
27、e stdlib.hconst int MaxVertexNum = 1000;typedef char VertexType; typedef struct node int adjvex; bool flag;/=为true,为false struct node *next;EdgeNode;typedef struct vnode VertexType vertex; EdgeNode *firstedge;VertexNode;class ALGraphprivate: VertexNode adjlistMaxVertexNum; int n,e; bool visitedMaxVe
28、rtexNum; int pathsMaxVertexNum;public: ALGraph():n(0),e(0) void addVex(VertexType key) int i; for(i = 0;i n;i+) if(adjlisti.vertex = key) return; adjlistn.firstedge = NULL; adjlistn.vertex = key; n+; bool addEdge(VertexType key1,VertexType key2,bool f) int i,j; for(i = 0;i n;i+) if(adjlisti.vertex =
29、 key1) break; if(i = n) return false; for(j = 0;j adjvex = j) if(p-flag = f) return false; else if(f = true) return false; else p-flag = false; return false; p = p-next; p = (EdgeNode *)malloc(sizeof(EdgeNode); p-adjvex = j; p-flag = f; p-next = adjlisti.firstedge; adjlisti.firstedge = p; e+; return
30、 true; bool hasCricle() int i,j,depth; for(i = 0;i n;i+) for(j = 0;j n;j+) visitedj = false; paths0 = i;/paths0为DFS访问第一个节点，pathn为以后访问路径边的flag值（标记边是=还是adjvex = paths0) pathsdepth+1 = p-flag; for(int j = 1;j adjvex) pathsdepth+1 = p-flag; if(!DFS(p-adjvex,depth+1) return false; p = p-next; return true
31、; ;void start() int n = 0,i; char str5; scanf(%d,&n); ALGraph G; for(i = 0;i n;i+) scanf(%s,str); G.addVex(str0); if(str1 = =&str2 = =) G.addVex(str3); G.addEdge(str0,str3,true); G.addEdge(str3,str0,true); else if(str1 = ) if(str2 = =) G.addVex(str3); G.addEdge(str0,str3,true); else G.addVex(str2);
32、G.addEdge(str0,str2,false); else if(str2 = =) G.addVex(str3); G.addEdge(str3,str0,true); else G.addVex(str2); G.addEdge(str2,str0,false); if(G.hasCricle() printf(NOn); else printf(YESn);void main() start(); system(pause);19、哈夫曼编码/译码器问题描述：设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。基本要求：1)将权值数据存放在数据文件(
33、文件名为data.txt，位于执行程序的当前目录中) 2)分别采用动态和静态存储结构3)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；4)编码：利用建好的哈夫曼树生成哈夫曼编码；5)输出编码；6)设字符集及频度如下表：字符 空格 A B C D E F G H I J K L M频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 进一步完成内容：1)译码功能；2)显示哈夫曼树；3)界面设计的优化20、括号匹配
34、的检验问题描述假设表达式中允许有三种括号：圆括号和方括号和大括号，其嵌套的顺序随意，即（） ）或（ ）等为正确格式，（ ）或（均为不正确的格式。检验括号是否匹配的方法可用“期待的紧迫程度”这个概念来描述。例如：考虑下列的括号序列：()12345678当计算机接受了第1个括号以后，他期待着与其匹配的第8个括号的出现，然而等来的却是第2个括号，此时第1个括号“”只能暂时靠边，而迫切等待与第2个括号相匹配的 第7个括号“）”的出现，类似的，因只等来了第3个括号“”，此时，其期待的紧迫程度较第2个括号更紧迫，则第2个括号只能靠边，让位于第3个括号，显然第3个括号的期待紧迫程度高于第2个括号，而第2个括
35、号的期待紧迫程度高于第1个括号；在接受了第4个括号之后，第3个括号的期待得到了满足，消解之后，第2个括号的期待匹配就成了最急迫的任务了， ，依次类推。可见这个处理过程正好和栈的特点相吻合。基本要求读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法”。测试数据 输入（ （），结果“匹配”输入 （ ），结果“此串括号匹配不合法”实现提示设置一个栈，每读入一个括号，若是左括号，则作为一个新的更急迫的期待压入栈中；若是右括号，并且与当前栈顶的左括号相匹配，则将当前栈顶的左括号退出，继续读下一个括号，如果读入的右括号与当前栈顶的左括号不匹配，则属于不合法的情况。在初始和结束时，栈应该是空的
36、。21、无向图应用问题 任务：如果以五向网表示n个城市之间通信网络的建设计划，顶点表示城市，边上的权表示该线路的造价，设计一个方案，使这个通讯网的总造价最低。 提示：这是一个求最小生成树的问题。n个城市名和各边的权值由用户输入，建立图的邻接矩阵，然后以Prim或Kruskal算法算法来求最小生成树，然后输出方案。22、表达式求值问题基本要求：1）先将算术表达式转换成后缀表达式2）然后对该后缀表达式求值。 提示：借助栈23、已知一棵二叉树的先序遍历和中序遍历序列，设计一个算法唯一确定一棵二叉树，并给出后序遍历序列。四、时间安排一周时间: 2014年2月24日2014年2月28日。上机时间： 周一
37、至周五，上午7:5011:20，下午13:0016:30，周三下午不设计。五、基本要求1明确课程设计任务，提高课程设计认识，严格服从教师安排，不迟到，不早退，不旷课，按时上机；上机时认真做设计，不得做聊天、上网、玩游戏等与课程设计无关的事情，一经发现，经警告不改者，取消上机资格并把其课程设计成绩作零分计。2认真独立完成设计内容，上机前准备程序，做好资料搜集，能够上网查询所需资料；除了上机，其余时间为查找资料和编写程序，要充分利用好时间。3利用数据结构及其C+的编程思想来完成系统的设计，给出详细地分析过程，画出程序流程图；编写程序，调试各模块。学会从问题入手，分析研究数据结构中数据表示和数据处理
38、的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法，并初步掌握时间和空间分析技术。要求学生书写符合软件工程规范的文件，编写的程序代码应结构清晰、正确易读，能上机调试并排除错误。4请各位同学携带U盘等存储设备，每次编写完程序作备份，以防源程序丢失。 5完成答辩，提交课程设计报告。6本次课程设计属于考查课，没有补考。上机程序未通过者或无设计报告者，成绩为不及格。其它情况根据界面设计、实现方法、功能效果、设计报告来评定优、良、中、及格。课程设计的最后成绩可评定为优、良、中、及格，不及格。每名学生独立完成课程设计，不许抄袭，一经发现取消成绩。主要从以下几个方面考察：项目得分备注程序运行情况25分程序的结构合理与否15分算法说明的清晰程度20分总结的深刻程度10分独立完成情况20分加分因素10分