厦门理工学院数据结构实验4

《数据结构》实验报告

实验序号：4实验项目名称：栈的操作

学号姓名专业、班

实验地点实1#514指导教师林仙丽实验时间2022-12-06

一、实验目的及要求

1.熟悉栈的基本概念；

2.掌握栈的顺序存储结构；

3.掌握栈的应用。

二、实验设备(环境)及要求

微型计算机；

windows操作系统；

MicrosoftVisualStudio6.0集成开辟环境。

三、实验内容与步骤

1.栈的顺序表表示和实现的如下：

#include<iostream>

ttdefineMaxSize100

usingnamespacestd;

typedefintElemType;

typedefstruct

(

ElemTypedata[MaxSize];

inttop;

}SqStack;

voidInitStack(SqStack*st)〃初始化栈

(

st->top=-l;

}

intStackEmpty(SqStack*st)〃判断栈为空

return(st->top==-l);

}

voidPush(SqStack*st,ElemTypex)〃元素进栈

(

if(st->top==MaxSize~l)

(

printf("栈上溢出!\n〃)；

)

else

(

st->top++;〃挪移栈顶位置

st->data[st->top]=x;//元素进栈

)

}

voidPop(SqStack*st,ElemType&e)〃出栈

(

if(st->top==-l)

(

printf(〃栈下溢出\n〃)；

}

else

(

e=st->data[st->top];//元素出栈

st->top-;〃挪移栈顶位置

)

)

intmain()

(

SqStackL;

SqStack*st=&L;

ElemTypee;

inti;

InitStack(st);

for(i=l;i<10;++i)

(

Push(st,i);

printf(〃入栈元素是：%d\nz，,i);

)

for(i=l;i<10;++i)

(

Pop(st,e);

printf(“出栈元素是：%d\n〃，e);

)

return0;

)

改写以上程序，实现功能如下：

改写Push和Pop函数，使得以上两个函数可以一次性将一个数组入栈和出栈。

2.C/C++的库函数中已经实现了栈，实例如下：

#include<stack>〃引入栈

usingnamespacestd;

intmain()

(

inta;

stack<int>s;

scanf(%d”,&a);

s.push(a);〃入栈

printf("d\n”,s.top());〃取得栈顶元素输出

s.pop();〃出栈

return0;

)

请根据以上程序，设计算法如下(任选一题)：

1.判别一个算术表达式中的圆括号配对是否正确。

运行结果截图:

2.判别一个算术表达式中的圆括号和方括号配对是否正确。

运行结果截图：

四、分析与讨论

因为有了上一章的练习，使得栈做起来相对容易。

对上机实践结果进行分析，上机的心得体味。

五、教师评语成绩

签名：

日期：

附源程序清单：

1.

#include<stdio.h>

include<eh.h>

#include<iostream>

#defineMaxSize100

usingnamespacestd;

typedefintElemType;

typedefstruct

(

ElemTypedata[MaxSize];

inttop;

}SqStack;

voidlnitStack(SqStack*st)〃初始化栈

{

st->top=-1;

)

intStackEmpty(SqStack*st)//判断栈为空

(

return(st->top==-1);

)

voidPush(SqStack*st,ElemTypex)//元素进栈

(

if(st->top==MaxSize-1)

(

printf("栈上溢出柱n");

)

else

st->top++;//挪移栈顶位置

st->data[st->top]=x;〃元素进栈

voidPop(SqStack*st,ElemType&e)//出栈

(

if(st->top==-1)

(

printf("栈下溢出\n下

)

else

(

e=st->data[st->top];〃元素出栈

st->top-;//挪移栈顶位置

voidPush1(SqStack*st)//元素进栈

(

intx[5];

inti;

if(st->top==MaxSize-1)

(

printf("栈上溢出!\n");

)

else

(

printf("请输入5个元素:)

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

scanf("%d",&x[i]);

for(i=4;i>=0;i—)

(

st->top++;〃挪移栈顶位置

st->data[st->top]=x[i];〃元素进栈

)

}

)

voidPop1(SqStack*st)〃出栈

(

inti,x[5];

if(st->top==-1)

printf("栈下溢出\n");

}

else

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

(

x[i]=st・>data[st->top];〃元素出栈

st->top-;〃挪移栈顶位置

)

printff出栈数组为：\nH);

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

printf("%dH,x[i]);

printf(M\n");

)

)

intmain()

(

SqStackL;

SqStack*st=&L;

ElemTypee;

inti,x[5],a;

InitStack(st);

Push1(st);

Push1(st);

Push1(st);

Pop1(st);

/*for(i=1;i<10;++i)

(

Push(st,i);

printf("入栈元素是：%d\n',i);

)

for(i=1;i<10;++i)

(

Pop(st,e);

printf("出栈元素是：%d\n",e);

}*/

return0;

)

2.

#include<stack>〃引入栈

usingnamespacestd;

voidmain()

intsign=1;

chara,b='(*;

stack<char>s;

printf(”请输入算术表达式，以#为结束标志：\nn);

a=getchar();

while(a!='#>)

(

switch(a)

(

case

s.push(a);

break;

case

if(s.top()=='(')

s.pop();

else

sign=0;

br