数据结构实验报告5.doc

数据结构实验报告实验5学号： 姓名： 得分：_一、实验目的1、复习栈的逻辑结构、存储结构及基本操作；2、掌握顺序栈、链栈。二、实验内容1、（必做题）假设栈中数据元素类型是字符型，请采用顺序栈实现栈的以下基本操作：（1）Status InitStack (&S) /构造空栈S；（2）Status Push(&S, e) /元素e入栈S；（3）Status Pop(&S, &e) /栈S出栈，元素为e。2、（必做题）请实现：对于一个可能包括括号、()的表达式，判定其中括号是否匹配。三、算法描述（采用自然语言描述）1. 构建空栈s，输入元素，将元素依次入栈，遍历打印栈中元素，输出栈顶元素，打印被输出的元素，遍历打印栈中元素。2.构建空栈，输入表达式，使用函数count判断表达式中括号是否匹配，如果匹配输出匹配正确，不匹配则输出匹配错误。四、详细设计1.打印被输出的元素遍历打印栈中元素开始构建空栈s将元素依次入栈输出栈顶元素结束输入元素遍历打印栈中元素2.输出匹配错误使用函数count判断表达式中括号是否匹配开始构建空栈s结束输入表达式输出匹配正确五、程序代码（给出必要注释）1.#include#include#define MaxSize 100typedef struct node* SqStack;typedef char ElemType;struct node/栈的数据结构 int top; ElemType dataMaxSize;void StatusInitStack(SqStack *L)/构造空栈S (*L) = (SqStack*)malloc(sizeof(SqStack); (*L)-top = -1;void StatusPush(SqStack L, ElemType e)/元素e入栈S if (L-top = MaxSize - 1) printf(栈满n); else L-top+; L-dataL-top = e; void StatusPop(SqStack L, ElemType *e)/栈S出栈，元素为e if (L-top = -1) printf(栈空n); else *e = L-dataL-top; L-top-; void Print(SqStack L)/遍历输出 int i = 0; for(i = 0; i top; i+) printf(%c, L-datai); printf(n);int main() SqStack s; ElemType e; ElemType* y; y = &e; StatusInitStack(&s); printf(输入入栈数据:); scanf(%c, &e); while (e!=n) StatusPush(s, e); scanf(%c, &e); printf(n目前栈中元素为:n); Print(s); StatusPop(s, y); printf(n出栈元素是:%cn, *y); printf(n栈顶元素出栈后，栈为:n); Print(s);2.#include#include#include#define STACK_INIT_SIZE 10#define STACK_GROW_SIZE 5#define ELEMTYPE chartypedef struct /*建立一个栈的首结点*/ ELEMTYPE * base; ELEMTYPE * top; int stacksize; SpStack;int InitStack(SpStack *s) /*建立空的栈并返回首地址*/ s-base=(ELEMTYPE*)malloc(STACK_INIT_SIZE*sizeof(ELEMTYPE); if (!s-base) return 0; s-top=s-base; s-stacksize=STACK_INIT_SIZE; return 1;int StackEmpty(SpStack *s) /*判断栈是否为空*/ if (s-top=s-base) return 1; else return 0;int Push(SpStack *s,ELEMTYPE e) /*往栈顶插入元素即进栈*/ if (s-top-s-base=s-stacksize) /*判断是否栈满*/ s-base=(ELEMTYPE*)realloc(s-base,(s-stacksize+STACK_GROW_SIZE)*sizeof(ELEMTYPE); if (!s-base) return 0; s-stacksize+=STACK_GROW_SIZE; s-top=s-base+s-stacksize; *s-top+=e; return 1;int Pop(SpStack *s,ELEMTYPE *e) /*让栈顶元素依次输出即出栈*/ if (StackEmpty(s) return 0; *e=*(-s-top); return 1;int Count(SpStack *s) ELEMTYPE eSTACK_INIT_SIZE*2; ELEMTYPE e1; int i; InitStack(s); gets(e); if (n=estrlen(e)-1) estrlen(e)-1=0; for (i=0; ei!=0; i+) switch (ei) case (: case : case : Push(s,ei); break; case ): case : case : if(StackEmpty(s) printf(匹配错误n); return 0; else Pop(s,&e1); break; if (StackEmpty(s) printf(匹配正确n); return 1; else printf(匹配错误n); return 0; int main() SpStack s; printf(请输入一个可能包括括号、()的表达式n); Count(&s);