計算機軟件技術(shù)基礎3-2 數(shù)據(jù)結(jié)構(gòu)及算法(棧與隊)

常用數(shù)據(jù)結(jié)構(gòu)及其運算第三章1§3.1概述§3.2線性表§3.3棧與隊

§3.4樹與二叉樹§3.5

圖§3.6查找與排序目錄23.3

棧與隊3.3.1棧的結(jié)構(gòu)和運算3.3.2隊的結(jié)構(gòu)和運算3.3.3小結(jié)33.3.1棧的結(jié)構(gòu)和運算棧的定義 是只能在表的一端進行插入和刪除操作的 線性表。允許插入和刪除的一端稱為棧頂 (top)，另一端稱為棧底(bottom)。

設棧s=(a1,a2,...,an)，a1稱為棧底元素，

an稱為棧頂元素。 棧中元素按a1,a2,...,an次序進棧，又按 an,...,a2,a1次序退棧。因此棧的操作特點 是：后進先出（LIFO）；n=0時稱為空棧。棧的存儲結(jié)構(gòu)：順序和鏈式棧的種類：順序棧、鏈棧a1a2a3……an棧底棧頂進棧出棧43.3.1棧的結(jié)構(gòu)和運算堆棧的主要操作有：?創(chuàng)建空棧。?進棧(push)操作:在棧頂插入元素。?出棧(pop)操作:在棧頂刪除元素。?讀棧頂元素:只是讀出棧頂元素，并不改變棧內(nèi)元素。

5順序棧 用向量作為存儲結(jié)構(gòu)，可用一維數(shù)組s[1:m] 表示。

m－棧的最大容量。 Top－棧頂指示器。top=0，棧空；top=m，棧滿。a1a2……top12a1a2……123top進棧：top+1a1a2……12退棧：top-1topa1a2a3……am棧滿top……0top棧空3.3.1棧的結(jié)構(gòu)和運算6順序棧(C++描述)#defineSTACKSIZE100 //堆棧最大可分配空間數(shù)量classSqStack{public: ElemTypedata[STACKSIZE]; //存儲元素的數(shù)組

inttop; //棧頂指針，存儲棧頂元素的下標

SqStack(){top=-1;} //構(gòu)造函數(shù)

voidPush(ElemTypex); //入棧操作

voidPop(ElemType&result); //出棧操作

voidGetTop(ElemType&result); //取棧頂元素};

