1.理解和掌握有關(guān)數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念；2.熟練掌握線形表存儲結(jié)構(gòu)和相關(guān)操作方法；3.掌握棧、隊列、樹數(shù)據(jù)結(jié)構(gòu)的運(yùn)算方法。第一節(jié)基本概念第二節(jié)線形表第三節(jié)棧、隊列和數(shù)組第四節(jié)樹結(jié)構(gòu)本章內(nèi)容《機(jī)械CAD/CAM》課程教案教學(xué)目的第二章機(jī)械CAD/CAM常用的數(shù)據(jù)結(jié)構(gòu)第1節(jié)基本概念1.數(shù)據(jù)(data)是對客觀事物的符號表示，是指所有能輸入到計算機(jī)內(nèi)并被計算機(jī)處理的符號的總稱。2.數(shù)據(jù)元素(dataelement)是數(shù)據(jù)的基本單位，是數(shù)據(jù)這個集合中相對獨(dú)立的個體。3.數(shù)據(jù)的邏輯結(jié)構(gòu)(Thelogicalstructureofthedata)是指數(shù)據(jù)之間的邏輯關(guān)系。表學(xué)生成績表學(xué)號姓名計算機(jī)導(dǎo)論高等數(shù)學(xué)大學(xué)物理平均成績1102044401丁一809085851102044402馬二756878741102044403張三908593891102044404李四708486801102044405王五82786675﹍﹍﹍﹍﹍﹍第1節(jié)基本概念4.數(shù)據(jù)的物理結(jié)構(gòu)(Thephysicalstructureofthedata)是數(shù)據(jù)元素和它們之間的關(guān)系在計算機(jī)中的存儲表示。計算機(jī)處理信息的最小單位叫做位(bit)，一個位表示一個二進(jìn)制的數(shù)。若干位的組合形成一個位串(string)

。用一個位串表示一個數(shù)據(jù)元素，稱這樣的位串為一個結(jié)點(node)

。6.數(shù)據(jù)運(yùn)算(dataoperation)是指對數(shù)據(jù)進(jìn)行的各種操作。5.數(shù)據(jù)類型(datatype)是程序設(shè)計語言提供的變量類別。7.數(shù)據(jù)結(jié)構(gòu)(datastructure)數(shù)據(jù)結(jié)構(gòu)非線性結(jié)構(gòu)數(shù)據(jù)存儲結(jié)構(gòu)數(shù)據(jù)運(yùn)算數(shù)據(jù)邏輯結(jié)構(gòu)線性結(jié)構(gòu)線性表隊列棧網(wǎng)狀結(jié)構(gòu)樹結(jié)構(gòu)鏈?zhǔn)酱鎯樞虼鎯Σ迦?，刪除，更新，檢索，排序，數(shù)學(xué)運(yùn)算，……第1節(jié)基本概念是按某種邏輯結(jié)構(gòu)組織起來，按一定的存儲表示方式把組織好的數(shù)據(jù)存儲到計算機(jī)中，并對之定義一系列操作運(yùn)算的數(shù)據(jù)的集合。

第2節(jié)線形表線性表——n(n≥0)個數(shù)據(jù)元素按前驅(qū)后繼關(guān)系排成的有限序列。同一表中的數(shù)據(jù)元素的類型必須相同；除了第一個和最后一個數(shù)據(jù)元素外，每個數(shù)據(jù)元素有且只有一個直接前趨，有且只有一個直接后繼；如工資表、學(xué)生名冊。線性表中數(shù)據(jù)元素的個數(shù)定義為線性表的長度。線性表的順序存儲結(jié)構(gòu)

順序存儲就是用一組連續(xù)的存儲單元，按照數(shù)據(jù)元素的邏輯順序依次存放。

假定每個數(shù)據(jù)元素占用L個存儲單元，每個數(shù)據(jù)元素第1個單元的存儲位置為該數(shù)據(jù)元素的存儲位置，若第1個數(shù)據(jù)元素的存儲化置為b，則第i個數(shù)據(jù)元素的存儲位置為

Loc(ai)＝b十(i—1)×L第2節(jié)線形表第2節(jié)線形表線性表的順序存儲結(jié)構(gòu)特點：1）有序性；2）均勻性。操作：1）建表；

2）訪問；

3）修改；

4）刪除；

