拓?fù)溧徑雨P(guān)系模擬演示程序-----基于GIS底層關(guān)系-畢業(yè)論文

1、廈門大學(xué)軟件學(xué)院學(xué)士論文本科畢業(yè)論文(科研訓(xùn)練、畢業(yè)設(shè)計(jì))題 目：拓?fù)溧徑雨P(guān)系模擬演示程序-基于GIS底層關(guān)系姓 名：學(xué) 院：軟件學(xué)院系：專 業(yè)：軟件工程年 級：學(xué) 號：指導(dǎo)教師（校內(nèi)）： 職稱：指導(dǎo)教師（校外）： 職稱： 年 月 日拓?fù)溧徑雨P(guān)系模擬演示程序 -基于GIS底層關(guān)系摘要：隨著計(jì)算機(jī)軟硬件水平的提高，促使地理信息系統(tǒng)（GIS）向?qū)嵱梅较蝻w速發(fā)展，GIS的應(yīng)用已經(jīng)從基礎(chǔ)信息的管理與規(guī)劃轉(zhuǎn)向更復(fù)雜的區(qū)域開發(fā)、預(yù)測預(yù)報(bào)，并與衛(wèi)星遙感技術(shù)相結(jié)合用于全球監(jiān)測、輔助決策等越來越廣闊的應(yīng)用領(lǐng)域。廈門億力吉奧信息科技有限公司隸屬于福建省電力集團(tuán)，公司宗旨是開發(fā)基于電網(wǎng)的GIS系統(tǒng)，為電力資源管理服

2、務(wù)，更好地合理調(diào)度電力資源，提高電網(wǎng)的效益。拓?fù)潢P(guān)系是電力網(wǎng)中最基本的底層關(guān)系之一。本文深入地剖析了拓?fù)潢P(guān)系對GIS的重要性，并對拓?fù)潢P(guān)系的結(jié)構(gòu)定義和應(yīng)用進(jìn)行研究，就拓?fù)潢P(guān)系中鄰接關(guān)系作為切入點(diǎn)，通過探討圖中點(diǎn)和邊的連接關(guān)系變化引起整個拓?fù)鋽?shù)據(jù)庫的變化，并結(jié)合公司的需要，我們開發(fā)了基于底層拓?fù)溧徑雨P(guān)系的模擬演示程序TPARSS（Topology adjacent relation Simulation procedure）。在TPARSS設(shè)計(jì)中，我們把復(fù)雜的電網(wǎng)系統(tǒng)抽象成一個簡單的圖。圖中的點(diǎn)節(jié)點(diǎn)表示電網(wǎng)系統(tǒng)中的桿塔（電線桿），配電站，變壓器等設(shè)施，邊節(jié)點(diǎn)表示這些設(shè)施之間的電線連線，對這個圖中

3、節(jié)點(diǎn)的操作代表了電網(wǎng)系統(tǒng)中幾個基本問題操作的情況。關(guān)鍵字：地理信息系統(tǒng) 拓?fù)潢P(guān)系 拓?fù)湫畔?鄰接關(guān)系A(chǔ)bstract：With the level of computers software and hardware improvement, make GIS developing forward utility direction at very fast speed, the applications of GIS have turned from management and programming of basic info into more complexity area impl

4、ode, forecast prediction, and combine secondary planet remote sensing technique for used in the seven seas inspect, assist decision-making etc. more and more broad application area.Xiamen Yilijiao Information Science and Technique corporation belong to fujian province electric power group, the tenet

5、 of company is develop GIS system based on electric power, service for electric resource management, even more get well in attempter electric resource in reason, improve benefit of electric network. Topology relation is one of the more basic bottom relation of electric network.The text go deep into

6、analysis the topology relations importance to GIS, study the structure definition and application of topology relation, treat topology relations adjacency relation as disquisitive emphases, through discussing change of link relation between point and edge in graphic arouse change of wholly topology

7、database , we develop TPARSS(Topology adjacent relation Simulation procedure) based bottom topology relation.During design of TPARSS , we abstract complex electric network system into a simple graphic. Point node in graphic show telegraph pole, electric-distribute station, transformer etc. establish

8、ment in electric network system, edge point show wire link between establishment, manipulation of graphics node show several basic question solution in electric network system.Keywords: GIS(Geographic Information System) Topology Relations Topology Information Adjacent relation目錄引言5第一章 地理信息系統(tǒng)(GIS)61

9、.1公司背景61.2地理信息與地理信息系統(tǒng)61.3 GIS的分類61.4 GIS中的拓?fù)潢P(guān)系及其表示71.4.1 拓?fù)涞母拍?1.4.2 拓?fù)潢P(guān)系的意義7第二章 TPARSS設(shè)計(jì)需求分析82.1 功能點(diǎn)要求82.2 需求分析：9第三章 TPARSS算法設(shè)計(jì)113.1 概要規(guī)格設(shè)計(jì)113.2 詳細(xì)規(guī)格設(shè)計(jì)123.2.1 界面設(shè)計(jì)123.2.2點(diǎn)節(jié)點(diǎn)及其拓?fù)溥B接信息的增加143.2.3 點(diǎn)節(jié)點(diǎn)拓?fù)溥B接信息的刪除163.2.4 節(jié)點(diǎn)刪除173.3 編碼設(shè)計(jì)183.3.1 CNodeManagerDlg（實(shí)現(xiàn)各個界面切換及刪除節(jié)點(diǎn)的功能）183.3.2 CAddNodeDlg（實(shí)現(xiàn)增加節(jié)點(diǎn)及其拓?fù)溥B接

10、信息的功能）193.3.3 CDelNodeDlg(實(shí)現(xiàn)刪除節(jié)點(diǎn)拓?fù)溥B接信息的功能)20第四章 TPARSS測試報(bào)告214.1增加節(jié)點(diǎn)214.2 增加節(jié)點(diǎn)拓?fù)溥B接信息224.3刪除連接邊234.4刪除連接點(diǎn)244.5刪除點(diǎn)節(jié)點(diǎn)254.6刪除邊節(jié)點(diǎn)26結(jié)論28致謝語29參考文獻(xiàn)30引言地理信息系統(tǒng)(Geographic Information System，簡稱GIS)是由計(jì)算機(jī)軟硬件支持，對地理空間（包括地理表面、地下、地上和其他人類生產(chǎn)與生活所感知到的空間）數(shù)據(jù)進(jìn)行采集、存儲、管理、分析和表達(dá)的信息系統(tǒng)。它是一門集計(jì)算機(jī)科學(xué)、地理學(xué)、測繪遙感學(xué)、環(huán)境科學(xué)、城市科學(xué)、空間科學(xué)、信息科學(xué)、應(yīng)用數(shù)

