第四章機(jī)械技術(shù)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)演示文稿

第四章機(jī)械技術(shù)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)演示文稿當(dāng)前第1頁\共有138頁\編于星期六\18點(diǎn)優(yōu)選第四章機(jī)械技術(shù)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)當(dāng)前第2頁\共有138頁\編于星期六\18點(diǎn)3

一個(gè)孤立的具體數(shù)據(jù)往往沒有任何意義。各相關(guān)數(shù)據(jù)的集合→描述任何復(fù)雜事物。數(shù)據(jù)之間的關(guān)系為數(shù)據(jù)賦予了豐富的含義。數(shù)據(jù)結(jié)構(gòu)---------是數(shù)據(jù)之間的關(guān)系車床床身及導(dǎo)軌主軸箱尾座走刀箱溜板箱刀架離合器主軸組件中間變速機(jī)構(gòu)主軸主軸齒輪主軸軸承當(dāng)前第3頁\共有138頁\編于星期六\18點(diǎn)第四章機(jī)械CAD中常用的數(shù)據(jù)結(jié)構(gòu)掌握CAD軟件開發(fā)所需數(shù)據(jù)結(jié)構(gòu)的基本理論；線性表?xiàng)涠鏄洚?dāng)前第4頁\共有138頁\編于星期六\18點(diǎn)數(shù)據(jù)

—是對客觀事物的符號表示，是指能輸入到計(jì)算機(jī)內(nèi)中并被計(jì)算機(jī)接受和處理的符號的總稱。用文字符號、數(shù)字符號及其它規(guī)定的符號（如圖形、圖像）對現(xiàn)實(shí)世界的事物及其活動(dòng)的抽象描述。4.1基本概念當(dāng)前第5頁\共有138頁\編于星期六\18點(diǎn)

數(shù)據(jù)元素

—數(shù)據(jù)元素是數(shù)據(jù)的基本單位，是數(shù)據(jù)這個(gè)集合中相對獨(dú)立的個(gè)體。在程序中通常作為一個(gè)整體來進(jìn)行考慮和處理。在設(shè)計(jì)產(chǎn)品的過程中，可以把該產(chǎn)品的每個(gè)部件的每一個(gè)零件看作一個(gè)相對獨(dú)立的單元，這時(shí)每個(gè)零件就是一個(gè)數(shù)據(jù)元素；圓柱體、長方體可以作為零件形體的數(shù)據(jù)元素；直線、圓弧可以作為圖形的數(shù)據(jù)元素。

一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)和組合項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位，數(shù)據(jù)項(xiàng)是對客觀事物某一方面特性的數(shù)據(jù)描述。當(dāng)前第6頁\共有138頁\編于星期六\18點(diǎn)數(shù)據(jù)項(xiàng)

是數(shù)據(jù)中最基本的、不可分的并有命名的數(shù)據(jù)單位，是對客觀事物某一方面特性的數(shù)據(jù)描述。2）組合項(xiàng)由若干個(gè)數(shù)據(jù)項(xiàng)組成。當(dāng)前第7頁\共有138頁\編于星期六\18點(diǎn)數(shù)據(jù)對象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。如字符集合C={‘A’,’B’,’C,…}

數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是指相互之間具有(存在)一定聯(lián)系(關(guān)系)的數(shù)據(jù)元素的集合。當(dāng)前第8頁\共有138頁\編于星期六\18點(diǎn)車床床身及導(dǎo)軌主軸箱尾座走刀箱溜板箱刀架離合器主軸組件中間變速機(jī)構(gòu)主軸主軸齒輪主軸軸承

數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是指相互之間具有(存在)一定聯(lián)系(關(guān)系)的數(shù)據(jù)元素的集合。當(dāng)前第9頁\共有138頁\編于星期六\18點(diǎn)數(shù)據(jù)結(jié)構(gòu)的三個(gè)組成部分：邏輯結(jié)構(gòu)：描述數(shù)據(jù)元素之間的邏輯關(guān)系。

D_S=（D，S）存儲(chǔ)結(jié)構(gòu)：

數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)及其邏輯關(guān)系的表現(xiàn)稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)或物理結(jié)構(gòu)。數(shù)據(jù)操作：

對數(shù)據(jù)要進(jìn)行的運(yùn)算（查找、插入、刪除）。

當(dāng)前第10頁\共有138頁\編于星期六\18點(diǎn)數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類型:①集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個(gè)集合”外，沒有其它關(guān)系。②線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。③樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。④圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)

定義：數(shù)據(jù)的邏輯結(jié)構(gòu)描述的是數(shù)據(jù)之間的邏輯關(guān)系、它從客觀的角度組織和表達(dá)數(shù)據(jù)。當(dāng)前第11頁\共有138頁\編于星期六\18點(diǎn)圖4-2四類基本結(jié)構(gòu)圖當(dāng)前第12頁\共有138頁\編于星期六\18點(diǎn)線性結(jié)構(gòu)—結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。每一個(gè)數(shù)據(jù)元素僅與它前面的一個(gè)和后面的一個(gè)數(shù)據(jù)元素相聯(lián)系。特點(diǎn)：數(shù)據(jù)間的關(guān)系很簡單，只是順序排列的位置關(guān)系，而且這種位置關(guān)系是線性的。這種結(jié)構(gòu)的數(shù)據(jù)可以用數(shù)表的形式表示。又稱這類數(shù)據(jù)結(jié)構(gòu)為“線性表結(jié)構(gòu)”當(dāng)前第13頁\共有138頁\編于星期六\18點(diǎn)姓名電話號碼陳四。。。。。例4-1：電話號碼查詢系統(tǒng)設(shè)有一個(gè)電話號碼薄，它記錄了N個(gè)人的名字和其相應(yīng)的電話號碼，假定按如下形式安排：(a1,b1)，(a2,b2)，…(an,bn)，其中ai,bi(i=1，2…n)

分別表示某人的名字和電話號碼。本問題是一種典型的表格問題。數(shù)據(jù)與數(shù)據(jù)成簡單的一對一的線性關(guān)系。當(dāng)前第14頁\共有138頁\編于星期六\18點(diǎn)例如：線性表的邏輯結(jié)構(gòu)當(dāng)前第15頁\共有138頁\編于星期六\18點(diǎn)樹狀結(jié)構(gòu)

結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。

每個(gè)數(shù)據(jù)元素僅與它前面的一個(gè)數(shù)據(jù)元素相關(guān)，可與后面多個(gè)數(shù)據(jù)元素相關(guān)。樹結(jié)構(gòu)ABCDEFGH當(dāng)前第16頁\共有138頁\編于星期六\18點(diǎn)例如：線性表的邏輯結(jié)構(gòu)當(dāng)前第17頁\共有138頁\編于星期六\18點(diǎn)例4－2：磁盤目錄文件系統(tǒng)

磁盤根目錄下有很多子目錄及文件，每個(gè)子目錄里又可以包含多個(gè)子目錄及文件，但每個(gè)子目錄只有一個(gè)父目錄，依此類推：本問題是一種典型的樹型結(jié)構(gòu)問題，如圖1-1

，數(shù)據(jù)與數(shù)據(jù)成一對多的關(guān)系，是一種典型的非線性關(guān)系結(jié)構(gòu)—樹形結(jié)構(gòu)。當(dāng)前第18頁\共有138頁\編于星期六\18點(diǎn)網(wǎng)狀結(jié)構(gòu)—結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。數(shù)據(jù)元素之間的關(guān)系是一種多元關(guān)系，即多對多、多對一。9412631078310584538912345678

910工藝路線方案圖當(dāng)前第19頁\共有138頁\編于星期六\18點(diǎn)例4－3：交通網(wǎng)絡(luò)圖

從一個(gè)地方到另外一個(gè)地方可以有多條路徑。本問題是一種典型的網(wǎng)狀結(jié)構(gòu)問題，數(shù)據(jù)與數(shù)據(jù)成多對多的關(guān)系，是一種非線性關(guān)系結(jié)構(gòu)。佛山惠州廣州中山東莞深圳珠海圖1-2

網(wǎng)狀結(jié)構(gòu)當(dāng)前第20頁\共有138頁\編于星期六\18點(diǎn)

數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu)定義:

是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)方式，它從物理存儲(chǔ)的角度來描述數(shù)據(jù)以及數(shù)據(jù)間的關(guān)系。常用種類:

順序存儲(chǔ)結(jié)構(gòu)、鏈接存儲(chǔ)結(jié)構(gòu)。(1)順序存儲(chǔ)結(jié)構(gòu)

定義:

利用一組地址連續(xù)的存儲(chǔ)單元依次存放各數(shù)據(jù)元素。

當(dāng)前第21頁\共有138頁\編于星期六\18點(diǎn)當(dāng)前第22頁\共有138頁\編于星期六\18點(diǎn)特點(diǎn)：1）存儲(chǔ)單元少，簡單易行，結(jié)構(gòu)緊湊。

2）數(shù)據(jù)結(jié)構(gòu)缺乏柔性，若要增刪數(shù)據(jù)，必須重新分配存儲(chǔ)單元。應(yīng)用：查詢頻繁，修改、補(bǔ)充、刪除數(shù)據(jù)量小的場合。當(dāng)前第23頁\共有138頁\編于星期六\18點(diǎn)

用一組任意的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素(這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的)。信息字段結(jié)構(gòu)形式：

一個(gè)數(shù)據(jù)元素項(xiàng)（結(jié)點(diǎn)）由兩個(gè)字段組成

信息字段（INFO）和指針字段(POINT)指針字段信息字段

存放數(shù)據(jù)元素本身的域指針字段

存放直接后繼或直接前驅(qū)的域稱為指針域(point)。指針域中存儲(chǔ)的信息稱作指針。（2）鏈接式存儲(chǔ)結(jié)構(gòu)當(dāng)前第24頁\共有138頁\編于星期六\18點(diǎn)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1536元素21536元素21346元素31346元素3∧元素4∧元素4存儲(chǔ)地址

存儲(chǔ)內(nèi)容

指針1345

元素1

14001346

元素4∧…….……..…….

1400

元素21536…….……..…….1536

元素313461400元素1h1400元素1h當(dāng)前第25頁\共有138頁\編于星期六\18點(diǎn)structlink{charname;structlink*next};當(dāng)前第26頁\共有138頁\編于星期六\18點(diǎn)存儲(chǔ)結(jié)構(gòu)可獨(dú)立于邏輯結(jié)構(gòu)。存儲(chǔ)的物理順序不必與邏輯順序一致而仍能按邏輯要求存取數(shù)據(jù)。特點(diǎn)：鏈接存儲(chǔ)結(jié)構(gòu)在不改變原來存儲(chǔ)結(jié)構(gòu)的條件下，增刪記錄十分方便，只要控制指針即可。根據(jù)指針的數(shù)目，鏈接存儲(chǔ)結(jié)構(gòu)有三種類型：單向鏈結(jié)構(gòu)

雙向鏈結(jié)構(gòu)多向鏈結(jié)構(gòu)當(dāng)前第27頁\共有138頁\編于星期六\18點(diǎn)在不改變原來存儲(chǔ)結(jié)構(gòu)的條件下，只要控制指針即可R1R2R3R4R5R6鏈接存儲(chǔ)結(jié)構(gòu)的記錄增刪R1R2R3R4R5鏈接存儲(chǔ)結(jié)構(gòu)的記錄增、刪

當(dāng)前第28頁\共有138頁\編于星期六\18點(diǎn)

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等

線性結(jié)構(gòu)

非線性結(jié)構(gòu)

順序存儲(chǔ)

鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)ｊ?duì)列樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面當(dāng)前第29頁\共有138頁\編于星期六\18點(diǎn)數(shù)據(jù)的邏輯結(jié)構(gòu)非線性結(jié)構(gòu)集合圖狀結(jié)構(gòu)有向圖無向圖樹形結(jié)構(gòu)一般樹二叉樹線性結(jié)構(gòu)一般線性表線性表推廣廣義表數(shù)組串受限線性表?xiàng)：完?duì)列圖1-5

數(shù)據(jù)邏輯結(jié)構(gòu)層次關(guān)系圖邏輯結(jié)構(gòu)與所采用的存儲(chǔ)結(jié)構(gòu)線性表樹圖順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)復(fù)合存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)當(dāng)前第30頁\共有138頁\編于星期六\18點(diǎn)數(shù)據(jù)類型：在一種程序設(shè)計(jì)語言中，變量所具有的數(shù)據(jù)種類。例1、在C語言中，數(shù)據(jù)類型：基本類型和構(gòu)造類型基本類型：整型、浮點(diǎn)型、字符型構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義數(shù)據(jù)對象：某種數(shù)據(jù)類型元素的集合。例2、整數(shù)的數(shù)據(jù)對象是{…-3，-2，-1，0，1，2，3，…}英文字符類型的數(shù)據(jù)對象是{A，B，C，D，E，F(xiàn)，…}

數(shù)據(jù)對象可以是有限的，也可以是無限的。當(dāng)前第31頁\共有138頁\編于星期六\18點(diǎn)

線性結(jié)構(gòu)是最常用、最簡單的一種數(shù)據(jù)結(jié)構(gòu)。而線性表是一種典型的線性結(jié)構(gòu)。其基本特點(diǎn)是線性表中的數(shù)據(jù)元素是有序且是有限的。在這種結(jié)構(gòu)中：①存在一個(gè)唯一的被稱為“第一個(gè)”的數(shù)據(jù)元素；②存在一個(gè)唯一的被稱為“最后一個(gè)”的數(shù)據(jù)元素；③除第一個(gè)元素外，每個(gè)元素均有唯一一個(gè)直接前驅(qū)；④除最后一個(gè)元素外，每個(gè)元素均有唯一一個(gè)直接后繼。4.2．線性表當(dāng)前第32頁\共有138頁\編于星期六\18點(diǎn)

線性表(LinearList)：是由n(n≧0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a1，a2，…an組成的有限序列。該序列中的所有結(jié)點(diǎn)具有相同的數(shù)據(jù)類型。其中數(shù)據(jù)元素的個(gè)數(shù)n稱為線性表的長度。當(dāng)n=0時(shí)，稱為空表。當(dāng)n>0時(shí)，將非空的線性表記作：(a1，a2，…an)a1稱為線性表的第一個(gè)(首)結(jié)點(diǎn)，an稱為線性表的最后一個(gè)(尾)結(jié)點(diǎn)。線性表的定義4.2．線性表當(dāng)前第33頁\共有138頁\編于星期六\18點(diǎn)a1，a2，…ai-1都是ai(2≦i≦n)的前驅(qū)，其中ai-1是ai的直接前驅(qū);ai+1，ai+2，…an都是ai(1≦i≦n-1)的后繼，其中ai+1是ai的直接后繼。當(dāng)前第34頁\共有138頁\編于星期六\18點(diǎn)線性表邏輯結(jié)構(gòu)

[a(1)，a(2)，a(3)，…,a(i-1)，a(i)，a(i+1)，…，a(n)]

其中，線性表中的數(shù)據(jù)元素ai(1≦i≦n)只是一個(gè)抽象的符號，其具體含義隨具體應(yīng)用的不同而不同。數(shù)據(jù)元素ai可以是一個(gè)數(shù)，可以是一個(gè)符號，還可以是一個(gè)線性表，甚至是更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。4.2.1線性表的邏輯結(jié)構(gòu)當(dāng)前第35頁\共有138頁\編于星期六\18點(diǎn)線性表中的結(jié)點(diǎn)可以是單值元素(每個(gè)元素只有一個(gè)數(shù)據(jù)項(xiàng))。例:26個(gè)英文字母組成的字母表：(A，B，C、…、Z）光軸軸徑系列值表示成線性表形式:（3，6，10，14，18，20，22，…,90）當(dāng)前第36頁\共有138頁\編于星期六\18點(diǎn)

線性表中的結(jié)點(diǎn)可以是記錄型元素，每個(gè)元素含有多個(gè)數(shù)據(jù)項(xiàng)，每個(gè)數(shù)據(jù)項(xiàng)稱為結(jié)點(diǎn)的一個(gè)域。每個(gè)元素有一個(gè)可以唯一標(biāo)識(shí)每個(gè)結(jié)點(diǎn)的數(shù)據(jù)項(xiàng)組，稱為關(guān)鍵字。例4：某校2001級同學(xué)的基本情況：{(‘2001414101’，‘張強(qiáng)’，‘男’，06/24/1983)，

(‘2001414102’，‘張化司’，‘男’，08/12/1984)…，

(‘2001414102’，‘李利辣’，‘女’，08/12/1984)}當(dāng)前第37頁\共有138頁\編于星期六\18點(diǎn)

減速器明細(xì)表也屬線性表，該表中的數(shù)據(jù)元素是由4個(gè)數(shù)據(jù)項(xiàng)組成的一個(gè)記錄。當(dāng)前第38頁\共有138頁\編于星期六\18點(diǎn)若線性表中的結(jié)點(diǎn)是按值(或按關(guān)鍵字值)由小到大(或由大到小)排列的，稱線性表是有序的。當(dāng)前第39頁\共有138頁\編于星期六\18點(diǎn)

線性表是一種相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu)，其長度可根據(jù)需要增長或縮短。對線性表的數(shù)據(jù)元素可以訪問、插入和刪除。

線性表的物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）

既可以采用順序存儲(chǔ)，也可以采用鏈接存儲(chǔ)結(jié)構(gòu)。當(dāng)前第40頁\共有138頁\編于星期六\18點(diǎn)、線性表的順序存儲(chǔ)結(jié)構(gòu)1、順序存儲(chǔ)：把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。用這種方法存儲(chǔ)的線性表簡稱順序表。

假設(shè)線性表的每個(gè)元素需占用m個(gè)存儲(chǔ)單元。則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置Loc(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置Loc(ai)之間滿足下列關(guān)系：

Loc(ai+1)=Loc(ai)+m

aiai+1Loc(ai+1)m個(gè)字節(jié)Loc(ai)當(dāng)前第41頁\共有138頁\編于星期六\18點(diǎn)線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為:a1a2aianLoc(a1)i-1個(gè)元素Loc(ai)=(i-1)*m+Loc(a1)

有序性：各數(shù)據(jù)元素之間的存儲(chǔ)順序與邏輯順序一致。均勻性：每個(gè)數(shù)據(jù)元素所占存儲(chǔ)空間的長度是相等的。線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)當(dāng)前第42頁\共有138頁\編于星期六\18點(diǎn)2順序表的基本操作

順序存儲(chǔ)結(jié)構(gòu)中，常用的線性表的操作：

建表、查找、修改、插入、刪除、求長度等。以下將對幾種主要的操作進(jìn)行討論。1）建表staticcharlistc[6]={‘A’,’B’,’C’,’D’,’E’};2）訪問charc;C=listc[2];3）修改listc[2]=‘T’;當(dāng)前第43頁\共有138頁\編于星期六\18點(diǎn)在線性表L=(a1，…ai-1，ai，ai+1，…，an)中的第i(1≦i≦n)個(gè)位置上插入一個(gè)新結(jié)點(diǎn)e，使其成為線性表：

L=(a1，…ai-1，e，ai，ai+1，…，an)

4)順序線性表的插入為保證線性表的均勻性，新的數(shù)據(jù)元素必須和表內(nèi)已有元素的類型一致；為了保證線性表的有序性，原線性表第i至最后一個(gè)元素要向后移動(dòng)一個(gè)數(shù)據(jù)元素所占存儲(chǔ)空間的長度。當(dāng)前第44頁\共有138頁\編于星期六\18點(diǎn)5)順序線性表的插入ABCXDE實(shí)現(xiàn)步驟(1)將線性表L中的第i個(gè)至第n個(gè)結(jié)點(diǎn)后移一個(gè)位置。(2)將結(jié)點(diǎn)e插入到結(jié)點(diǎn)ai-1之后。(3)線性表長度加1。[例4-5]

插入一個(gè)數(shù)據(jù)元素ABCDE插入后當(dāng)前第45頁\共有138頁\編于星期六\18點(diǎn)#defineLEN6Main（）{staticcharlistc[6]={‘A’,’B’,’C’,’D’,’E’};inti,j;charc1；

printf(“\n輸入插入新的數(shù)據(jù)元素：”);c1=getche（）；

printf(“\n輸入新的數(shù)據(jù)元素的位置：”);Scanf(“%d”,&i);For(j=LEN；j>i;j--)

listc[j]=listc[j-1];Listc[j-1]=c1;}當(dāng)前第46頁\共有138頁\編于星期六\18點(diǎn)3)順序線性表的刪除當(dāng)前第47頁\共有138頁\編于星期六\18點(diǎn)3)順序線性表的刪除[例4-4]刪除一個(gè)數(shù)據(jù)元素。#defineLEN5Main（）{staticcharlistc[5]={‘A’,’B’,’C’,’D’,’E’};inti,j;printf(“\n刪除第幾個(gè)數(shù)據(jù)元素？”);Scanf(“%d”,&i);For(j=i;j<LEN,;j++)

listc[j-1]=listc[j];

//第i個(gè)元素（下標(biāo)為i-1)開始

Listc[j]=‘\0’;}當(dāng)前第48頁\共有138頁\編于星期六\18點(diǎn)當(dāng)前第49頁\共有138頁\編于星期六\18點(diǎn)當(dāng)前第50頁\共有138頁\編于星期六\18點(diǎn)4.2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為了能正確表示數(shù)據(jù)元素間的邏輯關(guān)系，在存儲(chǔ)每個(gè)數(shù)據(jù)元素的域同時(shí)，還必須存儲(chǔ)指示其后繼數(shù)據(jù)元素的地址（或位置）信息。在鏈表結(jié)構(gòu)中，一個(gè)數(shù)據(jù)元素由數(shù)據(jù)域和指針域組成，稱為一個(gè)結(jié)點(diǎn)。datanext數(shù)據(jù)域(data)指針域(next)當(dāng)前第51頁\共有138頁\編于星期六\18點(diǎn)4.2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)數(shù)據(jù)元素用指針來保存其直接前趨或直接后繼的地址，形成環(huán)環(huán)相扣的鏈條，并通過指針來逐個(gè)檢索數(shù)據(jù)元素。……...a1a2a3aiai+1annil......a1a2aiai+1an(a1,a2,…ai,ai+1,…an)當(dāng)前第52頁\共有138頁\編于星期六\18點(diǎn)鏈接存儲(chǔ)結(jié)構(gòu)的記錄增、刪

在不改變原來存儲(chǔ)結(jié)構(gòu)的條件下，只要控制指針即可R1R2R3R4R5R6鏈接存儲(chǔ)結(jié)構(gòu)的記錄增刪R1R2R3R4R5當(dāng)前第53頁\共有138頁\編于星期六\18點(diǎn)根據(jù)指針的數(shù)目，鏈接存儲(chǔ)結(jié)構(gòu)有三種類型：單向鏈結(jié)構(gòu)

雙向鏈結(jié)構(gòu)多向鏈結(jié)構(gòu)當(dāng)前第54頁\共有138頁\編于星期六\18點(diǎn)2.單向鏈表單向鏈表的結(jié)點(diǎn)指針域中的指針存放該節(jié)點(diǎn)直接后繼的存放地址。第一個(gè)結(jié)點(diǎn)的地址存放在鏈表頭指針head中；鏈表的最后一個(gè)結(jié)點(diǎn)的指針城設(shè)為NULL。OFC如線性表為：L=(A，B，C，D，E，F(xiàn))A302BB06E663F∧DEFFC238OFCHEAD302B06238EFF663各個(gè)數(shù)據(jù)元素由一個(gè)指針域和一個(gè)數(shù)據(jù)域組成，通過指針構(gòu)成一個(gè)鏈狀結(jié)構(gòu)，且鏈接方向單一。當(dāng)前第55頁\共有138頁\編于星期六\18點(diǎn)頭結(jié)點(diǎn)：數(shù)據(jù)域不存放任何元素，其指針域存放第一個(gè)元素的存儲(chǔ)地址。頭指針：第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址；a1h頭結(jié)點(diǎn)

特點(diǎn)：

存儲(chǔ)空間不一定連續(xù)；

元素之間的后繼關(guān)系是由指針來體現(xiàn)的；

邏輯上相鄰，物理上不一定相鄰；

當(dāng)前第56頁\共有138頁\編于星期六\18點(diǎn)正向鏈：連接方向與邏輯順序相同反向鏈：連接方向與邏輯順序相反R1R2R3R4R5R1R2R3R4R5當(dāng)前第57頁\共有138頁\編于星期六\18點(diǎn)單向環(huán)鏈：最后一個(gè)數(shù)據(jù)元素與第一個(gè)數(shù)據(jù)元素通過指針鏈接．特點(diǎn)：①可以從任意一個(gè)元素進(jìn)入，按指針逐個(gè)存取各條記錄；②某個(gè)指針損壞不影響整個(gè)結(jié)構(gòu)。單向環(huán)鏈R1R2R3R4R5當(dāng)前第58頁\共有138頁\編于星期六\18點(diǎn)結(jié)點(diǎn)的描述

C語言中用帶指針的結(jié)構(gòu)體類型來描述typedefstructLnode{intdata;/*數(shù)據(jù)域，保存結(jié)點(diǎn)的值*/structLnode*next;/*指針域*/}LNode;/*結(jié)點(diǎn)的類型*/2)結(jié)點(diǎn)的實(shí)現(xiàn)

結(jié)點(diǎn)是通過動(dòng)態(tài)分配和釋放來的實(shí)現(xiàn)，即需要時(shí)分配，不需要時(shí)釋放。分別使用C語言提供的標(biāo)準(zhǔn)函數(shù)：malloc()，realloc()，sizeof()，free()。當(dāng)前第59頁\共有138頁\編于星期六\18點(diǎn)動(dòng)態(tài)分配

p=(LNode*)malloc(sizeof(LNode));函數(shù)malloc分配了一個(gè)類型為LNode的結(jié)點(diǎn)變量的空間，并將其首地址放入指針變量p中。動(dòng)態(tài)釋放

free(p);系統(tǒng)回收由指針變量p所指向的內(nèi)存區(qū)。P必須是最近一次調(diào)用malloc函數(shù)時(shí)的返回值。當(dāng)前第60頁\共有138頁\編于星期六\18點(diǎn)3)最常用的基本操作及其示意圖⑴結(jié)點(diǎn)的賦值

LNode*p;p=(LNode*)malloc(sizeof(LNode));p->data=20;p->next=NULL;p20NULL當(dāng)前第61頁\共有138頁\編于星期六\18點(diǎn)⑵常見的指針操作①q=p;操作前pa……q操作后②q=p->next;bpa……操作前操作后qbpa……③p=p->next;bpa……操作前操作后pba……bpa……當(dāng)前第62頁\共有138頁\編于星期六\18點(diǎn)操作前ypx……bqa…操作后ypx……bqa…④q->next=p;⑤q->next=p->next;操作前ypx……bqa…操作后ypx……bqa…當(dāng)前第63頁\共有138頁\編于星期六\18點(diǎn)

在鏈表建立過程中，首先要建立第一個(gè)結(jié)點(diǎn)，然后不斷地在其尾部增加新結(jié)點(diǎn)，直到不需再有新結(jié)點(diǎn)，即尾指針指向NULL為止。定義結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)，有兩個(gè)成員DATA和NEXT：

在數(shù)據(jù)域（data）中定義數(shù)據(jù)的類型，數(shù)據(jù)域中的數(shù)據(jù)可能只有一個(gè)也可能有多個(gè)，它們的類型可以一樣也可以不一樣，存放結(jié)點(diǎn)數(shù)據(jù)元素本身；在指針域（next）中定義指向數(shù)據(jù)結(jié)構(gòu)本身的指針，存放該結(jié)點(diǎn)直接后繼的地址。

4)建立單向鏈表當(dāng)前第64頁\共有138頁\編于星期六\18點(diǎn)定義結(jié)構(gòu)指針變量：

structnode*p,*p1,*head;

head：用來標(biāo)志鏈表頭；

p：在鏈表建立過程中，p總是不斷先接受系統(tǒng)動(dòng)態(tài)分配的新結(jié)點(diǎn)地址。

p1—>next：存儲(chǔ)新結(jié)點(diǎn)的地址。然后通過動(dòng)態(tài)分配內(nèi)存給每個(gè)結(jié)點(diǎn)賦值。申請動(dòng)態(tài)分配一個(gè)存儲(chǔ)空間的表示形式為：

(structnode*)malloc(sizeof(structnode))

4)建立單向鏈表當(dāng)前第65頁\共有138頁\編于星期六\18點(diǎn)鏈表建立的步驟：第-步：建立第一個(gè)結(jié)點(diǎn)structnode/*定義結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)*/{intdata;/*數(shù)據(jù)域*/structnode*next;}/*指向直接后繼的指針*/structnode*p,*p1,*head;/*定義結(jié)構(gòu)指針變量*/head=p1=p=(structnode*)malloc(sizeof(structnode);/*申請動(dòng)態(tài)分配一個(gè)存儲(chǔ)地址，為第一個(gè)結(jié)點(diǎn)地址*/dataheadp,p1當(dāng)前第66頁\共有138頁\編于星期六\18點(diǎn)第二步：給第一個(gè)結(jié)點(diǎn)成員data賦值并產(chǎn)生第二個(gè)結(jié)點(diǎn)scanf(“%d”,&p—>data);

/*輸入10*/p=(structnode*)malloc(sizeof(structnode);datanextnext10第一結(jié)點(diǎn)第二結(jié)點(diǎn)headp1p鏈表建立的步驟：當(dāng)前第67頁\共有138頁\編于星期六\18點(diǎn)第三步：將第一個(gè)結(jié)點(diǎn)與第二個(gè)結(jié)點(diǎn)連接起來

p1—＞next=p;10nextnextdata第一結(jié)點(diǎn)P1第二結(jié)點(diǎn)Pheadp1p鏈表建立的步驟：當(dāng)前第68頁\共有138頁\編于星期六\18點(diǎn)第四步：給第二個(gè)結(jié)點(diǎn)成員data賦值并產(chǎn)生第三個(gè)結(jié)點(diǎn)p1=p;scanf(“%d”,&p->data);/*輸入8*/p=(structnode*)malloc(sizeof(structnode);鏈表建立的步驟：10nextnext8第一結(jié)點(diǎn)第二結(jié)點(diǎn)p1第三結(jié)點(diǎn)pnext10第一結(jié)點(diǎn)headp18next第二結(jié)點(diǎn)p1datanext第三結(jié)點(diǎn)p第五步：將第二個(gè)結(jié)點(diǎn)與第三個(gè)結(jié)點(diǎn)連接起來

p1—＞next=p;nextdata當(dāng)前第69頁\共有138頁\編于星期六\18點(diǎn)

以后步驟都是重復(fù)第四、五步,直到給出一個(gè)結(jié)束條件，不再建新的結(jié)點(diǎn)時(shí)，要有：

p—>next＝NULL；它表示尾結(jié)點(diǎn)。當(dāng)前第70頁\共有138頁\編于星期六\18點(diǎn)[例4－6]建立鏈表。用C語言建立單向鏈表的程序如下：

#include<stdio．h>#include<alloc．h>#defineLENsizeof(structnode)structnode/*定義結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)*/{intdata；

structnode*next；

}；

main(){structnode*p,*pl,*head；

head＝p＝(structnode*)malloc(LEN)；/*申請動(dòng)態(tài)分配一個(gè)存儲(chǔ)地址，為第一個(gè)結(jié)點(diǎn)地址*/scanf(“％d”,&p->data)；/*輸入第一個(gè)結(jié)點(diǎn)的數(shù)據(jù)成員*/當(dāng)前第71頁\共有138頁\編于星期六\18點(diǎn)while(p->data!＝0)/*結(jié)束條件：當(dāng)輸入0時(shí)，退出循環(huán)*/{p1＝p；

p＝(structnode*)malloc(LEN)；/*申請動(dòng)態(tài)分配一個(gè)存儲(chǔ)地址，為下一個(gè)結(jié)點(diǎn)地址*/scanf(”％d”,&p->data)；

/*輸入中間結(jié)點(diǎn)數(shù)據(jù)成員*/p1->next=p；

/*中間結(jié)點(diǎn)的指針成員值，將前后兩個(gè)結(jié)點(diǎn)連接起來*/

}p->next＝NULL；/*尾結(jié)點(diǎn)的指針成員值*/

……}當(dāng)前第72頁\共有138頁\編于星期六\18點(diǎn)

為了證實(shí)已建鏈表是所需要的，應(yīng)在上程序的省略處加入下列程序段：

p＝head；/*頭指針*/printf(”鏈表數(shù)據(jù)成員是：”)；／*鏈表顯示*／

while(p->next!=NULL){printf(”％d”，p->data)；／*顯示中間結(jié)點(diǎn)數(shù)據(jù)成員*／

p＝p->next；

}printf(”％d＼n”，p->data)；【結(jié)果】

1086420／*建鏈表時(shí)輸入的數(shù)據(jù)*／鏈表數(shù)據(jù)成員是：1086420／*顯示所建的鏈表*／當(dāng)前第73頁\共有138頁\編于星期六\18點(diǎn)打印：沒找到訪問P開始輸入iP=head,j=0i=j+1P=P－﹥nextP為空嗎？i=j？返回返回YYNN5)單向鏈表的訪問訪問單向鏈表的第i個(gè)結(jié)點(diǎn)，應(yīng)從表頭開始檢索．根據(jù)指針域的值逐個(gè)查直到找到第i個(gè)結(jié)點(diǎn)。當(dāng)前第74頁\共有138頁\編于星期六\18點(diǎn)5)單向鏈表的訪問[例4－7]對[例4－1]所建鏈表的第i個(gè)結(jié)點(diǎn)的訪問程序如下（注意：在調(diào)用之前，應(yīng)將p指向表頭）：

visit(inti){Intj=1;intdata;Sructnode*p;p=head;while(p)/*當(dāng)結(jié)點(diǎn)指針非空時(shí)*/{if(j++＝＝i)/*如果是第i個(gè)結(jié)點(diǎn)*/{data＝p—>data；return；}/*將第i個(gè)結(jié)點(diǎn)數(shù)據(jù)保存在data中，返回*/當(dāng)前第75頁\共有138頁\編于星期六\18點(diǎn)p＝p－＞next;/*結(jié)點(diǎn)指針指向下一結(jié)點(diǎn)*/}Pritnf(“\n序號超出范圍”);return(0);}當(dāng)前第76頁\共有138頁\編于星期六\18點(diǎn)

在鏈表中查找是否有指定的數(shù)據(jù)元素，若有就輸出第一次出現(xiàn)這個(gè)數(shù)據(jù)元素的邏輯位置，否則輸出沒由這個(gè)數(shù)據(jù)元素的信息。

[例4－8]查找指定數(shù)據(jù)，程序如下

intsearch(){intj=1;intdata;sructnode*p;p=head;Pritnf(“\n輸入要查找的數(shù)據(jù)：”);scanf(”％d”,&data)；

/*輸入要查找的數(shù)據(jù)*/while(p)/*當(dāng)結(jié)點(diǎn)指針非空時(shí)*/{if(p—>data＝＝data；return（j）；)/*如果是第j個(gè)結(jié)點(diǎn)*/j++；6）單向鏈表查找當(dāng)前第77頁\共有138頁\編于星期六\18點(diǎn)p＝p－＞next;/*結(jié)點(diǎn)指針指向下一結(jié)點(diǎn)*/}Pritnf(“\n沒找到該數(shù)據(jù)”);return(0);}當(dāng)前第78頁\共有138頁\編于星期六\18點(diǎn)

在單鏈表中刪除第i個(gè)結(jié)點(diǎn)的基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，修改其指向后繼的指針。ai-1ai+1ai-1q=p->next;（引入一個(gè)結(jié)點(diǎn)q）p->next=q->next;

e=q->data;delete(q);pq7）單向鏈表刪除當(dāng)前第79頁\共有138頁\編于星期六\18點(diǎn)[例4-8]刪除第i個(gè)結(jié)點(diǎn)。Voiddelete(inti){intj=1;sructnode*p，*q;p=q=head;if(i==1){head=q－>next;free(q);return;}/*將頭結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)的后繼點(diǎn)*/while(p)/*當(dāng)結(jié)點(diǎn)指針非空時(shí)*/{if(++j==i-1)/*如果p是第i-1個(gè)結(jié)點(diǎn)*/{(q=p—>next；/*q指向第i個(gè)結(jié)點(diǎn)*/if(q==NULL){Pritnf(“\n序號超出范圍”);return;}p->next=q->next;/*將第i-1個(gè)結(jié)點(diǎn)指針指向第i+1個(gè)結(jié)點(diǎn)*/；

delete(q);

return;}當(dāng)前第80頁\共有138頁\編于星期六\18點(diǎn)p＝p－＞next;/*

如果p不是第i-1個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)指針指向下一結(jié)點(diǎn)*/}Pritnf(“\n序號超出范圍”);return(0);}當(dāng)前第81頁\共有138頁\編于星期六\18點(diǎn)

插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。xai-1ai8）單向鏈表插入

在單鏈表中的實(shí)現(xiàn)：有序?qū)?/p>

<……ai-1,ai…>

改變?yōu)?/p>

<…ai-1,x,ai…>當(dāng)前第82頁\共有138頁\編于星期六\18點(diǎn)

插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。首先找到ai-1所在的結(jié)點(diǎn)node，然后生成一個(gè)數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)newnode，newnode結(jié)點(diǎn)作為node的直接后繼結(jié)點(diǎn)，newnode結(jié)點(diǎn)的指針指向ai所在的結(jié)點(diǎn)。當(dāng)前第83頁\共有138頁\編于星期六\18點(diǎn)(1)查找到第i-1個(gè)節(jié)點(diǎn)，將第

i

個(gè)結(jié)點(diǎn)的地址node->next取出，存放在指針變量temp中，

即temp＝node->next;(2)為新節(jié)點(diǎn)申請一個(gè)存儲(chǔ)空間，

newnode

＝(structnode*)malloc(LEN)；(指針變量newnode指向該地址);

鏈表結(jié)點(diǎn)的插入過程：xnwenodeaitemp當(dāng)前第84頁\共有138頁\編于星期六\18點(diǎn)(3)將第i-1個(gè)節(jié)點(diǎn)的指針指向新節(jié)點(diǎn)的地址，

即將新結(jié)點(diǎn)的地址賦給第i-1個(gè)節(jié)點(diǎn)指針

node->next中，即node->next=newnode

(4)將新節(jié)點(diǎn)的指針指向第i個(gè)節(jié)點(diǎn)的地址，即將原鏈表中第

i個(gè)節(jié)點(diǎn)的地址值賦給新結(jié)點(diǎn)指針newnode->next中，即newnode->next=tempxai-1xai-1ai當(dāng)前第85頁\共有138頁\編于星期六\18點(diǎn)[例4－9]在下面所建鏈表的第i個(gè)節(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)的程序如下：當(dāng)前第86頁\共有138頁\編于星期六\18點(diǎn)Insert(structlink*node，inti，newdata)/*注意：在調(diào)用之前，應(yīng)將node指向表頭*/{intj=0;structlink*newnode，*temp;

node=head；

/*給新結(jié)點(diǎn)動(dòng)態(tài)分配內(nèi)存*/newnode＝(structlink*)malloc(sizeof(structlink));newnode->data=‘X’;/*給新結(jié)點(diǎn)的數(shù)據(jù)域賦新值*/Wile(node)/*當(dāng)結(jié)點(diǎn)指針非空時(shí)*/{ifj++==i-1/*如果node是第i-1個(gè)結(jié)點(diǎn)*/當(dāng)前第87頁\共有138頁\編于星期六\18點(diǎn){/*將第i個(gè)結(jié)點(diǎn)地址存放在temp中*/temp=node->next;

/*將第i-1結(jié)點(diǎn)指針指向新節(jié)點(diǎn)的地址*/node->next=newnode；

/*新結(jié)點(diǎn)的指針指向第i個(gè)節(jié)點(diǎn)的地址*/newnode->next=temp；

return;}node=node->next;/*結(jié)點(diǎn)指針指向下一結(jié)點(diǎn)*/}}當(dāng)前第88頁\共有138頁\編于星期六\18點(diǎn)注意

(1)本節(jié)僅描述在某結(jié)點(diǎn)后插入，若想在某結(jié)點(diǎn)之前插入，怎么做？？。

(2)在插入操作中，多增加了兩個(gè)結(jié)構(gòu)指針變量newnode，temp當(dāng)前第89頁\共有138頁\編于星期六\18點(diǎn)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)順序結(jié)構(gòu)存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰，即邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是統(tǒng)一的，要求內(nèi)存中存儲(chǔ)單元的地址必須是連續(xù)的。優(yōu)點(diǎn)：一般情況下，存儲(chǔ)密度大，存儲(chǔ)空間利用率高。缺點(diǎn)：（1）在做插入和刪除操作時(shí)，需移動(dòng)大量元素；（2）由于難以估計(jì)，必須預(yù)先分配較大的空間，往往使存儲(chǔ)空間不能得到充分利用；（3）表的容量難以擴(kuò)充。當(dāng)前第90頁\共有138頁\編于星期六\18點(diǎn)鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素可隨意存放，所占空間分為兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針。優(yōu)點(diǎn)：插入和刪除元素時(shí)很方便，使用靈活。缺點(diǎn)：存儲(chǔ)密度小，存儲(chǔ)空間利用率低。當(dāng)前第91頁\共有138頁\編于星期六\18點(diǎn)

進(jìn)棧

出棧

棧頂

an

…

a3

a2

棧底

a1

圖4-13-

棧的邏輯結(jié)構(gòu)4.3．棧棧是一種特殊的線性表，它的插入與刪除操作只能在表的一端進(jìn)行。定義:棧頂:

棧底:棧的操作:

允許插入和刪除操作的一端稱為棧頂。

不允許插入和刪除操作的一端稱為棧底。

是按照后進(jìn)先出的原則進(jìn)行的。

4.3.1棧的基本概念當(dāng)前第92頁\共有138頁\編于星期六\18點(diǎn)

進(jìn)棧

出棧

棧頂

an

…

a3

a2

棧底

a1

圖4-13-

棧的邏輯結(jié)構(gòu)

棧的邏輯結(jié)構(gòu)：s=(a1,a2,a3,,…,,ai,…,an)，則a1稱為棧底元素，an為棧頂元素。進(jìn)棧的順序：a1,a2,a3,,…,an

；出棧的順序是：an,an-1,…,a3,a2,a1。特點(diǎn)：后進(jìn)先出(LIFO---LastInFirstOut)。當(dāng)前第93頁\共有138頁\編于星期六\18點(diǎn)當(dāng)前第94頁\共有138頁\編于星期六\18點(diǎn)當(dāng)前第95頁\共有138頁\編于星期六\18點(diǎn)當(dāng)前第96頁\共有138頁\編于星期六\18點(diǎn)當(dāng)前第97頁\共有138頁\編于星期六\18點(diǎn)工程手冊的數(shù)據(jù)處理

設(shè)計(jì)資料的處理方法有以下兩種：

(1)程序化。即在應(yīng)用程序內(nèi)部對這些數(shù)表及線圖進(jìn)行查表、處理或計(jì)算。具體處理方法有兩種，第一種數(shù)組化:將數(shù)表中的數(shù)據(jù)或線圖經(jīng)離散化后存入一維、二維或三維數(shù)組，用查表、插值等方法檢索所需數(shù)據(jù)；第二種公式化:將數(shù)表或線圖擬合成公式，編入程序計(jì)算出所需數(shù)據(jù)。

(2)數(shù)據(jù)庫存儲(chǔ)。將數(shù)表及線圖(經(jīng)離散化)中的數(shù)據(jù)按數(shù)據(jù)庫中的規(guī)定進(jìn)行文件結(jié)構(gòu)化，如確定文件名、字段名、字段類型、字段寬度等，存放在數(shù)據(jù)庫中，數(shù)據(jù)獨(dú)立于應(yīng)用程序，但又能為所有應(yīng)用程序提供服務(wù)。當(dāng)前第98頁\共有138頁\編于星期六\18點(diǎn)3．1數(shù)表的程序化3．1數(shù)表的程序化

公式化:適用數(shù)表有精確的計(jì)算公式找到原來的理論計(jì)算公式或經(jīng)驗(yàn)公式，編入應(yīng)用程序

程序化:本來就無表達(dá)公式，或一時(shí)難以找到原來公式，在設(shè)計(jì)手冊或規(guī)范中，有各種形式的數(shù)表，從函數(shù)角度看，有單變量表，也有雙變量及多變量表。當(dāng)前第99頁\共有138頁\編于星期六\18點(diǎn)3．1．1六個(gè)實(shí)例1．普通V帶型號及截面尺寸(見表3—1)

此表查表時(shí)，只有一個(gè)自變量，即型號，且為非數(shù)值型，查得的函數(shù)值為V帶的頂寬、帶高等，均為離散型實(shí)型數(shù)。程序化時(shí)可定義3個(gè)一維數(shù)組，并將表中數(shù)值填寫在程序中使數(shù)組初始化，再定義一個(gè)整型變量i代表型號以此類推。如用戶給定i=2(即A型)，則程序可立即查出b[2]=13.0，h[2]=8.0，bp[2]=11.0．當(dāng)前第100頁\共有138頁\編于星期六\18點(diǎn)IntI;floatb[7]={6.0．10.13.0．17.0，22.0，32.0，38.0}；

floath[7]={4.0．6.0，8.0，10.5，13.5，19.0，23.5}；

floatbp[7]={5.3．8.5，11.0，14.0，19.0，27.0·32.0}；當(dāng)前第101頁\共有138頁\編于星期六\18點(diǎn)2．平鍵和鍵槽的剖面尺寸當(dāng)前第102頁\共有138頁\編于星期六\18點(diǎn)2．平鍵和鍵槽的剖面尺寸

查表時(shí)，根據(jù)設(shè)計(jì)中計(jì)算出來的直徑dgiven

，決定它位于表3—2軸徑的哪個(gè)范圍內(nèi)，由此查出b，h，t，t1的值。軸徑D是一個(gè)數(shù)值范圍，編程時(shí)可將它的上限或下限記入一維數(shù)組內(nèi)，表中其余列的值也放入各自的一維數(shù)組內(nèi)。當(dāng)前第103頁\共有138頁\編于星期六\18點(diǎn)Int1；floatdgiven．h，h，t．Tl；／*driven為已知軸徑*／float：D[12]一·{10．0．12．O，…，75．0，85．0)；／*float：kb[112]一{3．0，4．0，…，20．O，22．O}；／*floatkh[2]一{3．0，4．O，·一，12．O，14．0)；／*存放表中D的上}存放表中6值*／存放表中^值*／當(dāng)前第104頁\共有138頁\編于星期六\18點(diǎn)當(dāng)前第105頁\共有138頁\編于星期六\18點(diǎn)3．包角影響系數(shù)K2(見表3—3)3．包角影響系數(shù)K2(見表3—3)

查表時(shí)根據(jù)a查K2值，a和K2、均為數(shù)值型，可設(shè)計(jì)兩個(gè)一維數(shù)組來實(shí)現(xiàn)。但因計(jì)算所得的實(shí)際包角a?？赡懿粫?huì)正好是表3—3中所列的a值，自然相應(yīng)的K2值也不會(huì)正好是表中之值，因此要用一元函數(shù)插值求解(后面將敘述)。已知包角值為口1，定義兩個(gè)一維數(shù)組：floataIpha．[1O]={90．O，100．O，…，170．O，180．0)；floatK2[1O]一(O．68，O．74，…，·O．98，1．oo}；調(diào)用一元函數(shù)的插值函數(shù)(見3．1．2節(jié))，即可求出實(shí)際的系數(shù)值。當(dāng)前第106頁\共有138頁\編于星期六\18點(diǎn)4．齒輪傳動(dòng)工況系數(shù)KA(見表3—4)當(dāng)前第107頁\共有138頁\編于星期六\18點(diǎn)決定工況系數(shù)KA值時(shí)有兩個(gè)自變量，即原動(dòng)機(jī)的載荷特性和工作機(jī)的載荷特性，它們原本無數(shù)值概念，現(xiàn)分別定義整型變量主一O～2及歹一O～2代表不同工況，用一個(gè)二維數(shù)組KK(3，3)記錄表中系數(shù)值。因?yàn)楸碇凶宰兞考昂瘮?shù)的值均為離散值，因此查表時(shí)無須插值。有關(guān)變量及數(shù)組的定義如下：

floatKA；／*查得的系數(shù)值*／

inti，j；’

floatKK[3][3]={{1．O，1．25，1．75}，{1．25，1．5，2．O}，{1．5，1．75，2.25}}當(dāng)前第108頁\共有138頁\編于星期六\18點(diǎn)圖3—3齒輪傳動(dòng)工況系數(shù)KA查表流程圖當(dāng)前第109頁\共有138頁\編于星期六\18點(diǎn)表3-5軸肩圓角處理論應(yīng)力集中系數(shù)αα當(dāng)前第110頁\共有138頁\編于星期六\18點(diǎn)

決定系數(shù)αα?xí)r有兩個(gè)自變量，即r／d和D／d，因此這是一個(gè)二維查表問題。將表中系數(shù)αα值記錄在一個(gè)二維數(shù)組AA(6，10)中。這個(gè)查表問題的特殊之處是兩個(gè)自變量及系數(shù)αα均有可能是連續(xù)量，這是因?yàn)橛稍O(shè)計(jì)所得的D，d及r值在一定范圍內(nèi)是隨機(jī)的，因此必須采用二元函數(shù)插值。實(shí)際編程時(shí)，設(shè)已知Dgiven，dgiver，rgiven，再定義及初始化二維數(shù)組AA(6，1O)，調(diào)用二元插值函數(shù)(見3．1．3節(jié))即可求得實(shí)際的αα值。當(dāng)前第111頁\共有138頁\編于星期六\18點(diǎn)當(dāng)前第112頁\共有138頁\編于星期六\18點(diǎn)3.3數(shù)表的公式化處理改寫成為：可見，g(x)是兩個(gè)基本插值多項(xiàng)式的線性組合。

線性插值

(兩點(diǎn)插值）X

x1x2x3……….xn

Y

y1y2y3……….yn

列表函數(shù)當(dāng)前第113頁\共有138頁\編于星期六\18點(diǎn)

線性插值C語言函數(shù)程序floatinter(floatx,floatx1,floatx2,floaty1,floaty2){floaty;y=y1+(y2-y1)/(x2-x1)*(x-x1);return(y);}當(dāng)前第114頁\共有138頁\編于星期六\18點(diǎn)拋物線插值（三點(diǎn)插值）

當(dāng)前第115頁\共有138頁\編于星期六\18點(diǎn)拋物線插值（三點(diǎn)插值）

當(dāng)前第116頁\共有138頁\編于星期六\18點(diǎn)拉格朗日插值（多點(diǎn)插值）當(dāng)前第117頁\共有138頁\編于星期六\18點(diǎn)3.3.3函數(shù)擬合

：函數(shù)插值存在的不足：①嚴(yán)格通過每個(gè)結(jié)點(diǎn)，復(fù)印了原有的結(jié)點(diǎn)誤差；②仍需將各結(jié)點(diǎn)數(shù)據(jù)進(jìn)行存貯，占用存貯空間。函數(shù)擬合:曲線不要求通過已知結(jié)點(diǎn)，僅反映數(shù)據(jù)變化趨勢。1

、拉格朗日插值曲線2、函數(shù)擬合曲線當(dāng)前第118頁\共有138頁\編于星期六\18點(diǎn)最小二乘法函數(shù)擬合：曲線到各結(jié)點(diǎn)誤差平方和最小。步驟：

1）在坐標(biāo)紙上繪出各結(jié)點(diǎn)，根據(jù)其趨勢繪制曲線圖形；

2）確定近似函數(shù)，可為多項(xiàng)式、對數(shù)函數(shù)或指數(shù)函數(shù)等；

3）用最小二乘法求出待定系數(shù)。誤差函數(shù)：求導(dǎo)數(shù)：解方程求得方程系數(shù)a,b:例：直線段f(x)=a+bx的擬合：當(dāng)前第119頁\共有138頁\編于星期六\18點(diǎn)指數(shù)函數(shù)最小二乘法擬合：

y=abx

對上式兩邊取對數(shù)，轉(zhuǎn)化為線性函數(shù)：

lgy=lga+xlgb令:y’=lgy,u=lga,v=lgb，則：

y’=u+vx求出線性方程系數(shù)u和v，再根據(jù)u,v求出a和b，可得:

y=abx當(dāng)前第120頁\共有138頁\編于星期六\18點(diǎn)3.4

數(shù)據(jù)庫在CAD/CAM作業(yè)中的應(yīng)用

VisualFoxPro數(shù)據(jù)庫管理系統(tǒng)

是一種關(guān)系型模式，為目前應(yīng)用最廣泛的微機(jī)型系統(tǒng)，被稱之為大眾型數(shù)據(jù)庫管理系統(tǒng)；提供友好的集成環(huán)境，具有Windows窗口功能；可通過系統(tǒng)菜單、工具條或命令窗口進(jìn)行數(shù)據(jù)庫的創(chuàng)建、維護(hù)和各種應(yīng)用操作，包括數(shù)據(jù)記錄的輸入、修改、插入、刪除、剪切、拷貝、粘貼等作。有較強(qiáng)的數(shù)據(jù)管理功能、豐富的開發(fā)工具，用戶可利用編輯器、設(shè)計(jì)器、項(xiàng)目管理器等工具，開發(fā)功能齊全的應(yīng)用程序。當(dāng)前第121頁\共有138頁\編于星期六\18點(diǎn)FoxPro數(shù)據(jù)類型

—字符型(character)：用于表示包括漢字和各類字符在內(nèi)的字符型變量數(shù)值，一個(gè)字符占用一個(gè)字節(jié)，字符型變量最多為254個(gè)字節(jié)。

—數(shù)字型(numeral)：用于表示包括正號、負(fù)號、小數(shù)點(diǎn)及0-9的數(shù)字型變量的數(shù)值，占用8個(gè)字節(jié)的內(nèi)存。

—日期型(Data)：用于表示月、日、年的日期型變量的數(shù)值，占8個(gè)字節(jié)。

—邏輯型(logical)：用于表示由邏輯真或邏輯假構(gòu)成的邏輯型變量的數(shù)值，只用1個(gè)字節(jié)。

—備注型（Memory）：用于存放由可變長度的ASCⅡ碼組成的字段的數(shù)值，用10字節(jié)引用備注文件。

—貨幣型（Current）：用于表示貨幣值的變量數(shù)值，占用8個(gè)字節(jié)。

—

通用型（General）：用于存放OLE對象的數(shù)值，占用10字節(jié)。

當(dāng)前第122頁\共有138頁\編于星期六\18點(diǎn)數(shù)據(jù)庫的應(yīng)用實(shí)例

支承塊（GB2235-80）數(shù)據(jù)庫表文件當(dāng)前第123頁\共有138頁\編于星期六\18點(diǎn)數(shù)據(jù)庫的應(yīng)用實(shí)例

表3-9深溝球軸承輕（2）系列軸承型號尺寸/mm安裝尺寸mm額定動(dòng)負(fù)荷kN額定靜負(fù)荷kN極限轉(zhuǎn)速r/minDDBD1D32001030915254.702.702600020112321017274.802.702400020215351120306.003.552200020317401222357.504.5020000204204714264110.006.3018000205255215314611.007.1016000206306216365615.2010.2013000207357217426520.1013.9011000208408018477325.6018.1010000209458519527825.6018.109000210509020578327.5020.208500

深溝球軸承當(dāng)前第124頁\共有138頁\編于星期六\18點(diǎn)數(shù)據(jù)庫結(jié)構(gòu)定義：數(shù)據(jù)記錄輸入：

APPEND

或：EDIT

或：BROWSE軸承型號：內(nèi)徑d:外徑D：寬度B：軸肩D1：孔徑D3：動(dòng)負(fù)荷：當(dāng)前第125頁\共有138頁\編于星期六\18點(diǎn)當(dāng)前第126頁\共有138頁\編于星期六\18點(diǎn)當(dāng)前第127頁\共有138頁\編于星期六\18點(diǎn)當(dāng)前第128頁\共有138頁\編于星期六\18點(diǎn)當(dāng)前第129頁\共有138頁\編于星期六\18點(diǎn)3·1．2一元函數(shù)的插值設(shè)有一用數(shù)據(jù)表格給出的列表函數(shù)y--f(x)，如表3—7所示。表3·7列表函數(shù)由于列表函數(shù)只能給出結(jié)點(diǎn)z·，z2，…，z"處的函數(shù)值y。，y2，…'Yn當(dāng)自變量為結(jié)點(diǎn)的中間值時(shí)，就要用插值法求取其函數(shù)值。插值法的基本思想是在插值點(diǎn)附近選取幾個(gè)合適的結(jié)點(diǎn)，過這些選取的點(diǎn)構(gòu)造一個(gè)簡單函數(shù)g(z)，在此小段上用g(z)代替原來函數(shù)廠(z)，這樣插值點(diǎn)的函數(shù)值就用g(z)的值來代替。因此，插值的實(shí)質(zhì)問題是如何構(gòu)造一個(gè)既簡單又具有足夠精度的函數(shù)g(z)。當(dāng)前第130頁\共有138頁\編于星期六\18點(diǎn)

條件是給定z，求其函數(shù)值Y。由圖3—4可知，步驟如下：圖3—4線性插值示意圖

(1)選取網(wǎng)個(gè)相鄰自變量Xi與zH1，滿足條件zi<z<zi+l；

(2)過(zi，Yi)及(zm，Yi+·)兩點(diǎn)連直線參(z)代替原來的函數(shù)廠(z)，則y為了一警(x--x,)+yi(3—1)

。Zi+1一Zi’。，為了與后面拋物線插值的公式在形式上取得一致，可將公式(3—1)改寫成．(3-2)當(dāng)前第131頁\共有138頁\編于星期六\18點(diǎn)從圖3—4可以看出，這種插值存在一定誤差，但當(dāng)表格中自變量間隔較小，而插值精度又不要求很高時(shí)，是可以滿足使用要求的。線性插值程序的流程圖見圖3—5。符號說明如下：

z(行)，y(咒)——一維數(shù)組，存放列表函數(shù)中z，了值；九——列表函數(shù)中結(jié)點(diǎn)數(shù)；

z咖en，ygiven——已知的z插入值及求出的函數(shù)值。．．藉讀者注意，C語言中一維數(shù)組下標(biāo)是從0開始的，但圖3—5中的下標(biāo)均從1開始，最簡單的辦法是在定義C語言數(shù)組時(shí)，設(shè)其體積為以+1，而對下標(biāo)為0的數(shù)組元素不使用就是了。當(dāng)前第132頁\共有138頁\編于星期六\18點(diǎn)廠(z)上取三點(diǎn)，過三點(diǎn)作拋物線g(z)，以g(z)替代廠(z)，顯然可以獲得比線性插值精度好的結(jié)果，