5）插入。刪除或插入運(yùn)算時，數(shù)據(jù)移動量大，運(yùn)算時間長。順序表類型定義

#defineListSize100//表空間的大小可根據(jù)實際需要而定，這里假設(shè)為100typedefintDataType;//DataType的類型可根據(jù)實際情況而定，這里假設(shè)為int

typedefstruct{

DataTypedata[ListSize]；//向量data用于存放表結(jié)點

intlength；//當(dāng)前的表長度

}SeqList；

順序表上實現(xiàn)的基本運(yùn)算

（1）表的初始化

voidInitList（SeqList*L）

{\\順序表的初始化即將表的長度置為0

L-＞length=0；

}

（2）求表長

intListLength（SeqList*L）

{\\求表長只需返回L-＞length

returnL-＞length;

}

（3）取表中第i個結(jié)點

DataTypeGetNode（L，i）

{\\取表中第i個結(jié)點只需返回和L-＞data[i-1]即可

if(i<1||i>L-＞length-1)

Error("positionerror")；

returnL-＞data[i-1]；

}

線性表插入運(yùn)算：第2節(jié)線形表線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)特點：1）存儲單元可以不連續(xù)、動態(tài)分配存儲空間；

2）存儲結(jié)點有兩種域：數(shù)據(jù)域、指針域。單向鏈表雙向鏈表循環(huán)鏈表單鏈表類型描述typedefcharDataType;//假設(shè)結(jié)點的數(shù)據(jù)域類型為字符

typedefstructnode{

//結(jié)點類型定義

DataTypedata;

//結(jié)點的數(shù)據(jù)域

structnode*next;//結(jié)點的指針域

}ListNode;

typedefListNode*LinkList;

ListNode*p;

LinkListhead;

①生成結(jié)點變量的標(biāo)準(zhǔn)函數(shù)

p=(ListNode*)malloc(sizeof(ListNode))；

//函數(shù)malloc分配一個類型為ListNode的結(jié)點變量的空間,并將其首地址放入指針變量p中

②釋放結(jié)點變量空間的標(biāo)準(zhǔn)函數(shù)

free(p)；//釋放p所指的結(jié)點變量空間

③結(jié)點分量的訪問

利用結(jié)點變量的名字*p訪問結(jié)點分量

方法一：(*p).data和(*p).next

方法二：p-﹥data和p-﹥next

④指針變量p和結(jié)點變量*p的關(guān)系

指針變量p的值——結(jié)點地址

結(jié)點變量*p的值——結(jié)點內(nèi)容

(*p).data的值——p指針?biāo)附Y(jié)點的data域的值

(*p).next的值——*p后繼結(jié)點的地址

*((*p).next)——*p后繼結(jié)點第2節(jié)線形表單向鏈表的操作操作：1）建表；

2）訪問；

3）修改；

4）刪除；

5）插入。第2節(jié)線形表建表鏈表插入操作運(yùn)算步驟：①申請新結(jié)點存儲空間；②將待插入元素M存放在新增結(jié)點數(shù)據(jù)域；③新增結(jié)點指針鏈接。

第2節(jié)線形表訪問第2節(jié)線形表查找修改刪除插入第2節(jié)線形表雙向鏈表第2節(jié)線形表雙向鏈表的操作1）建表第2節(jié)線形表建表第2節(jié)線形表查找修改刪除插入第2節(jié)線形表鏈?zhǔn)酱鎯ο鄬τ陧樞虼鎯Φ奶攸c：(1)刪除或插入運(yùn)算速度快，因為刪除或插入運(yùn)算過程中數(shù)據(jù)并不移動；(2)無需事先分配存儲空間，以免有些空間不能充分利用；(3)表的容量易于擴(kuò)充；(4)按邏輯順序進(jìn)行查找的速度慢；(5)比相等長度的順序存儲多占用作為指針域的存儲空間。線性表順序存儲與鏈?zhǔn)酱鎯Y(jié)構(gòu)比較順序存儲：優(yōu)點：結(jié)構(gòu)均勻，便于數(shù)據(jù)元素訪問和修改操作；不足：刪除插入大量數(shù)據(jù)元素需移動，運(yùn)算效率低。應(yīng)用：多用于查找頻繁、很少增刪的場合。鏈?zhǔn)酱鎯Γ簝?yōu)點：刪除插入效率高，不需數(shù)據(jù)元素移動，不需事先分配存儲空間，存儲空間利用充分。不足：搜索效率低，需從頭結(jié)點順次搜尋。應(yīng)用－多用于事先難以確定容量，頻繁增、刪場合。第3節(jié)棧、隊列和數(shù)組棧棧的結(jié)構(gòu)(1)棧的邏輯結(jié)構(gòu)

