第2章支撐技術(shù)

CHAPTER2 （第三章）BasicDevelopmentofSoftwareforCAD/CAMCAD/CAM支撐技術(shù)

簡述

本章從軟件開發(fā)的演化過程入手，引出軟件工程的思想和方法以及軟件開發(fā)的一般步驟，介紹了軟件開發(fā)的技術(shù)基礎(chǔ)——數(shù)據(jù)結(jié)構(gòu),并就CAD/CAM集成的關(guān)鍵——數(shù)據(jù)庫技術(shù)進行闡述。

3.1軟件開發(fā)與軟件工程3.1.1軟件開發(fā)的演化過程個人編程時代（46年~50年代末）軟件開發(fā)是科學(xué)家們根據(jù)各自的應(yīng)用需要寫出的能夠解決預(yù)定問題的運行程序。程序生產(chǎn)的效率極低，可靠性難以保證，且僅限于處理比較簡單的數(shù)值計算問題。

軟件開發(fā)的演化過程

軟件作坊時代(60年代初一60年代未)

軟件作坊的開發(fā)方法是個體的或小組的思維行為，使得軟件任務(wù)延誤、質(zhì)量不可靠、甚至無法維護，極大地制約了計算機以后)的功能發(fā)揮和實際應(yīng)用。軟件工程時代(70年代在世界范圍內(nèi)出現(xiàn)了許多組織嚴(yán)密、管理科學(xué)、手段先進、工具齊全的軟件開發(fā)公司，為計算機軟件市場提供了大量成功的軟件產(chǎn)品。80年代，明確提出了“軟件工程支撐環(huán)境”的思想，使程序設(shè)計可以直接從支撐環(huán)境中調(diào)用所需的各個“組件”。3.1.2軟件工程

軟件工程的概念要解決軟件危機需要借鑒從事工程項目所積累的原理、概念、技術(shù)和方法來開發(fā)和維護軟件，把正確的管理和科學(xué)的技術(shù)結(jié)合起來，這就是軟件工程。軟件的生存周期軟件產(chǎn)品從形成概念開始，經(jīng)過開發(fā)、使用和不斷增補修正，直到最后被淘汰的整個過程。按照軟件工程的思想，這個過程又可劃分成若干個互相區(qū)別而又有聯(lián)系的階段。軟件的生存周期的六個階段

（1）可行性研究與計劃階段明確“要做什么”及“是否能做”（2）需求分析階段弄清“必須做什么”（3）設(shè)計階段“如何做”和“如何具體做”（4）實現(xiàn)階段源程序的編碼、編譯及程序單元測試。（5）測試階段總裝測試和確認(rèn)測試（6）運行與維護階段

根據(jù)新提出需求，擴充和修改軟件

軟件開發(fā)各階段

軟件的四類維護活動（1）改正性維護診斷和改正運行中發(fā)現(xiàn)的軟件錯誤（2）適應(yīng)性維護修改軟件以適應(yīng)環(huán)境的變化（3）完善性維護根據(jù)用戶的要求改進或擴充軟件（4）預(yù)防性維護

修改軟件為將來的維護活動做預(yù)備。3.1.3軟件工程規(guī)范

1．軟件工程規(guī)范國家標(biāo)準(zhǔn)

(1)《計算機軟件開發(fā)現(xiàn)范》(2)《計算機軟件產(chǎn)品開發(fā)文件編制指市》

(3)《計算機軟件需求說明編制指南》

(4)《計算機軟件測試文件編制規(guī)范》(5)《計算機軟件質(zhì)量保證計劃規(guī)范》(6)《計算機軟件配置管理計劃規(guī)范》

(7)《軟件工程術(shù)語》2．軟件文檔

文檔是軟件開發(fā)階段之間、程序員之間通訊的工具。按照《計算機軟件產(chǎn)品開發(fā)文件編制指南》(GB8567—88)規(guī)定，整個軟件生存周期共應(yīng)提交十四種標(biāo)準(zhǔn)文檔。3.1.4軟件開發(fā)方法軟件作為—種產(chǎn)品應(yīng)當(dāng)滿足以下基本要求(1)正確性滿足用戶提出的應(yīng)用需求，實現(xiàn)規(guī)劃的全部功能。(2)可靠性出錯概率小于預(yù)定指標(biāo)，運行正常，容錯性好。(3)完整性提供完整的有效運行程序和文檔資料以及必要的培訓(xùn)服務(wù)。(4)實用性具有良好的人機界面，操作簡便，有適用范圍，能解決實際問題。(5)可維護性

便于糾正軟件錯誤，擴充系統(tǒng)功能，實現(xiàn)各類維護活動。軟件開發(fā)方法的三種類型

軟件開發(fā)方法主要有三種類型：瀑布型快速原型及螺旋型平行進程型1.瀑布型

一種按軟件生存階段而順序工作的、單向、單鏈的開發(fā)方法。

2．快速原型及螺旋型

盡快向用戶提供原型系統(tǒng)，讓用戶試用，得到反饋信息，再按實用性、經(jīng)濟性、可靠性要求進一步修改設(shè)計，解決原型系統(tǒng)暴露出來的問題，從而開發(fā)出產(chǎn)品。3．平行進程型

該方法認(rèn)為軟件開發(fā)是三個進程組相立平行、相輔相成、齊頭并進的團隊行為。3.2數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)實際上是對客觀對象、現(xiàn)實世界的性質(zhì)和關(guān)系的一種描述。一個機械產(chǎn)品的數(shù)據(jù)，包括性能參數(shù)、結(jié)構(gòu)尺寸、工藝過程、圖樣信息等．它們代表著該產(chǎn)品的性質(zhì)及它與環(huán)境之間的關(guān)系。在CAD/CAM中，一個孤立出來的具體數(shù)據(jù)往往沒有實際意義，而各種相關(guān)數(shù)據(jù)的集合就能描繪任一復(fù)雜事物，數(shù)據(jù)之間的關(guān)系有豐富的涵義。因此，對于數(shù)據(jù)的研究與管理不單純限于數(shù)據(jù)本身，更重要的在于數(shù)據(jù)之間的關(guān)系，也就是結(jié)構(gòu)問題。3.2.1基本概念與術(shù)語

