機械CAD中常用的數(shù)據(jù)結構

第五章機械CAD中常用的數(shù)據(jù)結構學習內容：CAD中數(shù)據(jù)結構線性表棧樹二叉樹5.1基本概念在數(shù)據(jù)處理中，現(xiàn)實世界－－－－→

信息世界－－－→

數(shù)據(jù)世界。包含幾個層次概念：個體特征總體事物及其聯(lián)系現(xiàn)實世界實體屬性實體集實體及其聯(lián)系信息世界記錄數(shù)據(jù)項文件數(shù)據(jù)組織（數(shù)據(jù)文件、數(shù)據(jù)庫）計算機世界5.1基本概念數(shù)據(jù)的邏輯結構

定義：數(shù)據(jù)的邏輯結構描述的是數(shù)據(jù)之間的邏輯關系、它從客觀的角度組織和表達數(shù)據(jù)。數(shù)據(jù)的物理結構定義:

是指數(shù)據(jù)在計算機內部的存儲方式，它從物理存儲的角度來描述數(shù)據(jù)以及數(shù)據(jù)間的關系。5.2線性表線性表是一個由n（n≥0）個數(shù)據(jù)元素a1,a2,a3...an組成的有限序列，表中的每一個數(shù)據(jù)元素，除了第一個和最后一個，僅有一個直接前驅和直接后繼。線性表中數(shù)據(jù)元素的個數(shù)定義為線性表的長度。當n=0，稱為空表。例如：光軸軸徑系列值表示成線性表形式：

（3，6，10，14，18，...）5.2線性表1.線性表的邏輯結構5.2線性表2.線性表的物理結構（1）順序存儲（2）鏈式存儲1）單向鏈2）雙向鏈3）多向鏈5.2線性表（1）線性表的順序存儲結構定義:

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

特點：1）有序性2）均勻性5.2線性表線性表順序存儲結構的運算：（1）建表staticcharlistc[6]={‘A’,’B’,’C’,’D’,’E’};（2）訪問charc;C=listc[2];（3）修改listc[2]=‘T’;（4）刪除（5）插入5.2線性表特點：1）存儲單元少，簡單易行，結構緊湊。2）數(shù)據(jù)結構缺乏柔性，若要增刪數(shù)據(jù)，必須重新分配存儲單元。應用：查詢頻繁，修改、補充、刪除數(shù)據(jù)量小的場合。5.2線性表（2）線性表的鏈式存儲結構

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

一個數(shù)據(jù)元素項由兩個字段組成

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

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

存放直接后繼或直接前驅的域稱為指針域(point)。指針域中存儲的信息稱作指針。5.2線性表存儲結構可獨立于邏輯結構。

存儲的物理順序不必與邏輯順序一致而仍能按邏輯要求存取數(shù)據(jù)。特點：鏈式存儲結構在不改變原來存儲結構的條件下，增刪記錄十分方便，只要控制指針即可。根據(jù)指針的數(shù)目，鏈式存儲結構有三種類型：單向鏈結構

雙向鏈結構多向鏈結構5.2線性表正向鏈：連接方向與邏輯順序相同反向鏈：連接方向與邏輯順序相反R1R2R3R4R5反向鏈單向鏈結構

各個數(shù)據(jù)元素由一個指針域和一個數(shù)據(jù)域組成，通過指針構成一個鏈狀結構，且鏈接方向單一。R1R2R3R4R5

-個簡單的單向鏈表的圖示datanext頭指針headdatanext尾指針NULL5.2線性表1）．鏈表是結構、指針相結合的-種應用,它是由頭、中間、尾多個鏈環(huán)組成的單方向可伸縮的鏈表,鏈表上的鏈環(huán)我們稱之為結點。2）．每個結點的數(shù)據(jù)可用-個結構體表示,該結構體由兩部分成員組成：數(shù)據(jù)成員與結構指針變量成員。3）．數(shù)據(jù)成員存放用戶所需數(shù)據(jù),而結構指針變量成員則用來連接(指向)下-個結點,由于每-個結構指針變量成員都指向相同的結構體,所以該指針變量稱為結構指針變量。

5.2線性表4）．鏈表的長度是動態(tài)的,當需要建立-個結點,就向系統(tǒng)申請動態(tài)分配-個存儲空間,如此不斷地有新結點產(chǎn)生,直到結構指針變量指向為空(NULL)。申請動態(tài)分配-個存儲空間的表示形式為：

(structnode*)malloc(sizeof(structnode))5.2線性表

在鏈表建立過程中,首先要建立第-個結點,然后不斷地在其尾部增加新結點,直到不需再有新結點,即尾指針指向NULL為止。設有結構指針變量structnode*p,*p1,*head;

