目录

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

 1、知识回顾 

（1）数据结构的研究内容

（2）概念小结

2、抽象数据类型

（1）抽象数据类型的实现

（2）抽象数据类型如何实现

（3）用C语言真正实现抽象数据类型的定义

（4）抽象数据类型举例

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

 1、知识回顾

（1）数据结构的研究内容

（2）概念小结

2、抽象数据类型

一个问题抽象为一个抽象数据类型后，仅是形式上的抽象定义，还没有达到问题解决的目的，要实现这个目标，就要把抽象的变成具体的，即抽象数据类型在计算机上实现，变为一个能用的具体的数据类型。

 ADT Circle{     数据对象：D={r,x,y|r,x,y均为实数}     数据关系：R={<r,x,y>|r是半径,<x,y>是圆心坐标}     基本操作：         Circle(&C,r,x,y)             操作结果：构造一个圆。         double Area(C)             初始条件：圆已存在。             操作结果：计算面积。         double Circumference(C)             初始条件：圆已存在。             操作结果：计算周长。         …… }ADT Circle

（1）抽象数据类型的实现

 ADT 抽象数据类型名{     Data         数据对象的定义         数据元素之间逻辑关系的定义     Operation         操作1             初始条件             操作结果描述         操作2             ……         操作n             …… }ADT 抽象数据类型名

C语言实现抽象数据类型。用已有数据类型定义描述它的存储结构；用函数定义描述它的操作。就可以在程序中使用。

（2）抽象数据类型如何实现

抽象数据类型可以通过固有的数据类型（如整型、实型、字符型等）来表示和实现。即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。

备注：在本门课程的学习过程中，我们使用类C语言（介于伪码和C语言之间）作为描述工具。

（3）用C语言真正实现抽象数据类型的定义

例如：抽象数据类型“复数”的实现。

 //抽象数据类型“复数”的实现  typedef struct{  float realpart;//实部   float imagpart;//虚部  }Complex;//定义复数抽象类型  void assign(Complex *A, float real, float imag);//赋值 void add(Complex *C, Complex A, Complex B);//A+B void minus(Complex *C, Complex A, Complex B);//A-B void multiply(Complex *C, Complex A, Complex B);//A*B void divide(Complex *C, Complex A, Complex B);//A/B float GetReal(Complex A, float *RealPart);//返回A的实部值  float GetImag(Complex A, float *ImagPart);//返回A的虚部值   void assign(Complex *A, float real, float imag){  A->realpart = real;//实部赋值   A->imagpart = imag;//虚部赋值  }//End of assign()   void add(Complex *C, Complex A, Complex B){//C=A+B   C->realpart = A.realpart + B.realpart;//实部相加   C->imagpart = A.imagpart + B.imagpart;//虚部相加  }//End of Add()   void minus(Complex *C, Complex A, Complex B){//C=A-B   C->realpart = A.realpart - B.realpart;//实部相减   C->imagpart = A.imagpart - B.imagpart;//虚部相减  }//End of minus()  void multiply(Complex *C, Complex A, Complex B){//C=A*B  C->realpart = A.realpart * B.realpart - A.imagpart * B.imagpart;//实部   C->imagpart = A.imagpart * B.realpart + A.realpart * B.imagpart;//虚部 }//End of multiply()  void divide(Complex *C, Complex A, Complex B){//C=A/B   C->realpart = (A.realpart * B.realpart + A.imagpart * B.imagpart) / (B.realpart * B.realpart + B.imagpart * B.imagpart);//实部   C->imagpart = (A.imagpart * B.realpart - A.realpart * B.imagpart) / (B.realpart * B.realpart + B.imagpart * B.imagpart);//虚部  }//End of divide()  float GetReal(Complex A, float *RealPart){//返回A的实部值   *RealPart = A.realpart;  return *RealPart; }//End of GetReal()  float GetImag(Complex A, float *ImagPart){//返回A的虚部值   *ImagPart = A.imagpart;  return *ImagPart; }//End of GetImag()

备注：Complex是我们定义的一个结构体类型。带*：指针变量，它是指向Complex类型的指针；不带*：Complex类型的普通变量。

（4）抽象数据类型举例