從事物的物理狀態(tài)到表示信息的數(shù)據(jù)，實際上經(jīng)歷了三個不同的領(lǐng)域：

現(xiàn)實世界——是存在于人們頭腦之外的客觀世界。信息世界——現(xiàn)實世界在人們頭腦中的反映，是人們頭腦中的觀念世界。數(shù)據(jù)世界——是觀念世界中信息的數(shù)據(jù)化，它是計算機處理的對象。

在數(shù)據(jù)處理中，首先應(yīng)將現(xiàn)實世界轉(zhuǎn)換為信息世界，然后再將信息世界轉(zhuǎn)換為數(shù)據(jù)世界?；靖拍钆c術(shù)語

其中包含幾個層次的概念：

(1)實體客觀世界存在并可相互區(qū)別的事物。

(2)屬性實體的特性。

(3)屬性值每個屬性所能測量或記錄的值。若干屬性的屬性值組成的集合即可表征一個實體。

(4)域?qū)偌档淖兓秶?/p>

(5)數(shù)據(jù)

描述文體的數(shù)值、字符及其它等各種物理符號。數(shù)據(jù)按其組成內(nèi)容又可分為若干個層次級

數(shù)據(jù)1)字符

是數(shù)據(jù)的最小單位。2)數(shù)據(jù)項

是數(shù)據(jù)中最基本的、不可分的并有命名的數(shù)據(jù)單位。3)組合項

由若干個數(shù)據(jù)項組成。4)記錄

相關(guān)組合項或數(shù)據(jù)項的集合構(gòu)成一個記錄，是描述某個實體屬性值的集合。5)文件

相同性質(zhì)的記錄的集合就是文件。6)數(shù)據(jù)庫非單純性、有結(jié)構(gòu)文件的集合。3.2.2數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系。數(shù)據(jù)元素不是孤立的，而是彼此相互關(guān)聯(lián)的。數(shù)據(jù)結(jié)構(gòu)理論研究數(shù)據(jù)元素之間的抽象化的關(guān)系，并不涉及數(shù)據(jù)元素的具體內(nèi)容。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)

1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)描述的是數(shù)據(jù)之間的邏輯關(guān)系，它從客觀的角度組織和表達(dá)數(shù)據(jù)通?？蓪⑦壿嫿Y(jié)構(gòu)歸納為兩大類型。（1）線形結(jié)構(gòu)這種結(jié)構(gòu)的數(shù)據(jù)可以用數(shù)表的形式表示。在這種結(jié)構(gòu)中，每一個數(shù)據(jù)元素僅與它前面的一個和后面的一個數(shù)據(jù)元素相聯(lián)系，因而僅能用于表達(dá)數(shù)據(jù)之間的簡單順序關(guān)系。（2）非線性結(jié)構(gòu)

