第二章数据类型

Giovanna

About 2137 wordsAbout 7 min

2024-06-29

数据类型实质上是对存储器中所存储的数据进行的抽象。

它包含了一组值和一组操作。

一、内部类型（语言定义的）

内部类型反应基本硬件特性
- 25 -> 0001 1001
- 整数加法 -> 定点加
在语言级，内部类型标识共用某些操作的数据对象的抽象表示
- 整数表示能实现+、-、*、/等定点操作的数据对象的集合
内部类型的优越性
1. 基本表示的不可见性
  - 基本位串不可见
2. 编译时能检查变量使用的正确性
  - 进行静态类型检查，如非法运算、形实参类型匹配
3. 编译时可以确定无二义的操作
  - 超载，类型转换
4. 精度控制

二、用户自定义类型

1. 笛卡尔积

$N$ 个集合 $A_1,A_2,\ldots,A_n$ 的笛卡尔积表示为 $A_1\times A_2 \times\ldots\times A_n$ ，它是一个集合，其元素为 $(a_1,a_2,\ldots,a_n)$ ，其中 $a_i\in A_i$ 。

在COBOL和PASCAL中称为记录；在ALGOL中称为结构。

笛卡尔积数据对象有若干个域，每个域有唯一的名字，用域名进行操作。

2. 有限映像（射）

从定义域类型DT的值的有限集合，到值域类型RT的值的有限集合的函数称为有限映像（射）。

在高级语言中通常体现为数组构造
值域对象通过下标选取
下标越界会出错，动态检查
下标可用来选取值域的多个元素（APL，ALGOL，ADA）
SNOBOL4的ARRAY构造符并不要求值域集合的所有元素是同一类型
DT到相应值得特定子集的绑定策略
- 编译时绑定（静态数组）
- 对象建立时绑定（执行到分程序时，动态数组）
- 对象处理时绑定（对APL，子集范围可变）

3. 序列

序列由任意多个数据项组成，这些数据项称为该序列的成分，且类型相同。

串、顺序文件

Note

字符串的一般操作有4种：连接、首项选取、子串

4. 递归

若数据类型T包含属于同一类型T的成分，那么类型T称为递归类型。

递归类型的特点

允许在类型定义中使用被定义类型的名字
指针是建立递归数据类型的重要手段

单链表、二叉树、树

5. 判定或

一个选择对象结构的构造机制，规定在两个不同选择对象之间作出适当的选择；每一选择对象结构称为变体。

PASCAL、ADA中的变体记录；C和ALGOL68中的联合。

6. 幂集

类型 $T$ 的元素所有子集的集合，称为幂集，记为 $Powerset(T)$ ， $T$ 称为基类型。

基本操作：联合、与、测试某个元素是否在一个集合中。

集合

小结

新类型可以通过显式和非显式的方式说明。

显式定义有如下优点：

可读性（选择名字）
可修改性（不修改变量说明）
可分性（重复使用）
一致性检查

三、抽象数据类型

1. 用户定义类型与内部类型的异同

同：都建立某种基本表示的抽象；每一类型都关联一组操作。

异：内部类型隐蔽了基本表示，不能对它的成分进行操作；用户定义类型具有更高级别的抽象，可以对其基本表示的成分进行操作。

2. 抽象数据类型

信息隐蔽、重用

定义：满足下述特性的用户定义类型称为抽象数据类型

在实现该类型的程序单元中，建立与表示有关的基本操作
对使用该类型的程序单元来说，该类型的表示是隐蔽的

C++、JAVA中的抽象数据类型称为类，类的实例称为对象。

四、类型检查

对数据对象的类型和使用的操作是否匹配的一致性检查称为类型检查。

类型检查的分类

语言的类型检查分为静态检查和动态检查。

静态检查：在编译时进行的检查，特点是正确高效
动态检查：在运行时进行的检查，特点是编程方便但可读性差

语言按类型分类

语言按类型分为无类型语言、弱类型语言和强类型语言

无类型语言：语言没有类型定义
- 函数式语言FP和FFP
弱类型语言：语言的类型检查不能全部在编译时完成，有些要在运行时才能完成
- vb，php，pascal
强类型语言：语言的类型检查全部在编译时完成
- Java，C++，Python

五、类型转换

将一个类型的值转换成另一个类型的值，称为类型转换。

类型转换分为拓展和收缩

拓展：转换之后的类型值的集合包含转换之前的类型值的集合
- 整型->实型
收缩：转换之前的类型值的集合包含转换之后的类型值的集合
- 实型->整型

Warning

收缩可能导致某些信息的丢失。例如，PL/1语言中实数到整数的收缩采用截断；而PASCAL则使用舍入法进行从实数到整数的收缩。

在某些语言中，类型转换的要求和规则是隐式的，它由编辑器自动生成类型转换的代码。

一般来说，语言对基本类型提供适当的类型转换，而对复合类型或用户自定义类型不提供转换。

六、类型等价

若T1和T2是两个类型，且T1的任何值都可以赋予T2类型的变量，T1类型的实参可以对应T2类型的形参，反之亦然，则称T1和T2是相容的。

有两种类型的相容性概念：

名字等价：两个变量的类型名相同，e.g. Ada
结构等价：两个变量的类型具有相同的结构，e.g. ALGOL 68

七、实现模型

在实现模型中，数据用描述符和数据对象来表示。

描述符用来描述数据对象的所有属性。

1. 非结构类型

包括内部类型和用户定义的非结构类型

描述符一般由“类型”和一个指针组成
子界的描述符必须包括子界的界值
布尔型和字符型可以压缩存储

2. 笛卡尔积

各成分顺序排列（数据）
描述符包括：类型名、构造符、若干三元式。每个域对应一个三元式（选择符名，域类型，指针）
每个成分占整数个可编址的存储单元
可以用packed

type t=record a:real;
       b:integer;
    end;

3. 有限映像

为每一成分分配整数个可编址的存储单元
描述符包括：类型名、构造符、定义域的基类型、下界、上界、成分类型、单元个数、首地址
A[i]地址公式的计算b+k(i-m)=b-km+ki=b'+ki，b为首地址，k为每个元素所占存储单元个数，m为下界

type a=array[1..10] of real;

4. 序列

PASCAL中的串长度静态可定，静态分配
其他语言（如SNOBOL 4和ALGOL 68），可变串表示：静态描述符+动态描述符+堆

5. 判定或

对判定或类型的变量所分配的空间应足以容纳需要最大空间的变体的值
PASCAL的变体记录的表示包括：描述符、数据对象、case表、若干变体描述符

type v=record a:integer
	   case b:boolean of
	   true:(c:integer);
	   false:(d:integer;
	          e:real;)
	end;

6. 幂集

集合关联若干个机器字，通过每一位的取值可知该集合中有基类型的哪些元素
位操作

7. 指针

指针变量的表示类似于内部类型，只是其值为一地址，并且它指向的数据对象分配在堆上。

8. 层次数据结构

描述符中的类型可以指向另外的描述符。

type t1=array[0..3] of integer;
    t=record a:real;
		  b:t1;
		  c:integer;
	  end;

type t4=array[0..5] of integer;
     t2=array[0..2] of t4;

第二章 数据类型

第二章数据类型