——線形表：后進(jìn)先出(2)棧的存儲結(jié)構(gòu)

——一般采用順序存儲結(jié)構(gòu)

棧的定義

棧(Stack)是限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom).當(dāng)表中沒有元素時稱為空棧。假設(shè)棧S=(a1，a2，a3，…an)，則a1稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，a3，…，an的次序進(jìn)棧，退棧的第一個元素應(yīng)為棧頂元素。換句話說，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧稱為后進(jìn)先出表（LIFO）。棧：限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表.設(shè)棧s=（a1，a2，...,ai，...，an），其中a1是棧底元素，an是棧頂元素。棧頂（top)：允許插入和刪除的一端；棧頂?shù)漠?dāng)前位置由棧頂指針的位置指示器指示。棧底（bottom):不允許插入和刪除的一端。進(jìn)?；蛉霔＃簵５牟迦氩僮鳌３鰲；蛲藯＃簵５膭h除操作。a1a2….an進(jìn)棧出棧棧頂棧底棧的定義空棧：沒有元素的棧棧的特性：先進(jìn)后出（LIFO），即只能在末端（棧頂）進(jìn)行插、刪的操作棧的定義棧中的幾種基本操作：

1.設(shè)置空棧

初始化：initStack(S);清空：emptyStack(S);2.插入一個新的棧頂元素（進(jìn)棧）:push(S,x);3.刪除棧頂元素（出棧）:pop(S);4.讀取棧頂元素:getTop(S);5.判空棧:stackEmpty(S);6.判滿棧:stackFull(S);7.顯示棧中元素：stackTraverse(S);

第3節(jié)棧、隊列和數(shù)組

第3節(jié)棧、隊列和數(shù)組

第3節(jié)棧、隊列和數(shù)組棧的存儲結(jié)構(gòu)順序棧利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用一維數(shù)組表示必須附設(shè)一個位置指針top（棧頂指針）來動態(tài)地指示棧頂元素在順序棧中的位置鏈棧采用鏈表作為存儲結(jié)構(gòu)實現(xiàn)的必須設(shè)置一個棧頂指針永遠(yuǎn)指向棧頂棧的表示和實現(xiàn)一、順序棧

棧的順序存儲結(jié)構(gòu)簡稱為順序棧，它是運(yùn)算受限的線性表。因此，可用數(shù)組來實現(xiàn)順序棧。因為棧底位置是固定不變的,所以可以將棧底位置設(shè)置在數(shù)組的兩端的任何一個端點；棧頂位置是隨著進(jìn)棧和退棧操作而變化的。棧的表示和實現(xiàn)需用一個整型變量top來指示當(dāng)前棧頂?shù)奈恢?，通常稱top為棧頂指針。因此，順序棧的類型定義只需將順序表的類型定義中的長度屬性改為top即可。一、順序棧a1a2top順序棧的結(jié)構(gòu)#defineStack_Size50typedefstruct{StackElemTypeelem[Stack_Size];

/*用一維數(shù)組存放自棧底到棧頂?shù)臄?shù)據(jù)元素*/inttop;/*附設(shè)一個位置指針top*/}SeqStack;一、順序棧

設(shè)S是SeqStack類型的指針變量。若棧底位置在向量的低端，即s–>elem[0]是棧底元素.那么：

進(jìn)棧：s–>top加1；退棧：s–>top減1；

空棧：s–>top<0；棧滿：s–>top=stacksize-1。上溢：當(dāng)棧滿時再做進(jìn)棧運(yùn)算必定產(chǎn)生的空間溢出;下溢：當(dāng)?？諘r再做退棧運(yùn)算產(chǎn)生的溢出。上溢是一種出錯狀態(tài)，應(yīng)該設(shè)法避免之；下溢則可能是正常現(xiàn)象，因為棧在程序中使用時，其初態(tài)或終態(tài)都是空棧，所以下溢常常用來作為程序控制轉(zhuǎn)移的條件。一、順序棧設(shè)數(shù)組S是一個順序棧棧S的最大容量stacksize=4，初始狀態(tài)top=－1