一般將數(shù)組的0下標單元作為棧底，將棧頂元素的下標存儲在棧頂指針top中，它隨著元素進棧出棧而變化。top為-1表示空棧，top等于stacksize-1則表示棧滿。3.3.1棧的結(jié)構(gòu)和運算7（1）進棧操作若棧不滿，則在棧頂插入元素x作為新的棧頂。voidSqStack::Push(ElemTypex){ if(top<stacksize-1) { top++; data[top]=x; } elsecout<<”棧滿”;}3.3.1棧的結(jié)構(gòu)和運算8（2）出棧操作若棧不空，則刪除棧頂元素，用result返回其值。voidSqStack::Pop(ElemType&result){ if(top>-1)

{ result=data[top]; top--; }elsecout<<"棧空";}3.3.1棧的結(jié)構(gòu)和運算9（3）取棧頂元素若棧不空，則用result返回棧頂元素。voidSqStack::GetTop(ElemType&result){ if(top>-1){ result=data[top]; } elsecout<<"?？?;}3.3.1棧的結(jié)構(gòu)和運算10鏈棧 鏈棧是用鏈表作為棧的存儲結(jié)構(gòu)，top為棧頂指 針，指示棧頂元素位置，若top=NULL,則表示棧 空。鏈棧一般不會出現(xiàn)上溢，除非內(nèi)存中已不 存在可用空間。top^棧底top空棧3.3.1棧的結(jié)構(gòu)和運算11鏈棧的插入（進棧）：鏈棧的刪除（退棧）：top┄x^pp->data=x; p->next=top;top=p;top┄^p=top;top=top->next;

free(p);3.3.1棧的結(jié)構(gòu)和運算12鏈式棧(C++描述)

棧的鏈式存儲結(jié)構(gòu)實質(zhì)上就是一個無頭結(jié)點、只能在頭部插入、刪除元素的單鏈表。typedefstructnode{

ElemTypedata; //數(shù)據(jù)域

structnode*next; //指針域}SNode; classLinkStack{ public: SNode*top; //棧頂指針

LinkStack(){top=NULL;} //構(gòu)造函數(shù)

voidPush(ElemTypex); //入棧操作

voidPop(ElemType&result); //出棧操作};

3.3.1棧的結(jié)構(gòu)和運算13（1）進棧操作若棧不滿，則在棧頂插入元素x作為新的棧頂。

voidLinkStack::Push(ElemTypex){ SNode*p=newSNode; if(p!=NULL){ p->data=x; p->next=top;

top=p; }}3.3.1棧的結(jié)構(gòu)和運算14（2）出棧操作若棧不空，則刪除棧頂元素，用result返回其值。voidLinkStack::Pop(ElemType&result);{ SNode*p;

if(top!=NULL){ result=top->data;

p=top; top=top->next; deletep; }}3.3.1棧的結(jié)構(gòu)和運算154.棧的應用

(1)

表達式求值（用于高級語言的編譯程序）

運算符：**/*+-; 優(yōu)先數(shù)：322110小括號優(yōu)先數(shù)：θ1 θ2

(

<其它符號，=“)”

(

>其它符號)

>其它符號

)

<其它符號3.3.1棧的結(jié)構(gòu)和運算16

需建立兩個棧：操作數(shù)(NS)、運算符(OS)。

算法思想：置NS為空，“；”作為OS的棧底元素。自左至右掃描表達式：①若為操作數(shù)，將其壓入NS棧②若為運算符，與OS棧頂元素比較優(yōu)先級：>OS棧頂，則將當前運算符壓入OS棧。<=OS棧頂，則從NS棧中彈出兩個操作數(shù)x、y，再從OS棧中彈出一個運算符θ，構(gòu)成一條機器指令：xθy→T，將結(jié)果T送入NS棧。=“；”，且OS棧頂也為“；”，則表示表達式處理結(jié)束，此時NS棧頂?shù)脑丶礊榇吮磉_式的值。(1)

表達式求值3.3.1棧的結(jié)構(gòu)和運算17

舉例：設表達式為：A/B**C+D;過程為：CBA**/;DT2+;B**C-->T1T1A/;T2+

D-->T3T3;;A/T1-->T2T2得到表達式的值T33.3.1棧的結(jié)構(gòu)和運算18

過程嵌套－－多重嵌套時，用棧將各層斷點信息依次入棧，當各層子過程返回時，以相反的次序從棧頂取出（FILO,or,LIFO）r主過程rstrsrstrsr子程A子程B子程C3.3.1棧的結(jié)構(gòu)和運算(2)

過程調(diào)用19

遞歸調(diào)用－－一個過程通過過程調(diào)用語句 直接或間接地調(diào)用自己的過程。直接遞歸程序ABegin.A.End程序A程序BBegin.B.EndBegin.A.End間接遞歸3.3.1棧的結(jié)構(gòu)和運算20(3)

回溯求解算法3.3.1棧的結(jié)構(gòu)和運算1）問題描述：設有n件體積分別為w1,w2,...,wn的物品和一個能裝載總體積為T的背包，要求從n件物品中挑選出若干件物品，其體積之和恰好裝滿背包。若能，則背包問題有解，否則無解。2）解決方法：先將n件物品順序排列，依次裝入背包，每裝入一件即檢查當時包內(nèi)物品體積是否超過T，若裝入該件物品后不超過背包容 量T，則裝入，否則棄之取下一個，直到裝滿背包為止。若在裝入若干物品后背包未滿，但又無其它物品可選時，說明已裝入背包內(nèi)的物品組合不合適，需從背包中取出最后裝入的物品，繼續(xù)在其它未裝入物品中挑選，如此重復直到裝滿背包（有解）或無合適物品可選（無解）。3）分析：設一維數(shù)組W[n]用來存放n件物品的體積，棧S[n]用來存放放入背包內(nèi)物品的序號，T為背包能容納的體積，i為待選物品序號。每進棧一件物品，就從T中減去該物品的體積，若T-W[i]≥0，則該物品可選，若T-W[i]<0，則該物品不可選，若i>n，則需退棧，若此時?？眨瑒t說明無解。214）算法描述

Pack(T,n,W,S,top)

{

top=0;i=1;//初始化

while(T>0&&i<=n){if(T-W[i]==0||(T-W[i]>0&&i<n)){top++;S[top]=i;T=T-W[i];

}//可選if(T==0)return(1);//有解

else

｛if(i==n&&top>0){i=S[top];top--;T+=W[i];}//退棧

i++;//取下一個

}

}//endwhile

return(0);

}3.3.1棧的結(jié)構(gòu)和運算

5）舉例: 若T=10，W=(4,7,3,5,4,2)，棧的變化如下：22473542Wi初始狀態(tài)StopT=10473542Wi414StopT=1473542i11topT=6473542i313topT=3473542i回溯41topT=6473542i回溯51topT=6473542i515topT=2473542i6156topT=03.3.1棧的結(jié)構(gòu)和運算23

N=(Ndivd)*d+Nmodd;div為整除運算，mod為求余（1344)10=(2504)8N

