程序设计法学(三).ppt
《程序设计法学(三).ppt》由会员分享,可在线阅读,更多相关《程序设计法学(三).ppt(120页珍藏版)》请在三一文库上搜索。
1、2019/3/11,华东师大计算机科学技术系,1,第三章 程序的数据结构,数据结构是程序设计不可分割的部分。 算法数据结构程序 (N.Wirth) 数据及对数据的处理程序设计的核心。 数据表示的复杂程度直接决定了其上操作的复杂性,如不能有效地控制数据表示,必将导致软件系统的失败。 不同的应用领域对所要求的数据结构可能不同。 不同的数据结构直接决定了同一算法的不同实现。,2019/3/11,华东师大计算机科学技术系,2,3.1 类型,类型某些具有相同(相似)特性事物的集合 类型系统多种类型按某种方案加以组织以了解其复杂的关系,这是对科学发展起了重要作用的 方法分类法。 程序设计语言中,类型是一种
2、最基本的概念,也是构造程序的基础。 数据类型:1)一个值的集(类型域) 2)一个作用于值集的操作集,2019/3/11,华东师大计算机科学技术系,3,1. 对类型的描述,1) 确定值的集 如:布尔类型 Boolean:true,false 字符串 a)空串是字符串 b)单个字母是字符串 c)串的并置是字符串 2) 描述操作集 语法说明:指出操作名、被操作的数据类型 语义说明:操作的意义,2019/3/11,华东师大计算机科学技术系,4,描述方法: a)自然语言(非形式化方法)模糊 b)形式化方法精确 例如,加法(整数集上)可描述为: a) a,b是整数,则a+b是整数 b) +:intinti
3、nt 例1 字符串类型定义(操作集)Horowitz,2019/3/11,华东师大计算机科学技术系,5,type String declare NULLString /*语法说明*/ ISNULL(String)Boolean LEN(String)Int ADDCHAR(String,Char)String CONCAT(String,String)String SUBSTR(String,Int,Int)String INDEX(String,String)Int for all s,tString, c,dChar, i,jInt let ISNULL(NULL)=true ISNULL
4、(ADDCHAR(s,c)=false,2019/3/11,华东师大计算机科学技术系,6,LEN(NULL)=0 LEN(ADDCHAR(s,c)=LEN(s)+1 CONCAT(s,NULL)=s CONCAT(s,ADDCHAR(t,d)= ADDCHAR(CONCAT(s,t),d) SUBSTR(NULL,i,j)=NULL SUBSTR(ADDCHAR(s,c),i,j)= if j=0 then NULL else if j=LEN(s)-i+2 then ADDCHAR(SUBSTR(s,I,j-1),c) else SUBSTR(s,i,j),2019/3/11,华东师大计算机
5、科学技术系,7,INDEX(s,NULL)=LEN(s)+1 INDEX(NULL,ADDCHAR(t,d)=0 INDEX(ADDCHAR(s,t),ADDCHAR(t,d)= if INDEX(s,ADDCHAR(t,d) 0 then INDEX(s,ADDCHAR(t,d) else if c=d and t=SUBSTR(s,LEN(s)-LEN(t)+1,LEN(t) then LEN(s)-LEN(t)+1 else 0 end end String,2019/3/11,华东师大计算机科学技术系,8,2对类型的处理,)提供一个数据类型集;嵌入语言的类型 )提供一种机制,允许定义一
6、种新的类型 )变量的值限制于某种类型加以说明或定义 )提供一种类型检验的机制 a) 静态类型化语言。每个表达式的类型在 静态程序分析时确定 b) 强类型化语言。每个表达式类型是一致的 c) 弱类型化语言。,2019/3/11,华东师大计算机科学技术系,9,3类型化语言的优点,a)有助于正确性的加强(对系统的某种限制)。 b)增加了程序的可读性、可靠性、可维护性(防止基本逻辑单元间的不一致性)。 c)为程序设计者提供了在现实世界和程序所操纵的数据对象之间的连接渠道。 d)可以帮助发现错误(通过类型的唯一性)。,2019/3/11,华东师大计算机科学技术系,10,3.2 程序设计语言中的类型,发展
7、过程: 无类型、机器指令、汇编指令(抽象)基本数据类型(不够)结构化类型(大型程序设计)抽象数据类型(对象化)类、继承 1. 可枚举类型。 由有限的值集构成,所有的值组成一个表或通过上下界来限定,每个值称为一个文字量 操作:相等()、赋值(:=)、前者(pred(x))、后继(succ(x))、枚举、子界、集合(set) 如:Pascal语言中有枚举、子界类型,2019/3/11,华东师大计算机科学技术系,11,2 基本数据类型 布尔型、字符型、数值型、void型(值集为空) 3 结构化类型 )数组:是变量的有序的集合 type T :arrayI of T0 索引类型I:选择数组元素的值类型
8、 元素类型T0:数组元素类型,典型的是数类型,可 不加限制 元素均相同,称为同类数组;否则称为异类数组 数组的规模与表示这个数组所需的存贮容量有关 存储分配:编译时进行 C PASCAL FORTRAN 运行时进行 PL/I,2019/3/11,华东师大计算机科学技术系,12,操作:选择元素操作(下标) 整体复制 a:=b 部分复制 a*,3 )记录:多个值的集合 分量称为域,不同域可以有不同的类型 说明指出了类型的构造 type T=Record S1:T1,Sn:Tn end 操作:选择元素 同一记录每个域的标识必须不同, 不同的记录域的标识任意,2019/3/11,华东师大计算机科学技术
9、系,13,)序列(字符串) 序列是一个数组,串是一个字符序列,也可以作为独立的类型,长度可变。 操作:如:PL/1中定义了六种 | 连接 INDEX(a,b) b在a中第一次出现的位置 LENGTH 长度 SUBSTR 子串 TRANLATE(a,b,c) a中的c用b替代 VERIFY(a,b) a中第一个在b中不 出现的字符,否则为0,2019/3/11,华东师大计算机科学技术系,14,)指针 type T= T0 T0为所指对象的类型 指针最早在PL/1中出现,无类型检查, ALGOL68首次引入类型化指针。 能力很强: 允许存储的生命期超出程序块的边界。 允许若干变量共享存储。 允许复
10、杂结构有选择地被更新。 极易出错: 如“悬摆指针” 较难理解:如 int *(*(*x)6)( ); char (*(*y( ) )( );,2019/3/11,华东师大计算机科学技术系,15,操作:相等(不等)、赋值、引用、存储分配(new)(释放 free) )联合(变体记录) )递归类型:一个递归类型是涉及自身的类型 如:type tree=record left,right:tree; info:int; end record; root:tree; 无法解决直接存储问题,通常的方法是引入指针。,2019/3/11,华东师大计算机科学技术系,16,3.3 数据抽象,抽象:是普遍的概念,
11、是普遍的、科学的方法。是对一种事物(或一个系统)的简化描述。把注意力集中在本质方面,而忽略其细节。 E.Dijstra:设计实现一个大规模软件的中心问题是怎样减少复杂度。一个途径就是抽象。 软件技术的发展过程就是抽象程度不断提高的过程。,2019/3/11,华东师大计算机科学技术系,17,1. 数据抽象,“子程序”是一种沿用很久的一种抽象。但存在:如何对共享变量(全局量)进行检验的问题。 仅有结构化程序设计一个方法不能应付日益增大的软件规模。需要一种新的途径去组织并保护数据。 1) 数据类型的定义不仅只是值的集合,还应包含作用于值集的操作集。 2) 对数据的保护不能只依靠程序员或OS,语言本身
12、应提供保护的机制。 3) 应支持分块编译。,2019/3/11,华东师大计算机科学技术系,18,概念,于是产生数据抽象这一概念: 把数据类型的定义与其实现加以分离。 a) 把大系统分解成多个小部分,每部分有为所处理数据而设计的接口。 b) 接口是这个部分的说明,是外部可见的而该部分的实现是隐藏的,外部不可见的。 c) 所需的保护措施放在每个接口中。,2019/3/11,华东师大计算机科学技术系,19,意义,数据抽象是继结构化程序设计后又一次革命。 降低了程序设计的复杂性,为程序正确性验证提供了一个框架,为提高软件生产率提供了一种手段。 以后出现的新的程序设计语言都建立在数据抽象的基础上。,20
13、19/3/11,华东师大计算机科学技术系,20,2抽象数据类型(ADT),根据数据抽象的原则,符合“一个值集和作用在值集上的操作集”的数据类型,称为ADT. 一个ADT可以分解成四部分: 语法 说明 语义 ADT 表示 实现 算法,使用ADT不需要知道如何实现,有关实现的知识不能被直接使用!,2019/3/11,华东师大计算机科学技术系,21,语法:指出所有操作符或过程名,被操作对象 的个数及类型、返回类型 语义:说明类型的行为、意义(可以用形式的 或非形式的方法表示) 表示:指出ADT中值的存储形式(数据结构) 算法:说明是如何实现的,2019/3/11,华东师大计算机科学技术系,22,例:
14、用ADT定义字符串charstring,说明 语法:元素:AZ, 结构:元素间的先后线性关系 域:串长为060 语义:操作 用前置条件(pre)、后置条件 (post)说明操作的行为。 操作前的值,记为s_pre 操作后的值,记为s_post,2019/3/11,华东师大计算机科学技术系,23,leftchar(var s:charstring):char pre:字符个数0 post:leftchar是输入串s中最左边的字符,s_post是s_pre除去左边第一个字符后的字符串。 append(c:char;var s:charstring) pre:s_pre中的字符数小于60 post:
15、s_post的长度比s_pre的长度大1 s_post的最后一个字符是c empty(s:charstring):Boolean pre:无 post:如s空,返回true;否则false.,2019/3/11,华东师大计算机科学技术系,24,full(s:charstring) pre:无 post:如s包含60字符,返回true;否则false. reverse(var s:charstring) pre:无 post:倒转;第一个字符与最后一个字符互换 第二个字符与最后第二个字符互换 以此类推。,2019/3/11,华东师大计算机科学技术系,25,实现: 表示:type charstri
16、ng record n:060; str:array160 of char; end 算法:略 试用形式的方法表示各操作的pre和post,2019/3/11,华东师大计算机科学技术系,26,ADT的优点,1) 支持模块化:ADT自成模块,使结构化得以保证,程序易理解。 2) 封装性:“黑匣”,数据结构的完整性得以保证。 3) 简化对正确性的验证:可单独对ADT进行验证,ADT又是类型化的,可由编译加以检验。 4) 实现部分可独立更换不影响使用,支持复用,提高软件质量。,2019/3/11,华东师大计算机科学技术系,27,3.支持数据抽象的语言及其设施,最早支持ADT 是simula 67,其
17、ADT的设施是CLASS,在ALGOL语言的基础上发展起来的。 Modula是Pascal的直接后继者,流行的是 modula-2,ADT的设施是module。由定义部、实现部所组成。 a) 分别编译、存放在库中,主程序在执行中能自动调用module。 b) 定义部:外部可见;实现部:对外隐蔽的 。,2019/3/11,华东师大计算机科学技术系,28,例:Buffer的modula-2实现,DEFINITION MODULE Buffer EXPORT QUALIFIED put,get,nonempty,nonfull; VAR nonempty,nonfull:Boolean; Proce
18、dure Put(x:CARD); Procedure Get(x:CARD); END Buffer IMPLEMENTATION MODULE Buffer; CONST N=100;,2019/3/11,华东师大计算机科学技术系,29,VAR Procedure Put(x:CARD) Begin end Procedure get(x:CARD) Begin end Begin (初始化) end,2019/3/11,华东师大计算机科学技术系,30,Ada是数据抽象的概念趋于成熟时的产物。Ada支持ADT的设施是:Package(串行) task(并行) Package的二种形式: a
19、)由说明部和实现部组成 b)在说明部后加上private部,2019/3/11,华东师大计算机科学技术系,31,例:Stack的Ada实现,package STACK is procedure PUSH(x:REAL); function POP return REAL; end; package body STACK is MAX:constant:=100 S:array(1MAX)of REAL; PTR:INTEGER range 0MAX,2019/3/11,华东师大计算机科学技术系,32,procedure PUSH(x:REAL) is begin end PUSH; funct
20、ion POP return REAL begin end POP; begin PTR:=0; end STACK;,2019/3/11,华东师大计算机科学技术系,33,实现部中有关类型的说明可在说明部分中用private指出,如: package STACK is private type STACK is record MAX:constant:=100; S:array(1MAX)of REAL; PTR:INTEGER range 0MAX:=0; end record; end;,2019/3/11,华东师大计算机科学技术系,34,外部程序使用Package的三种形式: a) pa
21、ckage名加操作名,用.隔开,如: STACK.PUSH(X) b) 用一个子句,如: declare use STACK begin PUSH(X); end; c) 再命名方法: declare Procedure SPUSH(X:REAL) renames STACK_PUSH(X); begin SPUSH(X); end;,2019/3/11,华东师大计算机科学技术系,35,4.支持数据抽象其他设施,a) 类属函数(Generic) 问题:能否对同一类操作设计一个模板式的通用程序,可用于不同的数据类型。 解决:类属函数(过程),作为通用的模板,将一个或多个元素参数化,编译时被实例化
22、,得到确定数据类型的函数(过程)。 特点:不能直接使用,必须实例化。以类属说明定义,通过类属形实替换完成。,2019/3/11,华东师大计算机科学技术系,36,例:Ada支持类属函数的方法,以STACK为例: generic MAX:INTEGER; type ELEM is private; package STACK is procedure PUSH(x:ELEM); function POP return ELEM; end; end STACK;,2019/3/11,华东师大计算机科学技术系,37,b) 多态(polymorphism) 单态:若一个类型化的语言每个值有且只有一种类型
23、,称为单态语言。 多态:若一个类型化的语言每个值可以有多于一种的类型,称为多态语言。 参数的 通用 包含的 多态 过载的 特定 强制的,通用:对工作的类型数量不 限,允许不同类型的变 元执行相同的代码。 特定:对工作的类型数量限 制,不同类型的变元 可能需要执行不同的 代码。,2019/3/11,华东师大计算机科学技术系,38,参数多态:应用较广,被称为最纯的多态,如类属函数。 包含多态:如子类型化、继承。 过载多态:通过相同的语法对不同语义的对象使用相同的名。如重载。 强制多态:通过语义操作改变一个变元的类型,以符合特定的要求。如强制类型转换(cast)。,2019/3/11,华东师大计算机
24、科学技术系,39,c) 分别编译(Separate Compilation) 独立编译:FORTRAN 整体编译:PASCAL 分别编译:Ada ADT概念的形成和广泛应用和分别编译的思想及其应用密切相关。 分别编译支持: 程序库,使的ADT构成的模块可以存放在程序库中,不必使用时再编程。 被编译的程序与库中已编译的模块相链接。,2019/3/11,华东师大计算机科学技术系,40,联编(binding) 概念:联编是指一个名(标识符)和存储地址相连。 如: 不同的语言何时进行联编的安排是不同的。 如:FORTRAN 编译时 Pascal 过程入口处 C 分程序入口处 联编与变量的作用域、生存期
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 程序设计 法学
链接地址:https://www.31doc.com/p-2250255.html