1、一、 CAD/CAM 概論本章主要是講解 CAD/CAM的基本概念、基本功能和工作原理等。CAD/CAM技術是一門多學科綜合性應用技術，是20世紀制造領域最杰出的技術之一。1. 1 CAD/CAM的基本概念CAD(Computer Aided Design):是指工程技術人員以計算機為工具完成產品設計過程中的各項任務，如草圖繪制、零件設計、裝配設計、工裝設計、工程分析等；CAPP(Computer Aided Process Planning):是指工藝人員利用計算機，根據產品制造工藝要求，交互或自動地確定產品加工方法和方案，如加工方法的選擇、 工藝路線和工序的設計等；CAM(Computer

2、 Aided Manufacturing):制造人員借助于計算機完成從生產準備到產品制造出來的過程中各個環節與活動，如數控加工編程、制造過程控制、質量檢測等。1.1.1從產品制造的過程理解 CAD/CAM傳統制造概念與過程如圖1。13利用計算機完成各個環節的工作成為CAD/CAM幾點說明：1、計算機技術只能解決信息的查詢與統計，信息的管理、重復而繁瑣的工作等，而并不能代替人的工作，特別是創造性的工作。2、 現代制造概念很大，本書 CAD/CAM的概念只涉及到產品的設計、工藝設計、加工、車間控制與質量控制等內容。3、上述制造環中有三個流：物流、資金流與信息流。4、企業制造資源有人、財、物、技術與

3、信息。1.1.2 CAD/CAM 的基本功能在CAD/CAM 系統中，人們利用計算機完成產品結構描述、工程信息表達、工程信息的傳輸與轉化、信息管理等工作。因此，CAD/CAM系統應具備以下基本功能：1、產品與過程的建模如何用計算機能夠識別的數據（信息）來表達描述產品。如產品形狀結構的描述、產品加工特性的描述、如何將有限元分析所需要的網格及邊界條件描述出來等等。2、圖形與圖象處理在CAD/CAM 系統中，圖形圖象仍然是產品形狀與結構的主要表達形式，因此，如何在計算機中表達圖形、對圖形進行各種變換、編輯、消隱、光照等處理是CAD/CAM的基本功能。3、信息存儲與管理設計與制造過程會產生大量、種類繁

4、多的數據，如設計分析數據、工藝數據、制造數據、管理數據等。數據類型有圖形圖象、文字數字、聲音、視頻等；有結構化和非結構化的數據；有動態和靜態數據等。怎樣將CAD/CAM 系統產生這些大量的電子信息存儲與管理好，是 CAD/CAM的必備功能。采用工程數據庫。4、工程分析與優化計算體積、重心、轉動慣量等，機構運動計算、動力學計算、數值計算，優化設計等。CAE5、工程信息傳輸與交換信息交換有 CAD/CAM系統與其他系統的信息交換和同一CAD/CAM系統中 不同功能模塊的信息交換。6、模擬與仿真為了檢察產品的性能， 往往需要對產品進行各種試驗與測試，需要專門的設備與生產出樣品，并具有破壞性，時間長，

5、成本大。通過建立產品或系統的數字化模式， 采用計算機模擬技術可以解決這一問題。如加工軌跡仿真，機構運動仿真，工件、刀具 和機床碰撞與干涉檢驗等。7、人機交互數據輸入、路線與方案的選擇等，都需要人與計算機進行對話。人機對話交互的方 式有軟件界面與設備（鍵盤、鼠標等）8信息的輸入與輸出信息的輸入與輸出有人機交互式輸入輸出與自動輸入輸出。CAD/CAM的具體功能見圖1.3 P41.1.3 CAD/CAM系統的組成與工作過程如圖1.4 P51.2 CAD/CAM 技術的發展回顧1.2.1CAD技術的發展1. 形成期1950 MIT CRT（陰極射線管計算機能夠處理圖形宀 計算機圖形學。2. 發展期 5

6、0年代光筆t交互式會圖60年代屏幕菜單點擊、功能鍵盤、光筆定位、圖形動態修改。1962 美國Ivan Sutherland第一個交互式圖形系統(SketchPad) 2D 系統3、成熟期1973 實體造型技術實體造型軟件3D系統4.集成期信息分散、不能共享，不能發揮合力效益，開發專用接口，成本大，自動化程度不高等等 集成CAD/CAM.1.2.2 CAM技術的發展1952年數控機床t 1955自動編程工具（APT ）1958自動換刀系統t加工中心（MC）1962工業機器人t物料搬運自動化，利用一臺計算機控制多臺數控設備t （直接數控系統）DNC t FMS.70年代，交互式圖形編程系統，CAM

7、成熟智能化，集成化，自動化。1.2.3 CAPP技術的發展1969年，挪威，成組技術，零件分類歸族，典型樣件與典型工藝 AutoPros 1980年，英國AutoCAP. 派生式CAPP系統。簡單，實用，成本低， 周期短；但與企業的特性相關度高，一般不適合于其他企業。采用規則，推理，根據工藝的特性，自動生成工藝路線，成為創成式CAPP , 自動化程度高，適合于多種企業。 但由于工藝過程涉及的因素多， 開發周期及 成本高，目前仍然在研究階段。80年代中期，CAPP專家系統。1.2.4 CAD/CAM 的集成技術CAD、CAPP、CAM技術長時間獨立發展，使數據結構、軟件結構、平臺等方面有很大差異

