什么是抽象数据类型定义举例抽象数据类型ADT与接口

导读对于计算机科学来说，抽象（abstractions）是一个很重要的思维概念，与之相关的概念还有模块、分层等，如对一个复杂系统的模块化和层层抽象。如下图所示，....

对于计算机科学来说，抽象（abstractions）是一个很重要的思维概念，与之相关的概念还有模块、分层等，如对一个复杂系统的模块化和层层抽象。

如下图所示，计算机体系的分层结构，上层便是下层的抽象。

一般来说，所有高级编程语言也都提供抽象（abstractions）机制。某一功能或某一问题解决方案具体过程的描述，可以抽象为函数（算法也可以用函数来描述）。

对某类实体，可以抽象出共同的关键性的特性描述（数据）和行为（或功能，用函数或成员函数描述），在编程语言中称为抽象数据类型（ADT，Abstract Data Type）。

C和C 都可以实现一种抽象数据类型。

在C中，ADT的数据可以抽象为结构体（struct），如描述栈的struct：struct Statck stack。相应的，ADT的行为可以抽象为一个函数集，这些函数是对数据stack的处理或操作，这些函数通常以stack或其指针做为函数参数。

在C 中，ADT可以用类（class)来描述，ADT的数据及其对该数据的处理（成员函数）都被封装到一个类中。

通常，一种抽象数据类型可以用一个模块（mudole）来描述。在C和C 中，文件也是一种实现模块的方式之一。可通过头文件（.h）和源文件（.c或.cpp）实现模块化，实现接口（interface）与实现（implementation）的分离和封装。

C的头文件：可以包含结构体 函数原型声明；

C的源文件：可以包含各个函数实现；

C的头文件：可以包含类定义；

C的源文件：可以包含类的各个成员的函数实现；

更进一步，实现文件可以封装为库（函数库或类库，lib或dll）。

对于封装后的ADT，ADT的使用者（client）无须使用时无须关注ADT的实现文件或库文件（.lib或.dll），只需引入和对照接口文件（头文件）即可使用ADT。同时，ADT实现者（implementor）随时可以修改实现文件（不修改接口文件），不会影响client使用ADT的代码，这也就是所谓的实现隐藏，这也是封装的一个重要特征。

下面以实现一个链栈为例为说明C和C 在抽象数据类型方面的异同：

1 C栈实现抽象数据类型（ADT）

1.1 头文件（充当接口）

// Stack.h for interface#ifndef STACK_H#define STACK_Htypedef struct Link { // 链表节点 void* data; Link* next;}Link;typedef struct tagStack { // 链栈 Link* top; int size;}*Stack;void initLink(Link* link, void* dat, Link* nxt);void init(Stack stack);void push(Stack stack,void* dat);void* peek(Stack stack);void* pop(Stack stack);#endif

1.2 实现文件

// Stack.cpp// Includes definitions of member functions#include "Stack.h"#include <stdio.h>#include <stdlib.h>void initLink(Link* link, void* dat, Link* nxt){ link->data = dat; link->next = nxt;}void init(Stack stack) { stack->top = NULL; stack->size = 0;}void push(Stack stack,void* dat) { Link* newLink = (Link*)malloc(sizeof(Link)); initLink(newLink,dat,stack->top); stack->top = newLink; stack->size ;}void* peek(Stack stack) { if(stack->top==NULL) { printf("Stack empty!\n"); exit(0); } return stack->top->data;}void* pop(Stack stack) { if(stack->top == NULL) return NULL; void* result = stack->top->data; Link* oldtop = stack->top; stack->top = stack->top->next; free(oldtop); stack->size--; printf("%d\t",stack->size); return result;}

1.3 测试文件（充当client）

// StackTest.cpp// Test of nested linked list#include "Stack.h"#include <stdio.h>#include <stdlib.h>int main() { struct tagStack nums; init(&nums); for(int i=1; i<11; i ) { void *ptr = malloc(sizeof(double)); *(double*)ptr = i*0.5; push(&nums,ptr); } // Pop the lines from the Stack and print them: double * ptr; while(nums.top != NULL) { ptr = (double*)pop(&nums); printf("%lf\n",*ptr); free(ptr); } while(1); // for test return 0;}

2 C 实现栈抽象数据类型

2.1 头文件（充当接口）

// Stack.h for interface#ifndef STACK_H#define STACK_Hclass Stack { struct Link { // void* data; Link* next; Link(void* dat, Link* nxt); }* top;public: Stack(); void push(void* dat); void* peek(); void* pop();};#endif

2.2 实现文件

// Stack.cpp// Includes definitions of member functions#include "Stack.h"#include <iostream>Stack::Link::Link(void* dat, Link* nxt) { data = dat; next = nxt;}Stack::Stack() { top = 0; }void Stack::push(void* dat) { Link* newLink = new Link(dat, top); top = newLink;}void* Stack::peek() { if(top==0) { std::cout<<"Stack empty!\n"; exit(0); } return top->data;}void* Stack::pop() { if(top == 0) return 0; void* result = top->data; Link* oldtop = top; top = top->next; delete oldtop; return result;}

2.3 测试文件（充当client）

// StackTest.cpp// Test of nested linked list#include "Stack.h"#include<fstream>#include<iostream>#include<string>using namespace std;int main() { Stack nums; for(int i=1; i<11; i ) nums.push(new int(i)); // Pop the lines from the Stack and print them: int * ptr; while((ptr = (int*)nums.pop()) != NULL) { cout << *ptr << endl; delete ptr; } while(1); // for test return 0;}

－End－