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

空间数据结构实验
Experiment& Practice of Geo-data Structure
一、课程基本情况
课程总学时：48
实验总学时:16
学 分：3
开课学期：第3学期
课程性质：必修
对应理论课程：空间数据结构
适用专业：地理信息科学
教 材：严蔚敏，吴伟民，数据结构（C语言版），清华大学出版社，2002年。
开课单位：地理与遥感学院 地理信息科学系
二、实验课程的教学目标和任务空间数据结构课程为地理信息科学专业的必备基础课程，为专业必修课。
该课程的教学目标是，通过实验使学生掌握数据结构的理论与方法，学会分析研究各种 数据结构的特性，针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实验的 技能。主要针对地理空间问题的应用背景分析，选择使用常用的通用数据结构与算法，从而 培养地理信息科学专业本科生的程序设计能力。
该课程的任务是，研究对于地理空间问题进行程序设计所涉及的计算机操作的各种对 象，以及它们之间的关系和运算。
该课程的主要内容包括两局部，第一局部为通用数据结构的常规内容，包括线性表、栈 和队列、字符串、数组和广义表、树和二叉树、图，以及查找和排序算法；第二局部为空间 数据结构的一般内容，包括矢量数据结构及其算法，栅格数据结构及其算法，空间索引算法。
该课程的重点为：通用数据结构的存储表示及实现算法；顺序查找、二分查找、分块查 找算法；二分法插入排序、冒泡排序、希尔排序、快速排序算法；行程编码和四叉树的栅格 属性查询算法；四叉树向量数据索引方法；莫顿排序栅格数据索引方法。
三、实验课程的内容和要求
序号
工程名称
所需 学时
内容提要
工程要求
实验类型

必开
选开
实验一
线性表的存储表 示及应用
2
⑴线性表的顺序、链接存储表 示及实现。⑵设计一算法并实 现：对单链表实现就地逆置。
V

验证/设计
实验二
栈的存储表示及 应用
2
⑴栈的顺序、链接存储表示及 实现。（2）十六进制到二进制的 转换。
V

验证/设计
实验三
串的查找
2
对字符串进行查找、匹配功能 实现

V
验证/设计
实验四
稀疏矩阵存储与 压缩实现
2
对稀疏矩阵进行压缩存储，并 实现其基本的矩阵运算功能

V
验证/设计
实验五
二叉树的建立与 前序遍历算法实 现
2
以二叉链表为存储结构，实现 对二叉树的前、中、后序遍历, 写出递归与非递归算法程序。
V

验证/设计
实验六
二叉树的中序遍 历以及后序遍历 算法实现
2
实现对二叉树的中、后序遍 历，写出递归与非递归算法程 序。

V
验证/设计
实验七
图的建立与深度 遍历
3
编写程序，由输入的顶点数目、 弧的数目、各顶点的信息和各 条弧的信息建立有向图的邻接 表；对所建立的有向图进行深 度优先、广度优先遍历。
V

综合/设计
实验八
图的广度遍历
2
对所建立的有向图进行广度优 先遍历。

V
综合/设计
实验九
顺序查找与二分 法查找的实现与 比拟
3
随机生成10000个在指定值域 内的整数，分别用顺序查找法、 二分查找法进行10000次查找 并比拟二个算法。
V

综合/设计
实验十
常用排序算法
4
编写程序实现冒泡排序、希尔 排序、快速排序并进行比拟次 数和交换次数统计。
V

综合/设计

四、课程考核
（1）实验报告的撰写要求：具体要求见实验的内容和要求局部；每个实验工程需要提交1 份实验报告。
（2）实验报告：6次
（3）考核及成绩评定：以平时上机题完成情况和实验报告完成情况进行综合考核。
五、参考书目
1、张铭，王腾蛟，赵海燕，数据结构与算法，高等教育出版社，2008年；
2、李春葆，数据结构（C语言篇）习题与解析，清华大学出版社，2000年；
3、Stephen Wise著，朱定局译，GIS数据结构与算法基础，科学出版社，2012年。