GIS专业数据结构综合性实验选题的设计

刘远刚 邓 帆 龙颖波

（长江大学地球科学学院，湖北 武汉 430100）

1 引言

地理信息科学（Geographic Information Science,GIS）是综合地理学、测绘学、计算机信息技术等学科发展起来的一门交叉学科，其中计算机程序设计能力的培养是GIS专业人才培养计划的重点之一[1]。自20世纪70年代起，国内外高校普遍将数据结构课程列为计算机相关专业的必修课，向学生教授程序设计的基本方法和思想[2,3]。历时半个世纪，关于数据结构课程的教学内容和方法研究、教材建设等工作一直是各大专院校计算机类专业从教工作者孜孜追求的课题。面对如何降低课程学习难度，如何提高学生程序设计能力，如何激发学生学习兴趣和主动性，如何合理规划设计教材内容等问题，国内外同行展开了大量研究，在教学内容、教学方法和手段上形成了诸多共识[4-7]。尽管如此，作为GIS专业的一门专业基础课程，我们需要面向GIS专业学科背景开展教学改革，避免全盘照搬计算机专业教材内容的传统模式，体现GIS专业所特有的“空间思维”特色[8,9]，从而本增强本专业课程体系的系统性，帮助学生们尽早建立GIS学科概念，树立积极的专业思想，让学生切实体会课程教授的数据结构知识是为专业应用和实践服务的。

数据结构课程的综合实验是GIS专业学生学完数据结构理论课程后开展的综合性实践课，其目的是巩固课堂所学书本知识，培养学生运用数据结构的知识解决实际问题的能力。因此，有必要结合GIS专业问题设计实验选题，从而优化设计实践教学内容，引导低年级学生尽快专注于专业问题的探究[10]。鉴于目前尚缺乏面向GIS专业数据结构综合实验综合案例，结合科研项目的部分成果，本文设计了一个体现GIS空间思维的全新实验案例——河网干流提取，以此为例给出此类选题的基本思路和设计模板，为同类教学案例的设计提供参考。

2 实验选题设计策略和案例

2.1 实验选题设计策略

GIS学科中的地图制图、遥感分析、全球定位导航技术等研究领域均存在大量与数据结构相关的经典应用问题，例如矢量数据的多边形自动生成、栅格数据四叉树编码、道路网的最优路径导航、地图制图中的四色渲染等问题。作为一门程序设计类综合性实验课程，数据结构综合实验需要学生运用算法和程序设计的通用模式来指导实验过程的实施。

相应的选题设计，需要引导学生首先要采用数据结构的形式化表达方式简明严格地定义和描述问题，然后用流程图或伪代码设计求解方法，最后用计算机编程语言来实现这种求解方法，在经过测试定型后编写必要的软件设计文档。此过程中，GIS专业学生需要将数据结构分析设计方法与GIS专业问题融会贯通。

然而，GIS专业问题对低年级本科生还有一定难度，需要教师在选题设计中以通俗易懂的形式引入相关专业概念，给出比较详细的问题描述、约束条件和解题思路。学生在这些提示信息的帮助下通过文献调研和算法设计，逐步深入专业知识的学习和算法程序的实践，最终解决问题。

本文在此类选题的设计上，主要考虑实验选题描述、实验条件和要求、实验提示三个方面。其中选题描述主要用于概述选题相关的GIS专业概念和问题，给出问题中涉及对象的简要定义和描述，为学生解题过程中进行概念模型的设计提供基本依据；实验条件和要求主要罗列完成选题的设计与实现需要用到的数据、算法、参数和限定条件，以及提出具体的实验要求；实验提示主要给出选题中需要用到算法的设计思路、关键步骤和数据结构，必要时给出程序伪代码、流程图或部分辅助程序等材料。下面以“河网干流提取”问题为例介绍此类实验选题的设计思路和具体案例。

2.2 实验选题设计案例

2.2.1 选题描述

在基于GIS的水文分析中，河网水系特征的准确提取是一个热点研究方向。一条河流通常只有一个河口而有多个河源，而所谓“正源”则是在所有河源中选择一个最重要的河源。确定何为重要则靠一些所谓原则，主要是“河流惟长”“水量惟大”“河源惟直”三原则，以及政治、历史等方面的原则。实践中一般以河长为主要标准，“正源”到河口经过的水量最大、河道最顺直的路径就构成了河流的“干流”，其它汇入“干流”的河流为“支流”，例如图1（A）所示。本实验选题要求自动提取流域的干流路径。为此，首先要求构建流域河网的网络结构，如图1（B）所示，河流在地图中一般以其河道中心线表达其地理位置，通常并没有整个流域各河段的网络拓扑信息。为了便于进一步分析，需要对河网的几何图形进行处理，将相交的河道中心线打断，通过关联节点将整个河网关联，构成一个网络结构图，见图1（C），其对应的存储结构可采用邻接表形式，见图1（D）。

图1 流域河网抽象表达及其数据存储结构设计

