数据结构实验4

数据结构数据结构 实验报告实验报告 实验序号 4 实验项目名称 栈的操作 学 号姓 名专业 班 实验地点指导教师实验时间 一 实验目的及要求 1 熟悉栈的基本概念 2 掌握栈的顺序存储结构 3 掌握栈的应用 二 实验设备 环境 及要求 微型计算机 windows 操作系统 Microsoft Visual Studio 6 0 集成开发环境 三 实验内容与步骤 1 栈的顺序表表示和实现的如下 include define MaxSize 100 using namespace std typedef int ElemType typedef struct ElemType data MaxSize 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 else st top 移动栈顶位置 st data st top x 元素进栈 void Pop SqStack st ElemType else e st data st top 元素出栈 st top 移动栈顶位置 int main SqStack L SqStack st ElemType e int i InitStack st for i 1 i 10 i Push st i printf 入栈元素是 d n i for i 1 i 10 i Pop st e printf 出栈元素是 d n e return 0 改写以上程序 实现功能如下 1 调用栈操作函数实现判别一个算术表达式中的圆括号配对是否正确 2 改写 Push 和 Pop 函数 使得以上两个函数可以一次性将一个数组入栈和出 栈 1 2 2 C C 的库函数中已经实现了栈 实例如下 include 引入栈 using namespace std int main int a stacks scanf d s push a 入栈 printf d n s top 取得栈顶元素输出 s pop 出栈 return 0 请根据以上程序 设计算法如下 判别一个算术表达式中的圆括号和方括号配对是否正确 四 分析与讨论 五 教师评语 签名 日期 成绩 附源程序清单 1 1 include define MaxSize 100 define SUCCESS 0 define ERROR 1 typedef struct int nData MaxSize int nTop SqStack void InitStack SqStack PST List 初始化栈 PST List nTop 1 int StackEmpty SqStack PST List 判断栈为空 if PST List nTop 1 return ERROR else return SUCCESS void Push SqStack PST List int nData 元素进栈 if PST List nTop MaxSize 1 printf 栈上溢出 n else PST List nTop 移动栈顶位置 PST List nData PST List nTop nData 元素进栈 void Pop SqStack PST List int pnData 出栈 if PST List nTop 1 printf 栈下溢出 n else pnData 元素出栈 PST List nTop 移动栈顶位置 int GetTop SqStack PST List 获取栈顶 if StackEmpty PST List 先判断是否为空栈 不是空栈则返回栈顶 return PST List nData PST List nTop else return 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 否则就将判断标志置1 nSign 1 break default 对于其他的输入不做操作 break cData getchar if GetTop PST List 结束输入后判断栈顶是否还有左括号 nSign 1 if nSign 1 printf 圆括号配对不成功 n else printf 圆括号配对成功 n return SUCCESS int main SqStack ST List SqStack PST List int nData int nIndex InitStack PST List JudgeBrackets PST List for nIndex 1 nIndex 10 nIndex Push PST List nIndex printf 入栈元素是 d n nIndex for nIndex 1 nIndex nTop MaxSize 1 printf 栈上溢出 n else if MaxSize PST List nTop 1 nLength 判断栈剩余空间是否大于要 入栈的元素个数 for nIndex 0 nIndex nTop 移动栈顶位置 PST List nData PST List nTop pnData nIndex 元素进栈 printf 入栈元素为 d n PST List nData PST 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 nData PST List nTop pnData nIndex 元素进栈 printf 入栈元素为 d n PST List nData PST List nTop printf 元素进栈成功 n void Pop SqStack PST List int pnData int nLength 出栈 int nIndex 0 if PST List nTop 1 printf 栈下溢出 n else if nLength nTop 1 要出栈元素个数小于当前栈顶 for nIndex 0 nIndex nData PST List nTop 元素出栈 printf 出栈元素是 d n PST List nData PST List nTop PST List nTop 移动栈顶位置 printf 元素出栈成功 n else 要出栈元素个数大于当前栈顶 把栈内全部元素出栈 nLength PST List nTop 1 for nIndex 0 nIndex nData PST List nTop 元素出栈 printf 出栈元素是 d n PST List nData PST List nTop PST List nTop 移动栈顶位置 printf 元素出栈成功 n 2 include 引入栈 include using namespace std int main char cBuff int nSign 0 判断标志 初值为 0 stackStList printf 输入表达式 以 号结束输入 n do scanf c switch cBuff case StList push cBuff 入栈 printf 入栈 c n cBuff break case StList push cBuff 入栈 printf 入栈 c n cBuff break case if StList empty 对于一开始就输入 的情况作出判断 直接配对失败 nSign 1 else if StList top 取得栈顶元素输出 出栈 printf 出栈 c n StList top StList pop else nSign 1 break case if StList empty 对于一开始就输入 的情况作出判断 直接配对失败 nSign 1 else if StList top 取