数据结构-栈及其应用

数据结构-栈,对于程序设计来说： 编程语言是工具； 数据结构是基础； 算法设计是方法。,程序=数据结构+算法,数据结构,数据结构（data structure）是相互之间存在一种或多种特定关系的数据元素的集合。,数据结构的内涵 “操作”的对象：数据。 数据与数据间的关系。 针对数据的基本操作。,数据结构的形式定义 data _ structure=(D,S) D:数据元素的有限集； S:上关系的有限集；,数据结构相关概念,数据(data) 计算机科学中指所有能输入到计算机中并被程序处理的符号总称。例如数值、字符、图像、声音都属于数据的范畴。 数据元素(data element) 是数据的基本单位 ，在程序中作为一个整体进行考虑。 有时一个数据元素有若干数据项。 数据对象(data object)是性质相同的数据元素的集合，是数据的一个子集。,逻辑结构,前述“关系”即结构(sructure)，指数据之间的逻辑关系，又称逻辑结构。,物理结构,1 顺序结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 逻辑上关联的数据元素，物理存储结构中相邻。 2 链式结构 ：借助元素存储地址的指针(pointer）表示数据元素之间的逻辑关系 。 逻辑上关联的数据元素，物理存储结构中不一定相邻。 用高级语言中的数据类型(数组、动态变量)来描述 逻辑结构、物理结构密切相关 算法的设计取决于所选定的数据（逻辑）结构，而算法的实现依赖于所采用的存储结构。,由n个数据元素的有限序列 除头元素外，每个元素都有一个前趋 除尾元素外，每个元素都有一个后继,线性结构,线性表,线性表是最常用且最简单的一种数据结构，它是由有限个数据元素组成的有序集合。 每个数据元素有一个数据项或者含多个数据项。,线性表的两种存储方式,1、顺序存储结构 顺序存储结构是指用一组地址连续的存贮单元依次存储线性表的元素，通常用数组实现。数组的物理实现是一块连续的存储空间，它是按首址（表中第1个元素的地址）十位移来访问每一个元素。,2、链式存储结构 在链式存储结构的线性表中，逻辑上相邻的两元素，其物理位置不要求相邻。采用动态指针。数组元素和动态变量的类型一般采用记录类型，数据域存储结点的值，指针域存储后件的数组下标或地址。最后一个结点的指针域的值为0或nil。,数组的插入与删除,6,6.5,数组的插入与删除均需要移动后面的元素,插入：,删除：,6,1,2,3,4,5,6,7,8,9,10,11,12,1,2,3,4,5,6,7,8,9,10,11,12,链表的插入与删除,无需移动任何元素,线性表的具体实现,顺序存储结构 用数组类型： list: array 1maxlen of elemtp; 链式存储结构 用指针类型 和 动态变量： pointer = nodetype ; nodetype = record data : elemtp ; next : pointer ; end;,顺序存储与链式存储操作的对比,限定仅在表尾进行插入和删除操作的线性表,又称为后进先出(last in first out )线性表 (LIFO结构) 栈顶表尾 栈底表头,栈,通常栈可以用顺序的方式存储(数组)，分配一块连续的存储区域存放栈中的表目，并用一个变量t指向当前栈顶（如下图）。,栈的实现（一）,Const m=栈表目数的上限； Type stack=array1m of stype； 栈类型 Var s：stack；栈 top： integer； 栈顶指针,栈s,m,1,top,栈的实现（二）,const m=栈表目数的上限； type stack=record elem: array1m of elemtp; top:0m; 栈顶指针 end; Var s：stack；栈,TOP=0 表示栈空 Top=m 表示栈满,栈的基本操作,栈的基本操作包括四种 初始化（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 tt+1；stx；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 popst； tt-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 topst； 返回栈顶元素 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输入：】 【样例3输出：】 no 【样例4输入：】 【样例4输出：】 no,2、括号匹配 【问题描述：】 判断包含有括号，的字符串是否是合法匹配。 例如以下是合法的括号匹配： (), , (), ( ), () , ()() 以下是不合法括号匹配的： (, , , )(, ( , ()，( ) 【输入：】 一行，字符串（长度范围：1，200）。 【输出：】 如果字符串中括号匹配是合法的输出“yes”，不合法的输出“no”。,【样例1输入：】 【样例1输出：】 yes 【样例2输入：】 【样例2输出：】 no,i:=1; t:=0;tt:+0; while i'(' then begin tt:=1;break;end; '':if pop'' then tt:=1;break;end; '':if pop'' then tt:=1;break;end; '':if pop'0) or (tt0) then writeln('No') else writeln('Yes'); end.,var s:string; a:array0200 of char; n,i,t,tt:integer; procedure push(k:char); begin inc(t); at:=k; end; function pop:char; begin pop:=at; dec(t); end; begin readln(s); a0:=' ' n:=length(s);,算法1：,var f:arraychar of char; a:array0200 of char; s:string; ch:char; p,i,n:longint; function pop:char; begin pop:=ap;dec(p); end; procedure push(x:char); begin inc(p); ap:=x; end; procedure print(k:integer); begin writeln(k); halt;end; begin f'':='' f'(':=')' f'':='' f'',算法2：,readln(s); p:=0; i:=1; n:=length(s); while i0 then push(si) /左括号进栈 else /右括号判断 begin if p=0 then print(0); /有多余的右括号 if fpopsi then print(0); /和前面的不匹配 end; inc(i); end; if p=0 then print(1) else print(0); end.,栈的应用3表达式求值,输入一个表达式，该表达式含有“+”、“-”、“*”、“/”、“（”、“）”和操作数 输入以结束。输出该表达式的值。 分析： 由于一个表达式含操作数、运算符和括号，因此只能采用字符串类型输入，而字符是不能进行数值计算的。在这种情况下，计算机又如何计算表达式的值呢。一般方法是： 中缀表达式等价的后缀表达式计算后缀表达式的值,中缀表达式和后缀表达式的特征,中缀表达式：中缀表达式与通常的表达式一样，运算符位于两个操作之间，计算规则为 先括号内、后括号外； 无括号或同层括号内先*、/、后+、-； 同级运算按由左至右顺序进行。 为了计算方便，输入的中缀表达式串常以为结束标志。 例如3*(52)+7 后缀表达式：后缀表达式中不再引入括号，运算符放在两个运算对象之后。所有计算按运算符出现的顺序，严格地由左而右进行（不再考虑运算符的优先规则）。为了计算方便，以.为操作数的结束标志，以为后缀表达式的结束标志。 例如3*（5-2）+7 对应的后缀表达式为 352-*7+。后缀表达式是简化运算顺序的一种表达式。,中缀表达式的运算规则比较多，包括优先级、左右次序和括号；尤其是括号可以改变优先顺序，这就只能在计算的每一步，用肉眼去扫描、观察和比较整个表达式中谁的优先级高，就先计算那部分。但用计算机去做就很麻烦，而且效率不高。 所以，计算机科学中是把中缀表达式先转换成后缀表达式，在利用计算机来计算后缀表达式的值。后缀表达式又称“逆波兰式”，在后缀表达式中，不存在括号，也不存在优先级的差别，计算过程完全按照运算符出现的先后顺序进行，整个计算过程仅需一遍扫描即可完成。,中缀表达式转化成后缀表达式的规则是： 只要将每个运算符移到它的两个运算对象的后面，再删去所有括号，便得到与之等价的后缀表达式,栈的应用-中缀转后缀,输入一个中缀表达式，编程输出其后缀表达式，要求输出的后缀表达式的运算次序与输入的中缀表达式的运算次序相一致。为简单起见，假设输入的中缀表达式由（加）、（减）、×（乘）、（除）四个运算符号以及左右圆括号和大写英文字母组成，其中算术运算符遵守先乘除后加减的运算规则。假设输入的中缀表达式长度不超过80个字符，且都是正确的，即没有语法错误，并且凡出现括号其内部一定有表达式，即内部至少有一个运算符号。以下是一个运行实例。 输入：X+A*（Y-B）-Z/F 输出：XAYB-*+ZF/-,设置两个栈：操作数栈（ovs）和运算符栈（ops），用来分别存放表达式中的操作数和运算符。开始时操作数栈为空，运算符栈中放入一个特殊的标志运算符号#号，并在表达式的末尾加上一个#号，并规定#号的优先级最低，然后从左向右扫描表达式，凡遇操作数便一律进栈；若遇运算符，则判断其优先级是否大于运算符栈栈顶元素的优先级。若小，则栈顶运算符退栈，并从操作数栈中弹出两个操作数（操作数为后缀表达式）进行后缀变换处理，处理结果进操作数栈，重复刚才的比较，直到栈顶运算符的优先级小于等于当前运算符的优先级，此时，若当前运算符的优先级大于栈顶运算符