《空間數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)大綱

1、空間數(shù)據(jù)結(jié)構(gòu)Geo-data Structure一、課程基本情況課程類別：專業(yè)主干課課程學(xué)分： 3 學(xué)分課程總學(xué)時：48 學(xué)時，其中講課：32學(xué)時，實驗（含上機(jī)）：16 學(xué)時，課外 學(xué)時課程性質(zhì)：必修開課學(xué)期：第3學(xué)期先修課程： 計算機(jī)基礎(chǔ)、C語言適用專業(yè)： 地理信息科學(xué)教 材：嚴(yán)蔚敏，吳偉民，數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)出版社，2002年。開課單位：地理與遙感學(xué)院 地理信息科學(xué)系二、課程性質(zhì)、教學(xué)目標(biāo)和任務(wù)空間數(shù)據(jù)結(jié)構(gòu)課程為地理信息科學(xué)專業(yè)的必備基礎(chǔ)課程，為專業(yè)必修課。該課程的教學(xué)目標(biāo)是，使學(xué)生掌握解決地理空間問題的程序設(shè)計工具和技術(shù)，即學(xué)會空間數(shù)據(jù)的組織方法和地理空間世界問題在計算機(jī)內(nèi)部

2、的表示方法，針對地理空間問題的應(yīng)用背景分析，選擇介紹常用的通用數(shù)據(jù)結(jié)構(gòu)與算法，并且增加空間數(shù)據(jù)結(jié)構(gòu)與算法，從而培養(yǎng)地理信息科學(xué)專業(yè)本科生的程序設(shè)計能力。該課程的任務(wù)是，研究對于地理空間問題進(jìn)行程序設(shè)計所涉及的計算機(jī)操作的各種對象（包含空間對象），以及它們之間的關(guān)系和運算。該課程的主要內(nèi)容包括兩部分，第一部分為通用數(shù)據(jù)結(jié)構(gòu)的常規(guī)內(nèi)容，包括線性表、棧和隊列、字符串、數(shù)組和廣義表、樹和二叉樹、圖，以及查找和排序算法；第二部分為空間數(shù)據(jù)結(jié)構(gòu)的一般內(nèi)容，包括矢量數(shù)據(jù)結(jié)構(gòu)及其算法，柵格數(shù)據(jù)結(jié)構(gòu)及其算法，空間索引算法。該課程的重點為：通用數(shù)據(jù)結(jié)構(gòu)的存儲表示及實現(xiàn)算法；順序查找、二分查找、分塊查找算法；二分法

3、插入排序、冒泡排序、希爾排序、快速排序算法；線與多邊形的矢量算法；行程編碼和四叉樹的柵格屬性查詢算法；柵格面積計算算法；四叉樹向量數(shù)據(jù)索引方法；莫頓排序柵格數(shù)據(jù)索引方法。三、教學(xué)內(nèi)容和要求第1章 緒論（2學(xué)時）（1）了解數(shù)據(jù)結(jié)構(gòu)的三個方面：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算；（2）理解算法的概念和特性；（3）掌握算法的描述方法；（4）了解算法分析的內(nèi)容；重點：算法的描述方法；難點：算法分析的內(nèi)容。第2章 線性表（2學(xué)時）（1）理解線性表的基本概念，線性表有關(guān)的術(shù)語，線性表的特性；（2）熟悉線性表的抽象數(shù)據(jù)類型定義；（3）掌握線性表的順序存儲和鏈接存儲表示及實現(xiàn)；重點：線性表的順序存儲和鏈接存儲表示及實現(xiàn)

4、；難點：線性表的鏈接存儲表示及實現(xiàn)。第3章 棧和隊列（2學(xué)時）（1）理解棧的基本概念，棧有關(guān)的術(shù)語，棧的特性；（2）熟悉棧的抽象數(shù)據(jù)類型定義；（3）掌握棧的順序存儲和鏈接存儲表示及實現(xiàn)；（4）理解隊列的基本概念，隊列有關(guān)的術(shù)語，隊列的特性；（5）熟悉隊列的抽象數(shù)據(jù)類型定義；（6）掌握隊列的順序存儲和鏈接存儲表示及實現(xiàn)；重點：棧的鏈接存儲表示及實現(xiàn)；隊列的鏈接存儲表示及實現(xiàn)；難點：棧的鏈接存儲表示及實現(xiàn)；隊列的鏈接存儲表示及實現(xiàn)。第4章 字符串（2學(xué)時）（1）理解串的基本概念，串有關(guān)的術(shù)語，串的特性；（2）熟悉串的抽象數(shù)據(jù)類型定義；（3）掌握串的存儲表示及實現(xiàn)；（4）理解串的模式匹配運算。重點：