在此基础上，即可采用最短路径算法求得整个流域的干流路径。为此，首先需要确定最短路径的起点和终点，即整个河网的“正源”和“河口”，如图2所示，通过整个流域的最小外包矩形，可确定流域的“正源”和“河口”，然后求它们之间的最短路径即为干流的路径。

图2 确定干流的源头和河口并求干流路径

2.2.2 实验条件和要求

（1）本题以文本文件格式提供一个流域内各条河流的几何图形坐标，要求读取文件中的这些图形信息，并且以顺序表结构存储各条河流中心线的坐标序列；

（2）对河流几何图形进行分段处理，然后建立河网拓扑结构，并存储到邻接表中，要求在设计书中给出河流中心线分段算法和河网拓扑结构构建算法的流程图或伪代码；

（3）生成流域最小外接矩形，根据流域的最小外接矩形确定“正源”和“河口”，要求在设计书中给出生成最小外接矩形算法的流程图或伪代码；

（4）求干流路径，将干流路径的坐标输出，并计算其总长度，要求在设计书中给出干流路径提取算法的的流程图或伪代码。

2.2.3 实验提示

（1）数据的读取与组织。图3为存储河流各段中心线的坐标序列的文本文件，每个图形以“#”作为开始标记，之后是该图形对应的各顶点的坐标值，每行表示一对坐标及其高程，每条河流中心线由一个(x,y,h)的线性序列表示。建议以顺序表方式存储河流中心线坐标，其中每一条中心线用一个顺序表存储，以便后续进一步进行河段的生成和河网的构建等操作。具体用于存储河段中心线的顺序表可由如下代码定义：

图3 坐标文件格式说明

（2）构建河网。原始数据中仅仅提供了河段坐标信息，并没有事先建立河流的网络拓扑关系，题目给出的河段坐标序列也不一定是基本河段，见图1（B），还需要根据这些线段之间的相交关系将部分相交的河段打断，提取河网中的交叉点。最后，以打断后的河段集合为边，以河段端点和新生成的交叉点的并集合为结点，构建河网结构图，见图1（C）、图1（D）。此过程中，折线的求交打断算法、河网的拓扑构建算法是关键。折线求交是GIS图形处理中的基本算法，其主要思路是：将原始文件中读入的河段信息两两求交，如果两条折线存在相交的，则打断它们，并将它们的交叉点记录下来。构建河网的过程就是将河网中的端点、交叉点与相关联的河段建立关联的过程。首先需要将端点和交叉点合并成网络模型中结点的集合，然后依次针对每个顶点搜寻与之关联的河段，并将他们关联起来。建议学生采用图1（D）所示的邻近表存储河网数据，下面结合教材中图的邻近表的存储结构可给出河网的存储结构定义：

（3）确定流域的“正源”和“河口”。如图2所示，整个流域的河网可由其最小外接矩形的长轴确定其流水主方向，河流的干流路径一般沿着这一主方向延伸，即“正源”和“河口”的连线方向与最小外接矩形的长轴方向基本一致。因此，分别将离最小外接矩形两条短边的距离最近的两个结点作为整个流域的“正源”和“河口”，即干流路径的起点和终点。根据“水往低处流”的常识，进一步可以确定高程值大的为起点，高程值小的为终点。此部分的难点在于如何获得整个流域的最小外接矩形。二维图形（点群、线群和面群）的最小外接矩形问题，可以用这些几何对象的凸壳的最小外接矩形代表。凸壳生成算法和凸壳的最小外接矩形生成算法，在GIS专业领域已经有了较多成熟算法，例如经典的“旋转卡壳”算法，学生可通过查阅相关文献或查找相关开源算法库学习此类算法的设计思路和解决方案。

（4）确定干流路径。最后以得到的“正源”和“河口”为起止点，采用最短路径算法求整个流域的干流路径。相关最短路径算法较多，比如，数据结构理论课中已经介绍的Dijkstra算法和Floyd算法，以及其他常用算法包括A*算法等。

3 结语

数据结构是GIS专业的一门基础必修课程，重在培养学生程序设计思维方法和编程技能，需要在教学过程中加强理论与实践的结合。而目前GIS专业数据结构实验教学中普遍照搬计算机专业教材内容，忽视了本专业“空间思维”的特色。因此，提出了在数据结构综合性实验环节，将GIS专业问题引入实验选题，实现数据结构综合实验课程与本专业科学问题的深度融合。

为此，以“河网干流提取”问题为例，系统阐述了面向GIS专业综合性实验选题设计的基本思路和具体过程，从而为类似教学案例的设计提供参考。本选题的实验内容覆盖了数据结构中线性表、图、最短路径等经典数据结构和算法的应用，同时也引入了河网干流、凸壳、最小外接矩形、拓扑结构构建等GIS专业的基本概念和方法，通过这一策略增强了GIS专业课程的系统性，更能促进本专业学生学科概念和专业思想的形成。