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

1、機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)24.1 基本概念基本概念4.2 線性表線性表4.3 棧棧4.4 樹樹4.5 二叉樹二叉樹機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)3 一個(gè)孤立的具體數(shù)據(jù)往往沒(méi)有任何意義。一個(gè)孤立的具體數(shù)據(jù)往往沒(méi)有任何意義。 各相關(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)圖機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)4個(gè)體特征總體事物及其

2、聯(lián)系現(xiàn)實(shí)世界實(shí)體屬性實(shí)體集實(shí)體及其聯(lián)系信息世界記錄數(shù)據(jù)項(xiàng)文件數(shù)據(jù)組織（數(shù)據(jù)文件、數(shù)據(jù)庫(kù)）計(jì)算機(jī)世界4.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念機(jī)械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ū)分的事物； 實(shí)體的特征；實(shí)體的特征； 每個(gè)屬性所能測(cè)量或紀(jì)錄的值每個(gè)屬性所能測(cè)量或紀(jì)錄的值 屬性值的變化范圍；屬性值的變化范圍；機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)6 描述實(shí)體的數(shù)值、字符及其它的各種物理符號(hào)描述實(shí)體的數(shù)值、字符及其它的各種物理符號(hào) 是組成數(shù)據(jù)的最小單位；是組成數(shù)據(jù)的最小單位； 可用數(shù)字、字母、專用符號(hào)表示可用

3、數(shù)字、字母、專用符號(hào)表示 是數(shù)據(jù)中最基本的、不可分的并有命名的數(shù)據(jù)單位是數(shù)據(jù)中最基本的、不可分的并有命名的數(shù)據(jù)單位4.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)7 由若干個(gè)數(shù)據(jù)項(xiàng)組成；由若干個(gè)數(shù)據(jù)項(xiàng)組成； 相同性質(zhì)的記錄的集合就是文件相同性質(zhì)的記錄的集合就是文件 相關(guān)組合項(xiàng)和數(shù)據(jù)項(xiàng)的集合構(gòu)成一個(gè)記錄，是描述某個(gè)相關(guān)組合項(xiàng)和數(shù)據(jù)項(xiàng)的集合構(gòu)成一個(gè)記錄，是描述某個(gè)實(shí)體屬性的集合實(shí)體屬性的集合 非單純性、有結(jié)構(gòu)文件的集合非單純性、有結(jié)構(gòu)文件的集合4.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念機(jī)械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)機(jī)械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)系、它從客觀的角度組織和表達(dá)數(shù)據(jù)。組織和表達(dá)數(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)機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)10l

5、 線性結(jié)構(gòu)線性結(jié)構(gòu) 每一個(gè)數(shù)據(jù)元素僅與它前面的一個(gè)和后面的一個(gè)數(shù)據(jù)元素相聯(lián)系，每一個(gè)數(shù)據(jù)元素僅與它前面的一個(gè)和后面的一個(gè)數(shù)據(jù)元素相聯(lián)系，因而只能表達(dá)數(shù)據(jù)間的簡(jiǎn)單順序關(guān)系。因而只能表達(dá)數(shù)據(jù)間的簡(jiǎn)單順序關(guān)系。 特點(diǎn)：特點(diǎ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)機(jī)械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)機(jī)械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)機(jī)械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)系，每個(gè)數(shù)據(jù)元素僅與數(shù)據(jù)之間的關(guān)系是一種層次式的邏輯關(guān)系，每個(gè)數(shù)據(jù)元素僅與它前面的一個(gè)數(shù)據(jù)元素相關(guān)，可與后面多個(gè)數(shù)據(jù)元素相關(guān)。它前面的一個(gè)數(shù)據(jù)元素相關(guān)，可與后面多個(gè)數(shù)據(jù)元素相關(guān)。4.1.2數(shù)據(jù)結(jié)構(gòu)機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)144.1.2數(shù)據(jù)結(jié)構(gòu)機(jī)械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)系，即多對(duì)多、多數(shù)據(jù)元素之間的關(guān)系是一種多元關(guān)系，即多對(duì)多、多對(duì)一。對(duì)一。9412641078410584548912

7、445678 910工藝路線方案圖工藝路線方案圖4.1.2數(shù)據(jù)結(jié)構(gòu)機(jī)械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)機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)172.2. 數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu) ( (1) 1) 順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu) 4.1.2數(shù)據(jù)結(jié)構(gòu)機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)184.1.2數(shù)據(jù)結(jié)構(gòu)機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)

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

9、正向鏈：正向鏈：連接方向與邏輯順序相同連接方向與邏輯順序相同反向鏈：反向鏈：R1R2R4R4R5反向鏈 。 R1R2R4R4R54.1.2數(shù)據(jù)結(jié)構(gòu)機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)22單向環(huán)鏈：?jiǎn)蜗颦h(huán)鏈：最后一個(gè)數(shù)據(jù)元素與第一個(gè)數(shù)據(jù)元素通過(guò)指針鏈最后一個(gè)數(shù)據(jù)元素與第一個(gè)數(shù)據(jù)元素通過(guò)指針鏈接接單向環(huán)鏈R1R2R4R4R54.1.2數(shù)據(jù)結(jié)構(gòu)機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)23R1R2R4R4R5雙向鏈R1R2R4R4R5雙向鏈環(huán)鏈4.1.2數(shù)據(jù)結(jié)構(gòu)機(jī)械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)機(jī)械C

10、AD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)25 R1R2R4R4R5R6鏈接存儲(chǔ)結(jié)構(gòu)的記錄增刪鏈接存儲(chǔ)結(jié)構(gòu)的記錄增刪R1R2R4R4R54.1.2數(shù)據(jù)結(jié)構(gòu)機(jī)械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)機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)27 4.2 線性表機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)28。4.2 線性表機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)4.3 棧 機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)30 4.3 棧機(jī)械CAD技術(shù)基礎(chǔ)第4章 CAD數(shù)據(jù)結(jié)構(gòu)4.4 隊(duì)列 允許刪除的一端叫隊(duì)頭允許刪除的一端叫隊(duì)頭。 。機(jī)械CA

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

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