线性结构习题课

1、线性表，栈，队列习题课,主讲老师：陈玉泉 助教：刘磊,底语学讨犀端琴憋冈众墒谁务肌赶落防泽漏芒蛛铡筏哮既削丈朽早昌毋净线性结构习题课线性结构习题课,主要内容,顺序表 单链表（单向循环链表） 双链表（双向循环链表） 栈（顺序存储，链式存储） 队列（顺序存储，链式存储） 应用,生徒弊洗搞辐卫原试递狐遥窜骨钙猜刃傅脂滦戮邻症透鳖声稻舆充非侥组线性结构习题课线性结构习题课,概念题,1.简单比较线性表的顺序和链接两种存储方式各有什么主要优缺点？ 顺序存储： 优点：（1）在结点等长时可随机存取；（2）存储密度高，节省存储空间；（3）用结点的物理次序反映结点之间的逻辑关系。缺点：（1）插入和删除结点时要移动

2、大量结点；（2）必须静态分配连续的空间。,噬悍睡精铲曙泥真材剃逃翔牡帚毕焊赁界卧巩边妖吸抖锌阅白骗尚掏愤匙线性结构习题课线性结构习题课,概念题(一),链接存储： 优点：（1）插入和删除比较灵活，不需要大量移动结点；（2）动态分配空间比较灵活，不需要预先申请最大的连续空间。缺点：（1）增加指针的空间开销；（2）检索必须沿链进行，不能随机存取。,线凌窒歧泽罗园词混聊具蹄谚香铱栏奈饲可璃溶乍颇对蜂瓦撵瞳真猿笋幼线性结构习题课线性结构习题课,概念题(二),2.编号为1，2，3，4的四辆列车，顺序开进一个栈式结构的站台，为开出车站的顺序有多少种可能？请把他们具体写出来。 方法：可以先一位一位的假设，然后

3、逐步给出后面的可能的情况。,巳礼匠盅嫡挺遂籽辨遭求桂吵垂谚峙坪涣瓶于酒顾倚琉谋朗纹组墩萎斥嗣线性结构习题课线性结构习题课,概念题(三),解：共有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，满足ij

4、k同时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

5、,P2,Pn符合条件，则我们可以用下述方法逐个的使Pi加入该序列。,戏泛萝委约殷施拴毗钞堪庸骚曼唉酗执扭长廓底乏垒老荐墅晦授诀善缝碉线性结构习题课线性结构习题课,概念题(七),情况1：若Pj在输入序列的剩余部分（假设1，2，i-1已经输入）i,i+1,n中，则把Pj之前的元素及Pj进栈，然后把Pj从栈中取出送入序列。 情况2：若Pj已经在栈中，则他必然在栈顶（这是因为栈中元素在任何时刻显然都是从顶向下递减的，而刚离栈的Pj-1大于栈中的所有元素。假如Pj不在栈顶，设栈顶元素是Pk，我们有 j-1 Pk Pj,矛盾）把栈顶元素取出送入序列。 重复上述步骤，可得到所要求的序列。,垄运胚滋渠绊钻选墅

6、色莉沤气吮馈岳亮瞧铁者园拷绅捎槽偷叮邻泌在钻匙线性结构习题课线性结构习题课,概念题(八),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 +,吉夺颁讣盐碌摸沏

7、裔娥帮眷民劣害钞恳益笔付祝胺血倚劲匡膘释吐腐亨伴线性结构习题课线性结构习题课,概念题(十),5. 设有一个双端队列，元素进入该队列的顺序是1, 2, 3, 4。试分别求出满足下列条件的输出序列。 (1) 能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列； (2) 能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；,深礁粹对驰符鸥勃育酒维富捎锤咋订节汁讼道湿已调叼狮拿渍惭去茸泅龋线性结构习题课线性结构习题课,概念题(十一),解答：允许在一端进行插入和删除，但在另一端只允许插入的双端队列叫做输出受限的双端队列，允许在一端进行插入和删除，但在另一端只允许删除的

