数据结构 栈和队列的详细代码~

#include <stdlib.h> #include "stdio.h" typedef float SElemType; //栈数据元素的类型 #define STACk_INIT_SIZE 10 //栈存储空间的初始分配量 #define STACKINCREMENT 10 //栈存储空间的分配增量 typedef struct { SElemType *base; //构造之前和销毁之后，base的值为NULL SElemType *top; //栈顶指针 int stacksize; //当前分配的存储容量(以sizeof(SElemType)为单位) }SqStack; int InitStack(SqStack &S) { S.base=(SElemType *)malloc(STACk_INIT_SIZE * sizeof(SElemType)); //通过malloc函数分配空间 if (!S.base) return 0; //如果分配失败，则返回0 S.top=S.base; //头指针等于根 S.stacksize=STACk_INIT_SIZE; //当前分配的空间 return 1; } void DestroyStack(SqStack *S) { if(S->base) { if (S->base!=NULL) //如果堆栈非空，则释放空间 { free(S->base); S->base=NULL; S->top=NULL; } S=NULL; } } void ClearStack(SqStack &S) { if (S.base) //如果堆栈非空，则置top=base; { S.base=S.top; } } int StackEmpty(SqStack S) { if (S.base) { if (S.base==S.top) //如果堆栈为空栈，则返回1(true)，否则返回0(false) { return 1; } } return 0; } int StackLength(SqStack S) { if(S.base) { return S.top-S.base;//返回堆栈元素的个数 } return 0; } int GetTop(SqStack S,SElemType &e) { if (S.top==S.base) return 0;//判定是不是空栈 e=*(S.top-1); return 1; //如果不能得到数据元素，则返回0(false) } int Push(SqStack &S,SElemType e) { if (S.base) { if ((S.top-S.base)>=S.stacksize) //栈满，追加存储空间 { S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)* sizeof(SElemType)); if(S.base==NULL) return 0; //如果重新分配空间失败，则返回0(false)，表示插入不成功 S.top=S.base+S.stacksize; //设置数组的新地址 S.stacksize+=STACKINCREMENT; //分配空间要加上新增的空间 } *S.top++=e; return 1; } return 0; } int Pop(SqStack &S,SElemType &e) { if (S.base) { if (S.top>S.base) //若栈不是空的 { e=*--S.top; return 1; } } return 0; } ///////////////////////////////////////////////////下面是算法需要的函 int In(char c)//判断c是不是运算符 { if (c!='+'&&c!='-'&&c!='*'&&c!='/'&&c!='('&&c!=')'&&c!='#'&&c!='=') { return 0; } return 1; } int Priority(int e)//将运算符转换为优先级表中的序号 { switch (e) { case 43://'+' return 0; case 45://'-' return 1; case 42://'*' return 2; case 47://'/' return 3; case 40://'(' return 4; case 41://')' return 5; default: return 6; } } char precede(SElemType e,char c) { int priority[7][7]={{1,1,-1,-1,-1,1,1},{1,1,-1,-1,-1,1,1},{1,1,1,1,-1,1,1}, {1,1,1,1,-1,1,1},{-1,-1,-1,-1,-1,0,2},{1,1,1,1,-2,1,1}, {-1,-1,-1,-1,-1,-2,0}};//优先表 int q=priority[Priority((int) e)][Priority((int) c)];//得到优先值 switch (q) { case 1: return '>'; case 0: return '='; default : return '<'; } } SElemType Operate(SElemType a,SElemType theta,SElemType b) { switch ((int)theta) { case 43://'+' return (a+b); case 45://'-' return (a-b); case 42://'*' return (a*b); default : if (b!=0) { return a/b; } else { printf("除数为0\n"); return 0; } } } int EvaluateExpression(SElemType &answer) { char c; SElemType e,x,theta;//e来储存运算符栈栈顶字符 SElemType a,b; SqStack OPND;//OPEN栈用顺序堆栈存储运算数 SqStack OPTR;//OPTR栈用链式存储运算符 InitStack(OPTR); InitStack(OPND); Push(OPTR,'#'); c=getchar(); GetTop(OPTR,e); while(c!='#'||e!=35)//'#'的ASCII为35 { if (!In(c))//不是运算符则进栈 { Push(OPND,(SElemType)(c-48)); c=getchar(); GetTop(OPTR,e); while (!In(c)&&(c!='#'||e!=35))//当下一个字符还是数字时 { Pop(OPND,a); Push(OPND,a*10+c-48); c=getchar(); GetTop(OPTR,e); } } else { switch (precede(e,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); if (theta=='/'&&b==0) { printf("除数为0,请重新输入\n"); return 0; } Push(OPND,Operate(a,theta,b)); break; } GetTop(OPTR,e); } } GetTop(OPND,answer); return 1; } //////////////////////////////////////////////// int main() { SElemType answer; printf("请输入要计算的公式，以#号结束\n"); if (EvaluateExpression(answer)!=0) { printf(" %f \n",answer); } putchar(getchar()); getchar(); return 1; }