- 1、本文档共54页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
Abstract Data Types;摘要;回顾:结构化软件开发;回顾:结构化软件开发;注: 有关程序正确性;从面向过程到面向对象;The first step;如何导出软件系统的结构?;面向对象的分解好在何处?;例:考虑一个工资系统;例:考虑一个工资系统;“面向对象”的含义(之一) ;The O-O designer’s motto;对象设计相关问题;对象刻画;对象刻画问题;A stack, concrete object;A stack, concrete object;抽象数据类型;Stack: An abstract data type;Using functions to model operations;Reminder: Partial functions;The STACK ADT (cont’d);Formal stack expressions;Expressed differently;An operational view of the expression;;Expression reduction (2/10);ADT 函数分类;ADT规约质量?;Sufficient Completeness;Consistency;Stack: An abstract data type;The STACK ADT (cont’d);证明;基本思路;Weight;Weight Consistency rule :
A well-formed stack expression e, involving neither item nor empty, is correct if and only if its weight is non-negative, and any subexpression of e is (recursively) correct.
Zero Weight rule:
Let e be a well-formed and correct stack expression not involving item or empty. Then empty (e) is true if and only if e has weight 0.
;以归纳法证明上述两规则:
e 是 well-formed 的 不包含empty和item
1. e是correct的 = W(e) ≥ 0 ∧ e中的子表达式correct
2. 若e是correct的,empty(e) = W(e)=0
嵌套层数为0:必为new,上述两规则显然成立(当然我们也可以验证为1的情况)
假设对于嵌套层数不超过n的表达式上述两规则均成立,现证明对于嵌套层数为n+1时它们成立
考虑e的最外层函数 必为 put 或 remove
若e = put(s, x), ......
;.......
若e = remove(s),
1= e is correct, s is correct and not empty(s),
W(s)0 W(e)=W(s)-1 ≥0
1=
2 W(s)0, s至少有一个put,设其最外的put为
put(s’, xexp), 在e中它的外面必为remove
... remove( put ( s’, xexp ) ) ...
e 变成 e’ 层数减2 empty值不变 规则2成立
Correct的无empty和item的表达式可消去remove;
;ADT与软件开发;ADT and software architecture;Implementing an ADT;A choice of stack representation;信息隐蔽原则;“面向对象”的含义(初步) ;“面向对象”的含义(进一步) ;类:对象程序的基本结构;类之间的关系;Overall system structure;A very deferred class;小结;作业-2
文档评论(0)