A方向第4章_CAD中常用的數(shù)據(jù)結(jié)構(gòu) (1)

1、機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)24.1 基本概念基本概念4.2 線性表線性表4.3 棧棧4.4 樹樹4.5 二叉樹二叉樹機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)3 一個孤立的具體數(shù)據(jù)往往沒有任何意義。一個孤立的具體數(shù)據(jù)往往沒有任何意義。 各相關(guān)數(shù)據(jù)的集合各相關(guān)數(shù)據(jù)的集合描述任何復(fù)雜事物。描述任何復(fù)雜事物。 數(shù)據(jù)之間的關(guān)系為數(shù)據(jù)賦予了豐富的含義。數(shù)據(jù)之間的關(guān)系為數(shù)據(jù)賦予了豐富的含義。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)-是數(shù)據(jù)之間的關(guān)系是數(shù)據(jù)之間的關(guān)系4.1 數(shù)據(jù)結(jié)構(gòu)的概念車床的數(shù)據(jù)結(jié)構(gòu)圖車床的數(shù)據(jù)結(jié)構(gòu)圖機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)4個體特征總體事物及其

2、聯(lián)系現(xiàn)實世界實體屬性實體集實體及其聯(lián)系信息世界記錄數(shù)據(jù)項文件數(shù)據(jù)組織（數(shù)據(jù)文件、數(shù)據(jù)庫）計算機世界4.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)54.1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念 客觀存在的并可互相區(qū)分的事物；客觀存在的并可互相區(qū)分的事物； 實體的特征；實體的特征； 每個屬性所能測量或紀錄的值每個屬性所能測量或紀錄的值 屬性值的變化范圍；屬性值的變化范圍；機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)6 描述實體的數(shù)值、字符及其它的各種物理符號描述實體的數(shù)值、字符及其它的各種物理符號 是組成數(shù)據(jù)的最小單位；是組成數(shù)據(jù)的最小單位； 可用數(shù)字、字母、專用符號表示可用

3、數(shù)字、字母、專用符號表示 是數(shù)據(jù)中最基本的、不可分的并有命名的數(shù)據(jù)單位是數(shù)據(jù)中最基本的、不可分的并有命名的數(shù)據(jù)單位4.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)7 由若干個數(shù)據(jù)項組成；由若干個數(shù)據(jù)項組成； 相同性質(zhì)的記錄的集合就是文件相同性質(zhì)的記錄的集合就是文件 相關(guān)組合項和數(shù)據(jù)項的集合構(gòu)成一個記錄，是描述某個相關(guān)組合項和數(shù)據(jù)項的集合構(gòu)成一個記錄，是描述某個實體屬性的集合實體屬性的集合 非單純性、有結(jié)構(gòu)文件的集合非單純性、有結(jié)構(gòu)文件的集合4.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)8數(shù)據(jù)結(jié)構(gòu)理論數(shù)據(jù)結(jié)構(gòu)理論 研究數(shù)據(jù)元素之間的抽象化關(guān)系，并不涉及數(shù)

4、據(jù)元素的具體內(nèi)容。以車床為研究數(shù)據(jù)元素之間的抽象化關(guān)系，并不涉及數(shù)據(jù)元素的具體內(nèi)容。以車床為例：例：4.1.2數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)9數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)物理結(jié)構(gòu)1.1.數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)描述的是數(shù)據(jù)之間的邏輯關(guān)系、它從客觀的角度數(shù)據(jù)的邏輯結(jié)構(gòu)描述的是數(shù)據(jù)之間的邏輯關(guān)系、它從客觀的角度組織和表達數(shù)據(jù)。組織和表達數(shù)據(jù)。邏輯結(jié)構(gòu)歸納邏輯結(jié)構(gòu)歸納為兩大類型：為兩大類型：線性結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)非線性結(jié)構(gòu)樹狀結(jié)構(gòu)樹狀結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)樹狀網(wǎng)狀的結(jié)合樹狀網(wǎng)狀的結(jié)合4.1.2數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)10l

5、 線性結(jié)構(gòu)線性結(jié)構(gòu) 每一個數(shù)據(jù)元素僅與它前面的一個和后面的一個數(shù)據(jù)元素相聯(lián)系，每一個數(shù)據(jù)元素僅與它前面的一個和后面的一個數(shù)據(jù)元素相聯(lián)系，因而只能表達數(shù)據(jù)間的簡單順序關(guān)系。因而只能表達數(shù)據(jù)間的簡單順序關(guān)系。 特點：特點：l 這種結(jié)構(gòu)的數(shù)據(jù)可以用數(shù)表的形式表示。這種結(jié)構(gòu)的數(shù)據(jù)可以用數(shù)表的形式表示。又稱這類數(shù)據(jù)結(jié)構(gòu)為又稱這類數(shù)據(jù)結(jié)構(gòu)為“線性表結(jié)構(gòu)線性表結(jié)構(gòu)”4.1.2數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)11例如：線性表的邏輯結(jié)構(gòu)例如：線性表的邏輯結(jié)構(gòu)4.1.2數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)12 這種結(jié)構(gòu)的數(shù)據(jù)間邏輯關(guān)系比較復(fù)雜。這種結(jié)構(gòu)的數(shù)據(jù)間邏輯關(guān)系比較復(fù)雜。4.1.

