(精品)线性结构习题课

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,线性表，栈，队列习题课,主讲老师：陈玉泉,助教：刘磊,主要内容,顺序表,单链表（单向循环链表）,双链表（双向循环链表）,栈（顺序存储，链式存储）,队列（顺序存储，链式存储）,应用,概念题,1.,简单比较线性表的顺序和链接两种存储方式各有什么主要优缺点？,顺序存储：,优点：（,1,）在结点等长时可随机存取；（,2,）存储密度高，节省存储空间；（,3,）用结点的物理次序反映结点之间的逻辑关系。缺点：（,1,）插入和删除结点时要移动大量结点；（,2,）必须静态分配连续的空间。,概念题(一,),链接存储：,优点：（,1,）插入和删除比较灵活，不需要大量移动结点；（,2,）动态分配空间比较灵活，不需要预先申请最大的连续空间。缺点：（,1,）增加指针的空间开销；（,2,）检索必须沿链进行，不能随机存取。,概念题(二,),2.编号为1，2，3，4的四辆列车，顺序开进一个栈式结构的站台，为开出车站的顺序有多少种可能？请把他们具体写出来。,方法：可以先一位一位的假设，然后逐步给出后面的可能的情况。,概念题(三,),解：共有14种可能，分别如下：,4321，3214，3421，3241，2134，,2143，2341，2314，2431，1234，,1243，1342，1324，1432,概念题(四,),3.证明：有可能从初始输入序列1,2,n，,利用一个栈得到输出序列,P1,P2,Pn,，（P1,P2,Pn,是1,2,n,的一种排列）的充分必要条件是，不存在这样的下标,i,j,k，,满足,ijk,同时,Pj,Pk,Pi。,概念题(五,),必要性：用反证法证明。,假如存在这样的下标,i,j,k，,满足,ijk,同时,Pj,Pk,Pi，,则有：,（1）由于,ijk，,三元素出栈的相对次序是,Pi，,Pj，Pk,。,（2）因为,Pj,Pk,Pi，,所以入栈的相对次序为,Pj，Pk，Pi,。,概念题(六,),根据（2），当,Pi,入栈时，,Pj,和,Pk,都在栈中，并且,Pj,必在,Pk,之下。所以出栈的相对次序应该是,Pi，Pk，Pj,，,与（1）矛盾。,充分性：,设序列,P1,P2,Pn,符合条件，则我们可以用下述方法逐个的使,Pi,加入该序列。,概念题(七,),情况1：若,Pj,在输入序列的剩余部分（假设1，2，,i-1,已经输入）,i,i+1,n,中，则把,Pj,之前的元素及,Pj,进栈，然后把,Pj,从栈中取出送入序列。,情况2：若,Pj,已经在栈中，则他必然在栈顶（这是因为栈中元素在任何时刻显然都是从顶向下递减的，而刚离栈的,Pj-1,大于栈中的所有元素。假如,Pj,不在栈顶，设栈顶元素是,Pk,，,我们有,j-1j,Pk,Pj,矛盾）把栈顶元素取出送入序列。,重复上述步骤，可得到所要求的序列。,概念题(八,),4.把下面的中缀表达式转化为相应的后缀和前缀表达式：,(,A+B)*C-D*F+C,前缀：,(,A+B)*C-D*F+C,=(,(,A+B)*C)-(D*F)+C),=(+(-(*(+AB)C)(*DF)C),=+-*+ABC*DFC,概念题(九,),后缀：,(,A+B)*C-D*F+C,=(,(,A+B)*C)-(D*F)+C),=(AB+)C*)(DF*)-)C+),=AB+C*DF*-C+,概念题(十,),5.,设有一个双端队列，元素进入该队列的顺序是,1,2,3,4,。试分别求出满足下列条件的输出序列。,(1),能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；,(2),能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；,概念题(十一,),解答：,允许在一端进行插入和删除，但在另一端只允许插入的双端队列叫做输出受限的双端队列，允许在一端进行插入和删除，但在另一端只允许删除的双端队列叫做输入受限的双端队列。,输出受限双端队列不能得到的输出序列有：,4 1 3 2 4 2 3 1,输入受限双端队列不能得到的输出序列有：,4 2 1 3 4 2 3 1,程序设计题,6.将具有头结点的单链表的所有指针全部进行倒向。要求使用的额外空间只能为,O(1),时间代价只能为,O(n)，,其中,n,为结点个数。,解析：首先考虑头结点，然后对链表进行一遍遍历即可。,程序设计题(一,),template,void,List:,Inverse,(),if,(head-,Next,=,NULL,|,Head,-,Next,-,Next,=,NULL,),return,;,ListNode,*,pre,=,Head,-,Next,*,cur,=,pre,-,Next,*,next,;,pre,-,Next,=,NULL,;,程序设计题(二,),while,(,cur,),next,=,cur,-,Next,;,cur,-,Next,=,pre,;,pre,=,cur,;,cur,=,next,;,head-,Next,=,pre,;,程序设计题(三,),7.给出当进栈的车厢的序列为,1,、,2,、,3,、,4,、,、,N,时，所有出栈的序列的程序.,程序设计题(四,),算法思想：将出栈、入栈的操作次序求出来。,pun,是,push,次数，,pon,是,pop,次数。当,pun=pop=n,的时候，操作序列生成完毕。,程序设计题(五,),void,gen(int,pun,int,pon,int,n,char order),if(pun=n&,pon,=n),perform(n,order);,else,if(pun n),gen(pun,+1,pon,n,order+S);,if(,pon,pun),gen(pun,pon,+1,n,order+X);,程序设计题(六,),void,perform(int,n,char order),pos=0;,while(pos 2*n),switch(,orderpos,+),case S:PUSH;break;,case X:POP;break;,程序设计题(七,),void main(),gen(0,0,4,);,程序设计题(八,),8.,将编号为,0,和,1,的两个栈存放于一个数组空间,Vm,中，栈底分别处于数组的两端。当第,0,号栈的栈顶指针,top0,等于-,1,时该栈为空，当第,1,号栈的栈顶指针,top1,等于,m,时该栈为空。两个栈均从两端向中间增长。当向第,0,号栈插入一个新元素时，使,top0,增,1,得到新的栈顶位置，当向第,1,号栈插入一个新元素时，使,top1,减,1,得到新的栈顶位置。当,top0+1,=,top1,时或,top0,=,top1,-,1,时，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈,(,Double Stack),结构的类定义，并实现判栈空、判栈满、插入、删除算法。,双栈的类定义如下：,#,include,template class,DblStack,/,双栈的类定义,private:,int,top2,bot2,;,/,双栈的栈顶指针和栈底指针,Type,*elements,;,/,栈数组,int,m,;,/,栈最大可容纳元素个数,public:,DblStack,(,int,sz,=10),;,/,初始化双栈,总体积,m,的默认值为,10,DblStack,(),delete,elements,;,/,析构函数,void,DblPush,(,const Type&,x,int,i),;,/,把,x,插入到栈,i,的栈顶,int,DblPop,(,int,i),;,/,退掉位于栈,i,栈顶的元素,Type,*,DblGetTop,(,int,i),;,/,返回栈,i,栈顶元素的值,int,IsEmpty,(,int,i),const return,topi,=,boti,;,/,判栈,i,空否,空则返回,1,否则返回,0,int,IsFull,(),const return,top0+1=top1,;,/,判栈满否,满则返回,1,否则返回,0,void,MakeEmpty,(,int,i),;,/,清空栈,i,的内容,template,DblStack,:,DblStack,(,int,sz,),:,m(sz,),top0(,-,1),bot0(,-,1),top1(sz),bot1(sz),/,建立一个最大尺寸为,sz,的空栈,若分配不成功则错误处理。,elements=,new,Type,m,;,/,创建栈的数组空间,assert,(elements!=NULL),;,/,断言,:,动态存储分配成功与否,template void,DblStack,:,DblPush,(,const Type&,x,int,i),/,如果,IsFull,(),，,则报错；否则把,x,插入到栈,i,的栈顶,assert,(!,IsFull,(),;,/,断言,:,栈满则出错处理，停止执行,if,(i=0)elements+top0 =x,;,/,栈,0,情形：栈顶指针先加,1,然后按此地址进栈,else,elements,-,top1 =x,;,/,栈,1,情形：栈顶指针先减,1,然后按此地址进栈,template,int,DblStack,:,DblPop,(,int,i),/,如果,IsEmpty,(i),，,则不执行退栈，返回,0,；否则退掉位于栈,i,栈顶的元素，返回,1,if,(,IsEmpty,(i),return,0,;,/,判栈空否,若栈空则函数返回,0,if(i=0)top0,-,;,/,栈,0,情形：栈顶指针减,1,else,top1+,;,/,栈,1,情形：栈顶指针加,1,return,1,;,template,Type,*,DblStack,:,DblGetTop,(,int,i),/,若栈不空则函数返回该栈栈顶元素的地址。,if,(,IsEmpty,(,int,i),return,NULL,;,/,判栈,i,空否,若栈空则函数返回空指针,return&,elements,topi,;,/,返回栈顶元素的值,template void,MakeEmpty,(,int,i),if,(i=0)top0=bot0=,-,1,;,else,top1=bot1=m,;,程序设计题(九,),9.,所谓回文，是指从前向后顺读和从后向前倒读都一样的不含空白字符的串。例如,did,，,madamimadam,，,pop,即是回文。试编写一个算法，以判断一个串是否是回文。,方法一：,将字符串中全部字符进栈，然后将栈中的字符逐个与原字符串中的字符进行比较。,int,palindrome(,char,A,int,n),stack,st,(n+1);,int,yes=1,i=0,;,while,(,Ai,!=“0”),st.Push,(,Ai,),;,i+,;,/,扫描字符串，所有字符进栈,i=0,;,while,(,Ai,!=“0”)/,比较字符串,if,(,Ai,=,st.GetTop,(),st.Pop,(),;,i+,;,else,yes=0,;break;,return,yes,;,方法二：,采用递归算法，判断从,s,到,e,中的字符串是否回文，通过函数返回是或不是。,int,palindrome(,char,A,int,s,int,e),if,(,As,!=,Ae,),return,0,;,else if,(s e),return,1,;,else,palindrome(A,s+1,e,-,1),;,程序设计题(十,),程序设计题(十一,),10.,Fibonacci,序列0，1，1，2，3，5，8，13，21，其中每个元素是前两个元素的和。可递归定义为：,当,n=0,1,时,fib(n,)=n,当,n=2,时,fib(n,)=fib(n-2)+fib(n-1),设计一个计算,fib(n,),的递归函数，并利用栈