數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用

數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用.專業(yè)資料.《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗報告數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用全文共9頁，當(dāng)前為第1頁。實(shí)驗序號：4實(shí)驗項目名稱：棧的操作數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用全文共9頁，當(dāng)前為第1頁。學(xué)號1407022228姓名王元專業(yè)、班網(wǎng)絡(luò)工程2班實(shí)驗地點(diǎn)1-314指導(dǎo)教師林仙麗實(shí)驗時間一、實(shí)驗?zāi)康募耙?.熟悉棧的基本概念；2.掌握棧的順序存儲結(jié)構(gòu)；3．掌握棧的應(yīng)用。二、實(shí)驗設(shè)備（環(huán)境）及要求微型計算機(jī)；windows操作系統(tǒng)；MicrosoftVisualStudio6.0集成開發(fā)環(huán)境。三、實(shí)驗內(nèi)容與步驟1.棧的順序表表示和實(shí)現(xiàn)的如下：#include<iostream>#defineMaxSize100usingnamespacestd;typedefintElemType;typedefstruct{ ElemTypedata[MaxSize]; inttop;}SqStack;voidInitStack(SqStack*st)//初始化棧{ st->top=-1;}intStackEmpty(SqStack*st)//判斷棧為空{(diào) return(st->top==-1);}voidPush(SqStack*st,ElemTypex)//元素進(jìn)棧{ if(st->top==MaxSize-1) { printf("棧上溢出!\n"); } else { st->top++;//移動棧頂位置 st->data[st->top]=x;//元素進(jìn)棧 }}voidPop(SqStack*st,ElemType*e)//出棧{ if(st->top==-1) { printf("棧下溢出\n"); } else { *e=st->data[st->top];//元素出棧 st->top--;//移動棧頂位置 }}intmain(){ SqStackL; SqStack*st=&L; ElemTypee; inti; InitStack(st); for(i=1;i<10;++i) { Push(st,i); printf("入棧元素是：%d\n",i); } for(i=1;i<10;++i) { Pop(st,e); printf("出棧元素是：%d\n",e); } 數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用全文共9頁，當(dāng)前為第2頁。數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用全文共9頁，當(dāng)前為第2頁。}改寫以上程序，實(shí)現(xiàn)功能如下：調(diào)用棧操作函數(shù)實(shí)現(xiàn)判別一個算術(shù)表達(dá)式中的圓括號和方括號配對是否正確匹配。2.C/C++的庫函數(shù)中已經(jīng)實(shí)現(xiàn)了棧，實(shí)例如下：#include<stack>//引入棧usingnamespacestd;intmain(){ inta; stack<int>s; scanf("%d",&a); s.push(a);//入棧 printf("%d\n",s.top());//取得棧頂元素輸出 s.pop();//出棧 return0;}請根據(jù)以上程序，設(shè)計算法如下：判別一個算術(shù)表達(dá)式中的圓括號配對是否正確。分析與討論1.數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用全文共9頁，當(dāng)前為第3頁。數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用全文共9頁，當(dāng)前為第3頁。對上機(jī)實(shí)踐結(jié)果進(jìn)行分析，上機(jī)的心得體會。五、教師評語簽名：日期：成績附源程序清單：1.#include<iostream>#defineMaxSize100usingnamespacestd;typedefcharElemType;typedefstruct{ ElemTypedata[MaxSize]; inttop;}SqStack;voidInitStack(SqStack*st)//初始化棧{ st->top=-1;}intStackEmpty(SqStack*st)//判斷棧為空{(diào) return(st->top==-1);}voidPush(SqStack*st,ElemTypex)//元素進(jìn)棧數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用全文共9頁，當(dāng)前為第4頁。數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用全文共9頁，當(dāng)前為第4頁。 if(st->top==MaxSize-1) { printf("棧上溢出!\n"); } else { st->top++;//移動棧頂位置 st->data[st->top]=x;//元素進(jìn)棧 }}voidPop(SqStack*st,ElemType*e)//出棧{ if(st->top==-1) { printf("棧下溢出\n"); } else { *e=st->data[st->top];//元素出棧 st->top--;//移動棧頂位置 }}intmain(){ SqStackL; SqStack*st=&L; ElemTypee,a[MaxSize]; inti,j=1,k; do{ InitStack(st); gets(a); for(i=0;a[i]!='\0';i++) { if(a[i]=='('||a[i]=='{'||a[i]=='[')//左括號入棧 Push(st,a[i]); if(a[i]==')') { if(StackEmpty(st)==1)//判斷棧是否為空 { printf("多了“(”，不匹配\n"); break;數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用全文共9頁，當(dāng)前為第5頁。數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用全文共9頁，當(dāng)前為第5頁。 else if('('==st->data[st->top])//匹配成功出棧 Pop(st,&e); else { printf("%c不匹配\n",a[i]); break; } } if(a[i]=='}') { if(StackEmpty(st)==1)//判斷棧是否為空 { printf("多了“}”，不匹配\n"); break; } else if('{'==st->data[st->top])//匹配成功出棧 Pop(st,&e); else { printf("%c不匹配\n",a[i]); break; } } if(a[i]==']') { if(StackEmpty(st)==1)//判斷棧是否為空 { printf("多了“]”，不匹配\n"); break; } else if('['==st->data[st->top])//匹配成功出棧 Pop(st,&e); else { printf("%c不匹配\n",a[i]); break; } } }數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用全文共9頁，當(dāng)前為第6頁。數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用全文共9頁，當(dāng)前為第6頁。 printf("匹配成功\n"); else printf("匹配不成功，多了%c。\n",st->data[st->top]); printf("是否繼續(xù)匹配括號：（繼續(xù)不要按“#”）\n"); scanf("%c",&e); k=getchar();//這是為了輸入e時會敲回車鍵而加上去的 }while(e!='#');}2.（1）#include<stack>//引入棧usingnamespacestd;intmain(){ inta,i; charb[50]; stack<char>s;//聲明了一個char型的棧,括號里面的可以改為任何基本類型 gets(b); for(i=0;b[i]!='\0';i++) { if(b[i]=='('||b[i]=='[') { s.push(b[i]); }//如果為"（"或者是"["，就入棧 if(b[i]==')') { if(s.empty()==1)//s.empty是判斷函數(shù)，若無棧頂元素就會返回1，表明棧為空，否則就會返回0 { printf("不匹配\n"); break; } if(s.top()=='(')//判斷是否符合出棧的條件 { s.pop();//匹配就會出棧 } else { printf("不匹配\n"); break; } } if(b[i]==']')數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用全文共9頁，當(dāng)前為第7頁。數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用全文共9頁，當(dāng)前為第7頁。 if(s.empty()==1)//判斷棧是否為空 { printf("不匹配\n"); break; } if(s.top()=='[') { s.pop(); } else { printf("不匹配\n"); break; } } } if(s.empty()==1&&b[i]=='\0')//調(diào)用函數(shù)，判斷棧是否已經(jīng)為空或者數(shù)組的右括號已經(jīng)匹配完成 printf("匹配成功\n"); if(s.empty()==0)//b[i]已經(jīng)比較完了，但是若是棧里元素沒有出棧，就不能說是匹配完全printf("匹配不成功\n"); return0;}（2）#include"iostream"#include<stack>//引入棧usingnamespacestd;intmain(){ inta; stack<char>s;//申請一個char型的棧 printf("輸入回車鍵結(jié)束入棧\n"); while((a=getchar())!='\n')//一個一個的讀入并匹配，若不匹配就跳出 { switch(a)//swith是一種條件語句 { case'[': case'(': s.push(a); continue;//[或(就進(jìn)棧 case')':數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用全文共9頁，當(dāng)前為第8頁。 case']':數(shù)據(jù)結(jié)構(gòu)棧的應(yīng)用全文共9頁，當(dāng)前為第8頁。 if(s.empt