实验三

桂林电子科技大学数学与计算科学学院实验报告实验室：06303实验日期：2014年6月7日院（系）数学与计算科学学号1200710215姓名岑俞演成绩课程名称数据结构实验项目名称实验三栈的基本运算一，实验目的（1）掌握栈的各种存储结构及基本运算的实现。（2）掌握堆栈后进先出的运算原则在解决实际问题中的应用。（3）复习c语言中相关语句及函数的用法。（4）熟练掌握栈的存储结构及其基本操作。（5）理解所给出的算法，掌握栈在实际中的应用。（6）将上机程序调试通过，并能独立完成一至两个拓展题目。二，实验原理（1）采用顺序存储结构实现栈。（2）采用链表结构实现栈。三，实验内容括号配对检查。试设计一个程序对任意输入的语句或数学表达式，判断其括号是否匹配。若匹配，则返回1，否则返回0。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。首先建立一个栈结构，且初始化栈为空。然后由键盘上随即输入一个带括号的语句或带括号的数学表达式，同时将它们保存在一个字符型数组exps[]中。扫描表达式exps,当遇到“(”、“[”、“{”时，将其入栈。遇到“）”、“]”、“}”时，判断栈顶是否有相匹配的括号。若没有，则退出扫描过程，返回0，否则直到exps扫描完毕为止。若top为0，则返回1。#include“stdio.h”#defineMAXSIZE100#defineTRUE1#defineFALSE0#defineNULL0typedefintdatatype;typedefstruct/*顺序栈的结构体类型定义*/{datatypestack[MAXSIZE];inttop;}seqstack;voidsetnull(seqstack*s)/*置空栈—由于c语言的数组下标是从0开始的，所以置空栈操作时将栈顶指针放在下标为0之前，即-1处。*/{s-top=-1;}intempty(seqstack*s)/*判断当前栈是否为空栈*/{if(s-top0)returnTRUE;elsereturnFALSE;}intpush(seqstack*s,datatypex)/*把元素x压入栈s中*/{if(s-top=MAXSIZE-1){printf(stackoverflow!\n);/*发生上溢*/returnFALSE;}else{s-stack[++s-top]=x;/*栈顶指针上移，数据元素入栈*/returnTRUE;}}datatypepop(seqstack*s)/*弹出当前栈s的栈顶元素*/{if(s-top0){printf(stackempty!\n);/*栈空，返回空值*/returnNULL;}else{s-top--;return(s-stack[s-top+1]);}/*由于return语句的特点，必须先使top减1，然后再执行return语句。而此}时栈顶元素的表示应该为s-top+1.*/intjudge(seqstack*s)/*括号匹配检查算法。--遇到“(”、“[”、“{”时，将其压入栈s中。*/{datatypesymb,ch,store;push(s,'#');symb=getchar();/*从键盘接受字符*/while(symb!='#'){switch(symb){case'(':case'[':case'{':push(s,symb);break;case')':ch=pop(s);if(ch!='(')returnFALSE;break;case']':ch=pop(s);if(ch!='[')returnFALSE;break;case'}':ch=pop(s);if(ch!='{')returnFALSE;break;default:;}symb=getchar();}if(pop(s)=='#')returnTRUE;elsereturnFALSE;}main(){seqstackq;setnull(&q);printf(pleaseinputanexpressendwithsymbol'#':\n);if(judge(&q))printf(yes\n);/*括号匹配，则输出yes*/elseprintf(no\n);/*括号不匹配，则输出no*/}四，实验过程原始记录（数据，图表，计算等）#include“stdio.h”#defineMAXSIZE100#defineTRUE1#defineFALSE0#defineNULL0typedefintdatatype;typedefstruct/*顺序栈的结构体类型定义*/{datatypestack[MAXSIZE];inttop;}seqstack;voidsetnull(seqstack*s)/*置空栈—由于c语言的数组下标是从0开始的，所以置空栈操作时将栈顶指针放在下标为0之前，即-1处。*/{s-top=-1;}intempty(seqstack*s)/*判断当前栈是否为空栈*/{if(s-top0)returnTRUE;elsereturnFALSE;}intpush(seqstack*s,datatypex)/*把元素x压入栈s中*/{if(s-top=MAXSIZE-1){printf(stackoverflow!\n);/*发生上溢*/returnFALSE;}else{s-stack[++s-top]=x;/*栈顶指针上移，数据元素入栈*/returnTRUE;}}datatypepop(seqstack*s)/*弹出当前栈s的栈顶元素*/{if(s-top0){printf(stackempty!\n);/*栈空，返回空值*/returnNULL;}else{s-top--;return(s-stack[s-top+1]);}/*由于return语句的特点，必须先使top减1，然后再执行return语句。而此}时栈顶元素的表示应该为s-top+1.*/intjudge(seqstack*s)/*括号匹配检查算法。--遇到“(”、“[”、“{”时，将其压入栈s中。*/{datatypesymb,ch,store;push(s,'#');symb=getchar();/*从键盘接受字符*/while(symb!='#'){switch(symb){case'(':case'[':case'{':push(s,symb);break;case')':ch=pop(s);if(ch!='(')returnFALSE;break;case']':ch=pop(s);if(ch!='[')returnFALSE;break;case'}':ch=pop(s);if(ch!='{')returnFALSE;break;default:;}symb=getchar();}if(pop(s)=='#')returnTRUE;elsereturnFALSE;}main(){seqstackq;setnull(&q);printf(pleaseinputanexpressendwithsymbol'#':\n);if(judge(&q))printf(yes\n);/*括号匹配，则输出yes*/elseprintf(no\n);/*括号不匹配，则输出no*/}1、预习思考题调试好上述程序后，试着完成以下拓展内容：（1）假定表达式不是通过getchar()函数一个个传送的，而是存放在一个字符数组A[n]中，程序需要做哪些改变？（2）在judge()函数中，如果不用switch()函数，你会怎么处理？2、分析讨论题数制转换问题是栈应用的一个典型实例。将十进制数转换成其它进制的数有一种简单的方法：例：十进制转换成八进制：(66)10=(102)866/8=8余28/8=1余01/8=0余1结果为余数的逆序:102。如果用栈的算法来实现，怎样实现？其基本原理是什么？#includestdio.h#defineMAXSIZE100#defineTRUE1#defineFALSE0#defineNULL0typedefintdatatype;typedefstruct/*顺序栈的结构体类型定义*/{datatypestack[MAXSIZE];inttop;}seqstack;voidconversion(seqstack*s,intn,intr){datatypex;while(n){push(s,n%r);n=n/r;}while(!empty(s)){x=pop(s);printf(%d,x);}printf(\n);}voidmain(){inti=0,j=0;seqstackq;setnull(&q);printf(请输入进制数:);scanf(%d,%d,&i,&j);conversion(&q,i,j);}五，实验结果分析或总结通过这次试验，基本掌握栈了各种存储结构及基本运算的实现，掌握堆栈后进先出的运算原则在解决实际问题中的应用，熟练掌握栈的存储结构及其基本操作，理解所给出的算法，掌握栈在实际中的应用。