第2章 計(jì)算機(jī)輔助系統(tǒng)開(kāi)發(fā)基礎(chǔ)知識(shí)-tcae2_1

1、第2章 計(jì)算機(jī)輔助系統(tǒng)開(kāi)發(fā)基礎(chǔ)知識(shí)2.1 數(shù)據(jù)結(jié)構(gòu)對(duì)于軟件開(kāi)發(fā)來(lái)說(shuō)，數(shù)據(jù)結(jié)構(gòu)具有重要的意義，所謂程序可以看作是數(shù)據(jù)結(jié)構(gòu)+算法。借助數(shù)據(jù)結(jié)構(gòu)可以采用相對(duì)規(guī)范的方法將編程對(duì)象加以表述。例如，當(dāng)我們需要在程序中記錄一組等高線數(shù)據(jù)，并要求表達(dá)它們之間的相鄰關(guān)系（這往往是為了在相鄰登高線之間建立三角形數(shù)字地面模型），可能就需要借助于樹(shù)型數(shù)據(jù)結(jié)構(gòu)了：這時(shí)我們利用等高線包圍的區(qū)域相互包含與否的關(guān)系，建立樹(shù)結(jié)構(gòu)。在圖21中，等高線A包圍的區(qū)域直接包含了等高線B、D所包圍的區(qū)域，B包圍的區(qū)域包A AC D BDBE E C（a）（b）圖21 利用樹(shù)來(lái)表示等高線之間的關(guān)系含了C所包圍區(qū)域，D所包圍區(qū)域包含了E所包

2、圍區(qū)域。為此建立如圖21（b）所示的數(shù)據(jù)結(jié)構(gòu)。這樣，只要在父節(jié)點(diǎn)與子節(jié)點(diǎn)，以及同級(jí)子節(jié)點(diǎn)之間進(jìn)一步判別等高線是否相鄰，除此之外的情況是屬于絕對(duì)不會(huì)相鄰的。棧圖2-2棧結(jié)構(gòu)示意棧就像在一個(gè)只打開(kāi)一端的乒乓球筒中放入乒乓球一樣（參見(jiàn)圖22），先放入的球需要后取出，具有元素的先進(jìn)后出特性，我們往往利用這一特性實(shí)現(xiàn)編程過(guò)程中的某些目的。例如，在機(jī)場(chǎng)場(chǎng)道設(shè)計(jì)CAD系統(tǒng)的平面布局設(shè)計(jì)工作中，由于工作帶有試探性質(zhì)，希望必要時(shí)能夠放棄一些剛剛完成的操作，以退回原來(lái)的某種狀態(tài)重新開(kāi)始。這時(shí)我們可以將所進(jìn)行的設(shè)計(jì)工作（例如增加了一條滑行道）按照完成的先后順序逐步加入一個(gè)信息棧中，當(dāng)需要退回原來(lái)的某一狀態(tài)時(shí)，從棧的

3、頂端逐步取出修改變化情況的信息，一步一步加以恢復(fù)。首先恢復(fù)的是最后進(jìn)行的工作，直到達(dá)到希望退回的狀態(tài)為止。當(dāng)然這種情況下如果棧中已存滿了元素，我們需要在棧的另一端打開(kāi)取出一些元素加以放棄，以騰出一些?？臻g，這是一種特殊的取出操作。清楚了棧的基本工作原理，還需要定義棧的基本數(shù)據(jù)操作，這樣就便于我們確定棧的基本函數(shù)。在棧上定義的基本運(yùn)算一般有：l 在內(nèi)存空間建立一個(gè)棧；l 檢查棧中剩余的容量；l 從棧的頂端推入一個(gè)元素；l 從棧的頂端取出一個(gè)元素；l 刪除一個(gè)棧。除了這些基本運(yùn)算之外，我們往往需要定義一些輔助運(yùn)算，以幫助完成一些復(fù)雜的操作：l 查看棧中最上面一個(gè)元素的內(nèi)容（并不從棧中取出）；l 從