這種結(jié)構(gòu)的數(shù)據(jù)間邏輯關(guān)系比較復(fù)雜。這種數(shù)據(jù)元素之間的關(guān)系是一種多元關(guān)系。數(shù)據(jù)的物理結(jié)構(gòu)

2．?dāng)?shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)指的是數(shù)據(jù)在計算機內(nèi)部的存貯方式，它從物理存貯的角度來描述數(shù)據(jù)，以及數(shù)據(jù)間的關(guān)系。常用的物理結(jié)構(gòu)有順序存貯結(jié)構(gòu)與鏈接存貯結(jié)構(gòu)兩種。順序存貯結(jié)構(gòu)的存貯方式占用存貯單元少，簡單易行，結(jié)構(gòu)緊湊。但數(shù)據(jù)結(jié)構(gòu)缺乏柔性，若要增刪數(shù)據(jù)，必須重新分配存貯單元，重新存入全部數(shù)據(jù)。鏈接存貯結(jié)構(gòu)可獨立于邏輯結(jié)構(gòu)，它使存貯的物理順序不必與邏輯順序一致而仍能按邏輯要求來存取數(shù)據(jù)。順序存貯結(jié)構(gòu)（1）順序存貯結(jié)構(gòu)：用一組連續(xù)的存儲單元依次存放各種數(shù)據(jù)元素

。鏈接存貯結(jié)構(gòu)

(2)鏈接存貯結(jié)構(gòu)把數(shù)據(jù)的地址分散存放在其它有關(guān)的數(shù)據(jù)中，并按照存取路徑進行鏈接。這樣，在求得初始數(shù)據(jù)的地址后，檢索出該地址存放的數(shù)據(jù)和下一個數(shù)據(jù)的地址，可逐次找到各個所需的數(shù)據(jù)。數(shù)據(jù)中存入的下一個數(shù)據(jù)的地址稱為指針。通過各種指針，可構(gòu)成不同的存取路徑，以適應(yīng)邏輯結(jié)構(gòu)的需要。一個數(shù)據(jù)元素項由信息字段(INFO)和指針宇段(P()INT)組成。

鏈接存貯結(jié)構(gòu)的類型

鏈接存貯結(jié)構(gòu)根據(jù)指針的數(shù)目有三種類型

1)

單向鏈結(jié)構(gòu)

2)雙向鏈結(jié)構(gòu)

3）多向鏈結(jié)構(gòu)

3.2.3常見的數(shù)據(jù)結(jié)構(gòu)

1．線性表這是—種最簡單、最常見的數(shù)據(jù)結(jié)構(gòu)，其特點就是數(shù)據(jù)元素之間呈線性關(guān)系，線性表的物理結(jié)構(gòu)既可以采用順序存貯結(jié)構(gòu)，也可以采用鏈接存貯結(jié)構(gòu)。線性表邏輯上可以表示為：常見的數(shù)據(jù)結(jié)構(gòu)——棧與隊列

2．棧與隊列（1）棧

棧是一種特殊的線性表，它的插入和刪除操作只能在表的一端進行。在棧中允許插入和刪除的一端稱為棧頂，而不允許插入和刪除的另一端稱為棧底。順序存貯和鏈接存貯都可以作為棧的存貯結(jié)構(gòu)。只是采用順序存儲時要外加一個棧頂指示器。

在程序設(shè)計中，棧是一種非常有用的數(shù)據(jù)結(jié)構(gòu)。子程序的調(diào)用和返回處理大多是用棧來實現(xiàn)的：遞推算法也可以用棧結(jié)構(gòu)來實現(xiàn)。

棧與隊列棧與隊列

(2)隊列

隊列也是一種特殊的線性表，它限定只能在表的一端插入，在表的另一端刪除。允許插入的一端叫隊尾，允許刪除的一端叫隊頭。隊列的物理結(jié)構(gòu)可采用順序存貯和鏈接存貯結(jié)構(gòu)。常見的數(shù)據(jù)結(jié)構(gòu)——數(shù)組、串

3．?dāng)?shù)組數(shù)組是線性表的推廣，是一組按一定順序排列的具有相同類型的數(shù)據(jù)。一維數(shù)組的邏輯結(jié)構(gòu)實際上就是一個簡單的線性表。至于二維數(shù)組，可將一行(或一列)數(shù)據(jù)元素看成一個數(shù)組元素，這個數(shù)組元素本身也是一個一維數(shù)組，即也相當(dāng)于一個線性表。n維數(shù)組可以類推。數(shù)組與線性表的存貯方式相同，用順序存貯結(jié)構(gòu)存放無論一維數(shù)組還是二維數(shù)組或更高維數(shù)組在存貯器中部是按一維排列存貯的，只是按照一定的存貯順序。