11、據(jù)、管理科學(xué)為一體的新興科學(xué)。計(jì)算機(jī)軟硬件水平的提高，促使GIS向?qū)嵱梅较蝻w速發(fā)展，GIS的應(yīng)用已經(jīng)從基礎(chǔ)信息的管理與規(guī)劃轉(zhuǎn)向更復(fù)雜的區(qū)域開發(fā)、預(yù)測預(yù)報(bào)，并與衛(wèi)星遙感技術(shù)相結(jié)合用于全球監(jiān)測、輔助決策等越來越廣闊的應(yīng)用領(lǐng)域。在當(dāng)前大多數(shù)的GIS中，由矢量地圖數(shù)據(jù)庫構(gòu)成系統(tǒng)的基礎(chǔ)數(shù)據(jù)庫，矢量數(shù)據(jù)不僅包含必要的幾何坐標(biāo)數(shù)據(jù)，還包括重要的拓?fù)潢P(guān)系數(shù)據(jù)。拓?fù)潢P(guān)系在GIS的編碼、輸入、格式轉(zhuǎn)換、存儲管理、查詢分析等應(yīng)用中都有重要作用，是GIS的特色之一。拓?fù)鋵W(xué)是一種新興的幾何學(xué)，是研究圖形（或形狀）的科學(xué)。它之所以較新，是因?yàn)樗芯康氖菆D形在連續(xù)變形下的不變的整體性質(zhì)。拓?fù)鋵W(xué)中的運(yùn)動可以稱作“彈性運(yùn)動”，

12、對圖形可以任意地伸張、扭曲、拉縮，但圖形中的各點(diǎn)仍為不同的點(diǎn)。一個圖形中的拓?fù)湫再|(zhì)是那些與此圖形等價的圖形都具有的性質(zhì)。因此，圖形的拓?fù)湫再|(zhì)就是那些在彈性運(yùn)動中保持不變的性質(zhì)圖形的任何彈性運(yùn)動都毫不改變圖形的拓?fù)湫再|(zhì)。所以拓?fù)鋵W(xué)也叫“彈性拓?fù)鋵W(xué)”。本文合公司的需要，我們開發(fā)了基于底層拓?fù)溧徑雨P(guān)系的模擬演示程序（TPARSS）。在TPARSS設(shè)計(jì)中，我們把復(fù)雜的電網(wǎng)系統(tǒng)抽象成一個簡單的圖。圖中的點(diǎn)節(jié)點(diǎn)和邊節(jié)點(diǎn)分別表示電網(wǎng)系統(tǒng)中的設(shè)施和這些設(shè)施之間的電線連線。對這個圖中節(jié)點(diǎn)的操作代表了電網(wǎng)系統(tǒng)中幾個基本問題操作的情況。主要分為：1）點(diǎn)節(jié)點(diǎn)的增加2）點(diǎn)節(jié)點(diǎn)和邊節(jié)點(diǎn)的刪除3）點(diǎn)節(jié)點(diǎn)和邊節(jié)點(diǎn)拓?fù)溥B接信息

13、的增加和刪除這個模擬系統(tǒng)對以后工作中的電網(wǎng)建模系統(tǒng)，以及實(shí)際中電網(wǎng)的一些具體問題和拓?fù)潢P(guān)系作一次深入的研究，為公司的軟件開發(fā)打下理論基礎(chǔ)。第一章 地理信息系統(tǒng)(GIS)1.1公司背景在世界經(jīng)濟(jì)模式從現(xiàn)行的以自然資源為主的工業(yè)經(jīng)濟(jì)模式往未來的信息資源為主的知識經(jīng)濟(jì)模式轉(zhuǎn)換過程中，信息（Information）是最寶貴和重要的資源，信息的獲取、展示和傳播需要根本性的改革，“信息高速公路”、“知識經(jīng)濟(jì)”、“數(shù)字地球”都是為此而提出的嶄新概念，其特征為“信息電子化”，GIS就是在信息技術(shù)飛速發(fā)展的今天，圍繞信息的獲取和展示應(yīng)運(yùn)而生的最前沿的領(lǐng)先科技。1.2地理信息與地理信息系統(tǒng)地理信息（Geograp

14、hic Information）是指表征地理系統(tǒng)諸要素的數(shù)量、質(zhì)量、分布特征、相互聯(lián)系和變化規(guī)律的數(shù)字、文字、圖像和圖形等的總稱。地理信息屬于空間信息，其位置的識別是與數(shù)據(jù)聯(lián)系在一起的，這是地理信息區(qū)別于其它類型信息的最顯著的標(biāo)志。地理信息的這種定位特征，是通過經(jīng)緯網(wǎng)或者公路網(wǎng)建立的地理坐標(biāo)來實(shí)現(xiàn)空間位置識別的。地理信息還具有多維結(jié)構(gòu)的特征，即在二維空間的基礎(chǔ)上實(shí)現(xiàn)多專題的第三維結(jié)構(gòu)。而各個專題之間的聯(lián)系是通過屬性碼進(jìn)行的，這就是地理系統(tǒng)各圈層之間的綜合研究提供了可能，也為地理系統(tǒng)多層次的分析和信息的傳輸與篩選提供了方便。地理信息系統(tǒng)（Geographic Information System

