綜合 數(shù)據(jù)結(jié)構(gòu)03

上節(jié)課知識(shí)點(diǎn)回顧線性表的邏輯結(jié)構(gòu)線性表的順序存儲(chǔ)線性表的鏈?zhǔn)酱鎯?chǔ)如果限定線性表插入刪除的位置--受限的線性表回顧（練一練）2023/2/52．用鏈表表示線性表的優(yōu)點(diǎn)是（

）。(A)便于隨機(jī)存取(B)花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少(C)便于插入和刪除(D)數(shù)據(jù)元素的物理順序與邏輯順序相同2023/2/53若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（

）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。(A)單鏈表(B)僅有頭指針的單循環(huán)鏈表

(C)雙鏈表(D)僅有尾指針的單循環(huán)鏈表通常稱，棧和隊(duì)列是限定插入和刪除只能在表的“端點(diǎn)”進(jìn)行的線性表。

線性表?xiàng)ｊ?duì)列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n棧和隊(duì)列是兩種常用的數(shù)據(jù)類型2023/2/55

第3章棧和隊(duì)列

棧，也叫堆棧，是最常用也是最重要的數(shù)據(jù)結(jié)構(gòu)之一。比如編譯器中的語法識(shí)別、數(shù)學(xué)表達(dá)式的處理、程序運(yùn)行中的函數(shù)及過程的調(diào)用等，都要用到棧的有關(guān)特性。它們是棧應(yīng)用于實(shí)際問題的典型。3.1棧

棧和隊(duì)列是兩種常用的數(shù)據(jù)類型2023/2/561．棧的定義

棧是一種特殊的線性表，插入或刪除棧元素的運(yùn)算只能在表的一端進(jìn)行，稱運(yùn)算的一端為棧頂，另一端稱為棧底。

特點(diǎn)：后進(jìn)先出棧又稱為“后進(jìn)先出”的線性表，簡(jiǎn)稱LIFO表。

LastInFirstOut3.1.1棧的定義和運(yùn)算

棧頂棧底內(nèi)容提綱2023/2/51.棧的類型定義和實(shí)現(xiàn)

邏輯

順序鏈?zhǔn)?.棧的應(yīng)用舉例2023/2/582．棧的基本運(yùn)算初始化棧InitStack(S)設(shè)置一個(gè)空棧S。壓棧Push(S,x)將元素x插入棧S中，使x成為棧S的棧頂元素。出棧Pop(S,x)當(dāng)棧S不空時(shí)，由x返回棧頂元素，并從棧中刪除棧頂元素取棧頂元素GetTop(S,x)

若棧S不空，則由x返回棧頂元素。判棧空Empty(S)

若棧S為空棧，結(jié)果為1，否則結(jié)果為0。

2023/2/59

3.1.2棧的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)

棧有兩種存儲(chǔ)表示方法:順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)1.棧的順序存儲(chǔ)結(jié)構(gòu)

棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧。通常由一個(gè)一維數(shù)組和一個(gè)記錄棧頂元素位置的變量組成。練一練2023/2/510一個(gè)棧的入棧序列是1,2,3,4,5，則下列序列中不可能的出棧序列是()A.2,3,4,1,5B.5,4,1,3,2C.2,3,1,4,5D.1,5,4,3,22023/2/511ElemType為棧中元素的數(shù)據(jù)類型，可以根據(jù)需要而指定為某種具體的類型。

data域:為一個(gè)一維數(shù)組，用于存儲(chǔ)棧中元素。

top域:棧頂指針。取值范圍為0～MaxSize-1。

top=-1表示?？?，top=MaxSize-1表示棧滿。#defineMaxSize<存儲(chǔ)數(shù)據(jù)元素的最大個(gè)數(shù)>typedefstruct{ElemTypedata[MaxSize];inttop;}STACK;順序棧的C語言描述如下：2023/2/512。

順序棧的幾種狀態(tài)（最大長(zhǎng)度MaxSize為4）（a）當(dāng)棧中沒有數(shù)據(jù)元素時(shí)，表示為?？?。棧頂元素所對(duì)應(yīng)的下標(biāo)值top=-1。（b）表示在（a）基礎(chǔ)上執(zhí)行Push(S,‘A’)后得到這種狀態(tài)。（c）又有三個(gè)元素B、C、D先后入棧，此時(shí)棧頂元素的下標(biāo)值top=3。棧已滿。（d）表示在（c）狀態(tài)下，執(zhí)行一次Pop(S，x)運(yùn)算得到。（e）表示在（d）狀態(tài)下，執(zhí)行三次Pop(S，x)運(yùn)算得到。此時(shí)棧頂下標(biāo)值top=-l，又變成棧空狀態(tài)

