【正文】 徑上的前一個(gè)點(diǎn) public int LineID。//最短路徑中與前一個(gè)點(diǎn)之間的線的 ID public SearchLink SLink。//Open 或 Close 表中的鏈接 } class Link//點(diǎn)的鄰接關(guān)系 { public VERTEX v1。//每個(gè) Link 對(duì)象的 v1 都應(yīng)該指向它所附屬的點(diǎn)節(jié)點(diǎn) 內(nèi)蒙古科技大學(xué)畢業(yè)設(shè)計(jì) 說明書（畢業(yè) 論文 ） 21 public VERTEX v2。//每個(gè) Link 對(duì)象的 v2 都應(yīng)該指向與它所附屬的點(diǎn)相鄰的那個(gè)點(diǎn)節(jié)點(diǎn) public double weight。//線的權(quán)重 public Link v1Next。 public Link v2Next。 public int LineID。} class SearchLink//搜尋路徑時(shí)的鄰接關(guān)系，用來放入 Open 或 Close 表中 { public VERTEX v。 public SearchLink Prev。 public SearchLink Next。 } VERTEX 類用來存儲(chǔ)點(diǎn)節(jié)點(diǎn)， Link 類用來存儲(chǔ)鄰接關(guān)系， SearchLink 是一個(gè)臨時(shí)的中間鄰接關(guān)系，在尋徑時(shí)替代 VERTEX 實(shí)例進(jìn)行運(yùn)算，用來維持鄰接多重表。系統(tǒng)的主要功能函數(shù)為： private VERTEX BuildTopo(IFeatureLayer pFeatLayerP,IFeatureLayer pFeatLayerL,IPoint pStartV,IPoint pEndV,ref int PointCount,ref int EdgeCount)，主要用來建立拓?fù)潢P(guān)系 private void shortpath()，查詢最短路徑的主函數(shù) private void InsertOrder(SearchLink vIN,ref SearchLink vTO)按權(quán)重的升序插入 private void Insert(SearchLink vIN,ref SearchLink vTO)插入 private void Delete(ref SearchLink vOUT,ref SearchLink vFROM)從鏈表中刪除 建立拓?fù)潢P(guān)系 ： 內(nèi)蒙古科技大學(xué)畢業(yè)設(shè)計(jì) 說明書（畢業(yè) 論文 ） 22 VERTEX[]RoadNode=new VERTEX[NodeCount]。 indexP=0。 pFeatureP=()。 while(null!=pFeatureP) { indexP=(int)((ID))。 if(indexP0) { pFeatureP=()。 continue。 } RoadNode[indexP]=new VERTEX()。 RoadNode[indexP].Neighbor=null。 RoadNode[indexP].pPoint=(IPoint)。 RoadNode[indexP].Searched=0。 RoadNode[indexP].ShortPathPre=null。 RoadNode[indexP].Weight=。 pFeatureP=()。 } 首先建立 VERTEX 數(shù)組，用來存放點(diǎn)節(jié)點(diǎn)，在遍歷點(diǎn)層元素的過程中，根據(jù)點(diǎn)的ID 號(hào)找到數(shù)組索引號(hào)，生成點(diǎn)節(jié)點(diǎn)的實(shí)例（即 VERTEX 實(shí)例）。建立這一過程的時(shí)間消耗與點(diǎn)的數(shù)量 n 成正比，即時(shí)間復(fù)雜度為 O（ n）。 pFeatCsrL=(null,false)。 內(nèi)蒙古科技大學(xué)畢業(yè)設(shè)計(jì) 說明書（畢業(yè) 論文 ） 23 int indexP1=0,indexP2=0。 pFeatureL=()。 while(null!=pFeatureL)//遍歷線對(duì)象，根據(jù)線的首尾節(jié)點(diǎn) ID，即點(diǎn)的索引，找到點(diǎn)，建立鏈 接關(guān)系 { t1++。 tEdge++。 vLink1=vLink2=null。 pPointCol=(IPointCollection)。 p1=(0)。 p2=()。 vWork=。 flag1=flag2=0。 indexP1=(int)((STNODEID))。 indexP2=(int)((EDNODEID))。 indexP=(int)((FID))。 //依次獲得線元素的 STNODEID、 EDNODEID、 FID 三個(gè)字段的值 vLink1=new Link()。 =indexP。 =(double)(int)((Weight))。 =RoadNode[indexP1]。 =RoadNode[indexP1].Neighbor。 內(nèi)蒙古科技大學(xué)畢業(yè)設(shè)計(jì) 說明書（畢業(yè) 論文 ） 24 RoadNode[indexP1].Neighbor=vLink1。//獲得線元素的 STNODEID 值之后，直接可以得到點(diǎn)節(jié)點(diǎn)在數(shù)組中的位置 =RoadNode[indexP2]。 =RoadNode[indexP2].Neighbor。 RoadNode[indexP2].Neighbor=vLink1。 pFeatureL=()。 } 點(diǎn)的數(shù)組建立完成之后，可以開始遍歷線層元素，每取得一個(gè)線元素，則可以得到首尾節(jié)點(diǎn)的 ID，根據(jù)首尾節(jié)點(diǎn) ID（即首尾節(jié)點(diǎn)在數(shù)組中的索引）得到首尾節(jié)點(diǎn)，分別為首尾節(jié)點(diǎn)建立鄰接關(guān)系 vLink1 和 vLink2，從線元素獲得首尾節(jié)點(diǎn)的過程的時(shí)間復(fù)雜度為 O（ 1），而外層 while 循環(huán)是遍歷線層元素，時(shí)間復(fù)雜度為 O（ n），經(jīng)過這一過程 ，拓?fù)潢P(guān)系基本建立完成，由于采用數(shù)組存儲(chǔ) VERTEX 元素的目的是建立索引，減少建立拓?fù)潢P(guān)系時(shí)點(diǎn)的搜索時(shí)間，因此，拓?fù)潢P(guān)系建立完成后，為了方便運(yùn)算，也為了盡量減少數(shù)組元素所占用的大塊內(nèi)存區(qū)域，把 VERTEX 元素從數(shù)組中摘下并建立環(huán)狀鏈表： vWork=vHead。 for(indexP=1。indexPNodeCount。indexP++) { if(RoadNode[indexP]!=null) { RoadNode[indexP].Prev=vWork。 RoadNode[indexP].Next=。 =RoadNode[indexP]。 =RoadNode[indexP]。 內(nèi)蒙古科技大學(xué)畢業(yè)設(shè)計(jì) 說明書（畢業(yè) 論文 ） 25 vWork=RoadNode[indexP]。 } } =vHead。 =vWork。 通過這一步操作，環(huán)狀的鄰接多重表建立完成。以上三次遍歷并沒有嵌套關(guān)系，因此整個(gè)建立鄰接多重表的時(shí)間復(fù)雜度為 O（ n）。 查詢最短路徑 查詢最短路徑： int flag=0。 int c=0。 vWork=。 while(cPointCnt){//根據(jù)點(diǎn)節(jié)點(diǎn)的數(shù)量，循環(huán)設(shè)定點(diǎn)節(jié)點(diǎn)中各字段的初始值 if(==pStartID) { flag++。=vWork。 } if(==pEndID) { flag++。 =vWork。 } 內(nèi)蒙古科技大學(xué)畢業(yè)設(shè)計(jì) 說明書（畢業(yè) 論文 ） 26 =0。 =null。 =。 vWork=。 c++。 } 由于鄰接多重表可以重復(fù)使用，因此 在一次尋徑后，鏈表中的節(jié)點(diǎn)的一些屬性值可能被改變，因此需要重新初始化節(jié)點(diǎn)的屬性值，如查詢狀態(tài) Searched、最短路徑前導(dǎo)節(jié)點(diǎn) ShortPathPre，最短路徑值 Weight 等。 sOpen=new SearchLink()。 sClose=new SearchLink()。 ==null。 =null。 ==null。 =null。 sTemp=new SearchLink()。 =。 =1。 =0。 =sTemp。 ==null。 Insert(sTemp,ref sOpen)。//Insert 函數(shù)按升序?qū)⒐?jié)點(diǎn) sTemp 插入鏈表 sOpen 中 while(!=nullamp。amp。!=2)//一旦鏈表 sOpen 變?yōu)榭?，或終點(diǎn)內(nèi)蒙古科技大學(xué)畢業(yè)設(shè)計(jì) 說明書（畢業(yè) 論文 ） 27 的最短路徑已經(jīng)找到，則查詢結(jié)束 { sTemp=。 vWork=。 vLink=。 =2。 Delete(ref sTemp,ref sOpen)。//在 sOpen 鏈表中找到權(quán)值最小節(jié)點(diǎn)之后，將該節(jié)點(diǎn)從鏈表 sOpen 中移除，并插入鏈表 sClose 中，表示該節(jié)點(diǎn)的最短路徑已經(jīng)找到 Insert(sTemp,ref sClose)。 while(vLink!=null)//遍歷節(jié)點(diǎn)的各個(gè)鄰接點(diǎn) { if(==0)//Searched 字段表名該鄰接點(diǎn)的搜索狀 態(tài)，如果是 0，則表示該鄰接點(diǎn)從未被搜索過 { =+。 =。 =1。 =vWork。 sTemp1=new SearchLink()。 =。 =sTemp1。 InsertOrder(sTemp1,ref sOpen)。 } 內(nèi)蒙古科技大學(xué)畢業(yè)設(shè)計(jì) 說明書（畢業(yè) 論文 ） 28 else if(==1)//Searched 如果為 1，則表示該鄰接點(diǎn)已經(jīng)搜索過，但還沒有找到最短路徑 { if(+)//如果權(quán)值不是最小，則需要重新計(jì)算權(quán)值 { Delete(ref ,ref sOpen)。 =+。 =。 =vWork。 InsertOrder(,ref sOpen)。 } } vLink=。 } } 在開始最短路徑查詢之前，首先定義兩個(gè)鏈表 sOpen 和 sClose， sClose 用來放置已經(jīng)找到最短路徑的節(jié)點(diǎn)， sOpen 用來放置已經(jīng)搜索但還沒有找到最短路徑、等待繼續(xù)搜索的節(jié)點(diǎn)。其次需要初始化鄰接多重表，將每一個(gè)節(jié)點(diǎn)的 Searched 字段置為 0，表明該節(jié)點(diǎn)還沒有被搜索過，并把節(jié)點(diǎn)權(quán)重置為無窮大（最大值）。這一過程為單循環(huán)，時(shí)間復(fù)雜度為 O（ n）。 以上是最短 路徑算法的主體部分，首先將源節(jié)點(diǎn)的 Searched 字段置為 1，權(quán)重置為0，并插入鏈表 sOpen 中，而后進(jìn)入循環(huán)搜索最短路徑的過程。外循環(huán)用來遍歷鏈表內(nèi)蒙古科技大學(xué)畢業(yè)設(shè)計(jì) 說明書（畢業(yè) 論文 ） 29 sClose，直到鏈表 sClose 變?yōu)榭?，或者最短路徑的終點(diǎn) vTail 的最短路徑被找到（ Searched字段變?yōu)?2）。而內(nèi)循環(huán)則遍歷 sOpen 中節(jié)點(diǎn)的鄰接關(guān)系，本算法實(shí)現(xiàn)過程中這一循環(huán)與節(jié)點(diǎn)數(shù)或線數(shù)并沒有數(shù)學(xué)關(guān)系，它的循環(huán)次數(shù)通常為 2～ 5 之間。在每次循環(huán)中，首先將節(jié)點(diǎn)置于鏈表 sClose 中，并把 Searched 值置為 2，表明該節(jié)點(diǎn)已經(jīng)找到最短路徑，然后遍歷該節(jié)點(diǎn) 的每一個(gè)鄰接點(diǎn)，首先判斷該鄰接點(diǎn)的搜索情況（ Searched 字段值），然后進(jìn)行插入或重新插入集合 sOpen 的操作（ InsertOrder），程序中設(shè)置了兩個(gè)插入函數(shù)InsertOrder 和 Insert， InsertOrder 函數(shù)專用來向 sOpen 中插入節(jié)點(diǎn)，這一過程需要進(jìn)行排序，因此隨著 sOpen 鏈表的規(guī)模增大，相應(yīng)的時(shí)間消耗也會(huì)增大，插入排序過程的時(shí)間復(fù)雜度為 O（（ n＋ 1） /2）。為了使計(jì)算最短路徑時(shí)搜索的節(jié)點(diǎn)范圍盡量縮小，程序中對(duì)每次更改 Searched 字段值之后的節(jié)點(diǎn)都要移出原集合（鏈表），這一方式使 單次搜索最短路徑的效率得到很大的提高。但是隨之而來的問題是 ,單次搜索之后，原來的鄰接多重表被破壞了，在下一次搜索前不得不重新建立鄰接多重表，由于建立鄰接多重表時(shí)如果數(shù)據(jù)量比較大，則程序需要頻繁訪問外存儲(chǔ)器，造成了大量的時(shí)間開銷。而 SearchLink類的引入，使得鄰接多重表可以“一次建立，多次使用”，真正提高算法的效率和實(shí)用性。 SearchLink 是純指針類，實(shí)例化的時(shí)候只占用很少的內(nèi)存開銷，因此這種以空間換時(shí)間的方法能夠有效的提高算法執(zhí)行的效率。 內(nèi)蒙古科技大學(xué)畢業(yè)設(shè)計(jì) 說明書（畢業(yè) 論文 ） 30 第五章 GPS 導(dǎo)航功能 衛(wèi)星導(dǎo)航技術(shù)的飛速發(fā)展已逐漸取代了無 線 電導(dǎo)航、天文導(dǎo)航等傳統(tǒng)導(dǎo)航技術(shù)，而成為一種普遍采用的導(dǎo)航定位技術(shù)，并在精度、實(shí)時(shí)性、全天候等方面取得了長足進(jìn)步?，F(xiàn)不僅應(yīng)用于物理勘探、電離層測量和航天器導(dǎo)航等諸多民用領(lǐng)域，在軍事領(lǐng)域更是取得了廣泛的應(yīng)用 —— 在彈道導(dǎo)彈、野戰(zhàn)指揮系統(tǒng)、精確彈道測量以及軍用地圖快速測繪等領(lǐng)域均大量采用了衛(wèi)星導(dǎo)航定位技術(shù)。有鑒于衛(wèi)星導(dǎo)航技術(shù)在民用和軍事領(lǐng)域的重要意義，使其得到了許多國家的關(guān)注。我國也于 20xx 年 10 月 31 日和 12 月 21 日成功發(fā)射了第一顆和第二顆導(dǎo)航定位試驗(yàn)衛(wèi)星并建立了我國第一代衛(wèi)星導(dǎo)航定位系統(tǒng) 北斗導(dǎo)航系統(tǒng) ， 但由于起步晚也沒有得到廣泛應(yīng)用。目前在我國應(yīng)用最多的還是美國的 GPS系統(tǒng)。 GPS 接收機(jī)可接收到準(zhǔn)確至納秒級(jí)的時(shí)間信息 ； 用于預(yù)報(bào)未來幾個(gè)月內(nèi)衛(wèi)星所處概略位置的預(yù)報(bào)星歷；用于計(jì)算定位時(shí)所需衛(wèi)星坐標(biāo)的廣播星歷，精度為幾米至幾十米（各個(gè)衛(wèi)星不同，隨時(shí)變化）；以及 GPS 系統(tǒng)信息，如衛(wèi)星狀況等。 GPS 接收機(jī)對(duì)碼的量測就可得到衛(wèi)星到接收機(jī)的距離，由于含有接收機(jī)衛(wèi)星鐘的誤差及大氣傳播誤差，故稱為偽距。對(duì) 0A 碼測得的偽距稱為 UA 碼偽距，精度約為 20 米左右，對(duì) P 碼測得的偽距稱為 P 碼偽距，精度約為 2 米左右。 GPS 接收機(jī)