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

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