2023/2/5132．基本運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)初始化棧InitStack(S)

voidInitStack(STACK*S){S->top=-1;}

壓棧Push(S,x)

intPush(STACK*S,ElemTypex){if(S->top==MaxSize-1){printf("\nStackisfull!");return0;}S->top++;S->data[S->top]=x;return1;}212023/2/5142023/2/515出棧Pop(S,x)intPop(STACK*S,ElemType*x){if(Empty(S)){printf("\nStackisfree!");return0;}*x=S->data[S->top];S->top--;return1;}X2023/2/516

取棧頂元素GetTop(S,x)

intGetTop(STACK*S,ElemType*x){

if(Empty(S)){printf("\nStackisfree!");return0;}*x=S->data[S->top];return1;}判?？誆mpty(S)intEmpty(STACK*S){return(S->top==-1?1:0);}棧的應(yīng)用舉例數(shù)制轉(zhuǎn)換

算法基于原理：

N=(Ndivd)×d+Nmodd

2023/2/518

例如：（1348)10=(2504)8

，其運(yùn)算過程如下：

NNdiv8Nmod8

13481684

168210

2125

202計(jì)算順序輸出順序除基取余逆序法2023/2/5193．棧的共享存儲(chǔ)單元

兩個(gè)棧共享大小為m的內(nèi)存空間時(shí)，分配方法的示意圖如下兩個(gè)棧的共享存儲(chǔ)單元可用C語言描述如下：#defineMaxSize<共享存儲(chǔ)單元的最大長(zhǎng)度>typedefstruct{ElemTypedata[MaxSize];inttop[2];}STACK;2023/2/520（1）兩個(gè)棧共享存儲(chǔ)單元的壓棧算法intPush(STACK*S,ElemTypex,intk){if(S->top[0]+1==S->top[1]){printf("\nstackisfull!");return0;}if(k==0){S->top[0]++;S->data[S->top[0]]=x;}//棧0else{S->top[1]--;S->data[S->top[1]]=x;}//棧1return1;}2023/2/521（2）兩個(gè)棧共享存儲(chǔ)單元的出棧算法intPop(STACK*S,intk,ElemType*x){if((k==0)&&(S->top[0]==-1)){printf("\nstackisfree!");return0;}if((k==1)&&(S->top[1]==MaxSize)){printf("\nstackisfree!");return0;}if(k==0){*x=S->data[S->top[0]];S->top[0]--;}else{*x=S->data[S->top[1]];S->top[1]++;}return1;}2023/2/5223.1.3棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)1.棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

棧的鏈?zhǔn)綄?shí)現(xiàn)是以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，并在這種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)棧的基本運(yùn)算。棧的鏈?zhǔn)綄?shí)現(xiàn)稱為鏈棧鏈棧的C語言描述如下：typedefstructsnode{//定義鏈棧結(jié)點(diǎn)類型

ElemTypedata;structsnode*next;}LinkSTACK;LinkSTACK*top;鏈棧結(jié)構(gòu)示意圖2023/2/523鏈棧的幾種狀態(tài):2023/2/5242．基本運(yùn)算在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的實(shí)現(xiàn)棧初始化

voidInitStack(LinkSTACK**top){if(!*top=(LinkSTACK*)malloc(sizeof(LinkSTACK)))returnOVERFLOW;(*top)->next=NULL;}top’topnext2023/2/525壓棧運(yùn)算

intPush(LinkSTACK**top,ElemTypex){LinkSTACK*s;s=(LinkSTACK*)malloc(sizeof(LinkSTACK));s->data=x;s->next=(*top)->next;(*top)->next=s;return1;}判斷?？?/p>

intEmpty(LinkSTACK**top){return((*top)->next==NULL?1:0);}2023/2/526出棧運(yùn)算

intPop(LinkSTACK**top,ElemType*x)

{LinkSTACK*s;if(Empty(top)){printf("\nstackisfree!");return0;}s=(*top)->next;*x=s->data;(*top)->next=s->next;free(s);return1;}2023/2/527取棧頂元素