4．串串是一種字符型的線性表，串可用一個字符型數(shù)組來順序存貯，也可用鏈接存貯。

常見的數(shù)據(jù)結(jié)構(gòu)——樹

5.樹與二叉樹（1）樹樹的每一個結(jié)點可能有無數(shù)個后繼，但只有一個前驅(qū)，并且最高層結(jié)點沒有前驅(qū)，樹結(jié)構(gòu)表示了元素間的層次關(guān)系。樹中只有一個沒有前驅(qū)的結(jié)點稱為樹根，其它結(jié)點僅有一個直接前驅(qū)結(jié)點，樹中結(jié)點的最大層次稱為樹的深度；結(jié)點的子樹的個數(shù)稱為度；度數(shù)是0的結(jié)點稱為樹葉。樹的物理結(jié)構(gòu)可有多種形式。各數(shù)據(jù)元素既可以連續(xù)存貯在一起，也可以分散存貯，通過指針來建立元素間的聯(lián)系和存取路徑。

樹的表示

樹的存貯方式樹的單向鏈存儲結(jié)構(gòu)

1)單向鏈結(jié)構(gòu)

存貯結(jié)構(gòu)與邏輯結(jié)構(gòu)不—致，每一個元素只用一個指針，存取路徑和時間較長。樹的多向鏈存儲結(jié)構(gòu)

2）多向鏈結(jié)構(gòu)

存貯結(jié)構(gòu)與邏輯結(jié)構(gòu)—致，各層數(shù)據(jù)元素分別按順序連續(xù)存貯在三塊中，層次之間的邏輯關(guān)系用指針實現(xiàn)。樹的環(huán)鏈存儲結(jié)構(gòu)

3）環(huán)鏈結(jié)構(gòu)分別建立上下層之間、同層各元素之間的環(huán)鏈連接，可通過左右不同的指針來達(dá)到不同的存取要求或不同的數(shù)據(jù)組合。左指針構(gòu)造上下層次間的環(huán)鏈，右指針構(gòu)造每一個子樹的同層各元素間的環(huán)鏈。二叉樹

（2）二叉樹

1)特點與形態(tài)二叉樹是樹結(jié)構(gòu)中的一種重要類型。二叉樹與樹的區(qū)別：

a．二叉樹可以是空的，樹則必須至少有一個根結(jié)點。

b．二叉樹的度數(shù)不能超過2，樹則無此限制。

c．二叉樹的子樹有左、右之分．不能顛倒，樹的子樹則可以交換位置。

二叉樹的基本形態(tài)

二叉樹的基本形態(tài)二叉樹的存儲結(jié)構(gòu)

2)物理結(jié)構(gòu)

通常采用鏈接結(jié)構(gòu)．每個結(jié)點設(shè)兩個指針，左指針指向左子樹的地址；右指針指向右子樹的地址。這種結(jié)構(gòu)與邏輯結(jié)構(gòu)一致，描述清楚，也便于刪除和運算，但占用存貯單元較多。

遍歷二叉樹

3)遍歷二叉樹即按一定規(guī)律，不重復(fù)地訪問樹中的每一個結(jié)點。這對于在二叉樹中查找某一指定結(jié)點，或逐一對全部結(jié)點進行某種處理，或?qū)⒎蔷€性結(jié)構(gòu)線性化具有重要意義。對于線性結(jié)構(gòu)來說，遍歷并非難事，但對二叉樹來講就需要找到一個完整而有規(guī)則的遍歷方法。常用的遍歷方式有三種：前序遍歷中序遍歷后序遍歷常用的遍歷方式

a．前序遍歷操作過程為：若二叉樹為空，則退出。否則，a)訪問根結(jié)點；b)前序遍歷左子樹；c)前序遍歷右子樹。這是一個從上至下，先左后右的原則。如圖3—22所示二叉樹的前序遍歷為：ABDE—HICFG(見圖3—23a)。

b．中序遍歷操作過程為：若二叉樹為空，則退出。否則，a)中序遍歷左子樹；2b)訪問根結(jié)點；c)中序遍歷右子樹。這是—個從左向上．先上后下的原則。如圖3—22所示二叉樹的中序遍歷為：DBHEIAFCG(見圖3—23b)。

c．后序遍歷

操作過程為：若二叉樹為空．則退出。否則，a)后序遍歷左子樹；b)后序遍歷右子樹；c)訪問根結(jié)點。這是一個從左向右，先下后上的原則。常用的遍歷方式常見的數(shù)據(jù)結(jié)構(gòu)——圖與網(wǎng)

