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

数据结构-栈,对于程序设计来说：编程语言是工具；数据结构是基础；算法设计是方法。,程序=数据结构+算法,数据结构,数据结构（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 1.maxlen of elemtp;链式存储结构 用指针类型 和 动态变量：pointer=nodetype;nodetype=record data:elemtp;next:pointer;end;,顺序存储与链式存储操作的对比,限定仅在表尾进行插入和删除操作的线性表,又称为后进先出(last in first out)线性表(LIFO结构)栈顶表尾 栈底表头,栈,通常栈可以用顺序的方式存储(数组)，分配一块连续的存储区域存放栈中的表目，并用一个变量t指向当前栈顶（如下图）。,栈的实现（一）,Const m=栈表目数的上限；Type stack=array1.m of stype；栈类型Var s：stack；栈 top：integer；栈顶指针,栈s,m,1,top,栈的实现（二）,const m=栈表目数的上限；type stack=record elem:array1.m of elemtp;top:0.m;栈顶指针 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；pop4）函数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 pop0)or(tt0)then writeln(No)else writeln(Yes);end.,var s:string;a:array0.200 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:array0.200 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），用来分别存放表达式中的操作数和运算符。开始时操作数栈为空，运算符栈中放入一个特殊的标志运算符号#号，并在表达式的末尾加上一个#号，并规定#号的优先级最低，然后从左向右扫描表达式，凡遇操作数便一律进栈；若遇运算符，则判断其优先级是否大于运算符栈栈顶元素的优先级。若小，则栈顶运算符退栈，并从操作数栈中弹出两个操作数（操作数为后缀表达式）进行后缀变换处理，处理结果进操作数栈，重复刚才的比较，直到栈顶运算符的优先级小于等于当前运算符的优先级，此时，若当前运算符的优先级大于栈顶运算符的优先级，则当前运算符进栈，继续扫描；若当前运算符的优先级等于栈顶运算符的优先级，则弹出栈顶运算符，继续扫描。扫描完该表达式后运算符栈为空，操作数栈中只有一个元素，该元素就是所要求的后缀表达式。,X+A*（Y-B）-Z/F,以下程序中的数组f用来存放运算符之间的优先级关系，1()表示前面的运算符优先于后面的运算符，-1()表示后面的运算符优先于前面的运算符，0(=)表示前面的运算符的优先级与后面的运算符相同，2(ERROR)表示这两个运算符如果在扫描中相遇的话，意味着该表达式是错误的。需要补充的是：左括号的优先级是最高的，右括号的优先级是除#号以外最低的，而里层的左括号比外层的左括号更优先，但左括号和右括号的优先级则是相等的，这样定义的目的是为了消去括号。以上规律列表如下：,P2,P1,X+A*（Y-B）-Z/F,上述算法还可用于求一个表达式的值和判断一个表达式是否有错等等。program ex2;const max=100;op_set:set of char=+,-,*,/;运算符集合 letter:set of char=A.Z;运算数集合var expression,result:string;中缀表达式，后缀表达式，字符串procedure scan(expression:string);本过程完成中缀的扫描及到后缀的转换 var i,top1,top2:integer;操作数栈和操作符栈的栈顶指针 ovs:array 1.max of stringmax;操作数栈 ops:array 1.max of char;操作符栈 f:array#./,#./of shortint;数组f用来存放运算符之间的优先级关系,begin f+,+:=1;f+,-:=1;f+,*:=-1;f+,/:=-1;f+,(:=-1;f+,):=1;f+,#:=1;f-,+:=1;f-,-:=1;f-,*:=-1;f-,/:=-1;f-,(:=-1;f-,):=1;f-,#:=1;f*,+:=1;f*,-:=1;f*,*:=1;f*,/:=1;f*,(:=-1;f*,):=1;f*,#:=1;f/,+:=1;f/,-:=1;f/,*:=1;f/,/:=1;f/,(:=-1;f/,):=1;f/,#:=1;f(,+:=-1;f(,-:=-1;f(,*:=-1;f(,/:=-1;f(,(:=-1;f(,):=0;f(,#:=2;f),+:=2;f),-:=2;f),*:=2;f),/:=2;f),(:=2;f),):=2;f),#):=2;f#,+:=-1;f#,-:=-1;f#,*:=-1;f#,/:=-1;f#,():=-1;f#,:=2;f#,#:=0;expression:=expression+#;表达式的末尾放一个“#”ops1:=#;操作符栈先放入一个“#”top1:=0;初始化操作数栈 top2:=1;操作符栈中放入一个“#”,for i:=1 to length(expression)do在中缀表达式的长度范围内执行循环 begin if expressioni in letter 如果扫描到的中缀表达式的内容是操作数 then begin top1:=top1+1;ovstop1:=expressioni 操作数进栈 end else begin while fopstop2,expressioni=1 dobegin ovstop1-1:=ovstop1-1+ovstop1+opstop2;top1:=top1-1;top2:=top2-1 end;若遇运算符，则判断其优先级是否大于运算符栈栈顶元素的优先级。若小，则栈顶运算符退栈，并从操作数栈中弹出两个操作数（操作数为后缀表达式）进行后缀变换处理，处理结果进操作数栈重复刚才的比较，直到栈顶运算符的优先级大于等于当前运算符的优先级。if fopstop2,expressioni=0 then top2:=top2-1 else begin top2:=top2+1;opstop2:=expressioni end;若当前运算符的优先级大于栈顶运算符的优先级，则当前运算符进栈，继续扫描；若当前运算符的优先级等于栈顶运算符的优先级，则弹出栈顶运算符，继续扫描。end end;result:=ovs1 扫描完该表达式后运算符栈为空，操作数栈中只有一个元素，该元素就是所要求的后缀表达式。end;,beginmain write(Input a expression:);readln(expression);scan(expression);writeln(The result is:,result)end.测试输入：A*(X+Y)/(B-Z)输出：AXY+*BZ-/,将中缀表达式转换为等价的后缀表达式(方法2),在中缀表达式中，运算符出现次序与计算顺序不一致，实际计算顺序不仅要看它的出现次序，还要受运算符的优先级和括号的影响。如果把一个中缀表达式中所有的计算顺序都按计算规则用嵌套括号的形式表示出来，其转换过程就要清楚的多。例如中缀表达式3*(52)+7可以改写成（(3*(52)+7）。这时可以看出，只要将每对括号中的运算符移到相应括号的后面，再删去所有括号，便得到与之等价的后缀表达式352*7+。为了将中缀表达式转换为等价的后缀表达式，需要从左至右扫描中缀表达式，并使用一个栈s2来存放中缀表达式中的开括号（和暂时不能参与计算的运算符，显然s2栈的元素类型为char。为了方便表达式值的计算，在转换后的后缀表达式中，每一个操作数尾添加一个.。例如计算3*(52)+7,const m=1000;type stack=array1.mof char;var a,e:string;后缀表达式和中缀表达式 s:stack;栈，存放暂不参与计算的运算符 t,i:integer;栈顶指针、中缀表达式的字符指针 w:char;fi,fo:text;procedure push(x:char);begin t:=t+1;st:=x;end;function pop:char;begin pop:=st;t:=t-1;end;function top(s:stack;t:integer):char;begin top:=st;end;,begin assign(fi,zzh.in);reset(fi);assign(fo,zzh.out);rewrite(fo);read(fi,e);a:=;i:=1;t:=0;后缀表达式初始化为空 从中缀表达式的第一个字符开始分析，栈空 while ei do begin 由左而右扫描处理中缀表达式的每一个字符 case eiof 0.9:begin 操作数进入后缀表达式 while ei.do begin a:=a+ei;i:=i+1;end;a:=a+.;添加操作数的结尾标志 end;(:push();（入栈):begin s栈中栈顶至(间的所有运算符相继出栈，进入后缀表达式 w:=pop;while w(do begin a:=a+w;w:=pop;end;end;,+,-:begin s栈中，栈顶至(前的所有运算符相继出栈，进入后缀表达式，ei进入s栈 if t0 then begin w:=top(s,t);while w(do begin a:=a+w;w:=pop;if t=0 then break else w:=top(s,t);end;end;push(ei);end;*,/:begin s栈中栈顶至第1个+或-前的所有运算符相继出栈，进入后缀表达式，ei进入s栈 if t0 then begin w:=top(s,t);while(w=*)or(w=/)do begin a:=a+w;w:=pop;if t=0 then break else w:=top(s,t);end;end;push(ei);end;end;i:=i+1;准备扫描处理中缀表达式的下一个字符 end;,while t0 do a:=a+pop;s栈中的运算符相继出栈，进入后缀表达式 a:=a+;writeln(fo,a);close(fi);close(fo);end.,栈的应用4-计算后缀表达式,所谓后缀表达式是指这样的一种表达式：式中不再引入括号，运算符放在两个运算对象之后。所有计算按运算符出现的顺序，严格地由左而右进行（不再考虑运算符的优先规则）。例如 3*（5-2）+7 对应的后缀表达式为 352-*7+其中为后缀表达式的结束标记，为操作数的结束符。352-*7+=33*7+=97+=16 输入：后缀表达式A（假定A合乎文法，不需判错）；输出：表达式的值。,后缀表达式求值【问题描述：】所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。1)运算符号：+、-、*、/。/运算只取整数部分。采用 div 即可 2)一个完整的运算数以”.”作为结束符号。3)运算的中间结果与最后的结果数据范围：-1000000000，1000000000。如：3*(52)+72 对应的后缀表达式为：352-*72+运算过程：352-*72+=33*72+=972+=81【输入：】一行：后缀表达式（长度不超过100）。【输出：】表达式的值。【样例输入：】352-*72+【样例输出：】81,方法：利用栈结构,算法分析：假设后缀的表达式为A，操作数和计算结果存放在栈S中，s的类型为integer。从左向右处理A中的每一个字符：如果遇到一个操作数，就送入栈s中；如果遇到一个运算符，就从栈s中取出栈顶的两个操作数进行计算，然后将计算结果重新压栈。直到最后一个运算符处理结束，这时栈s顶的元素即是计算结果。例如计算后缀表达式352-*7+的值,352-*7+,const m=100;type stack=array1.m of integer;定义栈类型var s:stack;栈 a:string;后缀表达式，字符串 t,i,j,k,len:integer;t栈顶指针；i后缀表达式的字符指针；k、j操作数值procedure push(x:integer);进栈 begin t:=t+1;st:=x;end;function pop:integer;出栈 begin pop:=st;t:=t-1;end;,begin readln(a);读入后缀表达式 len:=length(a);后缀表达式的长度 i:=1;后缀表达式字符指针初始化 t:=0;栈初始化 while i=len do 处理后缀表达式，循环直至结束 begin case ai of,0.9:begin k:=0;while ai.do begin 从s中取出一个完整的操作数k k:=10*k+ord(ai)-48;ord(0)=48 i:=i+1;end;push(k);把操作数k压栈 end;+:push(pop+pop);从栈s中取出栈顶的两个数进行加法运算，然后将结果在压栈,-:begin 从栈s中取出栈顶的两个数进行减法运算，然后将结果在压栈 j:=pop;push(pop-j);end;*:push(pop*pop);从栈s中取出栈顶的两个数进行乘法运算，然后将结果在压栈/:begin 从栈s中取出栈顶的两个数进行除法运算，然后将结果在压栈 j:=pop;push(pop div j);end;end;case,i:=i+1;end;while writeln(pop);取出栈顶元素，即时表达式的最后结果end.,