【vfp精品源码栏目提醒】:本文主要为网学会员提供“栈的课程设计报告 - 大学课件”,希望对需要栈的课程设计报告 - 大学课件网友有所帮助,学习一下!
计算机科学与技术专业 《数据结构与算法》课程设计报告题目: 栈的类设计作者:指导教师: 2013 年 1 月 12 日 摘 要 主要实现入栈、出栈、取栈顶三个功能,并调用这三个个功能的算法(若栈满追加存储;否则将数据压入栈。
若栈空则提示错误;否则删除栈顶元素。
若栈空则提示错误,否则提取栈顶。
)完成栈的中序遍历,后序遍历,以及中序到后序转换的表达式,最后完成后序表达式的计算。
目 录 摘要……………………………………2 一、 概述………………………………………………5 二、数据结构设计……………………………………8 三、算法设计……………………………………………15 四、源代码说明………………………………………… 五、结果与分析………………………………………… 图 表 目 录图(1)栈…………………………………………………………………5图(2)入栈、出栈操作过程………………………………………………6图(3)功能实现…………………………………………………………8图(4)入栈流程图………………………………………………………8图(5)出栈流程图………………………………………………………9图(6)链栈结构图………………………………………………………12图(7)链栈的入栈、出栈………………………………………………13 概 述 -----描述部分------- 栈的概念: 栈(stack)是插入和删除操作限定在表尾进行的线性表。
进行插入或删除操作的一端称为栈顶,另一端称为栈底。
栈的逻辑表示为:S (a1a2 …an) 表尾元素 an 称为栈顶top 表头元素 a1 称为栈底bottom 不含元素的空表称为空栈 栈的基本运算包括: ⑴ 初始化;⑵判栈空; ⑶入栈; ⑷出栈; ⑸ 获取 栈顶;6栈中当前元素个数; 7 清空栈;栈的运算特性是:后进先出Last In First Out--LIFO或先进后出First In Last Out--FILO如图(1)所示。
入栈 出栈 栈顶 Kn … (图 1)栈 K1 栈底 K0 栈初始化:InitStackS 构造了一个空栈。
清空栈: ClearStacks将 s 栈置为空栈。
入栈 : PushS,e 在栈 s 的顶部插入新元素 e,e 成为新的栈顶元素,相当于线形表 ListInsertL n1 e。
出栈: PopS e 在栈 s 存在且非空的情况下,返回 S 栈的栈顶元素,并从 s 栈中删除该栈顶元素;否则返回空元素 NULL,相当于线性表的 ListDeleteL i e。
空栈 1入 栈 2入 栈 2出 栈 1 出栈 2 1 1 1top-1 top1 top2 top1 top-1 图(2)入栈、出栈操作过程用整形元素 top 来指示当前元素位置 。
我们可以看到没有数据时的空栈,此时 top -1,它可以作为判断空的条件。
入栈时加 1,出栈时减 1,从始至终 top 的值一直是顶元素的下标,这样在获取栈顶的元素时直接可以通过取栈顶下标的值 从而得到栈顶。
但要注意:为top -1 的情况,因为一个数组的下标是不可能小于 0 的。
遍历:所谓遍历,是指沿着某条搜索路线,依次对栈中每个数据均做一次且仅做一次访问。
获取栈顶元素:GetTopS e在栈 s 存在且非空情况下,读栈顶元素,栈不变化。
与 PopS e的差别在不删除栈顶元素,相当于线性表的 GetElemL I e。
中序转后序:中序是我们常用的表达式格式。
即数据--符号--数据或者符号—数据—符号—数据--符号。
我们将一个正规的计算式压入栈中,出栈时变成数据—数据—符号或者数据—数据--符号--符号—符号的格式。
这个过程我们称为中序转后序。
例如:abc-d 是一个中序表达式,转后序之后变成了 abcd-。
后序表达式:逻辑关系是数据在前,符号在后的表达式。
例如:abc-。
------简单算法分析--------入栈:初始条件是栈已存在;操作结果是推入栈内的新元素 e 为新的栈顶元素。
出栈:初始条件是栈已存在;操作结果是删除栈顶元素,并返回栈顶元素。
遍历: 初始条件是有若干的数据存在。
操作结果是将所有数据依次输出,得到所有数据。
获取栈顶元素:初始条件是栈已存在且非空;操作结果是得到栈顶元素。
中序转后序:首先有一个中序表达式存在