Ndiv8

Nmod81348

168416821021

25202順序進棧出棧順序（4）十進制數(shù)N轉(zhuǎn)換成其它d進制的數(shù)3.3.1棧的結(jié)構(gòu)和運算24輸入任意一個非負十進制整數(shù)，輸出與其等值的八進制數(shù)。voidconversion(){InitStack(S);//構(gòu)造空棧

scanf("%d",n);

while(n){push(S,n%8);n=n/8;}while(!StackEmpty){Pop(S,e);printf("%d",e);}}3.3.1棧的結(jié)構(gòu)和運算253.3.2隊的結(jié)構(gòu)和運算隊的定義 只允許在表的一端進行插入，在表的另一 端進行刪除的線性表。

隊尾－允許插入的一端(rear)

隊首－允許刪除的一端(front)隊中元素按a1,a2,…,an次序入隊和出隊。 隊的操作特點：先進先出（FIFO）；

n=0時稱為空隊。隊的存儲結(jié)構(gòu)：順序和鏈式abcfrontrear入隊出隊隊列示意圖261、順序隊列—隊列順序存儲

順序存儲的隊列中，每次出隊列的元素必定是隊頭元素，因此如果采取與普通順序表同樣的操作方式，則每次出隊操作必然將整個隊列向前移動，這使得效率大大降低。因此在順序存儲的隊列中，出隊和入隊操作都不移動元素而是移動指針。為方便起見，這里規(guī)定隊頭指針front指向隊頭元素的前一個位置，隊尾指針rear指向隊尾元素所在位置。這樣，入隊和出隊操作的執(zhí)行步驟都是首先執(zhí)行指針移動，再進行元素讀寫。對空隊列而言，可假定front和rear的值為-13.3.2隊的結(jié)構(gòu)和運算27假溢出ABCfrontrearfrontrear

(a)

A?B?C入隊

(b)

A?B出隊,D?E入隊

(c)隊列假溢出隊列假溢出示意圖CDEfrontrear隨著元素不斷入隊列、出隊列，rear和front指針會不斷向后移動（如圖(b)所示），最終會指向數(shù)組的最大下標位置（如圖(c)所示）。由于rear和front指針只能單方向移動，這時元素無法入隊列，但是隊列中仍有大量空閑位置。這種情況稱為假溢出。3.3.2隊的結(jié)構(gòu)和運算282、循環(huán)隊列 解決隊列假溢出的辦法是將存放隊列元素的數(shù)組首尾相接，形成循環(huán)隊列。循環(huán)隊列的基本操作方式為：入隊列時先執(zhí)行rear=(rear+1)%M，再將新元素在rear指示位置加入；出隊列時先執(zhí)行front=(front+1)%M，再將下標為front的元素取出。

3.3.2隊的結(jié)構(gòu)和運算29

為了將隊空和對滿的條件加以區(qū)分，一般不使用front指針所指的位置。

隊空條件為front=rear

隊滿條件為(rear+1)%M=front30124567frontrearABCD30124567frontrear30124567frontrearABCDFGE

(a)循環(huán)隊列空(b)非空循環(huán)隊列(c)循環(huán)隊列滿循環(huán)隊列示意圖

