什么是抽象数据类型定义举例（抽象数据类型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!
");
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 ",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
",*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!
";
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－
,免责声明：本文仅代表文章作者的个人观点，与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺，请读者仅作参考，并自行核实相关内容。
