实验二 栈和队列 M.doc

软件学院 数据结构 实验报告 2014 级 软件工程 专业 班级： 191 学号： 201419118 姓名： 孟 国 元 实验二 栈和队列的模拟操作 一、实验目的二、实验内容] } 输出：匹配括号对或者不匹配的结果（优先配对的顺序），例如( ) ( ) [ ] { }( ) 括号序列匹配 或者[ ] ( ) ( ) ] } 括号序列不匹配 1.2 具体操作的函数模块功能说明： （1）栈的存储结构（顺序存储结构） typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack;//顺序栈 （2）初始化一个空栈 函数：void InitStack(SqStack *S) （3）入栈 函数：void Push(SqStack *S, SelemType x)//插入x为新的栈顶元素 （4）出栈 函数：ElemType Pop(SqStack *S) //若栈不空，则删除栈的栈顶元素，用e返回其值，并返回OK，否则返回ERROR （5）匹配检验括号匹配的方法，就是对给定的字符串依次检验：若是左括号，入栈；若是右括号，出栈一个左括号判断是否与之匹配；是其他字符，不检验。检验到字符串尾，还要检查栈是否为空。只有栈空，整个字符串才是括号匹配的。void check(SqStack S,char *p);//对于*p指向的字符串序列，输出其中匹配的括号对 （6）主函数中实现输入和输出功能 SqStack S; //定义一个顺序栈 char ch[MAXNUM];//声明一个存储表达式的数组 1.3实验步骤： #include stdio.h #include stdlib.h #include string.h #define STACK_INIT_SIZE 20 #define STACKINCREMENT 10 typedef char SelemType; typedef struct{ SelemType *base; SelemType *top; int stacksize;//栈的存储长度 }SqStack;//顺序栈名 void InitStack(SqStack *S)//初始化栈 { S-base=malloc(STACK_INIT_SIZE * sizeof(SelemType)); if(!S-base) { printf(初始化失败！\n); exit(0); } else { S-top=S-base; S-stacksize=STACK_INIT_SIZE; printf(初始化成功！\n); } } void Push(SqStack *S,SelemType e)//插入x为新的栈顶元素 { if(S-top-S-base=S-stacksize) { S-base=(SelemType *)realloc(S-base,(S-stacksize+STACKINCREMENT) *sizeof(SelemType)); if(!S-base) { printf(开辟内存失败！\n); exit(0); } S-top=S-base+S-stacksize; S-stacksize+=STACKINCREMENT; } *S-top = e; S-top++; } int Pop(SqStack *S) { char e; if(S-base==S-top) { printf(此栈为空！\n); return 0; } else { e=* --S-top; return 1; } } void Check(SqStack *S) { int i,j=0; char ch[20],ch1[20]=\0; printf(请输入字符串序列：); scanf(%s,ch); for(i=0;istrlen(ch);i++) { if(ch[i]==( || ch[i]==[) { Push(S,ch[i]); ch1[j]=ch[i]; j++; } else if(ch[i]==) *(S-top-1)==( || ch[i]==] *(S-