数据结构实验报告——实验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 输入元素 将元素依次入栈 遍历打印栈中元素 输出栈顶元素 打印被输出的元素 遍历打印栈中元素 结束 1
2.
开始 构建空栈s 输入表达式 使用函数count判断表达式中括号是否匹配 输出匹配错误 输出匹配正确 结束
五、程序代码
（给出必要注释） 1.
#include
typedef struct node* SqStack; typedef char ElemType;
struct node//栈的数据结构 {
int top;
ElemType data[MaxSize]; };
void StatusInitStack(SqStack *L)//构造空栈S {
(*L) = (SqStack*)malloc(sizeof(SqStack)); (*L)->top = -1; }
2
void StatusPush(SqStack L, ElemType e)//元素e入栈S {
if (L->top == MaxSize - 1) {
printf(\栈满\\n\ } else {
L->top++;
L->data[L->top] = e; } }
void StatusPop(SqStack L, ElemType *e)//栈S出栈，元素为e {
if (L->top == -1) {
printf(\栈空\\n\ } else {
*e = L->data[L->top]; L->top--; } }
void Print(SqStack L)//遍历输出 {
int i = 0;
for(i = 0; i <= L->top; i++) {
printf(\ }
printf(\}
int main() {
SqStack s; ElemType e; ElemType* y; y = &e;
StatusInitStack(&s);
printf(\输入入栈数据:\ scanf(\
3
while (e!='\\n') {
StatusPush(s, e); scanf(\ }
printf(\目前栈中元素为:\\n\ Print(s);
StatusPop(s, y);
printf(\出栈元素是:%c\\n\
printf(\栈顶元素出栈后，栈为:\\n\ Print(s); } 2.
#include
#define STACK_INIT_SIZE 10 #define STACK_GROW_SIZE 5 #define ELEMTYPE char
typedef 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) /*往栈顶插入元素即进栈*/
4
{
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 e[STACK_INIT_SIZE*2]; ELEMTYPE e1; int i;
InitStack(s); gets(e);
if ('\\n'==e[strlen(e)-1]) e[strlen(e)-1]=0; for (i=0; e[i]!='\\0'; i++) {
switch (e[i]) {
case '(': case '[': case '{':
Push(s,e[i]); break; case ')': case ']': case '}':
if(StackEmpty(s)) {
printf(\匹配错误\\n\
5