8、。系統之間不能進行自動的數據交換，需要大量的人工參與以完成數據傳輸工作，嚴重阻礙CAD、CAPP、CAM技術的效益與發展。80年代，人們致力于 CAD> CAPP、CAM技術集成研究。相繼推出了 CADAM、 CATIA、UG、Pro/E 等。1.3CAD/CAM技術的應用1.3.1CAD/CAM 的應用現狀機械是主要應用領域2D應用最廣我國在2D CAD系統和CAPP系統中自主產品，市場占有率較高。3D剛起步。1.3.2 CAD/CAM 的應用效益生產精度與產品質量提高產品開發周期縮短GM 汽車 5年t 3年新產品可靠性提咼 20% t 60%生產成本下降波音777未生產樣機詳細效益請

9、見P111.4 CAD/CAM技術的新發展1.4.1制造企業面臨的市場形式產品形式多樣化、個性化，生產方式由大批量、少品種t少批量、多品種；市場響應速度快。大吃小T快吃慢產品的范疇：產品t產品P+質量Q+時間T+服務S (T,Q,C,S)競爭范圍：區域T全球核心競爭力T創新技術與人才各種新技術的出現與應用，特別是計算機與信息技術，In ternet上述原因，企業未來呈現的特點：1、產品開發生產周期短，上市快；2、制造柔性化；3、整個產品生命周期內的質量保證4、企業組織形式，出現虛擬企業與企業聯盟5、生產過程更為精良6、人才素質高7、智能化與自動化程度高8、綠色制造9、分布、并行、集成并存企業未

10、來力呈現的特點對CAD/CAM系統的要求1、集成化，2、智能話，3、網絡化，4、分布并行處理，5、綜合技術的 產品開發，6、虛擬現實技術，7、人機工程。1.4.2CAD/CAM 新方向1、支持 TOP-Down , 2、支持 DFx，3、智能 CAD/CAM，4、CE、5、 虛擬制造，6、集成制造，7、異地設計制造。二、CAD/CAM 系統CAD/CAM 系統的基本組成、結構與分類，軟件、硬件及網絡的基本概念，軟件、 硬件的分類，網絡設備的功能等。重點是應用軟件的基本概念及其分類和網絡與網絡設 備的基本功能。2.1 CAD/CAM系統組成與分類2.1.1 CAD/CAM 系統組成CAD/CAM

11、系統由硬件和軟件系統組成。硬件系統是指可觸摸到的物理設備，如主機設備、終端設備、網絡及通信設備、輸入輸出設 備，數控加工及控制設備等。軟件系統通常是指程序及其相關文檔的總和，軟件系統一般分為系統軟件、支撐軟件和應用軟件。具體見圖 2.1P21.2.1.1 CAD/CAM 系統的分類從不同的角度，CAD/CAM系統可分為不同的類型。從硬件角度，分為兩大類。1、 以大型機或小型計算機為主機的、多用戶分時 系統。其基本結構如 2.2a圖，P22. 主機系統的特點：1）外圍設備和用戶工作站與主機相連，用戶工作站中至少有一臺圖型工作站和一套圖形處理設備（如圖形終端，圖形輸入輸出設備等），圖形工作站基本結

12、構如 2.2b圖，P22.2）優點：主機功能強，可處理大量信息，如分析計算，模擬。使用性能取決于軟件水平。3）缺點：系統專用性強，比較封閉，終端過多，系統速度變慢，價格較高。另外，系統的可靠性取決于主機（主機發生故障，整個系統都將癱瘓）。2、 工程工作站或微機系統的單用戶系統。（）此系統特點:1 ）每一個工程工作站或微機系統都能獨立完成CAD/CAM系統所要求的各項任務。2）價格較低，在中小型企業得到應用3）可靠性高已成為主流按功能劃分，CAD/CAM 系統可分為 CAD、CAM、CAD/CAM。1、CAD系統：專門為設計而建立的系統，可完成各項設計任務，如造型、會圖、工程 分析仿真與模擬，文

13、檔管理等。不具備數控編程、加工仿真、生產控制及管理等。2、CAM系統：具備數控編程、加工仿真、生產控制及管理等功能，幾乎不具備造型、會圖、工程分析仿真與模擬等功能。3、 CAD/CAM系統：具備CAD與CAM的所有功能，并可進行信息的自動交換。已成 為主流。根據是否使用計算機網絡，CAD/CAM系統又可分為單機系統和網絡系統。計算機網絡：通過通信線路連接起來的自治的計算機集合。包括三個含義（1、必須有兩臺或兩臺以上的具有獨立功能的計算機系統相互連接在一起，達到資源共享的目的；2、連接在一起的計算機必須有一條信息交換的通道；3、在同一網絡中的計算機系統之間進行信息交換，必須遵循共同的約定與規則，