4、棧的底端刪除一個(gè)元素。隊(duì)列圖2-3隊(duì)列結(jié)構(gòu)示意隊(duì)列的工作方式與棧不同，它像一個(gè)兩端打開(kāi)的乒乓球筒（參見(jiàn)圖23），所有的乒乓球只能從指定的一端放入，而拿出乒乓球則必須在另一端進(jìn)行，具有先進(jìn)先出的特性。利用這種特性，我們可以建立一些特殊的數(shù)據(jù)模型來(lái)描述程序所要實(shí)現(xiàn)的解決某些問(wèn)題的過(guò)程。例如，當(dāng)我們采用仿真方法分析一系列交叉口所發(fā)生的交通狀態(tài)時(shí)，需要采用分時(shí)處理技術(shù)分別逐個(gè)改變每一個(gè)交叉口的狀態(tài)，同時(shí)系統(tǒng)整體環(huán)境也在發(fā)生著一些具有時(shí)間先后次序的情況。這時(shí)，我們可以采用如圖24所示的結(jié)構(gòu)建立計(jì)算機(jī)處理模型。在該模型中，具有兩個(gè)層次的隊(duì)列（我們可以把它們看作是一種信息管道），在上面的層次（稱之為環(huán)境層次

5、）上，系統(tǒng)環(huán)境隊(duì)列描述存儲(chǔ)環(huán)境情況的變化事件；在下面層次（稱之為交叉口層次）中，每一個(gè)交叉口對(duì)應(yīng)于一個(gè)信息隊(duì)列，其中的元素代表外界的一個(gè)影響事件。環(huán)境層次與交叉口層次之間的控制機(jī)構(gòu)判定某種環(huán)境變化事件將對(duì)哪些交叉口產(chǎn)生影響，從而將影響事件元素送入相應(yīng)的交叉口信息管道之中。計(jì)算過(guò)程中，計(jì)算機(jī)將逐個(gè)掃描各交叉口并根據(jù)從相應(yīng)信息隊(duì)列中取出的情況進(jìn)行必要的處理。系統(tǒng)環(huán)境信息管道 控制結(jié)構(gòu)交叉口信息管道交叉口4交叉口3交叉口2交叉口1交叉口5圖24 交叉口仿真系統(tǒng)控制機(jī)構(gòu)為具體說(shuō)明隊(duì)列的實(shí)現(xiàn)方法，在此列舉一個(gè)程序示例，這是采用C語(yǔ)言編寫(xiě)的程序，如果采用C+可以編寫(xiě)的更加合理，但我們的目的是說(shuō)明具體算法，

6、采用C語(yǔ)言程序?qū)⒂兄诟嗟淖x者理解。在這一程序中，采用一個(gè)隊(duì)列信息描述頭部記錄有關(guān)的信息，其中包括指向指向記錄隊(duì)列內(nèi)容內(nèi)存塊起始位置的指針start，指示當(dāng)前隊(duì)列頭部（出口）位置的參數(shù)head，指示當(dāng)前隊(duì)列尾部位置的參數(shù)tail，記錄隊(duì)列容量的參數(shù)size，記錄隊(duì)列每個(gè)元素占用內(nèi)存大小的參數(shù)objsize，記錄隊(duì)列中已有元素個(gè)數(shù)的參數(shù)nob。隊(duì)列中元素存儲(chǔ)在建立隊(duì)列時(shí)所申請(qǐng)的內(nèi)存空間，在這一內(nèi)存空間上，利用head、tail兩個(gè)位置參數(shù)構(gòu)成了一個(gè)環(huán)形內(nèi)存空間（參見(jiàn)圖25）。建議讀者閱讀一下程序清單中EnterQueue()和GetElementQueue()兩個(gè)函數(shù)。物理存儲(chǔ)終點(diǎn)物理存儲(chǔ)起點(diǎn)

7、隊(duì)列頭（出口）位置隊(duì)列尾（入口）位置圖25環(huán)形存儲(chǔ)空間隊(duì)列結(jié)構(gòu)示意【清單21】通用型隊(duì)列模塊的Include文件/*-* *-*/#defineQUEUE_NAME_LEN32typedef struct char *start;inthead;inttail;intsize;intnobj;intobjsize;charname QUEUE_NAME_LEN + 1 ; QUEUE;/*基本功能服務(wù)函數(shù)*/QUEUE * MakeQueue( int qsize, int objsize );/*建立隊(duì)列并返回其指針，qsize為隊(duì)列元素個(gè)數(shù)，objsize為單個(gè)元素占用的字節(jié)數(shù)*/intD

8、elQueue( QUEUE *qp );/*刪除整個(gè)隊(duì)列，其中qp為需要?jiǎng)h除的隊(duì)列指針*/intEnterQueue( char * obj, QUEUE * qp ); /*在隊(duì)列中加入一新元素，obj為元素指針，qp為隊(duì)列指針*/intGetElementQueue( char * obj, QUEUE * qp );/*從隊(duì)列中取出一個(gè)新元素*/intSpAvailQueue( QUEUE *qp );/*獲取隊(duì)列中剩余的元素容量*/*擴(kuò)展功能服務(wù)函數(shù)*/intSpUsedQueue( QUEUE * qp );/*獲取對(duì)列中已使用掉的元素容量*/char * ShowNextQueu

