機(jī)械CAD中常用的數(shù)據(jù)結(jié)構(gòu)

第五章機(jī)械CAD中常用的數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)內(nèi)容：CAD中數(shù)據(jù)結(jié)構(gòu)線(xiàn)性表?xiàng)?shù)二叉樹(shù)5.1基本概念在數(shù)據(jù)處理中，現(xiàn)實(shí)世界－－－－→

信息世界－－－→

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

定義：數(shù)據(jù)的邏輯結(jié)構(gòu)描述的是數(shù)據(jù)之間的邏輯關(guān)系、它從客觀的角度組織和表達(dá)數(shù)據(jù)。數(shù)據(jù)的物理結(jié)構(gòu)定義:

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

（3，6，10，14，18，...）5.2線(xiàn)性表1.線(xiàn)性表的邏輯結(jié)構(gòu)5.2線(xiàn)性表2.線(xiàn)性表的物理結(jié)構(gòu)（1）順序存儲(chǔ)（2）鏈?zhǔn)酱鎯?chǔ)1）單向鏈2）雙向鏈3）多向鏈5.2線(xiàn)性表（1）線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)定義:

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

特點(diǎn)：1）有序性2）均勻性5.2線(xiàn)性表線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)的運(yùn)算：（1）建表staticcharlistc[6]={‘A’,’B’,’C’,’D’,’E’};（2）訪(fǎng)問(wèn)charc;C=listc[2];（3）修改listc[2]=‘T’;（4）刪除（5）插入5.2線(xiàn)性表特點(diǎn)：1）存儲(chǔ)單元少，簡(jiǎn)單易行，結(jié)構(gòu)緊湊。2）數(shù)據(jù)結(jié)構(gòu)缺乏柔性，若要增刪數(shù)據(jù)，必須重新分配存儲(chǔ)單元。應(yīng)用：查詢(xún)頻繁，修改、補(bǔ)充、刪除數(shù)據(jù)量小的場(chǎng)合。5.2線(xiàn)性表（2）線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

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

一個(gè)數(shù)據(jù)元素項(xiàng)由兩個(gè)字段組成

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

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

存放直接后繼或直接前驅(qū)的域稱(chēng)為指針域(point)。指針域中存儲(chǔ)的信息稱(chēng)作指針。5.2線(xiàn)性表存儲(chǔ)結(jié)構(gòu)可獨(dú)立于邏輯結(jié)構(gòu)。

存儲(chǔ)的物理順序不必與邏輯順序一致而仍能按邏輯要求存取數(shù)據(jù)。特點(diǎn)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在不改變?cè)瓉?lái)存儲(chǔ)結(jié)構(gòu)的條件下，增刪記錄十分方便，只要控制指針即可。根據(jù)指針的數(shù)目，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有三種類(lèi)型：?jiǎn)蜗蜴溄Y(jié)構(gòu)

雙向鏈結(jié)構(gòu)多向鏈結(jié)構(gòu)5.2線(xiàn)性表正向鏈：連接方向與邏輯順序相同反向鏈：連接方向與邏輯順序相反R1R2R3R4R5反向鏈單向鏈結(jié)構(gòu)

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

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

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

(structnode*)malloc(sizeof(structnode))5.2線(xiàn)性表