10S[4]2310basetop=top+1s[top]=xtop

10

25

30S[4]2310topbasex=s[top]top=top-1?？?0進(jìn)棧30出棧S[4]2310Top=-1top棧滿top=stacksize-1

10

25

30

40S[4]2310top=3baseS[4]2310Top=-1top進(jìn)棧算法#defineStatck_Size100intPush(SeqStack*S,intx){if(S->top==Stack_Size－1)return0;S->top++;S->elem[S->top]=x;return(1);}a2a3a4987654321a10top一、順序棧進(jìn)棧算法#defineStatck_Size100intPush(SeqStack*S,intx){if(S->top==Stack_Size－1)return(0);

S->top++;S->elem[S->top]=x;return(1);}a2a3a4987654321a10top一、順序棧進(jìn)棧算法#defineStatck_Size100intPush(SeqStack*S,intx){if(S->top==Stack_Size－1)return(0);S->top++;

S->elem[S->top]=x;return(1);}a2a3a4987654321a10topx一、順序棧出棧算法：

intpop(SeqStack*S,StackElementType*x){if(S->top==－1){printf(“stackempty”);return(0);}else{*x=S->elem[S->top];/*返回出棧元素*/S->top--;return(1);}

}通過指針變量x，帶回出棧元素a2a3a4987654321a10top一、順序棧a2a3a4987654321a10topx出棧算法：

intpop(SeqStack*S,StackElementType*x){if(S->top==－1){printf(“stackempty”);return(0);}else{

*x=S->elem[S->top];/*返回出棧元素*/

S->top--;return(1);}

}一、順序棧為兩個棧申請一個共享的一維數(shù)組空間S[M]將兩個棧的棧底分別放在一維數(shù)組的兩端，分別是0，M－1a1a2a3b5b4b3b2b10M－1top[0]top[1]一、順序棧順序棧的共享共享棧的結(jié)構(gòu)定義a1a2a3b5b4b3b2b10M－1top[0]top[1]#defineM100typedefstruct{StackElementTypeelem[M];inttop[2];}DqStack;一、順序棧a1a2a3b5b4b3b2b10M－1top[0]top[1]判空：

top[0]=-1; top[1]=M;判滿：

top[0]+1==top[1];共享棧的操作共享棧的進(jìn)棧操作intPush(DqStack*S,StackElementTypex,inti){if(S->top[0]+1==S->top[1])return(0);switch(i){case0:S->top[0]++;S->elem[S->top[0]]=x;break;case1:S->top[1]++;S->elem[S->top[1]]=x;break;default:return(0);}return(1);}共享棧的出棧操作intPop(DqStack*S,StackElementType*x,inti){switch(i){case0:if(S->top[0]==-1)return(0);*x=S->elem[S->top[0]];S->top[0]--;break;case1:if(S->top[1]==M)return(0);*x=S->elem[S->top[1]];S->top[1]--;break;default:return(0);}return(1);}二、鏈棧

棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈棧，它是運(yùn)算受限的單鏈表，插入和刪除操作僅限制在表頭位置上進(jìn)行.由于只能在鏈表頭部進(jìn)行操作，故鏈表沒有必要像單鏈表那樣附加頭結(jié)點。棧頂指針就是鏈表的頭指針。

a1

an∧top棧底

用指針來實現(xiàn)的棧叫鏈棧。棧的容量事先不能估計時采用這種存儲結(jié)構(gòu)。鏈棧的類型說明如下：typedefstructLnode{intdata；structLnode

next；}Lnode，

LinkStack；top頭指針永遠(yuǎn)指向頭結(jié)點二、鏈棧進(jìn)棧算法intPush(LinkStacktop,StackElementTypee){Lnode*p;p=(LinkStack)malloc(sizeof(Lnode));p->data=e;p->next=top->next;top->next=p;return(1);}a1a2an∧basetop棧s進(jìn)棧元素e二、鏈棧進(jìn)棧算法intPush(LinkStacktop,StackElementTypee){Lnode*p;

p=(LinkStack)malloc(sizeof(Lnode));p->data=e;p->next=top->next;top->next=p;return(1);}

