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

1、空間數(shù)據(jù)結(jié)構(gòu)Geo-data Structure一、課程基本情況課程類別：專業(yè)主干課課程學(xué)分： 3 學(xué)分課程總學(xué)時(shí)：48 學(xué)時(shí)，其中講課：32學(xué)時(shí)，實(shí)驗(yàn)（含上機(jī)）：16 學(xué)時(shí)，課外 學(xué)時(shí)課程性質(zhì)：必修開課學(xué)期：第3學(xué)期先修課程： 計(jì)算機(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è)計(jì)工具和技術(shù)，即學(xué)會(huì)空間數(shù)據(jù)的組織方法和地理空間世界問題在計(jì)算機(jī)內(nèi)部

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

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

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

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

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

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

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