《空间数据结构》课程教学大纲

1、空间数据结构教学大纲一、说 明适用专业地理信息科学先修课程计算机应用基础，C/C+高级语言程序设计总学时80（48+32）总学分4（一）本课程的目的、要求空间数据结构是本学科必修的一门专业基础课程。其课程目的是介绍一些最常用的空间数据结构,阐明空间数据结构内在的逻辑关系,讨论它们在计算机中的存储表示,并结合各种典型应用说明它们在进行各种操作时的动态性质及实际的执行算法，可为学生深刻理解数据模型提供了基础,而且更重要的是进一步提高软件设计和编程水平。因此要求学生具备一定的计算机应用基础和C/C+语言编程能力,这将是学好本课程的基础。（二）内容选取和实施中注意的问题1.在内容选取方面，在反映空间数

2、据结构各个方面的内容前提下，突出概念、思想、方法和应用。在结构安排方面，以逻辑结构为主线，分成线性结构和非线性结构两部分。2.在实施方面，在保证课程内容完整性的前提下，把难度较大、论述较烦琐的思想内容用具体的实例进行介绍，有利于学生的掌握。（三）教学方法授课+上机实验（四）考核方式课程成绩由平时成绩、实验成绩和期末考试成绩组成。平时成绩包括平时上课的到勤情况和课堂回答问题等，占课程总成绩的10%；实验成绩包括作业、课程实验等，占课程总成绩的30%；期末考试采取闭卷考试的形式，占课程总成绩的60%； （五）教学内容与学时分配教学章节教学内容学时安排备注1概论 32线性表103栈和队列104串65

3、树156图167排序108查找10二、大 纲 内 容第一章 概论1什么是空间数据结构2数据的逻辑结构和数据的存储结构3数据的运算4算法和算法的衡量说明和要求：（1）领会数据，数据元素和数据项的概念及其相互间的关系。（2）清楚空间数据结构的逻辑结构，存储结构的联系与区别以及在空间数据结构上施加的运算及其实现。重点掌握逻辑结构和空间数据结构在概念上的联系与区别。（3）理解抽象数据类型的概念。（4）重点掌握对算法进行复杂度分析的方法。第二章 线性表 1线性表类型的定义 2线性表的顺序映像实现 3线性表的链式映像实现说明和要求：（1）理解线性结构的基本特征。（2）重点掌握线性表的顺序映像的具体实现方法

4、。（3）重点掌握线性表的链式映像的具体实现方法。（4）理解顺序映像和链式映像方法实现线性表时的插入和删除的时间复杂度分析。第三章 栈和队列1栈的概念和表示2栈的应用举例3栈类型的实现4队列的类型定义 5链队列和循环队列说明和要求：（1）理解栈和队列结构的操作特点。（2）重点掌握几种典型的栈的应用实例。（3）理解栈的实现方法。（4）掌握链队列和循环队列的操作特点，重点掌握队列的队满、队空的判断。第四章 串1串的类型定义2串的模式匹配说明和要求：（1）重点掌握串的简单模式匹配算法。（2）重点理解串的改进的KMP算法的思想并会手工计算。第五章 树1树的概念 2二叉树的概念、存储和遍历3线索二叉树的概

5、念4树和森林的遍历和应用说明和要求：（1）深刻理解树的定义、术语。（2）领会树的各种存储结构。（3）深刻理解二叉树的定义,性质及其存储方法。（4）领会二叉树的二叉链表存储方式,结点结构和类型定义。（5）重点理解二叉树的三种遍历算法，并掌握由先序和中序构造二叉树的方法。（6）掌握将树、森林和二叉树相互转换的方法。第六章 图1图的概念 2图的存储形式3图的连通性问题4图的最短路径说明和要求：（1）重点理解图的基本概念及术语。（2）掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法，重点掌握邻接矩阵的表示方法。（3） 熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想,步骤,并能列

6、出在两种存储结构上按上述两种遍历算法得到的序列。（4）领会并重点掌握最短路径的算法思想。（5）重点区分连通分量和强连通分量的区别。（6）重点掌握计算图中源点到其它点和每对顶点之间的最短路径的方法。第七章 排序1排序的分类2几种排序算法的思想和复杂度分析说明和要求：（1）掌握排序的概念和种类。（2）领会各种排序算法的算法思想并会实现和分析时间复杂度，以插入排序、冒泡排序和选择排序为重点。（3）能够根据数据的存储结构选择合适的排序算法。第八章 查找1表的查找的概念，ASL的定义2哈希表的构造和处理冲突的方法说明和要求：（1）掌握计算ASL的方法。（2）掌握哈希表的构造方法。（3）重点掌握哈希表构造过程中冲突处理的解决办法。（4）理解哈希表的插入和删除的处理方法。实验目录1顺序表、链表的删除算法实现。2设计停车场管理的算法思想。3顺序栈的存储、插入和删除的算法实现。4分组设计二叉树中由顺序输入创建二叉树链式存储结构的算法思想并尽可能的实现程序。5讨论每组设计的算法思想的性能和可行性，再改进。6插入排序算法的实现。7在顺序表中查找指定数据的算法的实现。三、教材和主要参考书1. 严蔚敏，吴伟民. 数据结构（C语言版）.清华大学出版社,2011年.2. 耿国华.数据结构C语言描述.高等教育出版社，2005年.3. 美K. N