GIS專業(yè)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計教學(xué)內(nèi)容優(yōu)化

龍穎波　劉遠(yuǎn)剛　何貞銘　蔡永香　李功權(quán)　鄧帆

摘? 要： GIS專業(yè)的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實踐教學(xué)，目標(biāo)是培養(yǎng)學(xué)生解決實際問題的能力，在教學(xué)內(nèi)容上還需兼顧數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識與GIS專業(yè)問題的銜接與融合，從而體現(xiàn)GIS專業(yè)特色。文章針對數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實踐教學(xué)，在傳統(tǒng)教學(xué)內(nèi)容中引入GIS專業(yè)的經(jīng)典問題作為有益補充;設(shè)計了新的課程設(shè)計選題方案，向?qū)W生提供針對不同層次教學(xué)目標(biāo)的三類選題，即基礎(chǔ)題、一般應(yīng)用題和GIS專業(yè)應(yīng)用題;并以柵格數(shù)據(jù)四叉樹壓縮編碼與解碼問題為例，詳細(xì)說明將數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識與GIS專業(yè)經(jīng)典問題結(jié)合出題的可行性、設(shè)計思路、實現(xiàn)手段及其對教學(xué)的促進作用。

關(guān)鍵詞： 數(shù)據(jù)結(jié)構(gòu); 課程設(shè)計; 地理信息科學(xué); 四叉樹編碼

中圖分類號：G642? ? ? ? ? 文獻標(biāo)志碼：A? ? ?文章編號：1006-8228（2019）12-81-04

Optimizing the teaching content of data structure practicum for GIS specialty

Long Yingbo， Liu Yuangang， He Zhenming， Cai Yongxiang， Li Gongquan， Deng fan

（School of Geosciences， Yangtze University， Wuhan， Hubei 430100， China）

Abstract： The practicum of data structure （DS） for students majoring in geographical information science （GIS） aims at cultivating students' ability to solve practical problems， but also should give consideration to the connection and integration of basic knowledge of DS and professional problems of GIS in the teaching content， so as to embody the characteristics of GIS. This paper introduces some classical problems of GIS into the traditional teaching content of course project of DS as a useful supplement. To this end， a new topic-choosing plan is designed to provide students with three types of topics， i.e. basic topics， general application topics and GIS professional application topics， for different levels of teaching objectives. Taking the quadtree compression coding and decoding of raster data as an example， the feasibility， design ideas， implement measures and promoting effects of the integration of basic knowledge of DS and professional problems of GIS in the teaching content are described in detail.

Key words： geographical information science （GIS）; practicum; data structure （DS）; quadtree coding

0 引言

數(shù)據(jù)結(jié)構(gòu)是一門研究計算機中非數(shù)值計算問題的數(shù)據(jù)組織和編排方式的綜合性基礎(chǔ)課程[1]。作為地理信息科學(xué)（Geographical Information Science， GIS）專業(yè)的一門核心基礎(chǔ)課程，數(shù)據(jù)結(jié)構(gòu)的基本理論與方法是GIS軟件設(shè)計、開發(fā)和應(yīng)用相關(guān)專業(yè)課程的重要支撐 [2-4]。有必要針對GIS專業(yè)的特點和需要對數(shù)據(jù)結(jié)構(gòu)課程教學(xué)內(nèi)容做進一步優(yōu)化[5]。無論是面向計算機類專業(yè)還是其它信息科學(xué)類專業(yè)，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的首要目的是為了提高應(yīng)用計算機解決實際問題的能力，培養(yǎng)學(xué)生的實踐能力是其教學(xué)重點[6，7]。在數(shù)據(jù)結(jié)構(gòu)教學(xué)中一般會設(shè)置較高比重的實踐教學(xué)，包括習(xí)題作業(yè)、上機訓(xùn)練和綜合課程設(shè)計等。其中，理論課程結(jié)束后的課程設(shè)計是實踐教學(xué)的最高層次，其目的是讓學(xué)生深化理解書本知識，學(xué)會把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來，提升實踐動手能力和解決實際問題能力。目前，數(shù)據(jù)結(jié)構(gòu)課程設(shè)計可參考的教材一般針對計算機相關(guān)專業(yè)編寫[8-10]，面向GIS專業(yè)學(xué)生授課時，若全盤照搬這些教材的內(nèi)容，則不能將這門課的基礎(chǔ)知識融入GIS專業(yè)課程體系，不利于本課程與GIS專業(yè)相關(guān)課程的銜接，體現(xiàn)不了GIS專業(yè)特色。因此，有必要面向GIS專業(yè)的培養(yǎng)目標(biāo)對數(shù)據(jù)結(jié)構(gòu)課程設(shè)計教學(xué)內(nèi)容進行補充和優(yōu)化，在數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的教學(xué)內(nèi)容中引入GIS專業(yè)的應(yīng)用問題。這樣既培養(yǎng)學(xué)生運用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識解決實際問題的能力，也激發(fā)學(xué)生探索和研究GIS專業(yè)問題的興趣，從而促進學(xué)生專業(yè)概念和專業(yè)思想的形成，為后續(xù)專業(yè)課的深入學(xué)習(xí)做準(zhǔn)備。