15、,簡稱GIS）是以采集、存儲、管理、描述、分析地球表面及空間和地理分布有關(guān)的數(shù)據(jù)的信息系統(tǒng)。它是以地理空間數(shù)據(jù)庫為基礎(chǔ)，在計(jì)算機(jī)硬、軟件環(huán)境的支持下，對空間相關(guān)數(shù)據(jù)進(jìn)行采集、管理、操作、分析、模擬和顯示，并采用地理模型分析方法，適時提供多種空間和動態(tài)的地理信息，為地理研究、綜合評價、管理、定量分析和決策服務(wù)而建立起來的一類計(jì)算機(jī)應(yīng)用系統(tǒng)。簡而言之，地理信息系統(tǒng)是以計(jì)算機(jī)為工具，具有地理圖形和空間定位功能的空間型數(shù)據(jù)管理系統(tǒng)，是一類特殊而又十分重要的信息系統(tǒng)。1.3 GIS的分類 專題信息系統(tǒng) Thematic Information System是具有有限目標(biāo)和專業(yè)特點(diǎn)的地理信息系統(tǒng)，為特定的

16、專門目的服務(wù)，如森林動態(tài)監(jiān)測信息系統(tǒng)、水資源管理信息系統(tǒng)、礦產(chǎn)資源信息系統(tǒng)、農(nóng)作物估產(chǎn)信息系統(tǒng)、草場資源管理信息系統(tǒng)、水土流失信息系統(tǒng)等。 區(qū)域地理信息系統(tǒng) Regional Information System主要以區(qū)域綜合研究和全面信息服務(wù)為目標(biāo)?？梢杂胁煌?guī)模，如國家級的、地區(qū)或省級的、市級或縣級等為各不同級別行政區(qū)服務(wù)的區(qū)域信息系統(tǒng)，也可以按自然分區(qū)或流域?yàn)閱挝坏膮^(qū)域信息系統(tǒng)。1.4 GIS中的拓?fù)潢P(guān)系及其表示1.4.1 拓?fù)涞母拍钔負(fù)鋵W(xué)是一種新興的幾何學(xué)，是研究圖形（或形狀）的科學(xué)。它之所以較新，是因?yàn)樗芯康氖菆D形在連續(xù)變形下的不變的整體性質(zhì)。拓?fù)鋵W(xué)中的運(yùn)動可以稱作“彈性運(yùn)動”，對

17、圖形可以任意地伸張、扭曲、拉縮，但圖形中的各點(diǎn)仍為不同的點(diǎn)。一個圖形中的拓?fù)湫再|(zhì)是那些與此圖形等價的圖形都具有的性質(zhì)。因此，圖形的拓?fù)湫再|(zhì)就是那些在彈性運(yùn)動中保持不變的性質(zhì)圖形的任何彈性運(yùn)動都毫不改變圖形的拓?fù)湫再|(zhì)。所以拓?fù)鋵W(xué)也叫“彈性拓?fù)鋵W(xué)”。1.4.2 拓?fù)潢P(guān)系的意義拓?fù)潢P(guān)系反映了空間實(shí)體之間不隨實(shí)體的連續(xù)變形而改變的與量度和方向無關(guān)的一種空間關(guān)系 ,對于GIS中數(shù)據(jù)的編碼、錄入、格式轉(zhuǎn)換、存儲管理、查詢檢索、空間分析都有重要意義，是GIS的特色之一。在GIS中，表示拓?fù)潢P(guān)系的數(shù)據(jù)屬于厄余數(shù)據(jù)，也就是說，拓?fù)鋽?shù)據(jù)并非必不可少，這是因?yàn)橥ㄟ^對幾何數(shù)據(jù)的計(jì)算可以隨時構(gòu)造拓?fù)潢P(guān)系。既然如此，為什

18、么大多數(shù)GIS仍舊存儲拓?fù)鋽?shù)據(jù)呢？這是出于那些構(gòu)造拓?fù)潢P(guān)系的計(jì)算所花費(fèi)的代價可能會很昂貴，比如綜合分析和連通性分析就是很費(fèi)時的運(yùn)算，如果有明確的拓?fù)潢P(guān)系數(shù)據(jù)作依據(jù)，這些問題的復(fù)雜度將會大大降低。具體地說，拓?fù)潢P(guān)系數(shù)據(jù)的作用體系在以下幾個方面：l 協(xié)助完成有關(guān)線狀要素聯(lián)結(jié)關(guān)系的分析，如連通性分析；l 協(xié)助完成有關(guān)線狀要素連接次序的分析，如路徑選擇；l 幫助進(jìn)行面狀要素的鄰接性分析；l 通過建立拓?fù)潢P(guān)系可以自動發(fā)現(xiàn)某些數(shù)據(jù)錯誤；l 幫助查找附近的要素，如緩沖區(qū)分析；l 幫助搜索相關(guān)的要素，如根據(jù)用戶要求進(jìn)行組合查詢時可能用到拓?fù)潢P(guān)系；l 通過將幾何坐標(biāo)數(shù)據(jù)與結(jié)構(gòu)數(shù)據(jù)分開，使數(shù)據(jù)更新更加方便；l 降

19、低了只使用幾何數(shù)據(jù)的局限性；l 更易于把基本的空間要素組合形成復(fù)合要素；l 為地圖自動配置和轉(zhuǎn)換提供基礎(chǔ)；l 協(xié)助進(jìn)行空間推理第二章 TPARSS設(shè)計(jì)需求分析在TPARSS設(shè)計(jì)中，我們把復(fù)雜的電網(wǎng)系統(tǒng)抽象成一個簡單的圖。圖中的點(diǎn)節(jié)點(diǎn)表示電網(wǎng)系統(tǒng)中的桿塔（電線桿），配電站，變壓器等設(shè)施，邊節(jié)點(diǎn)表示這些設(shè)施之間的電線連線。兩個點(diǎn)之間有線連接表示這兩個設(shè)施之間有電線連通，增加一個新的節(jié)點(diǎn)表示增加一個新的設(shè)施，增加節(jié)點(diǎn)之間的拓?fù)溥B接信息表示在這幾個點(diǎn)表示的設(shè)施之間增加新的連線（即之間有電路連通），刪除一個節(jié)點(diǎn)的拓?fù)溥B接信息表示中斷之間的連線或者關(guān)閉某一個設(shè)施，刪除一個點(diǎn)節(jié)點(diǎn)表示撤走某一個設(shè)施，刪除一個

