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

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

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

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

一般来说,所有高级编程语言也都提供抽象(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-

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。