GIS數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)

1、什么是“結(jié)構(gòu)”結(jié)構(gòu)是指組成整體的各元素的搭配和安排什么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)是組成數(shù)據(jù)整體的各元素的搭配和安排?！皵?shù)據(jù)結(jié)構(gòu)”的意義“數(shù)據(jù)結(jié)構(gòu)”并不關(guān)注數(shù)據(jù)整體中各個(gè)元素的具體數(shù)值，而是關(guān)注元素之間的關(guān)聯(lián)方式。同一類型信息的不同實(shí)體所對(duì)應(yīng)的數(shù)據(jù)整體，在元素的具體數(shù)字上可能并不一致，但在結(jié)構(gòu)(關(guān)聯(lián)方式)上往往具有相當(dāng)?shù)囊恢滦?。?shù)據(jù)結(jié)構(gòu)中的基本概念和術(shù)語數(shù)據(jù)(Data):是客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中指的是所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱數(shù)據(jù)元素(DataElement):是數(shù)據(jù)的基本單位,在程序中通常作為一個(gè)整體來進(jìn)行考慮和處理數(shù)據(jù)項(xiàng)(DataItem):一個(gè)數(shù)據(jù)元素可由若干

2、個(gè)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項(xiàng)是對(duì)客觀事物某一方面特性的數(shù)據(jù)描述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)m“算法”：將信息處理過程轉(zhuǎn)換為運(yùn)算過程的理論。算法的表達(dá)：形式化方式（流程圖，偽代碼）一一算法的設(shè)計(jì)計(jì)算機(jī)程序代碼和機(jī)器碼一一算法的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的形式化表達(dá)的基本規(guī)則是什么？概念明確化，信息符號(hào)化，結(jié)構(gòu)規(guī)則化算法的特征自主、序貫、操作指令算法的要求：IPO正確性：對(duì)于任意符合預(yù)定義要求的輸入數(shù)據(jù)，算法給的對(duì)應(yīng)輸出結(jié)果都應(yīng)該是正確的（符合預(yù)定義）；確定性：算法的每步操作都必須有明確的、與執(zhí)行者無關(guān)的結(jié)果可計(jì)算性：算法的每步操作最終都由有限幾種運(yùn)算操作組成有窮性：對(duì)于任意輸入數(shù)據(jù)，算法都能在

3、運(yùn)行有限次操作后結(jié)束，盡管“有限次”可能是個(gè)非常龐大的數(shù)字;文件頭存儲(chǔ)與文件基本特征相對(duì)應(yīng)的數(shù)據(jù)（元數(shù)據(jù)）信息記錄幾何體空間坐標(biāo)記錄，相當(dāng)于文件的正文一.shp文件的文件頭可以進(jìn)一步分解為更細(xì)致的結(jié)構(gòu)任何.shp文件的文件頭都具有相同的長(zhǎng)度和結(jié)構(gòu)總體上看，文件頭包含基本識(shí)別信息和空間信息概況兩部分#.shp文件的空間信息記錄這部分內(nèi)容沒有固定的長(zhǎng)度，其長(zhǎng)度由存儲(chǔ)的幾何體數(shù)量和幾何體具體特征決定；#總體上是由同類型的幾何體空間定位坐標(biāo)記錄依次排列連接而成#雖然長(zhǎng)度不固定，但是空間信息記錄仍然遵循統(tǒng)一的格式，每一個(gè)單獨(dú)的幾何體記錄都由記錄頭信息和記錄信息兩部分組成是文件中真正的空間信息部分每一個(gè)幾

4、何體信息分為兩部分：開始的部分為intShapeType之后是空間坐標(biāo)記錄結(jié)構(gòu)化算法設(shè)計(jì)的基本思路自頂向下逐層分解每一個(gè)層次都只包含盡量簡(jiǎn)潔的流程表達(dá)，用層次化分解應(yīng)對(duì)算法的復(fù)雜性中間層次中多采用描述性的文字而不是計(jì)算式表達(dá)框圖含義圖的基本定義設(shè)集合V表示所有的節(jié)點(diǎn)(頂點(diǎn))，集合E表示所有的邊；無向圖記做G(V,E),圖中任一條邊都可以用節(jié)點(diǎn)的無序?qū)Ρ硎荆涀鰁ij=vi,vj或者eij=vj,vi;有向圖記做D(V,E),圖中任一條邊都要用節(jié)點(diǎn)的有序?qū)Ρ硎?，記做eij=<vi,vj>或者eij=(vi,vj);為了區(qū)分，一般將有向圖中的邊稱為“弧”；如果圖中既有有向邊也有無向邊則

5、稱為混合圖，混合圖可以通過將無向邊拆成兩條方向相反的有向邊的方法轉(zhuǎn)換成有向圖賦權(quán)圖圖中的每一條邊（弧）eij均有一個(gè)權(quán)數(shù)wij相對(duì)應(yīng)的圖稱為賦權(quán)圖；圖的幾種常見存儲(chǔ)結(jié)構(gòu)：鄰接矩陣，鄰接鏈表,Arc-Node表鄰接矩陣在無向圖中,如果節(jié)點(diǎn)vi和vj之間存在一條邊,則稱vi與vj互相鄰接；在有向圖中,如果節(jié)點(diǎn)vi到vj之間存在一條弧,則稱vi與vj鄰接；將圖的節(jié)點(diǎn)按順序編號(hào)為（1,2,巾），構(gòu)造一個(gè)n*n矩陣，其行和列均與節(jié)點(diǎn)一一對(duì)應(yīng)，如果i節(jié)點(diǎn)與j節(jié)點(diǎn)鄰接，則矩陣（i,j）單元賦值為1,反之賦值為0,這樣的矩陣稱為圖的“鄰接矩陣”；二維的鄰接矩陣可以按行掃描的方式存儲(chǔ)到一維的線性存儲(chǔ)空間中。鏈表:分散式存儲(chǔ)結(jié)構(gòu)計(jì)算機(jī)通過“存儲(chǔ)地址”來讀寫數(shù)據(jù)，因此如果在數(shù)據(jù)元素中加入若干表達(dá)地址的數(shù)據(jù)項(xiàng)，就可以將數(shù)據(jù)元素分散存儲(chǔ)在不連續(xù)的位置，并通過表達(dá)地址的數(shù)據(jù)項(xiàng)將它們關(guān)聯(lián)起來形成數(shù)據(jù)結(jié)構(gòu)；為了提高存儲(chǔ)效率，使用分散結(jié)構(gòu)時(shí)，一般在數(shù)據(jù)元素中加入的地址數(shù)據(jù)項(xiàng)數(shù)目是固定的；一種常見的情況是使用一個(gè)地址數(shù)據(jù)項(xiàng)，這樣的分散結(jié)構(gòu)就構(gòu)成了鏈表。鏈表的優(yōu)勢(shì)在于存儲(chǔ)數(shù)據(jù)可以動(dòng)態(tài)添加和刪除利用