1 選題方案優(yōu)化

GIS專業(yè)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計選題，除了需要覆蓋數(shù)據(jù)結(jié)構(gòu)這門課本身的基礎(chǔ)知識點外，還應(yīng)該結(jié)合本專業(yè)特點，引入地理空間數(shù)據(jù)相關(guān)的專業(yè)問題，形成數(shù)據(jù)結(jié)構(gòu)基本概念與GIS專業(yè)應(yīng)用方法、技術(shù)的無縫結(jié)合。因此，將課程設(shè)計的選題分為三個層次，包括基礎(chǔ)題、一般應(yīng)用題和GIS專業(yè)應(yīng)用題（見表1）。

基礎(chǔ)題的內(nèi)容均來自數(shù)據(jù)結(jié)構(gòu)課本，此類題目的實驗?zāi)康氖庆柟獭娀瘮?shù)據(jù)結(jié)構(gòu)理論教學(xué)過程中的重點知識，培養(yǎng)學(xué)生運用所學(xué)基本概念和編程技能實現(xiàn)幾種通用數(shù)據(jù)結(jié)構(gòu)的組織存儲方法和常用算法的能力，是對理論課中實踐環(huán)節(jié)的有益補充。

一般應(yīng)用題比基礎(chǔ)題難度略高，要求學(xué)生綜合運用數(shù)據(jù)結(jié)構(gòu)的知識與相關(guān)算法解決具體應(yīng)用問題。比如，機器調(diào)度、迷宮求解、哈夫曼編碼解碼等。學(xué)生需對問題進行分析抽象，提取核心概念，然后與所學(xué)數(shù)據(jù)結(jié)構(gòu)知識點進行匹配。通過此類題目的演練，培養(yǎng)學(xué)生分析和解決實際問題的能力。

GIS專業(yè)應(yīng)用題可涉及GIS相關(guān)的地圖制圖、遙感分析、全球定位導(dǎo)航技術(shù)等各領(lǐng)域的經(jīng)典應(yīng)用問題，需要學(xué)生將數(shù)據(jù)結(jié)構(gòu)分析設(shè)計方法與GIS專業(yè)問題融會貫通。例如，矢量數(shù)據(jù)的多邊形自動生成、柵格數(shù)據(jù)四叉樹編碼、道路網(wǎng)的最優(yōu)路徑導(dǎo)航、地圖制圖中的四色渲染等。這些問題對低年級GIS專業(yè)學(xué)生還有一定難度，需要他們主動查閱專業(yè)資料，提前了解相關(guān)專業(yè)知識，理解其中的核心概念，然后設(shè)計出合適的數(shù)據(jù)存儲結(jié)構(gòu)和算法加以解決。通過這個過程，激發(fā)學(xué)生對GIS專業(yè)知識深入學(xué)習(xí)的興趣，為后續(xù)GIS專業(yè)課程的學(xué)習(xí)鋪墊，同時培養(yǎng)學(xué)生的文獻檢索與分析能力、研究性學(xué)習(xí)能力和創(chuàng)新能力。

2 GIS專業(yè)應(yīng)用題設(shè)計

選題方案中的基礎(chǔ)題和一般應(yīng)用題在很多數(shù)據(jù)結(jié)構(gòu)的實踐教材中均有介紹[8-10]，本文不再贅述。GIS專業(yè)應(yīng)用題需要結(jié)合GIS專業(yè)問題和數(shù)據(jù)結(jié)構(gòu)相關(guān)知識點綜合出題。GIS各領(lǐng)域涉及眾多空間數(shù)據(jù)結(jié)構(gòu)，如矢量、柵格數(shù)據(jù)的組織、空間索引和最短路徑算法等[11-12]。但相關(guān)教材鮮有將這些空間數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)結(jié)構(gòu)課程中的基本知識點進行關(guān)聯(lián)，不利于新舊知識之間的遷移與融合。實際上，這些問題經(jīng)過進一步的分解均可由線性表、樹、圖等基本數(shù)據(jù)結(jié)構(gòu)進行抽象表達。出題時需要厘清這些問題與各類基本數(shù)據(jù)結(jié)構(gòu)之間的對應(yīng)關(guān)系，用通俗易懂的語言描述題目中需要解決的專業(yè)問題、解題基本要求和條件，并給出必要的提示信息。

