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

对于计算机科学来说，抽象（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_H typedef 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_H class 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－