14、即協議）1、 單機CAD/CAM 系統：具備所有 CAD/CAM 的軟件與硬件功能。但不能與其他 CAD/CAM進行信息交換。信息不能共享。2、網絡CAD/CAM系統：將具備CAD/CAM的軟件與硬件功能的各個節點用網絡設備和通信線路進行連接就形成了一個網絡化的CAD/CAM系統。可實現資源與信息共享。已成為主流。網絡結構有星型、環型、總線型和網絡等形式。由于總線型具有兼容性強，開放性和可擴展性良好等特性，因此，總線已成為主流。2.2CAD/CAM系統中的典型硬件2.2.1計算機基本系統計算機基本系統由主機（包括CPU、主板和內存）、外存（磁盤、光盤）、顯示器、鍵盤和鼠標等組成。主機：包括 C

15、PU、主板和內存主機的性能主要取決于 CPU性能，CPU由控制器、運算器及各種寄存器組成，其性能由主頻和寄存器的位數決定。內存：內存直接與 CPU相連，并直接進行數據讀取。內存分為只讀存儲器ROM與隨機存取存儲器RAM。8位二進制為一個字節。外存：磁盤、光盤2.2.2輸入設備鍵盤、鼠標、操縱桿；數字化儀（如圖 2.7 P27），數字化一般用于將紙張圖轉化成計算 機圖。圖形板、光筆、觸摸屏、掃描儀、數字化手套、傳感器等。2.2.3輸出設備顯示器、打印機、繪圖儀、生產設備。2.2.4網絡設備服務器（用于提供公共服務的高性能計算機，運行網絡操作系統）、工作站。電纜：同軸電纜（500m）、光纜（100

16、0m）、雙絞線（100m ）。網卡中繼器：用于信號放大，使信息傳輸更遠，不改變信號。網橋：對網絡進行分割，平衡網絡負載。路由器：LAN與WAN的連接設備，將多個獨立網進行連接。實現互聯網之間的最佳 尋徑與數據傳輸。網關：連接不同體系網絡，如不同協議。Novell與Ethernet。2.3 CAD/CAM軟件系統軟件是一種邏輯實體，是程序、數據及相關技術文檔的總和。根據層次劃分，CAD/CAM軟件系統分為系統軟件、支撐軟件和應用軟件。其層次關系 如圖 2.13P35系統軟件：面向計算機及網絡系統的，實現對計算機及網絡的管理，提供用戶操作及管理計算機與網絡的界面。是其他軟件系統的基礎。系統軟件主要

17、包括操作系統、編程語言、 網絡通信及其管理三大部分。1、操作系統操作系統的主要功能是：處理器管理、設備管理、存儲管理、文件管理與用戶接口（界 面）。按功能及其工作方式分，操作系統可分為單用戶、批處理、實時、分時、網絡和分布式 六類。DOS是一個單用戶、 單任務系統，而Unix與Windows是多用戶分時系統。 可由人工干 預，實現交互式操作。實時系統不需要人工干預，處理速度快，可靠性高，能夠對信息處理的過程進行監控。在CAD/CAM 系統中，常用的操作系統有，工作站：Unix、VMS ;微機：Windows、XENIX。2、計算機編程語言計算機語言有機器、匯編(低級語言)及高級語言。機器語言是

18、計算機唯一能夠識別的語言。用匯編和高級語言編寫的程序必須經過轉換成機器語言后才能運行。低級語言依賴計算機硬件程度高，而高級語言幾乎不依賴以計算機硬件。低級語言編寫的程序比高級語言編寫的程序要快。高級語言編寫的程序必須經過編譯和連接后才能執行。常用的高級語言有 VisualC+、Visual Basic、Java (面向對象編程方法)。Lisp,ProLog用于人工智能與專家系統。3、網絡通信及其管理軟件網絡通信及其管理軟件主要包括網絡協議、網絡資源管理、網絡任務管理、網絡安全管理與網絡通信瀏覽工具等功能。在計算機網絡中，不同的計算機系統之間進行信息交換時，必須遵循某種共同的約定與規則，這種約定

19、與規則即為協議。網絡協議是按層次劃分的。按”開放系統網絡標準模式”OSI，網絡協議分為七層，即 應用層、表示層、會話層、傳輸層、網絡層、鏈路層和物理層<CAD/CAM流行的主要網絡協議有：1) MAP(Ma nufacturi ng Automation Protocol)用于工廠自動化2) TOP(Tech ni cality and Office Protocol)用于技術與辦公環境3) TCP/IP( Tran smissio n Co ntrol Protocol / In ternet Protocol) 按報文為傳輸單位。2.3.2機械CAD/CAM支撐軟件支撐軟件不為某一具

20、體應用而設計開發的，只為用戶提供應用工具和開發環境。從功能上劃分，支撐軟件可分為，基本圖形資源與自動繪圖，幾何造型、工程分析與計算、仿真與 模擬、專用設備控制程序生成器、集成與管理等6大部分。1、基本圖形資源管理與自動繪圖軟件基本圖形資源軟件是根據圖形標準或規范實現的軟件包，為用戶提供的是基本圖形及圖形操作的程序和函數庫。是其他圖形軟件的基礎。 常用的有CGI（計算機圖形界面），GKS（圖形軟件包）及 PHIGS（程序員等級交互圖形系統）等。自動繪圖軟件提供了各種基本圖元與圖形基本操作等功能，用戶可采用交互式方式完成繪圖工作，常用有 AutoCAD，CADKey等。2、幾何建模軟件。提供完整的