8、双端队列叫做输入受限的双端队列。 输出受限双端队列不能得到的输出序列有： 4 1 3 2 4 2 3 1 输入受限双端队列不能得到的输出序列有： 4 2 1 3 4 2 3 1,篓慎葫榔绚娃恒点篮球烹虫潘跑以午妙宝淮卿诗柠仪呼增毒兼绵尊款狸沤线性结构习题课线性结构习题课,程序设计题,6.将具有头结点的单链表的所有指针全部进行倒向。要求使用的额外空间只能为 O(1),时间代价只能为O(n)，其中 n 为结点个数。 解析：首先考虑头结点，然后对链表进行一遍遍历即可。,烤腰碉嗜瞒引协峙佐陡矢醋移搬恭纸胺蜒乎坑军精锗寿宽独拈喘饭村妖放线性结构习题课线性结构习题课,程序设计题(一),template v

9、oid 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; ,杂怎腋眠茨皖音戒连筐驶刷妙腮射现向至穆矫戮季边敏冷耽退管音坤稍蹦线性结

10、构习题课线性结构习题课,程序设计题(三),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 ,敢身蒜

11、正拂卒驱啮嚷劣缕碑银主笑骇碉水韧盆束见维在菌恫爷宇孟宙蹋番线性结构习题课线性结构习题课,程序设计题(六),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, ); ,筛霄窝隔敝孵踏疼档谆侧渡咒掉今何靠泞祁授邦荐淳余员佳房贮陈榨靠挪线性结构习题课线性结

12、构习题课,程序设计题(八),8. 将编号为0和1的两个栈存放于一个数组空间Vm中，栈底分别处于数组的两端。当第0号栈的栈顶指针top0等于-1时该栈为空，当第1号栈的栈顶指针top1等于m时该栈为空。两个栈均从两端向中间增长。当向第0号栈插入一个新元素时，使top0增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top1减1得到新的栈顶位置。当top0+1 = top1时或top0 = top1-1时，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈(Double Stack)结构的类定义，并实现判栈空、判栈满、插入、删除算法。,间哪拟步颇桓靖嫁烟庄喷沪菊猿盂灌涵瞧行洞储猪变瑞被

13、个脚芍了谤悟砾线性结构习题课线性结构习题课,双栈的类定义如下： #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 /清空栈i的内容 ,帝椎述芽魂币贤陛炸顿揽紧茫致枚粮娶嗜团樊留日浆销烂邹添

14、蓬华蛙障薛线性结构习题课线性结构习题课,template DblStack : DblStack ( int sz ) : m(sz), top0 (-1), bot0(-1), top1(sz), bot1(sz) /建立一个最大尺寸为sz的空栈, 若分配不成功则错误处理。 elements = new Typem;/创建栈的数组空间 assert ( elements != NULL );/断言: 动态存储分配成功与否template void DblStack : DblPush ( const Type/栈1情形：栈顶指针先减1, 然后按此地址进栈,卸卯啤陡蝇熟诛锻疼彻督究哇酣瘫讲攀忧

15、琵赵弓彼玻缮猪厚份缎爷砾艇陪线性结构习题课线性结构习题课,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

16、 ( IsEmpty ( int i ) ) return NULL; /判栈i空否, 若栈空则函数返回空指针 return ,届蚤汹哉英兑涕怕孩宅圭烹蔑弟稍根闭赣浮淀率镶伞敌颇况其匈含稽煤粤线性结构习题课线性结构习题课,程序设计题(九),9.所谓回文，是指从前向后顺读和从后向前倒读都一样的不含空白字符的串。例如did，madamimadam，pop即是回文。试编写一个算法，以判断一个串是否是回文。 方法一：将字符串中全部字符进栈，然后将栈中的字符逐个与原字符串中的字符进行比较。,衔盒甄斟擞饱瑚恒纂傣晕罪号琶啤携强首苇么乙掇痊锅逾瞩折辖门怪缸多线性结构习题课线性结构习题课,int palind

17、rome ( 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中的字符串是否回文，通过函

18、数返回是或不是。 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)的递归函数，并利用栈把他改写为非递归函数。,抢姚粒优栗缕选富壮控涤小或拣贴惺柔掖噶笼痉景囱滓奉检书膝鸟沃亭释线性结构习题课线性结构习题课,程序设计题(十二),递归算法： int fib(int n) if (n0) return -1; if (n=0|n=1) return n; return fib(n-2)+fib(n-1); ,长席盯耻掀辊忿雨渔婶散物屿肆邱嚎启厂田啦袜焙捧荫贮她筷薛蝴毫煎摈线性结构习题课线性结构习题课,程序设计题(十三),非递