《数据结构与算法分析课程设计》任务书2012版.doc

《《数据结构与算法分析课程设计》任务书2012版.doc》由会员分享，可在线阅读，更多相关《《数据结构与算法分析课程设计》任务书2012版.doc（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2012级数据结构与算法分析课程设计任务书 （适应于2012级软件工程专业12201801-3,12201807-9班）一、课程设计的目的与要求1教学目的数据结构与算法设计课程设计是软件工程、网络工程、数字媒体技术专业学生的重要实践性环节。通过本课程设计，学生可以了解数据结构、算法设计的基本方法与基本原理，掌握软件设计中数据的组织，算法的设计，为今后从事实际工作打下基础。同时，作为整个实践教学体系一部分，系统培养学生采用面向对象的方法分析问题与解决问题的能力及团体组织与协作能力。2教学要求从课程设计的目的出发，通过设计工作的各个环节，达到以下教学要求：1掌握各类基本数据结构及其实现；2掌握不同

2、数据结构的实际应用；3培养利用数据结构并对实际应用问题进行算法设计的能力。4编程简练，程序功能齐全，能正确运行。5说明书、流程图要清楚，规范6课题完成后必须按要求提交课程设计报告，格式规范，内容详实。二、课程设计的内容与安排序号项目名称内容提要时间安排目的要求教学方式1宿舍管理查询系统为宿舍管理人员编写一个宿舍管理查询软件，建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种) 查询菜单:(用二分查找实现以下操作) A. 按姓名查询 B. 按学号查询 C. 按房号查询1周掌握顺序表、链表实现线性表的基本操作。室内指导2文章编辑功能：输入一页文字，程序可以统

3、计出文字、数字、空格的个数。 静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。 存储结构使用线性表，分别用几个子函数实现相应的功能； 输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。 输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；1周1掌握结构体数组的表示和存储。 2.掌握线形表的存储和操作。 3掌握文件的操作。室内指导3散列

4、表的设计与实现设计散列表实现电话号码查找系统：1) 设每个记录有下列数据项：电话号码、用户名、地址； 2) 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表； 3) 采用一定的方法解决冲突； 4) 查找并显示给定电话号码的记录； 5) 查找并显示给定用户名的记录。1周1掌握结构体数组的表示和存储。 2.掌握链表的存储和操作。 3掌握文件的操作。室内指导4算术运算式的转换及求值1）对中序输入串进行合法性判断，若不合法重新输入，否则建立表达式二叉树。 2）转换为后缀表达式（逆波兰式） 3）转换为前缀表达式（波兰式） 4）计算表达式的值 5）输出计算结果及转换后串。1周1掌握二叉树的概念和

5、性质及基本操作 2.掌握栈的概念和操作室内指导5二叉树操作1 已知二叉树的后序、中序序列，恢复此二叉树； 2 求二叉树高度、分支结点数和叶子结点数； 3插入结点到指定位置、删除指定结点； 4将二叉树中所有结点的左右子树交换。 5对二叉树进行层序、非递归中序遍历。1周1掌握二叉树的概念和性质 2.掌握任意二叉树存储结构。 3掌握任意二叉树的基本操作。室内指导6哈夫曼树与哈夫曼码1输入一个文本，统计各字符出现的频度，输出结果 2使用字符出现的频度构造哈夫曼树 3确定和输出各字符的哈夫曼码 4输入一个由0和1组成的代码序列，翻译并输出与之对应的文体，若最后的代码子序列不能译为文本，则输出相关信息1周

6、1掌握哈夫曼树的建树原理 2.掌握哈夫曼树与哈夫曼码逻辑结构和存储结构。 3掌握哈夫曼树与哈夫曼码的基本操作。室内指导7字符串的操作（1） 字符串采用数组存储，建立两个字符串String1和String2。输出两个字符串。 （2） 将字符串String2的头n个字符添加到String1的尾部。输出结果。 （3） 查找串String3在串String1中的位置，若String3在String1中不存在，则插入String3在String1中的m位置上。输出结果。 （4） 求任意子字符串SUBSTR及删除子字符串。 （5） 求字符串的单词个数。1周1掌握顺序表的建立。 2掌握顺序表的基本操作。 3

7、掌握串的基本操作。室内指导8实现两个链表的合并设计内容和要求：（1） 建立两个链表A和B，链表元素个数分别为m和n个。 （2） 假设元素分别为(x1,x2,xm)，和(y1,y2,yn)。把它们合并成一个线形表C，使得： 当m=n时，C=x1,y1,x2,y2,xn,yn,xm 当nm时，C=y1,x1,y2,x2,ym,xm,yn 输出线形表C （3） 用直接插入排序法对C进行升序排序，生成链表D，并输出链表D。 （4） 能删除指定单链表中指定位子和指定值的元素。1周1掌握线性链表的建立。 2掌握线性链表的基本操作。室内指导9图的广度周游对任意给定的图（顶点数和边数自定），建立它的邻接表并输