head:用來標志鏈表頭；p:在鏈表建立過程中,p總是不斷先接受系統(tǒng)動態(tài)分配的新結點地址。

p1->next：存儲新結點的地址。鏈表的建立鏈表建立的步驟：第-步：建立第-個結點structnode{intdata;structnode*next;};structnode*p,*p1,*head;head=p1=p=(structnode*)malloc(sizeof(structnode);datanextheadp,p1第-結點第二步：給第-個結點成員data賦值并產(chǎn)生第二個結點scanf(“%d”,&p->data);/*輸入10*/p=(structnode*)malloc(sizeof(structnode);datanextnext10第-結點第二結點headp1p鏈表建立的步驟：第三步：將第-個結點與第二個結點連接起來p1-＞next=p;10nextnextdata第-結點第二結點headp1p鏈表建立的步驟：第四步：產(chǎn)生第三個結點p1=p;scanf(“%d”,&p->data);/*輸入8*/p=(structnode*)malloc(sizeof(structnode);

以后步驟都是重復第三、四步,直到給出-個結束條件,不再建新的結點時,要有p->next＝NULL；它表示尾結點。

鏈表建立的步驟：[例1]建立鏈表

#include<stdio.h>#include<malloc.h>#defineLENsizeof(structnode)structnode{intdata；structnode*next；}；main(){structnode*p,*p1,*head；head＝p＝(structnode*)malloc(LEN)；scanf(“％d”,&p->data)；/*頭結點的數(shù)據(jù)成員*/while(p->data!＝0)/*給出0結束條件,退出循環(huán)*/{p1＝p；p＝(structnode*)malloc(LEN)；scanf(”％d”,&p->data)；

/*中間結點數(shù)據(jù)成員*/p1->next=p；

/*中間結點的指針成員值*/

}p->next＝NULL；/*尾結點的指針成員值*/……}

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

p＝head；

／*鏈表顯示*／printf(”鏈表數(shù)據(jù)成員是：”)；while(p->next!=NULL){printf(”％d”，p->data)；p＝p->next；}printf(”％d＼n”，p->data)；

【結果】

1086420／*建鏈表時輸入的數(shù)據(jù)*／

鏈表數(shù)據(jù)成員是：1086420／*顯示所建的鏈表*／ai-1//插入數(shù)據(jù)元素ListInsert(&L,i,e),第i個節(jié)點前插入數(shù)據(jù)e在單鏈表中的實現(xiàn)：

有序對<ai-1,ai>改變?yōu)?lt;ai-1,e>和<e,ai>eaiai-1鏈表插入

因此，在單鏈表中第i個結點之前進行插入的基本操作為:

找到線性表中第i-1個結點，然后修改其指向后繼的指針。

可見，在鏈表中插入結點只需要修改指針。但同時，若要在第i個結點之前插入元素，修改的是第i-1個結點的指針。鏈表插入intListInsert_L(NODE*head,inti,inte){

}//LinstInsert_Lelse{……}

NODE*p,*s;intj;p=head;j=0;while(p&&j<i-1){p=p->next;j++;}

if(!p||j>i-1)

return0;