Pa1a2an∧basetop二、鏈棧進(jìn)棧算法intPush(LinkStacktop,StackElementTypee){Lnode*p;p=(LinkStack)malloc(sizeof(Lnode));p->data=e;p->next=top->next;top->next=p;return(1);}

ePa1a2an∧basetop二、鏈棧進(jìn)棧算法intPush(LinkStacktop,StackElementTypee){Lnode*p;p=(LinkStack)malloc(sizeof(Lnode));p->data=e;p->next=top->next;top->next=p;return(1);}

ePa1a2an∧basetop進(jìn)棧算法intPush(LinkStacktop,StackElementTypee){Lnode*p;p=(LinkStack)malloc(sizeof(Lnode));p->data=e;

p->next=top->next;

top->next=p;return(1);}

ePa1a2an∧basetop二、鏈棧出棧算法intPop(LinkStacktop,StackElementType*x){Lnode*temp;temp=top->next;if(temp==NULL)return(0);top->next=temp->next;*x=temp->data;free(temp);}棧s指針變量帶回出棧元素的值a1a2an∧basetop二、鏈棧tempa1a2an∧basetop出棧算法intPop(LinkStacktop,StackElementType*x){Lnode*temp;

temp=top->next;if(temp==NULL)return(0);top->next=temp->next;*x=temp->data;free(temp);}二、鏈棧tempa1a2an∧basetop出棧算法intPop(LinkStacktop,StackElementType*x){Lnode*temp;temp=top->next;if(temp==NULL)return(0);

top->next=temp->next;*x=temp->data;free(temp);}二、鏈棧tempa1a2an∧basetop出棧算法intPop(LinkStacktop,StackElementType*x){Lnode*temp;temp=top->next;if(temp==NULL)return(0);top->next=temp->next;*x=temp->data;free(temp);}xa1二、鏈棧tempa1a2an∧basetop出棧算法intPop(LinkStacktop,StackElementType*x){Lnode*temp;temp=top->next;if(temp==NULL)return(0);top->next=temp->next;*x=temp->data;free(temp);}xa1二、鏈棧隊列(Queue)也是一種運(yùn)算受限的線性表。它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪除的一端稱為隊頭(front)，允許插入的一端稱為隊尾(rear)。例如：排隊購物。操作系統(tǒng)中的作業(yè)排隊。先進(jìn)入隊列的成員總是先離開隊列。因此隊列亦稱作先進(jìn)先出(FirstInFirstOut)的線性表，簡稱FIFO表。當(dāng)隊列中沒有元素時稱為空隊列。在空隊列中依次加入元素a1,a2,…an之后，a1是隊頭元素，an是隊尾元素。顯然退出隊列的次序也只能是a1,a2,…an，也就是說隊列的修改是依先進(jìn)先出的原則進(jìn)行的。2.3隊列的定義隊列（Queue）：限定在表一端插入，在另一端刪除的“先進(jìn)先出”線性表。a1a2……ak……an-1an入隊出隊隊列數(shù)據(jù)結(jié)構(gòu)循環(huán)隊列第3節(jié)棧、隊列和數(shù)組

第3節(jié)棧、隊列和數(shù)組隊列

第3節(jié)棧、隊列和數(shù)組隊列尾追頭為滿頭追尾為空尾指‘+1’判斷下圖是隊列的示意圖：出隊入隊隊頭隊尾a1a2…an

隊尾：在隊列中，允許插入的一端隊頭：在隊列中，允許刪除的一端隊列的主要運(yùn)算設(shè)置一個空隊列；插入一個新的隊尾元素，稱為進(jìn)隊；刪除隊頭元素，稱為出隊；讀取隊頭元素；等2.3隊列的定義隊列的存儲結(jié)構(gòu)（1）順序存儲結(jié)構(gòu)(a)線性隊列(b)循環(huán)隊列（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)隊列的表示和實現(xiàn)隊列的類型定義：#defineMAXSIZE50typedefstruct{QueueElementTypeelem[MAXSIZE];intfront;intrear;}SeqQueue;e1,e2出隊，e4入隊隊滿e1e2e3