9、e( QUEUE * qp );/*顯示隊(duì)列中下一個(gè)預(yù)備出列元素的內(nèi)容*/intEnterHeadQueue( char * obj, QUEUE * qp );/*從隊(duì)列的出口端壓入一個(gè)元素*/intDeleteTailQueue( char * obj, QUEUE * qp );/*從隊(duì)列的入口刪除一個(gè)元素*/【清單22】通用型隊(duì)列模塊的源程序/*-* *-*/#include #include #include queue.hQUEUE * MakeQueue( int qsize, int objsize )QUEUE * qp;if( !( qp = ( QUEUE * )mall

10、oc( sizeof( QUEUE ) + qsize * objsize ) )return( NULL );qp-start = ( char * )( qp + 1 );qp-size = qsize;qp-objsize = objsize;qp-head = 0;qp-tail = 0;qp-nobj = 0;return( qp );intDelQueue( QUEUE *qp )if( qp-nobj )return( 0 );free( qp );return( 1 );intEnterQueue( char * obj, QUEUE * qp )int i;char * bp

11、;if( qp-nobj = qp-size )return( 0 );qp-nobj +;bp = qp-start + ( qp-objsize * qp-tail );for( i = qp-objsize; - i = 0; *bp+ = *obj + );if( + qp-tail = qp-size )qp-tail = 0;return( 1 );intDeleteTailQueue( char * obj, QUEUE * qp )inti;char* bp;if( qp-nobj nobj -;if( - qp-tail tail = qp-size - 1;bp = qp-

12、start + ( qp-objsize * qp-tail );for( i = qp-objsize; - i = 0; *obj+ = *bp + );return( 1 );intEnterHeadQueue( char * obj, QUEUE * qp )short i;char * bp;if( qp-nobj = qp-size )return( 0 );qp-nobj +;if( - qp-head head = qp-size - 1;bp = qp-start + ( qp-objsize * qp-head );for( i = qp-objsize; - i = 0;

13、 *bp+ = *obj + );return( 1 );intGetElementQueue( char * obj, QUEUE * qp )short i;char *bp;if( qp-nobj nobj -;bp = qp-start + ( qp-objsize * qp-head );for( i = qp-objsize; -i = 0; *obj + = *bp + );if( + qp-head = qp-size )qp-head = 0;return( 1 );char * ShowNextQueue( QUEUE * qp )return( qp-start + (

14、qp-head * qp-objsize ) );intSpUsedQueue( QUEUE * qp )return ( qp-nobj );shortSpAvailQueue( QUEUE *qp )return( qp-size - qp-nobj );鏈表鏈表提供了一種動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)非常便于處理如下的問(wèn)題：一組邏輯上成線性結(jié)構(gòu)的元素組，在程序運(yùn)行的過(guò)程需要不斷進(jìn)行元素的刪除或插入工作。例如，道路路線CAD系統(tǒng)中橫斷面設(shè)計(jì)程序中遇到的一個(gè)問(wèn)題是，如果考慮平面線形的修改，將會(huì)造成某一段路線橫斷面數(shù)量的增減變化，如采用連續(xù)方式存儲(chǔ)橫斷面數(shù)據(jù)（例如采用數(shù)組），則每次變化都需要大量

15、移動(dòng)數(shù)據(jù)才能完成，這時(shí)我們需要一種在邏輯上是線性連續(xù)，但在物理上卻允許是非線性的方法，以避免由于個(gè)別元素的增減造成大量數(shù)據(jù)移動(dòng)的情況。最簡(jiǎn)單的鏈接表是單向鏈表，它的每一個(gè)元素都有一個(gè)指向其后面元素位置的指針，其結(jié)構(gòu)如圖26(a)所示。在這一結(jié)構(gòu)中，如果需要?jiǎng)h除一個(gè)元素，只要將它前面元素的指針修改，直接指向被刪除元素后面的元素既可。而插入一個(gè)元素亦可通過(guò)插入位置前后元素的指針修改來(lái)實(shí)現(xiàn)。 數(shù)據(jù) 指針數(shù)據(jù) 指針數(shù)據(jù) 指針(a)單向鏈表結(jié)構(gòu)示意數(shù)據(jù) 指針數(shù)據(jù) 指針數(shù)據(jù) 指針(b)單向鏈表刪除元素?cái)?shù)據(jù) 指針數(shù)據(jù) 指針數(shù)據(jù) 指針數(shù)據(jù) 指針(c)單向鏈表增添元素圖26單向鏈表結(jié)構(gòu)及操作示意圖2.1.4 B