3.3.2隊的結(jié)構(gòu)和運算30循環(huán)隊列描述如下：#defineMAXSIZE100 //隊列最大可分配空間數(shù)量classSqQueue{public: ElemTypedata[MAXSIZE]; //存放元素的數(shù)組

intfront; //隊頭指針

intrear; //隊尾指針

voidEnQueue(ElemTypex);

//入隊操作

voidDeQueue(ElemType&e);//出隊操作

voidGetHead(ElemType&e);//取隊頭元素};front和rear指針取值均為所指數(shù)組單元的下標。由于隊頭指針所指單元總是空的，length比實際能存儲的元素多一。

3.3.2隊的結(jié)構(gòu)和運算31（1）入隊操作若隊列不滿，則在隊尾插入元素x作為新的隊尾。voidSqQueue::EnQueue(ElemTypex){ if((rear+1)%MAXSIZE==front)

cout<<"隊列已滿";

else{ rear=(rear+1)%MAXSIZE; data[rear]=x; }}常用算法

3.3.2隊的結(jié)構(gòu)和運算32

（2）出隊操作若隊列不空，則刪除隊頭元素并用e取回該元素的值。voidSqQueue::DeQueue(ElemType&e){ if(rear==front)cout<<"隊列已空";

else{ front=(front+1)%MAXSIZE;

e=data[front];

}}3.3.2隊的結(jié)構(gòu)和運算33（3）取隊頭元素若隊列不空，則用e取回隊頭元素的值。voidSqQueue::GetHead(ElemType&e){ if(rear==front)cout<<"隊列已空";

else{ inti=(front+1)%MAXSIZE; e=data[i]; }}3.3.2隊的結(jié)構(gòu)和運算343、鏈隊列—隊列鏈式存儲 鏈隊列實質(zhì)上就是只能在頭部刪除元素、只能在尾部插入元素的單鏈表。 隊頭指針front就是單鏈表的頭指針，隊尾指針rear則是指向單鏈表最后一個結(jié)點的指針。

Qa1an∧frontrear非空鏈隊列

3.3.2隊的結(jié)構(gòu)和運算35鏈隊列的結(jié)點可定義如下：

structQNode{

ElemTypedata;

structQNode*next; };

鏈隊列有兩個指針，因此可采用下面定義:classLinkQueue{public: QNode*front; //隊頭指針

QNode*rear; //隊尾指針(下頁繼續(xù)……)3.3.2隊的結(jié)構(gòu)和運算36(接上頁)

LinkQueue() { front=newQNode; //建立頭結(jié)點

front->next=NULL; rear=front; //尾指針也指向頭結(jié)點

}

intLength(); //求隊列長度

voidEnQueue(ElemTypex);//入隊操作

voidDeQueue(ElemType&e);//出隊操作

voidGetHead(ElemType&e);//求隊頭元素};3.3.2隊的結(jié)構(gòu)和運算37（1）求隊列的長度返回隊列的元素個數(shù)，即隊列的長度。

intLinkQueue::Length(){ QNode*p=front;

intlen=0; while(p!=rear){ len++; p=p->next; } returnlen;}3.3.2隊的結(jié)構(gòu)和運算38（2）入隊列操作插入元素x為隊列新的隊尾元素。

voidLinkQueue::EnQueue(ElemTypex){ QNode*s=newQNode; //建立新結(jié)點s s->data=x; s->next=NULL; rear->next=s; //在隊尾插入結(jié)點s rear=s; //修改隊尾指針}3.3.2隊的結(jié)構(gòu)和運算39（3）出隊列操作若隊列不空，則刪除隊頭元素，用e返回其值。voidLinkQueue::DeQueue(ElemType&e){ QNode*p; if(front==rear)cout<<"隊列已空"; else{ p=front->next; e=p->data; front->next=p->next; if(rear==p)rear=front;

deletep; }}刪除最后一個元素時，需要修改尾指針，使其指向頭結(jié)點3.3.2隊的結(jié)構(gòu)和運算40（4）取隊頭元素若隊列不空，則用e返回隊頭元素；voidLinkQueue::GetHead(ElemType&e){ QNode*p; if(front==rear)cout<<"隊列已空";

else{ p=front->next; e=p->data; }}3.3.2隊的結(jié)構(gòu)和運算41

FIFO原則－－模擬排隊問題。 多道程序中的CPU管理

