算法与数据结构课程设计--栈的应用.doc

栈的应用 1、表达式求值 #include stdlib.h #include stdio.h #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define NULL 0 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef int Status; /* 定义顺栈类型 */ typedef char SElemType1; typedef struct { SElemType1 *base; SElemType1 *top; int StackSize; } SqStack; /* 初始化顺栈 */ Status InitStack1(SqStack *S) { (*S).base=(SElemType1 *)malloc(STACK_INIT_SIZE*sizeof(SElemType1)); if (!(*S).base) exit(OVERFLOW); (*S).top=(*S).base; (*S).StackSize=STACK_INIT_SIZE; return OK; } /* 清空顺栈 */ void ClearStack1(SqStack *S) { (*S).top=(*S).base; } /* 判断顺栈是否为空 */ Status StackEmpty1(SqStack S) { if (S.top==S.base) return TRUE; else return FALSE; } /* 求顺栈长度 */ int StackLength1(SqStack S) { return S.top-S.base; } /* 取顺栈的栈顶元素(注意：形参表与课本有差别) */ SElemType1 GetTop1(SqStack S) { if (S.top==S.base) return ERROR; return *(S.top-1); } /* 入顺栈 */ Status Push1(SqStack *S,SElemType1 e) { if ((*S).top-(*S).base=(*S).StackSize) {(*S).base=(SElemType1*)realloc((*S).base,((*S).StackSize+STACKINCREMENT)*sizeof(SElemType1)); if (!(*S).base) exit(OVERFLOW); (*S).top=(*S).base+(*S).StackSize; (*S).StackSize+=STACKINCREMENT; } *((*S).top)=e; (*S).top++; return OK; } /* 出顺栈 */ Status Pop1(SqStack *S,SElemType1 *e) { if ((*S).top==(*S).base) return ERROR; (*S).top--; *e=*((*S).top); return OK; } /* 定义链栈类型 */ typedef int SElemType2; typedef struct SNode { SElemType2 data; struct SNode *next; } SNode,*SLinkStack; /* B2、初始化链栈 */ Status InitStack2(SLinkStack *S) { (*S)=(SLinkStack)malloc(sizeof(SNode)); if (!(*S)) exit(OVERFLOW); (*S)-next=NULL; return OK; } /* 判断顺栈是否为空 */ Status StackEmpty2(SLinkStack S) { if (!(S-next)) return TRUE; else return FALSE; } /* 取顺栈的栈顶元素*/ SElemType2 GetTop2(SLinkStack S) { if (StackEmpty2(S)) return ERROR; return S-next-data; } /* 入链栈 */ Status Push2(SLinkStack *S, SElemType2 e) { SLin