intGetTop(LinkSTACK**top,ElemType*x){if(Empty(top)){printf("\nstackisfree!");return0;}*x=(*top)->next->data;return1;}應(yīng)用舉例1、表達(dá)式求解2、遞歸程序2023/2/528

表達(dá)式的三種標(biāo)識(shí)方法：設(shè)

Exp=S1+OP

+S2則稱OP

+S1+S2

為前綴表示法

S1+

OP

+S2

為中綴表示法

S1+S2+

OP

為后綴表示法

例如:Exp=ab

+

(cd/e)f前綴式:+

ab

c/def中綴式:ab

+

cd/ef后綴式:ab

cde/f

+結(jié)論:1）操作數(shù)之間的相對(duì)次序不變;2）運(yùn)算符的相對(duì)次序不同;3）中綴式丟失了括弧信息，致使運(yùn)算的次序不確定;4)前綴式的運(yùn)算規(guī)則為:連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式;5)后綴式的運(yùn)算規(guī)則為:

運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序;

每個(gè)運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式。如何從后綴式求值？先找運(yùn)算符，再找操作數(shù)例如：

abcde/f+abd/ec-d/e(c-d/e)f如何從原表達(dá)式求得后綴式？

每個(gè)運(yùn)算符的運(yùn)算次序要由它之后的一個(gè)運(yùn)算符來定，在后綴式中，優(yōu)先數(shù)高的運(yùn)算符領(lǐng)先于優(yōu)先數(shù)低的運(yùn)算符。分析“原表達(dá)式”和“后綴式”中的運(yùn)算符:原表達(dá)式:a+b

cd/e

f

后綴式:abc+de/f

從原表達(dá)式求得后綴式的規(guī)律為：1)設(shè)立運(yùn)算符棧；2)設(shè)表達(dá)式的結(jié)束符為“#”，

予設(shè)運(yùn)算符棧的棧底為“#”；3)若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式。4)若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符，則進(jìn)棧；5)否則，退出棧頂運(yùn)算符發(fā)送給后綴式；

6)“(”對(duì)它之前后的運(yùn)算符起隔離作用，“)”可視為自相應(yīng)左括弧開始的表達(dá)式的結(jié)束符。從原表達(dá)式求得后綴式的規(guī)律為：2023/2/535下圖展示了算術(shù)表達(dá)式3×（7-2）求值的動(dòng)態(tài)過程

2023/2/536遞歸是一種非常重要的數(shù)學(xué)概念和解決問題的方法，在計(jì)算機(jī)科學(xué)和數(shù)學(xué)等領(lǐng)域有著廣泛的應(yīng)用。在計(jì)算機(jī)科學(xué)中，許多數(shù)據(jù)結(jié)構(gòu)，如廣義表、樹和二叉樹等，由于其自身固有的遞歸性質(zhì)，都可通過遞歸方式加以定義并實(shí)現(xiàn)許多問題的算法設(shè)計(jì)。在計(jì)算機(jī)內(nèi)部，通過棧來實(shí)現(xiàn)遞歸算法。所以遞歸是棧的一個(gè)實(shí)際應(yīng)用。

3.3棧與遞歸2023/2/537采用遞歸算法求解正整數(shù)n的階乘n!數(shù)學(xué)定義求n的階乘的遞歸函數(shù)算法如下:longfact(intn){longf;if(n==0)f=1;elsef=n*fact(n-1);returnf;}2023/2/538進(jìn)行fact(4)調(diào)用的系統(tǒng)棧的變化情況

2023/2/539函數(shù)fact(4)的遞歸調(diào)用過程的執(zhí)行流程內(nèi)容提綱2023/2/51.隊(duì)列的類型定義和實(shí)現(xiàn)

邏輯

順序鏈?zhǔn)?.隊(duì)列的應(yīng)用舉例2023/2/541

3.4.1隊(duì)列的定義和運(yùn)算

1．隊(duì)列的定義

隊(duì)列也是一種運(yùn)算受限的線性表。在這種線性表上，插入限定在表的某一端進(jìn)行，刪除限定在表的另一端進(jìn)行。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。

特點(diǎn)：隊(duì)列中數(shù)據(jù)元素的入隊(duì)和出隊(duì)過程是按照“先進(jìn)先出”的原則進(jìn)行的。因此，隊(duì)列又稱為“先進(jìn)先出”的線性表，簡(jiǎn)稱FIFO表。FirstInFirstOut3.4隊(duì)列隊(duì)頭隊(duì)尾queue2023/2/542

