深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017棧和隊列演示文檔
《深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017棧和隊列演示文檔》由會員分享,可在線閱讀,更多相關(guān)《深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017棧和隊列演示文檔(63頁珍藏版)》請在裝配圖網(wǎng)上搜索。
.,第三章棧和隊列,數(shù)據(jù)結(jié)構(gòu),.,一、棧,2,第一節(jié)棧,棧是限定僅在表尾(top)進(jìn)行插入或刪除操作的線性表。允許插入和刪除的一端稱為棧頂(top,表尾),另一端稱為棧底(bottom,表頭)特點:后進(jìn)先出 (LIFO),.,二、棧的實現(xiàn),3,第一節(jié)棧,棧的存儲結(jié)構(gòu)主要有兩種:1. 順序棧2. 鏈?zhǔn)綏?.,一、順序棧,4,第二節(jié)順序棧,順序棧是棧的順序存儲結(jié)構(gòu)利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素指針top指向棧頂元素在順序棧中的下一個位置,base為棧底指針,指向棧底的位置。,.,二、順序棧的定義,5,第二節(jié)順表棧,采用C語言中動態(tài)分配的一維數(shù)組表示順序表,#define STACK_INIT_SIZE 100 /棧存儲空間的初始分配量#define STACKINCREMENT 10 /棧存儲空間的分配增量typedef struct SElemType*base /存儲空間基址SElemType*top; /棧頂指針int stacksize; /當(dāng)前分配的存儲容量(元素數(shù)) SqStack;,.,三、順序棧的特性,6,第二節(jié)順序棧,top=0 或top=base 表示空棧base=NULL表示棧不存在當(dāng)插入新的棧頂元素時,指針top+1刪除棧頂元素時,指針top-1當(dāng)topstacksize時,棧滿,溢出,.,四、順序棧的主要操作,7,第二節(jié)順序棧,ADT Stack 數(shù)據(jù)對象:D = ai | aiElemSet, i=1,2,3,n 數(shù)據(jù)關(guān)系:R = | ai-1,aiD 基本操作: Status InitStack(SqStack &S) / 構(gòu)造空棧 Status Push(SqStack &S, e) / 進(jìn)棧 Status Pop(SqStack &S, &e) / 出棧 Status GetTop(SqStack S, &e)/ 取棧頂元素值 Status StackEmpty(SqStack S) / 棧是否為空 ADT Stack,.,五、創(chuàng)建順序棧,8,第二節(jié)順序棧,Status InitStack(SqStack / InitStack,.,六、進(jìn)棧(插入新元素),9,第二節(jié)順序棧,Status Push(SqStack / Push,.,七、出棧(刪除元素),10,第二節(jié)順序棧,Status Pop(SqStack / Pop,.,八、取棧頂元素,11,第二節(jié)順序棧,Status GetTop(SqStack S, SElemType / GetTop,.,1.創(chuàng)建堆棧節(jié)點類template class LinStack;/前視定義,否則友元無法定義template /模板類型為Tclass StackNode friend class LinStack; /定義類LinStack為友元private: T data; /數(shù)據(jù)元素 StackNode *next; /指針public: StackNode(StackNode *ptrNext = NULL) /構(gòu)造頭結(jié)點 next = ptrNext; StackNode(const T,第三節(jié)鏈棧,.,第三節(jié)鏈棧,2.創(chuàng)建鏈?zhǔn)蕉褩n?template class LinStackprivate:StackNode *head;/頭指針int size;/數(shù)據(jù)元素個數(shù)public:LinStack(void);/構(gòu)造函數(shù)LinStack(void);/析構(gòu)函數(shù)void Push(const T,.,第三節(jié)鏈棧,3.鏈?zhǔn)蕉褩5膶崿F(xiàn) template LinStack:LinStack()/構(gòu)造函數(shù) head = new StackNode;/頭指針指向頭結(jié)點 size = 0; /size的初值為0template LinStack:LinStack(void)/析構(gòu)函數(shù) StackNode *p, *q; /釋放所有動態(tài)申請的結(jié)點空間 p = head;/p指向頭結(jié)點 while(p != NULL) /循環(huán)釋放結(jié)點空間 q = p; p = p-next; delete q; template int LinStack:NotEmpty(void) const/堆棧非空否if(size != 0) return 1;else return 0;,.,第三節(jié)鏈棧,template void LinStack:Push(const T/元素個數(shù)加1,.,第三節(jié)鏈棧,template T LinStack:Pop(void)/出棧 if(size = 0) cout *p = head-next;/p指向棧頂元素結(jié)點 T data = p-data;head-next = head-next-next;/原棧頂元素結(jié)點脫鏈delete p;/釋放原棧頂結(jié)點空間size-;/結(jié)點個數(shù)減1return data;/返回原棧頂結(jié)點的data域值,.,第三節(jié)鏈棧,template T LinStack:GetTop(void)const /取棧頂元素return head-next-data;,.,一、數(shù)值轉(zhuǎn)換,18,第四節(jié)棧的應(yīng)用舉例,將十進(jìn)制轉(zhuǎn)換為其它進(jìn)制(d),其原理為: N = (N/d)*d + N mod d例1:(1348)10=(2504)8 ,其運(yùn)算過程如下: N N /8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2,.,一、數(shù)值轉(zhuǎn)換,19,第四節(jié)棧的應(yīng)用舉例,void conversion () InitStack(S); / 創(chuàng)建新棧S scanf (“%d”,N); / 輸入一個十進(jìn)制數(shù)N while (N) Push(S, N % 8); / 將余數(shù)送入棧中 N = N/8; / 求整除數(shù) while (!StackEmpty(S) / 如果棧不空 Pop(S,e); / 將棧中數(shù)出棧 printf ( %d, e ); / conversion,.,二、行編輯程序,20,第四節(jié)棧的應(yīng)用舉例,用戶輸入一行字符允許用戶輸入出差錯,并在發(fā)現(xiàn)有誤時,可以用退格符“#”及時更正假設(shè)從終端接受兩行字符: whli#ilr#e(s#*s) 實際有效行為: while (*s),.,二、行編輯程序,21,第四節(jié)棧的應(yīng)用舉例,例2:對用戶輸入的一行字符進(jìn)行處理,直到行結(jié)束(“n”)void LineEdit() InitStack(s); ch = getchar(); /從終端接受一個字符 while (ch != n) switch(ch) case # : Pop(S, c);break; / 僅當(dāng)棧非空時退棧 case : ClearStack(S); break; default: Push(S, ch); break; / 有效字符進(jìn)棧 ch = getchar(); / 從終端接受一個字符 /將從棧底到棧頂?shù)臈?nèi)字符傳送到調(diào)用過程的數(shù)據(jù)區(qū); ,.,第四節(jié)棧的應(yīng)用舉例,三.括號匹配 假設(shè)一個算術(shù)表達(dá)式中包括( )、 和 三種形式的括號,設(shè)計一個判別表達(dá)式中括號是否正確匹對的程序。1.算法思想: 算術(shù)表達(dá)式中右括號和左括號匹配的次序:后到括號要最先被匹配的“后進(jìn)先出”堆棧操作特點,因此可用一個堆棧來進(jìn)行判斷。順序掃描算術(shù)表達(dá)式(表現(xiàn)為一個字符串);當(dāng)遇到三種類型的左括號時,該括號進(jìn)棧;當(dāng)遇到某一種類型的右括號時,比較當(dāng)前棧頂括號是否與之匹配,若匹配則退棧,繼續(xù)進(jìn)行判斷;若不匹配,則左右括號配對次序不正確,結(jié)束。若字符串當(dāng)前為某一類型的右括號而堆棧為空,則右括號多于左括號,結(jié)束。若字符串掃描結(jié)束而堆棧非空,則左括號多于右括號,結(jié)束。若字符串掃描結(jié)束而堆棧為空,則左右括號匹配正確,結(jié)束。,.,第四節(jié)棧的應(yīng)用舉例,#include #include #include using namespace std;bool brackMatch(string str) /括號匹配 int i = 0;stack stk; / 使用C+的stack類while(istr.size() if(stri=(|stri=|stri=) /出現(xiàn)三種左括號之一壓棧;否則進(jìn)行匹配判斷 stk.push(stri); else if(stri=)|stri=|stri=) /遇到右括號,判斷棧頂元素是否為左括號,如不為匹配的左括號,括號不匹配;否則出棧 if(stri=) / 左括號多于右括號,.,四、迷宮求解,24,第四節(jié)棧的應(yīng)用舉例,迷宮求解一般采用“窮舉法”逐一沿順時針方向查找相鄰塊(一共四塊東(右)、南(下),西(左)、北(上))是否可通,即該相鄰塊既是通道塊,且不在當(dāng)前路徑上用一個棧來記錄已走過的路徑,.,四、迷宮求解,25,第四節(jié)棧的應(yīng)用舉例,.,四、迷宮求解(算法),第四節(jié)棧的應(yīng)用舉例,設(shè)定當(dāng)前位置為入口位置do 若當(dāng)前位置可通,則 將該位置插入棧頂(Push); 若該位置是出口,則結(jié)束 否則切換當(dāng)前位置的相鄰方塊為當(dāng)前位置; 否則 若棧不空則 如棧頂位置四周均不可通,則刪除棧頂位置(Pop),并重 新測試新的棧頂位置 如找到棧頂位置的下一方向未經(jīng)探索,則將該方向方 塊設(shè)為當(dāng)前位置 while(棧不空);找不到路徑;,.,第四節(jié)棧的應(yīng)用舉例,四、迷宮求解(舉例) 入口int mgm+1n+1= 1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1; 出口,.,第四節(jié)棧的應(yīng)用舉例,求解結(jié)果:迷宮路徑: (1,1) (1,2) (2,2) (3,2) (3,1) (4,1)(5,1) (5,2) (5,3) (6,3) (6,4) (6,5) (5,5) (4,5) (4,6) (4,7) (3,7) (3,8)(4,8) (5,8) (6,8) (7,8) (8,8),.,五、表達(dá)式求值,29,第四節(jié)棧的應(yīng)用舉例,表達(dá)式由操作數(shù)、運(yùn)算符和界限符組成,它們皆稱為單詞操作數(shù):常數(shù)或變量運(yùn)算符:+, -, *, / 等界限符:(, ), #(表達(dá)式開始及結(jié)束符),.,五、表達(dá)式求值,30,第四節(jié)棧的應(yīng)用舉例,設(shè)置兩個棧:操作數(shù)棧(OPND)運(yùn)算符棧(OPTR),.,五、表達(dá)式求值,31,第四節(jié)棧的應(yīng)用舉例,運(yùn)算符的優(yōu)先級關(guān)系,新運(yùn)算符,運(yùn)算符棧頂元素,.,五、表達(dá)式求值(算法),第四節(jié)棧的應(yīng)用舉例,置運(yùn)算符棧(OPTR)和操作數(shù)棧(OPND)為空#插入OPTR棧;取表達(dá)式第一個單詞;while(單詞 或 OPTR棧頂元素不為#) 若單詞是操作數(shù),則插入OPND棧頂,取下一個單詞否則 OPTR棧頂元素優(yōu)先級與新運(yùn)算符優(yōu)先級關(guān)系為:小于,則插入OPTR棧頂,取下一單詞等于,則刪除OPTR棧頂元素,取下一單詞大于,則從OPND棧頂依次取出兩個操作數(shù),用從OPTR棧頂取出的元素進(jìn)行計算,結(jié)果插入OPND棧頂 ,從棧頂取出元素,包括取值及刪除棧頂元素兩個過程,.,第四節(jié)棧的應(yīng)用舉例,舉例1:求算術(shù)表達(dá)式1+2*3-4/2的值 計算順序(1)2*3 (2)1+6 (3)4/2 (4)7-2,.,第四節(jié)棧的應(yīng)用舉例,步驟 OPTR OPND 輸入字符 棧操作 # 1+2*3-4/2# PUSH(OPND,1 ) # 1 +2*3-4/2# PUSH(OPTR,+ ) #+ 1 2*3-4/2# PUSH(OPND,2 ) #+ 1 2 *3-4/2# PUSH(OPTR,*) #+* 1 2 3-4/2# PUSH(OPND,3 ) #+* 1 2 3 -4/2# operate(2,*,3) #+ 1 6 -4/2# operate(1,+,6) # 7 -4/2# PUSH(OPTR,- ) # - 7 4/2# PUSH(OPND,4 ) #- 7 4 /2# PUSH(OPTR,/ ) #-/ 7 4 2# PUSH(OPND,2 ) #-/ 7 4 2 # operate(4,/,2) #- 7 2 # operate(7,-,2) # 5 # return(TOP(OPND),.,舉例2:寫出表達(dá)式5+(6-4/2)*3的計算過程,最后的結(jié)果T4,置于OPRD的棧頂。,.,第四節(jié)棧的應(yīng)用舉例,表達(dá)式求值算法: coutinput an expression (Ending with #)”next; /p指向新的隊頭結(jié)點T data = front-data;/保存原隊頭結(jié)點的data域值delete front;/釋放原隊頭結(jié)點空間front = p;/front指向新的隊頭結(jié)點count-;/計數(shù)器減1return data;/返回原隊頭結(jié)點的data域值,.,隊列應(yīng)用舉例,實例: 編寫判斷一個字符序列是否回文的函數(shù). 回文:一個字符序列以中間字符為基準(zhǔn)且兩邊字符 完全相同。 算法描述:字符數(shù)組中存放要判斷的字符串。 把字符數(shù)組中字符逐個分別存入一個隊列和一個堆棧 逐個出隊列和退棧并比較出隊列的字符和退棧的字符是否相等,若全部相等則該字符序列是回文,否則就不是回文。,.,隊列應(yīng)用舉例,const int MaxQueueSize = 10;const int MaxStackSize = 10;typedef char DataType; /構(gòu)造一個順序循環(huán)隊列,一個順序棧void HuiWen(char str) /判斷字符串str是否是回文SeqStack myStack;SeqQueue myQueue;int n = strlen(str); /求字符串長度for(int i = 0; i n; i+)myQueue. EnQueue(stri);myStack.Push(stri); while(myQueue.NotEmpty() ,.,隊列應(yīng)用舉例,void main(void)char str1 = ABCDEDCBA;char str2 = ABCDEDBAC;cout 字符串ABCDEDCBA;HuiWen(str1);cout next=s. Bs-next=top-next;top-next=s.Ctop-next=s;top=s. Ds-next=top; top=top-next.8. 從棧頂指針為top的鏈棧中刪除一個結(jié)點,并將被刪結(jié)點的值保存到x中,其操作步驟為()。Ax=top-data; top=top-next; Btop=top-next; x=top-data;Cx=top; top=top-next; Dx=top-data.,.,練 習(xí),9. 鏈棧和順序棧相比,有一個較明顯的優(yōu)點是()。A通常不會出現(xiàn)棧滿的情況 B通常不會出現(xiàn)??盏那闆rC插入操作更加方便 D刪除操作更加方便10. 設(shè)數(shù)組Am作為循環(huán)隊列sq的存儲空間,front為隊頭指針,rear為隊尾指針,則執(zhí)行入隊操作操作修改指針的是()Asq.front=(sq.front+1)%m Bsq.front=(sq.front+1)%(m+1)Csq.rear=(sq.rear+1)%m Dsq.rear=(sq.rear+1)%(m+1)11、在一個鏈隊列中,若f,r分別為隊首、隊尾指針,則插入s所指結(jié)點的操作為()。Af-next=c;f=s; Br-next=s;r=s;Cs-next=r;r= s Ds-next=f;f=s;,.,隊列應(yīng)用舉例,課堂練習(xí):報數(shù)問題有10個人站一排隊,從左向右編號:1-10號現(xiàn)從左向右報數(shù)”1,2,1,2,1,2,1,2,1,2”,要求報數(shù)1的人出列,報數(shù)2的人立即站到隊尾,直到所有的人都出列,給出人們的出列順序算法.,- 1.請仔細(xì)閱讀文檔,確保文檔完整性,對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
10 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計者僅對作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 深圳大學(xué) 數(shù)據(jù)結(jié)構(gòu) 2017 隊列 演示 文檔
鏈接地址:http://ioszen.com/p-359908.html