6、2數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)13（1 1） 樹狀結(jié)構(gòu)樹狀結(jié)構(gòu) 數(shù)據(jù)之間的關(guān)系是一種層次式的邏輯關(guān)系，每個數(shù)據(jù)元素僅與數(shù)據(jù)之間的關(guān)系是一種層次式的邏輯關(guān)系，每個數(shù)據(jù)元素僅與它前面的一個數(shù)據(jù)元素相關(guān)，可與后面多個數(shù)據(jù)元素相關(guān)。它前面的一個數(shù)據(jù)元素相關(guān)，可與后面多個數(shù)據(jù)元素相關(guān)。4.1.2數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)144.1.2數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)15（2) 2) 網(wǎng)狀結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu) 數(shù)據(jù)元素之間的關(guān)系是一種多元關(guān)系，即多對多、多數(shù)據(jù)元素之間的關(guān)系是一種多元關(guān)系，即多對多、多對一。對一。9412641078410584548912

7、445678 910工藝路線方案圖工藝路線方案圖4.1.2數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)16（4 4）樹狀網(wǎng)狀的結(jié)合）樹狀網(wǎng)狀的結(jié)合(E4)V1(V4)V2V4(E6)(E5)E2E4E1F1（F2）(F4)(F4)四面體四面體四面體的邏輯結(jié)構(gòu)圖四面體的邏輯結(jié)構(gòu)圖GF1F2E2E4E4E6E5F4F4V4V4V1V2E14.1.2數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)172.2. 數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu) ( (1) 1) 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 4.1.2數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)184.1.2數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)

8、據(jù)結(jié)構(gòu)19 一個數(shù)據(jù)元素項由兩個字段組成一個數(shù)據(jù)元素項由兩個字段組成 信息字段（信息字段（INFO）和指）和指針字段針字段(POINT)信息字段信息字段 存放數(shù)據(jù)元素本身的域存放數(shù)據(jù)元素本身的域指針字段指針字段 存放直接后繼或直接前驅(qū)的域稱為指針域存放直接后繼或直接前驅(qū)的域稱為指針域(point )。指針域中存儲的信息稱作指針。指針域中存儲的信息稱作指針。（2 2）鏈接存儲結(jié)構(gòu)）鏈接存儲結(jié)構(gòu)4.1.2數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)20根據(jù)指針的數(shù)目，鏈接存根據(jù)指針的數(shù)目，鏈接存儲結(jié)構(gòu)有三種類型：儲結(jié)構(gòu)有三種類型： 4.1.2數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)21

9、正向鏈：正向鏈：連接方向與邏輯順序相同連接方向與邏輯順序相同反向鏈：反向鏈：R1R2R4R4R5反向鏈 。 R1R2R4R4R54.1.2數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)22單向環(huán)鏈：單向環(huán)鏈：最后一個數(shù)據(jù)元素與第一個數(shù)據(jù)元素通過指針鏈最后一個數(shù)據(jù)元素與第一個數(shù)據(jù)元素通過指針鏈接接單向環(huán)鏈R1R2R4R4R54.1.2數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)23R1R2R4R4R5雙向鏈R1R2R4R4R5雙向鏈環(huán)鏈4.1.2數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)24 R24 R12 R42 R21R224) 4) 多向鏈結(jié)構(gòu)多向鏈結(jié)構(gòu)4.1.2數(shù)據(jù)結(jié)構(gòu)機械C

10、AD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)25 R1R2R4R4R5R6鏈接存儲結(jié)構(gòu)的記錄增刪鏈接存儲結(jié)構(gòu)的記錄增刪R1R2R4R4R54.1.2數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)26線線性性結(jié)結(jié)構(gòu)構(gòu)非非線線性性結(jié)結(jié)構(gòu)構(gòu)圖與網(wǎng)圖與網(wǎng)4.1.4 常見的數(shù)據(jù)結(jié)構(gòu)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)27 4.2 線性表機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)28。4.2 線性表機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)4.3 棧 機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)30 4.3 棧機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)4.4 隊列 允許刪除的一端叫隊頭允許刪除的一端叫隊頭。 。機械CA

11、D技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)32 4.5 數(shù) 組機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)33（1 1）樹）樹4.6 樹與二叉樹機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)34 4.6 樹與二叉樹機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)35 A B K F C J E G D H M I L機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)36B C DE F G H I J A K L M 機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)37傳動系統(tǒng)圖傳動系統(tǒng)圖邏輯結(jié)構(gòu)圖邏輯結(jié)構(gòu)圖物理結(jié)構(gòu)圖物理結(jié)構(gòu)圖4.6 樹與二叉樹機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)38機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)39（2

12、2）二叉樹）二叉樹AABBA只有左子樹的只有左子樹的兩叉樹兩叉樹ACB全兩叉樹全兩叉樹4.6 樹與二叉樹機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)40HGEDFCBAI 兩叉樹的邏輯結(jié)構(gòu)兩叉樹的邏輯結(jié)構(gòu)ABGEFDIHC兩叉樹的物理結(jié)構(gòu)兩叉樹的物理結(jié)構(gòu)4.6 樹與二叉樹機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)41HGEDFCBAI前序遍歷前序遍歷3）二叉樹的遍歷）二叉樹的遍歷4.6 樹與二叉樹機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)42HGEDFCBAI中序遍歷中序遍歷 4.6 樹與二叉樹機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)43HGEDFCBAI后序遍歷后序遍歷4.6 樹與二叉樹機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)44 154424.7 圖與網(wǎng)機械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)4515442 1 1）以數(shù)組的方式順序存儲，）以數(shù)組的方式順序存儲，2 2）多向鏈