。

 //抽象数据类型举例 #include <stdio.h>  typedef struct{  float realpart;//实部   float imagpart;//虚部  }Complex;//定义复数抽象类型  void assign(Complex *A, float real, float imag);//赋值 void add(Complex *C, Complex A, Complex B);//A+B void minus(Complex *C, Complex A, Complex B);//A-B void multiply(Complex *C, Complex A, Complex B);//A*B void divide(Complex *C, Complex A, Complex B);//A/B float GetReal(Complex A, float *RealPart);//返回A的实部值  float GetImag(Complex A, float *ImagPart);//返回A的虚部值   void assign(Complex *A, float real, float imag){  A->realpart = real;//实部赋值   A->imagpart = imag;//虚部赋值  }//End of assign()   void add(Complex *C, Complex A, Complex B){//C=A+B   C->realpart = A.realpart + B.realpart;//实部相加   C->imagpart = A.imagpart + B.imagpart;//虚部相加  }//End of Add()   void minus(Complex *C, Complex A, Complex B){//C=A-B   C->realpart = A.realpart - B.realpart;//实部相减   C->imagpart = A.imagpart - B.imagpart;//虚部相减  }//End of minus()  void multiply(Complex *C, Complex A, Complex B){//C=A*B  C->realpart = A.realpart * B.realpart - A.imagpart * B.imagpart;//实部   C->imagpart = A.imagpart * B.realpart + A.realpart * B.imagpart;//虚部 }//End of multiply()  void divide(Complex *C, Complex A, Complex B){//C=A/B   C->realpart = (A.realpart * B.realpart + A.imagpart * B.imagpart) / (B.realpart * B.realpart + B.imagpart * B.imagpart);//实部   C->imagpart = (A.imagpart * B.realpart - A.realpart * B.imagpart) / (B.realpart * B.realpart + B.imagpart * B.imagpart);//虚部  }//End of divide()  float GetReal(Complex A, float *RealPart){//返回A的实部值   *RealPart = A.realpart;  return *RealPart; }//End of GetReal()  float GetImag(Complex A, float *ImagPart){//返回A的虚部值   *ImagPart = A.imagpart;  return *ImagPart; }//End of GetImag()  void main(){  Complex z1, z2, z3, z4, z;  float RealPart, ImagPart;  assign(z1, 8.0, 6.0);//构造复数z1   assign(z2, 4.0, 3.0);//构造复数z2   add(z1, z2, z3);//两个复数相加  multiply(z1, z2, z4);//两个复数相乘   if(divide(z4, z3, z)){//两个复数相除    GetReal(z, RealPart);   GetImag(z, ImagPart);  }//if }

 //抽象数据类型举例（具体实现）  #include <stdio.h>  typedef struct{  float realpart;//实部   float imagpart;//虚部  }Complex;//定义复数抽象类型  void assign(Complex *A, float real, float imag);//赋值 void add(Complex *C, Complex A, Complex B);//A+B void minus(Complex *C, Complex A, Complex B);//A-B void multiply(Complex *C, Complex A, Complex B);//A*B void divide(Complex *C, Complex A, Complex B);//A/B void GetReal(Complex A);//返回A的实部值  void GetImag(Complex A);//返回A的虚部值   void assign(Complex *A, float real, float imag){  A->realpart = real;//实部赋值   A->imagpart = imag;//虚部赋值  }//End of assign()   void add(Complex *C, Complex A, Complex B){//C=A+B   C->realpart = A.realpart + B.realpart;//实部相加   C->imagpart = A.imagpart + B.imagpart;//虚部相加   printf("add:realpart=%f, imagpart=%fn", C->realpart, C->imagpart); }//End of Add()   void minus(Complex *C, Complex A, Complex B){//C=A-B   C->realpart = A.realpart - B.realpart;//实部相减   C->imagpart = A.imagpart - B.imagpart;//虚部相减   printf("minus:realpart=%f, imagpart=%fn", C->realpart, C->imagpart); }//End of minus()  void multiply(Complex *C, Complex A, Complex B){//C=A*B  C->realpart = A.realpart * B.realpart - A.imagpart * B.imagpart;//实部   C->imagpart = A.imagpart * B.realpart + A.realpart * B.imagpart;//虚部   printf("multiply:realpart=%f, imagpart=%fn", C->realpart, C->imagpart); }//End of multiply()  void divide(Complex *C, Complex A, Complex B){//C=A/B   C->realpart = (A.realpart * B.realpart + A.imagpart * B.imagpart) / (B.realpart * B.realpart + B.imagpart * B.imagpart);//实部   C->imagpart = (A.imagpart * B.realpart - A.realpart * B.imagpart) / (B.realpart * B.realpart + B.imagpart * B.imagpart);//虚部   printf("divide:realpart=%f, imagpart=%fn", C->realpart, C->imagpart); }//End of divide()  void GetReal(Complex A){//返回A的实部值   printf("GetReal:realpart=%fn", A.realpart); }//End of GetReal()  void GetImag(Complex A){//返回A的虚部值   printf("GetImag:imagpart=%fn", A.imagpart); }//End of GetImag()  int main(){  Complex z1, z2, z3, z4, z;  assign(&z1, 8.0, 6.0);//构造复数z1   assign(&z2, 4.0, 3.0);//构造复数z2   add(&z3, z1, z2);//两个复数相加  multiply(&z4, z1, z2);//两个复数相乘   divide(&z, z4, z3);//两个复数相除   GetReal(z);  GetImag(z);  return 0; }