威廉勃特勒叶芝willia.pptVIP

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