数据结构课程设计【算法实现】.doc

目 录
1 概述 2
1.1现状分析 2
1.2 存在问题 2
1.3实现意义 2
1 系统分析 2
2 概要设计 2
4 详细设计 3
5 运行与测试 3
5.1 主界面输出显示 3
5.2 中缀表达式到后缀表达式的转换的输出 4
5.3 后缀表达的计算输出 4
6 总结与心得 4
参考文献： 5
附录（实验代码） 5

1 概述
1.1现状分析
以字符序列的形式从终端输入语法正确的、不含变量的整数表达式，利用给定的算符优先关系，实现对算术四则混合运算表达式的求值，并演示在求值过程中运算符、操作数栈、输入字符和方根操作的变化过程。
1.2 存在问题
人们在书写表达式时通常采用“中缀”表示形式，也就是将运算符放在两个操作数中间，用这种方法表示称为中缀表达式，但是，这种表达式对计算机处理来是不大合适的。从而引出了后缀表达式，适合计算机的计算与存放。
1.3实现意义
实现中缀表达式到后缀表达式的转换和对后缀表达的计算机，这样计算机方法简单方便，特别适合计算机的处理方式。而在后缀表达式中，不仅不需要括号，而且还完全免除计算优先级的规则。对于操作者，既方便看懂又易于记忆等。
2系统分析
表达式的求值问题。运用了相应的队列、栈相关的定义与函数，使计算机处理方便，具有一定的可行性，并能帮助我们正确理解中缀，后缀表达式的相关计算，对于操作者有所提高等效果。
开始
输入中缀表达式
将中缀表达式转换为后缀表达式
输出后缀表达式
后缀表达式求值
输出结果
结束的
CTPostExp函数
CPostExp函数
3概要设计

4 详细设计
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,DataType x); // 入栈（进栈）
DataType Pop(SeqStack * S); // 退栈（出栈）
DataType GetTop(SeqStack * S); // 取栈顶元素
int Priority(DataType op); // 运算符优先级判断函数
void CTPostExp(SeqQueue *Q); // 压栈

void main() // 主函数
{
SeqQueue *Q;
SeqQueue PostQ; //定义队列，存放后缀表达式
Q=&PostQ;
InitQueue(Q);
CPostExp(Q);//调用后缀表达的计算
CTPostExp(Q); //调用转换函数将中缀表达式转换成后缀表达式
while(!QueueEmpty(Q)) //后缀表达式
printf("%c",DeQueue(Q));
}

5 运行与测试
5.1 主界面输出显示
调试程序代码，运行后得到主界面，等待算术表达式的输入：

5.2 中缀表达式到后缀表达式的转换的输出
在主界面中输入中缀表达式：9-（2+4*7）/5+3#,以“#”结束转换为后缀表达式：

5.3 后缀表达的计算输出
稍微修改程序代码，输出最终结果；

6 总结与心得
1. 程序调试，同学间的合作是很有效果的，在同学的帮助下，基本完成本实验的调试与运行，从而进一步理解了中缀、后缀表达式。
2. 中缀表达式到后缀表达式的转换中，必须保存两个运算符，后保存的运算符先输出。用计算机来实现这一过程，用到栈的后进先出的原则。
3. 在队列输出函数中，查阅了《数据结构》中的DeQueue函数，对学过的知识有所不清楚，需要温故而知新，从中获得新知识。
参考文献：
[1]《数据结构课程设计》 苏仕华等 机械工业出版社
[2] 《C程序设计（第三版）》 谭浩强 清华大学出版社
[3]《数据结构（C）》严蔚敏等 清华大学出版社
[4]《C++面向对象程序设计教程》游洪跃 清华大学出版
附录（实验代码）
#include<stdio.h>
#define StackSize 100
#define QueueSize 100

typedef char DataType;
typedef struct {
char data[100];
int front,rear;
}SeqQueue; //定义队列类型

typedef struct{
DataType data[100];
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 Push(SeqStack * S,DataType x);
DataType Pop(SeqStack * S);
DataType GetTop(SeqStack * S);
int Priority(DataType op);
void CTPostExp(SeqQueue *Q);

void InitQueue(SeqQueue * Q) //初始化队列
{
Q->front=0;Q->rear=0;
}

int QueueEmpty(SeqQueue * Q) //判空队列函数
{
return Q->front==Q->rear;
}

void EnQueue(SeqQueue * Q,DataType x) //入队列
{
if((Q->rear+1)%QueueSize==Q->front) //判断队列是否已满
printf("Queue overflow");
else
{
Q->data[Q->rear]=x;
Q->rear=Q->rear+1;
}
}

int DeQueue(SeqQueue * Q) //队列输出
{
char x;
x=Q->data[Q->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-1) //判断栈是否已满
printf("stack overflow");
else
{
S->top=S->top+1; //不能进行交换
S->data[S->top]=x;
}
}

DataType Pop(SeqStack * S) //出栈
{
if(S->top==-1)
printf("stack underflow");
else
return S->data[S->top--];
}

DataType GetTop(SeqStack * S) //取栈顶元素
{
if(S->top==-1)
printf("stack empty");
else
return S->data[S->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
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;
}
}while(c!='#');
}

void CPostExp(SeqQueue *Q)
{
SeqStack VS,*S;
char ch;
int x,y;
S=&VS;
InitStack(S);
while(Q->front!=Q->rear)
{
ch=DeQueue(Q);
if(ch>='0'&&ch<='9')
Push(S,ch-'0');
else
{
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("\n结果是： \n");
printf("%d ",GetTop(S));
//return GetTop(S);
}

void main()
{
printf("请输入算术表达式：\n ");
SeqQueue *Q;
SeqQueue PostQ;
Q=&PostQ;
InitQueue(Q);
CTPostExp(Q);

printf("转换为后缀表达式为：\n");
while(!QueueEmpty(Q))
printf("%c",DeQueue(Q));
CPostExp(Q);
printf("\n");

}

9