201431060399 高富奕 实验3

实验报告课程数据结构实验项目3、栈的应用成绩专业班级软件工程2014级1班指导教师朱小梅姓名高富奕学号201431060399实验日期2015.10.20一、实验目的：（1）掌握栈的存储结构表示方法（2）掌握栈基本运算实现二、实验内容：1.创建测试工程（1）启动VC++6.0，选择菜单“文件”－“新建”；（2）在打开的对话框中选中“工程”选项卡；（3）选择工程类型“Win32ConsoleApplication”；（4）在“工程名称”处输入工程的名字lab3_学号姓名；（红色字部分替换为本人实际学号姓名）（5）在“位置”处点击按钮，选择工程存放的目录位置；（6）按“确定”按钮，在出现的向导对话框中，选择“一个空工程”，按“完成”。说明：完成以上步骤后，VC++6.0将在指定的目录位置下创建与工程名同名的目录（如e:\lab3_学号姓名）；该目录包含了测试工程的所有文件，其中lab3_学号姓名.dsw是工程文件，是工程的主文件。2.顺序栈的基本操作与应用实现（1）按照以上步骤完成新建工程（lab3）后，选择菜单“文件”-“新建”；（2）在打开的对话框中选中“文件”选项卡；（3）选择文件类型“C++SourceFile”；（4）在“文件名”处输入程序文件的名字stack_学号姓名；（5）按“确定”按钮，进入代码编写窗口。说明：完成以上步骤后，VC++6.0将在工程的文件目录下创建单链表的实现源代码文件（stack_学号姓名.cpp）。（6）输入以下参考程序代码段，仔细阅读程序，正确理解各函数的功能，并按要求将代码补充完整；#includestdio.h#includestdlib.h#defineOK1#defineERROR0#defineOVERFLOW-1#defineMAXSIZE20typedefintStatus;typedefintSElemType;typedefstruct{SElemTypebase[MAXSIZE];inttop;}SqStack;voidInitStack(SqStack&S){//请编码实现初始化一个空栈SS.top=0;}StatusPush(SqStack&S,SElemTypee){//请编码实现将元素值e压入栈S。若入栈失败返回ERROR，否则返回成功状态值OKif(S.top==MAXSIZE)returnERROR;S.base[S.top]=e;S.top++;returnOK;}StatusPop(SqStack&S,SElemType&e){//请编码实现弹出S的栈顶元素，并将其值通过e传出。若出栈失败返回ERROR，否则返回成功状态值OKif(S.top==0)returnERROR;S.top--;e=S.base[S.top];returnOK;}StatusStackEmpty(SqStackS){//请编码实现判断栈S是否为空。若栈为空返回OK,否则返回ERRORif(S.top==0)returnOK;elsereturnERROR;}voidconversion(intN){inte;SqStackS;InitStack(S);while(N){Push(S,N%2);//将N取模后压入栈SN=N/2;//将N整除2}printf(转换所得结果为：);while(!StackEmpty(S)){Pop(S,e);printf(%d,e);}printf(\n);}//conversionvoidmain(){intN;printf(输入任意非负十进制整数：);scanf(%d,&N);conversion(N);}3.执行程序，记录程序运行结果（运行结果截图要求保留完整标题栏信息）：4.仔细阅读分析程序代码与运行结果以后，请回答以下问题：（1）当从键盘输入十进制整数为10时，conversion函数中第一个while循环while(N){Push(S,N%2);//将N取模后压入栈SN=N/2;//将N整除2}结束以后，栈S中从栈底到栈顶的元素值分别为多少？请依次列出。0101（3）函数conversion实现的功能是什么？将非负十进制整数转换为2进制数。三、选作内容：任意输入一个数学表达式，判断括号（包括大括号、中括号和小括号）是否匹配。解决思路：可将数学表达式作为字符串进行处理。依次读取字符串中每个字符，对非括号字符不作处理，若为左括号，则应等待与其匹配的右括号。在判断过程中，后读到的左括号比先读到的左括号更急于得到匹配，这一要求与栈先进后出的特点相符，因此可考虑用栈实现括号的匹配。首先，建立一个栈结构，且初始化为空，即令栈顶指针top=0。然后由键盘上随机输入一个带括号的语句或带括号数学表达式，同时将它们保存在一个字符型数组中，再对字符数组中的每个元素进行访问，若是遇到右括号，则将栈中的栈顶元素出栈。当字符数组所有元素都访问完之后，再根据栈顶指针top的值判断左右括号是否匹配，若top=base时，则左右括号匹配，否则，左右括号不匹配。用C语言完成程序设计并上机调试通过。要求：给出程序设计的基本思想、原理和算法描述；对源程序给出注释；给出运行结果。四、实验小结：（阐述实验过程中遇到的问题或心得体会）在实验过程当中，学习巩固了栈的应用的一些相关知识，但还需多加练习，才能熟练掌握并运用。