21、三維幾何形狀的描述與顯示。還具有各種圖形渲染及物性計算等功能，常用有 Pro/E、UGII。3、工程分析與計算利用工程計算及分析軟件可完成運動學、動力學、有限元分析等任務，常用的有Ansys、n astra n 等。4、仿真與模擬軟件5、工藝過程設計6、管理與集成對各種CAD/CAM軟件所產生的數據進行管理，采用數據庫。常用的數據庫有Oracle、Sybase、MS SQL Server、DB2、Informix 。2.3.3應用軟件基于系統軟件、支撐軟件基礎之上，專為某種特殊應用開發而成應用軟件。如機械標準件圖庫，公差標注工具，電子元器件。2.4 CAD/CAM系統的設計原則2.4.1系統設

22、計的總原則在滿足需求的前提下，既要實現目標，又要適應技術的發展， 還要考慮具有的人才與資金的條件。1、實用性；2、適度的先進性；3、系統性（完整性、功能與性能的配套，集成）；4、整體設計與分步實施。2.4.2系統硬件選用原則1、系統功能速度、精度、存儲能力及兼容性2、開發性與可移植性3、升級與擴展性4、性價比5、可靠性及維護性與服務2.4.3軟件選用原則1、功能；2、性價比；3、與硬件配套；4、二次開發能力、二次工具與開發環境；5、開放性；6、可靠性與服務。三、CAD/CAM軟件開發基礎重點：不同數據的數字化方法，特別是插值法，數據結構（線性表和二叉樹），數據庫的基本概念，工程數據的特點與工程

23、數據庫的功能。在CAD/CAM 系統應用過程中，不僅要向系統輸入大量的數據，同時系統也會產生大量的 數據，怎樣存儲、使用、管理好這些數據是使用好CAD/CAM 系統的重要任務，也是開發CAD/CAM軟件的基礎。3.1工程數據的程序化在進行機械設計與制造中，會遇見很多格式數據，要實現CAD/CAM 系統，首先要對這些數據進行計算機化或程序化。3.1.1數值程序化1、數組形式對于一組單一、精確、而數據之間又無規律的數列，可定義數組進行存放處理。如齒輪標準模數，見 P43表3.1可定義一個一維數組加以存放與處理。2、公式化對于一組單一、精確、而數據之間又規律的數列可采用公式表達。如60、70、80、

24、90、100、110 120這一標準的直徑序列，可采用下列公式（表達式進 行處理）D=int（Dc/10.02）*10+10 其中Dc是根據強度計算所得到的直徑。3.1.2數表程序化1、屏幕直觀交互式輸入法如果數表中的數據量不大，可在有限的屏幕中放置，且數據為有限個離散值，在使用時是根據綜合考慮選用中間值， 此時可這些數據用 屏幕輸出語句 輸到屏幕上供使用者 直觀交互式地選用。如齒輪傳動強度計算中的系數Kv ,此系數是根據原動機工作特性和工作載荷特性等進行綜合，在表3.2中進行選值(可選中間值)。表中數據量少，可在有限的屏幕中放置。2、數組化數據量較大，精確且無規律的數表可采用數組進行存儲與處

