深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017棧和隊(duì)列演示文檔

《深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017棧和隊(duì)列演示文檔》由會(huì)員分享，可在線閱讀，更多相關(guān)《深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017棧和隊(duì)列演示文檔（63頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

.,第三章棧和隊(duì)列,,,數(shù)據(jù)結(jié)構(gòu),.,一、棧,2,第一節(jié)　棧,棧是限定僅在表尾(top)進(jìn)行插入或刪除操作的線性表。 允許插入和刪除的一端稱為棧頂(top，表尾)，另一端稱為棧底(bottom，表頭) 特點(diǎn)：后進(jìn)先出 (LIFO),.,二、棧的實(shí)現(xiàn),3,第一節(jié)　棧,棧的存儲(chǔ)結(jié)構(gòu)主要有兩種： 1. 順序棧 2. 鏈?zhǔn)綏?.,一、順序棧,4,第二節(jié)　順序棧,順序棧是棧的順序存儲(chǔ)結(jié)構(gòu) 利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素 指針top指向棧頂元素在順序棧中的下一個(gè)位置， base為棧底指針，指向棧底的位置。,.,二、順序棧的定義,5,第二節(jié)　順表?xiàng)?采用C語(yǔ)言中動(dòng)態(tài)分配的一維數(shù)組表示順序表,#define STACK_INIT_SIZE 100 //棧存儲(chǔ)空間的初始分配量 #define STACKINCREMENT 10 //棧存儲(chǔ)空間的分配增量 typedef struct { SElemType *base //存儲(chǔ)空間基址 SElemType *top; //棧頂指針 int stacksize; //當(dāng)前分配的存儲(chǔ)容量(元素?cái)?shù)) } SqStack;,.,三、順序棧的特性,6,第二節(jié)　順序棧,top==0 或top==base 表示空棧 base=NULL表示棧不存在 當(dāng)插入新的棧頂元素時(shí),指針top+1 刪除棧頂元素時(shí)，指針top-1 當(dāng)top>stacksize時(shí)，棧滿，溢出,.,四、順序棧的主要操作,7,第二節(jié)　順序棧,ADT Stack { 數(shù)據(jù)對(duì)象：D = {ai | ai∈ElemSet, i=1,2,3,…,n} 數(shù)據(jù)關(guān)系：R = { | ai-1,ai∈D} 基本操作： 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é)點(diǎn)類(lèi) template class LinStack;//前視定義,否則友元無(wú)法定義 template //模板類(lèi)型為T(mén) class StackNode { friend class LinStack; //定義類(lèi)LinStack為友元 private: T data; //數(shù)據(jù)元素 StackNode *next; //指針 public: StackNode(StackNode *ptrNext = NULL) //構(gòu)造頭結(jié)點(diǎn) {next = ptrNext;} StackNode(const T,第三節(jié)　鏈棧,.,第三節(jié)　鏈棧,2.創(chuàng)建鏈?zhǔn)蕉褩ｎ?lèi) template class LinStack { private: StackNode *head; //頭指針 int size; //數(shù)據(jù)元素個(gè)數(shù) public: LinStack(void); //構(gòu)造函數(shù) ~LinStack(void);//析構(gòu)函數(shù) void Push(const T,.,第三節(jié)　鏈棧,3.鏈?zhǔn)蕉褩５膶?shí)現(xiàn) template LinStack::LinStack() //構(gòu)造函數(shù) { head = new StackNode;//頭指針指向頭結(jié)點(diǎn) size = 0; //size的初值為0 } template LinStack::~LinStack(void) //析構(gòu)函數(shù) { StackNode *p, *q; //釋放所有動(dòng)態(tài)申請(qǐng)的結(jié)點(diǎn)空間 p = head; //p指向頭結(jié)點(diǎn) while(p != NULL) //循環(huán)釋放結(jié)點(diǎn)空間 { 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 //元素個(gè)數(shù)加1 },.,第三節(jié)　鏈棧,template T LinStack::Pop(void) //出棧 { if(size == 0) { cout *p = head->next;//p指向棧頂元素結(jié)點(diǎn) T data = p->data; head->next = head->next->next; //原棧頂元素結(jié)點(diǎn)脫鏈 delete p; //釋放原棧頂結(jié)點(diǎn)空間 size--; //結(jié)點(diǎn)個(gè)數(shù)減1 return data; //返回原棧頂結(jié)點(diǎn)的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)算過(guò)程如下： N N /8 N mod 8 1348 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); // 輸入一個(gè)十進(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)用舉例,用戶輸入一行字符 允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)，可以用退格符“#”及時(shí)更正 假設(shè)從終端接受兩行字符： whli##ilr#e（s#*s) 實(shí)際有效行為： while (*s),.,二、行編輯程序,21,第四節(jié)　棧的應(yīng)用舉例,[例2]:對(duì)用戶輸入的一行字符進(jìn)行處理,直到行結(jié)束(“\n”) void LineEdit() { InitStack(s); ch = getchar(); //從終端接受一個(gè)字符 while (ch != ’\n’) { switch(ch) { case ’#’ : Pop(S, c);break; // 僅當(dāng)棧非空時(shí)退棧 case ‘@’: ClearStack(S); break; default: Push(S, ch); break; // 有效字符進(jìn)棧 } ch = getchar(); // 從終端接受一個(gè)字符 } //將從棧底到棧頂?shù)臈?nèi)字符傳送到調(diào)用過(guò)程的數(shù)據(jù)區(qū); … },.,第四節(jié)　棧的應(yīng)用舉例,三.括號(hào)匹配 假設(shè)一個(gè)算術(shù)表達(dá)式中包括( )、[ ]和{ }三種形式的括號(hào)，設(shè)計(jì)一個(gè)判別表達(dá)式中括號(hào)是否正確匹對(duì)的程序。 1.算法思想： 算術(shù)表達(dá)式中右括號(hào)和左括號(hào)匹配的次序:后到括號(hào)要最先被匹配的“后進(jìn)先出”堆棧操作特點(diǎn)，因此可用一個(gè)堆棧來(lái)進(jìn)行判斷。 順序掃描算術(shù)表達(dá)式（表現(xiàn)為一個(gè)字符串）； 當(dāng)遇到三種類(lèi)型的左括號(hào)時(shí)，該括號(hào)進(jìn)棧； 當(dāng)遇到某一種類(lèi)型的右括號(hào)時(shí)，比較當(dāng)前棧頂括號(hào)是否與之匹配，若匹配則退棧，繼續(xù)進(jìn)行判斷； 若不匹配，則左右括號(hào)配對(duì)次序不正確，結(jié)束。 若字符串當(dāng)前為某一類(lèi)型的右括號(hào)而堆棧為空，則右括號(hào)多于左括號(hào)，結(jié)束。 若字符串掃描結(jié)束而堆棧非空，則左括號(hào)多于右括號(hào)，結(jié)束。 若字符串掃描結(jié)束而堆棧為空，則左右括號(hào)匹配正確，結(jié)束。,.,第四節(jié)　棧的應(yīng)用舉例,#include #include #include using namespace std; bool brackMatch(string str) //括號(hào)匹配 { int i = 0; stack stk; // 使用C++的stack類(lèi) while(inext; //p指向新的隊(duì)頭結(jié)點(diǎn) T data = front->data; //保存原隊(duì)頭結(jié)點(diǎn)的data域值 delete front; //釋放原隊(duì)頭結(jié)點(diǎn)空間 front = p; //front指向新的隊(duì)頭結(jié)點(diǎn) count--; //計(jì)數(shù)器減1 return data; //返回原隊(duì)頭結(jié)點(diǎn)的data域值 },.,隊(duì)列應(yīng)用舉例,實(shí)例: 編寫(xiě)判斷一個(gè)字符序列是否回文的函數(shù). 回文:一個(gè)字符序列以中間字符為基準(zhǔn)且兩邊字符 完全相同。 算法描述: 字符數(shù)組中存放要判斷的字符串。 把字符數(shù)組中字符逐個(gè)分別存入一個(gè)隊(duì)列和一個(gè)堆棧 逐個(gè)出隊(duì)列和退棧并比較出隊(duì)列的字符和退棧的字符是否相等，若全部相等則該字符序列是回文，否則就不是回文。,.,隊(duì)列應(yīng)用舉例,const int MaxQueueSize = 10; const int MaxStackSize = 10; typedef char DataType; …… //構(gòu)造一個(gè)順序循環(huán)隊(duì)列,一個(gè)順序棧 void HuiWen(char str[]) //判斷字符串str是否是回文 { SeqStack myStack; SeqQueue myQueue; int n = strlen(str); //求字符串長(zhǎng)度 for(int i = 0; i < n; i++) { myQueue. EnQueue(str[i]); myStack.Push(str[i]); } while(myQueue.NotEmpty() },.,隊(duì)列應(yīng)用舉例,void main(void) { char str1[] = {"ABCDEDCBA"}; char str2[] = {"ABCDEDBAC"}; cout << "字符串ABCDEDCBA"; HuiWen(str1); cout << "字符串ABCDEDBAC"; HuiWen(str2); },.,隊(duì)列應(yīng)用舉例,下標(biāo) I j pre 0 1 1 -1 1 1 2 0 2 2 1 0 3 2 2 1 4 3 1 2 5 3 2 3 6 4 1 4 7 3 3 5 8 5 1 6 9 3 4 7 10 5 2 8 11 6 1 8 12 2 4 9 13 5 3 10 14 7 1 11 15 1 4 12 16 2 5 12 17 6 3 13 18 1 5 15 19 2 6 16 20 6 4 17,0 1 2 3 4 5 6 7 8 9,0 1 2 3 4 5 6 7 8 9,.,隊(duì)列應(yīng)用舉例,下標(biāo) I j pre 1 6 18 6 5 20 5 5 22 7 5 22 4 5 23 5 6 23 8 5 24 4 6 25 5 7 26 8 6 27 4 7 28 5 8 29 6 7 29 8 7 30 3 7 31 4 8 31 6 8 32 8 8 34,迷宮求解結(jié)果： 迷宮路徑： (1,1) (2,1) (3,1) (4,1) (5,1) (5,2) (5,3) (6,3) (6,4) (6,5) (7,5) (8,5) (8,6) (8,7) (8,8),.,練 習(xí),1.若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少? 一個(gè)棧的入棧序列是abcde，則可能的出棧序列為: A.edcab B.decba C.debca D.cabde,.,練 習(xí),3. 假定用一維數(shù)組a[7]順序存儲(chǔ)一個(gè)循環(huán)隊(duì)列，隊(duì)首和隊(duì)尾指針?lè)謩e用front和rear表示，當(dāng)前隊(duì)列中已有5個(gè)元素：23，45，67，80，34，其中23為隊(duì)首元素，front的值為3，請(qǐng)畫(huà)出對(duì)應(yīng)的存儲(chǔ)狀態(tài)，當(dāng)連續(xù)做4次出隊(duì)運(yùn)算后，再讓15，36，48元素依次進(jìn)隊(duì)，再次畫(huà)出對(duì)應(yīng)的存儲(chǔ)狀態(tài)。 4. 表達(dá)式a*(b+c)-d的后綴表達(dá)式是 ？,.,練 習(xí),5. 設(shè)有一順序棧S,元素s1,s2,s3,s4,s5,s6依次進(jìn)棧,如果6個(gè)元素出棧的順序是s2，s3，s4，s6，s5，s1,則棧的容量至少應(yīng)該是（）。 A.2 B.3 C.4 D.5 6. 設(shè)已將元素a1，a2，a3依次入棧，元素a4正等待進(jìn)棧。那么下列4個(gè)序列中不可能出現(xiàn)的出棧序列是（）。 A．a(chǎn)3 a1 a4 a2 B．a(chǎn)3 a2 a4 a1 C． a3 a4 a2 a1 D．a(chǎn)4 a3 a2 a1,.,練 習(xí),7. 向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，其操作步驟為（）。 A．top->next=s. B．s->next=top->next;top->next=s. C．top->next=s;top=s. D．s->next=top; top=top->next. 8. 從棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn),并將被刪結(jié)點(diǎn)的值保存到x中,其操作步驟為（）。 A．x=top->data; top=top->next; B．top=top->next; x=top->data; C．x=top; top=top->next; D．x=top->data.,.,練 習(xí),9. 鏈棧和順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是（）。 A．通常不會(huì)出現(xiàn)棧滿的情況 B．通常不會(huì)出現(xiàn)?？盏那闆r C．插入操作更加方便 D．刪除操作更加方便 ? 10. 設(shè)數(shù)組A[m]作為循環(huán)隊(duì)列sq的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行入隊(duì)操作操作修改指針的是（） A．sq.front=(sq.front+1)%m B．sq.front=(sq.front+1)%(m+1) C．sq.rear=(sq.rear+1)%m D．sq.rear=(sq.rear+1)%(m+1) ? 11、在一個(gè)鏈隊(duì)列中，若f，r分別為隊(duì)首、隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為（）。 A．f->next=c;f=s; B．r->next=s;r=s; C．s->next=r;r= s D．s->next=f;f=s;,.,隊(duì)列應(yīng)用舉例,[課堂練習(xí)]:報(bào)數(shù)問(wèn)題 有10個(gè)人站一排隊(duì),從左向右編號(hào):1-10號(hào) 現(xiàn)從左向右報(bào)數(shù)”1,2,1,2,1,2,1,2,1,2”, 要求報(bào)數(shù)1的人出列,報(bào)數(shù)2的人立即站到隊(duì) 尾,直到所有的人都出列,給出人們的出列順 序算法.,