【DOC】-算法与数据结构栈与队列实验报告

【DOC】-算法与数据结构栈与队列实验报告【DOC】-算法与数据结构栈与队列实验报告算法与数据结构栈与队列实验报告实验二栈和队列实现四则运算实验二栈和队列实现四则运算一、实验目的及要求: 1、掌握栈和队列的基本操作:建立、插入、删除、查找、合并 2、掌握用栈和队列的储存 3、熟悉C语言上机编程环境 4、掌握编译、调试程序的方法二、实验内容: 采用栈进行表达式的求值，表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的又一个典型例子，本报告使用的是“算符优先法”求表达式的值。要把一个表达式翻译成正确求值的一个机...

【DOC】-算法与数据结构栈与队列实验报告算法与数据结构栈与队列实验报告实验二栈和队列实现四则运算实验二栈和队列实现四则运算一、实验目的及要求: 1、掌握栈和队列的基本操作:建立、插入、删除、查找、合并 2、掌握用栈和队列的储存 3、熟悉C语言上机编程环境 4、掌握编译、调试程序的方法二、实验内容 : 采用栈进行表达式的求值，表达式求值是程序设计语言编译中的一个最基本问题。它的实现是栈应用的又一个典型例子，本报告使用的是“算符优先法”求表达式的值。要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。若要正确翻译则首先要了解算术四则运算的规则。即: (1)、先乘除，后加减; (2)、从左算到右; (3)、先括号内后括号外。任何一个表达式都是由操作数、运算符和界限符组成的，我们称它们为单词。一般地，操作数既可以是常数也可以是被说明为变量或常量的标识符;运算符可以分为算术运算符、关系运算符和逻辑运算符3类;基本界限符有左右括号和表达式结束符等。为了叙述的简洁，我们仅讨论简单算术表达式的求值问题。这种表达式只包含加、减、乘、除4种运算符。我们把运算符和界限符统称为算符，它们构成的集合命名为OP。根据上述3条运算规则，在运算的每一步中，任意两个相继出现的算符系之一: 1和 2之间的优先级之多是以下3种关 1 2 1的优先级低于 2 1 2 1的优先级等于 2 1 2 1的优先级高于 2 根据实际情况推导出如下的优先关系算符间的优先关系表有规则(3)，+、-、*和/为 1时优先性均低于“(”但高于“)，”由规则(2)，当 1 2时，令 1 2，“#”是表达式的结束符。为了算法简洁，在表达式左右括号的最左边也虚设了一个“#”构成整个表达式的一对括号。表中的“(”=“)”表示当左右括号相遇时，括号内的运算已经完成。同理，“#”=“#”表示整个表达式求值完毕。“)”与“(、“#”与“)”以及“(”与“#”之间无优先级，这是因为表达式中不允许它们相继出现，一旦遇到这种情况，则可以认为出现语法错误。为实现算符优先算法，可以使用两个栈。一个称作OPTR，用以寄存运算符;另一个称作OPND，用以寄存操作数户哟运算结果。算法的基本思想是: (1)首先输入一个表达式，用一数组记录; (2)置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素; (3)依次读入表达式中的每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶元素比较优先权后作相应操作，直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为“#”)。三、程序代码 #include #include #include #define error 0 //错误标志 #define ok 1 //正确标志 #define overflow -1 //溢出标志 #define Stack_Size 100 //一般表达式运算符和运算数不会很长，100足够用 #define OP_Size 7 //一共7种运算符 char OP[OP_Size]={'+','-','*','/','(',')','#'}; //运算符 unsigned char Prior[7][7] = { '>','>','<','<','<','>','>', '>','>','<','<','<','>','>', '>','>','>','>','<','>','>', '>','>','>','>','<','>','>', '<','<','<','<','<','=',' ', '>','>','>','>',' ','>','>', '<','<','<','<','<',' ','=' }; // 算符间的优先关系 template struct SqStack { T *top; T *base; int stacksize; };//顺序栈结构模板 template int InitStack(T1 &S) { S.base=(T2 *)malloc(Stack_Size*sizeof(T2)); if(!S.base) exit (overflow); S.top=S.base; S.stacksize=Stack_Size; return ok; }//初始化栈函数模板 template int Push(T1 &S,T2 e) { if(S.top-S.base>=S.stacksize) { S.base=(T2 *)realloc(S.base,(S.stacksize+1)*sizeof(T2)); S.top=S.base+S.stacksize; S.stacksize+=1; } *S.top++=e; return ok; }//入栈函数模板 template int Pop(T1 &S,T2 &e) { if(S.top==S.base) return error; e=*--S.top; return ok; }//出栈函数模板 template T2 GetTop(T1 S) { if(S.top==S.base) return error; else return *(S.top-1); }//获取栈顶元素模板 int In(char Test,char* TestOp) { bool Find=false; if(!S.base) exit (overflow); for (int i=0; i< OP_Size; i++) { if (Test == TestOp[i]) Find= true; } return Find; }//判断是否为运算符 float Operate(float a,unsigned char theta, float b) { switch(theta) { case '+': return a+b; case '-': return a-b; case '*': return a*b; case '/': return a/b; default : return 0; } }//运算 int ReturnOpOrd(char op,char* TestOp) { int i; for(i=0; i< OP_Size; i++) { if (op == TestOp[i]) return i; } return 0; } char precede(char Aop, char Bop) { return Prior[ReturnOpOrd(Aop,OP)][ReturnOpOrd(Bop,OP)]; }//ReturnOpOrd和precede组合，判断运算符优先级 float EvaluateExpression() { // 算术表达式求值的算符优先算法。 // 设OPTR和OPND分别为运算符栈和运算数栈，OPSET为运算符集合。 SqStack OPTR; // 运算符栈，字符元素 SqStack OPND; // 运算数栈，实数元素 char TempData[20]; float Data,a,b; char theta,c,x,Dr[2]; InitStack,char> (OPTR); Push (OPTR, '#'); InitStack ,float>(OPND); strcpy(TempData,"\0");//将TempData置为空 c=getchar(); while (c!= '#' || GetTop,char>(OPTR)!= '#') { if (!In(c, OP)) { Dr[0]=c; Dr[1]='\0';//存放单个数 strcat(TempData,Dr);//将单个数连到TempData中，形成字符串 c=getchar(); if(In(c,OP))//如果遇到运算符，则将字符串TempData转换成实数，入栈， //并重新置空 { Data=(float)atof(TempData); Push(OPND, Data); strcpy(TempData,"\0"); } } else { // 不是运算符则进栈 switch (precede(GetTop,char>(OPTR), c)) { case '<': // 栈顶元素优先权低 Push(OPTR, c); c=getchar(); break; case '=': // 脱括号并接收下一字符 Pop(OPTR, x); c=getchar(); break; case '>': // 退栈并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b)); break; } // for switch } } // for while return GetTop,float>(OPND); } // EvaluateExpression void main() { printf("请输入表达式，并以#结尾:\n"); printf("%f\n",EvaluateExpression()); } 四、运行结果: 五、实验心得运用栈来实现最简单的四则运算，从实例中了解栈和队列的结构，以及进栈和出栈的过程。有关栈的构造、入栈、出栈等模块的代码都有源程序可参考，完成本实验的代码只需要组合学过的各个模块，结合起来进行相应的调试就可以实现。从中学会了写程序不一定所有代码都是自己重新写的，只要会运用、会调试就能高效地完成。这就要求在学习的过程中多积累好的源代码以备不时之需，也应该多尝试着自己去调试程序完成一些功能。这样在学好了算法与数据结构的前提下就能很快地写出自己需要的程序。

                    本文档为【【DOC】-算法与数据结构栈与队列实验报告】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

【DOC】-算法与数据结构栈与队列实验报告

你可能还喜欢