程序设计法学(三).ppt

第三章程序的数据结构
数据结构是程序设计不可分割的部分。
算法+数据结构=程序()
数据及对数据的处理程序设计的核心。
数据表示的复杂程度直接决定了其上操作的复杂性,如不能有效地控制数据表示,必将导致软件系统的失败。
不同的应用领域对所要求的数据结构可能不同。
不同的数据结构直接决定了同一算法的不同实现。
Date
1
§ 类型
类型-某些具有相同(相似)特性事物的集合
类型系统-多种类型按某种方案加以组织以了解其复杂的关系,这是对科学发展起了重要作用的
方法——分类法。
程序设计语言中,类型是一种最基本的概念,也是构造程序的基础。
数据类型:1)一个值的集(类型域)
2)一个作用于值集的操作集
Date
2
1. 对类型的描述
1)  确定值的集
如:①布尔类型 Boolean:{true,false}
②字符串 a)空串是字符串
b)单个字母是字符串
c)串的并置是字符串
2) 描述操作集
语法说明:指出操作名、被操作的数据类型
语义说明:操作的意义
Date
3
描述方法:
a)自然语言(非形式化方法)——模糊
b)形式化方法——精确
例如,加法(整数集上)可描述为:
a)     a,b是整数,则a+b是整数
b)    ‘+’:int×int->int
※例1 字符串类型定义(操作集)Horowitz
Date
4
type String
declare NULLString /*语法说明*/
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,tString, c,dChar, i,jInt let
ISNULL(NULL)=true
ISNULL(ADDCHAR(s,c))=false
Date
5
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)
Date
6
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
Date
7

ⅰ)提供一个数据类型集;嵌入语言的类型
ⅱ)提供一种机制,允许定义一种新的类型
ⅲ)变量的值限制于某种类型加以说明或定义
ⅳ)提供一种类型检验的机制
a) 静态类型化语言。每个表达式的类型在静态程序分析时确定
b)   强类型化语言。每个表达式类型是一致的
c)    弱类型化语言。
Date
8

a)有助于正确性的加强(对系统的某种限制)。
b)增加了程序的可读性、可靠性、可维护性(防止基本逻辑单元间的不一致性)。
c)为程序设计者提供了在现实世界和程序所操纵的数据对象之间的连接渠道。
d)可以帮助发现错误(通过类型的唯一性)。
Date
9
§ 程序设计语言中的类型
发展过程:
无类型、机器指令、汇编指令(抽象)基本数据类型(不够)结构化类型(大型程序设计)抽象数据类型(对象化)类、继承
1. 可枚举类型。
由有限的值集构成,所有的值组成一个表或通过上下界来限定,每个值称为一个文字量
操作:相等(=)、赋值(:=)、前者(pred(x))、后继((x))、枚举、子界、集合(set)
如:Pascal语言中有枚举、子界类型
Date
10