数据结构实验

数据结构实验报告实验序号：4 实验项目名称：栈的操作学号姓名专业、班实验地点指导教师实验时间一、实验目的及要求1. 熟悉栈的基本概念；2. 掌握栈的顺序存储结构；3掌握栈的应用。二、实验设备（环境）及要求微型计算机；windows 操作系统；Microsoft Visual Studio 6.0集成开发环境。三、实验内容与步骤1.栈的顺序表表示和实现的如下：#include #define MaxSize 100using namespace std;typedef int ElemType;typedef structElemType dataMaxSize;int top;SqStack;void InitStack(SqStack *st) /初始化栈st-top=-1;int StackEmpty(SqStack *st) /判断栈为空return (st-top=-1);void Push(SqStack *st,ElemType x) /元素进栈if(st-top=MaxSize-1)printf(栈上溢出!n);elsest-top+; /移动栈顶位置st-datast-top=x; /元素进栈void Pop(SqStack *st,ElemType &e) /出栈if(st-top=-1)printf(栈下溢出n);elsee=st-datast-top; /元素出栈st-top-; /移动栈顶位置int main()SqStack L;SqStack *st=&L;ElemType e;int i;InitStack(st);for(i=1;i10;+i)Push(st,i);printf(入栈元素是：%dn,i);for(i=1;i10;+i)Pop(st,e);printf(出栈元素是：%dn,e);return 0; 改写以上程序，实现功能如下：1）调用栈操作函数实现判别一个算术表达式中的圆括号配对是否正确。2）改写Push和Pop函数，使得以上两个函数可以一次性将一个数组入栈和出栈。（1）（2）2.C/C+的库函数中已经实现了栈，实例如下：#include /引入栈using namespace std;int main()int a;stacks;scanf(%d,&a);s.push(a); /入栈printf(%dn,s.top(); /取得栈顶元素输出s.pop(); /出栈return 0; 请根据以上程序，设计算法如下：判别一个算术表达式中的圆括号和方括号配对是否正确。四、分析与讨论五、教师评语签名：日期：成绩附源程序清单：1.（1）#include #define MaxSize 100#define SUCCESS 0#define ERROR -1typedef structint nDataMaxSize;int nTop;SqStack;void InitStack(SqStack *PST_List) /初始化栈PST_List -nTop = -1;int StackEmpty(SqStack *PST_List) /判断栈为空if (PST_List -nTop = -1)return ERROR;elsereturn SUCCESS;void Push(SqStack *PST_List, int nData) /元素进栈if (PST_List -nTop = MaxSize - 1)printf(栈上溢出!n);elsePST_List -nTop+; /移动栈顶位置PST_List -nDataPST_List-nTop = nData; /元素进栈void Pop(SqStack *PST_List, int *pnData) /出栈if (PST_List -nTop = -1)printf(栈下溢出n);elsepnData = &PST_List -nDataPST_List -nTop; /元素出栈PST_List -nTop-; /移动栈顶位置int GetTop(SqStack *PST_List) /获取栈顶if ( ! StackEmpty(PST_List) ) /先判断是否为空栈,不是空栈则返回栈顶return (PST_List-nDataPST_List -nTop);elsereturn ERROR;int JudgeBrackets(SqStack *PST_List) /判断圆括号是否配对成功char cData;/输入变量int nSign = 0;/判断标志int *pnData = NULL;/传入pop中的参数printf(请输入一个表达式：);cData = getchar();while (cData != n) /按下回车结束死循环switch (cData)case (: /对于左括号就入栈Push(PST_List, (int)cData); break;case ):if (GetTop(PST_List) = () /栈顶有左括号就出栈Pop(PST_List, pnData);else /否则就将判断标志置1nSign = 1;break;default: /对于其他的输入不做操作 break;cData = getchar();if (GetTop(PST_List) = () /结束输入后判断栈顶是否还有左括号nSign = 1;if (nSign = 1)printf(圆括号配对不成功！n);elseprintf(圆括号配对成功！n);return SUCCESS;int main()SqStack ST_List;SqStack *PST_List = &ST_List;/int nData;/int nIndex;InitStack(PST_List);JudgeBrackets(PST_List);/*for(nIndex = 1; nIndex 10; +nIndex)Push(PST_List, nIndex);printf(入栈元素是：%dn, nIndex);for(nIndex = 1; nIndex nTop = MaxSize - 1)printf(栈上溢出!n);elseif( ( MaxSize - PST_List -nTop - 1) = nLength) /判断栈剩余空间是否大于要入栈的元素个数for(nIndex = 0; nIndex nTop+; /移动栈顶位置 PST_List -nDataPST_List-nTop = pnDatanIndex; /元素进栈printf(入栈元素为: %d n, PST_List -nDataPST_List-nTop);printf(元素进栈成功!n);else /栈空间小于要入栈元素的个数，只入栈剩余空间大小的元素个数printf(栈空间只剩 %d 个， 而数组元素有 %d 个，所以只入栈 %d 个!n, (MaxSize - PST_List -nTop -1 ), nLength, (MaxSize - PST_List -nTop - 1);nLength = MaxSize - PST_List -nTop - 1; /长度赋值为剩余空间大小for(nIndex = 0; nIndex nTop+; /移动栈顶位置 PST_List -nDataPST_List-nTop = pnDatanIndex; /元素进栈printf(入栈元素为: %d n, PST_List -nDataPST_List-nTop);printf(元素进栈成功!n);void Pop(SqStack *PST_List, int *pnData, int nLength) /出栈int nIndex = 0 ;if (PST_List -nTop = -1)printf(栈下溢出n);elseif( nLength nTop + 1)/要出栈元素个数小于当前栈顶for(nIndex = 0; nIndex nDataPST_List -nTop; /元素出栈printf(出栈元素是：%dn, PST_List -nDataPST_List -nTop); PST_List -nTop-; /移动栈顶位置printf(元素出栈成功!n);else /要出栈元素个数大于当前栈顶，把栈内全部元素出栈nLength = PST_List -nTop + 1;for(nIndex = 0; nIndex nDataPST_List -nTop; /元素出栈printf(出栈元素是：%dn, PST_List -nDataPST_List -nTop); PST_List -nTop-; /移动栈顶位置printf(元素出栈成功!n);2.#include /引入栈#includeusing namespace std;int main()char cBuff;int nSign = 0; /判断标志，初值为0stackStList;printf(输入表达式，以 # 号结束输入!n);doscanf(%c, &cBuff);switch (cBuff)case :StList.push(cBuff); /入栈/printf(入栈：%cn, cBuff);break;case (:StList.push(cBuff); /入栈/printf(入栈：%cn, cBuff);break;case ):if(StList.empty() /对于一开始就输入)的情况作出判断，直接配对失败 nSign = -1;elseif (StList.top() = () /取得栈顶元素输出 /出栈 /printf(出栈：%cn, StList.top(); StList.pop(); else nSign = -1; break;case :if(StList.empty() /对于一开始就输入的情况作出判断，直接配对失败 nSign = -1;elseif (StList.top() = ) /取得栈顶元素输出 /出栈 /