Abstract data type general provisions about abstract data. Abstract classes and class members
Developing abstract models for data and ways to process that data is essential component in the process of solving problems using a computer. We see examples of this both at a low level in everyday programming (for example, when using arrays and linked lists, discussed in), and at a high level when solving applied problems(as when solving the connectivity problem using the join-search forest in the "Introduction"). This lecture discusses abstract data types (hereinafter referred to as ADT), which allow you to create programs using high-level abstractions. Abstract data types allow the abstract (conceptual) transformations that programs perform on data to be separated from any concrete representation of the data structure and any concrete implementation of the algorithm.
All computing systems based on levels of abstraction: certain physical properties of silicon and other materials allow the adoption of an abstract model of a bit that can take binary values 0-1; then an abstract model of the machine is built on the dynamic properties of the values of a certain set of bits; further, based on the principle of operation of the machine under program control on machine language an abstract model of a programming language is built; and finally it is built abstract concept algorithm, implemented as a program in C++. Abstract data types make it possible to continue this process further and develop abstract mechanisms for certain computing tasks at a higher level than is provided by the C++ system, develop abstract mechanisms oriented to specific applications and suitable for solving problems in numerous application areas, as well as creating abstract mechanisms for more high level, which use these basic designs. Abstract data types provide us with an infinitely expandable set of tools for solving more and more new problems.
On the one hand, the use of abstract constructions frees you from worries about their detailed implementation; on the other hand, when performance program is important, you need to know the costs of performing basic operations. We use a lot of basic abstractions built into hardware computer and serving as the basis for machine instructions; implement other abstractions in software; and use additional abstractions provided by previously written system software. High-level abstract constructs are often created based on more simple designs. The same basic principle applies at all levels: find the most important operations in programs and the most important characteristics of data, and then precisely define both at the abstract level and design efficient concrete mechanisms for implementing them. In this lecture we will look at many examples of the application of this principle.
Developing a new level of abstraction will require (1) defining the abstract objects that must be manipulated and the operations that must be performed on them; (2) represent the data in some data structure and implement the operations; (3) and (most importantly) ensure that these objects are convenient to use for solving applied problems. These points also apply to simple data types, so the basic mechanisms for supporting data types that were discussed in "Elementary Data Structures" can be adapted for our purposes. However, C++ offers an important extension to the structure mechanism called class. Classes are extremely useful in creating layers of abstraction and are therefore considered the primary tool used for this purpose in the remainder of the book.
Definition 4.1. Abstract type data type (ATD) is a data type (a set of values and a set of operations on these values) that is accessed only through an interface. A program that uses an ADT will be called a client, and a program containing a specification of this data type will be called an implementation.
It is the word that only makes the data type abstract: in the case of an ADT, client programs do not have access to the data values in any way other than the operations described in the interface. The representation of this data and the functions that implement these operations are in the implementation and are completely separated by the interface from the client. We say that an interface is opaque: the client cannot see the implementation through the interface.
In C++ programs this distinction is usually made a little more clearly, since it is easiest to create an interface by including data presentation, but specifying that client programs are not allowed to directly access the data. In other words, client program developers can know data presentation, but cannot use it in any way.
As an example, consider the data type interface for points (program 3.3) from section 3.1 “Elementary data structures”. This interface explicitly declares that points are represented as structures consisting of a pair of floating-point numbers, denoted x and y. This use of data types is common in large systems software: We develop a set of data representation conventions (and also define a number of associated operations) and make these rules available through the interface so that they can be used by client programs included in the big system. The data type ensures that all parts of the system are consistent in representing the underlying system-wide data structures. No matter how good this strategy is, it has one flaw: if you need to change data presentation, then you will need to change all client programs. Program 3.3 again gives us a simple example: One of the reasons for designing this data type is to make it easier for client programs to work with points, and we expect clients to have access to individual point coordinates when needed. But we can't move to a different data representation (say, polar coordinates, or 3D coordinates, or even different data types for individual coordinates) without changing all the client programs.
In contrast, Program 4.1 contains an implementation of an abstract data type corresponding to the data type in Program 3.3, but using a C++ language class that immediately defines both the data and its associated operations. Program 4.2 is client program, working with this data type. These two programs perform the same calculations as programs 3.3 and 3.8. They illustrate a number of basic properties of classes that we will now look at.
When we write a definition like int i in a program, we are telling the system to reserve an area of memory for the (built-in) data. type int, which can be addressed by the name i. In the C++ language, there is a term for such entities as object. When a program writes a definition such as POINT p, it is said to create an object of class POINT that can be referred to by the name p. In our example, each object contains two data elements, named x and y. As with structures, they can be referred to by names like p.y.
The data members x and y are called data members of the class. The class may also define member functions that implement operations associated with this data type. For example, the class defined in Program 4.1 has two member functions named POINT and distance.
Client programs, such as Program 4.2, can call the member functions associated with an object by specifying their names in the same way as the names of the data contained in a struct. For example, the expression p.distance(q) calculates the distance between points p and q (the same distance should be returned by calling q.distance(p) ). The POINT() function, the first function in Program 4.1, is a special member function called a constructor: it has the same name as a class, and is called when you want to create an object of that class.
Program 4.1. Implementation of the POINT class
This class defines a data type that consists of a set of values that are "floating-point pairs" (assumed to be interpreted as points on the Cartesian plane), as well as two member functions defined for all instances of the POINT class: the function POINT() , which is a constructor that initializes coordinates with random values between 0 and 1, and a function distance(POINT) , which calculates the distance to another point. Data presentation is private and can only be accessed or modified by member functions. The member functions themselves are public and accessible to any client. The code can be saved, for example, in a file called POINT.cxx.
#include
Program 4.2. Client program for the POINT class (finding the nearest point)
This version of the 3.8 program is a client that uses the POINT ADT defined in the 4.3 program. The new operation creates an array of POINT objects (by calling the POINT() constructor to initialize each object with random coordinate values). The expression a[i].distance(a[j]) calls the distance member function on object a[i] with argument a[j] .
#include
Defining POINT p in the client program allocates a region of memory for the new object and then (using the POINT() function) assigns each of its two data elements a random value in the range from 0 to 1.
This style of programming, sometimes called object-oriented programming, is fully supported by the C++ class construct. A class can be considered an extension of the concept of a structure, where not only data is combined, but also operations on this data are defined. There may be many different objects belonging to the same class, but they are all similar in that their data members can take on the same set of values, and the same set of operations can be performed on those data members - in general , these are instances of the same data type. In object-oriented programming, objects are designed to process their member data (as opposed to using independent functions to process data stored in objects).
We're looking at the small class example described above just to become familiar with the basic features of classes; so it is far from complete. In real code, we will have many more operations for the point class. For example, in program 4.1 there are not even operations that allow you to find out the values of the x and y coordinates. As we'll see, adding these and other operations is a fairly simple task. In Part 5 we'll take a closer look at classes for the point and other geometric abstractions such as lines and polygons.
In C++ (but not C), structures can also have functions associated with them. The key difference between classes and structures relates to information access, which is characterized by keywords
A data type describes a set of objects with similar properties. All traditional programming languages use a set of basic data types (real, integer, string, character). Basic data types are subject to a predefined set of operations. For example, the basic data type integer allows you to perform operations such as addition, subtraction, multiplication, and division.
Traditional programming languages include type constructors, the most common of which is the record constructor. For example, for a record of type CUSTOMER, you can define data fields. The CUSTOMER record will be a new data type that will store customer information, you can directly access this data structure by referencing the field names. You can perform operations on a record such as WRITE, READ, DELETE, UPDATE. You cannot define new operations for basic data types.
Like basic data types, abstract data types (ATD) describe many similar objects. There are differences between ATD and the traditional data type:
· operations under ATD are defined by the user;
· ATDs do not allow direct access to internal data representation and method implementation.
Some object-oriented systems (such as Smalltalk) implement basic data types as abstract ones.
To create an abstract data type you must provide:
· type name;
· data representation or instance variables of an object owned by ATD; each instance variable has a data type, which can be either a base type or another ATD;
· operations under ATD and restrictions are implemented using methods.
The ATD definition rebuilds the class definition. Some object-oriented systems use the type keyword to distinguish between classes and types when referring to data structures and methods of a class, and the class keyword when referring to a set of instances of an object. Type is a more static concept, while class is primarily concerned with runtime. The difference between an OO class and an OO type can be illustrated with an example. Let's say we have a template for a constructor. The template is accompanied by a description of its structure, as well as instructions for its use. This template is the type definition. A set of real products made using a template, each of which has a unique number (or OID), constitutes a class.
ATD together with inheritance allow you to create complex objects. A complex object is formed by a combination of other objects that are in complex relationships with each other. An example of a complex object can be found in security systems where different types of data are used:
1. standard (tabular) data about the employee (full name, table no., etc.);
2. bitmap for storing an employee’s photograph;
The ability to work with such a complex data environment with relative ease increases the importance of OO systems in today's database market.
Appendix to the work program for the discipline “Structures and algorithms for data processing in computers”
Abstract data type "List".
List– a sequence of elements of a certain type a1 , a2 , ..., a n, Where n https://pandia.ru/text/78/308/images/image001_307.gif" width="13" height="16">1, then a1
Called the first element, and an– the last element of the list. The elements of a list are linearly ordered according to their position in the list. ai element precedes element ai+1 For i = 1,2, n-1 And ai should for ai-1 For i = 2,3, n. Each element of the list ai has position i, i=1,2, n. There is a position in the list , meaning the end of the list - nil. It follows the last element of the list.
Operators of ATD "List":
1.INSERT( x, r,L). This operator inserts an object X into position r on the list L, moving elements from position p and then to the next higher position. So if the list L consists of elements a1 , a2 , ..., An a1, a2, ..., ar-1, x, ar, ..., an.. If p takes the value nil, then we will have a1 , a2 , ..., an , , X. If on the list L no position p, then the result of executing this statement is undefined.
2. LOCATE(x , L ). This function returns the position of the object X on the list L. If the object is in the list x occurs several times, the position of the first object from the beginning of the list is returned X. If the object X not on the list L, then returns nil.
3. RETRIEVE(p , L ). This function returns the element that is at position r on the list L. The result is undefined if p = nil or in the list L no position r.
4. DELETE(p , L ). This operator removes the element at position r list L. So, if the list L consists of elements a1 , a2 , ..., An, then after executing this operator it will look like a1, a2, ...,, ap- i , ap+ i, ..., A n. The result is undefined if in the list L no position r or r = nil.
5. NEXT( p, L ) And PREVIOUS(p, L ). These functions return the next and previous positions respectively from the position r on the list L. If r - last position in the list L, then NEXT (p, L) = nil. NEXT function is not defined when p=nil. The PREVIOUS function is not defined if p = 1. Both functions are undefined if in the list L no position r.
6. MAKENULL( L ) . This function makes a list L empty and returns the position nil.
7. FIRST(L ). This function returns the first position in the list L. If the list is empty, then the position is returned nil.
8. PRINTLIST(L ). Prints list items L in the order they appear in the list.
Representing a list using an array:
List view using singly linked list:
Designations:
· – pointer to the beginning of the list,
· last - pointer to the last element in the list ,
· maxlenght – maximum length (number of elements) in the list.
Representing a list using a doubly linked list:
Exercises:
1. Write programs for inserting, deleting and searching for elements of a sorted list, using list implementation
§ array,
§ pointers.
2. Write a merge program
§ two sorted linked lists,
§ n sorted linked lists,
3. Given a polynomial of the form
p(x) = c1 xe1 + c2 xe2 + + WithnXn, Where e1 > e2 > ... > en> 0.
Such a polynomial can be represented as a linked list, where each element has three fields: one for the coefficient Withi the second is for the exponent ei the third is for a pointer to the next element. For the described representation of polynomials, write a program for adding and multiplying polynomials using this representation.
4. Implement a LIST ADT for any data type and its INSERT, LOCATE, RETRIEVE, DELETE, NEXT, PREVIOUS, MAKENULL, PRINTLIST operators:
§ the list is specified as an array,
§ the list is specified as a singly linked list,
§ The list is specified as a doubly linked list.
Work program section 2.1.2
Abstract data type "Stack".
Stack - is a special type of list in which all insertions and deletions are performed at only one end, called top , (top). The access method used for the stack is LIFO(last-in-first-out - last in - first out).
Operators of ATD "Stack":
1. MAKENULL(S). Makes S's stack empty.
2. TOP(S). Returns the element from the top of the stack S. Typically the top of the stack is identified by position 1, then TOP(S) can be written in terms of common list operators as RETRIEVE(FIRST(S), S).
3. POP(S). Removes an element from the top of the stack (pops it from the stack), in terms of list operators this operator can be written as DELETE(FIRST(S), S).
4. PUSH(x, S ). Inserts an element X to the top of the stack S (pushes an element onto the stack). The element previously at the top of the stack becomes the element next to the top, and so on. In terms of common list operators, this statement can be written as INSERT(;c, FIRST(S), S).
5. EMPTY(S) . This function returns true(true) if stack S empty, and false otherwise.
array:
Stack view using singly linked list:
Exercises:
Implement the STACK ADT for any data type and its MAKENULL, TOP, POP, PUSH, EMPTY operators.
§ the stack is specified as an array,
§ The stack is specified as a singly linked list.
Work program section 2.1.2
Abstract data type "Queue".
Queue (queue) is a special type of list where elements are inserted at one end, called rear (rear), but are removed from the other, front (front). Queues are also called "FIFO lists" (FIFO stands for first-in-first-out). The operators performed on queues are similar to stack operators. The significant difference between them is that the insertion of new elements is carried out in end of list , and not to the beginning, as in stacks.
Operators of ATD "Queue":
1. MAKENULL(Q) clears queue Q , making it empty.
2. FRONT(Q) - a function that returns the first element of the queue Q. You can implement this function using list operators like RETRIEVE(FIRST(Q), Q ).
3. ENQUEUE(a,Q) inserts an element X to the end of the Q queue.
Using list operators, this statement can be executed as follows: INSERT(x, END(Q), Q ).
4. DEQUEUE(Q) removes the first element of queue Q . We can also implement it using list operators like DELETE(FIRST(Q), Q).
5. EMPTY(Q) returns true if and only if Q is an empty queue.
cyclical array:
Designations:
Q- queue,
Q. front– pointer to the beginning of the queue,
Q. rear- pointer to the end of the queue.
Representing a queue using singly linked list:
Exercises:
Implement the QUEUE ADT for any data type and its MAKENULL, FRONT, ENQUEUE, DEQUEUE, EMPTY operators.
§ the queue is specified as a cyclic array,
§ The queue is specified as a doubly linked list.
Abstract data type "Tree".
Tree is a collection of elements called nodes (one of which is defined as root ), and relationships (“parent”) that form a hierarchical structure of nodes. Nodes, like list elements, can be elements of any type. Formally, a tree can be defined recursively as follows.
1. One node is a tree. This same node is also the root of this tree.
2. Let p - this is a node, a T1 , T2, ...,Tk- trees with roots n1 . n2 , ..., nk respectively. You can build a new tree by doing n parent of nodes n1 . n2 , ..., nk. In this tree n will be the root, a T1 , T2, ...,Tk - subtrees this root. Nodes n1 . n2 , ..., nk are called sons node p.
This definition often includes the concept zero tree , i.e. a “tree” without nodes, such a tree is denoted by the word nill .
Example: O The chapter of a book can be schematically represented by a tree. The parent-son relationship is shown as a line. Trees are usually drawn from top to bottom with the parents above the "children".
DIV_ADBLOCK135">
Node height the length of a tree is called long way from this node to any leaf. In the example, the node height Chapter 1 equal to 1, node Chapter 2 - 2, and nodes Ch. Z - 0. Tree height coincides with the height of the root. Node depth is defined as the length of the path (it is the only one) from the root to this node.
The children of a node are usually ordered from left to right. Therefore, the two trees in the figure are different, since the order of the children of a node A different. If the order of the sons is ignored, then such a tree is called disordered , otherwise the tree is called ordered .
Operators of ATD "Tree":
1. PARENT(n, T). This function returns the parent of the node n in the tree T. If n is a root that has no parent, then in this case it returns nill. Here nill indicates that there has been an exit outside the tree.
2. LEFTMOST__ CHILD(n , T). This function returns the leftmost child of the node n in the tree T. If n is a leaf (and therefore has no son), then returns nill.
3. RIGHT_ SIBLING(n , T). This function returns the right sibling of the node n in the tree T or meaning nill.if it doesn't exist. This is what the parent is for r node n and all the sons of the node p, then among these sons is the node located immediately to the right of. node p.
4. LABEL(n , T ). Returns the node's label n. tree T. This function requires that tree nodes have labels defined.
5. CREATE(v , T 1 , T 2 , ..., Ti ,) is a family of functions that for each i = 0, 1, 2,... create a new root r with label v and then for this root creates i sons, which become the roots of subtrees T1 , T2, ....Ti;. These functions return a rooted tree r. Note that if i = 0, then one node is returned r, which is both a root and a leaf.
6. ROOT(T ) returns the node that is the root of the tree T, If T- empty tree, then returns nill.
7. MAKENULL(T ). This operator makes a tree T an empty tree.
Representing a tree using an array of parents:
Representing a tree using linked lists:
Representation of a tree by means of left sons and right brothers.
Designations in the figure:
nodespace – array of tree nodes,
- label
–
node label, header
–
index of the left son in the list of sons,
cellsspace – an array of lists of children of nodes,
- node
–
pointer to a node in the arraynodespace
,
next
–
index of the right son in the list of sons.
Exercises:
1. Given a tree:
DIV_ADBLOCK137">
§ the tree is specified as an array of node records containing the index of the leftmost son, the index of the right brother and a label,
§ a connected binary tree is given with using pointers on the left and right sons.
4. Write functions for traversing a binary tree in forward, backward and symmetric order.
Work program section 2.1.3
Abstract data type "Set".
Many usually depicted as a sequence of its elements enclosed in braces, for example (1, 4) denotes a set consisting of two elements - numbers 1 and 4. The order in which the elements of the set are written is not significant, so you can write (4, 1) in the same way as (1, 4) , when recording the same set. A set is not a list (at least based on the arbitrary order in which the elements are written). The set has no repeating elements ((1, 4, 1) is not a set).
The fundamental concept of set theory is the concept of relation belonging to the set , denoted by the symbol. So the entry X X does not belong to the set A", i.e. X is not an element of the set A. Exists special set, denoted by the symbol, which is called empty, many , and which has no elements. Set DIV_ADBLOCK138">
They say that there are many A contained in abundance IN(or turns on into the multitude IN), is written A IN or IN A, if any element of the set A is also an element of the set IN. In case A IN they also say that there are many A is a subset of the set IN.
For example, (1, 2) https://pandia.ru/text/78/308/images/image019_36.gif" width="15" height="15 src="> IN and A B, then the set A is called own, true or strict subset sets IN.
The main operations performed on sets are the operations of union, intersection and difference. Association sets A And IN(denoted A IN) is a set consisting of elements belonging to at least one of the sets A And IN.
By crossing sets A And IN(denoted A IN) is a set consisting only of those elements that belong to the set A, and many IN. By difference sets A And IN(denoted A\ B) is a set consisting only of those elements of the set A, which do not belong to the set IN.
For example, if A = (a, b, c) and B = (b, a), then A B = (a, b, c, d), A B = ( b ) and A \ B = (a, c ).
Operators of ATD “Multiple”:
1. UNION(A, B, C) A And IN WITH, equal A IN.
2. INTERSECTION(A, B, C) has as "input" arguments a set A And IN, and as a result - the “output” set WITH, equal A IN..
3. DIFFERENCE(A, B, C) has as "input" arguments a set A And IN, and as a result - the “output” set WITH, equal A\B.
4. MERGE( A , B, C) operator executes merger (merge), or union of disjoint sets . This operator is no different from the operator. UNION, but here it is assumed that the operand sets do not intersect (i.e. they do not have common elements). The operator assigns to a set WITH meaning A IN, but the result will not be determined if A In , i.e. in the case when the sets A And IN have common elements.
5. member(x, A ) has many arguments A and object X the same type as the elements of the set A, and returns a boolean value true(true), if X a", "b", "c"))= "A". The operator is defined in a similar way MAX.
11.EQUAL(A , IN ) returns value true if and only if the sets A And IN consist of the same elements.
12. FIND(x ) operates in an environment where there is a set of disjoint sets. It returns the (single) name of the set that contains the element X.
Set representation:
A set can be specified using an array or a linked list.
Exercises:
1. Two sets A = (1, 2, 3) and B = (3, 4, 5) are given. What will be the result of executing the following statements?
UNION(A.V.C),
INTERSECTION(A, B, C),
DIFFERENCE(A. V. C),
MEMBER(l. A),
INSERT(1,A),
DELETE(1, A),
2. Implement the “Set” ADT for any data type and its operators MAKENULL, UNION, INTERSECTION, MEMBER, MIN.
· the set is defined using a fixed-length array and a pointer to the last occupied position in the array,
· the set is defined using an unsorted linked list,
· the set is defined using a sorted linked list,
Work program section 2.1.3
Special types of sets
Abstract data type “Binary Search Tree”
Binary search tree - a data structure for representing sets whose elements are ordered by some linear order relation. Set operators can be implemented in binary search trees INSERT, DELETE, MEMBER And MIN, and their execution time on average is of the order of O (log n) for sets consisting of n elements.
A characteristic feature of a binary search tree is that its nodes are labeled with set elements (tree nodes contain set elements). Moreover, all elements stored in the nodes of the left subtree of any node X, less than the element contained in the node X, and all elements stored in the nodes of the right subtree of the node X, more element contained in the node X.
Binary tree examples:
https://pandia.ru/text/78/308/images/image023_7.jpg" width="277" height="122 src=">
The AVL tree representation is no different from the binary search tree representation.
Another variation of the balanced search tree is 2-3 tree. The structure of a 2-3 tree is different from the structure of a binary search tree. A 2-3 tree is characterized by the fact that all nodes have 2 or 3 children, all paths from the root to a leaf have the same length, and all elements of the set are contained in the leaves. Nodes 2-3 of the tree are divided into internal and terminal (leaves). Internal nodes are used only for routing searches in the tree. Each internal node contains the keys of the smallest elements of the second and third son (if there is a third son) and pointers to the nodes of the sons.
Linked binary search tree representation:
Representation of a balanced connected 2-3 tree:
Exercises:
1. Draw all possible binary search trees for the four elements 1, 2, 3 and 4.
2. Insert the integers 7, 2, 9, 0, 5, 6, 8, 1 into the empty binary search tree.
3. Show the result of removing the number 7 and then the number 2 from the tree obtained in the previous exercise.
4. Draw a 2-3 tree that results from inserting elements 5, 2, 7, 0, 3, 4, 6, 1, 8, 9 into the empty set (represented as a 2-3 tree).
5. Show the result of removing element 3 from the 2-3 tree obtained in the previous exercise.
3. Implement the “Search Tree” ADT for any data type and its INSERT, DELETE, MEMBER and MIN operators.
· the tree is specified as a connected binary tree
· the tree is specified as 2-3 trees
Work program section 2.1.3
Abstract data type "Dictionary".
Dictionary – a set designed to store “current” objects with periodic insertion or removal of some of them. From time to time there is also a need to find out whether a particular element is present in a given set. The dictionary is implemented using the Dictionary ADT with operators INSERTDELETE And MEMBER. The set of dictionary operators also includes the operator MAKENULL to initialize ADT data structures.
A dictionary can be represented using a hash table. The table is built on the basis of the following idea: a potential set of elements (possibly infinite) is divided into a finite number of classes. For IN classes numbered from 0 to B -1, under construction hash function h such that for any element X function of the original set h(x) takes an integer value from the interval 0, ..., IN - 1, which corresponds to the class to which the element belongs X. Element X often called key, h( x) - hash-x value, and "classes" - segments . The method for resolving hashing collisions (two elements of a set have same value h(x)) open and closed hashing is used.
open hash table
An array called segment table and indexed segment numbers 0, 1,...,B - 1 , contains headers for IN linked lists. Element i th list is an element of the original set for which h(.x:) =i.
Representing a dictionary using private hash table
The segment table directly stores the dictionary elements. Therefore, each segment can only store one dictionary element. With closed hashing, the technique is used re-hashing . When trying to place an element x into the segment with number h ( x ) , which is already occupied by another element, a sequence of segment numbers is selected h 1 ( x ) ,h 2 ( x ) , … , where you can place the element. The occupancy of each of these segments is sequentially checked until a free segment is found. It contains an element x . Various collision resolution methods are used to set segment numbers during re-hashing. For example, linear hashing method, mid-square method, random hashing method
Exercises:
1. Suppose that the hash function h(i) = i % 7 is used to hash integers into a 7-segment hash table.
· give the resulting hash table if exact cubes 1, 8, 27,64,125, 216,343 are inserted into it;
· repeat the previous point for a closed hash table with a linear collision resolution technique.
2. Assume that there is a closed hash table with 5 segments, a hash function h(i) = i % 5 and a linear collision resolution technique. Show the result of inserting the sequence of numbers 23, 48, 35, 4, 10 into an initially empty hash table.
3. Implement the Dictionary ADT for text strings and its INSERT statements , DELETE, MEMBER and MAKENULL
· the dictionary is specified using an open hash table,
· the dictionary is specified using a closed hash table with a linear collision resolution technique,
Work program section 2.1.3
Abstract data type "Display".
Display - this is a set on whose elements a function for displaying elements of the same type is defined ( domain of definition ) to elements of another type ( range of values ) of another type. Display M matches an element d type domaintype from the scope of the element r type rangetype from the range of values: M(d) = r.Blank display does not contain any elements
Operators of ADT "Display":
1. MAKENULL(M ). Makes a display M empty.
2. ASSIGN(M d, r). Does M(d) equal r no matter how M(d) was previously defined.
3. COMPUTE( M, d, r). Returns true and assigns the variable r the value M(d), if the latter is defined, and returns false otherwise.
Display view: the mapping can be efficiently implemented using hash tables. Here x specifies a value from the display definition area, and the table element with number h ( x ) – element from the range of values.
Work program section 2.1.3
Abstract data type “Priority Queue”
Priority queue - this is a set for whose elements a priority function is specified, i.e. for each element x set, you can calculate the function p( x )- element priority x , which usually takes values from the set of real numbers, or, more generally, from some linearly ordered set.
ADT “Priority Queue” based on the “Set” ADT with operators INSERT And DELETEMIN, as well as with the operator MAKENULL to initialize the data structure. Operator INSERT for a priority queue is understood in in the ordinary sense, whereas DELETEMIN is a function that returns the element with the lowest priority and as side effect removes it from the set.
Representing a queue using ordered doubly linked list.
Representing a queue using partially ordered connected tree:
The main idea of this implementation is to organize the elements of the queue in the form of a binary tree. At a lower level, where some leaves may be missing, all the missing leaves may be located just to the right of the lower level leaves present. More importantly, the tree partially ordered . This means that the node priority v no greater than the priority of any child of the node v, where node priority is the priority value of the element stored in this node. The figure shows that small priority values cannot appear at a higher level where there are large priority values.
The DELETEMIN function returns the element with the minimum priority, which must be the root of the tree. To avoid destroying the tree and to maintain partial ordering of the priority values on the tree after removing the root, the following actions are performed: the rightmost node is located at the lowest level and is temporarily placed at the root of the tree. This element then moves down the branches of the tree (to lower levels), changing places along the way with its sons having lower priority, until that element becomes a leaf or is in a position where its sons have at least no less priority.
Representing a queue using an array containing the nodes of a partially ordered tree:
In the array A first n positions correspond n tree nodes. Element A contains the root of the tree. Left son of a tree node A[ i], if it exists, it is in the cell A, and the right son, if he exists, is in the cell A. And vice versa, if the son is in the cell A[ i], then its parent is in the cell A[ i%2] . Tree nodes fill cells A, A, … A[ n] sequentially level by level, starting from the root, and within the level - from left to right. The tree shown above will be represented in the array by the following sequence of its nodes: 3, 5, 9, 6, 8, 9, 10, 10, 18, 9.
Exercises:
1. Draw a partially ordered tree resulting from inserting the integers 5, 6, 4, 9, 3, 1 and 7 into an empty tree. What is the result consistent application to this tree of three DELETEMIN statements?
2. Implement the Priority Queue ADT for any data type and its INSERT, DELETEMIN and MAKENULL operators
§ a partially ordered tree is implemented using pointers,
§ A partially ordered tree is implemented using an array.
Work program section 2.1.3
Abstract data type "Union of sets".
An ADT is a union of objects, each of which is a set. The main actions performed on such a set are to combine the sets into in a certain order, as well as in checking whether a certain object belongs to a specific set. These problems are solved using operators MERGE(Drain) and FIND(Find). MERGE( A, B, C) does a lot WITH equal to the union of sets A And IN, if these sets do not intersect (that is, they do not have common elements); this operator is not defined if the sets A And IN intersect. Function FIND( x) returns the set to which the element belongs X; in case X belongs to several sets or does not belong to any, the value of this function is not defined.
Operators of the ADT “Union of sets”:
1. MERGE(A , IN) combines components A And . IN, the result is assigned to either A or IN.
2. FIND(x ) - a function that returns the name of the component to which it belongs X.
3. INITIAL(A , X ) creates a component named A containing only the element X.
Representation of combining sets using arrays:
The set name matches the array index value setheaders ( name 0 )
Designations:
setheaders – array of set headers:
§ With ount – number of elements in the set,
§ first element – array indexnameswith the first element of the set,
names – array of lists of set elements:
- setname
- the name of the set to which the element belongs, next element
– index of the next element in the list given set(index value 0 is used as the end of the list).
Work program section 2.1.3
Abstract data type “ Directed graph"
Basic definitions:
Directed graph (digraph ) G = (V, E) consists of many vertices V and sets of arcs E. Vertices are also called nodes , and arcs - oriented edges . An arc can be represented as an ordered pair of vertices ( u, w), where is the top And called the beginning , a w - the end arcs.
They also say that the arc And -> w leads from the top to the top w, and the top w adjacent with top v.
Example 1 digraph:
The vertices of a digraph can be used to represent objects, and the arcs can be used to represent relationships between objects.
By in a digraph the sequence of vertices is called v1 , v2 , … , vn , , for which arcs exist v1 -> v2 , v2 , -> v3, , ..., vn-1 , -> vn. This path starts at the top v1 and, passing through the peaks v2 , v3 , ..., vn-1 ends at the top vn. Path length - the number of arcs that make up the path, in this case the length of the path is p - 1 . As a special case of a path, consider one vertex v as a path of length 0 from the top vTo this same peak v. In the figure, the sequence of vertices 1, 2, 4 form a path of length 2 from vertex 1 to vertex 4.
The path is called simple , if all the vertices on it, with the possible exception of the first and last, are different. Cycle - is a simple path of length at least 1 that starts and ends at the same vertex. In the figure, vertices 3, 2, 4, 3 form a cycle of length 3.
In many applications, it is convenient to attach some information to the vertices and arcs of a digraph. For these purposes it is used labeled digraph , i.e., a digraph in which each arc and/or each vertex has corresponding labels. The label can be a name, weight or value (arc), or a data value of some kind. of this type.
Example 2 of a labeled digraph:
DIV_ADBLOCK149">
3. Transitive closure algorithm (Warshall algorithm):
For the count G = (V, E) the algorithm calculates the transitivity matrix T, each element of which T[i, j] = 1 only when there is a path from the top i to the top j And T[ i, j] = 0 otherwise.
4. Algorithm for finding the center of a digraph:
Let And - arbitrary vertex of a digraph G = (V,E). Eccentricity (maximum removal) peaks And defined as
max(minimum path length from the top w to the top v }
w V
Center of the digraph G called the vertex with minimal eccentricity. In other words, the center of the digraph is the vertex for which the maximum distance (path length) to other vertices is minimal.
Example: The center of the digraph is the vertex d
Eccentric-t |
||
| ||
5. Algorithm for traversing a digraph in depth (depth-first search):
When solving many problems involving directed graphs, it is necessary effective method systematic traversal of vertices and arcs of digraphs. This method is the so-called depth first search - generalization of the forward tree traversal method. Depth-first search begins with selecting a starting vertex v graph G, this vertex is marked with a label visited (visited). Then for each vertex adjacent to the vertex v and which has not been visited before, depth-first search is recursively applied. When all the peaks that can be reached from the top v, will be "honored" of a visit, the search ends. If some vertices remain unvisited, then one of them is selected and the search is repeated. This process continues until all vertices of the digraph are covered by the traversal. G.
6. Algorithm for constructing a deep spanning tree of a graph:
When traversing a graph using depth-first search, only certain arcs lead to unvisited vertices. Such arcs leading to new vertices are called tree arcs and form the graph spanning forest constructed using depth-first search method – deep spanning forest . When constructing a forest, there are 3 types of arcs: reverse, straight and transverse. Reverse arcs - such arcs that in the spanning forest go from descendants to ancestors. Straight arcs are called arcs that go from ancestors to true descendants, but which are not arcs of a tree.
Arcs connecting vertices that are neither ancestors nor descendants of each other are called transverse arcs . If, when constructing a spanning tree, the sons of one vertex are located from left to right in the order they are visited, and if new trees are added to the forest also from left to right, then all transverse arcs go from right to left.
For example, arcs D->C and G->D– transverse, arc C-> A– reverse, there are no direct arcs.
When traversing a tree in depth, it is often convenient to number the vertices in the order in which they are visited. Such numbers are called deep.
Digraph representation:
§ Representation of a digraph using an adjacency matrix:
Adjacency matrix for a digraph G- this is a matrix A size n n with Boolean values, where A[ i, j] = true if and only if there is an arc from the vertex i to vertex j. Often in adjacency matrices the value true is replaced by 1, and the value false- to 0.
A generalization of the representation of a digraph using an adjacency matrix can be considered the representation of a labeled digraph also using an adjacency matrix, but whose element A[ i, j] equal to arc label i ->j. If the arcs are from the vertex i to the top j does not exist, then the value of A[ i, j] cannot be the value of any valid label, but may be treated as an "empty" cell.
Adjacency matrix for a labeled digraph (example 2):
§ Representation of a digraph using adjacency lists:
Adjacency list for a vertex i is a list of all vertices adjacent to a vertex i, and ordered in a certain way. Digraph G can be represented using an array HEAD(Title) whose element HEAD[i] is a pointer to the adjacency list of a vertex i.
 |
