栈的应用实验报告.doc

数据结构实验报告 报告名称 栈的应用 专 业 网络工程 班 级 1001 学 号 201003120129 姓 名 张剑 指导教师 陈淑红 李珍辉 黄哲 2012 年 5 月 4日  实验目的： 实验内容与基本要求：概要设计：ypedef struct{ SElemType *base; SElemType *top; int stacksize; } SqStack; 2.栈的基本操作： InitStack(S) 操作结果：构造一个空栈S。 DestoryStack（S） 初始条件：栈S存在。、 操作结果：栈S被销毁。 ClearStack(S) 初始条件：栈S存在。、 操作结果：将S清为空栈。 StackEmpty（S） 初始条件：栈S存在。、 操作结果：若S为空栈，则返回TUUE，否则FALSE. StackLength(S) 初始条件：栈S存在。、 操作结果：返回S的 元素个数，即栈的长度。 GetTop（S,e） 初始条件：栈S存在且非空。 操作结果：用e 返回S的栈顶元素。 Push（S，e） 初始条件：栈S存在。、 操作结果：插入元素e为新的栈顶元素。 pop (s,e) 初始条件： 栈S存在且非空。 操作结果： 删除S的栈顶元素，并用e返回其值。 StackTravse(S,vist()) 初始条件:栈S存在且非空. 操作结果:从栈底到栈顶依次对S的每个元素调用函数vist()，一旦vist()失败，择操作结束。 3.表达式求职操作： OpperandType EvauluateExpresseion(){ //算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算式//栈OP为运算符集合。 TnitStack（OPTR）；Push（OPTR，”#”）; intStack (OPND); c=getchar(); while(c!’#’||Gettop(OPTR)!=’#’){if(!In(c,op))｛Push(OPND,c);c=getchar(); ｝//不是运算符则进栈。 else switch(Precede(GetTop(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; }//switch }//while return GetTop(OPND); }// EvauluateExpresseion 五、详细设计：#include stdio.h #include stdlib.h #include string.h #define STACK_MAX_SIZE 50 typedef struct { char symb; /*字符标记*/ int grade; /*运算级别 */ }elem_t; typedef struct { elem_t data[STACK_MAX_SIZE]; int top; }f_stack; /*符号栈*/ enum { S_DIGIT, S_OPERATOR, S_BRACKET, }; f_stack *StackInit() { f_stack *s; s = (f_stack *)malloc(sizeof(f_stack)); if (s==NULL) { printf(could not malloc memory for s!); exit(1); } memset(s-data,0,sizeof(elem_t)*STACK_MAX_SIZE); s-top = 0; return