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

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

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

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

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

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

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

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

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

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

選題方案中的基礎題和一般應用題在很多數(shù)據(jù)結(jié)構(gòu)的實踐教材中均有介紹[8-10]，本文不再贅述。GIS專業(yè)應用題需要結(jié)合GIS專業(yè)問題和數(shù)據(jù)結(jié)構(gòu)相關(guān)知識點綜合出題。GIS各領域涉及眾多空間數(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)之間的對應關(guān)系，用通俗易懂的語言描述題目中需要解決的專業(yè)問題、解題基本要求和條件，并給出必要的提示信息。

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

⑴ 問題描述

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

⑵ 基本要求

①讀取一個待壓縮的柵格數(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ū)域的柵格陣列應為2n×2n，如果圖像不是一個2n×2n的尺寸，通過邊緣增補空白行、列的方式湊足。如圖1（a）、圖1（b），一個8×8的柵格，經(jīng)過三層四叉樹剖分后，得到的每個單元只含有一種屬性代碼。

②線性四叉樹編碼方法。如圖1（c），四叉樹剖分結(jié)果邏輯上可用一棵四叉樹表示，樹中每個非葉子結(jié)點有四個分支，每個葉子結(jié)點對應的是只含有一種屬性代碼的剖分區(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è)二年級的學生可能是全新的，但是卻能與數(shù)據(jù)結(jié)構(gòu)課程所學的知識點之間建立緊密的聯(lián)系。例如，本題中原始柵格數(shù)據(jù)的表達，實際上就是數(shù)據(jù)結(jié)構(gòu)中介紹的二維數(shù)組;同時，四叉樹編碼的結(jié)果也可用數(shù)組存儲;需要構(gòu)建的四叉樹，其實就是二叉樹的一種擴展。數(shù)據(jù)結(jié)構(gòu)課程中，對二叉樹作了詳細介紹，學生應該可以根據(jù)對二叉樹的理解去實現(xiàn)四叉樹的存儲結(jié)構(gòu)和相關(guān)操作算法。通過這種訓練，可建立數(shù)據(jù)結(jié)構(gòu)與GIS專業(yè)知識之間的深度聯(lián)系，鍛煉學生舉一反三的能力。

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

3 結(jié)語

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

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

參考文獻（References）：

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

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

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

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

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

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

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

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

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

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

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

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