下面以“柵格數(shù)據(jù)四叉樹壓縮編碼與解碼”為例說明GIS專業(yè)應(yīng)用題的設(shè)計。柵格數(shù)據(jù)的四叉樹編碼是一種經(jīng)典的壓縮編碼方式，最早應(yīng)用于加拿大地理信息系統(tǒng)（CGIS）中，是GIS原理課程中的重要知識點之一，在GIS專業(yè)領(lǐng)域有廣泛應(yīng)用[11]。因此，課程組將四叉樹編碼與解碼問題納入課程設(shè)計選題。具體選題設(shè)計包括問題描述、基本要求和實現(xiàn)提示三個方面。

⑴ 問題描述

區(qū)域型物體的四叉樹表示方法，將四叉樹結(jié)構(gòu)表達的信息以一種線性編碼的方式存儲起來，稱之為四叉樹編碼，其在圖像分割、數(shù)據(jù)壓縮、地理信息系統(tǒng)等方面應(yīng)用廣泛。請實現(xiàn)二值柵格數(shù)據(jù)的四叉樹壓縮編碼/解碼算法，即設(shè)計四叉樹數(shù)據(jù)結(jié)構(gòu)及算法，將給定的二值圖像轉(zhuǎn)換為四叉樹線性編碼方式實現(xiàn)壓縮存儲，并設(shè)計解碼算法將壓縮編碼文件解碼還原為二值圖像。

⑵ 基本要求

①讀取一個待壓縮的柵格數(shù)據(jù)文件（BMP格式），文件中的每個像元僅有（0、1）兩種取值（即二值圖像），用一個矩陣存儲原始數(shù)據(jù);

②對該矩陣進行自上而下的四叉樹分割，構(gòu)建四叉樹結(jié)構(gòu);

③對得到的所有葉子節(jié)點進行線性四叉樹編碼，將編碼作為一個數(shù)組寫入文件;

④實現(xiàn)線性四叉樹編碼的解碼程序，即讀取壓縮編碼文件將其還原為柵格圖像數(shù)據(jù)文件。

⑶ 實現(xiàn)提示

問題的關(guān)鍵在于對柵格數(shù)據(jù)四叉樹剖分、四叉樹構(gòu)建以及線性四叉樹編碼幾個知識點的理解。其中四叉樹剖面和線性四叉樹編碼的基本思路見圖1，解碼過程與編碼正好相反。相關(guān)概念與方法描述如下。

①四叉樹剖分方法。將圖像區(qū)域按大小相同的象限四等分，每個象限又可根據(jù)一定規(guī)則判斷是否繼續(xù)等分為次一層的四個象限。若子象限只含一種屬性代碼，則停止繼續(xù)分割。圖像區(qū)域的柵格陣列應(yīng)為2n×2n，如果圖像不是一個2n×2n的尺寸，通過邊緣增補空白行、列的方式湊足。如圖1（a）、圖1（b），一個8×8的柵格，經(jīng)過三層四叉樹剖分后，得到的每個單元只含有一種屬性代碼。

②線性四叉樹編碼方法。如圖1（c），四叉樹剖分結(jié)果邏輯上可用一棵四叉樹表示，樹中每個非葉子結(jié)點有四個分支，每個葉子結(jié)點對應(yīng)的是只含有一種屬性代碼的剖分區(qū)域。線性編碼的目的就是記錄每個葉結(jié)點在四叉樹中的位置和值，其中值就是子區(qū)的屬性代碼，所以重點是如何在編碼中表達結(jié)點的位置。常用的線性四叉樹編碼方式有：a）基于深度和層次碼的方式;b）基于四進制的方式;c）基于十進制的方式。以第一種方式為例，用一個32位的二進制數(shù)表示節(jié)點的位置，具體分為兩部分，最右邊4位記錄該葉子結(jié)點的深度，從右第5位開始往左的28位依次記錄從葉節(jié)點到根結(jié)點的路徑。用0、1、2、3分別表示北西（NW）、北東（NE）、南西（SW）和南東（SE）。例如，圖1（c）中編號為10的葉子結(jié)點在樹中位置信息的線性編碼為：00000000 00000000 00000010 01110011。

