(精品)线性结构习题课.ppt

线性表，栈，队列习题课主讲老师：陈玉泉助教：刘磊主要内容n顺序表n单链表（单向循环链表）n双链表（双向循环链表）n栈（顺序存储，链式存储）n队列（顺序存储，链式存储）n应用概念题 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同时PjPkPi。概念题(五)必要性：用反证法证明。假如存在这样的下标i,j,k，满足ijk同时PjPkPi，则有：（1）由于ijk，三元素出栈的相对次序是Pi，Pj，Pk。（2）因为PjPkPi，所以入栈的相对次序为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)能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；概念题(十一)解答：允许在一端进行插入和删除，但在另一端只允许插入的双端队列叫做输出受限的双端队列，允许在一端进行插入和删除，但在另一端只允许删除的双端队列叫做输入受限的双端队列。输出受限双端队列不能得到的输出序列有：41324231输入受限双端队列不能得到的输出序列有：42134231 程序设计题6.6.将具有头结点的单链表的所有指针全部将具有头结点的单链表的所有指针全部进行倒向。要求使用的额外空间只能为进行倒向。要求使用的额外空间只能为 O(1),O(1),时间代价只能为时间代价只能为O(n)O(n)，其中其中 n n 为为结点个数。结点个数。解析：首先考虑头结点，然后对链表进行解析：首先考虑头结点，然后对链表进行一遍遍历即可。一遍遍历即可。程序设计题(一)templatevoidList: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);elseif(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时，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈(DoubleStack)结构的类定义，并实现判栈空、判栈满、插入、删除算法。双栈的类定义如下：#includetemplateclassDblStack/双栈的类定义private:inttop2,bot2;/双栈的栈顶指针和栈底指针Type*elements;/栈数组intm;/栈最大可容纳元素个数public:DblStack(intsz=10);/初始化双栈,总体积m的默认值为10DblStack()deleteelements;/析构函数voidDblPush(constType&x,inti);/把x插入到栈i的栈顶intDblPop(inti);/退掉位于栈i栈顶的元素Type*DblGetTop(inti);/返回栈i栈顶元素的值intIsEmpty(inti)constreturntopi=boti;/判栈i空否,空则返回1,否则返回0intIsFull()constreturntop0+1=top1;/判栈满否,满则返回1,否则返回0voidMakeEmpty(inti);/清空栈i的内容 templateDblStack:DblStack(intsz):m(sz),top0(-1),bot0(-1),top1(sz),bot1(sz)/建立一个最大尺寸为sz的空栈,若分配不成功则错误处理。elements=newTypem;/创建栈的数组空间assert(elements!=NULL);/断言:动态存储分配成功与否templatevoidDblStack:DblPush(constType&x,inti)/如果IsFull()，则报错；否则把x插入到栈i的栈顶assert(!IsFull();/断言:栈满则出错处理，停止执行if(i=0)elements+top0=x;/栈0情形：栈顶指针先加1,然后按此地址进栈elseelements-top1=x;/栈1情形：栈顶指针先减1,然后按此地址进栈templateintDblStack:DblPop(inti)/如果IsEmpty(i)，则不执行退栈，返回0；否则退掉位于栈i栈顶的元素，返回1if(IsEmpty(i)return0;/判栈空否,若栈空则函数返回0if(i=0)top0-;/栈0情形：栈顶指针减1elsetop1+;/栈1情形：栈顶指针加1return1;templateType*DblStack:DblGetTop(inti)/若栈不空则函数返回该栈栈顶元素的地址。if(IsEmpty(inti)returnNULL;/判栈i空否,若栈空则函数返回空指针return&elementstopi;/返回栈顶元素的值templatevoidMakeEmpty(inti)if(i=0)top0=bot0=-1;elsetop1=bot1=m;程序设计题(九)9.9.所谓回文，是指从前向后顺读和从后向前倒读都一样的不含空白字符的串。例如did，madamimadam，pop即是回文。试编写一个算法，以判断一个串是否是回文。方法一：将字符串中全部字符进栈，然后将栈中的字符逐个与原字符串中的字符进行比较。intpalindrome(charA,intn)stackst(n+1);intyes=1,i=0;while(Ai!=“0”)st.Push(Ai);i+;/扫描字符串，所有字符进栈i=0;while(Ai!=“0”)/比较字符串if(Ai=st.GetTop()st.Pop();i+;elseyes=0;break;returnyes;方法二：采用递归算法，判断从s到e中的字符串是否回文，通过函数返回是或不是。intpalindrome(charA,ints,inte)if(As!=Ae)return0;elseif(se)return1;elsepalindrome(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)的递归函数，并利用栈把他改写为非递归函数。程序设计题(十二)递归算法：int fib(int n)if(n0)return-1;if(n=0|n=1)return n;return fib(n-2)+fib(n-1);程序设计题(十三)非递归思想：定义一个整数num来存放结果。开始时，将n压入栈中，之后不断执行循环语句，直到栈为空：将栈顶元素（记为temp）弹出栈，如果temp是0或1，则num=num+temp;否则，将temp-1,temp-2压入栈，最终，num就是所求的值。int nfib(int n)int num=0,temp;PSeqStack pastack;if(n0)return-1;if(n=0|n=1)return n;push(pastack,n);while(!isEmptyStack(pastack)temp=top(pastack);pop(pastack);if(temp=0|temp=1)num+=temp;elsepush(pastack,temp-1);push(pastack,temp-2);return num;实习题完成情况问题：交的人数不够有的没有报告，源代码和可执行文件有的没有程序的使用说明希望：按时交作业报告，源代码，可执行文件，使用说明（或者最好给出几个测试数据）一个都不能少！