20、邊節(jié)點(diǎn)表示刪除某一段的電線連接。這個模擬系統(tǒng)對以后工作中的電網(wǎng)建模系統(tǒng)，以及實(shí)際中電網(wǎng)的一些具體問題和拓?fù)潢P(guān)系作一次深入的研究，為公司的軟件開發(fā)打下理論基礎(chǔ)。在這個設(shè)計(jì)中，我和陳鈞共同負(fù)責(zé)。我負(fù)責(zé)底層數(shù)據(jù)的處理，即拓?fù)湫畔⒌脑黾?，拓?fù)湫畔⒌母?。陳鈞負(fù)責(zé)將己處理好的數(shù)據(jù)用圖形顯示出來。例如主界面（即主要用于圖形顯示）通過一個菜單選項(xiàng)和節(jié)點(diǎn)管理界面（用于管理節(jié)點(diǎn)操作）交互。我進(jìn)行節(jié)點(diǎn)管理，節(jié)點(diǎn)拓?fù)溥B接信息的增加和顯示，節(jié)點(diǎn)拓?fù)溥B接信息的刪除的設(shè)計(jì)，并且根據(jù)不同的操作顯示不同的界面，即我負(fù)責(zé)CNodeManagerDlg類，CAddNodeDlg類，CDelNodeDlg類的函數(shù)的實(shí)現(xiàn)。程序之間的

21、交互通過界面間的切換進(jìn)行交互，通過各個類中控件的消息映射處理調(diào)用其他的界面進(jìn)行交互。2.1 功能點(diǎn)要求1) 圖中節(jié)點(diǎn)的信息分別存儲于數(shù)據(jù)庫的三個表中。node，topNode，topEdge。其中node表包括三個字段，如表2-1所示：Node表：節(jié)點(diǎn)類型節(jié)點(diǎn)的分局碼節(jié)點(diǎn)的EID1表示點(diǎn)，6表示邊表2-1topNode表包括點(diǎn)節(jié)點(diǎn)的拓?fù)溥B接信息。包括四個字段，如表2-2所示：topNode表點(diǎn)的分局碼點(diǎn)的EID點(diǎn)的連接邊的數(shù)目點(diǎn)的具體的連接信息包括每個連接邊和連接點(diǎn)的信息表2-2連接邊的信息包括連接邊的分局碼、EID和連通有效性；連接點(diǎn)的信息包括連接的分局碼和EID。topEdge表包括邊節(jié)點(diǎn)

22、的拓?fù)溥B接信息，包括四個字段，如表2-3所示：topEdge表邊的分局碼邊的EIDFrom節(jié)點(diǎn)To節(jié)點(diǎn)From端點(diǎn)和to端點(diǎn)的信息分別包括每個端點(diǎn)的分局碼、EID，連通有效性表2-32) TopNode表中的點(diǎn)的具體連接信息的字段中連接邊的信息中有一項(xiàng)關(guān)于連通有效性的子項(xiàng)，這個子項(xiàng)表示這條連接邊是否有相應(yīng)的連接點(diǎn)。3) 圖中的邊為無向邊。4) 可以任意增加一個新的節(jié)點(diǎn)及其拓?fù)溥B接信息。5) 可以任意增加一個已經(jīng)存在的節(jié)點(diǎn)的拓?fù)溥B接信息。6) 可以任意刪除一個節(jié)點(diǎn)。7) 可以任意刪除一個點(diǎn)的連接邊或者連接點(diǎn)。8) 對于增加的連接信息，可以只增加連接邊而不增加連接點(diǎn)。9) 對于刪除的連接信息，可以

23、刪除連接邊，也可以只刪除連接點(diǎn)。10) 對于增加和刪除的節(jié)點(diǎn)或者節(jié)點(diǎn)的連接信息在數(shù)據(jù)庫中能實(shí)時體現(xiàn)?？梢噪S意的查詢每個節(jié)點(diǎn)的信息。2.2 需求分析：1） 保持各個數(shù)據(jù)庫之間的數(shù)據(jù)信息相對應(yīng)。a) 在node表的點(diǎn)節(jié)點(diǎn)在topNode表有相應(yīng)的點(diǎn)拓?fù)湫畔⒐?jié)點(diǎn)，在node表中的邊節(jié)點(diǎn)在topEdge表中有相應(yīng)的邊拓?fù)湫畔⒐?jié)點(diǎn)。在topNode表和topEdge表中的節(jié)點(diǎn)在node表中都有相應(yīng)的節(jié)點(diǎn)記錄。如圖2-1所示：Node表點(diǎn)A。邊a。TopNode表點(diǎn)A拓?fù)溥B接信息。TopEdge表邊a拓?fù)溥B接信息。圖2-1b) 在點(diǎn)的連接信息中連接邊的連通有效性的信息要與這個邊的拓?fù)溥B接信息中的數(shù)據(jù)相對應(yīng)

24、。如果連通有效性為是，則這個邊的拓?fù)湫畔⒅衒rom端點(diǎn)和to端點(diǎn)都應(yīng)該有端點(diǎn)的信息。如果連通有效性為非，則這個邊的拓?fù)湫畔⒅兄挥幸粋€端點(diǎn)的信息。c) 在點(diǎn)的連接信息中每個點(diǎn)之間的信息應(yīng)該是互相對應(yīng)。如果點(diǎn)A有一條邊a與點(diǎn)B相連。則在點(diǎn)A的拓?fù)溥B接信息中有連接邊a和連接點(diǎn)B。在點(diǎn)B的拓?fù)溥B接信息中有連接邊a和連接點(diǎn)A。如表2-4所示：TopNode表點(diǎn)A。；連接邊a，連接點(diǎn)B；。點(diǎn)B。；連接邊a，連接點(diǎn)A；。表2-4d) 在點(diǎn)的拓?fù)溥B接信息中連接邊的信息要與這個連接邊的邊拓?fù)溥B接信息中的數(shù)據(jù)向?qū)?yīng)。如果點(diǎn)A有連接邊a和這條連接邊相應(yīng)的連接點(diǎn)B。則在邊a的拓?fù)溥B接信息中點(diǎn)A和點(diǎn)B分別是邊a的兩個端

