二維鏈表在重要天氣預告圖填圖原理中的應用

摘要：在重要天氣預告圖制作過程中，如何利用計算機圖形學制作出一個應用軟件供天氣預告員使用，是我們要解決的問題。該文闡述了利用二維鏈表作為基礎結構實現重要天預告圖填圖的基本原理以及采用二維鏈表實現該原理的過程，現在利用該原理開發出來的軟件已經在全國安裝使用，具有很好的推廣價值和業務使用價值。

關鍵詞：填圖；繪圖對象；圖層；二維鏈表

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)28-0193-03

Two-dimensional Chain in the Principle of Important Weather Forecast Map Mapping

SUN Sheng-yao，DONG Yang，WANG Fei-fei

( College of Computer Information Engineering， Henan University， Kaifeng Henan 475001，China)

Abstract: In an important weather forecast map production process， how to use computer graphics to produce weather forecast application software for the use of， is that we must solve the problem. This paper describes the use of two-dimensional chain infrastructure as an important day notice of plans to achieve mapping the basic principles and the adoption of two-dimensional realization of the principle of the chain process， using the principles of the software has been developed in the installation are very good Promote the value and business value.

Key words: mapping;object mapping;mapping layer;two-dimensional graphics objects Listless

1 引言

重要天氣預告圖是在民航系統中，飛機在低空飛行過程中飛行安全的重要依據材料；例如在西南地區廣漢航站；飛機飛行于低空的過程中，需要飛行機組人員知道飛行的航線上哪里有影響安全飛行的天氣情況，以便于機組人員在起飛前或者飛行過程做出調整，以確保飛機飛行的安全。現階段我國重要天氣預告圖制作采用得主要是手工手段，處理起來極其的不方便，如何利用電腦圖形學快速的制作出天氣預告圖，采取怎么樣的原理制作，是要解決的重點。

根據各方面的需求和民航總局提出的具體要求，經過認真的分析，考慮各種情況，最終采用二維鏈表的作為底層各種天氣符號的存取的數據結構，本文依據重要天氣預告圖填圖軟件的設計思想和底層的實現，闡述為什么會最終采用二維鏈表作為底層的數據存取結構和采用二維鏈表的優點。

本文組織如下，第二節介紹了從最簡單的一個天氣符號的情況到復雜的多個符號處理分別采用的數據結構，并比較其中的優缺點，最終統一到二維鏈表結構中，第三節具體模擬一下整個的工作過程，第四節介紹和很多出圖軟件比較采用二維鏈表的優點，最后總結。

2 二維鏈表在重要天氣預告圖中的應用

2.1 概念的引入

現在利用各種高級語言都可以在屏幕上通過語言控制，在電腦屏幕上繪制圖形，做出一張天氣效果圖并不困難，作圖的難點在于，當圖中有顯示的天氣符號發現有錯誤時（比如天氣符號的位置在圖上標示錯誤了），應該如何處理；假如按照標示錯了，把原來的圖摒除不要，然后再重新畫一張，這個處理方式肯定不行的，這樣作圖的效率非常低，并且不允許在作圖過程中出現任何差錯；處理的思路應該是發現標示錯了要么進行調整，要么把錯誤的符號刪除掉，然后重新畫在屏幕上；也就是說現在應該有這樣的思路：設計一種數據類型，在這個數據類型里，可以通過某種方式，發現某個錯誤的天氣符號，還可以動態的添加、刪掉某個符號；這是設計填圖軟件時考慮的首要解決的問題。

這個數據結構會自然的聯想到鏈表；鏈表可以動態的添加、刪除和找到某一個接點，符合剛才設想的數據類型，并且算法也很成熟，根據上面的敘述，涉及到鏈表的算法有：

插入操作：（算法1）

Proc ins_linklist(la:linkisttp;i:integer;b:elemtp)

{la為指向帶頭節點的單鏈表頭指針，本算法在鏈表中第i個元素之前插入元素b}

P:=la;j:=0{指針初始化；j為計數器}

