数据结构与算法测绘工程版 教学大纲.doc

数据结构与算法教学大纲英文课程名称：Data Structures and Algorithms课程代码： a041300070课程类别：专业基础课学时：72学分：3.5开课学期：第二学期适用专业：测绘工程专业本科考核方式：考试先修课程：高等数学、C语言程序设计开课单位：地理信息与旅游学院一、课程简介数据结构与算法作为一门独立的课程，最早是美国的一些大学开设的。1968年美国克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。瑞士计算机科学家，PASCAL之父，结构化程序设计的首创者-沃思教授曾指出：“算法+数据结构=程序”，认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。数据结构的研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有着更密切的关系，因此，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构与算法是地理信息系统、测绘工程本科专业中的一门综合性的专业基础课。本课程介绍如何组织数据在计算机中的存储、传递和转换，具体内容包括数组、链接表、栈和队列、树与森林、图、查找、排序等。课程采用C语言作为算法的描述工具，强化数据结构基本知识和程序设计基本能力的双基训练，为后续地理信息系统原理、GIS算法基础等课程的学习打下坚实的基础。 二、教学基本要求与内容安排（一）教学目的与要求教学目的：通过对本课程的系统学习，使学生比较全面了解数据结构与算法知识体系知识，重点熟悉线性结构，树型结构与图型结构的定义、相关操作与算法评价；学生在学完本门课程后应具备一定的实践动手能力，能够自主设计简单数据结构。教学要求：本课程要求学生熟悉C语言基本语法，熟悉结构化程序设计思想，熟悉使用VC开发环境，学生完成该课程的学习后，需掌握线性结构中的顺序表、单链表、栈、队列的定义和使用，需掌握二叉树和图的定义和掌握，需了解数组、字符串、排序算法等知识，能为后续课程打下坚实的基础。（二）教学内容安排教学内容主要由四部分构成。一是线性表，主要讲解顺序表和单链表、栈和队列、串以及数组等；二是树与二叉树，主要讲解树结构与二叉树结构等；三是图，主要图结构与网络结构等；四是排序，主要基本的排序算法。教学内容教学要求教学方法重点()难点()学时分配备注讲课实验上机其他第一章 绪论1、数据结构的基本概念C讲授法0.72、抽象数据类型C讲授法0.53、算法和算法的时间复杂度A讲授法0.84、回顾C语言的指针B讲授法1.01.05、回顾C语言的结构体B讲授法1.01.0第二章 线性表1、线性表的类型定义B讲授法0.52、线性表的顺序存储和实现A讲授法1.52.03、线性表的链式表示和实现A讲授法1.52.04、一元多项式的表示及相加B讲授法0.5第三章 堆栈和队列1、堆栈A讲授法1.52.02、堆栈应用举例A讲授法0.53、队列A讲授法1.52.04、队列的应用举例A讲授法0.5第四章 串1、串类型的定义A讲授法0.52、串的表示和实现B讲授法0.52.03、串的模式匹配算法B讲授法0.52.04、串操作应用举例C讲授法0.5第五章 数组1、数组的定义B讲授法0.52、数组的顺序表示和实现B讲授法0.53、动态数组B讲授法0.34、特殊矩阵的压缩存储B讲授法0.72.0第六章 递归算法1、递归的概念B讲授法0.52、递归算法的设计A讲授法1.02.03、递归算法的时间效率分析C讲授法0.54、递归算法到非递归算法转换C讲授法1.0第七章 广义表1、广义表概述C讲授法0.32、广义表的存储结构B讲授法0.53、广义表的操作实现C讲授法1.22.0第八章 树和二叉树1、树的定义和基本术语B讲授法1.02、二叉树A讲授法2.02.03、遍历二叉树和线索二叉树A讲授法1.02.04、树和森林B讲授法1.05、赫夫曼树及其应用A讲授法1.02.0第九章 图1、图的定义和术语B讲授法0.52、图的存储结构与实现A讲授法0.72.03、图的遍历A讲授法0.84、图的连通性问题A讲授法1.05、最小生成树A讲授法1.02.06、最短路径A讲授法1.02.0第十章 排序1、概述C讲授法0.22、插入排序B讲授法0.51.03、快速排序A讲授法1.01.04、选择排序B讲授法0.51.05、归并排序B讲授法1.01.06、基数排序B讲授法0.57、各种排序方法的比较讨论A讲授法0.3（教学要求：A熟练掌握；B掌握；C了解）三、习题课和课堂讨论内容无。四、实验（实践）内容1、C语言指针与结构体，2课时；2、线性表的表示与实现，4课时；3、栈和队列表示与实现，4课时；4、串与数组表示与实现，6课时；5、递归算法的设计与实现，2课时；6、广义表的存储结构与操作实现，2课时；7、二叉树的表示与实现，6课时；8、图表示与实现，6课时；9、排序算法的实现，4课时；五、成绩考核1、本课程考试方法：笔试；2、本课程最终成绩=平时成绩（课程上机实验，作业及出勤情况）40% +期末考试成绩60%。六、推荐教材和主要参考书：教 材：1 朱战立. 数据结构使用C语言(第4版).北京：电子工业出版社，2009.参考书：1秦玉平 马靖善 等.数据结构（C语言版）（第二版）.北京：清华大学出版社，2012.2 R Krishnamoorthy，G Indirani Kumaravel著. Data Structures using C.北京：清华大学出版社，2003.3 Ro