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

1、空間數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)Experiment& Practice of Geo-data Structure一、課程基本情況 課程總學(xué)時(shí)：48實(shí)驗(yàn)總學(xué)時(shí)：16學(xué)分：3開課學(xué)期：第3學(xué)期 課程性質(zhì)：必修 對(duì)應(yīng)理論課程：空間數(shù)據(jù)結(jié)構(gòu)適用專業(yè)：地理信息科學(xué)教 材：嚴(yán)蔚敏，吳偉民，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），清華大學(xué)出版社，2002年。開課單位：地理與遙感學(xué)院 地理信息科學(xué)系二、實(shí)驗(yàn)課程的教學(xué)目標(biāo)和任務(wù)空間數(shù)據(jù)結(jié)構(gòu)課程為地理信息科學(xué)專業(yè)的必備基礎(chǔ)課程，為專業(yè)必修課。該課程的教學(xué)目標(biāo)是，通過實(shí)驗(yàn)使學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的理論與方法，學(xué)會(huì)分析研究各種數(shù)據(jù)結(jié)構(gòu)的特性，針對(duì)問題的不同選擇合適的數(shù)據(jù)結(jié)構(gòu)，提高算法設(shè)計(jì)的能力和動(dòng)手實(shí)

2、驗(yàn)的技能。主要針對(duì)地理空間問題的應(yīng)用背景分析，選擇使用常用的通用數(shù)據(jù)結(jié)構(gòu)與算法，從而培養(yǎng)地理信息科學(xué)專業(yè)本科生的程序設(shè)計(jì)能力。該課程的任務(wù)是，研究對(duì)于地理空間問題進(jìn)行程序設(shè)計(jì)所涉及的計(jì)算機(jī)操作的各種對(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、；行程編碼和四叉樹的柵格屬性查詢算法；四叉樹向量數(shù)據(jù)索引方法；莫頓排序柵格數(shù)據(jù)索引方法。三、實(shí)驗(yàn)課程的內(nèi)容和要求序號(hào)項(xiàng)目名稱所需學(xué)時(shí)內(nèi) 容 提 要項(xiàng)目要求實(shí)驗(yàn)類型必開選開實(shí)驗(yàn)一線性表的存儲(chǔ)表示及應(yīng)用2(1)線性表的順序、鏈接存儲(chǔ)表示及實(shí)現(xiàn)。(2)設(shè)計(jì)一算法并實(shí)現(xiàn)：對(duì)單鏈表實(shí)現(xiàn)就地逆置。驗(yàn)證/設(shè)計(jì)實(shí)驗(yàn)二棧的存儲(chǔ)表示及應(yīng)用2(1)棧的順序、鏈接存儲(chǔ)表示及實(shí)現(xiàn)。(2)十六進(jìn)制到二進(jìn)制的轉(zhuǎn)換。驗(yàn)證/設(shè)計(jì)實(shí)驗(yàn)三串的查找2對(duì)字符串進(jìn)行查找、匹配功能實(shí)現(xiàn)驗(yàn)證/設(shè)計(jì)實(shí)驗(yàn)四稀疏矩陣存儲(chǔ)與壓縮實(shí)現(xiàn)2對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，并實(shí)現(xiàn)其基本的矩陣運(yùn)算功能驗(yàn)證/設(shè)計(jì)實(shí)驗(yàn)五二叉樹的建立與前序遍歷算法實(shí)現(xiàn)2以二叉鏈表為存儲(chǔ)結(jié)

4、構(gòu)，實(shí)現(xiàn)對(duì)二叉樹的前、中、后序遍歷，寫出遞歸與非遞歸算法程序。驗(yàn)證/設(shè)計(jì)實(shí)驗(yàn)六二叉樹的中序遍歷以及后序遍歷算法實(shí)現(xiàn)2 實(shí)現(xiàn)對(duì)二叉樹的中、后序遍歷，寫出遞歸與非遞歸算法程序。驗(yàn)證/設(shè)計(jì)實(shí)驗(yàn)七圖的建立與深度遍歷 3編寫程序，由輸入的頂點(diǎn)數(shù)目、弧的數(shù)目、各頂點(diǎn)的信息和各條弧的信息建立有向圖的鄰接表；對(duì)所建立的有向圖進(jìn)行深度優(yōu)先、廣度優(yōu)先遍歷。綜合/設(shè)計(jì)實(shí)驗(yàn)八圖的廣度遍歷 2對(duì)所建立的有向圖進(jìn)行廣度優(yōu)先遍歷。綜合/設(shè)計(jì)實(shí)驗(yàn)九順序查找與二分法查找的實(shí)現(xiàn)與比較3隨機(jī)生成10000個(gè)在指定值域內(nèi)的整數(shù)，分別用順序查找法、二分查找法進(jìn)行10000次查找并比較二個(gè)算法。綜合/設(shè)計(jì)實(shí)驗(yàn)十常用排序算法4編寫程序?qū)崿F(xiàn)冒泡排序、希爾排序、快速排序并進(jìn)行比較次數(shù)和交換次數(shù)統(tǒng)計(jì)。綜合/設(shè)計(jì)四、課程考核（1）實(shí)驗(yàn)報(bào)告的撰寫要求：具體要求見實(shí)驗(yàn)的內(nèi)容和要求部分；每個(gè)實(shí)驗(yàn)項(xiàng)目需要提交1份實(shí)驗(yàn)報(bào)告。（2）實(shí)驗(yàn)報(bào)告：6 次（3）考核及成績(jī)?cè)u(píng)定：以平時(shí)上機(jī)題完成情況和實(shí)驗(yàn)報(bào)告完成情況進(jìn)行綜合考核。五、參考書目1、張銘，王騰蛟，趙海燕，數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出版社，2008年；2、李春葆，數(shù)據(jù)結(jié)構(gòu)（