作為GIS專業(yè)后繼課程中的內(nèi)容，四叉樹及其壓縮編碼的相關(guān)概念對GIS專業(yè)二年級的學(xué)生可能是全新的，但是卻能與數(shù)據(jù)結(jié)構(gòu)課程所學(xué)的知識點之間建立緊密的聯(lián)系。例如，本題中原始柵格數(shù)據(jù)的表達，實際上就是數(shù)據(jù)結(jié)構(gòu)中介紹的二維數(shù)組;同時，四叉樹編碼的結(jié)果也可用數(shù)組存儲;需要構(gòu)建的四叉樹，其實就是二叉樹的一種擴展。數(shù)據(jù)結(jié)構(gòu)課程中，對二叉樹作了詳細(xì)介紹，學(xué)生應(yīng)該可以根據(jù)對二叉樹的理解去實現(xiàn)四叉樹的存儲結(jié)構(gòu)和相關(guān)操作算法。通過這種訓(xùn)練，可建立數(shù)據(jù)結(jié)構(gòu)與GIS專業(yè)知識之間的深度聯(lián)系，鍛煉學(xué)生舉一反三的能力。

必須承認(rèn)，完全依靠低年級學(xué)生現(xiàn)有的知識和能力去解決一個對他們來說全新的專業(yè)問題，是不太可行的。因此除了要向?qū)W生提供必要的提示信息外，還要引導(dǎo)和鼓勵他們多查閱專業(yè)資料，必要時提供部分輔助程序。例如，針對本選題，我們給學(xué)生提供了讀寫柵格數(shù)據(jù)文件（BMP格式）的源程序及使用說明，讓學(xué)生能夠從這種基礎(chǔ)但不涉及核心問題的代碼編寫工作中解放出來，集中精力解決主要問題。這樣即降低了題目的難度，也可鍛煉學(xué)生文獻研究、探究式學(xué)習(xí)和模塊化程序設(shè)計等方面的能力。

3 結(jié)語

數(shù)據(jù)結(jié)構(gòu)教學(xué)內(nèi)容比較抽象，必須理論聯(lián)系實踐，因此課程設(shè)計教學(xué)是重點。作為GIS專業(yè)的一門課程設(shè)計，選題不僅需要以基礎(chǔ)知識點的鞏固和動手能力的提高為主要目的，還要兼顧專業(yè)特色。本文將課程設(shè)計的選題分三個層次：基礎(chǔ)題、一般應(yīng)用題和GIS專業(yè)應(yīng)用題。在專業(yè)應(yīng)用題中引入GIS專業(yè)經(jīng)典問題，體現(xiàn)了基礎(chǔ)性、應(yīng)用型、專業(yè)性和創(chuàng)新性的有機融合，為后序GIS專業(yè)課程鋪墊。

課程設(shè)計的順利開展需要學(xué)生具備一定的編程能力作為支撐。而GIS低年級學(xué)生接觸編程課程較少，較多學(xué)生對程序設(shè)計與調(diào)試存在畏懼心理，他們很容易由于中途受挫而影響后續(xù)學(xué)習(xí)的信心和興趣。因此，課程設(shè)計也包括理論教學(xué)過程中應(yīng)該多稱贊學(xué)生，鼓勵他們自主調(diào)試程序，盡快樹立學(xué)習(xí)自信心。

參考文獻（References）：

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，2016.

[2] 吳信才，徐世武，萬波，等.地理信息系統(tǒng)原理與方法（第三版）[M]. 北京：電子工業(yè)出版社，2014.

[3] 李滿春，陳剛，陳振杰，等.GIS設(shè)計與實現(xiàn)（第二版）[M].北京：科學(xué)出版社，2011.

[4] 郭慶勝，蔡忠亮."GIS工程設(shè)計"的實驗教學(xué)模式研究[J]. 測繪工程，2016。25（9）：77-80

[5] 劉遠(yuǎn)剛，何貞銘，蔡永香，等.地理信息科學(xué)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程教學(xué)改革與實踐[J].電腦知識與技術(shù)，2017.13（17）：96-97

[6] 陳越，何欽銘，馮雁."數(shù)據(jù)結(jié)構(gòu)"綜合性課程設(shè)計教學(xué)探索與實踐[J].計算機教育，2008.8：54-55

[7] 孫歧峰."數(shù)據(jù)結(jié)構(gòu)"課程教學(xué)反思與改革[J].計算機教育，2009.22：66-67，35

[8] 嚴(yán)蔚敏，吳偉民，米寧.數(shù)據(jù)結(jié)構(gòu)題集（C語言版）[M].北京：清華大學(xué)出版社，2008.

[9] 徐雅靜，肖波.數(shù)據(jù)結(jié)構(gòu)與STL習(xí)題解析與實驗指導(dǎo)[M].北京：北京郵電大學(xué)出版社，2015.

[10] 盧玲，陳媛，何波，等.數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)指導(dǎo)及實踐教程[M].北京：清華大學(xué)出版社，2019

[11] 張宏，溫永寧，劉愛利，等. 地理信息系統(tǒng)算法基礎(chǔ)[M].北京：科學(xué)出版社，2006.

[12] Stephen Wise（英）著;朱定局譯.GIS數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)[M].北京：科學(xué)出版社，2017.