GIS專業(yè)數(shù)據(jù)結構綜合性實驗選題的設計

劉遠剛 鄧 帆 龍穎波

（長江大學地球科學學院，湖北 武漢 430100）

1 引言

地理信息科學（Geographic Information Science,GIS）是綜合地理學、測繪學、計算機信息技術等學科發(fā)展起來的一門交叉學科，其中計算機程序設計能力的培養(yǎng)是GIS專業(yè)人才培養(yǎng)計劃的重點之一[1]。自20世紀70年代起，國內(nèi)外高校普遍將數(shù)據(jù)結構課程列為計算機相關專業(yè)的必修課，向?qū)W生教授程序設計的基本方法和思想[2,3]。歷時半個世紀，關于數(shù)據(jù)結構課程的教學內(nèi)容和方法研究、教材建設等工作一直是各大專院校計算機類專業(yè)從教工作者孜孜追求的課題。面對如何降低課程學習難度，如何提高學生程序設計能力，如何激發(fā)學生學習興趣和主動性，如何合理規(guī)劃設計教材內(nèi)容等問題，國內(nèi)外同行展開了大量研究，在教學內(nèi)容、教學方法和手段上形成了諸多共識[4-7]。盡管如此，作為GIS專業(yè)的一門專業(yè)基礎課程，我們需要面向GIS專業(yè)學科背景開展教學改革，避免全盤照搬計算機專業(yè)教材內(nèi)容的傳統(tǒng)模式，體現(xiàn)GIS專業(yè)所特有的“空間思維”特色[8,9]，從而本增強本專業(yè)課程體系的系統(tǒng)性，幫助學生們盡早建立GIS學科概念，樹立積極的專業(yè)思想，讓學生切實體會課程教授的數(shù)據(jù)結構知識是為專業(yè)應用和實踐服務的。

數(shù)據(jù)結構課程的綜合實驗是GIS專業(yè)學生學完數(shù)據(jù)結構理論課程后開展的綜合性實踐課，其目的是鞏固課堂所學書本知識，培養(yǎng)學生運用數(shù)據(jù)結構的知識解決實際問題的能力。因此，有必要結合GIS專業(yè)問題設計實驗選題，從而優(yōu)化設計實踐教學內(nèi)容，引導低年級學生盡快專注于專業(yè)問題的探究[10]。鑒于目前尚缺乏面向GIS專業(yè)數(shù)據(jù)結構綜合實驗綜合案例，結合科研項目的部分成果，本文設計了一個體現(xiàn)GIS空間思維的全新實驗案例——河網(wǎng)干流提取，以此為例給出此類選題的基本思路和設計模板，為同類教學案例的設計提供參考。

2 實驗選題設計策略和案例

2.1 實驗選題設計策略

GIS學科中的地圖制圖、遙感分析、全球定位導航技術等研究領域均存在大量與數(shù)據(jù)結構相關的經(jīng)典應用問題，例如矢量數(shù)據(jù)的多邊形自動生成、柵格數(shù)據(jù)四叉樹編碼、道路網(wǎng)的最優(yōu)路徑導航、地圖制圖中的四色渲染等問題。作為一門程序設計類綜合性實驗課程，數(shù)據(jù)結構綜合實驗需要學生運用算法和程序設計的通用模式來指導實驗過程的實施。

相應的選題設計，需要引導學生首先要采用數(shù)據(jù)結構的形式化表達方式簡明嚴格地定義和描述問題，然后用流程圖或偽代碼設計求解方法，最后用計算機編程語言來實現(xiàn)這種求解方法，在經(jīng)過測試定型后編寫必要的軟件設計文檔。此過程中，GIS專業(yè)學生需要將數(shù)據(jù)結構分析設計方法與GIS專業(yè)問題融會貫通。

然而，GIS專業(yè)問題對低年級本科生還有一定難度，需要教師在選題設計中以通俗易懂的形式引入相關專業(yè)概念，給出比較詳細的問題描述、約束條件和解題思路。學生在這些提示信息的幫助下通過文獻調(diào)研和算法設計，逐步深入專業(yè)知識的學習和算法程序的實踐，最終解決問題。