p=head->next,如何修改程序？j=1時，如何修改程序鏈表插入s=(NODE*malloc(sizeof(NODE));

//生成新結點if(s==NULL)return0;s->data=e;s->next=p->next;p->next=s;//插入return1;eai-1aiai-1sp鏈表插入鏈表結點的插入意味著要在某結點前或后插入-個或多個結點，所插入的結點必須(1)動態(tài)分配地址p2＝(structnode*)malloc(LEN)；(指針變量p2指向該地址);(2)將原鏈表插入處,后結點p->next取出,存放在指針變量p3中即p3＝p->next;(3)將新結點的地址賦給而原插入處前結點的p->next即p->next＝p2(4)而原插入處后結點的地址值(p3)賦給新結點的p2->next即p2->next＝p3注意(1)本節(jié)僅描述在某結點前插入，若想在某結點之后插入，怎么做？？。(2)在插入操作中，多增加了兩個結構指針變量p2、p3。鏈表結點的插入[例2]在鏈表中插入新結點的程序段。

p＝head；while(p!=NULL){if(p->data==8){p3＝p->next；p2＝(structnode*)malloc(LEN)；scanf(”％d”，&p2->data)；p2->next＝p3；p->next=p2；}}鏈表插入//刪除數(shù)據(jù)元素ListDelete(&L,i,&e)在鏈表中的實現(xiàn):有序對<ai-1,ai>和<ai,ai+1>改變?yōu)?lt;ai-1,ai+1>ai-1aiai+1ai-1鏈表結點刪除

在單鏈表中刪除第

i個結點的基本操作為:找到線性表中第i-1個結點，修改其指向后繼的指針。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;delete(q);pq鏈表結點刪除

intListDelete_L(NODE*head,inti,int*e){

//刪除以head為頭指針(帶頭結點)的單鏈表中第i個結點

}//ListDelete_LNODE*p=head;intj=0;while(p->next&&j<i-1){p=p->next;j++;}

//尋找第i-1個結點，q=p->next;p->next=q->next；e=q->data;free（q）;//刪除并釋放結點return1;if(!(p->next)||j>i-1)

return0;//刪除位置不合理雙向鏈結構5.2線性表單鏈表的每個結點再增加一個指向其前趨的指針域prior，這樣形成的鏈表有兩條不同方向的鏈，稱之為雙（向）鏈表。特點：雙鏈表一般也由頭指針head唯一確定。每一結點均有：數(shù)據(jù)域（data)左鏈域（prior)指向前趨結點.右鏈域（next)指向后繼。是一種對稱結構（既有前趨，又有后繼）。L雙鏈表的結點類型描述Typedefstruct{ElemTypedata;//數(shù)據(jù)域structDuLNode*prior;//前向指針域structDuLNode*next;//后向指針域}DuLNode,*DuLinkList;DuLinkListL,p;L空雙向鏈表Initlist(intn){inti;

DuLNode*p,*q;head=(DuLNode*)malloc(sizeof(DuLNode));q=head;//q指向頭節(jié)點q->prior=NULL

for(i=1;i<=n;i++){p=(NODE*)malloc(sizeof(NODE));

//p指向新生成的新結點scanf("%d",&p->data);q->next=p;p->prior=q;q=p;//將p指向的結點連在鏈表的尾端}q->next=NULL;//鏈表的尾端}雙向鏈建立雙向鏈表的插入在結點p后面插入一個新結點s頭結點^psq引入一個指針qq=p->nexts->next=qq->prior=sp->next=ss->prior=p不引入指針s->next=p->nextp->next->prior=s;p->next=s;s->prior=p雙向鏈表的刪除L雙向鏈表中刪除第i個數(shù)據(jù)元素StatusDuListDelete_L(DuLinkList&L,inti,ElemType&e){if(!(p=GetElemP_Dul(L,i)))returnERROR;//尋找第i-1個結點，確定第i個結點的指針e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);//釋放空間returnOK;}第i個結點p雙向鏈表的插入和刪除在雙向鏈表的給定結點前插入一結點。設p為給定結點的指針，x為待插入結點的值，其實現(xiàn)算法如下：

voidDLInsert(DLNode*p，DataTypex)

{

DLNode*s=(DLNode*)malloc(sizeof(DLNode))；

s->data=x；

s->prior=p->prior；s->next=p；

p->prior->next=s；p->prior=s；

}

在雙向鏈表上刪除指定結點*p。算法如下：

voidDLDelete(DLNode*p)

{//刪除帶頭結點的雙向鏈表中指定結點*p

p->prior->next=p->next：

p->next->prior=p->prior；

free(p)；

}

最后一個結點的指針域的指針又指回第一個結點的鏈表.a1a2…...an循環(huán)鏈表和單鏈表的差別僅在于，判別鏈表中最后一個結點的條件不再是“后繼是否為空”，而是“后繼是否為頭結點”。結構中有多個指針域（多于2個）應用：通常用于矩陣元素、樹結構存儲，只要查詢到某一元素，即可獲得相鄰的、相關元素的地址。R24R12R42R21R22多向鏈結構順序存儲結構和鏈式存儲結構的特點順序結構存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰，即邏輯結構和存儲結構是統(tǒng)一的，要求內存中存儲單元的地址必須是連續(xù)的。

優(yōu)點：一般情況下，存儲密度大，存儲空間利用率高。

缺點：（1）在做插入和刪除操作時，需移動大量元素；（2）由于難以估計，必須預先分配較大的空間，往往使存儲空間不能得到充分利用；（3）表的容量難以擴充。鏈式結構存儲時，相鄰數(shù)據(jù)元素可隨意存放，所占空間分為兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針。

優(yōu)點：插入和刪除元素時很方便，使用靈活。

缺點：存儲密度小，存儲空間利用率低。練習雙向鏈表，某一節(jié)點p，前驅為prior，后繼為next，在該節(jié)點前插入節(jié)點s，不引入指針，列其數(shù)據(jù)物理結構單向鏈表，某一節(jié)點p，后繼為next，在該節(jié)點后插入節(jié)點s，不引入指針，列其數(shù)據(jù)結構，5.3棧從邏輯結構看，棧是一種特殊的線性表，它的插入與刪除操作只能在表的一端進行。定義:棧頂

棧底

棧的操作

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

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

是按照后進先出的原則進行的。

棧的示例圖出棧入棧a3a2a1top棧的順序存儲結構(順序棧)

順序棧:是利用一組地址連續(xù)的存儲單元依次存放從棧底到棧頂?shù)臄?shù)據(jù)元素，通常用一維數(shù)組存放棧的元素。設“指針”top指示棧頂元素的當前位置或后一空位置(下標)。順序棧的類型說明：