25、點(diǎn)。同理類推于點(diǎn)B。如果點(diǎn)A有連接邊b，連接邊b沒有連接點(diǎn)。則在邊b的拓?fù)溥B接信息中只有一個端點(diǎn)：點(diǎn)A。如表2-5，表2-6所示：TopNode表點(diǎn)A。；連接邊a，連接點(diǎn)B；。；連接邊b，；點(diǎn)B。；連接邊a，連接點(diǎn)A；。表2-5TopEdge表邊a點(diǎn)A點(diǎn)B邊b點(diǎn)A表2-62） 增加一個新的點(diǎn)及其拓?fù)溥B接信息。a) 首先在node表中和topNode表中要增加這個點(diǎn)的記錄，在topNode表中更新連接信息。b) 其次對于每個連接邊和連接點(diǎn)，如果是新增加的邊和點(diǎn)，需要在node表中增加這些記錄。并且在topNode表中增加每個新增加的點(diǎn)的記錄，更新它們的連接信息。在topEdge表中增加每個新增加

26、的邊的記錄，更新它們的from端點(diǎn)和to端點(diǎn)的信息。3） 增加一個已經(jīng)存在的點(diǎn)的拓?fù)溥B接信息。a) 首先對于新增的連接信息在topNode表中這個點(diǎn)的記錄中體現(xiàn)出來，如果有新的連接邊和連接點(diǎn)，在node表中增加這些記錄。b) 其他對于topNode表和topEdge表的操作和增加一個新節(jié)點(diǎn)相同。4） 刪除一個節(jié)點(diǎn)。a) 首先在node表中刪除這個點(diǎn)的記錄。b) 如果這個節(jié)點(diǎn)是點(diǎn)節(jié)點(diǎn)，在topNode表中要刪除這個點(diǎn)的記錄。并且這個點(diǎn)的所有連接點(diǎn)的連接信息要修改，刪除掉有關(guān)這個點(diǎn)的信息。這個點(diǎn)的所有連接邊的端點(diǎn)信息也要修改，刪除掉以這個點(diǎn)為端點(diǎn)的from端點(diǎn)或者to端點(diǎn)的信息。c) 如果刪除的這

27、個節(jié)點(diǎn)是邊節(jié)點(diǎn)，topEdge表中要刪除這個邊的記錄。并且這個邊的from端點(diǎn)和to端點(diǎn)的點(diǎn)節(jié)點(diǎn)的連接信息也要修改，刪除掉這個邊的信息。5） 可以任意刪除一個點(diǎn)的連接邊或者連接點(diǎn)。a) 如果刪除一個連接邊，首先在node表中和topEdge表中這個要刪除這個邊的記錄。并且這個連接邊的from端點(diǎn)和to端點(diǎn)的點(diǎn)節(jié)點(diǎn)的連接信息也要刪除掉這個邊的連接信息。b) 如果刪除一個連接點(diǎn)。首先在topNode表中要修改這個點(diǎn)的連接信息，刪除掉這個連接點(diǎn)，保留連接邊。在topEdge表中這個連接邊的連接信息也要修改，刪除掉以這個點(diǎn)為端點(diǎn)的from端點(diǎn)或者to端點(diǎn)的信息。第三章 TPARSS算法設(shè)計(jì)3.1 概要

28、規(guī)格設(shè)計(jì)1） 語言環(huán)境本項(xiàng)目采用Microsoft Visual C+語言，使用MFC完成整個的程序設(shè)計(jì)，并且通過classWizard方便地完成消息映射和數(shù)據(jù)轉(zhuǎn)換，縮短編程的時間，使程序設(shè)計(jì)從一些很繁瑣的界面設(shè)計(jì)和消息處理的工作中解脫出來。2） 與數(shù)據(jù)庫的連接數(shù)據(jù)庫使用Microsoft Access。使用ADO與數(shù)據(jù)庫進(jìn)行連接并操作數(shù)據(jù)庫。ADO是建立在OLE DB底層技術(shù)之上的高級程序接口，因而它具有強(qiáng)大的數(shù)據(jù)處理功能（處理各種不同類型的數(shù)據(jù)源、分布式的數(shù)據(jù)處理等等）和極其簡單、易用的編程接口。3） 界面設(shè)計(jì)軟件界面的設(shè)計(jì)要清晰明了，便于使用。界面要包含所有的操作，并且界面的各個控件之間

29、關(guān)系不能模糊不清。在這個程序中包含有下拉式菜單，多個對話框。每個對話框之間的關(guān)系要明確?？丶娘@示要根據(jù)不同的操作的情況而定。每個特定的界面要清楚、明確地顯示出要表達(dá)的信息。界面設(shè)計(jì)貫穿與節(jié)點(diǎn)的操作過程中，針對不同的操作和不同的信息界面的顯示也各不相同。4） 點(diǎn)節(jié)點(diǎn)增加增加一個點(diǎn)節(jié)點(diǎn)，則在node表和topNode表中都要增加相應(yīng)的記錄。并且彼此相對應(yīng)。5） 節(jié)點(diǎn)刪除刪除一個節(jié)點(diǎn)，則在node表和相應(yīng)的topNode表（或者topEdge表）中的記錄都會被刪除，并且這個與這個節(jié)點(diǎn)相關(guān)的其他節(jié)點(diǎn)的信息也要相應(yīng)地進(jìn)行修改。6） 節(jié)點(diǎn)拓?fù)溥B接信息的增加可以增加若干條節(jié)點(diǎn)拓?fù)溥B接信息。對于新增加的連接

30、邊和連接點(diǎn)，在node表和topNode表、topEdge表中都要增加相應(yīng)的記錄。并且它們的連接信息要正確地記錄新增加的連接信息。對于已經(jīng)存在的連接邊和連接點(diǎn)，則要根據(jù)增加的信息修改它們的拓?fù)溥B接信息。7） 節(jié)點(diǎn)連接信息的刪除可以刪除任何一條連接邊或者連接點(diǎn)。對于刪除掉的信息，在node表和topEdge表和topNode表中要對這個刪除的信息所相關(guān)的節(jié)點(diǎn)的信息作相應(yīng)的改動。刪除連接邊和刪除連接點(diǎn)要分別處理，刪除連接邊和刪除連接點(diǎn)所引起的信息的變化是不同的。8） 節(jié)點(diǎn)顯示可以顯示任何一個點(diǎn)節(jié)點(diǎn)的所有連接邊和連接點(diǎn)或者任何一個邊節(jié)點(diǎn)的兩個端點(diǎn)。3.2 詳細(xì)規(guī)格設(shè)計(jì)3.2.1 界面設(shè)計(jì)界面分為一個

