《数据结构课程设计A》教学大纲

1、数据结构课程设计A教学大纲 编写日期：课程组组长签名：审定人签名：一、课程基本信息1课程代码：419209012课程中文名称：数据结构课程设计A 课程英文名称：Course Design for Data structure A3面向对象：地理信息科学，软件工程，信息工程及遥感科学与技术专业本科学生4开课学院（课部）、系（中心、室）：信息工程学院、软件工程系5实习周数：2周6学分数：27授课语种：中文，考试语种：中文 8教材：参见实习指导书。二、课程内容简介数据结构课程是软件工程及计算机相关专业一门重要的专业必修课，它涉及的概念多、内容广，具有较强的理论性和实践性，在整个教学课程体系中处于承上

2、启下的作用。数据结构课程实习，是在完成理论课程学习之后安排的综合实践训练。通过两周的课程实验活动，加深学生对数据结构课程内容的理解，增加感性认识，掌握利用计算机解决问题的基本方法、步骤和技术，提高学生利用所学知识解决实际问题的能力。三、课程的地位、作用和教学目标学生通过该课程实习，应该达到的教学目标为：1、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作

3、方法和作风。四、与本课程相联系的其他课程 计算机高级语言（C+），计算机高级程序语言课程设计，数据结构。五、教学基本要求数据结构课程实习要求学生根据教师布置实习题目，独立设计并编写能正确运行的程序，并且能通过多种黑盒法测试用例进行健壮性验证。实习结束后，学生还应按照指定文档模板，撰写并提交课程实验报告。学生在课程实习过程中，应遵循以下步骤： 问题分析和任务定义。根据课程设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计

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

5、块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实或排除这些疑点。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。 结果分析。程序运行结果不仅包括正确的输入及其输出结果，还应含有错误的输入及其输出结果，采用黑盒测试的方法进行多方位用例测试；同时，通过对算法的时间、空间复杂性的分析，提供更为优化的改进程序版本。同时，在课程实习报告的撰写中，要求学生按照给定文档模板格式，体现出对问题进行分析、软件设计、程序编码和调试、软件测试等上述环节的实施细节。课程实习报告要求在实习结束后一周内上交。六、考核方式与评价结构比例1、考核方式

6、：课程实习的成绩由三部分组成：上机考勤、课程设计报告和课堂检查结果。其中，课堂检查结果与学生完成的题数和质量相关。以3题为例，课堂检查结果等级如下：优秀：完成3题，且代码质量高；良好：完成2题，且代码质量高；中等：完成2题，且代码质量一般；及格：完成1题；不及格：完成小于1题。如检查结果发现有网上直接下载使用，或同学之间拷贝使用，成绩将以不及格计。2、评价结构比例：上机考勤10%，课程设计报告30%，课堂检查的软件作品60%。指导老师按优秀、良好、中等、及格、不及格五档提交成绩，成绩等级如下：优秀：90-100；良好：80-89；中等：70-79；及格：60-69；不及格：60，成绩不合格者需

7、要重修。七、教学参考资料 1 软件工程系, 数据结构课程设计大纲20112014版, 2011.12.2 Sartaj Sahni著, 数据结构算法与应用C+语言描述, 机械工业出版社.3 严蔚敏 吴伟民等编著, 数据结构, 清华大学出版社.4 殷人昆 陶永雷 等编著, 数据结构（用面向对象方法与C+描述）, 清华大学出版社.5 William Ford William Topp著, Data Structure with C+, 清华大学出版社.6 Donald E. Knuth著, 计算机程序设计艺术第1卷基本算法, 国防工业出版社.7 Thomas H.Cormen Charles E.

8、Leiserson Ronald L.Rivest Clifford Stein, Introduction to Algorithms(Second Edition)（美）,高等教育出版社.八、教学进度与内容安排序次教学基本内容、重点、难点1线性表的应用1）线性表的顺序存储结构：顺序表上的插入、删除等基本操作；利用顺序表解决简单的应用问题；2）线性表的链式存储结构：单链表上的建表、查找、插入和删除等基本操作；单链表、双链表和循环链表的使用；利用链表解决简单的应用问题。实习题目1）单链表的搜索；2）单链表的递归输出；3）法雷序列的生成；4）大数运算系列。2栈与队列的应用1）顺序栈和链栈上的压栈

9、、弹栈等基本操作；2）顺序队列和链队列上的入队、出队等基本操作；循环队列的使用；3）利用栈和队列解决简单的应用问题。实习题目1）表达式括号匹配问题；2）简单数学计算器的实现；3）火烧连营问题；4）二值图像的像元分组。3树和二叉树及其应用1）二叉树的表示方法、存储方式、三种遍历方式；2）堆的插入、删除、初始化等基本操作；堆排序；3）哈夫曼树及其应用。实习题目二叉树的前序创建、交换等操作练习；2）由遍历结果确定一棵二叉树；3）由字符串构建Huffman树；4）软件压缩/解压缩软件的实现（Huffman算法及应用）；5）磁盘树管理器的实现。4搜索树的应用1）二叉搜索树的基本操作及应用；2）平衡二叉树的基本操作及应用；3）红黑树的基本操作及应用；4）B-树的基本操作及应用。实习题目1）利用BST树统计文献中单词出现的频率；2）电话簿软件的实现（动态查找表算法的应用）；3）英语四级电子辞典的实现（动态查找表算法的应用）。5图及其应用1）图的邻接矩阵和邻