《数据结构课程设计大纲(修订)new》由会员分享，可在线阅读，更多相关《数据结构课程设计大纲(修订)new（3页珍藏版）》请在金锄头文库上搜索。
1、课程设计实践教学大纲（修订）编 号171006实践名称课程设计II周 数2学 分2学 期5实践承担单位计算机系1目的与意义数据结构课程设计作为数据结构课程的后续实践环节，以C/C+语言为工具，以该课程中的数据结构和算法为基础进行算法设计及程序实现的综合性课程设计。其任务是培养学生进一步理解和掌握所学的各种基本抽象数据类型的逻辑结构、存储结构和实现算法，以及它们在程序设计中的使用方法，提高学生进行算法设计与分析能力，提高学生程序设计和调试能力。其目的是为了培养学生具备高级程序设计与系统开发的初步能力。2设计要求本课程设计重在过程控制，要对学生在以下几个方面进行训练。1）问题分析和任务定义：根据设
2、计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图；3）详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做
3、出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；7）编写课程设计报告；3设计内容在每次课程设计时围绕数据结构课程中的一些抽象数据类型和各种算法
4、，选择与实际应用结合紧密的较综合性的题目，难度应大于课程实验的题目。例如下述一些题目：1)一元多项式的代数运算设计要求：计算任意两个一元多项式的加法、减法以及乘法。2)算术表达式求值设计要求：将任意一个算术表达式转化为逆波兰表示，并根据逆波兰表示计算表达是的值。3)舞伴问题假定在一舞会上，男士排成一队，女士排成一队。跳舞开始时，依次从男队和女队的队头各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。设计要求：模拟上述舞伴系统，并能计算对于任何男士A和女士B在哪一轮舞曲中的k次跳舞？4)集合的等价划分设计要求：对于任何一个集合及其上的一个等价关系（要验证此关系的等价
5、性），给出该集合的等价划分。5)树或二元树的层次遍历设计要求：对于任何一个给定的树或二元树依据其层次关系从上到下（层次之间），从左到右（同一层内）进行遍历。6)哈夫曼编码与译码设计要求：针对字符集A及其各字符的频率值（可统计获得）给出其中给字符哈夫曼编码，并针对一段文本（定义在A上）进行编码和译码，实现一个哈夫曼编码/译码系统。7)地图着色问题设计要求：已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使用的颜色总数最少。8)小型文本编辑器设计要求：设计一个文本编辑器，使其具有通常编辑器（如Notepad）具备的功能。9)校园导航问题设计要求：设计你的学校的平面图，至少包括10个
6、以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。10)学校超市选址问题（带权有向图的中心点）设计要求：对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。11)教学计划编制问题 设计要求：针对计算机本科课程，根据课程之间的依赖关系（如离散数学应在数据结构之前开设）制定课程安排计划，并满足各学期课程数目大致相同。12)散列法的实验研究散列法中，散列函数构造方法多种多样，同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法，
7、做实验观察，不同的解决冲突方法对查询性能的影响。13)关键路径设计要求：对于任何大型工程项目（由若干小工程组成），求其关键路径。14)最小生成树问题设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。15)平衡二元树的判定设计要求：给定一个二元树的先序遍历或后序遍历结果，判定其是否为平衡二元树。4实践方式学生应按照所选题目的要求，积极查阅资料，自行编制和调试程序，教师只在技术上进行指导。5实习地点校内6考核与成绩评定课程设计的成绩评定主要由以下几部分组成：平时（考勤、态度、课设过程中的课设进展情况等）20；软件实现程度、正确性以及结构合理性，课程设计报告中算法说明的清晰程度、程序中的注释是否适当、总结的深刻程度等40；验收情况（设计完成的及时性以及报告的规范程度等）、答辩（自我陈述情况、相关基础知识的掌握程度等）情况40。7主要教学参考书1 严蔚敏.数据结构.北京：清华大学出版社.2006.2 李春葆.数据结构教程.北京：清华大学出版社.2005.3 黄国瑜，叶乃菁.数据结构（C语言版）.北京：清华大学出版社.2006.执 笔 人：曹记东审 核 人：李 军批 准 人：郭天印修订时间：2008年12月
