数据结构实验-栈的基本运算

******************************* 实验题目：栈的基本运算 实验者信息：

班级 13007102，姓名 庞文正，学号 1300710226 实验完成的时间 3：00

****************************** 一、 实验目的

1，掌握栈的各种存储结构及基本运算的实现。

2，掌握堆栈后进先出的运算原则在解决实际问题中的应用。 3，复习c语言中相关语句及函数的用法。 二、 实验内容

括号配对检查。试设计一个程序对任意输入的语句或数学表达式，判断其括号是否匹配。若匹配，则返回1，否则返回0。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。

三、 算法设计与编码 1. 本实验用到的理论知识

总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，最好能加上自己的解释。 2. 算法概要设计

给出实验的数据结构描述，程序模块、功能及调用关系

首先建立一个栈结构，且初始化栈为空。然后由键盘上随即

----完整版学习资料分享----

=====WORD完整版----可编辑----专业资料分享=====

输入一个带括号的语句或带括号的数学表达式，同时将它们保存在一个字符型数组exps[]中。扫描表达式exps,当遇到“(”、“[”、“{”时，将其入栈。遇到“）”、“]”、“}”时，判断栈顶是否有相匹配的括号。若没有，则退出扫描过程，返回0，否则直到exps扫描完毕为止。若top为0，则返回1。 #include #define MAXSIZE 100 #define TRUE 1 #define FALSE 0

typedef int datatype;

typedef struct //顺序栈的结构体定义 {

datatype stack[MAXSIZE]; int top;

}seqstack;

void setnull(seqstack *s) //置空栈-由于c语言的数组下标是从0开始的，所以置

{s->top=-1;} // {s->top=-1;} 空栈操作时将栈顶指针放在下标为0之前，即-1处。

int empty(seqstack *s) /*判断当前栈是否为空栈*/

----完整版学习资料分享----

=====WORD完整版----可编辑----专业资料分享=====

{

if(s->top<0) return TRUE; else

return FALSE; }

int push(seqstack *s,datatype x) /*把元素x压入栈s中*/ {

if(s->top>=MAXSIZE-1) {

printf(\"stack overflow!\\n\"); /*发生上溢*/ return FALSE; } else {

s->stack[++s->top]=x; /*栈顶指针上移，数据元素入栈*/

return TRUE; } }

datatype pop(seqstack *s) /*弹出当前栈s的栈顶元素*/ {

----完整版学习资料分享----

=====WORD完整版----可编辑----专业资料分享=====

if(s->top<0) {

printf(\"stack empty!\\n\"); /*栈空，返回空值*/

return -1; } else {

s->top--;

return(s->stack[s->top+1]);

}//由于return语句的特点，必须先使top减1，然后再执行return语句。而此

} // 时栈顶元素的表示应该为s->top+1.

int judge(seqstack *s) //括号匹配检查算法。--遇到\"(\"、\"[\"、\"{\"时,

{ // 将其压 栈s中。 datatype symb,ch,store; push(s,'#');

symb=getchar();/*从键盘接受字符*/ while(symb!='#') {

switch(symb) {

----完整版学习资料分享----

=====WORD完整版----可编辑----专业资料分享=====

case '(': case '[': case '{':

push(s,symb);break;

case ')':

ch=pop(s);

if(ch!='(') return FALSE; break;

case ']':

ch=pop(s);

if(ch!='[') return FALSE; break;

case '}':

ch=pop(s);

if(ch!='{') return FALSE; break;

default: ; }

symb=getchar(); }

if(pop(s)=='#') return TRUE; else return FALSE; }

----完整版学习资料分享----

=====WORD完整版----可编辑----专业资料分享=====

int jinzhishuchu(seqstack *s) {

int x,symb;

scanf(\"%d\从键盘接受字符*/ while(symb!=0) {

push(s,symb%8); symb=symb/8; }

while (!empty(s)) {

x=pop(s); //出栈操作

printf(\"%d\ //依次输出出栈结果 } printf(\"\\n\"); } main() {

seqstack q; setnull(&q);

printf(\"please input an express end with symbol '#':\\n\");

----完整版学习资料分享----

=====WORD完整版----可编辑----专业资料分享=====

if(judge(&q))

printf(\"yes\\n\"); /*括号匹配，则输出yes*/ else

printf(\"no\\n\"); /*括号不匹配，则输出no*/

jinzhishuchu(&q); }

四、 运行与测试

（1） 在调试程序的过程中遇到什么问题，是如何解决的？

答：遇到很多括号不匹配

（2） 设计了那些测试数据？测试结果是什么？

（3） 程序运行的结果如何？

----完整版学习资料分享----

=====WORD完整版----可编辑----专业资料分享=====

成功运行！ 1、 预习思考题

调试好上述程序后，试着完成以下拓展内容：

（1） 假定表达式不是通过getchar()函数一个个传送的，而是

存放在一个字符数组A[n]中，程序需要做哪些改变？ 将while改为for（i=0;i<=strlen(A[n]);i++） {

switch(A[i]) {

case '(': case '[': case '{':

push(s,symb);break;

----完整版学习资料分享----

=====WORD完整版----可编辑----专业资料分享=====

case ')':

ch=pop(s);

if(ch!='(') return FALSE; break; case ']':

ch=pop(s);

if(ch!='[') return FALSE; break; case '}':

ch=pop(s);

if(ch!='{') return FALSE; break; default: ; } }

（2） 在judge()函数中，如果不用switch()函数，你会怎么处

理？ 用if替代

if(symb=='(' || symb=='{' || symb=='[') {

----完整版学习资料分享----

=====WORD完整版----可编辑----专业资料分享=====

push(s,symb); }

if(symb==')') {

ch=pop(s);

if(ch!='(') return FALSE; }

if(symb=='}') {

ch=pop(s);

if(ch!='{') return FALSE; }

if(symb==']') {

ch=pop(s);

if(ch!='[') return FALSE; }

----完整版学习资料分享----

=====WORD完整版----可编辑----专业资料分享=====

2、 分析讨论题：

数制转换问题是栈应用的一个典型实例。将十进制数转换成其它进制的数有一种简单的方法：例：十进制转换成八进制：(66)10=(102)8 66/8=8 余 2 8/8=1 余 0 1/8=0 余 1

结果为余数的逆序:102 。如果用栈的算法来实现，怎样实现？其基本原理是什么？

int jinzhishuchu(seqstack *s) //括号匹配检查算法。--遇到\"(\"、\"[\"、\"{\"时, {

int x,symb;

----完整版学习资料分享----

=====WORD完整版----可编辑----专业资料分享=====

scanf(\"%d\从键盘接受字符*/ while(symb!=0) {

push(s,symb%8); symb=symb/8; }

while (!empty(s)) {

x=pop(s); //出栈操作

printf(\"%d\ //依次输出出栈结果 } printf(\"\\n\"); }

----完整版学习资料分享----

=====WORD完整版----可编辑----专业资料分享=====

五、 总结和心得

实验完成后的总结和思考。 此次实验很顺利！

----完整版学习资料分享----