面向对象编程中的抽象数据类型是什么？

Question

面向对象编程中的抽象数据类型是什么？我已经浏览了这个主题的维基,但我仍然不清楚它.有人可以澄清吗？

Answer 1

一个抽象类是一个泛化的概念.它是一个你发明的类,它只用作继承的基类,但不用于实例化对象.

和抽象数据类型 (ADT)不一定是面向对象的概念.在没有描述实现的情况下,在功能方面描述例如Stack和Queue的概念是一个较旧的术语.

Answer 2

" 抽象数据类型 "和" 抽象类 " 之间存在差异.

一个抽象类是一个可能没有定义为所有它定义的方法.因此,您无法直接实例化抽象类.您必须创建一个子类,然后实例化它.

一个抽象数据类型是一个模型的某一种数据结构的例如的堆栈.Stack具有push()和pop()操作,并且具有明确定义的行为.

抽象数据类型(ADT)本身是指该模型,而不是任何特定编程语言或范例中的任何特定实现.您可以使用面向对象的语言实现Stack,但您也可以使用函数式编程语言实现它.

ADT允许讨论堆栈,队列等的属性,这些属性适用于ADT的所有正确实现.

Answer 3

嗯,这都是关于抽象的.抽象在编程中特别有用.主要优点是隐藏实现细节的能力.您将其隐藏在一个模块(所谓的"服务器模块")中,并为其他模块(所谓的"客户端模块")提供一些公共接口.现在我们有三种不同的可能性:

服务器模块本身可以提供抽象数据结构(ADS).

在这种情况下,它包含ADS实体本身.公共接口由一些过程(可能还有一些常量)组成.

服务器模块的接口(stack_ads.h):

#ifndef STACK_ADS
#define STACK_ADS

const int capacity = 10;

void clear();
int size();
int pop();
void push(int value);

#endif STACK_ADS

实现(stack_ads.cpp):

#include "stack_ads.h"

int items[capacity];
int top = -1;

void clear()
{
  top = -1;
}

int size()
{
  return top + 1;
}

int pop()
{
  top -= 1;
  return items[top + 1];
}

void push(int value)
{
  top += 1;
  items[top] = value;
}

在客户端模块(main.cpp)中,我们导入服务器模块并直接使用数据结构.

#include <iostream>
#include "stack_ads.h"

int main (int argc, char* const argv[]) 
{
  push(1);
  push(2);
  push(3);

  std::cout << pop() << std::endl;
  std::cout << pop() << std::endl;
  std::cout << pop() << std::endl;

  return 0;
}

服务器模块可以以struct/record的形式提供抽象数据类型(ADT).

在客户端模块中,我们可以将变量声明为该类型.由于模块可以自由地将多个变量声明为导出类型,因此它可以具有多个数据结构.每个抽象数据结构都是抽象数据类型的变量.

接口(stack_adt.h):

#ifndef STACK_ADT
#define STACK_ADT

const int capacity = 10;

typedef struct
{
  int items[capacity];
  int top;
} StackADT;

void clear(StackADT* stack);
int size(StackADT* stack);
int pop(StackADT* stack);
void push(StackADT* stack, int value);  

#endif STACK_ADT

实现(stack_adt.cpp):

#include "stack_adt.h"

void clear(StackADT* stack)
{
  stack->top = -1;
}

int size(StackADT* stack)
{
  return stack->top + 1;
}

int pop(StackADT* stack)
{
  stack->top -= 1;
  return stack->items[stack->top + 1];
}

void push(StackADT* stack, int value)
{
  stack->top += 1;
  stack->items[stack->top] = value;
}

客户端模块:

#include <iostream>
#include "stack_adt.h"

int main (int argc, char* const argv[]) 
{
  StackADT stack1;
  StackADT stack2;
  stack1.top = -1;
  stack2.top = -1;

  push(&stack1, 1);
  push(&stack1, 2);
  push(&stack1, 3);

  std::cout << pop(&stack1) << std::endl;
  std::cout << pop(&stack1) << std::endl;
  std::cout << pop(&stack1) << std::endl;

  push(&stack2, 10);
  push(&stack2, 20);
  push(&stack2, 30);

  std::cout << pop(&stack2) << std::endl;
  std::cout << pop(&stack2) << std::endl;
  std::cout << pop(&stack2) << std::endl;

  return 0;
}

最后,服务器模块可以以类的形式提供抽象数据类型(ADT).

如果我们的语言支持OOP,我们可以通过类来描述ADT.再次在客户端模块中,我们可以将变量声明为该类型.在面向对象的术语中,类型称为类,具有该类型的变量称为对象.

服务器模块接口(Stack.h):

#ifndef STACK
#define STACK

const int capacity = 10;

class Stack
{
public:
  Stack();
  void clear();
  int size();
  int pop();
  void push(int value);
private:
  int items[capacity];
  int top;
};

#endif STACK

实现(Stack.cpp):

#include "Stack.h"

Stack::Stack()
{
  this->top = -1;
}

