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

第四章機(jī)械技術(shù)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)演示文稿現(xiàn)在是1頁(yè)\一共有138頁(yè)\編輯于星期一優(yōu)選第四章機(jī)械技術(shù)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)現(xiàn)在是2頁(yè)\一共有138頁(yè)\編輯于星期一3

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

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

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

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

一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)和組合項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位，數(shù)據(jù)項(xiàng)是對(duì)客觀事物某一方面特性的數(shù)據(jù)描述。現(xiàn)在是6頁(yè)\一共有138頁(yè)\編輯于星期一數(shù)據(jù)項(xiàng)

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

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

數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是指相互之間具有(存在)一定聯(lián)系(關(guān)系)的數(shù)據(jù)元素的集合。現(xiàn)在是9頁(yè)\一共有138頁(yè)\編輯于星期一數(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)稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)或物理結(jié)構(gòu)。數(shù)據(jù)操作：

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

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

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

分別表示某人的名字和電話號(hào)碼。本問(wèn)題是一種典型的表格問(wèn)題。數(shù)據(jù)與數(shù)據(jù)成簡(jiǎn)單的一對(duì)一的線性關(guān)系?，F(xiàn)在是14頁(yè)\一共有138頁(yè)\編輯于星期一例如：線性表的邏輯結(jié)構(gòu)現(xiàn)在是15頁(yè)\一共有138頁(yè)\編輯于星期一樹(shù)狀結(jié)構(gòu)

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

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

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

，數(shù)據(jù)與數(shù)據(jù)成一對(duì)多的關(guān)系，是一種典型的非線性關(guān)系結(jié)構(gòu)—樹(shù)形結(jié)構(gòu)?，F(xiàn)在是18頁(yè)\一共有138頁(yè)\編輯于星期一網(wǎng)狀結(jié)構(gòu)—結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。數(shù)據(jù)元素之間的關(guān)系是一種多元關(guān)系，即多對(duì)多、多對(duì)一。9412631078310584538912345678

910工藝路線方案圖現(xiàn)在是19頁(yè)\一共有138頁(yè)\編輯于星期一例4－3：交通網(wǎng)絡(luò)圖

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

網(wǎng)狀結(jié)構(gòu)現(xiàn)在是20頁(yè)\一共有138頁(yè)\編輯于星期一

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

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

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

定義:

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

現(xiàn)在是21頁(yè)\一共有138頁(yè)\編輯于星期一現(xiàn)在是22頁(yè)\一共有138頁(yè)\編輯于星期一特點(diǎn)：1）存儲(chǔ)單元少，簡(jiǎn)單易行，結(jié)構(gòu)緊湊。

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

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

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

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

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

存放直接后繼或直接前驅(qū)的域稱(chēng)為指針域(point)。指針域中存儲(chǔ)的信息稱(chēng)作指針。（2）鏈接式存儲(chǔ)結(jié)構(gòu)現(xiàn)在是24頁(yè)\一共有138頁(yè)\編輯于星期一

鏈?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現(xiàn)在是25頁(yè)\一共有138頁(yè)\編輯于星期一structlink{charname;structlink*next};現(xiàn)在是26頁(yè)\一共有138頁(yè)\編輯于星期一存儲(chǔ)結(jié)構(gòu)可獨(dú)立于邏輯結(jié)構(gòu)。存儲(chǔ)的物理順序不必與邏輯順序一致而仍能按邏輯要求存取數(shù)據(jù)。特點(diǎn)：鏈接存儲(chǔ)結(jié)構(gòu)在不改變?cè)瓉?lái)存儲(chǔ)結(jié)構(gòu)的條件下，增刪記錄十分方便，只要控制指針即可。根據(jù)指針的數(shù)目，鏈接存儲(chǔ)結(jié)構(gòu)有三種類(lèi)型：?jiǎn)蜗蜴溄Y(jié)構(gòu)

雙向鏈結(jié)構(gòu)多向鏈結(jié)構(gòu)現(xiàn)在是27頁(yè)\一共有138頁(yè)\編輯于星期一在不改變?cè)瓉?lái)存儲(chǔ)結(jié)構(gòu)的條件下，只要控制指針即可R1R2R3R4R5R6鏈接存儲(chǔ)結(jié)構(gòu)的記錄增刪R1R2R3R4R5鏈接存儲(chǔ)結(jié)構(gòu)的記錄增、刪

現(xiàn)在是28頁(yè)\一共有138頁(yè)\編輯于星期一

數(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ì)列樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面現(xiàn)在是29頁(yè)\一共有138頁(yè)\編輯于星期一數(shù)據(jù)的邏輯結(jié)構(gòu)非線性結(jié)構(gòu)集合圖狀結(jié)構(gòu)有向圖無(wú)向圖樹(shù)形結(jié)構(gòu)一般樹(shù)二叉樹(shù)線性結(jié)構(gòu)一般線性表線性表推廣廣義表數(shù)組串受限線性表?xiàng)：完?duì)列圖1-5

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

數(shù)據(jù)對(duì)象可以是有限的，也可以是無(wú)限的?，F(xiàn)在是31頁(yè)\一共有138頁(yè)\編輯于星期一

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

線性表(LinearList)：是由n(n≧0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a1，a2，…an組成的有限序列。該序列中的所有結(jié)點(diǎn)具有相同的數(shù)據(jù)類(lèi)型。其中數(shù)據(jù)元素的個(gè)數(shù)n稱(chēng)為線性表的長(zhǎng)度。當(dāng)n=0時(shí)，稱(chēng)為空表。當(dāng)n>0時(shí)，將非空的線性表記作：(a1，a2，…an)a1稱(chēng)為線性表的第一個(gè)(首)結(jié)點(diǎn)，an稱(chēng)為線性表的最后一個(gè)(尾)結(jié)點(diǎn)。線性表的定義4.2．線性表現(xiàn)在是33頁(yè)\一共有138頁(yè)\編輯于星期一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的直接后繼?，F(xiàn)在是34頁(yè)\一共有138頁(yè)\編輯于星期一線性表邏輯結(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è)抽象的符號(hào)，其具體含義隨具體應(yīng)用的不同而不同。數(shù)據(jù)元素ai可以是一個(gè)數(shù)，可以是一個(gè)符號(hào)，還可以是一個(gè)線性表，甚至是更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。4.2.1線性表的邏輯結(jié)構(gòu)現(xiàn)在是35頁(yè)\一共有138頁(yè)\編輯于星期一線性表中的結(jié)點(diǎn)可以是單值元素(每個(gè)元素只有一個(gè)數(shù)據(jù)項(xiàng))。例:26個(gè)英文字母組成的字母表：(A，B，C、…、Z）光軸軸徑系列值表示成線性表形式:（3，6，10，14，18，20，22，…,90）現(xiàn)在是36頁(yè)\一共有138頁(yè)\編輯于星期一

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

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

(‘2001414102’，‘李利辣’，‘女’，08/12/1984)}現(xiàn)在是37頁(yè)\一共有138頁(yè)\編輯于星期一

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

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

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

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

假設(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)現(xiàn)在是41頁(yè)\一共有138頁(yè)\編輯于星期一線性表的第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ǔ)空間的長(zhǎng)度是相等的。線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)現(xiàn)在是42頁(yè)\一共有138頁(yè)\編輯于星期一2順序表的基本操作

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

建表、查找、修改、插入、刪除、求長(zhǎng)度等。以下將對(duì)幾種主要的操作進(jìn)行討論。1）建表staticcharlistc[6]={‘A’,’B’,’C’,’D’,’E’};2）訪問(wèn)charc;C=listc[2];3）修改listc[2]=‘T’;現(xiàn)在是43頁(yè)\一共有138頁(yè)\編輯于星期一在線性表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)已有元素的類(lèi)型一致；為了保證線性表的有序性，原線性表第i至最后一個(gè)元素要向后移動(dòng)一個(gè)數(shù)據(jù)元素所占存儲(chǔ)空間的長(zhǎng)度?，F(xiàn)在是44頁(yè)\一共有138頁(yè)\編輯于星期一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)線性表長(zhǎng)度加1。[例4-5]

插入一個(gè)數(shù)據(jù)元素ABCDE插入后現(xiàn)在是45頁(yè)\一共有138頁(yè)\編輯于星期一#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;}現(xiàn)在是46頁(yè)\一共有138頁(yè)\編輯于星期一3)順序線性表的刪除現(xiàn)在是47頁(yè)\一共有138頁(yè)\編輯于星期一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)開(kāi)始

Listc[j]=‘\0’;}現(xiàn)在是48頁(yè)\一共有138頁(yè)\編輯于星期一現(xiàn)在是49頁(yè)\一共有138頁(yè)\編輯于星期一現(xiàn)在是50頁(yè)\一共有138頁(yè)\編輯于星期一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ù)域和指針域組成，稱(chēng)為一個(gè)結(jié)點(diǎn)。datanext數(shù)據(jù)域(data)指針域(next)現(xiàn)在是51頁(yè)\一共有138頁(yè)\編輯于星期一4.2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)數(shù)據(jù)元素用指針來(lái)保存其直接前趨或直接后繼的地址，形成環(huán)環(huán)相扣的鏈條，并通過(guò)指針來(lái)逐個(gè)檢索數(shù)據(jù)元素。……...a1a2a3aiai+1annil......a1a2aiai+1an(a1,a2,…ai,ai+1,…an)現(xiàn)在是52頁(yè)\一共有138頁(yè)\編輯于星期一鏈接存儲(chǔ)結(jié)構(gòu)的記錄增、刪

在不改變?cè)瓉?lái)存儲(chǔ)結(jié)構(gòu)的條件下，只要控制指針即可R1R2R3R4R5R6鏈接存儲(chǔ)結(jié)構(gòu)的記錄增刪R1R2R3R4R5現(xiàn)在是53頁(yè)\一共有138頁(yè)\編輯于星期一根據(jù)指針的數(shù)目，鏈接存儲(chǔ)結(jié)構(gòu)有三種類(lèi)型：?jiǎn)蜗蜴溄Y(jié)構(gòu)

雙向鏈結(jié)構(gòu)多向鏈結(jié)構(gòu)現(xiàn)在是54頁(yè)\一共有138頁(yè)\編輯于星期一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ù)域組成，通過(guò)指針構(gòu)成一個(gè)鏈狀結(jié)構(gòu)，且鏈接方向單一。現(xiàn)在是55頁(yè)\一共有138頁(yè)\編輯于星期一頭結(jié)點(diǎn)：數(shù)據(jù)域不存放任何元素，其指針域存放第一個(gè)元素的存儲(chǔ)地址。頭指針：第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址；a1h頭結(jié)點(diǎn)

特點(diǎn)：

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

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

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

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

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

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

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

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

LNode*p;p=(LNode*)malloc(sizeof(LNode));p->data=20;p->next=NULL;p20NULL現(xiàn)在是61頁(yè)\一共有138頁(yè)\編輯于星期一⑵常見(jiàn)的指針操作①q=p;操作前pa……q操作后②q=p->next;bpa……操作前操作后qbpa……③p=p->next;bpa……操作前操作后pba……bpa……現(xiàn)在是62頁(yè)\一共有138頁(yè)\編輯于星期一操作前ypx……bqa…操作后ypx……bqa…④q->next=p;⑤q->next=p->next;操作前ypx……bqa…操作后ypx……bqa…現(xiàn)在是63頁(yè)\一共有138頁(yè)\編輯于星期一

在鏈表建立過(guò)程中，首先要建立第一個(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ù)的類(lèi)型，數(shù)據(jù)域中的數(shù)據(jù)可能只有一個(gè)也可能有多個(gè)，它們的類(lèi)型可以一樣也可以不一樣，存放結(jié)點(diǎn)數(shù)據(jù)元素本身；在指針域（next）中定義指向數(shù)據(jù)結(jié)構(gòu)本身的指針，存放該結(jié)點(diǎn)直接后繼的地址。

4)建立單向鏈表現(xiàn)在是64頁(yè)\一共有138頁(yè)\編輯于星期一定義結(jié)構(gòu)指針變量：

structnode*p,*p1,*head;

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

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

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

(structnode*)malloc(sizeof(structnode))

4)建立單向鏈表現(xiàn)在是65頁(yè)\一共有138頁(yè)\編輯于星期一鏈表建立的步驟：第-步：建立第一個(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);/*申請(qǐng)動(dòng)態(tài)分配一個(gè)存儲(chǔ)地址，為第一個(gè)結(jié)點(diǎn)地址*/dataheadp,p1現(xiàn)在是66頁(yè)\一共有138頁(yè)\編輯于星期一第二步：給第一個(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鏈表建立的步驟：現(xiàn)在是67頁(yè)\一共有138頁(yè)\編輯于星期一第三步：將第一個(gè)結(jié)點(diǎn)與第二個(gè)結(jié)點(diǎn)連接起來(lái)

p1—＞next=p;10nextnextdata第一結(jié)點(diǎn)P1第二結(jié)點(diǎn)Pheadp1p鏈表建立的步驟：現(xiàn)在是68頁(yè)\一共有138頁(yè)\編輯于星期一第四步：給第二個(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)連接起來(lái)

p1—＞next=p;nextdata現(xiàn)在是69頁(yè)\一共有138頁(yè)\編輯于星期一

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

p—>next＝NULL；它表示尾結(jié)點(diǎn)。現(xiàn)在是70頁(yè)\一共有138頁(yè)\編輯于星期一[例4－6]建立鏈表。用C語(yǔ)言建立單向鏈表的程序如下：

#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)；/*申請(qǐng)動(dòng)態(tài)分配一個(gè)存儲(chǔ)地址，為第一個(gè)結(jié)點(diǎn)地址*/scanf(“％d”,&p->data)；/*輸入第一個(gè)結(jié)點(diǎn)的數(shù)據(jù)成員*/現(xiàn)在是71頁(yè)\一共有138頁(yè)\編輯于星期一while(p->data!＝0)/*結(jié)束條件：當(dāng)輸入0時(shí)，退出循環(huán)*/{p1＝p；

p＝(structnode*)malloc(LEN)；/*申請(qǐng)動(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)連接起來(lái)*/

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

……}現(xiàn)在是72頁(yè)\一共有138頁(yè)\編輯于星期一

為了證實(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／*顯示所建的鏈表*／現(xiàn)在是73頁(yè)\一共有138頁(yè)\編輯于星期一打?。簺](méi)找到訪問(wèn)P開(kāi)始輸入iP=head,j=0i=j+1P=P－﹥nextP為空嗎？i=j？返回返回YYNN5)單向鏈表的訪問(wèn)訪問(wèn)單向鏈表的第i個(gè)結(jié)點(diǎn)，應(yīng)從表頭開(kāi)始檢索．根據(jù)指針域的值逐個(gè)查直到找到第i個(gè)結(jié)點(diǎn)?，F(xiàn)在是74頁(yè)\一共有138頁(yè)\編輯于星期一5)單向鏈表的訪問(wèn)[例4－7]對(duì)[例4－1]所建鏈表的第i個(gè)結(jié)點(diǎn)的訪問(wèn)程序如下（注意：在調(diào)用之前，應(yīng)將p指向表頭）：

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

在鏈表中查找是否有指定的數(shù)據(jù)元素，若有就輸出第一次出現(xiàn)這個(gè)數(shù)據(jù)元素的邏輯位置，否則輸出沒(méi)由這個(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)指針?lè)强諘r(shí)*/{if(p—>data＝＝data；return（j）；)/*如果是第j個(gè)結(jié)點(diǎn)*/j++；6）單向鏈表查找現(xiàn)在是77頁(yè)\一共有138頁(yè)\編輯于星期一p＝p－＞next;/*結(jié)點(diǎn)指針指向下一結(jié)點(diǎn)*/}Pritnf(“\n沒(méi)找到該數(shù)據(jù)”);return(0);}現(xiàn)在是78頁(yè)\一共有138頁(yè)\編輯于星期一

在單鏈表中刪除第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）單向鏈表刪除現(xiàn)在是79頁(yè)\一共有138頁(yè)\編輯于星期一[例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)指針?lè)强諘r(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序號(hào)超出范圍”);return;}p->next=q->next;/*將第i-1個(gè)結(jié)點(diǎn)指針指向第i+1個(gè)結(jié)點(diǎn)*/；

delete(q);

return;}現(xiàn)在是80頁(yè)\一共有138頁(yè)\編輯于星期一p＝p－＞next;/*

如果p不是第i-1個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)指針指向下一結(jié)點(diǎn)*/}Pritnf(“\n序號(hào)超出范圍”);return(0);}現(xiàn)在是81頁(yè)\一共有138頁(yè)\編輯于星期一

插入運(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…>現(xiàn)在是82頁(yè)\一共有138頁(yè)\編輯于星期一

插入運(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)?，F(xiàn)在是83頁(yè)\一共有138頁(yè)\編輯于星期一(1)查找到第i-1個(gè)節(jié)點(diǎn)，將第

i

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

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

newnode

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

鏈表結(jié)點(diǎn)的插入過(guò)程：xnwenodeaitemp現(xiàn)在是84頁(yè)\一共有138頁(yè)\編輯于星期一(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現(xiàn)在是85頁(yè)\一共有138頁(yè)\編輯于星期一[例4－9]在下面所建鏈表的第i個(gè)節(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)的程序如下：現(xiàn)在是86頁(yè)\一共有138頁(yè)\編輯于星期一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)指針?lè)强諘r(shí)*/{ifj++==i-1/*如果node是第i-1個(gè)結(jié)點(diǎn)*/現(xiàn)在是87頁(yè)\一共有138頁(yè)\編輯于星期一{/*將第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)*/}}現(xiàn)在是88頁(yè)\一共有138頁(yè)\編輯于星期一注意

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

(2)在插入操作中，多增加了兩個(gè)結(jié)構(gòu)指針變量newnode，temp現(xiàn)在是89頁(yè)\一共有138頁(yè)\編輯于星期一順序存儲(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ò)充。現(xiàn)在是90頁(yè)\一共有138頁(yè)\編輯于星期一鏈?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ǔ)空間利用率低?，F(xiàn)在是91頁(yè)\一共有138頁(yè)\編輯于星期一

進(jìn)棧

出棧

棧頂

an

…

a3

a2

棧底

a1

圖4-13-

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

棧底:棧的操作:

允許插入和刪除操作的一端稱(chēng)為棧頂。

不允許插入和刪除操作的一端稱(chēng)為棧底。

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

4.3.1棧的基本概念現(xiàn)在是92頁(yè)\一共有138頁(yè)\編輯于星期一

進(jìn)棧

出棧

棧頂

an

…

a3

a2

棧底

a1

圖4-13-

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

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

；出棧的順序是：an,an-1,…,a3,a2,a1。特點(diǎn)：后進(jìn)先出(LIFO---LastInFirstOut)?，F(xiàn)在是93頁(yè)\一共有138頁(yè)\編輯于星期一現(xiàn)在是94頁(yè)\一共有138頁(yè)\編輯于星期一現(xiàn)在是95頁(yè)\一共有138頁(yè)\編輯于星期一現(xiàn)在是96頁(yè)\一共有138頁(yè)\編輯于星期一現(xiàn)在是97頁(yè)\一共有138頁(yè)\編輯于星期一工程手冊(cè)的數(shù)據(jù)處理

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

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

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

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

程序化:本來(lái)就無(wú)表達(dá)公式，或一時(shí)難以找到原來(lái)公式，在設(shè)計(jì)手冊(cè)或規(guī)范中，有各種形式的數(shù)表，從函數(shù)角度看，有單變量表，也有雙變量及多變量表?，F(xiàn)在是99頁(yè)\一共有138頁(yè)\編輯于星期一3．1．1六個(gè)實(shí)例1．普通V帶型號(hào)及截面尺寸(見(jiàn)表3—1)

此表查表時(shí)，只有一個(gè)自變量，即型號(hào)，且為非數(shù)值型，查得的函數(shù)值為V帶的頂寬、帶高等，均為離散型實(shí)型數(shù)。程序化時(shí)可定義3個(gè)一維數(shù)組，并將表中數(shù)值填寫(xiě)在程序中使數(shù)組初始化，再定義一個(gè)整型變量i代表型號(hào)以此類(lèi)推。如用戶給定i=2(即A型)，則程序可立即查出b[2]=13.0，h[2]=8.0，bp[2]=11.0．現(xiàn)在是100頁(yè)\一共有138頁(yè)\編輯于星期一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}；現(xiàn)在是101頁(yè)\一共有138頁(yè)\編輯于星期一2．平鍵和鍵槽的剖面尺寸現(xiàn)在是102頁(yè)\一共有138頁(yè)\編輯于星期一2．平鍵和鍵槽的剖面尺寸

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

，決定它位于表3—2軸徑的哪個(gè)范圍內(nèi)，由此查出b，h，t，t1的值。軸徑D是一個(gè)數(shù)值范圍，編程時(shí)可將它的上限或下限記入一維數(shù)組內(nèi)，表中其余列的值也放入各自的一維數(shù)組內(nèi)?，F(xiàn)在是103頁(yè)\一共有138頁(yè)\編輯于星期一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值*／存放表中^值*／現(xiàn)在是104頁(yè)\一共有138頁(yè)\編輯于星期一現(xiàn)在是105頁(yè)\一共有138頁(yè)\編輯于星期一3．包角影響系數(shù)K2(見(jiàn)表3—3)3．包角影響系數(shù)K2(見(jiàn)表3—3)

查表時(shí)根據(jù)a查K2值，a和K2、均為數(shù)值型，可設(shè)計(jì)兩個(gè)一維數(shù)組來(lái)實(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ù)(見(jiàn)3．1．2節(jié))，即可求出實(shí)際的系數(shù)值?，F(xiàn)在是106頁(yè)\一共有138頁(yè)\編輯于星期一4．齒輪傳動(dòng)工況系數(shù)KA(見(jiàn)表3—4)現(xiàn)在是107頁(yè)\一共有138頁(yè)\編輯于星期一決定工況系數(shù)KA值時(shí)有兩個(gè)自變量，即原動(dòng)機(jī)的載荷特性和工作機(jī)的載荷特性，它們?cè)緹o(wú)數(shù)值概念，現(xiàn)分別定義整型變量主一O～2及歹一O～2代表不同工況，用一個(gè)二維數(shù)組KK(3，3)記錄表中系數(shù)值。因?yàn)楸碇凶宰兞考昂瘮?shù)的值均為離散值，因此查表時(shí)無(wú)須插值。有關(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}}現(xiàn)在是108頁(yè)\一共有138頁(yè)\編輯于星期一圖3—3齒輪傳動(dòng)工況系數(shù)KA查表流程圖現(xiàn)在是109頁(yè)\一共有138頁(yè)\編輯于星期一表3-5軸肩圓角處理論應(yīng)力集中系數(shù)αα現(xiàn)在是110頁(yè)\一共有138頁(yè)\編輯于星期一

決定系數(shù)αα?xí)r有兩個(gè)自變量，即r／d和D／d，因此這是一個(gè)二維查表問(wèn)題。將表中系數(shù)αα值記錄在一個(gè)二維數(shù)組AA(6，10)中。這個(gè)查表問(wèn)題的特殊之處是兩個(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ù)(見(jiàn)3．1．3節(jié))即可求得實(shí)際的αα值?，F(xiàn)在是111頁(yè)\一共有138頁(yè)\編輯于星期一現(xiàn)在是112頁(yè)\一共有138頁(yè)\編輯于星期一3.3數(shù)表的公式化處理改寫(xiě)成為：可見(jiàn)，g(x)是兩個(gè)基本插值多項(xiàng)式的線性組合。

線性插值

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

x1x2x3……….xn

Y

y1y2y3……….yn

列表函數(shù)現(xiàn)在是113頁(yè)\一共有138頁(yè)\編輯于星期一

線性插值C語(yǔ)言函數(shù)程序floatinter(floatx,floatx1,floatx2,floaty1,floaty2){floaty;y=y1+(y2-y1)/(x2-x1)*(x-x1);return(y);}現(xiàn)在是114頁(yè)\一共有138頁(yè)\編輯于星期一拋物線插值（三點(diǎn)插值）

現(xiàn)在是115頁(yè)\一共有138頁(yè)\編輯于星期一拋物線插值（三點(diǎn)插值）

現(xiàn)在是116頁(yè)\一共有138頁(yè)\編輯于星期一拉格朗日插值（多點(diǎn)插值）現(xiàn)在是117頁(yè)\一共有138頁(yè)\編輯于星期一3.3.3函數(shù)擬合

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

、拉格朗日插值曲線2、函數(shù)擬合曲線現(xiàn)在是118頁(yè)\一共有138頁(yè)\編輯于星期一最小二乘法函數(shù)擬合：曲線到各結(jié)點(diǎn)誤差平方和最小。步驟：

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

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

3）用最小二乘法求出待定系數(shù)。誤差函數(shù)：求導(dǎo)數(shù)：解方程求得方程系數(shù)a,b:例：直線段f(x)=a+bx的擬合：現(xiàn)在是119頁(yè)\一共有138頁(yè)\編輯于星期一指數(shù)函數(shù)最小二乘法擬合：

y=abx

對(duì)上式兩邊取對(duì)數(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現(xiàn)在是120頁(yè)\一共有138頁(yè)\編輯于星期一3.4

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

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

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

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

—數(shù)字型(numeral)：用于表示包括正號(hào)、負(fù)號(hào)、小數(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）：用于存放由可變長(zhǎng)度的ASCⅡ碼組成的字段的數(shù)值，用10字節(jié)引用備注文件。

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

—

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

現(xiàn)在是122頁(yè)\一共有138頁(yè)\編輯于星期一數(shù)據(jù)庫(kù)的應(yīng)用實(shí)例

支承塊（GB2235-80）數(shù)據(jù)庫(kù)表文件現(xiàn)在是123頁(yè)\一共有138頁(yè)\編輯于星期一數(shù)據(jù)庫(kù)的應(yīng)用實(shí)例

表3-9深溝球軸承輕（2）系列軸承型號(hào)尺寸/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

深溝球軸承現(xiàn)在是124頁(yè)\一共有138頁(yè)\編輯于星期一數(shù)據(jù)庫(kù)結(jié)構(gòu)定義：數(shù)據(jù)記錄輸入：

APPEND

或：EDIT

或：BROWSE軸承型號(hào)：內(nèi)徑d:外徑D：寬度B：軸肩D1：孔徑D3：動(dòng)負(fù)荷：現(xiàn)在是125頁(yè)\一共有138頁(yè)\編輯于星期一現(xiàn)在是126頁(yè)\一共有138頁(yè)\編輯于星期一現(xiàn)在是127頁(yè)\一共有138頁(yè)\編輯于星期一現(xiàn)在是128頁(yè)\一共有138頁(yè)\編輯于星期一現(xiàn)在是129頁(yè)\一共有138頁(yè)\編輯于星期一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)，過(guò)這些選取的點(diǎn)構(gòu)造一個(gè)簡(jiǎn)單函數(shù)g(z)，在此小段上用g(z)代替原來(lái)函數(shù)廠(z)，這樣插值點(diǎn)的函數(shù)值就用g(z)的值來(lái)代替。因此，插值的實(shí)質(zhì)問(wèn)題是如何構(gòu)造一個(gè)既簡(jiǎn)單又具有足夠精度的函數(shù)g(z)?，F(xiàn)在是130頁(yè)\一共有138頁(yè)\編輯于星期一

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

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

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

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

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

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