31、主界面，和三個對話框。主界面有一塊畫圖的區(qū)域用來做圖的圖形顯示。這個畫圖的區(qū)域的坐標(biāo)是左上角的坐標(biāo)是（0，0），x值是向右增加，y值是向下增加。如圖3-1所示：y增加x增加（0，0）圖3-1對話框分為管理數(shù)據(jù)對話框，增加和顯示數(shù)據(jù)對話框，刪除數(shù)據(jù)對話框。主界面可以通過下拉菜單的選項(xiàng)與這幾個對話框交互。主界面如圖3-2所示：圖3-2管理數(shù)據(jù)對話框可以和刪除數(shù)據(jù)對話框和增加并顯示數(shù)據(jù)對話框交互（增加和顯示數(shù)據(jù)使用同一個對話框），如圖3-3所示。刪除數(shù)據(jù)對話框和增加數(shù)據(jù)對話框不能交互。管理數(shù)據(jù)對話框包含了節(jié)點(diǎn)各種操作所需要的控件。圖3-3增加和顯示數(shù)據(jù)對話框包含了節(jié)點(diǎn)增加和顯示時所需要的控件，并且針

32、對于增加和顯示兩種不同的操作，顯示的界面和控件的顯示狀態(tài)是不同的。顯示的界面如圖3-4所示，增加的界面如圖3-5所示：圖3-4圖3-5刪除數(shù)據(jù)對話框包含了刪除節(jié)點(diǎn)連接信息所需要的控件。如圖3-6所示：圖3-63.2.2點(diǎn)節(jié)點(diǎn)及其拓?fù)溥B接信息的增加單獨(dú)增加點(diǎn)節(jié)點(diǎn)比較簡單，直接在node表和topNode表中增加這個記錄就可以了。而點(diǎn)節(jié)點(diǎn)拓?fù)溥B接信息的增加就會比較復(fù)雜一些，它可以同時增加多條連接信息，每增加一條連接信息，假設(shè)點(diǎn)A增加連接邊a和連接點(diǎn)B，它主要分下面幾個步驟進(jìn)行：（1） 首先判斷要增加的連接邊a是否存在，a） 如果增加的連接邊a已經(jīng)存在，（即在topEdge表中有邊a的記錄，則取出邊

33、a的兩個端點(diǎn)進(jìn)行判斷）1. 則要判斷這條連接邊是否有兩個端點(diǎn)，如果邊只有一個端點(diǎn)，并且這個端點(diǎn)是點(diǎn)A或者是要增加的連接點(diǎn)點(diǎn)B，則可以修改邊a的拓?fù)溥B接信息。否則表示這是一條錯誤的連接信息，將直接退出這條連接信息增加的操作。2. 如果邊a有兩個端點(diǎn)，表示這是一條錯誤的連接信息，退出操作。b） 如果增加的連接邊a不存在，直接在topEdge表中增加這條邊的記錄。（2） 然后判斷要增加的連接信息（包括連接邊和連接點(diǎn)）是否正確（從topNode表中取出這個點(diǎn)節(jié)點(diǎn)的具體連接信息進(jìn)行判斷）a） 如果要增加的連接點(diǎn)B已存在，這是一個簡單的連通圖，不允許兩條點(diǎn)之間存在直接連接的多條邊，所以這是一個錯誤信息，退

34、出操作。b） 如果要增加的連接邊a已存在并且它的連接有效性為是，這表示一條邊的的另一端有兩個端點(diǎn)，所以這是一個錯誤信息，對出操作。c） 如果要增加的連接邊a已存在并且它的連接有效性為非，這表示向這條邊的另一端加上了連接的端點(diǎn)點(diǎn)B，直接增加這條信息。d） 如果要增加的連接邊不存在，則直接加入這個連接信息。（3） 向node表中增加邊a的記錄（4） 如果這個連接點(diǎn)點(diǎn)B是新增加的點(diǎn)節(jié)點(diǎn)，直接向node表和topNode表中增加這個點(diǎn)B的點(diǎn)節(jié)點(diǎn)記錄，然后在topNode表中修改這個點(diǎn)B的點(diǎn)節(jié)點(diǎn)記錄：增加這個新的連接信息，連接邊邊a，連接點(diǎn)點(diǎn)A。（5） 還有一種情況就是增加的連接信息中只有連接邊a，沒有

35、連接點(diǎn)。則只進(jìn)行上述的（1），（2），（3）步驟就可以了。這個過程的流程圖如圖3-7： 否 退出輸入連接邊a，連接點(diǎn)B（可選）在topEdge表中判斷邊a增加的拓?fù)湫畔⑹欠裾_是是 否,退出在node表中加入邊節(jié)點(diǎn)a如果只輸入了連接邊，而沒有輸入連接點(diǎn)否在node表和topNode表中加入點(diǎn)節(jié)點(diǎn)B，在topNode表中修改點(diǎn)B的連接信息 是,退出在topNode表中判斷點(diǎn)A增加的拓?fù)湫畔⑹欠裾_圖3-73.2.3 點(diǎn)節(jié)點(diǎn)拓?fù)溥B接信息的刪除點(diǎn)節(jié)點(diǎn)拓?fù)溥B接信息的刪除分為刪除連接邊和連接點(diǎn)。假設(shè)點(diǎn)A有連接邊a和相應(yīng)的連接點(diǎn)B（1） 刪除連接邊a，分為下面幾個步驟。a） 首先在topNode表中找到點(diǎn)

36、A的拓?fù)溥B接信息，并取出點(diǎn)A的具體連接信息。把這個連接邊a和其相應(yīng)的連接點(diǎn)B的信息從點(diǎn)A的連接信息中刪除。b） 然后再topNode表中找到這個連接點(diǎn)B的拓?fù)溥B接信息，并取出這個連接點(diǎn)的具體連接信息。把這個連接邊a和點(diǎn)A的信息從連接點(diǎn)B的連接信息中刪除。c） 然后將邊a的記錄從topEdge表中和node表中刪除。d） 另外一種特殊的情況就是連接邊a沒有相應(yīng)的連接點(diǎn)，則只要進(jìn)行第a），c）步驟。整個過程的流程圖如圖3-8是否在topNode表中將連接邊a和相應(yīng)的連接點(diǎn)從點(diǎn)A的連接信息中刪除如果連接邊a有相應(yīng)的連接點(diǎn)B在topNode表中將連接邊a和相應(yīng)的連接點(diǎn)A從點(diǎn)B的連接信息中刪除在node