Operators of ATD “Orgraf”:
The most common operators performed on directed graphs include operators for reading vertex and arc labels, inserting and deleting vertices and arcs, and moving through sequences of arcs.
To view a set of adjacent vertices, the following three operators are required.
1. FIRST( v) returns the index of the first vertex adjacent to the vertex v. If the top v has no adjacent vertices, then the “zero” vertex is returned nil.
2.NEXT( v, i) returns the index of the vertex adjacent to the vertex v, next to index i. If i- this is the index of the last vertex adjacent to the vertex v, then it comes back nil.
3. VERTEX( v,i) returns the vertex with index i from the set of vertices adjacent to v.
Exercises:
Given a directed graph (digraph):
https://pandia.ru/text/78/308/images/image043_12.gif" width="125" height="100 src=">
Example of a disconnected graph:
Cycle (simple) is a path (simple) of length at least 3 from any vertex to itself. The graph is called cyclical , if it has at least one cycle. A connected acyclic graph, which is a "tree without a root", is called free tree . The second figure above shows a graph consisting of two connected components, each of which is a free tree. A free tree can be made into a “regular” tree if some vertex is designated as the root, and all edges are oriented in the direction from this root.
Free trees have two important properties:
1. Every free tree with the number of vertices n, n > 1 , has exactly n - 1 ribs
2. If you add a new edge to a free tree, you will definitely get a cycle.
Let G = (V, E) - connected graph in which each edge ( r, w) marked with a number With(v, w), which is called rib cost . spanning tree graph G a free tree containing all vertices is called V column G. Price spanning tree is calculated as the sum of the costs of all edges included in this tree
Basic algorithms for processing undirected graphs:
1. Building a spanning tree minimum cost(Prim's algorithm):
Many peaks are being built U, from which the spanning tree “grows”. Let V= (1, 2, ...,n}. At first U = (1). At each step of the algorithm, the edge of the least cost is found ( u,v) such that u U And v V\U, then the top v transferred from set V\U into the multitude U. This process continues until many U will not be equal to the set V.
The sequence for constructing a spanning tree is given below.
https://pandia.ru/text/78/308/images/image048_12.gif" width="501" height="384 src=">
3. Traversing undirected graphs using depth-first search:
Depth-first search is used to systematically traverse all vertices of a graph. The depth-first search algorithm is similar to the algorithm for traversing the vertices of a digraph. The latter is also used for undirected graphs, since an undirected edge (v, w) can be represented as a pair of oriented arcs v -> w And w -> v.
Depth-first traversal can be used to construct a spanning tree.
The graph and spanning tree obtained by traversing its vertices using the depth-first search method are given below:
4. Traversing undirected graphs using breadth-first search
Another method for systematically traversing the vertices of a graph is called breadth first search . It got its name due to the fact that when reaching any peak while walking around v then all vertices adjacent to the vertex are considered v, i.e., the vertices are viewed “breadth first”. This method can also be applied to directed graphs.
Just like when applying depth-first search, using the breadth-first search method, a spanning forest is created when traversing the graph. If after reaching the top X when examining the rib (x, y) vertex at has not been visited before, then this edge is considered an edge of the tree. If the top at has already been visited before, then the edge (x, y) will be a transverse edge, since it connects vertices that are not connected by inheritance from each other.
The spanning tree obtained using the breadth-first search method is shown below.
Representing an undirected graph using an adjacency matrix:
To represent undirected graphs, you can use the same methods as for representing directed graphs, if the undirected edge between the vertices v And w treated as two oriented arcs from the vertex v to top w and from the top w to the top v.
https://pandia.ru/text/78/308/images/image051_12.gif" width="159" height="106">
Representing an undirected graph using adjacency lists:
https://pandia.ru/text/78/308/images/image053_12.gif" width="339" height="115 src=">
1. Build:
minimum cost spanning tree using Prim's algorithm;
minimum cost spanning tree using Kruskal's algorithm;
spanning tree using depth-first search, starting from vertices a and d;
spanning tree using breadth-first search, starting from vertices a and d.
2. Implement the Prim and Kruskal algorithms.
3. Implement the construction of a spanning tree using the depth-first search method
§ for an undirected graph represented using an adjacency matrix,
§ for an undirected graph represented using adjacency lists.
4. Implement the construction of a spanning tree using the breadth-first search method
§ for an undirected graph represented using an adjacency matrix,
§ for an undirected graph represented using adjacency lists.
Abstract data type
Abstract data type (ATD)- this is a data type that provides a certain set of functions for working with elements of this type, as well as the ability to create elements of this type using special functions. The entire internal structure of this type is hidden from the software developer - this is the essence of abstraction. An abstract data type defines a set of functions independent of the specific implementation of the type for operating on its values. Specific implementations of ADTs are called data structures.
In programming, abstract data types are usually represented as interfaces, which hide the corresponding type implementations. Programmers work with abstract data types exclusively through their interfaces, since the implementation may change in the future. This approach follows the principle of encapsulation in object-oriented programming. The strength of this technique is precisely the hiding of the implementation. Since only the interface is published externally, then as long as the data structure supports this interface, all programs that work with the given abstract data type structure will continue to work. Developers of data structures try, without changing the external interface and semantics of functions, to gradually refine implementations, improving algorithms in terms of speed, reliability and memory used.
The difference between abstract data types and data structures that implement abstract types can be illustrated with the following example. The abstract list data type can be implemented using an array or a linear list, using various methods dynamic memory allocation. However, each implementation defines the same set of functions, which should perform the same (in output, not speed) across all implementations.
Abstract data types enable modularity software products and have several alternative interchangeable implementations of a particular module.
ADT examples
See also
Links
- Lapshin V. A. Abstract data types in programming
Wikimedia Foundation. 2010.
See what “Abstract data type” is in other dictionaries:
abstract data type- A data type (abstract class) defined by listing its methods and properties, without creating a concrete implementation of them. Topics information Technology in general EN Abstract Data TypeADT ... Technical Translator's Guide
In programming theory, any type whose values are the values of some other types, “wrapped” by constructors of an algebraic type. In other words, an algebraic data type has a set of type constructors, each of which... ... Wikipedia
Integer, an integer data type (English Integer), in computer science one of the simplest and most common data types in programming languages. Used to represent integers. The set of numbers of this type is... ... Wikipedia
This term has other meanings, see Set (meanings). A set, a type and data structure in computer science, is an implementation of the mathematical object set. Data type set allows you to store a limited number of values... ... Wikipedia
Some programming languages provide a special data type for complex numbers. The presence of a built-in type simplifies the storage of complex quantities and calculations on them. Contents 1 Arithmetic over complex complexes 2 Support in languages ... Wikipedia
This term has other meanings, see Index. Pointer diagram A pointer (English pointer) is a variable whose range of values consists of the addresses of memory cells and the special value of the zero address.... ... Wikipedia
One of the types of algebraic data types, which is characterized by the fact that its constructors can return values that are not their own type. This concept is implemented in several programming languages, in particular in the ML and Haskell languages, and in ... ... Wikipedia
A trait is an abstract type in computer science, used as a “simple conceptual model for structuring object-oriented programs." Traits are similar to mixins, but can include definitions of class methods.... ... Wikipedia
A binary tree, a simple example of a branching connected data structure. Data structure is a program unit that allows storing ... Wikipedia
- (top type) in type theory, often denoted simply by the top or by the "pinned" symbol (⊤), a universal type, that is, a type that contains every possible object in required system types. The highest type is sometimes called... ... Wikipedia
Abstract data type General provisions about data Abstract data type general provisions specification, representation, implementation 1
What is data? Set of various information objects, on which certain actions are performed by program operators, are called data. Data is an indispensable attribute of any program. They can be: - individual bits; - sequence of independent bits; -numbers in different forms of representation; -bytes and groups of independent bytes; -arrays of numbers; - linked lists; -separate files and file systems. 2
A universal representation of this variety of data is difficult and impractical. It is advisable to divide them into 3 types
What is a data type? The data type is determined by: – The format of representation in computer memory according to certain conventions of the algorithmic language, but without the need for calculations; – Many acceptable values, which a variable or constant belonging to the selected type can take; – The set of valid operations applicable to this type. 4
Examples of data types Integer types Real type Boolean type Character type Enumerated type Interval type Pointers 5
Integer Types There are five predefined integer types: Shortint, Integer, Longint, Byte, and Word. Each type denotes a specific subset of integers. A value of one integral type can be explicitly converted to another integral type using a type cast. 6
Real type The real type is a subset of numbers represented in floating-point format and with a fixed number of digits. Writing a value in floating point format typically involves three values - m, b and e - such that m * b ^ e = n, where b is always 2 and m and e are integer values in the real range. These values of m and e further determine the representation range and precision of the real type. Example: 0.143 E+22, where m - 0.143; b=2(implied), e=22. There are five types of real types: Real, Single, Double, Extended, and Comp. 7
Logical type There are 4 predefined logical (Boolean) types: Boolean, Byte. Bool, Word. Bool and Long. Bool. Boolean values are denoted by built-in constant identifiers False and True. Boolean variables can be used to store the results of any logical calculations. For Boolean variables, only 2 comparison operations are allowed: "=" (equal) and "" (unequal). 8
Character type The value set of this type is characters ordered according to the extended ASCII character set. These are the letters ["A". . . "Z", "a". . . "z"], numbers ["0". . . "9"], punctuation marks and special characters. A variable of this type occupies one byte in memory. 9
Enumeration Type Enumeration types define ordered sets of values by enumerating identifiers that represent those values. The sets are ordered according to the sequence in which the identifiers are listed. Type Week = (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday); 10
Interval Type An interval type represents a range of values from an ordinal type. The definition of interval type includes least and highest value in the sub-range. Type Interval = 0. . . 1000; This type declaration tells the compiler that only numbers within the specified range are valid for variables of this type. Thus, the program can automatically check the correctness of assignment operations for these variables. 11
Common to Data Types Each data type has a number of simple operations associated with it. INTEGER operations +, -, *, div, mod REAL - operations + , -, *, / BOOLEAN - operations - conjunction (and), disjunction V (or), negation (not) CHAR operations ORD (c) -N : (C in ASCII), CHR (I) I-th character in ASCII As the volume and complexity of information representation increases, the need arises for convenient forms of its presentation, storage and processing. 12
Definition: An abstract data type (ATD or abstract data type, or ADT) is a set of abstract objects representing data elements, and sets of operations defined on it that can be performed on the elements of this set. 13
ADT - generalization of data types Abstract data types (ADT) can be considered as a means of extending programming languages. Let's compare an abstract data type with such a familiar concept as a procedure. A procedure can be considered as a generalized concept of an operator. Two characteristic features of procedures, generalization and encapsulation, perfectly characterize abstract data types. An ADT can be thought of as a generalization of simple data types (integer, real, etc.), just as a procedure is a generalization simple operators(+, -, etc.) 14
Advantages of ADT Abstract data structures are designed for convenient storage and access to information. They provide user-friendly interface for typical operations with stored objects, hiding implementation details from the user. Of course, this is very convenient and allows you to achieve greater modularity of the program. 15
Example For automated control temperature in the various rooms of a large building, a useful ADT would be THERMOSTAT. The program may contain many type variables THERMOSTAT, corresponding to real thermostats in various areas of the building. An ADT can be described by its name, set of values, and valid operations just like any other data type. Description for the THERMOSTAT type: – Data type: THERMOSTAT – Range of values: the temperature can vary from 0 to 50 degrees (Celsius). – Operations: High, Low, Set, Check, Alarm. (You can come up with many useful operations, but too many of them degrade the abstraction) 16
Levels of Abstraction Levels of abstraction are like layers of software. The highest levels of abstraction reflect the user's understanding of the solution to the problem. Lower levels abstractions - the capabilities of a programming language. 17
Example of user-level abstraction An architect represents a house as walls, floors, windows, doors, etc. In this case, the data type is Drawing. Doors would make a good abstract type. Data type: Drawing. Door Operations: Draw. Door Erase. Door Draw. Double. Door ……. Drawing. Doors are a high-level abstraction that reflects the user's view of the problem 18
Example of Programmer-Level Abstraction The programmer can propose another level of abstraction for these objects, such as a rectangle. Data type: Rectangle Operations: Draw. Rectangle Erase. Rectangle Divide. Rectangle. On. Parts……. A rectangle is more of an abstraction low level, since it is closer to implementation. 19
ADT constructors Each ADT must contain operations for constructing values of its type. Such operations are called constructors. There must be enough constructors to generate the entire set of values of a given type. An ADT that satisfies this property is called complete. Incomplete ADT is a design error. 20
Recommendations for selecting operations of an abstract data type It is advisable to include the following operations: – constructor operations, – verification operations, – type conversion operations, – input-output operations, – copy operations, – selector operations. Try to keep the number of operations to a minimum. Simple ADT is easier to understand. Maintain operations associated with the selected type abstraction. 21
Primary constructor Operations that create new values of an ADT regardless of its previous value are called primary constructors. Each ADT includes at least one primary constructor: without it, it is impossible to generate the initial value. 22
Using Hidden Types Abstract data types are best declared as hidden types. This allows the data structure description to be moved to the implementation module, where it is primarily used. They also provide the ability to prevent direct access to type components from the importer side. Since a hidden type is always implemented using a pointer, three operations must be included in the ADT. – Create - an operation that creates a node of the corresponding structure. – Destroy is an operation to free the memory of a hidden type node. – Assign - the operation of copying the fields of the dynamic structure of a node of a hidden type. 23
What is the specification and implementation of an abstract data type? An abstract data type is a way of defining a certain concept in the form of a class of objects with certain properties and operations. In a programming language, such a definition is formalized as a special syntactic construction called different languages capsule, module, cluster, class, package, form, etc. This construction in its most developed form contains: a data type specification, including a description of the interface (name of the type being defined, names of operations with their profiles) and an abstract description of operations and objects, with which they work, some specification tools; an implementation of a data type, including a specific description of the same operations and objects. 24
Classification of data types according to the method of description and protection; packaged, if the description of the data type is collected in one place (in one package), i.e. its objects and operations are combined into one concept; it has a definition, which can, however, only contain its implementation; encapsulated, if the data type is packaged, its definition contains an interface description and implementation, and encapsulation of the implementation is also provided; abstract if the data type is encapsulated and its specification includes an abstract description. 25
Components of a specification Programming, as a process, begins with a statement of the problem (its definition), or specification of the problem. Further throughout the text, specifications consisting of six components are used: – Title - the name of the problem being solved; – Description - several sentences describing the essence of the task; - Entrance - detailed description expected form of input data; – Output - a detailed description of the expected form of the output data; – Errors - detailed list situations arising from incorrect input data; – Example - an example of execution in terms of input-output. 26
Specification example Abstract data type STACK, implementing a well-known data structure, which is characterized by the fact that you can “put” some element into it and “select” the element most recently placed there. The syntax portion of the STACK data type specification is view type STACK specification is CREATE: function () return (@); INSERT: function (integer; @) return (@); DELETE: function (@) return (@); TOP: function (@) return (integer); EMPTY: function (@) return (boolean); end specification; Here, the CREATE operation produces an empty stack as a result, INSERT - a stack with its element added to the "top", DELETE - a stack with the "top" element removed, TOP - the value of the "top" element of the stack, EMPT - a sign that the stack is empty. The elements of the stack here can only be integers. 27
IMPLEMENTATION OF AN ABSTRACT DATA TYPE Implementation is more conveniently done using object-oriented programming languages, such as C++ or Java, in which abstract data types are supported using classes. Implementation of an ADT includes a specific description of objects of a defined type and implementation of operations of this type. This means that objects are described either as data of simple types, or as arrays, records, or unions. Moreover, predefined data types or ADTs defined earlier are used. The implementation of operations consists of describing subroutines that perform the necessary actions with specified objects. For example, operations +, *, =. . etc., but at the same time the very implementation of these operations is hidden. 28