8、出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索周游。1周1掌握图的邻接表存贮结构。 2掌握队列的基本运算实现。 3掌握图的邻接表的算法实现。 4掌握图的广度优先搜索周游算法实现。室内指导10图的深度周游对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用堆栈的五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现图的深度优先搜索周游1周1掌握图的邻接表存贮结构。 2掌握堆栈的基本运算实现。 3掌握图的邻接表的算法实现。 4掌握图的深度优先搜索周游算法实现。11成绩管理问题描述：给出n个学生的考试成绩表，成绩表包括学生的学号、姓

9、名、考试成绩（高等数学、英语、物理），设计一个简单的成绩管理程序。基本要求：（1）建立成绩表，能够插入、删除、修改学生的成绩记录；（2）按任一单科成绩排序；(3) 计算每名学生的平均成绩；(4) 统计任一单科成绩不及格的学生人数, 输出不及格人数及不及格的学生名单(5) 根据平均成绩将成绩表按由高到低的次序排列，统计每名学生在考试中获得的名次，分数相同的为同一名次，按名次输出成绩表。(6) 成绩表保存在文件中, 可以从文件读取数据。1周1、 掌握线性表的创建及基本操作；2、 掌握基本排序3、 复习文件相关的操作（1）用顺序结构表示成绩单，完成任务（1）（6），成绩为及格；（2）用链表表示成绩单

10、，完成任务（1）（6），且软件容错能力强，成绩为中等12一元多项式简单计算问题描述：设计一个简单一元多项式计算器。基本要求：(1)输入并建立多项式； (2)输出多项式； (3)两个多项式相加，输出结果多项式； (4)两个多项式相减，输出结果多项式。1周考核要求：（1）用链表表示多项式，完成任务（1）（4），成绩为及格（2）满足考核（1）的要求，同时能够输入变量的值，计算出多项式的结果，成绩中等，特别注意不能用XN计算，否则等同于没有完成提高要求。13漫游中国问题描述：从任一省会出发，走遍所有省会，给出某种评价指标，然后根据该指标由计算机选择最优的漫游路线。基本要求：（1）建立以省会为节点，以是

11、否相邻为边的一个无向赋权图；（2）只能选择陆路和水路交通；(3) 每条边的权重为两地之间的距离，以公里为单位；1周考核要求：（1）不要求画图，用数字或文字表示省会，给出漫游路线，达到基本要求，成绩可为优秀。（2）鼓励画图，用不同颜色的线画出漫游路线14银行业务模拟问题描述：设银行有四个服务窗口，一个等待队列, 每个窗口均可以办理存款、取款、挂失、还贷业务，每种业务所需的服务时间不同，客户到达银行后，先到打号机上打号，号票上包括到达时间、编号和需要办理的业务，然后在银行内等候, 当任一服务窗口空闲时,处理等候客户中排在最前面的客户的业务。写一个上述银行业务的模拟系统,通过模拟方法求出客户在银行内

12、逗留的平均时间和每个窗口办理的客户数及办理的每种业务数。1周考核要求：（1）数据结构选择合理，达到题目的基本要求，成绩为良好。（2）达到提高要求，用户界面友好，能够处理异常，成绩可以为优秀15管道铺设施工的最佳方案问题描述:需要在某个城市的n个小区铺设管道，则在这n个小区之间铺设n-1条管道即可，假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费不同，选择最优的施工方案使总投资尽可能的少。基本要求：输入表示小区间关系的图及每条管道的权值，选择出n-1条管道, 使总投资最小。图的信息输入一次后, 保存到文件中, 选择的n-1条管道输出到显示器的同时, 也保存于文件中。测试用例：

13、任意选择一个图，模拟小区间可能铺设的管道及费用。1周考核要求：本题要求能够从键盘和文件中读取原始图的数据，且选择出的最佳方案也要保存到文件中，成基本要求，成绩为中等。16稀疏矩阵应用要求：实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。（1）稀疏矩阵的存储（2）稀疏矩阵加法（3）矩阵乘法（4）矩阵转置1周考核要求：本题侧重于数组的操作17神秘国度的爱情故事输入要求：输入由若干组测试数据组成。每组数据的第1行包含一正整数N（1N50000），代表神秘国度中小村的个数，每个小村即从0到N-1编号。接下来有N-1行输入，每行包含一条双向道路的两端小村的编号，中间用空格分开。之后一行包含一正整数M