本文在此類選題的設計上，主要考慮實驗選題描述、實驗條件和要求、實驗提示三個方面。其中選題描述主要用于概述選題相關的GIS專業(yè)概念和問題，給出問題中涉及對象的簡要定義和描述，為學生解題過程中進行概念模型的設計提供基本依據(jù)；實驗條件和要求主要羅列完成選題的設計與實現(xiàn)需要用到的數(shù)據(jù)、算法、參數(shù)和限定條件，以及提出具體的實驗要求；實驗提示主要給出選題中需要用到算法的設計思路、關鍵步驟和數(shù)據(jù)結構，必要時給出程序偽代碼、流程圖或部分輔助程序等材料。下面以“河網(wǎng)干流提取”問題為例介紹此類實驗選題的設計思路和具體案例。

2.2 實驗選題設計案例

2.2.1 選題描述

在基于GIS的水文分析中，河網(wǎng)水系特征的準確提取是一個熱點研究方向。一條河流通常只有一個河口而有多個河源，而所謂“正源”則是在所有河源中選擇一個最重要的河源。確定何為重要則靠一些所謂原則，主要是“河流惟長”“水量惟大”“河源惟直”三原則，以及政治、歷史等方面的原則。實踐中一般以河長為主要標準，“正源”到河口經(jīng)過的水量最大、河道最順直的路徑就構成了河流的“干流”，其它匯入“干流”的河流為“支流”，例如圖1（A）所示。本實驗選題要求自動提取流域的干流路徑。為此，首先要求構建流域河網(wǎng)的網(wǎng)絡結構，如圖1（B）所示，河流在地圖中一般以其河道中心線表達其地理位置，通常并沒有整個流域各河段的網(wǎng)絡拓撲信息。為了便于進一步分析，需要對河網(wǎng)的幾何圖形進行處理，將相交的河道中心線打斷，通過關聯(lián)節(jié)點將整個河網(wǎng)關聯(lián)，構成一個網(wǎng)絡結構圖，見圖1（C），其對應的存儲結構可采用鄰接表形式，見圖1（D）。

圖1 流域河網(wǎng)抽象表達及其數(shù)據(jù)存儲結構設計

在此基礎上，即可采用最短路徑算法求得整個流域的干流路徑。為此，首先需要確定最短路徑的起點和終點，即整個河網(wǎng)的“正源”和“河口”，如圖2所示，通過整個流域的最小外包矩形，可確定流域的“正源”和“河口”，然后求它們之間的最短路徑即為干流的路徑。

圖2 確定干流的源頭和河口并求干流路徑

2.2.2 實驗條件和要求

（1）本題以文本文件格式提供一個流域內(nèi)各條河流的幾何圖形坐標，要求讀取文件中的這些圖形信息，并且以順序表結構存儲各條河流中心線的坐標序列；

（2）對河流幾何圖形進行分段處理，然后建立河網(wǎng)拓撲結構，并存儲到鄰接表中，要求在設計書中給出河流中心線分段算法和河網(wǎng)拓撲結構構建算法的流程圖或偽代碼；

（3）生成流域最小外接矩形，根據(jù)流域的最小外接矩形確定“正源”和“河口”，要求在設計書中給出生成最小外接矩形算法的流程圖或偽代碼；

（4）求干流路徑，將干流路徑的坐標輸出，并計算其總長度，要求在設計書中給出干流路徑提取算法的的流程圖或偽代碼。

2.2.3 實驗提示

（1）數(shù)據(jù)的讀取與組織。圖3為存儲河流各段中心線的坐標序列的文本文件，每個圖形以“#”作為開始標記，之后是該圖形對應的各頂點的坐標值，每行表示一對坐標及其高程，每條河流中心線由一個(x,y,h)的線性序列表示。建議以順序表方式存儲河流中心線坐標，其中每一條中心線用一個順序表存儲，以便后續(xù)進一步進行河段的生成和河網(wǎng)的構建等操作。具體用于存儲河段中心線的順序表可由如下代碼定義：

圖3 坐標文件格式說明

