还剩7页未读,继续阅读
文本内容:
怀化学院计算机系《数据结构》实验报告书姓名郑乐成学号1206406011系部计算机工程系专业软件工程W6班指导老师及职称杨玉军讲师
一、实验目的实验二栈与队列的操作.掌握实现栈的基本操作方法1掌握栈的基本操作建栈,2等运算在顺序存储结构Push,Pop上的实现通过本次实习加深对高级语言运
3.语言的使用,熟悉串的基本算顺序结构上的实现C
二、实验要求进行栈的基本操作时要注意栈“后进先出”的特性
1.编写完整程序完成下面的实验内容并上机运行
2.整理并上交实验报告
3.
三、实验内容编写生成栈的函数,栈的元素从键盘输入
1.编写在栈中压入一个元素的函数
2.编写在栈中弹出一个元素的函数
3.编写主函数,调用以上各函数,以便能观察出各函数的屏幕输
4.出
四、实验步骤以及程序测试#includeiostream#includestring#define L1100#define L210typedef intElemType;using namespacestd;编写程序任意输入栈长度和栈中的元素值//
1.typedef structElemType*base;ElemType*top;int stacksize;}SqStack;//构造一个顺序栈int lnitStackSqStackSS.base=ElemType*mallocL1*sizeofElemType;if!S.basereturn0;S.top=S.base;S.stacksize=L1;return1;//清空、int ClearStackSqStackSifS.top!=S.base S.top=S.base;S.stacksize=O;}return1;销毁、int DestroyStackSqStackS//freeS.base;ifS.basereturn0;return1;//入栈int PushSqStackS,ElemType eifS.top-S.base=S.stacksizeS.base=ElemType*reallocS.base,S.stacksize+L2*sizeofElemType;if!S.basereturn0;S.top=S.base+S.stacksize;S.stacksize+=L2;*S.top++=e;return1;}〃出栈int PopSqStackS ElemTypee3ifS.top==S.basereturn0;e=*-S.top;return1;//取栈顶元素操作}ElemType GetTopSqStackSifS.top==S.basereturn NULL;//用来比较运算符优先级的return*S.top-1;};int Psrewcietcdhetochpar top,char e函数casecase价生//栈顶元素i[E[=+l|e==7|e==||e==#{return1;}优先,返回1〃栈顶元素没有优先权,返回以else{return-1;}-1卜相可I叫casecase7:,,ife=={return-1;else{return1;}case〃返回表示搭配括号ife=={return0;}0else{return-1;}case:return1;,1;case ife==#{return0;}else return-1ElemType OperateElemType a,ElemType theta,ElemType b//计算加减乘除switchthetacase43:return a+b;case45:return a-b;case42:return a*b;case47:return a/b;}double EvalExpressionstringexElemType a,b,theta;SqStackOPTR,OPND;设运算符栈InitStackOPTR;//OPTR运算数栈InitStackOPND;//OPND〃栈底PushOPTR,#;char ch=ex
[0];forint i=0;ch!=#||GetTopOPTR!=#;i++ElemType oprand=0;int j=10;判断是否是数字whileex[i]=48ex[i]=57//oprand=oprand*j+ex[i++]-48;if oprand!=0PushOPND,oprand;ch=ex[i];ifch=40chv=43||ch==T|ch==/||ch==#switchPrecedeGetTopOPTR,ch栈顶元素优先权-底-case-1://PushOPTR,ch;break;栈顶元素和为配对括号,脱掉case0://ex[i]PopOPTR,a;break;栈顶元素优先case1://PopOPTR,theta;PopOPND b;PopOPND a;55PushOPND,Operatea theta,b;Jbreak;}//switch}elsereturn0;}return GetTopOPND;int mainintn;string str;cin»n;whilen-cin»str;,1H Hdoubleresult=EvalExpressionstr+#;cout«str«=«result«endl;return0;■J G\Users\xiaocheng\Desktop\Debug\c.exe32*52*5=74*2*3-10/54+2*3-10/5=83*7-23*7-2=19Press anykey tocontinue
五、总结、程序中关于字符与数值之间的转换,是耗费我大量时间考虑的部份,我试图寻1觅一种更高效的方法来实现,然而我仍在学习中、这次实验用栈来求表达式值,让我更加熟悉了栈的特点及操作2
六、思量与提图如果一个程序中要用到两个栈,为了不发生上溢错误,就必须给每一个栈预先分配一个足够大的存储空间若每一个栈都预分配过大的存储空间,势必会造成系统空间紧张如何解决这个问题?答就像以上程序中预定义的事先给栈设置一个存储空间分配增量,当栈L1,L2,满的时候,使用函数扩大栈的空间realloc。