抽象数据类型总结：复数 adt 和 FIFO 队列adt

数据结构

---

定义：抽象数据类型（abstract data type, ADT）是指”只“通过接口进行访问的数据类型。我们将那些使用ADT的程序叫做客户，将那些确定数据类型的程序叫做实现。
客户程序除了通过接口中提供的那些操作外，并不访问任何数据值。数据的表示和操作都在接口的实现里，和客户完全分离。

数据结构、数据类型和抽象数据类型

   数据结构、数据类型和抽象数据类型，这3个术语在字面上虽不同但相近，反映出它们在含义上既有区别又有联系。       

1. 数据结构

   数据结构是计算机科学与技术领域常用的术语。它用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。逻辑上的数据结构反映成分数据之间的逻辑关系，物理上的数据结构反映成分数据在计算机内的存储安排。数据结构是数据存在的形式。

2. 数据类型

   数据是按照数据结构分类的，具有相同数据结构的数据属同一类。同一类数据的全体称为数据类型。在程序设计高级语言中，数据类型用来说明一个数据在数据分类中的归属。它是数据的一种属性。这个属性限定了该数据的变化范围。为了解题的需要，根据数据结构的种类，高级语言定义了一系列的数据类型。不同的高级语言所定义的数据类型不尽相同。

3. 抽象数据类型

   抽象数据类型的含义可理解为数据类型的进一步抽象。即把数据类型和数据类型上的运算捆在一起，进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开，使它们相互独立。对于抽象数据类型的描述，除了必须描述它的数据结构外，还必须描述定义在它上面的运算（过程或函数）。抽象数据类型上定义的过程和函数以该抽象数据类型的数据所应具有的数据结构为基础。

抽象数据类型的举例：

1.复数的一级ADT

完整工程下载：传送门--vs2012 dev.

复数的一级ADT接口

句柄定义为指向结构体的一个指针，该结构体只有命名标志，没有明确定义。客户程序可以以任意方式使用这个句柄，但是不能通过改变指针指向访问结构体中的一个域，这是因为它没有这些域的任何名字。

