下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
数据结构(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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 浙江省杭州地区达标名校2024年中考四模生物试题含解析
- 江苏省连云港市东海县2024届高一下数学期末综合测试模拟试题含解析
- 内蒙古呼和浩特市2024年高一数学第二学期期末检测试题含解析
- 2024届江西省南昌市进贤二中高一数学第二学期期末调研试题含解析
- 混合动力式医用控温毯控制系统研究
- 含分布式光伏源的配电网无功电压控制策略的研究
- 2024届山东省平阴县第一中学高一下数学期末学业质量监测模拟试题含解析
- 乌兰察布市重点中学2024届高一下数学期末学业质量监测试题含解析
- 2023-2024学年甘肃省兰州市第五中学高一下数学期末质量跟踪监视模拟试题含解析
- Doxifluridine-d3-Ro-21-9738-d-sub-3-sub-生命科学试剂-MCE
- 《杨氏之子》的评课稿
- 塔吊安装拆除安全措施
- 01《工程测量》第一章绪论作业与习题答案
- 优秀工会积极分子先进申报材料
- 商业街整体招商方案3篇
- 危险化学品生产企业安全评价导则(试行)安监管危化字[2004]127号
- 低压电工考试题易错题
- 空压机能效测试方案
- 病历质量管理小组.doc
- ICAO英语四级资料:复考部分
- 我和我的祖国(李谷一)原版正谱钢琴谱五线谱乐谱.docx
评论
0/150
提交评论