What is an abstract data type in object oriented programming?
What is an abstract data type in object oriented开发者_JAVA百科 programming? I've gone through the wiki for this topic, but I am still unclear about it. Could someone clarify?
An abstract class is a generalization concept. It is a class you invent to only use as a base class for inheritance but not to instantiate objects from.
And abstract datatype (ADT) is not necessarily an OOP concept. It is an older term to describe the concepts of for example Stack and Queue in terms of their functionality, without describing the implementation.
There is a difference between an "abstract data type" and an "abstract class".
An abstract class is one that may not have definitions for all the methods it defines. You therefore cannot directly instantiate an abstract class. You have to create a subclass and then instantiate that.
An abstract data type is a model of a certain kind of data structure e.g. a Stack. A Stack has push() and pop() operations and that have well-defined behaviour.
The abstract data type (ADT) itself refers to this model, not any particular implementation in any particular programming language or paradigm. You could implement a Stack in an object-oriented language, but you could also implement it in a functional programming language.
ADTs allow discussion about the properties of Stacks, Queues etc that hold for all correct implementations of the ADT.
Well, it's all about abstraction. Abstraction is particularly useful in programming. The main advantage is ability to hide realization details. You hide it inside one modules (so-called "server modules") and provide some public interface for other modules (so-called "client modules"). And now we have three different possibilities:
Server module can supply an abstract data structure (ADS) itself.
In that case it contains ADS entity itself. The public interface consists of some procedures (and maybe some constants).
Interface of server module (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
Implementation (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;
}
In the client module (main.cpp) we import server module and use data structure directly.
#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;
}
Server module can supply an abstract data type (ADT) in the form of struct/record.
In client module we can declare variables to be of that type. Because a module is free to declare more than one variable to be of the exported type, it can have more than one data structure. Each abstract data structure is variable of abstract data type.
Interface (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
Implementation (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;
}
Client module:
#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;
}
Finally the server module can supply an abstract data type (ADT) in the form of class.
If our language support OOP we can describe ADT by means of classes. And once again in client module we can declare variables to be of that type. In object-oriented terminology, the type is called a class, and the variable with that type is called an object.
Server module interface (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
Implementation (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;
}
The differences between two last options are:
- Terminological mentioned above (type <-> class, variable <-> object).
- In the non-class ADT, the formal parameter list of every procedure must include a variable s of type Stack. In the stack class, the specification of the data structure s is not included with the other formal parameters following the name of the procedure, but stands alone enclosed in parentheses before the name of the procedure. Using Smalltalk terminology formal parameter before the procedure name is called the receiver.
- The location of the procedures. In the non-class ADT, the procedures are located outside the Stack struct. In the class, the procedures are located within the class. In object-oriented terminology, procedures that have receivers, and are therefore contained within a class type, are called methods.
Client code:
#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;
}
An Abstract Data Type (ADT) is a mathematical model of a type of data. It describes operations that can be performed on the data and the mathematical definition of those operations using equations.
For example, you can model the behaviour of a stack of numbers, perfectly abstractly using operations such as pop(), push(), top() and maybe a constant symbol representing the empty stack.
For example here are some equations that could form part of the definition of a stack of numbers:
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
An abstract data type isn't at all the same thing as a class in an object model - although they bare some similarities.
Here are the names of the important concepts: initial algebra semantics, isomorphism, quotients, congruences
The point of an abstract data type is to understand the behaviour of a whole class of equivalent type representations using equations and some fancy mathematics that demonstrates that each implementation is "isomorphic" - i.e. that both implementations are exactly equivalent as far as the observable behaviour is concerned.
The wikipedia entry on this is pretty good: http://en.wikipedia.org/wiki/Abstract_data_type
Here are some good (but very theoretical) course notes that pin down what an ADT is http://www-compsci.swan.ac.uk/~csulrich/ftp/adt/adt.pdf
Although superficially similar to the concept of a "class" in some object-oriented programming languages, a "class" is not an ADT, but a class can be used to implement a specific ADT.
In general the ADT concept is probably more applicable to functional programming than object-oriented programming because not all object-oriented programming languages have classes and ADT-style thinking produces less effective OO designs.
- Here's a paper that demonstrates the problems of thinking in terms of ADTs in an OO language: http://portal.acm.org/citation.cfm?id=74885
- Basically the paper shows that the "class" that you use to implement an ADT ends up covered with lots of tiny little methods (that look like the basis of ADT equations) rather than having a few powerful, high-abstraction methods.
Definition:
Roughly speaking, Abstract Data Type (ADT) is a way of looking at a data structure: focusing on what it does and ignoring how it does its job.
Abstract data types are defined primarily by their interface: the permissible operations that can be carried out on them. The underlying mechanism used to implement them is typically not visible to their user.
Examples:
Stack, Queue and PriorityQueue are some of the examples of the ADTs, they are more abstract than say arrays, linked lists and many other data storage structures.
For example, the underlying mechanism for a stack, can be an Array or it can be a LinkedList. The underlying mechanism for a PriorityQueue can be an Array or a special kind of tree called a Heap.
Code:
Here is a Java example of the abstract data type called PriorityQueue, implemented using the Heap:
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();
}
}
Here you can see that the methods for the PriorityQueue class are simply wrapped around the methods for the underlying Heap class. Similarly you can use Array instead of Heap to implement the same functionality, even though in case of Array you'll need more code to take care of operations like insert and remove. This example should make it conceptually clear that a PriorityQueue is an ADT that can be implemented in a variety of ways, using heap, arrays and so on.
Although, ADTs make more sense in object oriented programming (OOP) languages, they are not limited to only OOP languages and can also be created using non-OOP languages.
In the school they taught me that an ADT is just a group which contains a collection of data, and a set of operations that can be taken over this data. It just refers to the idea, and is not related with any ,language, implementation neither paradigm.
Updated:
so re-reading the question, and accordingly to mi definition, an abstract data type in OOP should be a class abstraction, inherited or not, because it contains data (properties, fields, etc) and operations (methods).
regards
Abstract is most fundamental and generalized concept in a programming and real life.
What is an abstract data type in object oriented programming?
ADT is a container which holds different types of objects with specifications. logical representation(i.e an interface or protocol) of the data and the operations to manipulate the component elements of the data.
Examples of ADT: List, Map, Set, Stack, Queue, Tree, Graph.
Data structures can implement one or more particular abstract data types (ADT). In java for example ArrayList, LinkedList, Stack and Vector are data structures implementation(classes) of List.
Stack examples in real life:
- When a person wear bangles the last bangle worn is the first one to be removed and the first bangle would be the last to be removed. This follows last in first out (LIFO) principle of stack.
- In a stack of plates, once can take out the plate from top or can keep plate at the top. The plate that was placed first would be the last to take out. This follows the LIFO principle of stack.
- Batteries in the flashlight :- You cant remove the second battery unless you remove the last in. So the battery that was put in first would be the last one to take out. This follows the LIFO principle of stack.
- Clothes in the trunk
queue examples in real life
- A queue of people at ticket-window: The person who comes first gets the ticket first. The person who is coming last is getting the tickets in last. Therefore, it follows first-in-first-out (FIFO) strategy of queue.
- Vehicles on toll-tax bridge: The vehicle that comes first to the toll tax booth leaves the booth first. The vehicle that comes last leaves last. Therefore, it follows first-in-first-out (FIFO) strategy of queue.
- Luggage checking machine: Luggage checking machine checks the luggage first that comes first. Therefore, it follows FIFO principle of queue.
- Patients waiting outside the doctor's clinic: The patient who comes first visits the doctor first, and the patient who comes last visits the doctor last. Therefore, it follows the first-in-first-out (FIFO) strategy of queue.
The above examples collected from Source1 and Source2
Take one step back from the code:
What does abstract mean? Abstract
The gist of it is "not real, but capturing a property of real things"
You need to know this for OOP because you will be designing object universes, which requires you to think about how those objects are related.
Abstraction allows you to group some of those objects, thus organizing
1) Your thinking process 2) Your code
I had the same problem until last week.
An abstract class is something that is common or something in general. You can use that class to mould it and extend it in anyway you like.
I can give you a practical example here
Take a class called animal. And it contains functions like eat, sound, move which is general that all animals do. You can extend that class to get specific like cats, dogs etc.
eg.
abstract class animal {
abstract protected function eat();
abstract protected function sound();
}
class dogs extends animal
{
protected function eat() {
return "meat";
}
public function sound() {
return "bow wow";
}
}
hope my answer made sense to you
classes uses the concept of data abstraction , known as absract data type .
abstract data type is an older term to describe the concepts of stack and queues in terms of their functionality without describing their implementation .
Abstract Data Type (ADT) is a mathematical model with a collection of operations defined on that model.
Also, ADT is a data type whose behavior is defined by set of values and set of operations.
Shortly: abstract means that you can't make objects from the defined class. ex: if you have shape,square and rectangle classes, but you don't want to define any objects from shape so you will mark it as abstract...
after that if the user try to define a new object from shape, he will got compiler error..
This is from Code Complete -Quote: Abstract data types form the foundation for the concept of classes. In lanuages that support classes, you can implement each abstract data type in its own class. Classes usually involve the additional concepts of inheritance and polymorphism. One way of thinking of a class is as an abstract data type plus inheritance and polymorphism.
So in my opinion, Abstract data type in OO means abstract class.
What is an abstract data type in object oriented programming?
A Class/Abstract data type is a group of properties, and functions (for accessing data) of anything which we may want to deal with while solving some problem in an object oriented way.
What is an object?
Object is an interface to a Class/Abstract data type through which we can access its properties and functions. Objects have memories associated with them used for storing data.
An ADT defines a set of data values and a set of operations on these values.
From this post:
ADT is a set of objects and operations, no where in an ADT’s definitions is there any mention of how the set of operations is implemented. Programmers who use collections only need to know how to instantiate and access data in some pre-determined manner, without concerns for the details of the collections implementations. In other words, from a user’s perspective, a collection is an abstraction, and for this reason, in computer science, some collections are referred to as abstract data types (ADTs). The user is only concern with learning its interface, or the set of operations its performs.
Object such as lists, sets and graphs along with their operations can be viewed as abstract data types. ADTs are basically data types that hides its implementation details. Any part of a program that needs to perform an operation on ADT can do so by merely changing the routines that performs the ADT operations. The program that use them (ADT) will not necessarily need to know which implementation was used
ADT is a kind of data structure. Instead of describing the structure of data, it describes the operation on the data.
For example, what is a stack? Maybe a search tree or some linear data structure, but the user doesn't care. The user just cares about "last in first out" (LIFO).
It is just like an interface. Abstract data type in a class is just used to define something i.e. Without body/implementation such as abstract methods. The body will be added where that class will be inherited. The difference between interface and Abstract class is that we can not add a method with body in interface where as in abstract class, we can add methods/variables with body/value or make it abstract(i.e. Define there and implement where it is overrided).
An abstract class does not form a concrete object in the real world unlike pure implementation classes. Abstract as the name suggestes they hold/define common behaviours of related objects that need to be reused/defined independantly in all related objects.
Take an example of Birds. If you are writing a progrm that will have something to do with the birds, then you'll first have an abstract base class as Bird and each bird deriving from the abstract base class Bird. Do note that abstract class BIRD does not represent a concrete real world object but a type of related objects that is birds!
Lets start with the class-diagram and then some code.
alt text http://ruchitsurati.net/files/birds.png
public abstract class Bird
{
protected string Name = string.Empty;
public Bird(string name)
{
this.Name = name;
}
public virtual void Fly()
{
Console.WriteLine(string.Format("{0} is flying.", this.Name));
}
public virtual void Run()
{
Console.WriteLine(string.Format("{0} cannot run.", this.Name));
}
}
public class Parrot : Bird
{
public Parrot() : base("parrot") { }
}
public class Sparrow : Bird
{
public Sparrow() : base("sparrow") { }
}
public class Penguin : Bird
{
public Penguin() : base("penguin") { }
public override void Fly()
{
Console.WriteLine(string.Format("{0} cannot fly. Some birds do not fly.", this.Name));
}
public override void Run()
{
Console.WriteLine(string.Format("{0} is running. Some birds do run.", this.Name));
}
}
class Program
{
static void Main(string[] args)
{
Parrot p = new Parrot();
Sparrow s = new Sparrow();
Penguin pe = new Penguin();
List<Bird> birds = new List<Bird>();
birds.Add(p);
birds.Add(s);
birds.Add(pe);
foreach (Bird bird in birds)
{
bird.Fly();
bird.Run();
}
Console.ReadLine();
}
}
Abstract type means whose objects does not exist in real world since it does not have physical entity.
It acts as a base class for concrete class which has physical existance.
e.g.
Shape is an abstract class whereas circle,rectangle are concrete classes.
加载中,请稍侯......
精彩评论