栈的课程设计报告.doc

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