第2章支撐技術

CHAPTER2 （第三章）BasicDevelopmentofSoftwareforCAD/CAMCAD/CAM支撐技術

簡述

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

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

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

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

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

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

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

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

軟件開發(fā)各階段

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

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

1．軟件工程規(guī)范國家標準

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

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

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

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

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

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

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

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

2．快速原型及螺旋型

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

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

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

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

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

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

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

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

(2)屬性實體的特性。

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

(4)域屬件值的變化范圍。

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

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

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

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

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

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

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

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

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

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

這種結構的數(shù)據(jù)間邏輯關系比較復雜。這種數(shù)據(jù)元素之間的關系是一種多元關系。數(shù)據(jù)的物理結構

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

。鏈接存貯結構

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

鏈接存貯結構的類型

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

1)

單向鏈結構

2)雙向鏈結構

3）多向鏈結構

3.2.3常見的數(shù)據(jù)結構

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

2．棧與隊列（1）棧

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

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

棧與隊列棧與隊列

(2)隊列

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

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

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

常見的數(shù)據(jù)結構——樹

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

樹的表示

樹的存貯方式樹的單向鏈存儲結構

1)單向鏈結構

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

2）多向鏈結構

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

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

（2）二叉樹

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

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

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

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

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

二叉樹的基本形態(tài)二叉樹的存儲結構

2)物理結構

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

遍歷二叉樹

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

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

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

c．后序遍歷

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

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

(2)網(wǎng)

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

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

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

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

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

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

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

1.

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

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

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

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

1．

屏幕直觀輸出法

2．

數(shù)組存貯法

3．

公式計算法

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

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

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

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