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

1、精选优质文档-倾情为你奉上*实验题目：栈的基本运算 实验者信息：班级 ，姓名 庞文正，学号 实验完成的时间 3：00*一、 实验目的1，掌握栈的各种存储结构及基本运算的实现。2，掌握堆栈后进先出的运算原则在解决实际问题中的应用。3，复习c语言中相关语句及函数的用法。二、 实验内容括号配对检查。试设计一个程序对任意输入的语句或数学表达式，判断其括号是否匹配。若匹配，则返回1，否则返回0。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。三、 算法设计与编码1. 本实验用到的理论知识总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实

2、验密切相关，最好能加上自己的解释。2. 算法概要设计给出实验的数据结构描述，程序模块、功能及调用关系首先建立一个栈结构，且初始化栈为空。然后由键盘上随即输入一个带括号的语句或带括号的数学表达式，同时将它们保存在一个字符型数组exps中。扫描表达式exps,当遇到“(”、“”、“”时，将其入栈。遇到“）”、“”、“”时，判断栈顶是否有相匹配的括号。若没有，则退出扫描过程，返回0，否则直到exps扫描完毕为止。若top为0，则返回1。#include#define MAXSIZE 100#define TRUE 1#define FALSE 0typedef int datatype; typed

3、ef struct /顺序栈的结构体定义 datatype stackMAXSIZE;int top;seqstack;void setnull(seqstack *s) /置空栈-由于c语言的数组下标是从0开始的，所以置 s-top=-1; / s-top=-1; 空栈操作时将栈顶指针放在下标为0之前，即-1处。int empty(seqstack *s) /*判断当前栈是否为空栈*/ if(s-toptop=MAXSIZE-1) printf(stack overflow!n); /*发生上溢*/ return FALSE; else s-stack+s-top=x; /*栈顶指针上移，数

4、据元素入栈*/ return TRUE; datatype pop(seqstack *s) /*弹出当前栈s的栈顶元素*/ if(s-toptop-; return(s-stacks-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(

5、symb) 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; int jinzhishuchu(seqstack *s) int

6、x,symb; scanf(%d,&symb);/*从键盘接受字符*/ while(symb!=0) push(s,symb%8); symb=symb/8; while (!empty(s) x=pop(s); /出栈操作 printf(%d,x); /依次输出出栈结果 printf(n); main() seqstack q; setnull(&q); printf(please input an express end with symbol #:n); if(judge(&q) printf(yesn); /*括号匹配，则输出yes*/ else printf(non); /*括号不匹

7、配，则输出no*/jinzhishuchu(&q); 四、 运行与测试（1） 在调试程序的过程中遇到什么问题，是如何解决的？答：遇到很多括号不匹配（2） 设计了那些测试数据？测试结果是什么？（3） 程序运行的结果如何？成功运行！1、 预习思考题调试好上述程序后，试着完成以下拓展内容：（1） 假定表达式不是通过getchar()函数一个个传送的，而是存放在一个字符数组An中，程序需要做哪些改变？将while改为for（i=0;i=strlen(An);i+）switch(Ai) case (: case : case : push(s,symb);break; case ): ch=pop(s)

8、; 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=) 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; 2、 分析讨论题：数制转换问题是栈应用的一个典型实例。将十进制数转换成其它进制的数有一种简单的方法：例：十进制转换成八进制：(66)10=(102)866/8=8 余 28/8=1 余 01/8=0 余 1结果为余数的逆序:102 。如果用栈的算法来实现，怎样实现？其基本原理是什么？int jinzhishuchu(seqstack *s) /括号匹配检查算法。-遇到(、时, int x,symb; scanf(%d,&symb);/*从键盘接受字符*/ while(s