void Stack::clear()
{
  this->top = -1;
}

int Stack::size()
{
  return this->top + 1;
}

int Stack::pop()
{
  this->top -= 1;
  return this->items[this->top + 1];
}

void Stack::push(int value)
{
  this->top += 1;
  this->items[this->top] = value;
}

最后两个选项之间的差异是:

• 上面提到的术语(类型< - >类,变量< - >对象).
• 在非类ADT中,每个过程的形式参数列表必须包含Stack类型的变量s.在堆栈类中,数据结构s的规范不包含在过程名称后面的其他形式参数中,而是单独包含在过程名称之前的括号中.在过程名称之前使用Smalltalk术语形式参数称为接收器.
• 程序的位置.在非类ADT中,过程位于Stack结构之外.在课堂上,程序位于班级内.在面向对象的术语中,具有接收器并因此包含在类类型中的过程称为方法.

客户代码:

#include <iostream>
#include "stack.h"

int main (int argc, char* const argv[]) 
{
  Stack stack1;
  Stack stack2;

  stack1.push(1);
  stack1.push(2);
  stack1.push(3);

  std::cout << stack1.pop() << std::endl;
  std::cout << stack1.pop() << std::endl;
  std::cout << stack1.pop() << std::endl;

  stack2.push(10);
  stack2.push(20);
  stack2.push(30);

  std::cout << stack2.pop() << std::endl;
  std::cout << stack2.pop() << std::endl;
  std::cout << stack2.pop() << std::endl;

  return 0;
}

Answer 4

抽象数据类型(ADT)是一种数据的数学模型.它描述了可以对数据执行的操作以及使用公式对这些操作的数学定义.

例如,您可以使用pop(),push(),top()等操作完美抽象地模拟数字堆栈的行为,也可以使用表示空堆栈的常量符号.

例如,这里有一些方程式可以构成数字堆栈定义的一部分:

pop(empty) = empty  // silently ignores popping an empty stack
pop(push(N,S)) = S  // i.e. pop removes the top element of push(N,S)
top(push(N,S)) = N  // return topmost element of the stack without changing the stack

抽象数据类型与对象模型中的类完全不同 - 尽管它们有一些相似之处.

以下是重要概念的名称:初始代数语义,同构,商,同余

抽象数据类型的要点是使用方程式和一些花哨的数学来理解整类等价类型表示的行为,这些数学表明每个实现都是"同构的" - 即两个实现完全等效,只要可观察行为是关心.

维基百科的相关内容非常好:http://en.wikipedia.org/wiki/Abstract_data_type

以下是一些很好的(但非常理论化的)课程笔记,其中列出了ADT的内容http://www-compsci.swan.ac.uk/~csulrich/ftp/adt/adt.pdf

虽然在某些面向对象的编程语言中表面上类似于"类"的概念,但"类"不是ADT,而是可以使用类来实现特定的ADT.

一般来说,ADT概念可能比面向对象编程更适用于函数式编程,因为并非所有面向对象的编程语言都有类,而ADT式思维会产生效率较低的OO设计.

• 这篇论文用OO语言展示了ADT思维方面的问题:http://portal.acm.org/citation.cfm？id = 74885
• 基本上,本文表明,用于实现ADT的"类"最终会覆盖许多微小的方法(看起来像ADT方程的基础),而不是具有一些强大的,高抽象的方法.

Answer 5

定义:

粗略地说,抽象数据类型(ADT)是一种查看数据结构的方式:关注它的作用并忽略它的工作方式.

抽象数据类型主要由它们的接口定义:可以对它们执行的允许操作.用于实现它们的底层机制通常对其用户不可见.

例子:

Stack,Queue并且PriorityQueue是ADT的一些示例,它们比数组,链表和许多其他数据存储结构更抽象.

例如,堆栈的底层机制可以是Array或者它可以是LinkedList.a的底层机制PriorityQueue可以是Array一种叫做a的特殊树Heap.

码:

下面是一个PriorityQueue使用Heap实现的抽象数据类型的Java示例:

class Heap {
  private Node heapArray[];
  public void insert(Node node) {...}
  public Node remove() {...}
}

class PriorityQueue {
  private Heap heap;
  public void insert(Node node) { 
    heap.insert(node);
  }
  public Node remove() {
    return heap.remove();
  }
}

在这里,您可以看到PriorityQueue类的方法只是围绕底层Heap类的方法.类似地,您可以使用Array而不是Heap实现相同的功能,即使Array您需要更多代码来处理插入和删除等操作.这个例子应该在概念上清楚地表明a PriorityQueue是一个可以使用堆,数组等以各种方式实现的ADT.

虽然ADT在面向对象编程(OOP)语言中更有意义,但它们不仅限于OOP语言,也可以使用非OOP语言创建.

Answer 6

简而言之：抽象意味着你不能从定义的类中创建对象。例如：如果您有形状、正方形和矩形类，但您不想从形状定义任何对象，因此您将其标记为抽象...

之后，如果用户尝试从形状定义一个新对象，他将收到编译器错误。