(b)rearfronte1,e2,e3入隊隊空時，令rear=front=0，當(dāng)有新元素入隊時，尾指針加1，當(dāng)有元素出隊時，頭指針加1。故在非空隊列中，頭指針始終指向隊頭元素的位置，而尾指針始終指向隊尾元素后一個位置rear=front=0(隊空)front

3210(a)rearrear=4(c)e3e4front隊列的順序存儲和棧類似，隊列中亦有上溢和下溢現(xiàn)象。此外，順序隊列中還存在“假上溢”（假溢出）現(xiàn)象。因為在入隊和出隊的操作中，頭尾指針只增加不減小，致使被刪除元素的空間永遠(yuǎn)無法重新利用。因此，盡管隊列中實際的元素個數(shù)遠(yuǎn)遠(yuǎn)小于向量空間的規(guī)模，但也可能由于尾指針?biāo)瘸鱿蛄靠臻g的上界而不能做入隊操作。該現(xiàn)象稱為假上溢。隊列的順序存儲為充分利用向量空間?？朔鲜黾偕弦绗F(xiàn)象的方法是將向量空間想象為一個首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量，存儲在其中的隊列稱為循環(huán)隊列CircularQueue)。在循環(huán)隊列中進(jìn)行出隊、入隊操作時，頭尾指針仍要加1，朝前移動。只不過當(dāng)頭尾指針指向向量上界（QueueSize-1）時，其加1操作的結(jié)果是指向向量的下界0。這種循環(huán)意義下的加1操作可以描述為：

if(i+1==QueueSize)i=0;elsei++;利用模運(yùn)算可簡化為：i=(i+1)%QueueSize隊列的順序存儲顯然，因為循環(huán)隊列元素的空間可以被利用，除非向量空間真的被隊列元素全部占用，否則不會上溢。因此，除一些簡單的應(yīng)用外，真正實用的順序隊列是循環(huán)隊列。如圖所示：由于入隊時尾指針向前追趕頭指針，出隊時頭指針向前追趕尾指針，故隊空和隊滿時頭尾指針均相等。因此，我們無法通過front=rear來判斷隊列“空”還是“滿”。

解決此問題的方法至少有三種：其一是另設(shè)一個布爾變量以區(qū)別隊列的空和滿；其二是少用一個元素的空間，約定入隊前，測試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認(rèn)為隊滿（注意：rear所指的單元始終為空）；隊列的順序存儲其三是使用一個計數(shù)器記錄隊列中元素的總數(shù)（實際上是隊列長度）。下面我們用第三種方法實現(xiàn)循環(huán)隊列上的六種基本操作，為此先給出循環(huán)隊列的類型定義。

#defineQueueSize100typedefstruct{Queuedatatypedata[queuesize]intfront，rear;intlen;}sqqueue;隊列的順序存儲（1）置空隊voidinitqueue(sqqueue*q){q–>front=q–>rear=-1;q–>len=0;}（2）判斷隊空intqueueempty(sqqueue*q){returnq–>len==0;}（3）判斷隊滿intqueuefull(sqqueue*q){returnq–>len==queuesize;}隊列的順序存儲（4）入隊voidinqueue(sqqueue*q,datatypex){if(queuefull(q)){printf(“queueoverflow”);return;}q–>len++;q–>data[q–>rear]=x;

q–>rear=(q–>rear+1)%queuesize;}隊列的順序存儲（5）出隊queuedatatypedequeue(sqqueue*q){datatypetemp;if(queueempty(q)){printf(“queueunderflow”);return;}temp=q–>data[q–>front];q–>len--;q–>front=(q–>front+1)%queuesize;returntemp;}隊列的順序存儲（6）取頭元素queuedatatypequeuefront(sqqueue*q){if(queueempty(q)){printf(“queueisempty.”);return(0);}returnq–>data[q–>front];}隊列的順序存儲區(qū)分隊列空與滿另一種方法少用一個元素的空間，約定入隊前，測試尾指針在循環(huán)意義下加1后是否等于頭指針,若相等則認(rèn)為隊滿（注意：rear所指的單元始終為空）；隊列的順序存儲循環(huán)隊列

rearfront

0123(3)隊空隊滿條件：(Q.rear+1)%MAX=Q.front注：實際上為了避免與隊空標(biāo)志沖突，還留有一個空間。將頭尾連接成一個環(huán)，形成循環(huán)隊列。(1)一般情況

rearfront0123e4e3

(2)隊滿fronte3

