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

2012级数据结构与算法分析课程设计任务书 （适应于2012级软件工程专业12201813-15、12201820-21、12221001-3班）一、课程设计的目的与要求1教学目的数据结构与算法设计课程设计是软件工程、网络工程、数字媒体技术专业学生的重要实践性环节。通过本课程设计，学生可以了解数据结构、算法设计的基本方法与基本原理，掌握软件设计中数据的组织，算法的设计，为今后从事实际工作打下基础。同时，作为整个实践教学体系一部分，系统培养学生采用面向对象的方法分析问题与解决问题的能力及团体组织与协作能力。2教学要求从课程设计的目的出发，通过设计工作的各个环节，达到以下教学要求：1掌握各类基本数据结构及其实现；2掌握不同数据结构的实际应用；3培养利用数据结构并对实际应用问题进行算法设计的能力。4编程简练，程序功能齐全，能正确运行。5说明书、流程图要清楚，规范6课题完成后必须按要求提交课程设计报告，格式规范，内容详实。二、课程设计的内容与安排序号项目名称内容提要时间安排目的要求教学方式1宿舍管理查询系统为宿舍管理人员编写一个宿舍管理查询软件，建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种) 查询菜单:(用二分查找实现以下操作) A. 按姓名查询 B. 按学号查询 C. 按房号查询1周掌握顺序表、链表实现线性表的基本操作。室内指导2文章编辑功能：输入一页文字，程序可以统计出文字、数字、空格的个数。 静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。 存储结构使用线性表，分别用几个子函数实现相应的功能； 输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。 输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；1周1掌握结构体数组的表示和存储。 2.掌握线性表的存储和操作。 3掌握文件的操作。室内指导3散列表的设计与实现设计散列表实现电话号码查找系统：1) 设每个记录有下列数据项：电话号码、用户名、地址； 2) 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表； 3) 采用一定的方法解决冲突； 4) 查找并显示给定电话号码的记录； 5) 查找并显示给定用户名的记录。1周1掌握结构体数组的表示和存储。 2.掌握链表的存储和操作。 3掌握文件的操作。室内指导4二叉树操作1 已知二叉树的后序、中序序列，恢复此二叉树； 2 求二叉树高度、分支结点数和叶子结点数； 3插入结点到指定位置、删除指定结点； 4将二叉树中所有结点的左右子树交换。 5对二叉树进行层序、非递归中序遍历。1周1掌握二叉树的概念和性质 2.掌握任意二叉树存储结构。 3掌握任意二叉树的基本操作。室内指导5哈夫曼树与哈夫曼码1输入一个文本，统计各字符出现的频度，输出结果 2使用字符出现的频度构造哈夫曼树 3确定和输出各字符的哈夫曼码 4输入一个由0和1组成的代码序列，翻译并输出与之对应的文体，若最后的代码子序列不能译为文本，则输出相关信息1周1掌握哈夫曼树的建树原理 2.掌握哈夫曼树与哈夫曼码逻辑结构和存储结构。 3掌握哈夫曼树与哈夫曼码的基本操作。室内指导6字符串的操作（1） 字符串采用数组存储，建立两个字符串String1和String2。输出两个字符串。 （2） 将字符串String2的头n个字符添加到String1的尾部。输出结果。 （3） 查找串String3在串String1中的位置，若String3在String1中不存在，则插入String3在String1中的m位置上。输出结果。 （4） 求任意子字符串SUBSTR及删除子字符串。 （5） 求字符串的单词个数。1周1掌握顺序表的建立。 2掌握顺序表的基本操作。 3掌握串的基本操作。室内指导7实现两个链表的合并设计内容和要求：（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掌握线性链表的基本操作。室内指导8图的广度遍历对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索遍历。1周1掌握图的邻接表存贮结构。 2掌握队列的基本运算实现。 3掌握图的邻接表的算法实现。 4掌握图的广度优先搜索周游算法实现。室内指导9图的深度遍历对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用堆栈的五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现图的深度优先搜索遍历1周1掌握图的邻接表存贮结构。 2掌握堆栈的基本运算实现。 3掌握图的邻接表的算法实现。 4掌握图的深度优先搜索周游算法实现。10成绩管理问题描述：给出n个学生的考试成绩表，成绩表包括学生的学号、姓名、考试成绩（高等数学、英语、物理），设计一个简单的成绩管理程序。基本要求：（1）建立成绩表，能够插入、删除、修改学生的成绩记录；（2）按任一单科成绩排序；(3) 计算每名学生的平均成绩；(4) 统计任一单科成绩不及格的学生人数, 输出不及格人数及不及格的学生名单(5) 根据平均成绩将成绩表按由高到低的次序排列，统计每名学生在考试中获得的名次，分数相同的为同一名次，按名次输出成绩表。(6) 成绩表保存在文件中, 可以从文件读取数据。1周1、 掌握线性表的创建及基本操作；2、 掌握基本排序3、 复习文件相关的操作（1）用顺序结构表示成绩单，完成任务（1）（6），成绩为及格；（2）用链表表示成绩单，完成任务（1）（6），且软件容错能力强，成绩为中等或以上11一元多项式简单计算问题描述：设计一个简单一元多项式计算器。基本要求：(1)输入并建立多项式； (2)输出多项式； (3)两个多项式相加，输出结果多项式； (4)两个多项式相减，输出结果多项式。1周考核要求：（1）用链表表示多项式，完成任务（1）（4），成绩为及格（2）满足考核（1）的要求，同时能够输入变量的值，计算出多项式的结果，成绩中等或以上，特别注意不能用XN计算，否则等同于没有完成提高要求。12稀疏矩阵应用要求：实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。（1）稀疏矩阵的存储（2）稀疏矩阵加法（3）矩阵乘法（4）矩阵转置1周考核要求：本题侧重于数组的操作注：鼓励各位同学自主查找资料，结合专业特性，尽量应用图形界面实现，以期对图形界面的开发有一个比较深入的了解。 2、任务要求1问题分析和任务定义。根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 2逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。3详细设计。定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。4程序编码。把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚。 5程序调试与测试。采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。 6结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。 三、课程设计的教学建议1、课程设计任务及安排应尽早发给学生，以便学生做好课程设计的准备；2、给学生提供一些可选的题目供学生研究时参考，学生在教师指导下，自行选定力所能及的专题，分组进行研究，采用科学研究的方法去解决所选择的问题。在课程设计中，充分发挥主动性和创造性，通过检索资料、现场调查来获取信息，对资料进行分析、讨论、概括总结并最终得出结论、解决问题。3、课程设计应强调学生采用面向对象的方法分析问题的过程4、课程设计中实体关系的描述应注重规范化，最好全部采用UML描述5、在适应条件下，如学生给定的课题工作量较大时，可考虑采用以工作组模式完成，培养学生的团体协作能力。6、课程设计强调的是学习过程而不是结果，通过课程设计学生可以了解并学习掌握科学研究方法，提高分析问题、解决问题的能力。课程设计没有事先预定的内容（也可以提出参考性课题），排除了很多人做同一个题目，答案千篇一律的弊病。研究内容可以根据学习过程中的新发现、新体会而改变，评价的标准具有多元性。7、教师在整个学习过程中只是起指导性作用，解放学生受局限的思想，培养学生的创新能力和创新意识。这样的课程设计可以提高大学生的团队协作精神。8、课程设计的时间建议在课程结束后1-2周内进行四、课程设计的成绩评定课程设计作为特定专业技能训练的一个重要环节，应注重过程与结果的同步考核。成绩评定分三个环节进行：1、平时课程设计考核30%考核学生课程设计日常考勤及课程设计的绩效考核，每天完成多少工作量2、课程设计成果 40%考核课程设计程序成果的正确性、完整性、编程的规范化等分以下四个层次：A、全面熟悉程序结构、编码规范、基本功能实现完整，并新增有2-3个独创性功能模块，并具有明显的程序代码改进点B、全面熟悉程序结构、编码相对规范、基本功能实现完整，并具有并新增有1-2个独创性功能模块，并具有明显的程序代码改进点C、熟悉程序结构、编码相对规范、基本功能实现完整3、课程设计报告 30% 课程设计报告的完整性、规范化 (详见课程设计报告的格式文档) 课程设计报告课程设计题目： 学生姓名 专 业班 级 指导教师 年 月 日东华理工大学课程设计评分表学生姓名： 班级： 学号：课程设计题目：项目内容满分实 评选题能结合所学课程知识、有一定的能力训练。符合选题要求（5人一题）10工作量适中，难易度合理10能力水平能熟练应用所学知识，有一定查阅文献及运用文献资料能力10理论依据充分，数据准确，公式推导正确10能应用计算机软件进行编程、资料搜集录入、加工、排版、制图等10能体现创造性思维，或有独特见解10成果质量总体设计正确、合理，各项技术指标符合要求。10说明书综述简练完整，概念清楚、立论正确、技术用语准确、结论严谨合理；分析处理科学、条理分明、语言流畅、结构严谨、版面清晰10设计说明书栏目齐全、合理，符号统一、编号齐全。格式、绘图、表格、插图等规范准确，符合国家