在只有一個CPU的條件下，多個用戶共同使用計算機，隊列在實現(xiàn)合理分配CPU中起重要作用。操作系統(tǒng)可作如下處理： 1）當一個用戶請求CPU時，它就進入使用CPU的隊列。3.3.2隊的結(jié)構(gòu)和運算4、隊的應用42

2）在此隊列首部的用戶是當前CPU的使用者，并且在整個CPU時間周期內(nèi)繼續(xù)留在隊列的首部。 3）當一個用戶完成了它的現(xiàn)行請求CPU的時間周期后，就出此隊列，并在形成下一個請求時間周期之前不再進隊，兩次請求之間的時間稱為延遲周期。 這種調(diào)度原則稱為“先來先服務”， 請參見教材第42頁的例子。3.3.2隊的結(jié)構(gòu)和運算43 緩沖區(qū)的設計

1）適用于多道程序?qū)σ粋€公共數(shù)據(jù)區(qū)（公共緩沖區(qū)）進行數(shù)據(jù)存取的情況。遵循“先存入先取出”的原則。

2）在計算機系統(tǒng)中由于高速的主機與慢速的外設之間速度不匹配，致使主機要等待，使效率大大降低，利用緩沖區(qū)可以進行解決。

例：打印機速度較計算機慢得多，計算機輸出的數(shù)據(jù)不能同時打印出來，通過設置打印緩沖區(qū)隊列來解決。 －－常用循環(huán)隊列來實現(xiàn)緩沖區(qū)設置。3.3.2隊的結(jié)構(gòu)和運算44/***用隊列結(jié)構(gòu)處理備忘錄****/#include<stdio.h>#include<stdlib.h>#include<string.h>#defineM10/*最多十條記錄*/char*p[M];/*指針數(shù)組，存放備忘錄隊列*/intrear,front;/*rear:隊列，front:對頭*/voidenter(),list(),delete(),save(),load();main(){charc,s[80];registerintt;for(t=0;t<M;t++)p[t]=NULL;rear=front=0;/*隊列賦初值，空隊列*/

for(;;)switch(menu_select()){case1:enter();break; case2:save();break; case3:load();break; case4:list();break; case5:delete();break; case0:exit(0);}}3.3.2隊的結(jié)構(gòu)和運算--應用實例閱讀理解45menu_select(){chars[80];intc;printf("1----inputmemo\n");/*顯示菜單，接收用戶輸入*/

printf("2----savememotofile\n");printf("3----loadmemofromfile\n");printf("4----listmemo\n");printf("5----deletememoitem\n");printf("0----exit\n");do{ printf("\nPleaseinputyourselect:"); gets(s);/*接收輸入，并將字符串轉(zhuǎn)化為整數(shù)*/

c=atoi(s);}while(c<0||c>6);/*c<0或c>6，輸入無效*/

returnc;}46voidenter()/*輸入備忘錄內(nèi)容*/{chars[256]=""；/*接收輸入，暫存*/char*item;

do{ printf("inputthe%dstitem:",rear+1);/*st：表示序號*/

gets(s); if(*s==0)break; item=malloc(strlen(s)+1);/*增開存儲區(qū)域*/

if(!item) {printf("Noenoughmomery!");return;} strcpy(item,s); if(*s) {if(rear==M)

{printf("Overflow!\n");} else

{p[rear]=item;rear++;}

}

}while(*s);}存放動態(tài)分配的內(nèi)存首地址，分配的內(nèi)存用于存放S中的內(nèi)容把item指針所指的內(nèi)容存放到隊列的第rear位置47voidsave()/*將備忘錄存入文件*/{

FILE*fp;inti;if((fp=fopen("memo.txt","w+"))==NULL){printf("Cannotopenfile!");exit(0);}for(i=front;i<rear;i++){fwrite(p[i],strlen(p[i]),1,fp);

fwrite("C",1,1,fp);}

fwrite("\0",1,1,fp);/*在文件末尾寫上“0”，作為結(jié)束標記*/

fclose(fp);}strlen()為要寫的字節(jié)數(shù)，p[i]為記錄首地址在每一項記錄末尾寫上“C”，作為結(jié)束標記48voidsave()/*將備忘錄存入文件*/{

FILE*fp;inti;if((fp=fopen("m