1、 1 / 21 计算机科学与技术专业 数据结构与算法课程设计报告数据结构与算法课程设计报告 题目：题目： 栈的类设计栈的类设计 作者：作者： 指导教师：指导教师： 20132013 年年 1 1 月月 1212 日日 2 / 21 摘 要 主要实现入栈、出栈、取栈顶三个功能，并调用这三个个功能的 算法（若栈满追加存储；否则将数据压入栈。若栈空则提示错误；否 则删除栈顶元素。若栈空则提示错误，否则提取栈顶。 ）完成栈的中 序遍历，后序遍历，以及中序到后序转换的表达式，最后完成后序表 达式的计算。 3 / 21 目 录 摘要2 一、 概述5 二、数据结构设计8 三、算法设计15 四、源代码说明 五
2、、结果与分析 4 / 21 图 表 目 录 图（1）栈5 图 （2） 入栈、 出栈操作过程6 图（3）功能实现8 图（4）入栈流程图8 图（5）出栈流程图9 图 （6） 链栈结构图12 图 （7） 链栈的入栈、 出栈13 5 / 21 概概 述述 -描述部分描述部分- 栈的概念：栈的概念： 栈 （stack） 是插入和删除操作限定在表尾进行的线性表。 进行插入或删除操作的一端称为栈顶，另一端称为栈底。 栈的逻辑表示为：S =（a1,a2, ,an） 表尾元素 an称为栈顶(top) 表头元素 a1称为栈底(bottom) 不含元素的空表称为空栈 栈的基本运算栈的基本运算包括包括： 初始化；判栈
3、空； 入栈； 出栈； 获取 栈顶；(6)栈中当前元素个数； (7) 清空栈； 栈的运算特性是：栈的运算特性是：后进先出(Last In First Out-LIFO)或先进后出 (First In Last Out-FILO)如图（1）所示。 入栈 出栈 （图 1）栈 Kn K1 K0 栈 顶 栈底 6 / 21 栈初始化：栈初始化：InitStack(&S) 构造了一个空栈。 清空栈清空栈: : ClearStack(&s)将 s 栈置为空栈。 入栈入栈 ： Push(&S，&e) 在栈 s 的顶部插入新元素 e，e 成为新的栈 顶元素，相当于线形表 ListInsert(&L, n+1,
4、e)。 出栈：出栈： Pop(&S, &e) 在栈 s 存在且非空的情况下，返回 S 栈的栈 顶元素，并从 s 栈中删除该栈顶元素；否则返回空元素 NULL，相当 于线性表的 ListDelete(&L, i, &e)。 空栈空栈 1 1 入入 栈栈 2 2 入入 栈栈 2 2 出出 栈栈 1 1 出栈出栈 2 1 1 1 top=-1 top=1 top=2 top=1 top=-1 图（2）入栈、出栈操作过程 用整形元素 top 来指示当前元素位置 。我们可以看到没有数据时的 空栈，此时 top =-1，它可以作为判断空的条件。入栈时加 1，出栈 时减 1，从始至终 top 的值一直是顶元
5、素的下标，这样在获取栈顶的 元素时直接可以通过取栈顶下标的值 从而得到栈顶。但要注意：为 top =-1 的情况，因为一个数组的下标是不可能小于 0 的。 遍历：遍历：所谓遍历，是指沿着某条搜索路线，依次对栈中每个数据均做 一次且仅做一次访问。 7 / 21 获取栈顶元素获取栈顶元素：GetTop(S, &e)在栈 s 存在且非空情况下，读栈顶元 素，栈不变化。与 Pop(&S, &e)的差别在不删除栈顶元素，相当于线 性表的 GetElem(L, I, &e)。 中序转后序中序转后序： 中序是我们常用的表达式格式。即数据-符号-数据或 者符号数据符号数据-符号。 我们将一个正规的计算式压入栈 中， 出栈时变成数据数据符号或者数据数据-符号-符号符 号的格式。这个过程我们称为中序转后