16、樹(shù)對(duì)于一維升序或降序數(shù)據(jù)序列（假設(shè)其個(gè)數(shù)為N）來(lái)說(shuō)，可以采用兩分檢索的方法來(lái)迅速地找到需要插入或刪除元素的位置。但是當(dāng)采用順序存儲(chǔ)的方式時(shí)，為插入一個(gè)元素，需要將其以下的數(shù)據(jù)均進(jìn)行后移；為刪除一個(gè)元素，需要將以下的數(shù)據(jù)進(jìn)行前移。為避免大量的數(shù)據(jù)移動(dòng)，提高插入和刪除的工作效率，研究者提出了多種解決方法，B樹(shù)就是其中較好的一種方案。B樹(shù)是由一系列節(jié)點(diǎn)（有的資料中稱之為頁(yè)）所構(gòu)成，它的每一個(gè)節(jié)點(diǎn)均由2m個(gè)數(shù)據(jù)域和2m+1個(gè)指針域所構(gòu)成，每個(gè)節(jié)點(diǎn)的數(shù)據(jù)從左向右成升序排列。一般情況下，B樹(shù)的每個(gè)節(jié)點(diǎn)中的數(shù)據(jù)域不一定存放滿數(shù)據(jù)，但基本上每個(gè)節(jié)點(diǎn)存放的數(shù)據(jù)數(shù)大于m個(gè)。圖22顯示了一棵m=2的B樹(shù)結(jié)構(gòu)。 0.

17、25 0.40 0.72 A 0.27 0.31 0.12 0.15 0.20 0.22 0.75 0.80 0.95 0.51 0.60 EBDC圖27 B樹(shù)示例B樹(shù)中父節(jié)點(diǎn)與子節(jié)點(diǎn)中的數(shù)據(jù)之間具有如下關(guān)系：父節(jié)點(diǎn)中每一數(shù)據(jù)域中存放的數(shù)據(jù)，均大于該數(shù)據(jù)域左側(cè)指針指向的子節(jié)點(diǎn)中的所有數(shù)據(jù)，也小于該數(shù)據(jù)域右側(cè)指針指向子節(jié)點(diǎn)中的所有數(shù)據(jù)。以圖22所示的B樹(shù)來(lái)看，節(jié)點(diǎn)A中的數(shù)據(jù)，其左側(cè)的指針指向節(jié)點(diǎn)B，B中的數(shù)據(jù)均小于，其右側(cè)的指針指向C，C中的數(shù)據(jù)也均大于。為建立一棵B樹(shù)，需要將一個(gè)一個(gè)的數(shù)據(jù)插入其中。在此，我們討論有關(guān)在B樹(shù)中插入數(shù)據(jù)的問(wèn)題。當(dāng)需要在上面所示的B樹(shù)中插入一個(gè)數(shù)據(jù)，例如是，首先需要

18、查詢其應(yīng)插入的位置。首先將根節(jié)點(diǎn)的數(shù)據(jù)與帶插入數(shù)據(jù)向比較，其結(jié)果發(fā)現(xiàn)應(yīng)插入在與之間。而后，根據(jù)這兩個(gè)數(shù)據(jù)之間的指針?biāo)档奈恢茫榈剿赶虻淖庸?jié)點(diǎn)D。比較之后確認(rèn)應(yīng)插入在數(shù)據(jù)之后，當(dāng)檢查右側(cè)的指針后發(fā)現(xiàn)該指針為空，由此確認(rèn)應(yīng)插入在節(jié)點(diǎn)D中數(shù)據(jù)之右側(cè)，恰巧在這個(gè)位置是空的，因此插入數(shù)據(jù)后即完成了所需的插入工作。這是存在的另一種可能性，是在右側(cè)有另外的數(shù)據(jù)，但節(jié)點(diǎn)D中還有空間允許填入新的數(shù)據(jù)，這是需要將后面的數(shù)據(jù)進(jìn)行右移，空出位置來(lái)插入這一數(shù)據(jù)。當(dāng)查詢到插入位置，卻發(fā)現(xiàn)該節(jié)點(diǎn)已填滿數(shù)據(jù)時(shí)，我們需要進(jìn)行節(jié)點(diǎn)的分割。仍以上述B樹(shù)為例，設(shè)需要插入的數(shù)據(jù)是。采用相同的方法，確認(rèn)需要插入的位置在節(jié)點(diǎn)B的數(shù)據(jù)的