//complex.h
typedef struct complex *Complex; //隐藏数据表示，不提供具体的说明
Complex COMPLEXinit(float , float);
float Re(Complex);
float Im(Complex
Complex COMPLEXmult(Complex, Complex);
Complex COMPLEXadd(Complex, Complex);
void showComplex(Complex );

复数的一级ADT实现

它包括了结构定义和函数实现。对象是指向结构的指针，因而我们使指针指向这个链域。

//complex.cpp
/************************************************************************/
/*                复数的一级ADT：包含结构定义和函数实现                            */
/************************************************************************/
#include "Complex.h"
#include <malloc.h>
#include <stdio.h>
struct complex
{
    float Re;
    float Im;
};
//初始化
Complex COMPLEXinit( float re, float im)
{
    Complex t = (Complex)malloc(sizeof(t));
    t->Re = re;
    t->Im = im;
    return t;
}
//取实部
float Re(Complex z)
{
    return z->Re;
}
//取虚部
float Im(Complex z)
{
    return z->Im;
}
//复数乘
Complex COMPLEXmult( Complex a, Complex b)
{
    return COMPLEXinit(Re(a) * Re(b) - Im(a) * Im(b), 
                                  Re(a) * Im(b) + Im(a) * Re(b));
}
//复数加
Complex COMPLEXadd(Complex a, Complex b)
{
    return COMPLEXinit( Re(a) + Re(b), 
                                    Im(a) + Im(b));
}
void showComplex(Complex z)
{
    printf("%3.1f + %3.1f*i\n", Re(z), Im(z));
}

客户驱动程序（测试）

//main.cpp
#include <stdio.h>
#include<stdlib.h>
#include "Complex.h"
int main(int argc, char *argv[])
{ 
    Complex c1, c2, c3, c4;
    c1 = COMPLEXinit(1, 1);
    c2 = COMPLEXinit(1, -1);
    c3 = COMPLEXmult(c1, c2);
    c4 = COMPLEXadd(c1, c2);
    showComplex(c1);
    showComplex(c2);
    showComplex(c3);
    showComplex(c4);
    system("pause");
    return 0;
}

运行结果

2. FIFO队列ADT

完整工程下载：传送门--vs2012 dev.
修改为单一对象提供FIFO队列实现（传送门）的代码，使之为对象句柄提供实现。

队列客户程序：随机把N个项赋给M个FIFO队列中的一个，然后逐个删除队列中的项

队列ADT接口

//queue.h
/************************************
队列的一级ADT接口
************************************/
typedef int Item;
typedef struct Node Node;//隐藏数据表示，使客户不能直接访问
typedef struct queue* Queue;
Node* NewNode(Item , Node* ); // Next为插入的后一节点
Queue QueueInit(int );
int QueueIsEmpty(Queue );
void QueuePut(Queue , Item );
Item QueueGet(Queue );

队列ADT实现

//queue.cpp
/*************************************************************
                        FIFO队列的ADT实现
功能：先进先出队列的链表形式实现：Init、Put、Get操作
说明：  从头部Get，从尾部Put
时间： 2015/02/09
作者： quinn
**************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include "queue.h"
struct Node //节点结构
{
    Item item;
    Node* next;
};
struct queue
{
    Node* head;
    Node* tail;
};
//新建一个节点
Node* NewNode(Item item, Node* Next) // Next为插入的后一节点
{
    Node* x = (Node*)malloc(sizeof(*x));//被插入的节点
    x->item = item;
    x->next = Next;
    return x;
}
//队列初始化
Queue QueueInit(int maxN)
{
    Queue q = (Queue)malloc(sizeof(q));
    q->head =  NULL;
    return q;
}
//判断队列是否为空
int QueueIsEmpty(Queue q)
{
    return (q->head == NULL);
}
//put操作
void QueuePut(Queue q, Item item)
{
    if(QueueIsEmpty(q))
    {
        q->head = (q->tail = NewNode(item, q->head));
    }
    else
    {
        q->tail->next = NewNode(item, q->tail->next);
        q->tail =q->tail->next;
    }
    printf("Put: %d\n", item);
}
//get操作
Item QueueGet(Queue q)
{
    if(q->head == NULL)
    {
        printf("序列为空！\n");
        return -1;
    }
    Item firstItem = q->head->item;//序列的头元素
    Node* tmpNode = q->head;
    q->head = q->head->next;
    free(tmpNode);
    return firstItem;
}

客户驱动程序

//main.cpp
/*********************************************
        队列客户驱动程序
功能：随机把N个项赋给M个FIFO队列中的一个，然后逐个删除队列中的项
其他：使用对象句柄带有ADT对象的复合数据结构；每个队列都对应自己的head和tail
时间： 2015/02/09
作者： quinn
*********************************************/
#include "queue.h"
#include <stdlib.h>
#include <stdio.h>
#define M 10
int main(int argc, char *argv[])
{
    int N = atoi(argv[1]);
    Queue q[M];
    //初始化
    for (int i = 0; i < M; i++)
    {
        q[i] = QueueInit(N);
    }
    //put
    for (int j = 0; j < N; j++)
    {
        QueuePut(q[rand() % M], j); 
    }
    //get
    for (int i = 0; i < M; i++)
    {
        while (!QueueIsEmpty(q[i]))
        {
            printf("%3d", QueueGet(q[i]));
        }
        printf("\n");
    }
    system("pause");
    return 0;
}

运行结果

带参数 100 （N = 100项）

总结

ADT接口定义用户和实现的一种协议，为他们直接相互通信提供了精确手段。我们可以更改接口的实现方式，但客户程序不受影响。

参考资料：
1. http://jsjedu.hxu.edu.cn/dxjsjjc/kcnr/wlkj/06software/detail/6-3-2.htm#
2. 《算法：C语言实现》 第4章 抽象数据类型