实验7栈的顺序表示和实现

浙江大学城市学院实验报告浙江大学城市学院实验报告 课程名称课程名称 数据结构基础 实验项目名称实验项目名称 实验七 栈的顺序表示和实现 实验成绩实验成绩 指导老师 签名指导老师 签名 日期日期 一一 实验目的和要求实验目的和要求 1 掌握栈的存储结构及其基本操作 学会定义栈的顺序存储结构及其各种基本 操作的实现 2 掌握栈的后进先出原则 3 通过具体的应用实例 进一步熟悉和掌握栈在实际问题中的运用 二二 实验内容实验内容 1 设栈采用顺序存储结构 用动态数组 请编写栈的各种基本操作的实现函 数 并存放在头文件 test7 h 中 同时建立一个验证操作实现的主函数文件 test7 cpp 编译并调试程序 直到正确运行 提示 栈的动态数组顺序存储结构可定义如下 struct Stack ElemType stack 存栈元素 int top 栈顶指示器 int MaxSize 栈的最大长度 栈的基本操作可包括 void InitStack Stack 构造一个空栈 S int EmptyStack Stack S 若栈 S 为空栈返回 1 否则返回 0 void Push Stack 元素 item 进栈 ElemType Pop Stack 栈 S 的栈顶元素出栈并返回 ElemType Peek Stack S 取栈 S 的当前栈顶元素并返回 void ClearStack Stack 清除栈 s 使成为空栈 2 应用 写一函数 判断给定的字符串是否中心对称 如字符串 abcba abccba 均为中心对称 字符串 abcdba 不中心对称 要求利用 test7 h 中 已实现的有关栈的基本操作函数来实现 请把该函数添加到文件 test7 cpp 中 的主函数前 并在主函数中添加相应语句进行测试 函数原型如下 int IsReverse char s 判断字符串 S 是否中心对称 是返回 1 否则返回 0 3 填写实验报告 实验报告文件取名为 report7 doc 4 上传实验报告文件 report7 doc 源程序文件 test7 cpp 及及 test7 h 到 Ftp 服务器上 ftp 10 61 14 240 5000 自己的文件夹下 三三 函数的功能说明及函数的功能说明及算法思路算法思路 包括每个函数的功能说明 及一些重要函数的算法实现思路 函数 void InitStack Stack S 功能 构造一个空栈 S 思路 采用动态数组的方式新建一个大小为 10 的空栈 S 函数 int EmptyStack Stack S 功能 判断是否为空栈 若栈 S 为空栈返回 1 否则返回 0 思路 以 top 值作为判断条件 当 top 为 1 时表明为空栈 其他则为非空栈 函数 void Push Stack S ElemType item 功能 元素 item 进栈 思路 首先判断栈是否已满 若已满则动态申请空间将数组大小扩大一倍 通 过改变 top 的值确定入栈位置并将 item 入栈 函数 ElemType Pop Stack S 功能 栈 S 的栈顶元素出栈并返回 思路 以 top 值减 1 的方式进行出栈操作 并返回出栈的栈顶元素 函数 ElemType Peek Stack S 功能 取栈 S 的当前栈顶元素并返回 思路 返回当前 top 所指的栈顶元素值 函数 void ClearStack Stack S 功能 清除栈 s 使成为空栈 思路 释放数组空间 置 top 为 1 表示空栈 置 MaxSize 为 0 表示无空间 函数 选作 int IsReverse char s 功能 判断字符串 S 是否中心对称 是返回 1 否则返回 0 思路 将字符串的前一半字符依次入栈 再全部出栈并依次与字符串后一半字 符对比 只要有一个不相同 就说明不是中心对称 全部相同 表明是中心对 称 四四 实验结果与分析实验结果与分析 包括运行结果截图 结果分析等 栈操作部分 测试数据 22 30 16 36 58 80 55 结果分析 栈顶元素为 55 正确 3 次出栈元素依次为 55 80 58 正确 出栈 操作完成后栈顶元素为 36 证明出栈操作成功 选作部分 测试数据 abcba 结果分析 输出判断为 YES 是中心对称 正确 栈操作部分 测试数据 42 5 2 结果分析 栈顶元素为 2 正确 2 次出栈元素依次为 2 5 正确 出栈操作完 成后栈顶元素为 42 证明出栈操作成功 选作部分 测试数据 abccba 结果分析 输出判断为 YES 是中心对称 正确 栈操作部分 测试数据 28 36 42 44 65 65 74 80 结果分析 栈顶元素为 80 正确 3 次出栈元素依次为 80 74 65 正确 出栈 操作完成后栈顶元素为 65 证