19、左側(cè)，但由于節(jié)點(diǎn)B已填入了四個(gè)數(shù)據(jù)，必須建立新的節(jié)點(diǎn)存放數(shù)據(jù)。為此，我們將原節(jié)點(diǎn)中存放的數(shù)據(jù)和待插入的數(shù)據(jù)一起，找尋其中間數(shù)據(jù)，根據(jù)中間數(shù)據(jù)將這2m+1個(gè)數(shù)據(jù)分為兩部分：小于中間數(shù)據(jù)的m個(gè)數(shù)據(jù)存入新的節(jié)點(diǎn)B1，大于中間數(shù)據(jù)的m個(gè)數(shù)據(jù)存入節(jié)點(diǎn)B2中，將中間數(shù)據(jù)存入節(jié)點(diǎn)B的父節(jié)點(diǎn)A中，同時(shí)對(duì)中間數(shù)據(jù)兩側(cè)的指針加以處理，使其指向節(jié)點(diǎn)B1和B2。當(dāng)出現(xiàn)父節(jié)點(diǎn)同樣數(shù)據(jù)存滿的情況時(shí)，采用類似的方法將父節(jié)點(diǎn)進(jìn)行相應(yīng)的分割。對(duì)于上述插入結(jié)果，可以參見(jiàn)圖23所示的情況。 0.15 0.25 0.40 0.72 A 0.10 0.12 B1 0.20 0.22 B2圖28 在B樹(shù)中插入新的數(shù)據(jù)示例不斷插入新的數(shù)據(jù)

20、，我們能夠建立完整的B樹(shù)。對(duì)于B樹(shù)來(lái)說(shuō)，其深度不會(huì)超過(guò)logmN，在查找的過(guò)程中最不利的情況下其數(shù)據(jù)比較運(yùn)算的次數(shù)不會(huì)超過(guò)m logmN次。2.1.5 位圖如果我們面臨這樣一個(gè)問(wèn)題：需要建立一個(gè)集合，集合中可能的成員包括26各英文字母。這時(shí)采用位圖描述集合是一個(gè)非常有效的方法：該位圖中包括26個(gè)bit，每一個(gè)與一個(gè)字母相對(duì)應(yīng)，檢查某一字母是否在集合之中，只要查看對(duì)應(yīng)該字母的位是0還是1即可。位圖的邏輯結(jié)構(gòu)非常簡(jiǎn)單，為線性連續(xù)空間，在此主要結(jié)合程序編制介紹其實(shí)現(xiàn)方法。在本書(shū)的后面，我們還可以看到將位圖應(yīng)用到大型二值矩陣中的做法（在第章等高線圖繪制中）。位圖模塊程序是道路交通基本函數(shù)庫(kù)中的一部分，

21、其任務(wù)是為位圖操作提供基本支持。實(shí)際上該函數(shù)庫(kù)已是較老的版本，現(xiàn)在使用的是C+類庫(kù)的版本，為了讓讀者易于理解采用技術(shù)難度小一些的方式介紹，目前我們的重點(diǎn)并不在程序結(jié)構(gòu)而在于實(shí)現(xiàn)方法。【清單23】位圖模塊的Include文件/*-* *-*/typedef charBITMAP;BITMAP *MakeBitmap( unsigned size );/根據(jù)給定的長(zhǎng)度size建立一個(gè)位圖。intSetBit( unsigned c, char * map, unsigned val );/設(shè)置第c個(gè)bit的數(shù)值。intTestBit( unsigned c, char * map );/獲取第c個(gè)bit的數(shù)值。該程序是一個(gè)采用C語(yǔ)言編寫(xiě)的程序，三個(gè)對(duì)外服務(wù)函數(shù)的功能如上所述，具體程序結(jié)構(gòu)如清單24所示?！厩鍐?4】位圖模塊源程序清單/*-* *-*/#define DEBUG#include#include#includebitmap.hBITMAP *MakeBitmap( unsigned size )unsigned*map, numbyte;numbyte = ( size 3 ) + ( ( size * 0x07) ? 1 : 0 );if( map = ( unsigned * )malloc(