深圳大學-數(shù)據(jù)結構-2017棧和隊列演示文檔
《深圳大學-數(shù)據(jù)結構-2017棧和隊列演示文檔》由會員分享,可在線閱讀,更多相關《深圳大學-數(shù)據(jù)結構-2017棧和隊列演示文檔(63頁珍藏版)》請在裝配圖網(wǎng)上搜索。
.,第三章棧和隊列,,,數(shù)據(jù)結構,.,一、棧,2,第一節(jié) 棧,棧是限定僅在表尾(top)進行插入或刪除操作的線性表。 允許插入和刪除的一端稱為棧頂(top,表尾),另一端稱為棧底(bottom,表頭) 特點:后進先出 (LIFO),.,二、棧的實現(xiàn),3,第一節(jié) 棧,棧的存儲結構主要有兩種: 1. 順序棧 2. 鏈式棧,.,一、順序棧,4,第二節(jié) 順序棧,順序棧是棧的順序存儲結構 利用一組地址連續(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ù)關系:R = { | ai-1,ai∈D} 基本操作: Status InitStack(SqStack &S) // 構造空棧 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) //構造頭結點 {next = ptrNext;} StackNode(const T,第三節(jié) 鏈棧,.,第三節(jié) 鏈棧,2.創(chuàng)建鏈式堆棧類 template class LinStack { private: StackNode *head; //頭指針 int size; //數(shù)據(jù)元素個數(shù) public: LinStack(void); //構造函數(shù) ~LinStack(void);//析構函數(shù) void Push(const T,.,第三節(jié) 鏈棧,3.鏈式堆棧的實現(xiàn) template LinStack::LinStack() //構造函數(shù) { head = new StackNode;//頭指針指向頭結點 size = 0; //size的初值為0 } template LinStack::~LinStack(void) //析構函數(shù) { StackNode *p, *q; //釋放所有動態(tài)申請的結點空間 p = head; //p指向頭結點 while(p != NULL) //循環(huá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 //元素個數(shù)加1 },.,第三節(jié) 鏈棧,template T LinStack::Pop(void) //出棧 { if(size == 0) { cout *p = head->next;//p指向棧頂元素結點 T data = p->data; head->next = head->next->next; //原棧頂元素結點脫鏈 delete p; //釋放原棧頂結點空間 size--; //結點個數(shù)減1 return data; //返回原棧頂結點的data域值 },.,第三節(jié) 鏈棧,template T LinStack::GetTop(void)const //取棧頂元素 { return head->next->data; },.,一、數(shù)值轉換,18,第四節(jié) 棧的應用舉例,將十進制轉換為其它進制(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ù)值轉換,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]:對用戶輸入的一行字符進行處理,直到行結束(“\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ù)臈茸址麄魉偷秸{用過程的數(shù)據(jù)區(qū); … },.,第四節(jié) 棧的應用舉例,三.括號匹配 假設一個算術表達式中包括( )、[ ]和{ }三種形式的括號,設計一個判別表達式中括號是否正確匹對的程序。 1.算法思想: 算術表達式中右括號和左括號匹配的次序:后到括號要最先被匹配的“后進先出”堆棧操作特點,因此可用一個堆棧來進行判斷。 順序掃描算術表達式(表現(xiàn)為一個字符串); 當遇到三種類型的左括號時,該括號進棧; 當遇到某一種類型的右括號時,比較當前棧頂括號是否與之匹配,若匹配則退棧,繼續(xù)進行判斷; 若不匹配,則左右括號配對次序不正確,結束。 若字符串當前為某一類型的右括號而堆棧為空,則右括號多于左括號,結束。 若字符串掃描結束而堆棧非空,則左括號多于右括號,結束。 若字符串掃描結束而堆棧為空,則左右括號匹配正確,結束。,.,第四節(jié) 棧的應用舉例,#include #include #include using namespace std; bool brackMatch(string str) //括號匹配 { int i = 0; stack stk; // 使用C++的stack類 while(i- 配套講稿:
如PPT文件的首頁顯示word圖標,表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設計者僅對作品中獨創(chuàng)性部分享有著作權。
- 關 鍵 詞:
- 深圳大學 數(shù)據(jù)結構 2017 隊列 演示 文檔
裝配圖網(wǎng)所有資源均是用戶自行上傳分享,僅供網(wǎng)友學習交流,未經(jīng)上傳用戶書面授權,請勿作他用。
鏈接地址:http://www.hcyjhs8.com/p-359908.html