劉遠(yuǎn)剛 鄧 帆 龍穎波

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

1 引言

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

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

2 實(shí)驗(yàn)選題設(shè)計(jì)策略和案例

2.1 實(shí)驗(yàn)選題設(shè)計(jì)策略

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

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

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

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

2.2 實(shí)驗(yàn)選題設(shè)計(jì)案例

2.2.1 選題描述

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

圖1 流域河網(wǎng)抽象表達(dá)及其數(shù)據(jù)存儲結(jié)構(gòu)設(shè)計(jì)

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

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

2.2.2 實(shí)驗(yàn)條件和要求

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

（2）對河流幾何圖形進(jìn)行分段處理，然后建立河網(wǎng)拓?fù)浣Y(jié)構(gòu)，并存儲到鄰接表中，要求在設(shè)計(jì)書中給出河流中心線分段算法和河網(wǎng)拓?fù)浣Y(jié)構(gòu)構(gòu)建算法的流程圖或偽代碼；

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

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

2.2.3 實(shí)驗(yàn)提示

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

圖3 坐標(biāo)文件格式說明

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

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

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

3 結(jié)語

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

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