《线性结构习题课》PPT课件.ppt

《线性结构习题课》PPT课件.ppt

ID:52372004

大小:227.06 KB

页数:34页

时间:2020-04-05

《线性结构习题课》PPT课件.ppt_第1页
《线性结构习题课》PPT课件.ppt_第2页
《线性结构习题课》PPT课件.ppt_第3页
《线性结构习题课》PPT课件.ppt_第4页
《线性结构习题课》PPT课件.ppt_第5页
资源描述:

《《线性结构习题课》PPT课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、线性表,栈,队列习题课主讲老师:陈玉泉助教:刘磊主要内容顺序表单链表(单向循环链表)双链表(双向循环链表)栈(顺序存储,链式存储)队列(顺序存储,链式存储)应用概念题1.简单比较线性表的顺序和链接两种存储方式各有什么主要优缺点?顺序存储:优点:(1)在结点等长时可随机存取;(2)存储密度高,节省存储空间;(3)用结点的物理次序反映结点之间的逻辑关系。缺点:(1)插入和删除结点时要移动大量结点;(2)必须静态分配连续的空间。概念题(一)链接存储:优点:(1)插入和删除比较灵活,不需要大量移动结点;(2)动态分配空间比较灵活,不需要预先申请最大的连续空间。缺点

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

3、,…,n的一种排列)的充分必要条件是,不存在这样的下标i,j,k,满足i

4、念题(七)情况1:若Pj在输入序列的剩余部分(假设1,2,…,i-1已经输入)i,i+1,…,n中,则把Pj之前的元素及Pj进栈,然后把Pj从栈中取出送入序列。情况2:若Pj已经在栈中,则他必然在栈顶(这是因为栈中元素在任何时刻显然都是从顶向下递减的,而刚离栈的Pj-1大于栈中的所有元素。假如Pj不在栈顶,设栈顶元素是Pk,我们有j-1Pk>Pj,矛盾)把栈顶元素取出送入序列。重复上述步骤,可得到所要求的序列。概念题(八)4.把下面的中缀表达式转化为相应的后缀和前缀表达式:(A+B)*C-D*F+C前缀:(A+B)*C-D*F+C=>

5、((((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)能由输出受限的双端队列得到,但不能由输入受限的双端队列得到的输出序列;概念题(十一)解答:允许在一

6、端进行插入和删除,但在另一端只允许插入的双端队列叫做输出受限的双端队列,允许在一端进行插入和删除,但在另一端只允许删除的双端队列叫做输入受限的双端队列。输出受限双端队列不能得到的输出序列有:41324231输入受限双端队列不能得到的输出序列有:42134231程序设计题6.将具有头结点的单链表的所有指针全部进行倒向。要求使用的额外空间只能为O(1),时间代价只能为O(n),其中n为结点个数。解析:首先考虑头结点,然后对链表进行一遍遍历即可。程序设计题(一)templatevoidList::Inverse(){if(hea

7、d->Next==NULL

8、

9、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次数,po

10、n是pop次数。当pun=pop=n的时候,操作序列生成完毕。程序

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。