37、表中將邊節(jié)點(diǎn)a的記錄刪除圖3-8（2） 刪除連接點(diǎn)B，分為下面幾個步驟a） 首先在topNode表中找到點(diǎn)A的拓?fù)溥B接信息，并取出點(diǎn)A的具體連接信息。把連接點(diǎn)B的信息從點(diǎn)A的連接信息中刪除，注意，連接邊a的信息保留，不過連接邊a的連接有效性改為非。b） 然后在topEdge表中找到邊a的拓?fù)溥B接信息，并將端點(diǎn)是點(diǎn)B的信息刪除。c） 最后在topNode表中找到連接點(diǎn)B的拓?fù)溥B接信息，并取出連接點(diǎn)B的具體連接信息。把連接邊a和點(diǎn)A的信息從連接點(diǎn)B的信息中刪除。整個過程的流程圖如圖3-9在topNode表中將連接點(diǎn)B從點(diǎn)A的連接信息中刪除在topNode表中將連接邊a和相應(yīng)的連接點(diǎn)A從點(diǎn)B的連接信

38、息中刪除在topNode表中將連接點(diǎn)B從點(diǎn)A的連接信息中刪除圖3-93.2.4 節(jié)點(diǎn)刪除節(jié)點(diǎn)刪除分為點(diǎn)節(jié)點(diǎn)刪除和邊節(jié)點(diǎn)刪除。（1） 刪除點(diǎn)節(jié)點(diǎn)。假設(shè)刪除點(diǎn)節(jié)點(diǎn)A，點(diǎn)A有連接邊a和連接點(diǎn)B，連接邊b和連接點(diǎn)C，連接邊c（連接邊c無連接點(diǎn)）。要刪除點(diǎn)A分下面的步驟進(jìn)行：a) 打開topNode表，查詢每一條記錄。如果當(dāng)前記錄是點(diǎn)A，刪除這條記錄。如果當(dāng)前記錄是連接點(diǎn)B或者連接點(diǎn)C，將點(diǎn)A的信息從它們的連接信息中刪除。b) 打開topEdge表，查詢每一條記錄。如果當(dāng)前記錄是邊a或者邊b，將點(diǎn)A的信息從它們的連接信息中刪除。如果當(dāng)前記錄是邊c，直接將這條記錄刪除。c) 打開node表，查詢每一條記錄

39、。如果當(dāng)前記錄是點(diǎn)A，刪除這條記錄。如果當(dāng)前記錄是邊c，刪除這條記錄。（2） 刪除邊節(jié)點(diǎn)。假設(shè)刪除邊節(jié)點(diǎn)a，邊a的兩個端點(diǎn)分別為點(diǎn)A和點(diǎn)B。要刪除邊a分下面幾個步驟進(jìn)行：打開topEdge表，將邊a的記錄刪除a) 打開topNode表，找到點(diǎn)A的拓?fù)溥B接信息，并取出點(diǎn)A的具體連接信息。把這個連接邊a和其相應(yīng)的連接點(diǎn)B的信息從點(diǎn)A的連接信息中刪除。b) 打開topNode表，找到點(diǎn)B的拓?fù)溥B接信息，并取出點(diǎn)B的具體連接信息。把這個連接邊a和其相應(yīng)的連接點(diǎn)A的信息從點(diǎn)B的連接信息中刪除。c) 打開node表，查詢每一條記錄。如果當(dāng)前記錄是邊a，刪除這條記錄。3.3 編碼設(shè)計(jì) 主要使用了下面三個類實(shí)

40、現(xiàn)程序的主要功能3.3.1 CNodeManagerDlg（實(shí)現(xiàn)各個界面切換及刪除節(jié)點(diǎn)的功能）CNodeManagerDlg類的變量和函數(shù)說明如表3-1：CNdeManagerDlgCListCtrlm_ctrlEdgesLst;/邊節(jié)點(diǎn)列表的變量CListCtrlm_ctrlNodesLst;/點(diǎn)節(jié)點(diǎn)列表的變量void OnNodeShow();/將界面切換到顯示點(diǎn)節(jié)點(diǎn)信息的界面void OnLinkDelete();/將界面切換到刪除點(diǎn)節(jié)點(diǎn)連接信息的界面void OnNodeAdd();/增加一個新的點(diǎn)節(jié)點(diǎn)及其拓?fù)溥B接信息或者增加一個已存在點(diǎn)節(jié)點(diǎn)的連接信息void OnWindowExit

41、();/退出管理界面BOOL OnInitDialog();void OnNodeDelete();/刪除一個點(diǎn)節(jié)點(diǎn)void OnEdgeShow();/將界面切換到顯示邊節(jié)點(diǎn)信息的界面void OnEdgeDelete();/刪除一個邊節(jié)點(diǎn)void DeleteLinkEdge(CString divi, CString ei, CString leDivi, CString leEi);/在topNode表中將分局碼和EID為divi和ei的記錄的連接信息中的連接邊的分局碼和EID分別為leDivi和leEi的信息刪除void DelEdgeFromTopEdge(CString divi

42、, CString ei, CString &fDivi, CString &fEi, CString &tDivi, CString &tEi);/在TopEdge表中將分局碼和EID分別為divi和ei的邊節(jié)點(diǎn)拓?fù)溥B接信息刪除void DelNodeFromNode(int type, CString divi, CString ei, CString lInfo ="" );/在node表中將類型、分局碼和EID分別為type，divi和ei的記錄，及其相關(guān)的記錄刪除void DelNodeFromTopEdge(CString div

43、i, CString ei);/在topEdge表中修改from端點(diǎn)或者to端點(diǎn)的分局碼和EID為divi和ei的記錄，將這個點(diǎn)從這條記錄中刪除void DelNodeFromTopNode(CString divi, CString ei, CString &lInfo);/在topNode表中刪除分局碼和EID分別為divi和ei的記錄，并將連接信息中連接點(diǎn)包括分局碼和EID為divi和ei的信息從這條記錄的連接信息中刪除void ListNodes();/分別將點(diǎn)節(jié)點(diǎn)和邊節(jié)點(diǎn)的信息顯示在點(diǎn)節(jié)點(diǎn)列表和邊節(jié)點(diǎn)列表上void AddListCtrlHeader();/加入點(diǎn)節(jié)點(diǎn)列表和邊