25、理。如平鍵和鍵槽與軸徑的尺寸關系數表3.3 P45。注：只能選用數表中數據，不能取中間值。3、公式化如果數表中只有兩個參數，設Pi、fi，且這兩個參數存在一一對應關系，即已知一個在數表中找得到的 Pi值、數表中有一個fi值與其對應，且若已知一個在數表中找不到的Pi值,有一個近似非數表中的 fi值與之對應，R與fi存在函數關系，則此數表可進行公式化。如表3.4(P47 )中蝸輪當量齒數與齒形系數的關系表。工程上常采用插值法和擬合法對這種數表可進行公式化。插值法原理：設有離散點序列( xi,yi)、(X2,y2)、 、(Xi,yi)、(Xn,yn),若有一函數 y=f(x)，且 yi=f(xj,則

26、稱 y=f(x)為(xi,yi)、(X2,y2)、 、(Xi,yJ、(Xn,yn)序列插值函 數。常用的插值方法有線性插值和拉格朗日插值法。1) 線性插值(兩點插值)已知兩點，(xi ,yi )、(X2,y2),并近似地認為其它數據在這兩點區間成線性關系，則可采用線 性插值。插值函數為(x-x 1)亠=1 Ty=yi+1X Xtx2 Xtx2 Xt如果有多點，相鄰兩點用直線段連接，則每段線性插值的一般形式為:y=yi+yi y*(X-X i-1 )例如：如表3.4(P47 )中蝸輪當量齒數與齒形系數的關系表,Xi Xi 丄當 Zv=25.6(即 x=25.6) ( Xi-i =24, y/=1

27、.88); ( Xi=26, yi=1.85)，求 Yf2) 拉格朗日插值當線性插值誤差較大，可采用高次插值(二次和二次以上)通過整理線性插值表達式得：17f(x)=y=y i x - X2+ y2 x - X1Xi X2X2 Xi二次插值f(X)=y=y i (xji + y2(Xi - X2)(Xi - X3)(XXi)(XX3)+ 沽(X2 Xi)(X2 X3)(x Xi)(X X2)(X3 Xi)(X3 X2)#對于n個節點的n-i次拉格朗日插值的一般式子有:”（X _Xi）（ X -X2）（x - Xi i）（x _Xj*）（X Xn）f（X）=y= a yi Ai 其中 Ai=2厘

28、-社（Xi -Xi）（Xi X2）（Xi X）（Xi x）（Xi -Xn）4、交互式分級描述法將復雜的多元函數表按一定的原則分解成多個子表，用程序描述各子表之間的關系，通過人機交互式的方式逐步選值。如表3-5齒輪常用材料及力學性能，P48。3.1.3線圖程序化在工程中有許多線圖，這些線圖有的是通過計算公式所計算數據而來，有的是通過實驗數據而來。對實驗數據，由于實際情況的復雜性，很難用公式精確描述，一般采用某種近似 曲線公式來加以描述，這種曲線公式就稱為經驗公式，建立經驗公式的過程稱為曲線擬合。 擬合與插值的區別是，插值是必須過插值節點，而擬合是不一定需要過節點的。1、擬合原理曲線擬合的方法很多

29、，常用的是最小二乘法。1） 線性方程擬合有n組實驗數據（xi，yi），設線性方程的形式：y=a+bx最小二乘法：為了達到最好的擬合，應使各節點的偏差平方最小，即使。nS（a, b）' （yi -a-bXj）2最小。S（a，b）有兩個參數 a與b。采用偏導求出最大值。i 土2） 對數方程擬合有n組實驗數據（Xi，yj,設對數方程的形式：y=a+blnx設X= Inx，則對數方程的形式為 y=a+bX。注意：在利用 3.9和3.i0式求a，b時，應將Inxi代入。3） 指數方程擬合有n組實驗數據（Xi，yi），設指數方程的形式：y=axb對兩邊取對數。得 Iny=lna+blnx。設 Y=

30、lny，X=lnx， A=lna，則有 Y=A+bX與線性方程擬合一樣求解。4）對數指數方程擬合（略）5）二次方程及多次方程擬合（略）3.2CAD/CAM 中的數據結構在CAD/CAM 中存在大量的數據，如性能參數，工藝數據、管理數據等。這些數據不是孤立的，他們之間存在作關系。怎樣將這些數據進行有效的管理與存儲，表達和定義好他們的結構是基礎。這就是數據結構問題。3.2.1基本概念與術語即人們感知到的景象。數據可以是數據：是現實世界客觀存在的實體或事物的屬性值, 數值、字符、文字，也可以是聲音、圖形圖象等。信息：是含有一定意義的數據稱為信息信息與數據的關系是：1）信息是有一定含義的數據2）信息是

31、經過加工處理后的數據3）信息是對決策有價值的數據現實世界（數據）、信息與計算機之間的關系如圖3.8 P56實體：客觀存在并可相互區別的事物。屬性：實體特性屬性值：每一個實體屬性所能測量或記錄的值。數據（屬性）域：屬性取值范圍數據按組成的內容可分成若干層次1）字符 是組成數據的最小單位。包括數字、字母、特殊符號等2） 數據項是數據中最基本的、不可分的、并有命名的數據單位，由字符組成，代表某一數據量。如軸承性能表3.9 P57中的軸承代號、尺寸、載荷等。3）組合項 由一個或多個數據項組成。如尺寸由四個數據項組成。4）記錄：相關數據項或組合項構成的集合稱為一條記錄，他描述了一個實體。如代號為6202

32、軸承對應一行中的各數據項共同描述的某一型號的軸承。記錄又稱為數據元素5） 文件相同性質的記錄的集合就是文件。表3.9中記錄全體構成了一個文件6） 數據庫 非單純性（即有一定的特點與要求）、具有結構文件的集合。3.2.2數據結構數據元素（記錄）不是孤立的，而是相互有關聯的。多個數據元素之間的關系構成一個數據結構，而數據結構又可能是另一個數據結構中的數據元素。即數據結構是可嵌套的。如圖3.9中的車床結構圖。數據結構有邏輯結構和物理結構之分。1、邏輯結構邏輯結構描述的是數據之間的邏輯關系，它是從客觀的角度去組織和表達數據。根據關系特點，邏輯結構分為線性結構和非線性結構。1）線性結構數據之間的關系只有

33、順序排列的位置關系，這種順序位置關系是線性的。因此這種數據結構稱為線性結構，也稱為線性表結構。數組就是一種線性結構。在線性結構中，每一數據元素（節點或數據域）只有一個前趨節點和一個后趨節點。2）非線性結構當數據結構中的某數據元素有兩個或兩個以上的前趨或后趨節點，則這種數據結構中的數據元素之間的關系是非線性的，因此此種數據結構稱為非線性數據結構。如圖3-9車床零部件關系（樹狀結構）和圖 3-10工藝路線方案（網狀結構）P58圖3-11表示的是一個幾何圖形及其數據結構，在這個數據結構中，樹狀結構與網狀結 構共存。樹狀結構：當數據結構中的數據元素有多個前趨，只有一個后趨。網狀結構：當數據結構中的數據

34、元素有多個前趨和多個后趨。2、物理結構數據的物理結構是指數據在計算機內部的存儲方式，是從物理存儲的角度描述數據之間的關系。常用的物理結構有順序存儲結構與鏈接存儲結構 兩種。1）順序存儲結構：用一組連續的存儲單元依次存放各數據元素。特點：存儲順序與邏輯順序一致， 只需要存放第一個數據元素的地址， 其他元素的地址 是第一個元素地址加上一個相對地址， 因此占用存儲單元少， 簡單，結構緊湊。但缺乏柔性， 當要進行增刪操作時，必須重新分配存儲單元。費時。如數組。2）鏈接存儲結構在數據元素中，除存放數據外，還存放其他數據的存放地址。這樣，在得到第一個元素得地址后，就可以根據第一個數據元素中地址檢索出其下一

35、個數據元素的存放地，以此類推。這種物理存儲方式稱為鏈接存儲結構。在鏈接存儲結構中，每一個數據元素有數據和地址（或指針）兩種域組成。根據指針域的個數，鏈接存儲結構可大致分為三類。（1） 單向鏈結構在每一個數據元素中，只有一個指向下（或上）一個數據元素指針域。如圖3-14a如果指針所指的方向與邏輯順序相同，則稱正向鏈；如圖3-14a如果指針所指的方向與邏輯順序相反，則稱為反向鏈；如圖3-14b如果在最后一個數據元素中，有指向第一個數據元素的指針，則此鏈接結構構成了一個環鏈；如圖3-14C（2） 雙向鏈結構在每一個數據元素中，有兩個指針，一個指向下一個數據元素，而另一個指向上一個數據元素。雙向鏈也可

36、以構成環鏈。如圖3-14d和如圖3-14e環鏈的最大特點是任何一個數據元素都可以是數據存取的入口點，存取效率高。（3） 多向鏈結構在數據結構中，某些數據元素有兩個以上的指向其他數據元素的指針域。多向鏈結構一般用于矩、樹狀等數據結構存儲。如圖3-14f3.2.3常用的數據結構1、線性表線性表是一個由 n （n>=0）個數據元素（ai, a?, ,為）組成的有限序列，表中的每一個數據元素，除第一個和最后一個外，僅有一個直接前驅和一個直接后繼。當n=0時,稱為空表。線性表的邏輯表示可為：（ai, a2, ,ai）,如軸徑序列值（3, 6, 10, 14 ,18, 24, 30, 40, 50,

37、 65,.）線性表的物理存儲結構既可以采用順序存儲，也可以采用鏈接存儲結構。2、棧與隊列1 ）棧當對線性表的刪除與插入操作只能在表的一端進行時，線性表就變成了棧。在棧中，允許插入與刪除的端稱為棧頂，而另一端稱為棧底。 棧的操作是按后進先出的原則進行的，因此棧也稱為后進先出表（LIFO）。實際生活中，棧的例子很多。如穿衣服，火車換道。棧的示意圖如圖3-16。舉例2534按順序入棧，出棧有幾種順序？棧的物理存儲結構可以是順序，也可以是鏈接。在順序棧中，要有一個棧頂指示器和一 個棧頂界限（限制棧的空間）2）隊列 當對線性表的刪除與插入操作限制只在一端插入，在另一端刪除時，線性表就變成了隊。允許插入的

38、一端稱為隊尾，而允許刪除的一端稱為隊頭。棧的操作是按先進先出的 原則進行的，因此隊也稱為先進先出表（LIFO）。實際生活中，隊的例子很多。如排隊買東西，如圖3-18。隊的物理存儲結構可以是順序，也可以是鏈接。在順序隊中，要分別設置隊頭指針和隊尾指針以及一個隊尾界限（限制隊的空間）。隊“溢出”與“假溢出”，參見P 62.采用循環隊解決“假溢出”問題。3、數組數組是一種按順序排列與存儲、并且每個數據元素具有相同的數據類型的特殊線性表。4、串是一種特殊的數組，其數據元素中數據為字符類型。5、樹與二叉樹1）樹棧、隊、數組與串都是線性結構，不能解決實際中非線性問題，如行政單位結構，產品 結構等問題。這就

39、需要各種非線性結構。樹是一種常用的非線性結構，其定義為當數據元素集合中的每一個數據元素都一個或多個后繼，而只有一個前驅，并且處于最高層的那個數據元素沒有前驅。這樣的數據結構稱為樹。沒有前驅的最高層的那個數據元素（節點）稱為樹根；樹的最大層次稱為樹的深度；節 點的后繼（子樹）個數稱為度；度數（或后繼）為零的節點稱為樹葉。用例子圖3-21說明這些概念。 P63樹的物理結構可以是順序、也可以是鏈接。2）二叉樹當樹具有以下特點時，就稱其為而叉樹。（1）可以沒有任何數據節點，即為空。樹必須具有至少一個根節點。（2）每一個節點的度不能超過 2。樹則無限制；（3）二叉樹的子樹有左右之分，不能顛倒。樹的子樹無

40、左右之分，可以交換位置。 二叉樹的物理存儲結構常采用鏈接結構，其每個節點有一個左指針域和一個右指針域。 這種結構與二叉樹的邏輯結構一致。3) 二叉樹的遍歷按一定規律，不重復地訪問樹中的每一個節點，這種操作稱為遍歷。對于二叉樹，有三中遍歷方式，即前序、中序和后序。具體算法見P64。舉例說明三種遍歷方法的算法。參見圖 3-24P656、圖與網在一個數據結構中，每一個節點(數據元素)可以有多個直接的前驅和后繼時，這種數據結構稱為圖。圖由頂點與邊組成，見圖3-25P65設V是頂點集合，E是邊的集合，則圖 G可用下式表示：G=(V,E)若頂點之間是有序的，則邊是有方向的，如圖3-25 G3 P65,這種

