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

1、空间数据结构实验Experiment& Practice of Geo-data Structure一、课程基本情况 课程总学时：48实验总学时：16学分：3开课学期：第3学期 课程性质：必修 对应理论课程：空间数据结构适用专业：地理信息科学教 材：严蔚敏，吴伟民，数据结构（C语言版），清华大学出版社，2002年。开课单位：地理与遥感学院 地理信息科学系二、实验课程的教学目标和任务空间数据结构课程为地理信息科学专业的必备基础课程，为专业必修课。该课程的教学目标是，通过实验使学生掌握数据结构的理论与方法，学会分析研究各种数据结构的特性，针对问题的不同选择合适的数据结构，提高算法设计的能力和动手实

2、验的技能。主要针对地理空间问题的应用背景分析，选择使用常用的通用数据结构与算法，从而培养地理信息科学专业本科生的程序设计能力。该课程的任务是，研究对于地理空间问题进行程序设计所涉及的计算机操作的各种对象，以及它们之间的关系和运算。该课程的主要内容包括两部分，第一部分为通用数据结构的常规内容，包括线性表、栈和队列、字符串、数组和广义表、树和二叉树、图，以及查找和排序算法；第二部分为空间数据结构的一般内容，包括矢量数据结构及其算法，栅格数据结构及其算法，空间索引算法。该课程的重点为：通用数据结构的存储表示及实现算法；顺序查找、二分查找、分块查找算法；二分法插入排序、冒泡排序、希尔排序、快速排序算法

3、；行程编码和四叉树的栅格属性查询算法；四叉树向量数据索引方法；莫顿排序栅格数据索引方法。三、实验课程的内容和要求序号项目名称所需学时内 容 提 要项目要求实验类型必开选开实验一线性表的存储表示及应用2(1)线性表的顺序、链接存储表示及实现。(2)设计一算法并实现：对单链表实现就地逆置。验证/设计实验二栈的存储表示及应用2(1)栈的顺序、链接存储表示及实现。(2)十六进制到二进制的转换。验证/设计实验三串的查找2对字符串进行查找、匹配功能实现验证/设计实验四稀疏矩阵存储与压缩实现2对稀疏矩阵进行压缩存储，并实现其基本的矩阵运算功能验证/设计实验五二叉树的建立与前序遍历算法实现2以二叉链表为存储结

4、构，实现对二叉树的前、中、后序遍历，写出递归与非递归算法程序。验证/设计实验六二叉树的中序遍历以及后序遍历算法实现2 实现对二叉树的中、后序遍历，写出递归与非递归算法程序。验证/设计实验七图的建立与深度遍历 3编写程序，由输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表；对所建立的有向图进行深度优先、广度优先遍历。综合/设计实验八图的广度遍历 2对所建立的有向图进行广度优先遍历。综合/设计实验九顺序查找与二分法查找的实现与比较3随机生成10000个在指定值域内的整数，分别用顺序查找法、二分查找法进行10000次查找并比较二个算法。综合/设计实验十常用排序算法4编写程序实现冒泡排序、希尔排序、快速排序并进行比较次数和交换次数统计。综合/设计四、课程考核（1）实验报告的撰写要求：具体要求见实验的内容和要求部分；每个实验项目需要提交1份实验报告。（2）实验报告：6 次（3）考核及成绩评定：以平时上机题完成情况和实验报告完成情况进行综合考核。五、参考书目1、张铭，王腾蛟，赵海燕，数据结构与算法，高等教育出版社，2008年；2、李春葆，数据结构（