《数据结构与算法 C语言版》—— 1.4数据类型与抽象数据类型

本节书摘来自华章出版社《数据结构与算法 C语言版》一 书中的第1章，第1.4节，作者：徐凤生，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

1.4数据类型与抽象数据类型

1.4.1数据类型

数据类型是和数据结构密切相关的一个概念，它最早出现在高级程序语言中，用以刻画(程序)操作对象的特性。在用高级程序语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。类型显式或隐含地规定了在程序执行期间变量或表达式所有可能的取值范围，以及在这些值上允许进行的操作。因此，数据类型是一个值的集合和定义在此集合上的一组操作的总称。例如，C语言中的整型变量，其值为某个区间上的整数(依赖于机器)，定义在其上的操作为加、减、乘、除和取模等算术运算。
按“值”的不同特性，高级程序语言中的数据类型分为原子类型和结构类型两类。原子类型的值是不可分解的，如C语言中整型、字符型、浮点型、双精度型等基本类型，分别用保留字int、char、float、double标识。结构类型的值是由若干成分按某种结构组成的，因此是可分解的，并且它的成分可以是非结构的，也可以是结构的。例如，数组的值由若干分量组成，每个分量可以是整数，也可以是数组等。在某种意义上，数据结构可以看成是一组具有相同结构的值，而数据类型则可看成是由一种数据结构和定义在其上的一组操作组成的。

1.4.2抽象数据类型

抽象数据类型(Abstract Data Type，ADT)是指一个数学模型以及定义在此数学模型上的一组操作。例如，“整数”是一个抽象数据类型，其数学特性和具体的计算机或语言无关。“抽象”的意义在于强调数据类型的数学特性。抽象数据类型和数据类型实质上是一个概念，只是抽象数据类型的范围更广，除了已有的数据类型外，抽象数据类型还包括用户在设计软件系统时自己定义的数据类型。
ADT的定义取决于它的一组逻辑特性，而与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部的使用，从而为实现软件的部件化和可重用性提供了保证，进而提高了软件生产率。
抽象数据类型的最重要的特点是抽象和信息隐蔽。抽象的本质是抽取反映问题本质的东西，忽略非本质的细节，从而使所设计的数据结构更具有一般性，可以解决一类问题。信息隐蔽就是对用户隐蔽数据存储和操作实现的细节，使用者仅需了解抽象操作或界面服务，通过界面中的服务来访问这些数据。
一个含抽象数据类型的软件模块通常应包含定义、表示和实现三部分。
抽象数据类型可用(D，S，P)三元组表示，其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。本书采用以下格式定义抽象数据类型：

ADT抽象数据类型名{
数据对象：〈数据对象的定义〉
数据关系：〈数据关系的定义〉
基本操作：〈基本操作的定义〉
}ADT抽象数据类型名
其中，数据对象和数据关系的定义采用伪码描述，基本操作的定义格式为：

基本操作名(参数表)
初始条件：〈初始条件描述〉
操作结果：〈操作结果描述〉
基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应的出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则省略操作结果。

1.4.3抽象数据类型的表示与实现

抽象数据类型可以通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已实现的操作来组合新的操作。本书采用介于伪码和C语言之间的类C语言作为描述工具，下面对其作简要说明。
(1)预定义常量

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW-1

(2)数据结构的表示(存储结构)
数据结构的表示用类型定义(typedef)描述，数据元素类型约定为ElemType,由用户在使用该数据类型时自行定义。
(3)基本操作算法的描述

函数类型函数名(参数表)｛//算法说明
语句序列
｝//函数说明

除了需要说明函数中的参数类型外，对算法中使用的变量可以不作变量说明，但在必要时要对其作用给予注释。在参数表中，以＆打头的参数为引用参数。
一般而言，a、b、c、d等用作数据元素名，i、j、k等用作整型变量名，p、q、r等用作指针变量名。
(4)赋值语句
简单赋值：变量名=表达式;
串联赋值：
变量名1=…=变量名k=表达式;
条件赋值：
变量名=条件表达式?表达式T:表达式F;
(5)选择语句
条件语句1：
if(表达式)语句;
条件语句2：
if(表达式)语句;

else语句;

开关语句1：
switch(表达式){
case值1:语句序列1;break;
…
case值n:语句序列n;break;
default:语句序列n+1;break;

}
开关语句2：
switch{
case条件1:语句序列1;break;
…
case条件n:语句序列n;break;
default:语句序列n+1;break;

}
(6)循环语句
for语句:

for(赋初值表达式序列;条件;修改表达式序列)语句;
while语句:
while(条件){
语句序列

}；
do-while语句:
do{
语句序列;

}while(条件);
(7)输入输出语句
输入语句:
scanf(［格式串］,变量1,变量2,…,变量n);
输出语句:
printf(［格式串］,变量1,变量2,…,变量n);
(8)结束语句
函数结束语句：
return表达式;

return;
异常结束语句：
exit(异常代码);
case结束语句：
break;
(9)注释
单行注释：//文字序列
(10)逻辑运算符
与运算&&、或运算||、非运算！。
例1

抽象数据类型“复数”的表示与实现。
//-----复数存储结构的定义-----
typedef struct{
float realpart;
float imagpart;
}complex;
//定义抽象数据类型“复数”
ADT Complex {
数据对象:D={e1,e2｜e1,e2∈RealSet}
数据关系:R1={|e1是复数的实数部分,e2是复数的虚数部分}
基本操作:
AssignComplex(&z,v1,v2)
操作结果:构造复数z,其实部和虚部分别被赋予参数v1和v2的值。
GetReal(z,&realPart)
初始条件:复数已存在。
操作结果:用realPart返回复数z的实部值。
GetImag(z,&ImagPart)
初始条件:复数已存在。
操作结果:用ImagPart返回复数z的虚部值。
Add(z1,z2,∑)
初始条件:z1,z2是复数。
操作结果:用sum返回两个复数z1,z2的和值。
DispComplex(complex z);
初始条件:复数已存在。
操作结果:输出复数z。
}ADT Complex

//-----基本操作的实现-----
void AssignComplex(complex &z,float v1,float v2){//构造复数Z
z.realpart=v1;
z.imagpart=v2;
}
void GetReal(complex z,float &realpart){//用realPart返回复数Z的实部值
realpart=z.realpart;
}
void GetImag(complex z,float &imagpart){//用ImagPart返回复数Z的虚部值
imagpart=z.imagpart;
}
void add(complex z1,complex z2,complex &sum){//以sum返回两个复数z1,z2的和
sum.realpart=z1.realpart+z2realpart;
sum.imagpart=z1.imagpart+z2imagpart;
}
void DispComplex(complex z){//输出复数Z
printf("%f+%fi\\n",z.realpart,z.imagpart);