数据结构实验报告栈操作

《数据结构实验报告栈操作》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构实验报告》◎实验题目：栈的应用。◎实验目的：熟悉掌握对栈的应用和基本操作。◎实验内容：用算符优先法对算术表达式求值。一、需求分析通过程序设计实现算符优先法：1以字符串的形式输入整形数据和运算符号；2、输出算术表达式的结果；3、实现简单的一位整型数据的算术运算；4、测试数据：算术表达式，其中的整型数据均只有一•位。二概要设计1.基本操作voidInitStack(SqStack*s)操作结果：栈的初始化。intGetTop(SqStack*s)初始条件：栈已存在且不空；操作结果：将栈顶元素返回。voidPush(SqStack*s,inte)初始条件：栈已

2、存在；操作结果：插入e作为新的栈顶元素。charPopl(SqStack*s)初始条件：运算符栈己存在且不空；操作结果：栈顶元素出栈。intPop2(SqStack*s)初始条件：运算数栈已存在且不空；操作结果：栈顶元素出栈。charprecede(charA,charB)操作结果：比较两个算符的优先级，并将比较结果返回。intIn(charTest)操作结果：判断字符是否是运算符。intEvaluateExpression()操作结果：通过调用一系列的函数，对表达式求值。main()操作结果：主要通过调用函数EvaluateExpression得到最终结果。2.

3、本程序包含两个模块：(1)构造栈的模块；(2)主程序模块；(三)详细设计1.声明，栈的结构体和判断运算符优先级的表格(以数组形式表达)：typedefstructint*base;int*top;intstacksize;}SqStack;#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineoverflow1#defineerror0charOPSET[7]={'+',,'#'}；//运算符种类unsignedcharPrior[7][7]={//算符间的优先关系}；2•各个函数的详细设计：voidInit

4、Stack(SqStack*s)//栈的初始化{s~>base=(int*)malloc(STACKINITSIZE*sizeof(int));if(!s~>base)exit(error);//存储分配失败s->top=s->base;s->stacksize=STACKINITSIZE;JintGetTop(SqStack*s)//若运算符栈不空则川e返冋栈顶元索{if(s->t()p=s-〉base)exit(overflow);return(*(s->top-l));}voidPush(SqStack*s,inte)〃插入e为新的栈顶元素{if(s->to

5、p-s->base>=s->stacksize){s->base=(int*)real1oc(s->base,(STACK_TNTT_STZE+STACKINCREMENT)*sizeof(int));if(!s->base)exit(error);s->top二s->base+s-〉stacksize;;s->stacksize=s->stacksize+STACKINCREMENT;}*s->top二e;s->top++;charPopl(SqStack*s)//运算符栈顶元索出栈if(s->top=s~>base)returnerror;return(*—s

6、->top);}intPop2(SqStack*s)//运算数栈顶元素出栈{if(s->top=s~>base)returnerror;return(*—s->top);}charPrecede(charA,charB)//实现两个算符优先级的比较{returnPrior[FindOpOrd(A,OPSET)][FindOpOrd(B,OPSET)];}在Precede函数中再调用FindOpOrd函数，设计如下：intFindOpOrd(charop,char*TestOp)//在Prior数组中按行或者按列找到算符对应的位置{inti;for(i=0;i<7;

7、i++){if(op==TestOp[i])returni;}}intOperate(inta,unsignedchartheta,intb)//根据运算符进彳亍二元运算{switch(theta){casereturna+b;casereturna-b;casereturna*b;caseT:if(b!=O)returna/b;elseexit(error);default:returnenor;I}intIn(charTest)//判断字符是否为运算符，如果是运算符返回1,否则返回0{ifCO*<=Test&&Testv=9)return0;elseretur

8、n1;}i