5、串的存儲表示及實現(xiàn)；難點：串的模式匹配運算。第5章 數(shù)組和廣義表（2學(xué)時）（1）理解數(shù)組的定義，數(shù)組的順序表示和實現(xiàn)；（2）了解對稱矩陣、三角矩陣、稀疏矩陣的壓縮存儲；（3）了解廣義表的定義，廣義表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。重點：對稱矩陣、三角矩陣、稀疏矩陣的壓縮存儲；難點：廣義表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。第6章 樹和二叉樹（5學(xué)時）（1）理解樹的基本概念，樹有關(guān)的術(shù)語，樹的特性；（2）熟悉樹的抽象數(shù)據(jù)類型定義；（3）了解樹的存儲表示；（4）理解二叉樹的基本概念，二叉樹有關(guān)的術(shù)語，二叉樹的特性；（5）熟悉二叉樹的抽象數(shù)據(jù)類型定義；（6）掌握二叉樹的順序與鏈接存儲表示；（7）掌握二叉樹的遍歷運算及實現(xiàn)；（8）了解森

6、林與二叉樹的轉(zhuǎn)換；（9）了解樹和森林的遍歷。重點：二叉樹的順序與鏈接存儲表示；二叉樹的遍歷運算及實現(xiàn)；難點：森林與二叉樹的轉(zhuǎn)換。第7章 圖（3學(xué)時）（1）理解圖的基本概念，圖有關(guān)的術(shù)語，圖的特性；（2）熟悉圖的抽象數(shù)據(jù)類型定義；（3）掌握圖的鄰接矩陣、鄰接表存儲表示；（4）理解圖的深度優(yōu)先遍歷、廣度優(yōu)先遍歷算法；重點：圖的鄰接矩陣、鄰接表存儲表示；難點：圖的深度優(yōu)先遍歷、廣度優(yōu)先遍歷算法。第8章 查找（4學(xué)時）（1）理解查找的定義及相關(guān)概念；（2）掌握：順序查找，二分查找，分塊查找；（3）掌握：二叉排序樹，平衡二叉樹；（4）了解：B-樹、B+樹的概念及特點；（5）了解哈希表及其查找。重點：順序

7、查找，二分查找，分塊查找；難點：二叉排序樹，平衡二叉樹。第9章 排序（4學(xué)時）（1）理解排序的定義及相關(guān)概念；（2）掌握以下常用的內(nèi)排序方法：直接插入排序，二分法插入排序，直接選擇排序，冒泡排序，希爾排序，快速排序；（3）了解常用內(nèi)排序方法的特點：時間復(fù)雜度，空間復(fù)雜度。重點：二分法插入排序，冒泡排序，希爾排序，快速排序；難點：冒泡排序，希爾排序，快速排序。第10章 矢量數(shù)據(jù)結(jié)構(gòu)（2學(xué)時）（1）熟悉點、線的存儲；（2）熟悉多邊形的存儲；（3）掌握線的矢量算法；（4）掌握多邊形的矢量算法。重點：線的矢量算法；多邊形的矢量算法；難點：多邊形的矢量算法。第11章 柵格數(shù)據(jù)結(jié)構(gòu)（2學(xué)時）（1）熟悉行程

8、編碼和四叉樹；（2）掌握行程編碼和四叉樹的柵格屬性查詢算法；（3）掌握柵格面積計算算法。重點：行程編碼和四叉樹的柵格屬性查詢算法；柵格面積計算算法；難點：柵格面積計算算法。第12章 空間索引（2學(xué)時）（1）熟悉基于K-D樹建立索引的方法；（2）掌握利用四叉樹建立向量數(shù)據(jù)索引的方法；（3）掌握利用莫頓排序建立柵格數(shù)據(jù)索引的方法。重點：利用四叉樹建立向量數(shù)據(jù)索引的方法；利用莫頓排序建立柵格數(shù)據(jù)索引的方法；難點：利用四叉樹建立向量數(shù)據(jù)索引的方法；利用莫頓排序建立柵格數(shù)據(jù)索引的方法。四、課程考核（1）作業(yè)等：作業(yè)：8 次，課程論文：1 篇；（2）考核方式：閉卷考試（3）總評成績計算方式：平時考勤成績、期中考試成績、實驗成績各占20%，期末考試成績占4