Abstract Data Types………..

When designing Data Structures and Algorithms it is desirable to avoid makingdecisions based on the accident of how you first sketch out a piece of code. Alldesign should be motivated by the explicit needs of the application. The idea ofan Abstract Data Type (ADT) is to support this (the idea is generally consideredgood for program maintainablity as well, but that is no great concern for thisparticular course). The specification of an ADT is a list of the operations thatmay be performed on it, together with the identities that they satisfy. This specificationdoes not show how to implement anything in terms of any simpler datatypes. The user of an ADT is expected to view this specification as the completedescription of how the data type and its associated functions will behave — noother way of interrogating or modifying data is available, and the response to anycircumstances not covered explicitly in the specification is deemed undefined.

To help make this clearer, here is a specification for an Abstract Data Type called STACK:

make empty stack(): manufactures an empty stack.

is empty stack(s): s is a stack. Returns TRUE if and only if it is empty.

push(x, s): x is an integer, s is a stack. Returns a non-empty stack which canbe used with top and pop. is empty stack(push(x, s))=FALSE.

top(s): s is a non-empty stack; returns an integer. top(push(x, s))= x.

pop(s): s is a non-empty stack; returns a stack. pop(push(x, s))=s.

SHARE THE KNOWLEDGE


Advertisements

About Dinesh

I am engineering student........ I am selected in Microsoft Student Partner as MSP............

Posted on January 8, 2011, in Knowledge. Bookmark the permalink. 6 Comments.

  1. data structure concepts was totaly clear… bt i suggest u to give informatin about binary trees….

    • pls give me…………

      • check out the wikipedia…

      • In computer science, a binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as “left” and “right”. Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the “root” node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left or right child.

        Binary trees are used to implement binary search trees and binary heaps.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: