栈与队列应用

《栈与队列应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、夭津理工丸学卖验报告学院（系）名称：计算机与通信工程学院姓名段斌学号20101959专业计算机科学与技术班级2班实验项目栈与队列应用课程名称数据结构课程代码实验时间2012年3月23日2：00-3：40pm实验地点7—215批改意见成绩实验目的：理解栈和队列的逻辑特点；掌握栈和队列基木操作的实现，并能达到在实际问题背景下的灵活运用栈或队列结构解决问题的程度。具体实验题目：每位同学完成下面1-2个题目：十进制数与N进制数据的转换1）问题描述：将从键盘输入的十进制数转换为N（如二进制、八进制、十六进制）进制数据。2）要求：利用顺序栈实现数制转换问题算术表达式求值算法1）问题描述：从键盘输入一个

2、算术表达式并输11!它的结果2）要求：算术表达式可包含加、减、乘、除、十进制整数和小括号，利用栈实现（1）算法设计思路将十进制数N转换为r（「取值2〜9）进制的数，其转换方法采用逐次除以基数I•取余法，直至商等于0为止。釆用这种方法，转换所得的I■进制数将按低位到高位的顺序产生，而通常数的输出形式是从高位到低位进行的，恰好与计算过程相反，因此转换过程中每得到一位[进制数则进栈保存，转换完毕后依次出栈，这样正好是转换结果。（2）算法基本思想如下：1）若N=（）,将栈s的内容依次111栈，算法结束。若NHO,则将N%i•压入栈s中。2）用N/r代替N,返冋（1）继续执行。（3）程序代码如下：#

3、include#include#defineStacklnitSize100typedefintStackElementType;typedefstruct{StackElementTypedata[StackInitSize];inttop;[SeqStack;SeqStack*InitStack（）{SeqStack*s;s=（SeqStack*）malloc（sizeof（SeqStack））;if（s!=NULL）{s->top=-1;returns;elseprintfC*没有足够内存空间，申请失败，程序运行终止。“）;exit(O);i

4、ntlsEmpty(SeqStack*s){return(s->top==-l)?1:0;}voidPush(SeqStack*s,StackElementTypex){if(s->top==StackInitSize){printfC1栈满！栈发生上溢，程序运行终止！”);exit(O);}else{s->top++;s->data[s->top]=x;}return;}StackElementTypePop(SeqStack*s){StackElementTypetemp;if(IsEmpty(s)){printfC栈空！栈发生下溢，程序运行终止！『)；exit(O);}else

5、{temp=s->data[s->topl;s->top—;returntemp;}}voidconversion(intN,intr){SeqStack*s;StackElementTypex;s=InitStack();while(N)Push(s,N%r);N=N/r;}while(!IsEmpty(s)){x=Pop(s);printf(”％d”,x);}printf(,,H);}voidmain()intN,r;printf("输入十进制整数：”)；scanf(“％d”,&N);printf(H输入数字转换基数(2〜9)：”)；scanf(”％d“,&r);printfCli

6、t制数％d转换为％cl进制数结果：”,Nj);conversion(N,r);（4）输出结果:"D:^4«^：^MSDev98MyPrpjectslDebugl.exe"锁入十进制整数：99予进制数99转质菊8进制数结果：丄43Pi'essanykeytocontinue—（5）问题与解决办法：函数的类型与返冋值类型不一致导致错误函数的返回形参定义出错误导致返回的还是原来的空值回文判断时入栈元素知道&,出栈元素首先与数组中的下一元素比较数组的位序要把握清楚（1）算法设计框图：（2）算法基本思想：求值表达式需要按级数由高到低运算，解决方法是，1）需要两个栈：对象栈OPND和算符栈

7、OPTR。2）自左至右扫描表达式，若当前字符是运算对象，入OPND栈。3）若当前字符值运算符，并且该运算符比算符栈OPTR的栈顶运算符优先级高，则该运算符入OPTR栈，继续向后处理。若该运算符比OPTR栈顶运算符优先级低则从OPND栈出栈两个运算对象，从OPTR栈出栈一个运算符进行运算，并将其运算结果入OPND栈中，继续处理当前字符，直到遇到结束符（以#作为表达式的结朿标志）。（3）程序代码如下:#include