数据结构课程设计 栈和队列.doc

实验课程名称 数据结构与课程设计 专 业 班 级 10级计科（2）班 学 生 姓 名 赵 腾 松 学 号 10410902044 指 导 教 师 冯 韵 2012 至 2013学年第 1 学期第 3 至 4 周目录1 概述32 系统分析33 概要分析34 详细设计34.1 中缀表达式转换为后缀表达式算法设计34.2 后缀表达式算法设计95 程序代码106 运行与测试147总结与心得148 参考文献141 概述本次实验需要对栈和队列进行充分的了解虽然栈和队列实质上是不同的但在编写程序时大致相似。通常栈可以用顺序的方式存储分配一块连续的存储区域存放栈中元素并用一个变量指向当前的栈顶。而队列的顺序存储结构需要使用一个数组和两个整数型变量来实现。2 系统分析 栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。对于顺序栈入栈时首先判断栈是否为满栈满的条件为p-top= =MAXNUM-1栈满时不能入栈; 否则出现空间溢出引起错误这种现象称为上溢。 出栈和读栈顶元素操作先判栈是否为空为空时不能操作否则产生错误。通常栈空作为一种控制转移的条件。队列的顺序存储结构称为顺序队列顺序队列实际上是运算受限的顺序表。 入队时将新元素插入rear所指的位置然后将rear加1。出队时删去front所指的元素然后将front加1并返回被删元素。3 概要分析编写一个程序实现顺序栈的各种基本运算并在此基础上设计一个主程序完成如下功能：1初始化顺序栈；2插入元素；3删除栈顶元素；4取栈顶元素；5遍历顺序栈；6置空顺序栈。编写一个程序实现顺序队列的各种基本运算并在此基础上设计一个主程序完成如下功能：1初始化队列；2建立顺序队列；3入队；4出队；5判断队列是否为空；6取队头元素；7遍历队列。4 详细设计4.1 中缀表达式转换为后缀表达式算法设计 顺序扫描中缀表达式，当读到数字时直接将其送至输出队列中；当读到运算符时，将栈中所有优先级高于或等于该运算符的运算符弹出，送至输出队列中，再将当前运算符入栈；当读到左括号时，即入栈；当读到右括号时，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至输出队列，再删除栈中的左括号。具体算法如下：void CTPostExp(SeqQueue *Q)SeqStack OS; /运算符栈char c,t;SeqStack *S;S=&OS; InitStack(S); /初始化栈Push(S,#); /压入栈底元素#do /扫描中缀表达式 c=getchar();switch(c)case :break; /去除空格符case 0:case 1:case 2:case 3:case 4:case 5:case 6:case 7:case 8:case 9:EnQueue(Q,c); break;case(: Push(S,c); break;case ):case #:do t=Pop(S);if(t!=( & t!=#) EnQueue(Q,t); while(t!=( & S-top!=-1); break;case +:case -:case *:case /:while(Priority(c)=Priority(GetTop(S)t=Pop(S); EnQueue(Q,t);Push(S,c); break;/EndSwitchwhile(c!=#);/以#号结束表达式扫描 要执行上述算法，还必须给出相关的栈和队列的定义、操作以及调用该算法的主函数。 具体算法如下：#include#define StackSize 100#define QueueSize 100/*队列的相关操作*/typedef char DataType;typedef struct char data100;int front,rear;SeqQueue; /定义队列类型void InitQueue(SeqQueue * Q)/初始化队列Q-front=0; Q-rear=0;int QueueEmpty(SeqQueue * Q) /判空队列return Q-rear=Q-front;void EnQueue(SeqQueue * Q, DataType x) /入队列if(Q-rear+1)%QueueSize=Q-front)printf(Queue overflow);else Q-dataQ-rear=x;Q-rear=(Q-rear+1)%QueueSize; int DeQueue(SeqQueue *Q) return Q-dataQ-front+;/*栈的相关操作*/typedef struct DataType data100;int top;SeqStack; /栈类型的定义void InitStack(SeqStack * S) /初始化栈S-top=-1;void Push(SeqStack * S,DataType x) /入栈(进栈）if(S-top=StackSize-1)printf(stack overflow);else S-top=S-top+1;S-dataS-top=x;DataType Pop(SeqStack * S) /退栈出栈）if(S-top=-1)printf(stack underflow);elsereturn S-dataS-top-;DataType GetTop(SeqStack * S) /取栈顶元素if(S-top=-1)printf(stack empty);elsereturn S-dataS-top;/求运算符优先级函数int Priority(DataType op)switch(op) case (:case #:return(0);case -:case +:return(1);case *:case /:return(2); void main()SeqQueue *Q;SeqQueue PostQ; /定义队列，存放后缀表达式Q=&PostQ;InitQueue(Q); /初始化队列CTPostExp(Q); /调用转换函数将中缀表达式转换为后缀表达式while(!QueueEmpty(Q)/输出后缀表达式printf(%2c,DeQueue(Q);Q-front=0;printf(n);printf(求值结果为：%dn,CPostExp(Q); 表4-1 中缀表达式到后缀表达式的转换过程示例转换步骤中缀表达式的读入运算符栈OS后缀表达式Post（）初始9-（2+4*7）/5+3#空1-（2+4*7）/5+3#92（2+4*7）/5+3#-932+4*7）/5+3#-（94+4*7）/5+3#-（9 254*7）/5+3#-(+9 26*7）/5+3#-(+9 2 477）/5+3#-(+*9 2 48)/5+3#-(+*9 2 4 79/5+3#-9 2 4 7 * +105+3#-/9 2 4 7 * +11+3#-/9 2 4 7 * +5123#+9 2 4 7 * +5 / -13#+9 2 4 7 * +5 / - 314空9 2 4 7 * +5 / - 3 +4.2 后缀表达式算法设计 在计算后缀表达式时，最后保存的值是最先取出参与运算，所以要用到栈。利用前面生成的后缀表达式队列，很容易写出计算后缀表达式的算法。在算法中使用了VS栈来存储读入的操作和运算结果，因为在生成的后缀表达式队列中存放的是字符序列，因此，在算法中要有一个数字字符到值的转换。 如下图所示：表4-2 后缀表达式的计算过程示例计算步骤后缀表达式的读入运算结果栈VS初始9 2 4 7 * +5 / - 3 +空12 4 7 * +5 / - 3 +924 7 * +5 / - 3 +2 937 * +5 / - 3 +4 2 94* +5 / - 3 +7 4 2 95+5 / - 3 +28 2 965 / - 3 +30 97/ - 3 +5 30 98- 3 +6 993 +310+3 311空65 程序代码#include#define StackSize 100#define QueueSize 100/*队列的相关操作*/typedef char DataType;typedef struct char data100;int front,rear;SeqQueue; /定义队列类型void InitQueue(SeqQueue * Q)/初始化队列Q-front=0; Q-rear=0;int QueueEmpty(SeqQueue * Q) /判空队列return Q-rear=Q-front;void EnQueue(SeqQueue * Q, DataType x) /入队列if(Q-rear+1)%QueueSize=Q-front)printf(Queue overflow);else Q-dataQ-rear=x;Q-rear=(Q-rear+1)%QueueSize; int DeQueue(SeqQueue *Q)return Q-dataQ-front+;/*栈的相关操作*/typedef struct DataType data100;int top;SeqStack; /栈类型的定义void InitStack(SeqStack * S) /初始化栈S-top=-1;void Push(SeqStack * S,DataType x) /入栈(进栈）if(S-top=StackSize-1)printf(stack overflow);else S-top=S-top+1;S-dataS-top=x;DataType Pop(SeqStack * S) /退栈出栈）if(S-top=-1)printf(stack underflow);elsereturn S-dataS-top-;DataType GetTop(SeqStack * S) /取栈顶元素if(S-top=-1)printf(stack empty);elsereturn S-dataS-top;/求运算符优先级函数int Priority(DataType op)switch(op) case (:case #:return(0);case -:case +:return(1);case *:case /:return(2);void CTPostExp(SeqQueue *Q)SeqStack OS; /运算符栈char c,t;SeqStack *S;S=&OS; InitStack(S); /初始化栈Push(S,#); /压入栈底元素#do /扫描中缀表达式 c=getchar();switch(c)case :break; /去除空格符case 0:case 1:case 2:case 3:case 4:case 5:case 6:case 7:case 8:case 9:EnQueue(Q,c); break;case(: Push(S,c); break;case ):case #:do t=Pop(S);if(t!=( & t!=#) EnQueue(Q,t); while(t!=( & S-top!=-1); break;case +:case -:case *:case /:while(Priority(c)=0 & chfront=0;printf(n);printf(求值结果为：%dn,CPost