#defineMAXSIZE100typedefstruct{intdata[MAXSIZE];inttop;}SeqStack;MaxTop...210stop=0（初始狀態(tài)，棧為空）記錄當前堆棧頂端的索引值SeqStacks;s.top=0;MAXSIZE-1base123450?？諚ｍ斨羔榯op,指向實際棧頂后的空位置.top123450進棧Atop出棧棧滿BCDEF設數(shù)組大小為maxsizes.top=0,?？眨藭r出棧，則下溢s.top=maxsize,棧滿，此時入棧，則上溢toptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？誸opbasebase假設maxsize＝６順序棧的幾種情況⑴置空棧：首先建立?？臻g，然后初始化棧頂指針。SeqStack*SSInitiate(){SeqStack*s;s=(SeqStack*)malloc(sizeof(SeqStack));s->top=0;returns;}⑵判空棧intSSIsEmpty(SeqStack*s){if(s->top==0)return1;elsereturn0;}基本操作算法：

⑶入棧intSSpush(SeqStack*s,ElemTypex){if(s->top==MAXSIZE)return0;/*棧滿不能入棧*/s->data[s->top]=x;s->top++;return1;}

⑷出棧intSSpop(SeqStack*s,ElemType*x){if(s->top==0)return0;/*?？詹荒艹鰲?/

s->top--;

*x=s->data[s->top];return1;}⑸取棧頂元素intSSGetTop(SeqStack*s,int*x){if(s->top==0)return0;/*棧空*/*x=s->data[s->top-1];return1;}

以下幾點說明：1.對于順序棧，入棧時，首先判斷棧是否滿了，棧滿的條件為：s->top==MAXSIZE，棧滿時，不能入棧;否則出現(xiàn)空間溢出，引起錯誤，這種現(xiàn)象稱為上溢。2.出棧和讀棧頂元素操作，先判斷棧是否為空，為空時不能操作，否則產(chǎn)生錯誤。棧的應用傳動系統(tǒng)圖5．4樹與二叉樹（1）樹數(shù)據(jù)之間的關系是層次關系車床零部件關系示意圖車床床身及導軌主軸箱尾座走刀箱溜板箱刀架離合器主軸組件中間變速機構主軸主軸齒輪主軸軸承樹中沒有前驅的結點，且只有一個。樹的邏輯結構特點：1）樹根

2）其它結點僅有一個直接前驅結點；4）樹的深度

樹中結點的最大層次；4）度

結點的子樹的個數(shù)；5）樹葉

度數(shù)是0的結點

樹的物理結構

鏈式存儲，通過指針來建立元素間的聯(lián)系和存取路徑。單向鏈結構

存儲結構與邏輯結構不一致，每個元素只用一個指針，存取路徑和時間較長（不可取）。

AA

BB

KK

FF

CCJJ

EE

GG

DD

HH

MM

II

LL多向鏈結構

存儲方式與邏輯方式一致，各層次的數(shù)據(jù)元素分別按順序連續(xù)存儲在多塊中，層次間的邏輯聯(lián)系用指針實現(xiàn)。當下層數(shù)據(jù)個數(shù)較多時，指針就多，所占存儲單元就多。B

C

DE

F

G

H

I

JAK

L

M

傳動系統(tǒng)圖邏輯結構圖物理結構圖用定長或不定長兩種方式描述樹的結點。

1.定長方式以最大度數(shù)結點的結構作為該樹的所有結點的結構，每個結點都有相同數(shù)量的子樹域。a)

定長方式的結點

數(shù)據(jù)域

指向直接后繼1的指針

指向直接后繼2的指針

…

指向直接后繼n的指針

c)定長結點的鏈表結構

b)樹結構ABCDEFGHB

E

0

0

D

0

0

0

F

0

0

0

A0

H000

C

0

0G

0

0

0

樹的存儲結構2.不定長方式每個結點增加一個存放度數(shù)的域，結點長度隨著度數(shù)不同而不同。a)

不定長結點

不定長結點表示的樹b