41、圖稱為有向圖。否則稱為無向圖。樹與圖的關系：樹是一種特殊的圖。圖3-25中的圖G2，即是圖，也是樹。P65通常用n階鄰接方陣來表示n個頂點的圖的邏輯結構。鄰接矩陣中每個元素定義如下：L 1 若V與Vj相連V(i,j)= YI- 0 若Vi與Vj不相連參見圖3-26說明圖及其鄰接矩陣。當圖的邊有權重時，圖的鄰接變為Wij 若Vi與Vj相連V(i,j)= YJ 0 若Vi與Vj不相連此時圖稱為網。參見圖3-27說明網及其鄰接矩陣。3.3數據文件文件是數據管理的一種形式，它能獨立于應用程序單獨存儲。文件用于數據的管理、交換等。文件是記錄的集合，文件記錄中唯一能夠記錄的數據項的稱為關鍵字。如表3-10

42、齒輪 參數表（P67）中的零件編號就是齒輪參數文件的關鍵字。1、常用的文件組織方法1） 順序文件物理存儲順序與其邏輯順序一致。其存儲是連續的，結構緊湊簡單，但增刪、查詢算法較為復雜，時間度與空間度較大。有一些存儲設備只能存儲順序文件，如磁帶。2）索引文件 帶有一個包括關鍵字與記錄存放地址索引表的文件稱為索引文件。索引文件查詢方法是：先按關鍵字到索引文件中查到該關鍵字所對應的記錄存放地址，在根據地址到數據文件中去查找記錄。索引文件的索引表必須按關鍵字按順序排序。而文件本身可以排序或不排序。若文件本身排序稱為索引順序文件，否則稱為索引非順序文件。3） 直接存取文件又稱為隨機文件。采用一種算法將記錄

