綜合 數(shù)據(jù)結構03

上節(jié)課知識點回顧線性表的邏輯結構線性表的順序存儲線性表的鏈式存儲如果限定線性表插入刪除的位置--受限的線性表回顧（練一練）2023/2/52．用鏈表表示線性表的優(yōu)點是（

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

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

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

線性表棧隊列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棧和隊列是兩種常用的數(shù)據(jù)類型2023/2/55

第3章棧和隊列

棧，也叫堆棧，是最常用也是最重要的數(shù)據(jù)結構之一。比如編譯器中的語法識別、數(shù)學表達式的處理、程序運行中的函數(shù)及過程的調用等，都要用到棧的有關特性。它們是棧應用于實際問題的典型。3.1棧

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

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

特點：后進先出棧又稱為“后進先出”的線性表，簡稱LIFO表。

LastInFirstOut3.1.1棧的定義和運算

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

邏輯

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

若棧S不空，則由x返回棧頂元素。判?？誆mpty(S)

若棧S為空棧，結果為1，否則結果為0。

2023/2/59

3.1.2棧的順序存儲結構及其基本運算的實現(xiàn)

棧有兩種存儲表示方法:順序存儲和鏈式存儲1.棧的順序存儲結構

棧的順序存儲結構簡稱為順序棧。通常由一個一維數(shù)組和一個記錄棧頂元素位置的變量組成。練一練2023/2/510一個棧的入棧序列是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域:為一個一維數(shù)組，用于存儲棧中元素。

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

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

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

2023/2/5132．基本運算在順序存儲結構的實現(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;}判棧空Empty(S)intEmpty(STACK*S){return(S->top==-1?1:0);}棧的應用舉例數(shù)制轉換

算法基于原理：

N=(Ndivd)×d+Nmodd

2023/2/518

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

，其運算過程如下：

NNdiv8Nmod8

13481684

168210

2125

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

兩個棧共享大小為m的內存空間時，分配方法的示意圖如下兩個棧的共享存儲單元可用C語言描述如下：#defineMaxSize<共享存儲單元的最大長度>typedefstruct{ElemTypedata[MaxSize];inttop[2];}STACK;2023/2/520（1）兩個棧共享存儲單元的壓棧算法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）兩個棧共享存儲單元的出棧算法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棧的鏈式存儲結構及其基本運算的實現(xiàn)1.棧的鏈式存儲結構

棧的鏈式實現(xiàn)是以鏈表作為棧的存儲結構，并在這種存儲結構上實現(xiàn)棧的基本運算。棧的鏈式實現(xiàn)稱為鏈棧鏈棧的C語言描述如下：typedefstructsnode{//定義鏈棧結點類型

ElemTypedata;structsnode*next;}LinkSTACK;LinkSTACK*top;鏈棧結構示意圖2023/2/523鏈棧的幾種狀態(tài):2023/2/5242．基本運算在鏈式存儲結構的實現(xiàn)棧初始化

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

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出棧運算

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;}應用舉例1、表達式求解2、遞歸程序2023/2/528

表達式的三種標識方法：設

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

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

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

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

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

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

cd/e

f

后綴式:abc+de/f

從原表達式求得后綴式的規(guī)律為：1)設立運算符棧；2)設表達式的結束符為“#”，

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

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

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

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

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

邏輯

順序鏈式2.隊列的應用舉例2023/2/541

3.4.1隊列的定義和運算

1．隊列的定義

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

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

2．隊列的基本運算隊列初始化InitQueue(SQ)

設置一個空隊列SQ。入隊列EnQueue(SQ，x)

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

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

由x返回隊頭結點的值。

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

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

（a）表示空隊列，

rear=front=0。（b）元素A入隊后，

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

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

rear=front=0。（b）元素A入隊后，

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

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

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

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

入隊列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出隊intOutQueue(SQUEUE*SQ,ElemType*x){if(Empty(SQ)){printf("\nQueueisfree");return0;}SQ->front=(SQ->front+1)%MaxSize;*x=SQ->data[SQ->front];return1;}判隊列空intEmpty(SQUEUE*SQ){return(SQ->rear==SQ->front)?1:0;}

2023/2/5503.4.3隊列的鏈式存儲結構及其基本運算的實現(xiàn)

1.隊列的鏈式存儲結構

隊列的鏈式存儲結構簡稱為鏈隊。它實際上是一個同時帶有首指針和尾指針的單鏈表。頭指針指向表頭結點，而尾指針則指向隊尾元素。鏈隊結構示意圖2023/2/551鏈隊運算指針變化情況2023/2/5522．基本運算鏈隊的實現(xiàn)隊列初始化

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