数据结构中栈和队列的应用数据结构程序设计实验报告1.doc

实 验 报 告课程名称 数据结构程序设计 实验项目 数据结构中栈和队列的应用 系 别_ _计算机学院 _ _专 业_ 网络工程 _班级/学号_网工1202/2012011411_学生姓名 _王宇涵_实验日期 _2014年6月2日 成 绩 _ 指导教师 黄改娟 田英爱 实验题目:表达式的运算1、 程序功能分析（1）程序整体功能流程分析如下。第一步，用户输入表达式。第二步，对用户输入的表达式进行过滤，如果有错，请用户重新输入正确表达式；否则，返回正确的表达式。第三步，对表达式进行处理，将运算数和运算符按照“计算器算法”分别压入栈中，并在此过程中记录顶元素的变化情况。第四步，最后，返回结果，打印输出。二、设计方案（1）数据结构设计任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR，用以寄存运算符，另一个称做OPND，用以寄存操作数或运算结果。1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素；2.依次读入表达式，若是操作符即进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为”#”）。（2）数据存储结构因为表达式是由操作符，运算符和界限符组成的。如果只用一个char类型栈，不能满足2位以上的整数，所以还需要定义一个int类型的栈用来寄存操作数。定义两个栈的类型如下：/* 定义字符类型栈 */typedef struct int stacksize; char *base; char *top; Stack;/* 定义整型栈 */ typedef struct int stacksize; int *base; int *top; Stack2;1. Precede(char c1,char c2) 判断运算符优先权，返回优先权高的。算符间的优先关系如下：+-*/()#+-*/(#=算法步骤：第一步，如果输入符号位“+”或“减”。如果栈顶元素为“（”，“#”，此时栈顶符号优先级高，返回“”。第二步，如果输入符号为“*”或“/”。如果栈顶元素为“）”“*”“/”，此时栈顶元素符号优先级高，返回“”，否则，栈顶符号优先级低，返回“”。第三步，如果输入符号为“（”，则直接返回“”。第五步，输入符号为其他。栈顶元素为“#”,此时优先级同，返回“=”；否则，栈顶元素符号优先级高，返回“” 。算法代码char Precede(char c1,char c2) static char array49=, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; /用一维数组存储49种情况switch(c1) /* i为下面array的横标 */ case + : i=0;break; case - : i=1;break; case * : i=2;break; case / : i=3;break; case ( : i=4;break; case ) : i=5;break; case # : i=6;break; switch(c2) /* j为下面array的纵标 */ case + : j=0;break; case - : j=1;break; case * : j=2;break; case / : j=3;break; case ( : j=4;break; case ) : j=5;break; case # : j=6;break; return (array7*i+j); / 返回运算符array7*i+j为对应的c1,c2优先关系 2. int EvalExpr()主要操作函数。算法概要流程图：利用该算法对算术表达式3*(7-2)求值操作过程如下：步骤OPTR栈OPND栈输入字符主要操作1#3*(7-2)#Push(OPND,3)2#3*(7-2)#Push(OPTR,*)3#*3(7-2)#Push(OPNR,()4#*(37-2)#Push(OPND,7)5#*(3 7-2)#Push(OPNR,-)6#*(-3 72)#Push(OPND,2)7#*(-3 7 2)#Operate(7,-,2)8#*(3 5)#Pop(OPTR)9#*3 5#Operate(3,*,5)10#15#Return(GetTop2(OPND)算法代码如下：int EvalExpr()/主要操作函数 c = *ptr+; while(c!=#|GetTop(OPTR)!=#) if(!In(c) /不是运算符即进栈 if(!In(*(ptr-1) ptr=ptr-1;m=atoi(ptr);/取字符串前面的数字段m=atoi(ptr);/取字符串前面的数字段n=num(m); Push2(&OPND,m); ptr=ptr+n;c=*ptr+; else switch(Precede(GetTop(OPTR),c) case :/退栈并将运算结果入栈 theta=Pop(&OPTR); b=Pop2(&OPND); a=Pop2(&OPND); Push2(&OPND,Operate(a,theta,b);break; 程序代码#include #include #include #define NULL 0 #define OK 1#define ERROR -1 #define STACK_INIT_SIZE 100#define STACKINCREMENT 20 /* 定义字符类型栈 */ typedef struct int stacksize; char *base; char *top; Stack; /栈的类型/* 定义整型栈 */ typedef struct int stacksize; /栈类型个数int *base; int *top; Stack2;/* - 全局变量- */ Stack OPTR;/* 定义运算符栈*/Stack2 OPND; /* 定义操作数栈 */ char expr255 = ; /* 存放表达式串 */ char *ptr = expr; int InitStack(Stack *s) /构造运算符栈 s-base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); /建立新结点if(!s-base) return ERROR; s-top=s-base; s-stacksize=STACK_INIT_SIZE;return OK; int InitStack2(Stack2 *s) /构造操作数栈 s-base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!s-base) return ERROR; s-stacksize=STACK_INIT_SIZE; s-top=s-base; return OK; int In(char ch) /判断字符是否是运算符，运算符即返回1 return(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#); int Push(Stack *s,char ch) /运算符栈插入ch为新的栈顶元素 *s-top=ch; s-top+; return 0; int Push2(Stack2 *s,int ch)/操作数栈插入ch为新的栈顶元素 *s-top=ch; s-top+; return 0; char Pop(Stack *s) /删除运算符栈s的栈顶元素，用p返回其值 char p;s-top-; p=*s-top; return p; int Pop2(Stack2 *s)/删除操作数栈s的栈顶元素，用p返回其值 int p;s-top-; p=*s-top; return p;char GetTop(Stack s)/用p返回运算符栈s的栈顶元素 char p=*(s.top-1); return p; int GetTop2(Stack2 s) /用p返回操作数栈s的栈顶元素 int p=*(s.top-1); return p; /* 判断运算符优先权，返回优先权高的 */ char Precede(char c1,char c2) int i=0,j=0; static char array49= /array是数组, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; switch(c1) /* i为下面array的横标 */ case + : i=0;break; case - : i=1;break; case * : i=2;break; case / : i=3;break; case ( : i=4;break; case ) : i=5;break; case # : i=6;break; switch(c2) /* j为下面array的纵标 */ case + : j=0;break; case - : j=1;break; case * : j=2;break; case / : j=3;break; case ( : j=4;break; case ) : j=5;break; case # : j=6;break; return (array7*i+j); /* 返回运算符 */ /*操作函数 */ int Operate(int a,char op,int b) switch(op) case + : return (a+b); case - : return (a-b); case * : return (a*b); case / : return (a/b); return 0; int num(int n)/返回操作数的长度 char p10;itoa(n,p,10);/把整型转换成字符串型n=strlen(p);return n;int EvalExpr()/主要操作函数 char c,theta,x; int n,m;int a,b; c = *ptr+; while(c!=#|GetTop(OPTR)!=#) if(!In(c) if(!In(*(ptr-1) ptr=ptr-1;m=atoi(ptr);/取字符串前面的数字段n=num(m); Push2(&OPND,m); ptr=ptr+n;c=*ptr+; else switch(Precede(GetTop(OPTR),c) case : /退栈并将运算结果入栈theta=Pop(&OPTR); b=Pop2(&OPND); a=Pop2(&OPND); Push2(&OPND,Operate(a,theta,b);break; return GetTop2(OPND); int main( ) printf(请输入正确的表达式以#结尾:); do gets(expr); while(!*expr); InitStack(&OPTR); /* 初始化运算符栈 */ Push(&OPTR,#); /* 将#压入运算符栈 */ InitStack2(&OPND); /* 初始化操作数栈 */ printf(表达式结果为:%dn, EvalExpr();return 0; 输出结果：实验总结：这次课程设计让我更加了解大一学到的C和这个学期学到的数据结构。课设题目要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。这次课程设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。就像我在写Ev