《《线性结构习题课》ppt课件》由会员分享，可在线阅读，更多相关《《线性结构习题课》ppt课件（34页珍藏版）》请在金锄头文库上搜索。
1、线性表，栈，队列习题课,主讲老师：陈玉泉 助教：刘磊,主要内容,顺序表 单链表（单向循环链表） 双链表（双向循环链表） 栈（顺序存储，链式存储） 队列（顺序存储，链式存储） 应用,概念题,1.简单比较线性表的顺序和链接两种存储方式各有什么主要优缺点？ 顺序存储： 优点：（1）在结点等长时可随机存取；（2）存储密度高，节省存储空间；（3）用结点的物理次序反映结点之间的逻辑关系。缺点：（1）插入和删除结点时要移动大量结点；（2）必须静态分配连续的空间。,概念题(一),链接存储： 优点：（1）插入和删除比较灵活，不需要大量移动结点；（2）动态分配空间比较灵活，不需要预先申请最大的连续空间。缺点：（1
2、）增加指针的空间开销；（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的一种排列）的充分必要条件是，
3、不存在这样的下标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
4、+1,n中，则把Pj之前的元素及Pj进栈，然后把Pj从栈中取出送入序列。 情况2：若Pj已经在栈中，则他必然在栈顶（这是因为栈中元素在任何时刻显然都是从顶向下递减的，而刚离栈的Pj-1大于栈中的所有元素。假如Pj不在栈顶，设栈顶元素是Pk，我们有 j-1 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,概念题(九),后缀： (
5、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) 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；,概念题(十一),解答：允许在一端进行插入和删除，但在另一端只允许插入的双端队列叫做输出受限的双端队列，允许在一端进行插入和删除，但在另一端只允许删除的双端队列叫做输入受限的
6、双端队列。 输出受限双端队列不能得到的输出序列有： 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
7、-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 =
8、 n ,程序设计题(六),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
9、增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
10、 );/初始化双栈, 总体积m的默认值为10 DblStack ( ) delete elements; /析构函数 void DblPush ( const Type /清空栈i的内容 ,template DblStack : DblStack ( int sz ) : m(sz), top0 (-1), bot0(-1), top1(sz), bot1(sz) /建立一个最大尺寸为sz的空栈, 若分配不成功则错误处理。 elements = new Typem; /创建栈的数组空间 assert ( elements != NULL ); /断言: 动态存储分配成功与否 template
11、void DblStack : DblPush ( const Type /栈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 : DblGetTo
12、p ( int i ) /若栈不空则函数返回该栈栈顶元素的地址。 if ( IsEmpty ( int i ) ) return NULL; /判栈i空否, 若栈空则函数返回空指针 return ,程序设计题(九),9.所谓回文，是指从前向后顺读和从后向前倒读都一样的不含空白字符的串。例如did，madamimadam，pop即是回文。试编写一个算法，以判断一个串是否是回文。 方法一：将字符串中全部字符进栈，然后将栈中的字符逐个与原字符串中的字符进行比较。,int palindrome ( char A , int n ) stack st (n+1); int yes = 1, i = 0;
13、 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; els
14、e 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)的递归函数，并利用栈把他改写为非递归函数。,程序设计题(十二),递归算法： int fib(int n) if (n0) return -1; if (n=0|n=1) return n; return fib(n-2)+fib(n-1); ,程序设计题(十三)
15、,非递归思想：定义一个整数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; else push(pastack,temp-1); push(pastack,temp-2); return num; ,实习题完成情况,问题： 交的人数不够 有的没有报告，源代码和可执行文件 有的没有程序的使用说明 希望： 按时交作业 报告，源代码，可执行文件，使用说明（或者最好给出几个测试数据）一个都不能少！,
