数据结构(C语言版)习题集答案 第三章_第1页
数据结构(C语言版)习题集答案 第三章_第2页
数据结构(C语言版)习题集答案 第三章_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

数据结构(C语言版)习题集答案第三章数据结构(C语言版)习题集答案第三章数据结构(C语言版)习题集答案第三章数据结构(C语言版)习题集答案第三章编制仅供参考审核批准生效日期地址：电话：传真:邮编:习题三给定操作序列P1P2P3…Pi…Pn（Pk为S或X，k=1,2,…n）是合法的，当且仅当满足下列条件：a.序列中包含的S的个数和X的个数相等；b.对于任意的j（1≤j≤n）；有P1P2P3…Pj子序列中所包含的S的个数大于等于X的个数；证明：设P1P2P3…Pi…Pn，Q1Q2Q3…Qi…Qn是两个不同的合法序列；∵两者不同，∴k=min{i|Pi≠Qi,1≤i≤n}且k>1，Pk≠Qk（因P1，Q1肯定是S，否则不合法！）即，P1P2P3…Pk-1和Q1Q2Q3…Qk-1是相等的，但Pk≠Qk由此可知：两个操作序列在前k-1步操作后输出序列和栈中所剩元素均相同，由于Pk≠Pk不妨设Pk=X，而Qk=S；这样，在操作序列P1P2P3…Pi…Pn中的第k-1步后输出的第一个元素是目前栈中的元素，而对于操作序列Q1Q2Q3…Qi…Qn中的第k-1步后输出的第一个元素是目前还在栈外的元素。所以输出序列不同。即两个不同的合法操作序列，不可能得到相同的输出序列。证毕！用反证法证明：假设存在这样的输出序列，P1…Pi…Pj…Pk…Pn，满足i<j<k,使Pj<Pk<Pi;因Pi在这三个数中最大，且Pi最先出栈，按照题意所给进栈顺序，在Pi出栈时Pj和Pk都还在栈中；又因，Pj<Pk，所以Pj比Pk先进栈，则出栈顺序应该是Pk先出栈而不是Pj先出栈，矛盾！证毕！(1)输出序列为：0,5,9,12,14,15由于输入的数据个数不定，采用单链表存储输入的元素，又因是先输入的，后累加到累加器里，所以用链栈的形式存储。（类型定义与书本上第二章相同）

人人文库> 全部分类> 教育资料 > 备课教案

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论