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

空间数据结构Geo-data Structure一、课程基本情况课程类别：专业主干课课程学分：3学分课程总学时：48学时，其中讲课：32学时，实验（含上机）：16学时，课外 学时课程性质：必修开课学期：第3学期先修课程：计算机基础、C语言适用专业：地理信息科学教 材：严蔚敏，吴伟民，数据结构（C语言版），清华大学出版社，2002年。开课单位：地理与遥感学院 地理信息科学系二、课程性质、教学目标和任务空间数据结构课程为地理信息科学专业的必备基础课程，为专业必修课。该课程的教学目标是，使学生掌握解决地理空间问题的程序设计工具和技术，即学会空 间数据的组织方法和地理空间世界问题在计算机内部的表示方法，针对地理空间问题的应用 背景分析，选择介绍常用的通用数据结构与算法，并且增加空间数据结构与算法，从而培养 地理信息科学专业本科生的程序设计能力。该课程的任务是,研究对于地理空间问题进行程序设计所涉及的计算机操作的各种对象 （包含空间对象），以及它们之间的关系和运算。该课程的主要内容包括两局部，第一局部为通用数据结构的常规内容，包括线性表、栈 和队列、字符串、数组和广义表、树和二叉树、图，以及查找和排序算法；第二局部为空间 数据结构的一般内容，包括矢量数据结构及其算法，栅格数据结构及其算法，空间索引算法。该课程的重点为：通用数据结构的存储表示及实现算法；顺序查找、二分查找、分块查 找算法；二分法插入排序、冒泡排序、希尔排序、快速排序算法；线与多边形的矢量算法; 行程编码和四叉树的栅格属性查询算法；栅格面积计算算法；四叉树向量数据索引方法；莫 顿排序栅格数据索引方法。三、教学内容和要求第1章绪论（2学时）（1）了解数据结构的三个方面：逻辑结构、存储结构、运算；（2）理解算法的概念和特性；（3）掌握算法的描述方法；（4） 了解算法分析的内容；重点：算法的描述方法；难点：算法分析的内容。第2章线性表（2学时）（1）理解线性表的基本概念，线性表有关的术语，线性表的特性;（2）熟悉线性表的抽象数据类型定义；（3）掌握线性表的顺序存储和链接存储表示及实现；重点：线性表的顺序存储和链接存储表示及实现；难点：线性表的链接存储表示及实现。第3章栈和队列（2学时）（1）理解栈的基本概念，栈有关的术语，栈的特性；（2）熟悉栈的抽象数据类型定义；（3）掌握栈的顺序存储和链接存储表示及实现；（4）理解队列的基本概念，队列有关的术语，队列的特性；（5）熟悉队列的抽象数据类型定义；（6）掌握队列的顺序存储和链接存储表示及实现；重点：栈的链接存储表示及实现；队列的链接存储表示及实现；难点：栈的链接存储表示及实现；队列的链接存储表示及实现。第4章字符串（2学时）（1）理解串的基本概念，串有关的术语，串的特性；（2）熟悉串的抽象数据类型定义；（3）掌握串的存储表示及实现；（4）理解串的模式匹配运算。重点：串的存储表示及实现；难点：串的模式匹配运算。第5章数组和广义表（2学时）（1）理解数组的定义，数组的顺序表示和实现；（2） 了解对称矩阵、三角矩阵、稀疏矩阵的压缩存储；（3） 了解广义表的定义，广义表的链式存储结构。重点：对称矩阵、三角矩阵、稀疏矩阵的压缩存储；难点：广义表的链式存储结构。第6章树和二叉树（5学时）（1）理解树的基本概念，树有关的术语，树的特性；（2）熟悉树的抽象数据类型定义；（3） 了解树的存储表示；（4）理解二叉树的基本概念，二叉树有关的术语，二叉树的特性;（5）熟悉二叉树的抽象数据类型定义；（6）掌握二叉树的顺序与链接存储表示；（7）掌握二叉树的遍历运算及实现；（8） 了解森林与二叉树的转换；（9） 了解树和森林的遍历。重点：二叉树的顺序与链接存储表示；二叉树的遍历运算及实现；难点：森林与二叉树的转换。第7章图（3学时）（1）理解图的基本概念，图有关的术语，图的特性；（2）熟悉图的抽象数据类型定义；（3）掌握图的邻接矩阵、邻接表存储表示；（4）理解图的深度优先遍历、广度优先遍历算法；重点：图的邻接矩阵、邻接表存储表示；难点：图的深度优先遍历、广度优先遍历算法。第8章查找（4学时）（1）理解查找的定义及相关概念；（2）掌握：顺序查找，二分查找，分块查找；（3）掌握：二叉排序树，平衡二叉树；（4） 了解：B-树、B+树的概念及特点；（5） 了解哈希表及其查找。重点：顺序查找，二分查找，分块查找；难点：二叉排序树，平衡二叉树。第9章排序（4学时）（1）理解排序的定义及相关概念；（2）掌握以下常用的内排序方法：直接插入排序，二分法插入排序，直接选择排序，冒泡 排序，希尔排序，快速排序；（3） 了解常用内排序方法的特点：时间复杂度，空间复杂度。重点：二分法插入排序，冒泡排序，希尔排序，快速排序；难点：冒泡排序，希尔排序，快速排序。第10章矢量数据结构（2学时）（1）熟悉点、线的存储；（2）熟悉多边形的存储；（3）掌握线的矢量算法；（4）掌握多边形的矢量算法。重点：线的矢量算法；多边形的矢量算法;难点：多边形的矢量算法。第11章栅格数据结构（2学时）（1）熟悉行程编码和四叉树；（2）掌握行程编码和四叉树的栅格属性查询算法；（3）掌握栅格面积计算算法。重点：行程编码和四叉树的栅格属性查询算法；栅格面积计算算法；难点：栅格面积计算算法。第12章空间索引（2学时）（1）熟悉基于K-D树建立索引的方法；（2）掌握利用四叉树建立向量数据索引的方法；（3）掌握利用莫顿排序建立栅格数据索引的方法。重点：利用四叉树建立向量数据索引的方法；利用莫顿排序建立栅格数据索引的方法；难点：利用四叉树建立向量数据索引的方法；利用莫顿排序建立栅格数据索引的方法。四、课程考核（1）作业等：作业：8次，课程论文：1篇；（2）考核方式：闭卷考试（3）总评成绩计算方式：平时考勤成绩、期中考试成绩、实验成绩各占20%,期末考试成绩占40% o五、参考书目1、张铭，王腾蛟，赵海燕，数据结构与算法，高等教育出版社，2008年；2、李春葆，数据结构（C语言篇）习题与解析，清华大学出版社，2000年；3、Stephen Wise著,朱定局译，GIS数据结构与算法基础,科学出版社，2012年。