2．隊(duì)列的基本運(yùn)算隊(duì)列初始化InitQueue(SQ)

設(shè)置一個(gè)空隊(duì)列SQ。入隊(duì)列EnQueue(SQ，x)

將x插入到隊(duì)列SQ的隊(duì)尾。出隊(duì)OutQueue(SQ，x)

將隊(duì)頭元素賦給x，并刪除隊(duì)頭元素。取隊(duì)頭元素GetHead(SQ，x)

由x返回隊(duì)頭結(jié)點(diǎn)的值。

判隊(duì)列空Empty(SQ)隊(duì)列SQ是否為空。若為空返回1，否則返回0。練一練棧和隊(duì)列的共同點(diǎn)是()。A．都是先進(jìn)后出B．都是先進(jìn)先出C．只允許在端點(diǎn)處插入和刪除元素D．沒有共同點(diǎn)2023/2/5432023/2/544

3.4.2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)隊(duì)列有兩種存儲(chǔ)表示方法:順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)1．隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱順序隊(duì)。順序隊(duì)是用一維數(shù)組依次存放隊(duì)列中的元素和分別指示隊(duì)列的首端和隊(duì)列的尾端的兩個(gè)變量組成。這兩個(gè)變量分別稱為“隊(duì)頭指針”和“隊(duì)尾指針”。順序隊(duì)列的數(shù)據(jù)類型定義如下#defineMaxSize<隊(duì)列的最大容量>typedefstruct{ElemTypedata[MaxSize];intfront,rear;}SQUEUE;2023/2/545順序隊(duì)列（MaxSize=5）的幾種狀態(tài)

（a）表示空隊(duì)列，

rear=front=0。（b）元素A入隊(duì)后，

rear=1，front=0。（c）B，C依次入隊(duì)后，

rear=3，front=0。（d）A，B，C依此出隊(duì)后,rear=front=3。（e）D入隊(duì)后,rear=4,front=3。（f）D出隊(duì)后，rear=front=4。2023/2/546如圖所示是具有五個(gè)存儲(chǔ)單元的循環(huán)隊(duì)列（a）表示空隊(duì)列，

rear=front=0。（b）元素A入隊(duì)后，

rear=1，front=0。（c）B，C，D依次入隊(duì)后，

rear=4，front=0。（d）A出隊(duì)后,front=1,rear=4。（e）B，C，D出隊(duì)后,rear=front=4。

環(huán)形隊(duì)列指針SQ的四要素如下? 隊(duì)空：SQ->rear==SQ->front? 隊(duì)滿：(SQ->rear+1)%MaxSize==SQ->front進(jìn)隊(duì)操作：SQ->rear=(SQ>rear+1)%MaxSize;SQ->data[SQ->rear]=x;?出隊(duì)操作：SQ->front=(SQ->front+1)%MaxSize;*x=SQ->data[SQ->front];。2023/2/5472023/2/5482．基本運(yùn)算順序隊(duì)列的實(shí)現(xiàn)隊(duì)列初始化

voidInitQueue(SQUEUE*SQ){SQ->rear=SQ->front=0;}

入隊(duì)列intEnQueue(SQUEUE*SQ,ElemTypex){if((SQ->rear+1)%MaxSize==SQ->front){printf("\nQueueisfull!");return0;}SQ->rear=(SQ->rear+1)%MaxSize;SQ->data[SQ->rear]=x;return1;}2023/2/549出隊(duì)intOutQueue(SQUEUE*SQ,ElemType*x){if(Empty(SQ)){printf("\nQueueisfree");return0;}SQ->front=(SQ->front+1)%MaxSize;*x=SQ->data[SQ->front];return1;}判隊(duì)列空intEmpty(SQUEUE*SQ){return(SQ->rear==SQ->front)?1:0;}

2023/2/5503.4.3隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)

1.隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)。它實(shí)際上是一個(gè)同時(shí)帶有首指針和尾指針的單鏈表。頭指針指向表頭結(jié)點(diǎn)，而尾指針則指向隊(duì)尾元素。鏈隊(duì)結(jié)構(gòu)示意圖2023/2/551鏈隊(duì)運(yùn)算指針變化情況2023/2/5522．基本運(yùn)算鏈隊(duì)的實(shí)現(xiàn)隊(duì)列初始化

voidInitQueue(SQUEUE*LQ){QTYPE*p;p=(QTYPE*)malloc(sizeof(QTY