数据结构（C语言版）（第2版）
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

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

运用抽象数据类型描述数据结构，有助于在设计一个软件系统时，不必首先考虑其中包含的数据对象，以及操作在不同处理器中的表示和实现细节，而是在构成软件系统的每个相对独立的模块上定义一组数据和相应的操作，把这些数据的表示和操作细节留在模块内部解决，在更高的层次上进行软件的分析和设计，从而提高软件的整体性能和利用率。

抽象数据类型的概念与面向对象方法的思想是一致的。抽象数据类型独立于具体实现，将数据和操作封装在一起，使得用户程序只能通过抽象数据类型定义的某些操作来访问其中的数据，从而实现了信息隐藏。在C++中，我们可以用类的声明表示抽象数据类型，用类的实现来实现抽象数据类型。因此，C++中实现的类相当于数据的存储结构及其在存储结构上实现的对数据的操作。

抽象数据类型和类的概念实际上反映了程序或软件设计的两层抽象：抽象数据类型相当于在概念层（或称为抽象层）上描述问题，而类相当于在实现层上描述问题。此外，C++中的类只是一个由用户定义的普通类型，可用它来定义变量（称为对象或类的实例）。因此，在C++中，最终是通过操作对象来解决实际问题的，所以我们可将该层次看做是应用层。例如，main程序就可看做是用户的应用程序。

由此可以看出，最终表示和实现抽象数据类型，最好用面向对象的方法，比如用C++语言的类描述比较方便、有效，但本课程大都在大学低年级开设，用C语言的描述方法更符合学生的实际情况。另外，由于实际问题千变万化，数据模型和算法也形形色色，因此抽象数据类型的设计和实现，就不可能像基本数据类型那样规范和一劳永逸。本书所讨论的数据结构及其算法主要是面向读者的，故采用介于伪码和C语言之间的类C语言作为描述工具。这使得数据结构与算法的描述与讨论简明清晰，不拘泥于C语言的细节，又容易转换成C或C++程序。

本书采用的类C语言精选了C语言的一个核心子集，同时做了若干扩充修改，增强了语言的描述功能，以下对其做简要说明。

（1）预定义常量及类型：

//函数结果状态代码
#define OK 1
#define ERROR 0
#define OVERFLOW -2
//Status是函数返回值类型，其值是函数结果状态代码。
typedef int Status;

（2）数据结构的表示（存储结构）用类型定义（typedef）描述；数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。

（3）基本操作的算法都用如下格式的函数来描述：

函数类型 函数名（函数参数表）
{
   //算法说明
   语句序列
}//函数名

当函数返回值为函数结果状态代码时，函数定义为Status类型。为了便于描述算法，除了值调用方式外，增加了C++语言引用调用的参数传递方式。在形参表中，以“&”打头的参数即为引用参数。传递引用给函数与传递指针的效果是一样的，形参变化实参也发生变化，但引用使用起来比指针更加方便、高效。

（4）内存的动态分配与释放。

使用new和delete动态分配和释放内存空间：

分配空间 指针变量=new数据类型;
释放空间 delete指针变量;

（5）赋值语句：

简单赋值 变量名=表达式;
串联赋值 变量名1=变量名2=...=变量名n=表达式;
成组赋值 (变量名1, ..., 变量名n)=(表达式1, ..., 表达式n);
结构赋值 结构名1=结构名2;
        结构名=(值1, 值2, ..., 值n);
条件赋值 变量名=条件表达式 ? 表达式T：表达式F;
交换赋值 变量名1 <-->变量名2;

（6）选择语句：

条件语句1 if (表达式) 语句;
条件语句2 if (表达式) 语句;
         else 语句;
开关语句 switch (表达式)
          {
             case 值1: 语句序列1 ;break;
             case 值2: 语句序列2 ;break;
             …
             case 值n: 语句序列n;break;
             default: 语句序列n+1;
          }

（7）循环语句：

for语句        for (表达式1; 条件; 表达式2) 语句;
while语句      while (条件) 语句;
do-while语句   do {
                   语句序列;
                 } while (条件);

（8）结束语句：

函数结束语句    return 表达式;
              return;
              case或循环结束语句 break;
              异常结束语句 exit (异常代码);

（9）输入输出语句使用C++流式输入输出的形式：

输入语句   cin>>变量1>>…>>变量n;
输出语句   cout<<表达式1<<…<<表达式n;

（10）基本函数：

求最大值    Max (表达式1,...,表达式n)
求最小值    Min (表达式1,...,表达式n)

下面以复数为例，给出一个完整的抽象数据类型的定义、表示和实现。

（1）定义部分：

ADT Complex {
   数据对象：D={e1,e2|e1,e2∈R,R是实数集}
   数据关系：S={<e1,e2>|e1是复数的实部，e2 是复数的虚部}
   基本操作：
     Creat(&C,x,y)
       操作结果：构造复数C，其实部和虚部分别被赋以参数x和y的值。
     GetReal(C)
       初始条件：复数C已存在。
       操作结果：返回复数C的实部值。
     GetImag(C)
       初始条件：复数C已存在。
       操作结果：返回复数C的虚部值。
     Add(C1,C2)
       初始条件：C1，C2是复数。
       操作结果：返回两个复数C1和C2的和。
     Sub(C1,C2)
       初始条件：C1，C2是复数。
       操作结果：返回两个复数C1和C2的差。
} ADT Complex

在后面的章节中，每定义一个新的数据结构，都先用这种定义方式给出其抽象数据类型的定义，对于数据结构的表示方法，则根据不同的存储结构相应给出，同时用类C语言给出主要操作的实现方法。下面为了让读者对抽象数据类型有一个完整、正确的理解，给出复数的存储表示和相应操作的具体实现过程。

（2）表示部分：

typedef struct                  //复数类型
{
   float Realpart;              //实部
   float Imagepart;             //虚部
}Complex;

（3）实现部分：

void Create( &Complex C, float x, float y)
{ //构造一个复数
   C.Realpart=x;
   C.Imagepart=y;
}
float GetReal(Complex C)
{ //取复数C=x+yi的实部
   return C.Realpart;
}
float GetImag(Complex C)
{ //取复数C=x+yi的虚部
   return C.Imagepart;
}
Complex Add(Complex C1, Complex C2)
{ //求两个复数C1和C2的和sum
   Complex sum;
   sum.Realpart=C1.Realpart+C2.Realpart;
   sum.Imagepart=C1.Imagepart+C2.Imagepart;
   return sum;
}
Complex Sub(Complex C1, Complex C2)
{ //求两个复数C1和C2的差difference
   Complex difference;
   difference.Realpart=C1.Realpart-C2.Realpart;
   difference.Imagepart=C1.Imagepart-C2.Imagepart;
   return difference;
}

这样定义之后，就可以在主程序中通过调用Create函数构造一个复数，调用Add或Sub函数实现复数的加法或减法运算，用户可以像使用整数类型那样使用复数类型了。通过上述实例，读者可以对抽象数据类型的概念有更加深刻的理解。

上一章目录下一章