44、節(jié)點(diǎn)列表的表頭表3-13.3.2 CAddNodeDlg（實(shí)現(xiàn)增加節(jié)點(diǎn)及其拓?fù)溥B接信息的功能）CAddNodeDlg類的變量和函數(shù)說明如表3-2：CAddNodeDlgint m_nRows, m_nCols, m_nFixRows, m_nFixCols, m_nStartRow;/這些變量表示自定義列表的列和行的屬性int m_nNodeDividCol, m_nNodeEidCol, m_nEdgeDividCol, m_nEdgeEidCol, m_nEdgeLinkCol,m_nEdgeMark, m_nNodeMark;/這些變量表示連接邊和連接點(diǎn)的各個屬性在列表中列的位置CStr

45、ingm_strDivid;CStringm_strEid;CGridCtrl m_Grid;/自定義的列表的變量int m_nNodeType;/true表示一個增加一個新的拓?fù)涔?jié)點(diǎn),false表示在已存在的拓?fù)涔?jié)點(diǎn)上增加新的連接信息bool m_bShowNode;/1表示點(diǎn)，6表示邊bool m_bNewNode;/true表示查看節(jié)點(diǎn)信息，false表示增加節(jié)點(diǎn)信息CAddNodeDlg(CWnd* pParent = NULL);BOOL OnInitDialog();void OnSave();void OnExit();BOOL ModifyTopNode(CString div

46、i, CString ei, CString leDivi, CString leEi, CString lnDivi, CString lnEi);/增加分局碼和EID分別為divi和ei的點(diǎn)的連接信息，連接邊的分局碼和EID分別為leDivi和leEi，連接點(diǎn)的分局碼和EID分別為lnDivi和lnEivoid ShowNode(); /將節(jié)點(diǎn)的拓?fù)溥B接信息顯示在界面上void AddTopNode(CString divi, CString ei); /向topNode表中加入一條分局碼和EID分別是divi和ei的記錄BOOL AddNode(int type, CString div

47、i, CString ei);/向node表中加入一條節(jié)點(diǎn)類型、分局碼和EID分別為type，divi和ei的記錄BOOL AddTopedge(CString, CString, CString, CString, CString, CString);/向topEdge表加入一條新的記錄，或者根據(jù)輸入的信息修改舊的記錄void DeleteTopedge(CString divi, CString ei);/從topEdge表中刪除一條分局碼和EID分別是divi和ei的記錄BOOL JudgeInputReasonable(BOOL *RowReasonable);/判斷輸入的信息是否正確

48、完整表3-23.3.3 CDelNodeDlg(實(shí)現(xiàn)刪除節(jié)點(diǎn)拓?fù)溥B接信息的功能)CDelNodeDlg類的變量和函數(shù)說明如表3-3：CDelNodeDlgCListCtrl m_ctrlLNodesLst;/連接邊列表的變量CListCtrl m_ctrlLEdgesLst;/連接點(diǎn)列表的變量CString m_strDivid;CString m_strEid;void OnLinkDel();/刪除一條連接邊或者一個連接點(diǎn)void OnDelExit();BOOL OnInitDialog();void AddListCtrlHeader();/加入連接邊列表和連接點(diǎn)列表的表頭void S

49、howNode();/顯示這個節(jié)點(diǎn)的所有連接信息到連接邊列表和連接點(diǎn)列表中void DeleteTopedge(CString divi, CString ei);/在topEdge表中將分局碼和EID分別為divi和ei的記錄息刪除void DeleteEdgePoint(CString divi, CString ei, CString pDivi, CString pEi);/在topEdge表找出分局碼和EID分別為divi和ei的記錄，將端點(diǎn)的分局碼和EID分別為pDivi和pEi的信息刪除void EnableLinkEdge(CString divi, CString ei, C

50、String leDivi, CString leEi, bool enable);/在topNode表中找出分局碼和EID分別為divi和ei的記錄，將連接信息中連接邊的分局碼和EID為leDivi和leEi的相應(yīng)的連接點(diǎn)刪除void DeleteLinkEdge(CString divi, CString ei, CString leDivi, CString leEi);/在topNode表中找出分局碼和EID分別為divi和ei的記錄，將連接信息中連接邊的分局碼和EID為leDivi和leEi刪除void DeleteNode(int type, CString divi, CStri

51、ng ei);/在node表中將類型、分局碼和EID分別為type，divi和ei的記錄刪除表3-3第四章 TPARSS測試報(bào)告假設(shè)現(xiàn)在得數(shù)據(jù)庫中的數(shù)據(jù)如表4-1a，表4-1-b，表4-1-c所示：node表 topNode表typedivideIdEiddivideIdEidnumberlinkInfo0131,7,1,0,7,;1,2,1,0,2,;1,5,1,0,5,;0221,3,1,0,3,;1,2,1,0,1,;0311,3,1,0,2,;0411,4,1,0,7,;0511,5,1,0,1,;0731,7,1,0,1,;1,4,1,0,4,;1,8,1,0,8,;0811,8,1

52、,0,7,;表4-1-b101102103104105107108topEdge表divideIdEidfromInfotoInfo120,1,1,0,2,1,130,3,1,0,2,1,140,7,1,0,4,1,150,1,1,0,5,1,170,1,1,0,7,1,180,7,1,0,8,1,612613614615617618表4-1-a 表4-1-c圖形顯示如圖4-1所示，在對圖中的節(jié)點(diǎn)進(jìn)行操作后，數(shù)據(jù)會自動地更新。：圖4-14.1增加節(jié)點(diǎn)增加一個新的點(diǎn)（0，6）增加之后的數(shù)據(jù)如表4-2-a，表4-2-b所示：node表 topNode表typedivideIdEiddivideIdEidnumberlinkInfo060106表4-2-a 表4-