e40123reare5隊列的順序存儲#defineMAXSIZE50typedefstruct{QueueElementTypeelement[MAXSIZE];intfront;intrear;}SeqQueue;注意事項：1、出隊時，頭指針的變化為front=(front+1)modMAXSIZE2、入隊時，尾指針的變化為rear=(rear+1)modMAXSIZE3、凡是遇到指針要發(fā)生變化，頭和尾指針的有效范圍為[0,MAXSIZE-1]，所以用取模運(yùn)算來保證頭尾指針的取值循環(huán)隊列的類型定義循環(huán)隊列中加入一個元素的算法：

intEnQueue(SeqQueue*Q,intx)Q為已有的循環(huán)隊列將插入的值循環(huán)隊列循環(huán)隊列中加入一個元素的算法：intEnQueue(SeqQueue*Q,intx){if((Q->rear+1)%MAXSIZE==Q->front)return(0);else{Q->rear=x;Q->rear=(Q->rear+1)%MAXSIZE;return(1);}}

rearfront0123e4e3rearX循環(huán)隊列循環(huán)隊列中刪除一個元素的算法：intDeQueue(SeqQueue*Q，int*py)已有的循環(huán)隊列返回刪除的值的地址循環(huán)隊列循環(huán)隊列中刪除一個元素的算法：intDeQueue(SeqQueue*Q，int*py){if(Q->rear==Q->front)return(0);else{*py=Q[Q->front];Q->front=(Q->front+1)%MAXSIZE;return(1);}}

rearfront0123e4e3front循環(huán)隊列鏈?zhǔn)酱鎯Y(jié)構(gòu)ana2a1

Q.frontQ.rear隊頭隊尾typedefstructNode{QueueElementTypedata;structNode*next;}LinkQueueNode;/*結(jié)點的定義*/typedefstruct{LinkQueueNode*front;LinkQueueNode*rear;}LinkQueue;/*隊列的定義*/注意：隊頭永遠(yuǎn)指向頭結(jié)點，隊尾永遠(yuǎn)指向最后一個元素。3.3.2隊列的表示和實現(xiàn)

e^a1a2anQ.frontQ.rear

鏈隊列添加操作Q.rearnewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));newNode->data=e;newNode->next=0;Q->rear->next=newNode;Q->rear=newNode;newNodeana2a1

ana2a1

Q.frontQ.rear刪除一個元素鏈隊列刪除操作Q.frontQ.rearQ.front->next=Q.front->next->next;設(shè)棧S為空，隊Q的狀態(tài)是abcd，其中a為隊首元素，d為隊尾元素，經(jīng)過下面兩個操作后，隊Q的狀態(tài)是（）。（1）刪除隊Q中的元素，將刪除的元素插入棧S，直到隊Q為空。（2）依次將棧S中的元素插入隊Q，直到棧S為空。(a)abcd(b)acbd(c)dcba(d)bacddcbafrontreartop隊Q棧Sfrontreardcbatop隊Q棧Sabcdfrontreartop隊Q棧Sc設(shè)一個棧的輸入序列為A、B、C、D，則借助一個棧所得到的輸出序列不可能是（） A）A，B，C，D B）D，C，B，A C）A，C，D，B D）D，A，B，C實現(xiàn)A的過程：Push(A)、Pop(A)、Push(B)、Pop(B)、Push(C)、Pop(C)、Push(D)、Pop(D)實現(xiàn)B的過程：Push(A)、Push(B)、Push(C)、Push(D)、Pop(A)、Pop(B)、Pop(C)、Pop(D)實現(xiàn)C的過程：Push(A)、Pop(A)、Push(B)、Push(C)、Pop(C)、Push(D)、Pop(D)、Pop(B)D

第3節(jié)棧、隊列和數(shù)組數(shù)組樹結(jié)構(gòu)（層次結(jié)構(gòu)）：除根結(jié)點之外，所有結(jié)點僅有一個直接前驅(qū)。

第4節(jié)樹結(jié)構(gòu)結(jié)點

結(jié)點的度樹的度

葉子結(jié)點分支結(jié)點子結(jié)點與父結(jié)點結(jié)點層數(shù)樹的深度

森林

一個結(jié)點具有的子樹個數(shù)樹中最大結(jié)點的度，圖示樹的度為4