《数据结构课程设计【算法实现】》由会员分享，可在线阅读，更多相关《数据结构课程设计【算法实现】（9页珍藏版）》请在金锄头文库上搜索。
1、1目目 录录1 概述.21.1 现状分析.21.2 存在问题.21.3 实现意义.21系统分析 .22概要设计 .24 详细设计.35 运行与测试.35.1 主界面输出显示.35.2 中缀表达式到后缀表达式的转换的输出.45.3 后缀表达的计算输出.46 总结与心得.4参考文献：.5附录（实验代码）.521 概述概述1.1 现状分析现状分析以字符序列的形式从终端输入语法正确的、不含变量的整数表达式，利用给定的算符 优先关系，实现对算术四则混合运算表达式的求值，并演示在求值过程中运算符、操作数 栈、输入字符和方根操作的变化过程。1.2 存在问题存在问题人们在书写表达式时通常采用“中缀”表示形式，
2、也就是将运算符放在两个操作数中 间，用这种方法表示称为中缀表达式，但是，这种表达式对计算机处理来是不大合适的。 从而引出了后缀表达式，适合计算机的计算与存放。1.3 实现意义实现意义实现中缀表达式到后缀表达式的转换和对后缀表达的计算机，这样计算机方法简单方 便，特别适合计算机的处理方式。而在后缀表达式中，不仅不需要括号，而且还完全免除 计算优先级的规则。对于操作者，既方便看懂又易于记忆等。2 系统分析系统分析表达式的求值问题。运用了相应的队列、栈相关的定义与函数，使计算机处理方便， 具有一定的可行性，并能帮助我们正确理解中缀，后缀表达式的相关计算，对于操作者有 所提高等效果。3 概要设计概要设
3、计开始输入中缀表达 式将中缀表达式转换为后缀表达式输出后缀表达式后缀表达式求值输出结果结束 的CTPostExp 函 数CPostExp 函数34 详细设计详细设计int DeQueue(SeqQueue * Q); / 队列输出 void InitQueue(SeqQueue * Q); /初始化队列 int QueueEmpty(SeqQueue * Q); /判空队列 void EnQueue(SeqQueue * Q,DataType x); / 入队列 void InitStack(SeqStack * S); / 初始化栈 void Push(SeqStack * S,DataTy
4、pe x); / 入栈（进栈） DataType Pop(SeqStack * S); / 退栈（出栈） DataType GetTop(SeqStack * S); / 取栈顶元素 int Priority(DataType op); / 运算符优先级判断函数 void CTPostExp(SeqQueue *Q); / 压栈void main() / 主函数 SeqQueue *Q; SeqQueue PostQ; /定义队列，存放后缀表达式 Q= InitQueue(Q);CPostExp(Q);/调用后缀表达的计算 CTPostExp(Q); /调用转换函数将中缀表达式转换成后缀表达式
5、 while(!QueueEmpty(Q) /后缀表达式 printf(“%c“,DeQueue(Q); 5 运行与测试运行与测试5.1 主界面输出显示主界面输出显示调试程序代码，运行后得到主界面，等待算术表达式的输入：45.2 中缀表达式到后缀表达式的转换的输出中缀表达式到后缀表达式的转换的输出在主界面中输入中缀表达式：9-（2+4*7）/5+3#,以“#”结束转换为后缀表达式：5.3 后缀表达的计算输出后缀表达的计算输出稍微修改程序代码，输出最终结果；6 总结与心得总结与心得1.程序调试，同学间的合作是很有效果的，在同学的帮助下，基本完成本实验的调试与运行，从而进一步理解了中缀、后缀表达式
6、。2.中缀表达式到后缀表达式的转换中，必须保存两个运算符，后保存的运算符先输出。用计算机来实现这一过程，用到栈的后进先出的原则。3.在队列输出函数中，查阅了数据结构中的 DeQueue 函数，对学过的知识有所不清楚，需要温故而知新，从中获得新知识。5参考文献：参考文献：1数据结构课程设计 苏仕华等 机械工业出版社 2 C 程序设计（第三版） 谭浩强 清华大学出版社3数据结构（C） 严蔚敏等 清华大学出版社4C+面向对象程序设计教程游洪跃 清华大学出版附录（实验代码）附录（实验代码）#include #define StackSize 100 #define QueueSize 100typed
7、ef char DataType; typedef struct char data100; int front,rear; SeqQueue;/定义队列类型typedef struct DataType data100; int top; SeqStack;/栈类型的定义int DeQueue(SeqQueue * Q); void InitQueue(SeqQueue * Q); int QueueEmpty(SeqQueue * Q); void EnQueue(SeqQueue * Q,DataType x); void InitStack(SeqStack * S); void Pu
8、sh(SeqStack * S,DataType x); DataType Pop(SeqStack * S); DataType GetTop(SeqStack * S); int Priority(DataType op); void CTPostExp(SeqQueue *Q);void InitQueue(SeqQueue * Q)/初始化队列 6Q-front=0;Q-rear=0; int QueueEmpty(SeqQueue * Q)/判空队列函数 return Q-front=Q-rear; void EnQueue(SeqQueue * Q,DataType x)/入队列
9、if(Q-rear+1)%QueueSize=Q-front) /判断队列是否已满 printf(“Queue overflow“); else Q-dataQ-rear=x; Q-rear=Q-rear+1; int DeQueue(SeqQueue * Q) /队列输出 char x; x=Q-dataQ-front; Q-front=Q-front+1; return x; void InitStack(SeqStack * S)/初始化栈 S-top=-1; void Push(SeqStack * S,DataType x)/对输入的元素进行进栈 if(S-top=StackSize
10、-1)/判断栈是否已满 printf(“stack overflow“); else S-top=S-top+1; /不能进行交换 S-dataS-top=x; DataType Pop(SeqStack * S)/出栈7 if(S-top=-1) printf(“stack underflow“); else return S-dataS-top-; DataType GetTop(SeqStack * S)/取栈顶元素 if(S-top=-1) printf(“stack empty“); else return S-dataS-top; int Priority(DataType op)
11、/求运算符优先级函数 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= InitStack(S);/初始化栈 Push(S,#);/将#号压入栈底 do c=getchar(); switch(c) case :break;/将空格去除 case 0: case 1:8case 2: case 3
12、: 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 t=Pop(S); if(t!=( while(t!=(break; case +: case -: case *: case /: while(Priority(c)front!=Q-rear) ch=DeQueue(Q); if(ch=0 else9 y=Pop(S); x=Pop(S); switch(ch) case +:Push(S,x+y);break; case -:Push(S,x-y);break; case *:Push(S,x*y);break; case /:Push(S,x/y);break; printf(“
