数据结构栈.ppt
《数据结构栈.ppt》由会员分享,可在线阅读,更多相关《数据结构栈.ppt(30页珍藏版)》请在第壹文秘上搜索。
1、顺序栈的数据结构表示顺序栈的数据结构表示 #define maxsize 栈的大小栈的大小; struct stack1 int astack_size; int t; stack1 s;3526例1:1,2,3,4,5 例2:5,4,3,2,1 例3:3,2,4,5,1 例4:3,1,4,5,2 C A B 入栈:1,2,3,4,5 no; yes; yes; yes; 设设f(n)表示有表示有n节车厢的出站的方法数节车厢的出站的方法数 那么那么,第第1节车厢显然有进栈和不进栈两种方法节车厢显然有进栈和不进栈两种方法. 不进栈的方法为不进栈的方法为f(n-1) 进栈的方法数进栈的方法数,可以
2、归结为元素可以归结为元素1第第i次出栈的所有可能性。次出栈的所有可能性。 元素元素1排列在第排列在第i个位置,那么将整个序列分裂为个位置,那么将整个序列分裂为2i,1,i+1n 两个部分。显然方法数为两个部分之积,如下:两个部分。显然方法数为两个部分之积,如下:nfinfif21)0(),(*) 1(其中nfinfifnf21)0(),(*) 1()(其中 char a9= ,(,),; cinst;x=true;k=0; len=st.length(); for(j=0;jlen;j+) for(w=1;w=8;w+) if(stj=aw)break; if(ww)coutNOendl;x=
3、false;break; else k+;ck=w;/入栈入栈 else if(ck+w!=9)coutNOendl;x=false;break; else k-;/出栈出栈 if(x=true) if(k=0)coutYESendl; else coutNOendl;Description:由键盘输入一个算术表达式,该表达式由数字,加(+)、减(-)、乘(*)、求商(/)运算符及小括号组成。 例如:6+8*(5-5*(26-1)/2+7) 请编一程序,若输入的表达式的值。 Input:输入一个算术表达式(表达式的长度小于255,输入数字的值 int compare_PRI(char a,ch
4、ar b) /优先级比较,a:符号栈顶,b:将入栈符号 if(a=(&b=)return 0; /返回相等信息,则出栈,b丢弃左右括号相遇则两者消失 if(a=() return -1; /返回-1,则b入栈(优先级低于其它符号 if(b=)|a=/|b=+|b=-|a=b) return 1; /返回1,则用栈项a计算将处理的)低于其它符号,ab相等则b低 return -1;以以3*(7-2)为例为例,操作过程如下操作过程如下,构造操作符和操作数栈构造操作符和操作数栈int cal(int a,char mark,int b)/计算函数 switch (mark) case +: retu
5、rn a+b; case -: return a-b; case *: return a*b; case /: return a/b; int main() int temp,num250,numtop=-1,marktop=0,k; char mark250; string s; cins; mark0=(; s+=); while(ks.length() if(sk=0)/若当前要处理字符是数字若当前要处理字符是数字 temp=0;/将连续的数字字符转换成数压入数字栈将连续的数字字符转换成数压入数字栈 while(sk=0&ks.length()temp=temp*10+sk+-0; nu
6、m+numtop=temp; continue; switch(compare_PRI(markmarktop,sk)/若不是数字则是符号,根据当前符号栈与当前若不是数字则是符号,根据当前符号栈与当前符号优先级比较结果处理符号优先级比较结果处理 case 1:/当前符号低,则用栈顶符号计算,并将符号栈顶出栈,数字栈出两个进一个当前符号低,则用栈顶符号计算,并将符号栈顶出栈,数字栈出两个进一个 numnumtop-1=cal(numnumtop-1,markmarktop,numnumtop);/计算计算 numtop-;/修改数字栈顶修改数字栈顶 marktop-;/修改符号栈顶修改符号栈顶
7、break; case 0: marktop-;k+;break;/相等,则符号栈出栈,栈顶减相等,则符号栈出栈,栈顶减1,扫描下一个字符,扫描下一个字符 case -1: mark+marktop=sk;k+;/优先级高则当前符号入栈,扫描下一个字符优先级高则当前符号入栈,扫描下一个字符 coutnum0st; int len=strlen(st); couttree(st,0,len-1); return 0;int poskh(char st,int right ,int p) /寻找字符串left到right区间内与p位置的(匹配的)的位置 int t=1;/sp是一个( p+;/从下
8、一个位置开始找 for(int i=p;i=left;i-) /从右到左扫描,主要因为减号和除号如3-2-1 应是(3-2)-1 而不是3-(2-1). if(sti=A&sti=a&sti=z) continue; if(sti=() t-;continue; if(sti=) t+;continue; if(sti=+|sti=-)&t=0) return i; if(t=0&k=0) k=i;/返回最右边的*、/号 return k; int isnum(char st,int left,int right)/判断字符串left到right区间是否是一个数,是则返回数值,否则返回1 in
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构