43、的關鍵字轉換為一個隨機數，根據這個隨機數確定記錄在存儲器中存放的位置。2、文件的操作文件的操作主要是查詢與排序。1）查詢 即查找關鍵字為某值的記錄常用的查找方法有順序、折半和分塊等三種查找方法。（1） 順序查找法從第一條記錄開始，逐條查找，若查找到欲查數值則查找結束。此方 法最為簡單，但效率低。（2） 折半查找法也叫二分查找法原理是：先將文件記錄按關鍵字大小順序排序，再將位置為中間的記錄的關鍵字值Km與欲查值K進行比較，比較結果有三種，Km > K、Km v K Km = K。若Km v K，則欲查記錄在文件前半區；若 Km v K，則欲查記錄在文件后半區；若Km=K，則查到欲查記錄，查

44、找結束。如果為前兩種情況，則在前半區或后半區繼續進行。（3） 分塊查找 原理與折半法類似，不同是將按關鍵字排好序的文件分成大于 2的若干塊； 再將欲查關鍵字依次與各塊的最大關鍵字值進行比較，確定查找范圍；然后在確定的那一塊 進行順序查找。舉例 設有一零件記錄，其關鍵字分別為4、7、16、31、39、41、47、55、61、77、80、83,以升序排序，要查找關鍵字為80的記錄。查找步驟：1、將記錄分成三塊（4、7、16、31）、（39、41、47、55）、）61、77、80、83）2、將欲查值80與各塊的最大值（31、55、83 ）進行比較，確定欲查記錄在第三塊3、在第三塊中進行順序查找2 ）

45、、排序對文件中記錄的關鍵字按遞增或遞減的順序進行重新排列稱為排序。排序的方法有很多，常用的有（1 ）選擇排序在記錄文件中找出關鍵字最小的記錄，將其與第一條記錄進行位置交換，然后從第二條記錄開始到最后一條記錄重復上述操作。舉例 P69冒泡法順序比較相鄰記錄的關鍵字，若后者比前者小，則交換位置，否則位置不變。經過不斷 的比較與位置交換，小值往前移，大值往后移，如水中的氣泡。舉例 P 69（3）插入法首先假定第一條記錄的位置是合適的，然后取出第二條記錄與第一條記錄進行關鍵字比較，若小于，則將第二條記錄插入到第一條記錄的前面，再取第三條記錄與前面各條記錄進行關鍵字比較；依次操作。舉例 P703.3.2

46、數據庫系統要解決CAD/CAM 系統中的數據信息交換問題，首先是解決數據信息集成與共享問題。數 據庫技術是進行數據集成與共享的最佳技術。1、數據庫特點數據管理技術經歷了三個階段，即人工管理、文件管理與數據庫管理。人工管理：程序中所用到的數據及其相關操作（如存儲、查詢等）都必須由程序員自己編程完成。數據與程序依賴度高，程序中存在大量的重復數據（冗余），數據不能共享。數據與程序對應。如圖3-30P70文件管理：數據按統一格式，以文件形式長期保存在計算機外存儲器中，數據與程序之間相對獨立。但數據文件之間彼此孤立，文件內部又無結構信息，因此數據的冗余度較大， 共享范圍有限，且文件管理系統缺乏對數據進行