While(p<>nul)And (j

If（p=nul）or(j>i-1)

Then error(‘No this position’){插入位置不合理}

Else[new(s);s↑.data=b;{生成新接點}

s↑.next=p↑.next;p↑.next=s;{插入完成}

]

Endp

刪除操作：（算法2）

Proc del_linklist(la:linkisttp;i:interger)

{la為指向頭結點的單鏈表的頭指針，當1<=i<=表長時，本算法刪除表中的第i個元素結點}

P:=la;j:=0;{指針初始化，j為計數器}

While(p↑.next<>nil) and(j

{尋找第i個接點，并令p指向它的前驅接點}

If(p↑.next=nil) or (j>i-1)

Then error(‘No this Position’){i<1或i>表長}

Else[q:=p↑.next;p↑.next:=p↑.next↑.next;

Dispose(q){釋放被刪接點}

]

Endp；

得到某一接點算法：（算法3）

Func get_linklist(la:linkisttp;i:interger):elemtp;

{ la為指向頭結點的單鏈表的頭指針，當1<=i<=表長時，返回第i個數據元素，否則返回空元素1}

P:=la;j:=1;{指針初始化，j為計數器}

While(p<>nil) and (j

{順指針查找指向第i個元素結點或指針為空}

If(p<>nil) and (j=i)

Then return (p↑.data)

Else return(1)

Endp;

定位函數：（算法4）

Func loc_sqlist(va:sqlisttp;x:elemtp):integer

{在鏈表va中查找第一個值和小相同的元素，若存在則返回該元素在鏈表中的位序，否則返回0}

i:=1;{i指示鏈表中元素的位序}

while (i<=va.last) cand (va.elem[i]<>x)do i：=i+1；

if(i<=va.last)then return(i) else return(0)

endp;

2.2 只有一個天氣符號的調整

找到實現的數據結構后，接下來考慮鏈表接點中應該存儲什么樣的數據對象，先考慮天氣預告圖上只有一個天氣符號的情況。如果需要在屏幕上（起名為畫布）繪制天氣符號，因該需要這些確切的信息：什么天氣符號，在畫布上的準確位置，顯示的寬與高；根據這些信息抽象成一個類：命名為：DrawObject，其中屬性包括：

Drawobject對象類：

屬性：位置和大小（位置：x、y；高：Height；寬：Width）；天氣圖像（Bitmap）

其中的“位置和大小”屬性可以用當前天氣符號的外接矩形來代替；這時候DrawObject的屬性成為：外接矩形；天氣符號（bitmap）；那么鏈表中的每個節點就放一個DrawObject類對象。

當在畫布上畫一個天氣符號時，發現天氣符號在天氣圖上標示錯誤，應該這樣調整：首先把新的調整后的DrawObject對象對現有的DrawObject對象賦值，然后直接在畫布上畫即可，具體實現步驟為：

Step 1 重新聲明一個新的DrawObject對象

Step 2 給調整后的值賦給聲明的對象（外接矩形，天氣圖像）

Step 3 用新對象代替原來的對象

Step 4 在畫布上畫調整后的DrawObject對象；

Step 5 完成調整。

對于錯誤的調整方式和以上步驟一致，只是在第二步中把天氣的圖形屬性調整過程中換成需要的天氣符號圖形即可。

2.3 多個天氣符號在單鏈表中調整

單個符號調整非常容易，當畫布上有多個天氣符號時，調整其中的某一時，應該如何處理；不妨設現在已經把在畫布上的多個天氣符號存放到了鏈表（List）中;如果調整齊中的一個首先需要找到要調整的，然后進行相應的調整，具體步驟：

Step1找到要調整的天氣符號，調用算法4；

Step2記錄下來調整的天氣符號在鏈表中的位置，在該結點上調用2.1處理單個天氣符號的方式

Step3在畫布上重新繪制List< DrawObject >調整后所有天氣符號對象。

Step4完成體調整；

在step3中，在畫布上重新繪制調整后的鏈表時，是把鏈表中記錄的所有天氣符號都重新繪制了一遍，為什么不是調整哪個天氣符號就重新繪制哪個呢，主要是考慮到調整的過程中每次調整可能不止是一個符號，有可能每次要調整多個，比如一次性把多個天氣符號的位置改變，這個時候如果每次都要調用鏈表找到某一個節點的方法，按照計算機中處理問題的最壞算法，算法復雜度將是（N2），如果采用以上的方式算法復雜度為（N）

2.4 圖層概念在填圖中的應用

在填圖的過程中，一張天氣預告圖上是一個天氣符號的可能性很小，如果每次都是按照2.3的方式處理，每次調整都是把鏈表中每個天氣符號都要重新繪制，這時算法效率是非常低的；在填圖過程中，總是會有一部分天氣符號不需要調整，即在調整中不需要每次都要重新繪制所有的符號，而是只需要繪制其中經常調整的符號；基于這種考慮，在填圖過程軟件設計中引入了二維鏈表的概念。具體示意圖為：

■

圖1

在圖1中，橫向鏈表記錄的是填圖過程中天氣符號信息，從整體上觀察，鏈表好像一層一層的，把縱向鏈表命名為圖層，縱向鏈表的每個節點都記錄了當前層中一系列天氣符號的公共信息，比如某層中一系列符號是否在調整時需要重新繪制，在畫布上有很多天氣符號時，當前層的天氣符號是否需要顯示等一系列屬性，把圖層也抽象化一個類對象，命名為layer其中屬性有：

當前層是否可見：IsVissal

當前層是否活動：IsActive

當前層是否選中：IsSelected

在縱向圖層鏈表中涉及到算法有圖層的添加、圖層的移除、設置圖層是否可見、設置圖層是否活動、設置圖層是否被選中；

具體算法設置為：

添加圖層操作：調用算法1；

圖層移去算法：調用算法2；

設置圖層是否可見、設置圖層是否活動、設置圖層是否被選中調用算法3，操作的步驟是首先找到要設置的圖層，然后設置相應的屬性。

這個時候二維鏈表數據結構為：

List，其中layer=list

天氣符號在二維鏈表里存儲，然后再畫布上重新繪制，基于設置二維鏈表的考慮和重新繪制過程中效率的考慮，當前處于活動的圖層只能有一個，也就是說把經常做調整天氣符號都放到某一個圖層中，即當前活動層，當作某一符號調整時，只需要重新繪制當前活動層里面記錄的天氣符號即可;這并不代表那些不在“經常調整鏈表”的天氣符號就不能做調整了，可以通過設置活動層的方式把原來不活動的圖層，設置成新的活動圖層，然后再對新活動圖層調整，以完成調整過程，具體操作步驟為：

Step 1 找到當前活動的圖層（或者是設置某一層為活動層）；調用算法4；

Step 2 找到要調整的天氣符號，調用算法4；

Step 3 把相應調整的值重新賦值給當前調整地符號；

Step 4 開始重新繪制；

Step 5 完成調整。

3 二維鏈表在填圖軟件中的工作過程

在2.2和2.3討論的情況都可以統一到二維鏈表的中，2.1單個天氣符號的情況相當于圖層鏈表只有一層，天氣符號鏈表結點也只有一個情況；對于2.3中多個天氣符號在單鏈表調整的情況相當于圖層鏈表有一層，天氣符號鏈表結點有多個；現在整體模擬一下二維鏈表在填圖軟件中是具體的工作步驟。

3.1 二維鏈表添加天氣符號過程

Step 1初始化鏈表；

Step 2聲明一個天氣符號對象，把要在畫布上顯示的屬性賦值給該天氣符號；

Step 3在二維鏈中調用算法1加入一個圖層接點；

Step 4在當前圖層中調用算法1，加入一個繪圖對象接點；

Step 5把剛才聲明的天氣符號對象，賦值給新申請的對象接點

Step 6如果繼續添加新的天氣符號，轉回Step 2；

Step 7如果當前的活動層符號不再做調整，回到Step 1；

Step 8得到活動層，遍歷活動層鏈表在畫布上重新繪制；

Step 9完成。

3.2 符號調整的過程

Step1得到當前整個二維鏈表

Step2得到當前活動的圖層編號，調用算法4

Step3得到調整的符號在當前活動層中序號，調用算法4；

Step4得到在鏈表中的位置i，如果刪除調用算法2；如果調整，把要調整的屬性賦給位置i的符號。

Step5得到活動層，遍歷活動層鏈表在畫布上重新繪制；

Step6完成調整。

3.3 調整某一圖層的過程

Step1調用算法4，獲得要調整的圖層編號；

Step2如果移出圖層，調用算法2

Step3把設置新的圖層的屬性賦值給當前的圖層，設置的屬性包括當前的圖層是否為可見，把當前圖層設置為不活動的等；

Step4得到活動層，遍歷活動層鏈表在畫布上重新繪制；

Step5完成調整。

4 二維鏈表在填圖軟件中的使用的優點

采用二維鏈表作為天氣預告圖填圖軟件的存儲數據的數據結構，具有很多的優點：

1) 可以很好的滿足初始設計的理念；現在我國很多地區作天氣預告圖，仍然采用手工方式，采用二維鏈表作為設計數據存儲對象制作出的填圖軟件，把天氣預告圖的制作利用計算機處理，能很好提高工作效率；大大提高了天氣預告圖制作的準確性和及時性。

2) 二維鏈表可以提高在重新繪制過程中效率問題，把經常調整的天氣符號對象放到二維鏈表活動圖層中，可以在每次調整中不用把二維鏈表中的每個天氣符號對象都重新繪制；只需要繪制一部天氣符號就可以完成調整過程。

3) 和其他的很多的作圖軟件比較，采用二維鏈表作為底層的數據結構不但能實現其他作圖軟件的所有功能，而且還能提供其他作圖軟件不具備的作圖功能，比如現在比較流行的Snigit抓圖軟件，沒有圖層的概念和某些圖形不可見得概念，利用二維鏈表作存儲結構制作出來的填圖軟件不但具有圖層概念，而且也可以設置某一圖層里面的天氣符號不顯示等一系列功能，最重要的是采用二維鏈表作為存儲結構，比采用單鏈表效率要高。