（2）構建河網(wǎng)。原始數(shù)據(jù)中僅僅提供了河段坐標信息，并沒有事先建立河流的網(wǎng)絡拓撲關系，題目給出的河段坐標序列也不一定是基本河段，見圖1（B），還需要根據(jù)這些線段之間的相交關系將部分相交的河段打斷，提取河網(wǎng)中的交叉點。最后，以打斷后的河段集合為邊，以河段端點和新生成的交叉點的并集合為結點，構建河網(wǎng)結構圖，見圖1（C）、圖1（D）。此過程中，折線的求交打斷算法、河網(wǎng)的拓撲構建算法是關鍵。折線求交是GIS圖形處理中的基本算法，其主要思路是：將原始文件中讀入的河段信息兩兩求交，如果兩條折線存在相交的，則打斷它們，并將它們的交叉點記錄下來。構建河網(wǎng)的過程就是將河網(wǎng)中的端點、交叉點與相關聯(lián)的河段建立關聯(lián)的過程。首先需要將端點和交叉點合并成網(wǎng)絡模型中結點的集合，然后依次針對每個頂點搜尋與之關聯(lián)的河段，并將他們關聯(lián)起來。建議學生采用圖1（D）所示的鄰近表存儲河網(wǎng)數(shù)據(jù)，下面結合教材中圖的鄰近表的存儲結構可給出河網(wǎng)的存儲結構定義：

（3）確定流域的“正源”和“河口”。如圖2所示，整個流域的河網(wǎng)可由其最小外接矩形的長軸確定其流水主方向，河流的干流路徑一般沿著這一主方向延伸，即“正源”和“河口”的連線方向與最小外接矩形的長軸方向基本一致。因此，分別將離最小外接矩形兩條短邊的距離最近的兩個結點作為整個流域的“正源”和“河口”，即干流路徑的起點和終點。根據(jù)“水往低處流”的常識，進一步可以確定高程值大的為起點，高程值小的為終點。此部分的難點在于如何獲得整個流域的最小外接矩形。二維圖形（點群、線群和面群）的最小外接矩形問題，可以用這些幾何對象的凸殼的最小外接矩形代表。凸殼生成算法和凸殼的最小外接矩形生成算法，在GIS專業(yè)領域已經(jīng)有了較多成熟算法，例如經(jīng)典的“旋轉(zhuǎn)卡殼”算法，學生可通過查閱相關文獻或查找相關開源算法庫學習此類算法的設計思路和解決方案。

（4）確定干流路徑。最后以得到的“正源”和“河口”為起止點，采用最短路徑算法求整個流域的干流路徑。相關最短路徑算法較多，比如，數(shù)據(jù)結構理論課中已經(jīng)介紹的Dijkstra算法和Floyd算法，以及其他常用算法包括A*算法等。

3 結語

數(shù)據(jù)結構是GIS專業(yè)的一門基礎必修課程，重在培養(yǎng)學生程序設計思維方法和編程技能，需要在教學過程中加強理論與實踐的結合。而目前GIS專業(yè)數(shù)據(jù)結構實驗教學中普遍照搬計算機專業(yè)教材內(nèi)容，忽視了本專業(yè)“空間思維”的特色。因此，提出了在數(shù)據(jù)結構綜合性實驗環(huán)節(jié)，將GIS專業(yè)問題引入實驗選題，實現(xiàn)數(shù)據(jù)結構綜合實驗課程與本專業(yè)科學問題的深度融合。

為此，以“河網(wǎng)干流提取”問題為例，系統(tǒng)闡述了面向GIS專業(yè)綜合性實驗選題設計的基本思路和具體過程，從而為類似教學案例的設計提供參考。本選題的實驗內(nèi)容覆蓋了數(shù)據(jù)結構中線性表、圖、最短路徑等經(jīng)典數(shù)據(jù)結構和算法的應用，同時也引入了河網(wǎng)干流、凸殼、最小外接矩形、拓撲結構構建等GIS專業(yè)的基本概念和方法，通過這一策略增強了GIS專業(yè)課程的系統(tǒng)性，更能促進本專業(yè)學生學科概念和專業(yè)思想的形成。