在鏈表建立過(guò)程中,首先要建立第-個(gè)結(jié)點(diǎn),然后不斷地在其尾部增加新結(jié)點(diǎn),直到不需再有新結(jié)點(diǎn),即尾指針指向NULL為止。設(shè)有結(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)的地址。鏈表的建立鏈表建立的步驟：第-步：建立第-個(gè)結(jié)點(diǎn)structnode{intdata;structnode*next;};structnode*p,*p1,*head;head=p1=p=(structnode*)malloc(sizeof(structnode);datanextheadp,p1第-結(jié)點(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鏈表建立的步驟：第三步：將第-個(gè)結(jié)點(diǎn)與第二個(gè)結(jié)點(diǎn)連接起來(lái)p1-＞next=p;10nextnextdata第-結(jié)點(diǎn)第二結(jié)點(diǎn)headp1p鏈表建立的步驟：第四步：產(chǎn)生第三個(gè)結(jié)點(diǎn)p1=p;scanf(“%d”,&p->data);/*輸入8*/p=(structnode*)malloc(sizeof(structnode);

以后步驟都是重復(fù)第三、四步,直到給出-個(gè)結(jié)束條件,不再建新的結(jié)點(diǎn)時(shí),要有p->next＝NULL；它表示尾結(jié)點(diǎn)。

鏈表建立的步驟：[例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)；/*頭結(jié)點(diǎn)的數(shù)據(jù)成員*/while(p->data!＝0)/*給出0結(jié)束條件,退出循環(huán)*/{p1＝p；p＝(structnode*)malloc(LEN)；scanf(”％d”,&p->data)；

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

/*中間結(jié)點(diǎn)的指針成員值*/

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

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

p＝head；

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

【結(jié)果】

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

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

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

因此，在單鏈表中第i個(gè)結(jié)點(diǎn)之前進(jìn)行插入的基本操作為:

找到線(xiàn)性表中第i-1個(gè)結(jié)點(diǎn)，然后修改其指向后繼的指針。

可見(jiàn)，在鏈表中插入結(jié)點(diǎn)只需要修改指針。但同時(shí)，若要在第i個(gè)結(jié)點(diǎn)之前插入元素，修改的是第i-1個(gè)結(jié)點(diǎn)的指針。鏈表插入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時(shí)，如何修改程序鏈表插入s=(NODE*malloc(sizeof(NODE));

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

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)在鏈表中的實(shí)現(xiàn):有序?qū)?lt;ai-1,ai>和<ai,ai+1>改變?yōu)?lt;ai-1,ai+1>ai-1aiai+1ai-1鏈表結(jié)點(diǎn)刪除

在單鏈表中刪除第

i個(gè)結(jié)點(diǎn)的基本操作為:找到線(xiàn)性表中第i-1個(gè)結(jié)點(diǎn)，修改其指向后繼的指針。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;delete(q);pq鏈表結(jié)點(diǎn)刪除

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

//刪除以head為頭指針(帶頭結(jié)點(diǎn))的單鏈表中第i個(gè)結(jié)點(diǎn)

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

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

return0;//刪除位置不合理雙向鏈結(jié)構(gòu)5.2線(xiàn)性表單鏈表的每個(gè)結(jié)點(diǎn)再增加一個(gè)指向其前趨的指針域prior，這樣形成的鏈表有兩條不同方向的鏈，稱(chēng)之為雙（向）鏈表。特點(diǎn)：雙鏈表一般也由頭指針head唯一確定。每一結(jié)點(diǎn)均有：數(shù)據(jù)域（data)左鏈域（prior)指向前趨結(jié)點(diǎn).右鏈域（next)指向后繼。是一種對(duì)稱(chēng)結(jié)構(gòu)（既有前趨，又有后繼）。L雙鏈表的結(jié)點(diǎn)類(lèi)型描述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é)點(diǎn)q->prior=NULL

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

//p指向新生成的新結(jié)點(diǎn)scanf("%d",&p->data);q->next=p;p->prior=q;q=p;//將p指向的結(jié)點(diǎn)連在鏈表的尾端}q->next=NULL;//鏈表的尾端}雙向鏈建立雙向鏈表的插入在結(jié)點(diǎn)p后面插入一個(gè)新結(jié)點(diǎn)s頭結(jié)點(diǎn)^psq引入一個(gè)指針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個(gè)數(shù)據(jù)元素StatusDuListDelete_L(DuLinkList&L,inti,ElemType&e){if(!(p=GetElemP_Dul(L,i)))returnERROR;//尋找第i-1個(gè)結(jié)點(diǎn)，確定第i個(gè)結(jié)點(diǎn)的指針e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);//釋放空間returnOK;}第i個(gè)結(jié)點(diǎn)p雙向鏈表的插入和刪除在雙向鏈表的給定結(jié)點(diǎn)前插入一結(jié)點(diǎn)。設(shè)p為給定結(jié)點(diǎn)的指針，x為待插入結(jié)點(diǎn)的值，其實(shí)現(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；

}

在雙向鏈表上刪除指定結(jié)點(diǎn)*p。算法如下：

voidDLDelete(DLNode*p)

{//刪除帶頭結(jié)點(diǎn)的雙向鏈表中指定結(jié)點(diǎn)*p

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

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

free(p)；

}

最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)的鏈表.a1a2…...an循環(huán)鏈表和單鏈表的差別僅在于，判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點(diǎn)”。結(jié)構(gòu)中有多個(gè)指針域（多于2個(gè)）應(yīng)用：通常用于矩陣元素、樹(shù)結(jié)構(gòu)存儲(chǔ)，只要查詢(xún)到某一元素，即可獲得相鄰的、相關(guān)元素的地址。R24R12R42R21R22多向鏈結(jié)構(gòu)順序存儲(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ò)充。鏈?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ǔ)空間利用率低。練習(xí)雙向鏈表，某一節(jié)點(diǎn)p，前驅(qū)為prior，后繼為next，在該節(jié)點(diǎn)前插入節(jié)點(diǎn)s，不引入指針，列其數(shù)據(jù)物理結(jié)構(gòu)單向鏈表，某一節(jié)點(diǎn)p，后繼為next，在該節(jié)點(diǎn)后插入節(jié)點(diǎn)s，不引入指針，列其數(shù)據(jù)結(jié)構(gòu)，5.3棧從邏輯結(jié)構(gòu)看，棧是一種特殊的線(xiàn)性表，它的插入與刪除操作只能在表的一端進(jìn)行。定義:棧頂