6．圖與網(wǎng)(1)圖圖是比樹更為復(fù)雜的一種非線性結(jié)構(gòu)。在圖結(jié)構(gòu)中，每個結(jié)點可能有多個直接前趨，也可能有多個直接后繼，結(jié)點的聯(lián)系是任意的，因此，它不象樹結(jié)構(gòu)那樣有明顯的層次關(guān)系。網(wǎng)

(2)網(wǎng)

當(dāng)圖的邊具有與它相關(guān)的權(quán)時，這樣的圖稱為網(wǎng)。權(quán)可以代表從一個頂點到另一個頂點的距離、時間、所耗代價等等?？捎绵徑泳仃嚤硎揪W(wǎng)，只要把矩陣中原來為l的元素改為權(quán)值即可。3.2.4文件

文件是數(shù)據(jù)管理的一種形式，它能獨立于應(yīng)用程序單獨存貯。在CAD／CAM系統(tǒng)中，文件常常作為管理數(shù)據(jù)、交換數(shù)據(jù)的方法而被廣泛采用。具體地說，文件是記錄的集合。能夠唯一地標(biāo)識記錄的數(shù)據(jù)項的值稱為關(guān)鍵字。

同一文件的邏輯結(jié)構(gòu)可以有多種物理組織方法，也可對文件進行需要的操作。

1．常用的文件組織方法順序文件、索引文件、直接存取文件、索引鏈接文件、倒排文件、B樹和變長記錄文件等。文件的操作2．文件的操作文件的操作主要表現(xiàn)在兩個方面，—是查找，二是排序。（1）查找即尋找關(guān)鍵字為某值的記錄．常用的查找方法有三種：1)順序查找法；2)折半查找法；3)分塊查找法。（2）排序?qū)ξ募杏涗浀年P(guān)鍵字(或數(shù)組元素值)按遞增或遞減的順序重新排列。常用的排序方法：1)選擇排序、2)

冒泡排序、3)插入排序3.3數(shù)據(jù)資料的程序化處理

在CAD／CAM過程中，常常要參照各種標(biāo)準(zhǔn)和規(guī)范，根據(jù)一系列相關(guān)數(shù)據(jù)資料、圖表、實驗曲線來選用所需的數(shù)據(jù)。這些資料是先期以數(shù)據(jù)庫或文件形式加以管理，以便在設(shè)計時由計算機按要求自動檢索和調(diào)用；或在程序編制過程中融于其中，將其程序化，隨著程序的運行，自然選用，加工處理。這是CAD／CAM軟件開發(fā)的基本工作之一。3.3.1數(shù)值程序化

數(shù)值程序化就是將要使用的各個參數(shù)及其函數(shù)關(guān)系，用一種合理編制的程序存入計算機，以便運行使用。其方法要具體問題具體分析。

1.

用數(shù)組形式存貯數(shù)據(jù)如果要使用的數(shù)據(jù)是一組單一、嚴(yán)格、又無規(guī)律可循的數(shù)列存貯數(shù)據(jù)，可以用訴諸形式存儲數(shù)據(jù)，以便在程序運行時直接檢索使

2.用數(shù)學(xué)公式計算數(shù)據(jù)

如果要使用的數(shù)值是一組單一、嚴(yán)格、但能找到某種規(guī)律的數(shù)列，則不必定義數(shù)組逐項賦值，將反映這種規(guī)律的數(shù)學(xué)公式編入程序，通過計算即可快速、準(zhǔn)確地達(dá)到目的。3.3.2數(shù)表程序化

數(shù)表程序化就是用程序完整、準(zhǔn)確地描述不同函數(shù)關(guān)系的數(shù)表，以便在運行過程中迅速、有效地檢索和使用數(shù)表中的數(shù)據(jù)。歸納起來，一般有下述幾種方法。

1．

屏幕直觀輸出法

2．

數(shù)組存貯法

3．

公式計算法

4．交互式分級描述法3.3.3線圖程序化

線圖程序化的前提就是找出能描述線圖的數(shù)學(xué)公式。由于實際工程問題比較復(fù)雜，往往很難將實驗數(shù)據(jù)用公式進行精確描述，而常常采用某個曲線公式近似地反映它們的關(guān)系，這就是所謂經(jīng)驗公式。建立這種經(jīng)驗公式的過程稱為曲線擬合。常用的方法一般為：最小二乘法。

3.3.4數(shù)據(jù)資料文件化

對于需要頻繁修改、或系統(tǒng)內(nèi)各應(yīng)用程序之間共享