資料結構在gis中對於資料的採集、儲存、查詢、檢索和應用分析等操作方式有著重要的影響，一種高效率的資料結構應該具備以下幾個要求：
1、組織的資料能夠表示要素之間的層次關係，便於不同資料聯絡於覆蓋；
2、正確反映地理實體之間的空間排列方式和各實體之間的相互關係；
3、便於訪問與檢索；
4、節省儲存空間，減少資料冗餘；
5、訪問速度快，在運算速度較慢的微機上要達到快速響應；
6、具有足夠的靈活性，資料組織應具有插入新的資料、刪除或修改部分資料的基本功能。
柵格資料結構
柵格結構是以規則的陣列來表示空間地物或現象分布的資料組織,組織中的每個資料表示地物或現象的非幾何屬性特徵。
柵格結構的顯著特點:屬性明顯,定位隱含,即資料直接記錄屬性的指標或資料本身,而所在位置則根據行列號轉換為相應的座標。
柵格資料的編碼方法:直接柵格編碼,就是將柵格資料看作乙個資料矩陣,逐行（或逐列）逐個記錄**;壓縮編碼,包括鏈碼（弗里曼鏈碼）比較適合儲存圖形資料;遊程長度編碼通過記錄行或列上相鄰若干屬性相同點的**來實現;塊碼是有成長度編碼擴充套件到二維的情況,採用方形區域為記錄單元;四叉樹編碼是最有效的柵格資料壓縮編碼方法之一,還能提高圖形操作效率,具有可變的解析度。
向量資料結構
向量資料結構是通過記錄座標的方式盡可能精確地表示點、線和多邊形等地理實體,座標空間設為連續,允許任意位置、長度和面積的精確定義。
向量結構的顯著特點:定位明顯,屬性隱含。
向量資料的編碼方法:
對於點實體和線實體,直接記錄空間資訊和屬性資訊;
對於多邊形地物,有座標序列法、樹狀索引編碼法和拓撲結構編碼法。座標序列法是由多邊形邊界的x,y座標對集合及說明資訊組成,是最簡單的一種多邊形向量編碼法,檔案結構簡單,但多邊形邊界被儲存兩次產生資料冗餘,而且缺少鄰域資訊;樹狀索引編碼法是將所有邊界點進行數位化,順序儲存座標對,由點索引與邊界線號相聯絡,以線索引與各多邊形相聯絡,形成樹狀索引結構,消除了相鄰多邊形邊界資料冗餘問題;拓撲結構編碼法是通過建立乙個完整的拓撲關係結構,徹底解決鄰域和島狀資訊處理問題的方法,但增加了演算法的複雜性和資料庫的大小。
向量柵格資料的比較
向量資料的優缺點:
優點為資料結構緊湊、冗餘度低,有利於網路和檢索分析,圖形顯示***、精度高;
缺點為資料結構複雜,多邊形疊加分析比較困難。
柵格資料的優缺點:
優點為資料結構簡單,便於空間分析和地表模擬,現勢性較強;
缺點為資料量大,投影轉換比較複雜。
兩者比較:
柵格資料操作總的來說容易實現,向量資料操作則比較複雜;
柵格結構是向量結構在某種程度上的一種近似,對於同一地物達到於向量資料相同的精度需要更大量的資料;在座標位置搜尋、計算多邊形形狀面積等方面柵格結構更為有效,而且易於遙感相結合,易於資訊共享;向量結構對於拓撲關係的搜尋則更為高效,網路資訊只有用向量才能完全描述,而且精度較高。對於地理資訊系統軟體來說,兩者共存,各自發揮優勢是十分有效的。
向量柵格相互轉換演算法
向量轉柵格:內部點擴散法,即由多邊形內部種子點向周圍鄰點擴散,直至到達各邊界為止;複數積分演算法,即由待判別點對多邊形的封閉邊界計算複數積分,來判斷兩者關係;射線演算法和掃瞄演算法,即由圖外某點向待判點引射線,通過射線與多邊形邊界交點數來判斷內外關係;邊界代數演算法,是一種基於積分思想的向量轉柵格演算法,適合於記錄拓撲關係的多邊形向量資料轉換,方法是由多邊形邊界上某點開始,順時針搜尋邊界線,上行時邊界左側具有相同行座標的柵格減去某值,下行時邊界左側所有柵格點加上該值,邊界搜尋完畢之後即完成多邊形的轉換。
柵格轉向量:即是提取具有相同編號的柵格集合表示的多邊形區域的邊界和邊界的拓撲關係,並表示成向量格式邊界線的過程。步驟包括:
多邊形邊界提取,即使用高通濾波將柵格影象二值化;邊界線追蹤,即對每個弧段由乙個節點向另乙個節點搜尋;拓撲關係生成和去處多餘點及曲線圓滑。
拓撲的基本概念
幾何資訊和拓撲關係是地理資訊系統中描述地理要素的空間位置和空間關係的不可缺少的基本資訊。其中幾何資訊主要涉及幾何目標的座標位置、方向、角度、距離和面積等資訊，它通常用解析幾何的方法來分析。而空間關係資訊主要涉及幾何關係的「相連」、「相鄰」、「包含」等資訊，它通常用拓撲關係或拓撲結構的方法來分析。
拓撲關係是明確定義空間關係的一種數學方法。在地理資訊系統中用它來描述並確定空間的點、線、面之間關係及屬性，並可實現相關的查詢和檢索。從拓撲觀點出發，關心的是空間的點、線、面之間的聯接關係，而不管實際圖形的幾何形狀。
因此，幾何形狀相差很大的圖形，它們的拓撲結構卻可能相同。
在向量拓撲資料結構中，空間資料不但要記錄空間實體的位置，而且要記錄空間實體間的拓撲關係，這是地理資訊系統區別於其他資料庫管理系統的重要標誌。建立拓撲關係是一種對空間結構關係進行明確定義的數學方法。目前，空間資料的拓撲資料結構的表示方式沒有固定的格式，也沒有形成標準，其基本原理是相同的。
因此，在向量拓撲結構表示方法中，任何地理實體均可以用點、線、面來表示其特徵，並且可根據各實體間的空間拓撲關係，解譯出更多的資訊。
對於二維空間資料而言，向量資料可以抽象點、線、面三種要素，也稱拓撲要素。對三維而言，還要加上體。其最基本的拓撲關係主要有拓撲鄰接、拓撲關聯、拓撲包含等幾種。
拓撲資料結構中關鍵的就是對這些拓撲要素間的拓撲關係進行表示，幾何資料的表示可參照向量資料的簡單資料。雖然目前gis中基本的拓撲關係的表示方法不盡相同，但只要能完整表達出拓撲要素間的基本拓撲關係就可以。
拓撲資料結構：
拓撲資料結構包括dime(對偶獨立地圖編碼法)、polyvrt(多邊形轉換器)、tiger(地理編碼和參照系統的拓撲整合)等。它們共同的特點是:點是相互獨立的，點連成線，線構成面。
每條線始於起始結點(fn)，止於終止結點tn)，並與左右多邊形(lp和rp)相鄰接。構成多邊形的線叉稱為鏈段或弧段，兩條以上的弧段相交的點稱為結點，由一條弧段組成的多邊形稱為島，多邊形圖中不含島的多邊形稱為簡單多邊形，表示單連通區域;含島區的多邊形稱為復合多邊形，表示復連通區域。在復連通區域中，包括有外邊界和內邊界，島區多邊形看作是復連通區域的內邊界，復連通區域的內邊界多邊形對應的區域含有平面上的無窮遠慮。
該資料結構的基本元素如圖2-11所示。
在這種資料結構中，弧段或鏈段是資料組織的基本物件。弧段檔案由弧段記錄組成，每個弧段記錄包括弧段標識碼、fn、tn、lp和rp。結點檔案由結點記錄組成，包括每個結點的結點號、結點座標及與該結點連線的弧段標識碼等。
多邊形檔案由多邊形記錄組成，包括多邊形標識碼、組成該多邊形的弧段標識碼以及相關屬性等。現以圖2-11為例，列出拓撲資料結構的弧段檔案格式(表2-5):
表2-5 拓撲資料結構的弧段檔案構成
拓撲資料結構最重要的技術特徵和貢獻是具有拓撲編輯功能。這種拓撲編輯功能，不但保證數位化原始資料的自動查錯編輯，而且可以自動形成封閉的多邊形邊界，為由各個單獨儲存的弧段組成所需要的各類多邊形及建立空間資料庫奠定基礎。
拓撲編輯功能包括多邊形連線編輯和結點連線編輯，前者指順序連線組成封閉多邊形一組線段的編輯，後者指順序連線環繞某個結點所有多邊形的編輯。具體的編輯演算法如下:
(1)多邊形連線編輯。例如，設需要對多邊形p1進行編輯，其演算法過程為:
①從表2-5所示的弧段檔案中，檢出與當前編輯的多邊形p1相關的所有記錄:
②在檢出的記錄中，計算機檢查當前編輯的多邊形p1所處的位置:
如果p1位在左多邊形位置，將之與位於右多邊形位置的多邊形號相交換，同時也將該記錄的結點號位置作相應的交換;反之，如果當前編輯的多邊形p1位於右多邊形位置，則該記錄的所有資料項順序不作改變。
按照上述規則，檢出的記錄變為以下形式:
③從經過**位置轉換的記錄中，任取乙個起結點作為起點，順序連線各個結點，必要時可對記錄的前後順序作調整，使得連線的結點能自行封閉，如圖2-12所示。
如果依照上述順序連線的結點不能自行閉合，或者出現記錄缺損或記錄多餘等情況，則表示弧段檔案有錯，必須改正出錯的記錄。直到所有多邊形都經過編輯和改正，再轉入結點連線編輯。
(2)結點連線編輯。例如，設需要對結點n2進行編輯，其演算法過程為:
①從表2-5所示的弧段檔案中，檢出與當前編輯的結點n2相關的所有記錄：
②在檢出的記錄中，計算機檢查當前編輯的結點n2所處的位置:
如果n2位在起結點位置，將之與位於終結點位置的結點號相交換，同時也符該記錄的多邊形號位置作相應的交換;反之，如果當前編輯的結點n2位於終結點位置，則該記錄所有資料項順序不作改變。
按照上述規則，檢出的記錄變為以下形式:
③從經過**位置轉換的記錄中，任取乙個左多邊形作為起點，順序連線各個多邊形，同樣，必要時可對記錄的前後順序作調整，使得連線的多邊形能首尾呼應，如圖2-13所示。
如果依照上述序連線的多邊形不能首尾呼應，或者出現記錄缺損或記錄多餘等情況，同樣也表示弧段檔案有錯，必須改正出錯的記錄。直到所有結點都經過編輯和改正，才能將該弧段檔案用於結點檔案和多邊形檔案的自動生成以及資料庫的建立。
這種拓撲資料結構及其自動編輯功能，已經被許多商品化的gis軟體所採用，例如美國的arc/info gis軟體等。
拓撲資料結構的結構特點：
1、空間關係明確，不依賴於具體的座標位置。多邊形的公共邊界、網路的節點表達簡明。
2、便於分析查詢，尤其是點、線、面直線的相鄰關係查詢和分析。
拓撲資料結構的優缺點：
1、 圖形的修改方便，可由軟體檢查資料輸入錯誤，容易保證資料質量；
2、 便於疊合分析、網路分析等；
3、 資料結構複雜，軟體複雜；
4、 建立拓撲關係需花計算時間，特別是當地圖覆蓋範圍很大，資料量很大時。
拓撲資料結構的構建實際上大大增加了資料編輯的難度和複雜性，以至於它成了引起廣泛爭議的問題。顯然，拓撲關係的存在為資料錯誤的查詢和空間分析提供了必要的前提，但並不是所有的gis應用丟必須具備這種預先儲存的、消耗大量精力才能建立的資料結構。許多gis軟體只使用其中集中最基本的拓撲關係，就能滿足大多數空間分析的需要，但更複雜的空間分析，也許需要更多的拓撲關係。
一般的，建立的拓撲關係越多，資料編輯維護難度越大、越複雜，但進行處理比較複雜的空間分析就越方便，空間分析花費的時間就越少。因此，究竟是否應該預先儲存拓撲關係、儲存哪些拓撲關係就成為當前爭論的焦點。
資料結構為我們人類利用模型來描述這個世界帶來更方便的操作，也是目前我們利用最為廣泛的方式，隨著世界的發展，人類所需要研究的客觀事物越來越多，也越來越複雜，因此描述這個世界的資料也將越來越多、越來越複雜。但是要想實現如此龐大的資料量以及資料的複雜性在執行速度比較緩慢的微機上流暢的被執行，被處理使用，對資料結構的要求也將會越來越高，只有進一步優化資料結構，才能使微機更好更快的處理資料來模擬我們的客觀事物，才更有利於人類研究這個現實的世界。
演算法與資料結構
演算法 是按部就班地解決某個問題的方法，是對特定問題求解步驟的一種描述。偽碼語言是一種包括高階程式語言的3種基本控制結構 順序 選擇和迴圈 和自然語言成分的 物件導向 的語言。演算法的特徵 1 可行性 一是演算法中的每個步驟必須是能實現的 二是演算法執行的結果要能達到預期的目的。2 確定性 演算法的...
資料結構與演算法
課程設計報告 目錄一 問題描述1 二 資料結構1 三 演算法設計思想及流程圖1 四 源程式2 五 測試情況6 參考文獻6 一 問題描述 計算表示式的值 問題描述 對於給定的乙個表示式，表示式中可以包括常數 算術執行符和括號，編寫程式計算表示式的值。基本要求 從鍵盤輸入乙個正確的中綴表示式，將中綴表示...
《資料結構》作業
本課程作業由兩部分組成。第一部分為 客觀題部分 由選擇題組成，每題1分，共15分。第二部分為 主觀題部分 由簡答題和應用題組成，共15分。作業總分30分，將作為平時成績記入課程總成績。客觀題部分 一 選擇題 每題1分，共10題 1 順序儲存結構中資料元素之間的邏輯關係是由 表示的。a.線性結構 b....