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

如有侵权，请联系网站删除，仅供学习与交流实验7 栈的顺序表示和实现【精品文档】第 7 页浙江大学城市学院实验报告课程名称 数据结构基础 实验项目名称 实验七 栈的顺序表示和实现 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1、掌握栈的存储结构及其基本操作。学会定义栈的顺序存储结构及其各种基本操作的实现。2、掌握栈的后进先出原则。3、通过具体的应用实例，进一步熟悉和掌握栈在实际问题中的运用。二. 实验内容1、设栈采用顺序存储结构（用动态数组），请编写栈的各种基本操作的实现函数，并存放在头文件test7.h中。同时建立一个验证操作实现的主函数文件test7.cpp，编译并调试程序，直到正确运行。 提示： 栈的动态数组顺序存储结构可定义如下： struct Stack ElemType *stack ;/ 存栈元素 int top; / 栈顶指示器 int MaxSize; / 栈的最大长度 栈的基本操作可包括： void InitStack (Stack &S); /构造一个空栈 S int EmptyStack (Stack S); /若栈S为空栈返回1，否则返回0 void Push(Stack &S, ElemType item); /元素 item进栈 ElemType Pop(Stack &S); /栈S的栈顶元素出栈并返回 ElemType Peek(Stack S); /取栈S的当前栈顶元素并返回 void ClearStack (Stack &S); /清除栈s，使成为空栈2、应用：写一函数，判断给定的字符串是否中心对称。如字符串“abcba”、“abccba”均为中心对称，字符串“abcdba”不中心对称。要求利用test7.h中已实现的有关栈的基本操作函数来实现。请把该函数添加到文件test7.cpp中的主函数前，并在主函数中添加相应语句进行测试。函数原型如下： int IsReverse(char *s) /判断字符串S是否中心对称，是返回1，否则返回03、填写实验报告，实验报告文件取名为report7.doc。4、上传实验报告文件report7.doc 、源程序文件test7.cpp及test7.h到Ftp服务器上（ ）自己的文件夹下。三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路）函数：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，证明出栈操作成功。选作部分测试数据：achilleselihca结果分析：输出判断为NO，不是中心对称，正确。五. 心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）