数据结构-栈及其应用.ppt

数据结构-栈 程序=数据结构+算法 对于程序设计来说： 编程语言是工具； 数据结构是基础； 算法设计是方法。 数据结构 数据结构相关概念 数据(data) 计算机科学中指所有能输入到计算机中并被程序处理的符号总称。例如数值、字符、图像、声音都属于数据的范畴。 数据元素(data element) 是数据的基本单位 ，在程序中作为一个整体进行考虑。 　有时一个数据元素有若干数据项。 数据对象(data object)是性质相同的数据元素的集合，是数据的一个子集。 逻辑结构 物理结构 线性表 线性表的两种存储方式 1、顺序存储结构 顺序存储结构是指用一组地址连续的存贮单元依次存储线性表的元素，通常用数组实现。数组的物理实现是一块连续的存储空间，它是按首址（表中第1个元素的地址）十位移来访问每一个元素。 链表的插入与删除 线性表的具体实现 顺序存储结构 用数组类型： list: array [1..maxlen] of elemtp; 链式存储结构 用指针类型 和 动态变量： pointer = nodetype ^ ; nodetype = record data : elemtp ; next : pointer ; end; 顺序存储与链式存储操作的对比 栈 通常栈可以用顺序的方式存储(数组)，分配一块连续的存储区域存放栈中的表目，并用一个变量t指向当前栈顶（如下图）。 栈的实现（一） 栈的实现（二） const m=栈表目数的上限； type stack=record elem: array[1..m] of elemtp; top:0..m; {栈顶指针} end; Var s：stack；{栈} 栈的基本操作 栈的基本操作包括四种 初始化（init）、 进栈（push）、 出栈（pop）、 读取栈顶元素（top）。 1） 过程init(s,t) —初始化 procedure init; begin t:=0; end; 2)、过程push(x)—往栈s中压入一个值为x的数据： procedure push (var s：stack； x：stype； var t：integer)； begin if t=m then writeln(‘overflow’) {上溢} else begin t←t+1；s[t]←x；end；{else} {x入栈} end；{Push} 3）函数pop(s，t)—从栈中弹出一个表目 function pop (var s：stack； var t：integer)：stype； begin if t=0 then writeln (‘underflow’) {下溢} else begin pop←s[t]； t←t-1； end；{else} {栈顶元素出栈} end；{pop} 4）函数top(s，t)—读栈顶元素 function top (s：stack； t：integer)：stype； begin if t=0 then writeln (‘stack empty’) else top←s[t]； {返回栈顶元素} end；{top} 栈的应用 1、（1998） 栈S初始状态为空，现有5个元素组成的序列{1，2，3，4，5}，对该序列在栈S上一次进行如下操作（从序列中的1开始，出栈后不再进栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是______ (A) {5,4,3,2,1} (B) {2,1} (C) {2,3} (D) {3,4} 栈的应用3——表达式求值 输入一个表达式，该表达式含有“+”、“-”、“*”、“/”、“（”、“）”和操作数 输入以‘@’结束。输出该表达式的值。 分析： 由于一个表达式含操作数、运算符和括号，因此只能采用字符串类型输入，而字符是不能进行数值计算的。在这种情况下，计算机又如何计算表达式的值呢。一般方法是： 中缀表达式→等价的后缀表达式→计算后缀表达式的值 ? 中缀表达式和后缀表达式的特征 中缀表达式：中缀表达式与通常的表达式一样，运算符位于两个操作之间，