数据结构实验三 基于数组的栈基本操作实验

实验三 基于数组的栈基本操作实验

一 、实验目的

1．熟悉并能实现栈的定义和基本操作。

2．了解和掌握栈在递归和非递归算法的应用。

二 、实验要求

1．进行栈的基本操作时要注意栈“后进先出”的特性。

2．编写完整程序完成下面的实验内容并上机运行。

3．整理并上交实验报告。

三、实验内容

1.编写程序任意输入栈长度和栈中的元素值，构造一个顺序栈，对其进行入栈、出栈以及取栈顶元素操作。写个功能写成一个函数。

#include\"stdio.h\"

#include

#define MAXSIZE 20

typedef struct

{int data[MAXSIZE];

int top;}seqstack;

seqstack stainit()

{seqstack s;

s.top=-1;

return s;}

seqstack stackpush(seqstack s,int x)

{

if(s.top==MAXSIZE-1)

{ printf(\"overflow\\n\");

exit(0);}

s.top++;

s.data[s.top]=x;

return s;

}

int stackpop(seqstack *st)

{int x;

if(st->top==-1)

{printf(\"empty\\n\");exit(0);}

x=st->data[st->top];

st->top--;

return x;

}

void main()

{seqstack s,*st;

st=&s;

int i,a[5],m;

printf(\"请输入依次入栈中五个值：\\n\");

for(i=0;i<5;i++)

scanf(\"%d\

s=stainit();

for(i=0;i<5;i++)

s=stackpush(s,a[i]);

printf(\"得到的栈顶元素为：\\n\");

for(i=s.top;i>=0;i--)

{m=stackpop(st);

printf(\"%d\\n\

}

2．从键盘上输入一串带括号的字符，如果其中的括号是匹配的，则输出“balance”，如果括号不匹配，则输出“not balance”

#include\"stdio.h\"

#include

#define MAXSIZE 200

typedef struct

{char data[MAXSIZE];

int top;}seqstack;

seqstack stainit()

{seqstack s;

s.top=-1;

return s;}

seqstack stackpush(seqstack s,char x)

{

if(s.top==MAXSIZE-1)

{ printf(\"overflow\\n\");

exit(0);}

s.top++;

s.data[s.top]=x;

return s;

}

char stackpop(seqstack *st)

{char x;

if(st->top==-1)

{printf(\"empty\\n\");exit(0);}

x=st->data[st->top];

st->top--;

return x;

}

void main()

{char c[MAXSIZE],t,m,*p;

int k=0;

seqstack s,*st;

st=&s;

s=stainit();

printf(\"请输入字符串：\");

gets(c);

p=c;

for(;*p!='\\0';p++)

{ if(*p!=')'&&*p!=']')

if(*p=='('||*p=='[')

{t=*p;s=stackpush(s,*p); }

else

continue;

if(s.top>=0)

{if(*p==')'||*p==']')

{m=stackpop(st);

if((m=='('&&*p==')')||(m=='['&&*p==']'))

continue;

else

{printf(\"not balance.\\n\");break;}

}

}

else

{s=stackpush(s,*p);k++;

if(k==1)

printf(\"not balance.\\n\");break;}

}

if(s.top==-1&&*p=='\\0')

printf(\"balance.\\n\");}

四、思考与提高

1．栈的两种存储结构在判别栈空与栈满时，所依据的条件有何不同？

答案略