第十二讲：线性结构(线形表、栈和队列).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,12,讲,:,数据结构之,线性结构,数据结构之：线性结构,由,n,个数据元素组成的有限序列,除头元素外，每个元素都有一个前趋,除尾元素外，每个元素都有一个后继,例如,:,26,个英文字母表,(a,，,b,，,，,Z),是一个线性表,线性结构,:,线性表、栈、队列,操作方法和要求的不同划分,线性表的两种存储方式,顺序存储结构：,数组,连续存储,易于定位，不易于插入和删除,链式存储结构：,链表,非连续存储,易于插入和删除，不易于定位,一、线性表,线性表是最常用且最简单的一种数据结构，它是由,n,个数据元素组成的有序集合。,数组与链表,链表,数组,数组的插入与删除,1,2,3,4,5,6,7,8,9,10,11,12,6.5,数组的插入与删除均需要移动后面的元素,插入：,6.5,删除：,4,1,2,3,4,5,6,7,8,9,10,11,12,1,2,3,4,5,6,7,8,9,10,11,12,1,2,3,4,5,6,7,8,9,10,11,12,链表的插入与删除,无需移动任何元素,插入：,删除：,顺序存储结构的元素访问,顺序存储结构是指用一组地址连续的存贮单元依次存储线性表的元素，通常用数组实现。,它是按首址（表中第,1,个元素的地址）,十,位移来访问每一个元素。,loc(ai,)a,表中元素,i,的内存地址（,1in,）；,loc(bi,，,j)b,表中（,i,，,j,）,元素的内存地址（,1in,，,1jm,）；,一维数组按照下标递增的顺序访问表中元素,a1,a2,an,loc(ai)=loc(a1)+(i-1)*k /,k,每个数据元素的长度,(,字节或机器字,),；,首址 位移,二维数组有按照,先行后列,和,先列后行,的顺序访问表中元素：,b1.n,，,1.m,先行后列,:,loc(bi,，,j)=,loc(b1,，,1),+,(m*(i-1)+(j-1)*k,k,每个数据元素的长度；,首址 位移,先列后行,:,loc(bi,，,j)=,loc(b1,，,1),+,(n*(j-1)+(i-1)*k,k,每个数据元素的长度；,首址 位移,一个向量第一个元素的存储地址是,100,，每个元素的长度是,2,，则第,5,个元素的地址是（）。,(NOIP8),A,）,110 B,）,108 C,）,100 D,）,109,已知数组中,A,中，每个元素,A,（,I,，,J,）,在存贮时要占,3,个字节，设,I,从,1,变化到,8,，,J,从,1,变化到,10,，分配内存时是从地址,SA,开始连续按行存贮分配的。试问：,A,（,5,，,8,）,的起始地址为（）,(NOIP6)A.SA+141,B.SA+180,C.SA+222,D.SA+225,一个文本屏幕有,25,列及,80,行，屏幕的左上角以（,1,，,1,）表示，而右下角则以（,80,，,25,）表示，屏幕上每一个字符占用两字节（,byte,），,整个屏幕则以线性方式存储在电脑的存储器内，从屏幕左上角开始，位移为,0,，然后逐列逐列存储。求位於屏幕（,X,，,Y,）,的第一个字节的位移是（）,(NOIP6)A.,（,Y*80+X,）*,2-1,B.,（,Y-1,）*,80+X-1,）*,2C.,（,Y*80+X-1,）*,2,D.,（,Y-1,）*,80+X,）,*,2-1,(4),、设有一个,10,阶的对称矩阵,A,，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组,B,中，,A00,存入,B0,中，则,A85,在,B,中（）位置。,A,32 B,33 C,41 D,65,应用举例：,1,、插入排序。,2,、两个有序线性表的合并。,输入,:,1 4 8 10,2 3 7 9 11 13,输出：,1 2 3 4 7 8 9 10 11 13,3,、两个多项式的合并。,输入：,1+x+2X2-x3-30X5,2x+x2+x3,输出：,1+3x+3x2-30 x5,二、栈,栈的定义,栈是一种,“后进先出”,线性表。,对它的插入和删除都限制地表的同一端进行。这一端叫做栈的“顶”，另一端则叫做栈的“底”。,特点,:,后进先出,(LIFO),、或者先进后出（,FILO,）,栈底,3,2,5,进栈,进栈,进栈,出栈,出栈,出栈,不一定进栈结束后才出栈，进出栈可,交叉,进行,【,竞赛试题,】,1,、一个栈的输入顺序为,1,、,2,、,3,、,4,、,5,，下列序列中可能是栈的输出序列是,(),。,(A)54312 (B)24,15,(C)21543 (D)125,3,2,、若已知一个栈的入栈顺序是,1,，,2,，,3,，,，,n,，,其输出序列为,P1,，,P2,，,P3,，,，,Pn,，若,P1,是,n,，则,Pi,是,()(NOIP7),A)i,B)n-1,C)n-i+1,D),不确定,3,、设有一个顺序栈,S,，,元素,S1,S2,S3,S4,S5,S6,依次进栈，如果,6,个元素的出栈顺序为,S2,S3,S4,S6,S5,S1,，,则顺序栈的容量至少应为多少？,3 B)4 C)5 D)6,4,、向顺序栈中压入新元素时，应当（）。,A,先移动栈顶指针，再存入元素,B,先存入元素，再移动栈顶指针,C,先后次序无关紧要,D,同时进行,假设栈中表目数的上限为,m,，,所有表目都具有同一类型,stype,，,则可以用下列方式定义栈：,Const,m=,栈表目数的上限；,Var,s,：,array1m of,stype,；,栈,t,：,integer,；,栈顶指针，初始值为,栈的基本操作,栈的基本操作：初始化（,init,）、,进栈（,push,）、出栈（,pop,）和,读取栈顶元素（,top,）。,1,）,过程,init(s,t),procedure init;,begin,t:=0;,end;,2),、,过程,push(x),往栈,s,中压入一个值为,x,的数据：,procedure push,（,x,：,stype,),；,begin,t:=t+1,；,st,:=x,；,x,入栈,end,；,Push,3),、函数,pop,从栈中弹出一个元素,function pop,：,stype,；,begin,pop:=,st,；,栈顶元素出栈,t:=t-1,；,指针下移,end,；,pop,4),、函数,top,读栈顶元素,function top,：,stype,；,begin,if t=0 then,writeln,(stack empty,),else top:=,st,；,返回栈顶元素,end,；,top,栈的应用,1,、后缀表达式求值,【,问题描述：,】,后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。,如：,3*(52)+7,对应的后缀表达式为：,3,5,2,-*7,+,。,为表达式的结束符号。,.,为操作数的结束符号。,3,5,2,-*7,+=3,3,*,7,+=9,7,+=16,运算符号：,+,、,-,、*、,/,/,运算只取整数部分。采用,div,即可,【,输入：,】,后缀表达式（长度不超过,100,）。,【,输出：,】,表达式的值。,说明：运算的中间结果与最后的结果数据范围：,-1000000000,，,1000000000,。,【,样例输入：,】,3,5,2,-*7,+,【,样例输出：,】,16,中缀表达式转化为后缀表达式,方法一：不会栈操作,算法分析：,后缀表达式为,A:string,;,数组,S:,保存操作数和中间计算结果。,s,的类型为,longint,。,1),、从左向右处理,a,中的每一个字符：,2),、如果遇到一个操作数，就送入,数组,s,中；,如果遇到一个运算符，就从,数组,s,中取出后面的两个操作数进行计算，然后将计算结果重新放入到数组中。,3),、直到遇到,处理结束。,这时数组中,s,剩下唯一的元素即是计算结果。,方法二：利用栈结构,算法分析：,假设后缀的表达式为,A,，,操作数和计算结果存放在栈,S,中。,1),、从左向右处理,a,中的每一个字符：,2),、如果遇到一个操作数，就送入栈,s,中；,如果遇到一个运算符，就从栈,s,中取出栈顶的两个操作数进行计算，然后将计算结果重新压栈。,3),、直到遇到,处理结束。,这时栈,s,顶的元素即是计算结果。,2,、括号匹配,【,问题描述：,】,判断包含有括号,，,，,，,，,的字符串是否是合法匹配。,例如以下是合法的括号匹配：,(),(),(),(),()(),以下是不合法括号匹配的：,(,)(,(,(),，,(),【,输入：,】,一行，字符串（长度范围：,1,，,200,）。,【,输出：,】,如果字符串中括号匹配是合法的输出“,yes”,，不合法的输出“,no”,。,【,样例,1,输入：,】,abcabbmaa,【,样例,1,输出：,】,yes,【,样例,2,输入：,】,abcabbmaa,【,样例,2,输出：,】,no,分析：,遇到左括号进栈；,遇到右括号，出栈，看是否和右括号匹配，如果匹配继续看下一个括号，否则停止，输出,no,即可。,栈底,3,2,5,进栈,进栈,进栈,出栈,出栈,出栈,3,5,2,栈顶,加入一个数,4,取出栈顶元素,再取出栈顶元素,6,栈底,