5 總結

本文集中討論了怎樣在設計填圖軟件時，如何考慮選擇二維鏈表作為底層實現的數據結構和采用二維鏈表好處的；通過采用二維鏈表，使得在重要天氣預告圖填圖軟件設計實現的過程中能夠快速的設計出用戶需求的軟件，利用這個原理制作的軟件現在已經在全國的很多地區安裝使用，用戶普遍反映這個軟件簡單易用，具有很好的推廣價值。

二維鏈表的在填圖軟件中使用的設計理念不單是針對于重要天氣預告圖填圖軟件具有很好指導作用，其他很多的填圖軟件制作時也可以采用這套理論，為他人制作填圖軟件提供了很好的借鑒價值，有助于其他人快速的設計出功能更加強大的填圖軟件。

參考文獻：

[1] 孫正興，馮桂煥，周若鴻.基于手繪草圖的人機交互技術研究進展[J].計算機輔助設計與圖形學學報，2005，17(9):1889-1899.

[2] Landay J A， MyersB A1 Sketchinginterfaces: toward more hu2man interface design [J].1 IEEE Computer，2001，34(3):56-64.

[3] Lin J，Newman M W DENIM:finding a tighter fit between tools and practice for1web site design[C].Proceedings of SIGCHI Conference on Human Factors in ComΠputinΠ g Systems，New York，2000:510-517.

[4] 嚴蔚敏.數據結構[M].2版，北京:清華大學出版社，1992.

[5] 姚家弈.計算機圖像技術及其應用[M].北京:國防工業出版社，1998.

[6] 李朝暉.用雙向鏈表實現繪圖軟件中的幾個常用功能[J].河北理工學院學報，2000，22(2):63-68.

[7] 馮桂煥，孫正興，謝強，鄭文濤.基于手繪草圖的方案設計CAD系統[J].計算機輔助設計與圖形學學報，2007(6):58-63.

[8] 王琦，魯東明.中國書畫的計算機虛擬繪制概述[J].計算機輔助設計與圖形學學報，2007(2):3-10.