棧底

棧的操作

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

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

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

棧的示例圖出棧入棧a3a2a1top棧的順序存儲(chǔ)結(jié)構(gòu)(順序棧)

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

#defineMAXSIZE100typedefstruct{intdata[MAXSIZE];inttop;}SeqStack;MaxTop...210stop=0（初始狀態(tài)，棧為空）記錄當(dāng)前堆棧頂端的索引值SeqStacks;s.top=0;MAXSIZE-1base123450?？諚ｍ斨羔榯op,指向?qū)嶋H棧頂后的空位置.top123450進(jìn)棧Atop出棧棧滿(mǎn)BCDEF設(shè)數(shù)組大小為maxsizes.top=0,?？?，此時(shí)出棧，則下溢s.top=maxsize,棧滿(mǎn)，此時(shí)入棧，則上溢toptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？誸opbasebase假設(shè)maxsize＝６順序棧的幾種情況⑴置空棧：首先建立棧空間，然后初始化棧頂指針。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;/*棧滿(mǎn)不能入棧*/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;}

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

2）其它結(jié)點(diǎn)僅有一個(gè)直接前驅(qū)結(jié)點(diǎn)；4）樹(shù)的深度

樹(shù)中結(jié)點(diǎn)的最大層次；4）度

結(jié)點(diǎn)的子樹(shù)的個(gè)數(shù)；5）樹(shù)葉

度數(shù)是0的結(jié)點(diǎn)

樹(shù)的物理結(jié)構(gòu)

鏈?zhǔn)酱鎯?chǔ)，通過(guò)指針來(lái)建立元素間的聯(lián)系和存取路徑。單向鏈結(jié)構(gòu)

存儲(chǔ)結(jié)構(gòu)與邏輯結(jié)構(gòu)不一致，每個(gè)元素只用一個(gè)指針，存取路徑和時(shí)間較長(zhǎng)（不可?。?/p>

AA

BB

KK

FF

CCJJ

EE

GG

DD

HH

MM

II

LL多向鏈結(jié)構(gòu)

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

C

DE

F

G

H

I

JAK

L

M

傳動(dòng)系統(tǒng)圖邏輯結(jié)構(gòu)圖物理結(jié)構(gòu)圖用定長(zhǎng)或不定長(zhǎng)兩種方式描述樹(shù)的結(jié)點(diǎn)。

1.定長(zhǎng)方式以最大度數(shù)結(jié)點(diǎn)的結(jié)構(gòu)作為該樹(shù)的所有結(jié)點(diǎn)的結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)都有相同數(shù)量的子樹(shù)域。a)

定長(zhǎng)方式的結(jié)點(diǎn)

數(shù)據(jù)域

指向直接后繼1的指針

指向直接后繼2的指針

…

指向直接后繼n的指針

c)定長(zhǎng)結(jié)點(diǎn)的鏈表結(jié)構(gòu)

b)樹(shù)結(jié)構(gòu)ABCDEFGHB

E

0

0

D

0

0

0

F

0

0

0

A0

H000

C

0

0G

0

0

0

樹(shù)的存儲(chǔ)結(jié)構(gòu)2.不定長(zhǎng)方式每個(gè)結(jié)點(diǎn)增加一個(gè)存放度數(shù)的域，結(jié)點(diǎn)長(zhǎng)度隨著度數(shù)不同而不同。a)

不定長(zhǎng)結(jié)點(diǎn)

不定長(zhǎng)結(jié)點(diǎn)表示的樹(shù)b