14、（1M500000），代表着该组测试问题的个数。接下来M行，每行给出A,B,C三个小村 的编号，中间用空格分开。当N为0时，表示全部测试结束，不要对该数据做任何处理。输出要求：对每一组测试给定的A,B,C，在一行里输出答案，即：如果C在A和B之间的路径上，输出Yes,否则输出No。考核要求：实现基本目标18图的基本操作与实现设计要求：(1)自选存储结构,输入含n个顶点（用字符表示顶点）和e条边的图G(2)求每个顶点的度,输出结果；(3)指定任意顶点x为初始顶点,对图G作DFS遍历,输出DFS顶点序列(提示:使用一个栈实现DFS)；(4)指定任意顶点x为初始顶点,对图G作BFS遍历,输出BFS顶

15、点序列(提示:使用一个队列实现BFS)；(5)输入顶点x,查找图G:若存在含x的顶点,则删除该结点及与之相关连的边,并作DFS遍历(执行操作3)；否则输出信息“无x”；1周考核要求：实现基本目标注：1、鼓励各位同学自主查找资料，结合专业特性，尽量应用图形界面实现，以期对图形界面的开发有一个比较深入的了解。 2、课程设计题目在一个循环（也就是划在1-18中的同学可以相互调整）2、任务要求1问题分析和任务定义。根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 2逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模

16、块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。3详细设计。定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。4程序编码。把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚。 5程序调试与测

17、试。采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。 6结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。 三、课程设计的教学建议1、课程设计任务及安排应尽早发给学生，以便学生做好课程设计的准备；2、给学生提供一些可选的题目供学生研究时参考，学生在教师指导下，自行选定力所能及的专题，分组进行研究，采用科学研究的方法去解决所选择的问题。在课程设计中，充分发挥主动性和创造性，通过检索资料、现

18、场调查来获取信息，对资料进行分析、讨论、概括总结并最终得出结论、解决问题。3、课程设计应强调学生采用面向对象的方法分析问题的过程4、课程设计中实体关系的描述应注重规范化，最好全部采用UML描述5、在适应条件下，如学生给定的课题工作量较大时，可考虑采用以工作组模式完成，培养学生的团体协作能力。6、课程设计强调的是学习过程而不是结果，通过课程设计学生可以了解并学习掌握科学研究方法，提高分析问题、解决问题的能力。课程设计没有事先预定的内容（也可以提出参考性课题），排除了很多人做同一个题目，答案千篇一律的弊病。研究内容可以根据学习过程中的新发现、新体会而改变，评价的标准具有多元性。7、教师在整个学习过

19、程中只是起指导性作用，解放学生受局限的思想，培养学生的创新能力和创新意识。这样的课程设计可以提高大学生的团队协作精神。8、课程设计的时间建议在课程结束后1-2周内进行四、课程设计的成绩评定课程设计作为特定专业技能训练的一个重要环节，应注重过程与结果的同步考核。成绩评定分三个环节进行：1、平时课程设计考核30%考核学生课程设计日常考勤及课程设计的绩效考核，每天完成多少工作量2、课程设计成果 40%考核课程设计程序成果的正确性、完整性、编程的规范化等分以下四个层次：A、全面熟悉程序结构、编码规范、基本功能实现完整，并新增有2-3个独创性功能模块，并具有明显的程序代码改进点B、全面熟悉程序结构、编码

20、相对规范、基本功能实现完整，并具有并新增有1-2个独创性功能模块，并具有明显的程序代码改进点C、熟悉程序结构、编码相对规范、基本功能实现完整3、课程设计报告 30% 课程设计报告的完整性、规范化 (详见课程设计报告的格式文档) 课程设计报告课程设计题目： 学生姓名 专 业班 级 指导教师 年 月 日东华理工大学课程设计评分表学生姓名： 班级： 学号：课程设计题目：项目内容满分实 评选题能结合所学课程知识、有一定的能力训练。符合选题要求（5人一题）10工作量适中，难易度合理10能力水平能熟练应用所学知识，有一定查阅文献及运用文献资料能力10理论依据充分，数据准确，公式推导正确10能应用计算机软件

21、进行编程、资料搜集录入、加工、排版、制图等10能体现创造性思维，或有独特见解10成果质量总体设计正确、合理，各项技术指标符合要求。10说明书综述简练完整，概念清楚、立论正确、技术用语准确、结论严谨合理；分析处理科学、条理分明、语言流畅、结构严谨、版面清晰10设计说明书栏目齐全、合理，符号统一、编号齐全。格式、绘图、表格、插图等规范准确，符合国家标准10有一定篇幅，字符数不少于500010总 分100指导教师评语： 指导教师签名： 年 月 日课程设计报告要求：报告内容要求包括：（1）问题的概述、分析及研究意义；（2）数据结构的逻辑设计和物理存储设计；（3）重要算法的设计、流程描述或伪代码描述；（4）数据结构的时空复杂性分析以及重要算法的复杂性分析；（5）程序最终实现结果（包括重点结果界面的抓取，能过说明问题的重要实验结果数据的打印或其可视化结果等）。（6）参考文献（如果需要）。格式要求：中文正文使用五号字体，英文及代码使用小五号字体