47、集中管理與控制，數據的操作仍然離不開程序員，數據與程序不能完全獨立。數據文件與程序之間的關系見圖3-31 P71數據管理：其特點如下：1） 數據模型復雜在描述數據的同時，也描述數據之間的關系，即數據結構化強。2）數據的共享性好、冗余度低3） 數據具有獨立性數據可獨立于程序存在，應用程序不必隨著數據結構的變化而修改。數據庫系統本身具有很強數據操作功能，不需要程序進行數據操作。數據文件與程序之間的關系見圖3-32P714）數據具有安全性、完整性。數據庫系統提供了對數據控制的功能，數據能夠得到保護；數據的正確性、有效性、相容性，即完整性能得到保證。任何一個數據庫管理系統DBMS （ Data Bas

48、e Management System）,都會提供上述特點和功能。DBMS是數據庫系統的核心。盡管數據庫管理有許多優點，但必須根據具體情況選用數據的管理方法。2、數據庫管理系統1）數據庫系統的構成數據庫系統由相應的硬件、軟件和專職管理人員及數據構成。（1）硬件（2）軟件 數據庫軟件系統層次見圖3-33P72（3）數據庫管理人員（Data Base Administrator）DBA。決定數據庫的信息內容與存儲結構，定義和存儲數據庫數據；監督與控制對數據庫的使用與運行，保證數據的完整性；定義用戶權限；維護和改進數據庫。（4）數據庫 由DBMS建立、運行、管理及維護的通用化的、綜合性的數據集合。2

49、 ）數據庫管理系統的功能（1） 數據庫定義功能實現對數據的全局邏輯結構、局部邏輯結構、物理存儲結構及 權限等定義。（2） 數據庫管理功能提供對數據各種應用操作，如增刪、排序、查找、統計、輸入 輸出、修改等。（3） 數據庫的建立與維護功能建立、更新、再組織、恢復等功能。（4） 通信功能 與操作系統通信、與應用程序的通信（5） 其他功能文件管理、應用開發、存儲管理、設備管理等3 ）數據庫管理系統的組成（1）、數據描述語言（Data Description Ianguage ,DDL ）及其翻譯程序，用于描述數據 及其之間的關系，實現對數據庫的定義。（2）數據庫操縱語言（Data Manipulat

50、ion Ianguage ,DML ）及其編譯程序，用于存儲、 檢索、編輯數據庫數據。（3）數據庫管理例行程序（ Data Base Ma nageme nt Rout in ess ,DBMR ），一般包括系統運行控制程序、語言翻譯程序和DBMS的公用程序4）數據庫管理系統的抽象層次用戶所看到的數據與計算機中存儲的數據之間有一種映射關系，這種映射關系通過數據庫的三個模型層實現的。（1） 外模型用戶使用的數據視圖，是局部的邏輯視圖。表示用戶理解的實體、實體 屬性、實體之間的關系。外模型有多個，處理系統的外層。（2） 概念模型數據庫的全局邏輯視圖。表示整個系統的實體、實體屬性、實體之間 的關系。

51、概念模型只有一個，屬于系統的概念層。（3） 內模型數據庫的物理存儲模型。只有一個，最底層。在DBMS中用DDL精確描述上述三種模型，就得到相應的模式。即外模式（子模式）、概念模式（模式）、內模式（物理模式）。以內模式（物理模式）為框架的數據庫為物理數據庫。以概念模式（模式）為框架的數據庫為概念數據庫。概念數據庫是由數據庫設計者在物理數據庫之上構造出來的。以外模式（子模式）為框架的數據庫為用戶數據庫。從內模式到外模式需要經過物理模式t模式t子模式的兩級轉換。參見圖3-34和3-35 P743、數據庫的數據模型表示實體與實體之間的關系的模型稱為實體模型。常見的數據模型有層次模型、網狀模型和關系模型

52、。1 ）層次模型用樹結構表示實體及實體之間的關系的模型。層次模型必須滿足兩個條件，即只有一個根節點，根節點以外的其他節點有且僅有一個前驅。 如圖3-36P752）網狀模型取消層次模型的兩個要求，就可得到網狀模型如圖3-37 P753）關系模型 用二維表結構表示實體及實體之間的關系的模型。一張二維表就是一個關系。參見表3-11P76關系二維表必須滿足下列條件：（1）表中的每一列必須是基本數據項，不能是組合項（2）每一列必須具有相同的數據類型（3）每一列必須有一個唯一的屬性名（4）不能有兩條相同數據的行（5）列與行的順序不受限制基于關系模型建立的數據系統稱為關系型數據庫系統。4、工程數據庫目前，商用數據庫（即關系型數據庫） 發展已較為成熟，但仍然不能滿足對工程數據的管理。這是因為，工程數據具有如下特點:1 ）數據形態多樣性靜態數據、動態過程數據、定期改變的結果數據。30#2）數據類型的