Abstract data type concept. Abstract classes and class members

The C++ language allows you to create data types that behave similarly to the basic types of the C language. These types are usually called abstract data types(ATD).
To implement ADT in the C language, structures are used. But data usage structural type significantly limited compared to using basic data types. For example, structure data cannot be used as operands in various operations (addition, subtraction). To manipulate such data, you need to write a set of functions that perform various actions, and call these functions instead of operations.

In addition, the elements of the structure are in no way protected from accidental modification. That is, any function (even not from the set of tools for manipulating structural data) can access a structure element. This contradicts one of the basic principles of object-oriented programming - data encapsulation: no other functions except special functions manipulations of this data type should not have access to the data elements.

Let's look at the implementation of the date concept using struct to define a date representation and a set of functions for working with variables of this type:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include
struct date
{
int month; // month
int day; // day
int year; // year
};
void set_date(date* f, int d, int m, int y)
{
f->day = d;
f->month = m;
f->year = y;
}
void print_date(date* f)
{
printf("%d.%d.%d" , f->day, f->month, f->year);
}
int main()
{
date today;
set_date(&today, 2, 4, 2014);
print_date(&today);
getchar();
return 0;
}

There is no explicit connection between functions and data type in this example. To call any of the described functions, you must pass a pointer to an instance of the structure as an argument.

This connection can be made by describing functions as members of a structure. These functions can act on data contained within the structure itself.
By default, when declaring a structure, its data and functions are shared, that is, objects of type structure have neither encapsulation nor data protection:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include
struct date
{
int month; // month
int day; // day
int year; // year
void set_date(int d, int m, int y)
{
day = d; month = m; year = y;
}
void print_date(void);
};
void date::print_date(void )
{
printf("%d.%d.%d" , day, month, year);
}
int main()
{
date today;
today.set_date(2, 4, 2014);
today.print_date();
getchar();
return 0;
}

Member functions and data members

The functions declared in the body of an abstract data type are member functions or methods and can only be called on a special variable of the corresponding type using the standard syntax for accessing data members or fields of a structure.

Member functions can be defined in two ways:

• description of the function directly when describing the structure;
• description of a function outside the structure.

Member functions that are defined inside a structure are implicitly inlined ( ). As a rule, only short, frequently used member functions should be defined inside the structure:

void set(int m, int d, int y) (month = m; day = d; year = y;);

• type— return type of the member function
• ATD— name of an abstract data type (name of a structure or class)
• Name— member function name

void date::print_date(void )
( printf("%d.%d.%d" ,day, month, year);)

In a member function, member names can be used without an explicit reference to the object. In this case, the name refers to the member of the object on which the function was called.

Member functions of the same structure can be polymorphic, that is, overloaded.

Access rights

The concept of a structure in C++ (as opposed to C) allows members of a structure to be public, private, or protected:

• public – general;
• private – private;
• protected – protected.

The use of the protected keyword is related to the concept of inheritance.

Using the private keyword restricts access to members that follow this construct. Private members can only be used by a few categories of functions whose privileges include access to those members. Basically these are member functions of the same structure.
The public keyword forms an interface to a structure object.

It is standard to place member data in the private area (private) and part of the member functions in the public part (public) of the abstract data type. In this case, the private part defines the object data and service functions, and the member functions of the public part implement methods for working with the object.

Let's change the date structure to hide the data representation (data encapsulation):

1
2
3
4
5
6
7
8

struct date
{
private :
int month, day, year;
public:
void set(int, int, int);
void print();
};

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. Data structure developers try without changing external interface and semantics of functions, 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 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 within itself every possible object in required system types. The highest type is sometimes called... ... Wikipedia

Good day, Khabra residents!

The following post is a summary of my thoughts on the nature of classes and ADT. These thoughts are supplemented with interesting quotes from the books of development gurus software

Introduction

Abstraction is the selection and imparting to a set of objects of common properties that determine their conceptual boundaries and distinguish them from all other types of objects.
In other words, abstraction allows us to “shed light” on the object data we need and, at the same time, “shade” the data that is not important to us.

So, what happens if you merge the concepts of “data type” and “abstraction” together? We will receive a data type that provides us with a certain set of operations that ensure the behavior of objects of this data type, and this data type will also hide the data with which this behavior is implemented. Hence, we come to the concept of ADT:

An ADT is a data type that hides its internal implementation from clients.
The amazing thing is that by applying abstraction, ADT allows us to not worry about low-level implementation details, but to work with the high-level essence of the real world (Steve McConnell).

I believe that when developing an ADT, you first need to define an interface, since the interface should not depend on the internal representation of data in the ADT. After defining the operations that make up the interface, you need to focus on the data that will implement the specified behavior of the ADT. As a result, we will get a certain data structure - a mechanism that allows us to store and process data. At the same time, the beauty of ADT is that if we want to change the internal representation of data, we do not have to wander through the entire program and change every line of code that depends on the data that we want to change. An ADT encapsulates this data, which allows you to change the operation of objects of this type, rather than the entire program.

Advantages of ATD

Using an ADT has a lot of advantages (all the advantages described can be found in Steve McConnell's book "Perfect Code"):

• Encapsulation of implementation details.
  This means that once we have encapsulated the implementation details of the ADT, we provide the client with an interface with which it can interact with the ADT. By changing the implementation details, the clients' perception of the ADT operation will not change.

• Reduced complexity.
  By abstracting away from implementation details, we focus on the interface, that is, on what the ADT can do, rather than on how it is done. Moreover, ADT allows us to work with the essence of the real world.

• Limiting the scope of data use.
  Using an ADT, we can be sure that the data representing the internal structure of the ADT will not depend on other parts of the code. In this case, the “independence” of the ADT is realized.

• Highly informative interface.
  ADT allows you to present the entire interface in terms of domain entities, which, you see, increases the readability and informativeness of the interface.

Steve McConnell recommends representing low-level data types, such as a stack or a list, as an ADT. Ask yourself what this list represents. If it represents a list of bank employees, then consider the ATD as a list of bank employees.

So, we figured out what ADT is and named the advantages of its use. Now it is worth noting that when developing classes in OOP, you should think, first of all, about ADT. At the same time, as Steve McConnell said, you program not in a language, but with the help of a language. That is, you will program beyond the boundaries of the language, not limited to thinking in terms of arrays or simple data types. Instead you will think about high level abstractions (for example, in terms of spreadsheets or employee lists). A class is nothing more than an addition and a way to implement the ADT concept. We can even represent the class as a formula:
Class = ADT + Inheritance + Polymorphism.
So why should you think about ADT when developing classes? Because first we must decide which operations will make up the interface of the future class, which data to hide and which to provide open access. We need to think about making the interface highly informative, making the code easy to optimize and test, and how we can provide the right abstraction so we can think about real-world entities rather than low-level implementation details. I believe that it is after defining ADT that we should think about issues of inheritance and polymorphism.

It is worth noting that the ADT concept has found wide application in OOP, since it is this concept that complements OOP and makes it possible to reduce the complexity of programs in the rapidly changing world of software requirements.

I wrote this article in order to draw the attention of developers to ADT in order to improve the quality of work and software development.

Sources used:

Steve McConnell - “Perfect Code”;
Robert Sedgwick - “Algorithms in Java.”

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 traditional type data:

· 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 basic 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 when referring to a set of instances of an object - keyword class. 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. Example complex object can be found in security systems where they are used various types data:

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 value of OO systems by modern market databases.

It is customary to call an abstract data type that is not explicitly present in a programming language; in this sense, this is a relative concept - a data type that is absent in one programming language may be present in another.

Abstract data type(ATD) is defined regardless of the method of its implementation:

§ set of possible values ​​of this type,

§ and a set of operations with values ​​of this type.

The use of ADT may be limited to the software development stage, but for its explicit use in a program, it is necessary to have its implementation based on existing (and previously implemented) data types in the programming language:

§ a way to represent values ​​of this type,

§ and implementation of operations with values ​​of this type.

ADT is not predefined in a programming language, and even moreover, the construction operations of such types, predefined in the language, shift to the developer-programmer the question of how to represent values ​​of this type and implement operations with values ​​of this type. Therefore, for such data types the question is about choosing definitions and methods for implementing operations of the form constructor (values ​​and data stores) of this type, selector And modifier components (values ​​and data stores) of this type rests with the programmer developer.

In the ADT concept, the concepts have a special status interface , open to the user, and implementation , hidden from him. The special role of these concepts in the concept of ADT is associated with the fundamental position about the independence of the concept of ADT from the method of its implementation.

In modern “practical programming languages”, a predefined type construction operation is usually used to construct an ADT class , which gives the developer-programmer not only the means of grouping data and operations (with this data) into a single whole, but also the means of encapsulation, inheritance and polymorphism to control how such data is constructed and accessed. Note that a class describes one possible implementation of an ADT, the mapping of a class to an ADT is expressed by an abstraction function, but the inverse relation is usually not functional; there can be several implementations of the same ADT.

In research on abstract types data was realized at an early stage important role concepts " type parameterization " Indeed, for example, the ADT “Stack” does not depend on the type of stack elements, but it is impossible to implement this ADT by pointing to “elements of some identical type.” In the Ada programming language, appropriate tools for constructing parameterized data types were included initially, and in modern “practical programming languages” which tools appeared only since the advent of development using the STL library. Today the concept of “generalized programming” occupies significant position in practical programming due to its inclusion in "practical programming languages" tools for constructing parameterized data types (templates, template , generic) .

All of the above means that from a methodological and theoretical point of view, a more detailed precise definition of the concept of “abstract data type” is necessary. In theory, the concept of "abstract data type" is usually defined as multi-sorted (multi-basic) algebraic system , in which, in addition to the set of possible values ​​(carrier) and the set of operations on such values, the following concepts are highlighted:

§ Sort and signature - these concepts allow you to classify both media elements and operations with them according to their types (for operations - according to the types of their arguments and return value).

§ Predicates are relations on elements of the carrier. This allows you to determine the range of possible values ​​by imposing restrictions (requirements) on permissible values, as well as work with arbitrary logical expressions in a natural interpretation, without being forced to interpret them as membership functions for sets or as multi-valued operations.

On this basis, it is possible to consider abstract data types from a single holistic logical-algebraic point of view, including questions about constructors (types and values), selectors and property modifiers for objects of this type.

The concepts of “data structure” and “abstract data type” are very close in some ways. One can, of course, assume that these concepts are simply two views of the same thing. The way an ADT represents values ​​is always based on some data structure, less or more complex, and the implementation of operations on such values ​​naturally depends on this chosen data structure. On the other hand, if we really want to, we can always design the data structure that interests us as an ADT.

But still we will distinguish between these two concepts, taking into account:

§ Abstract data type - implies a certain level of abstraction in order to fix an applied (domain-oriented) data type, regardless of the methods of its implementation, and it is possible to include this data type in an application library, well, at least for the specific development of a specific software system. An ADT may have several alternative implementations based on different data structures.

§ Data structure is rather a scheme for organizing and managing data, which requires appropriate specifications when used in specific situations to solve specific problems.

Abstract data types primarily naturally include mathematical basic algebraic systems - sequences, sets, relations and mappings (functional relations, functions). But in programming, the foreground is not the study of the general properties of these mathematical concepts, but the possibility of using them in the development of models for solving problems in the subject area, algorithms for solving these problems, and the effective implementation of the developed algorithms. Therefore, in programming in the form of ADT, on the one hand, limited versions of these basic algebraic systems are usually formalized, and on the other hand, expanded with specialized sets of operations that are of pragmatic interest from the point of view of the field of application.

2.1. Sequence.

An infinite (finite) sequence is formally defined as a function whose domain is the set of positive integers: f(i)= , . In many cases, it is more convenient to index a sequence from scratch; then the domain of / will be the set of non-negative integers. Similarly, we define a finite sequence or list as a function whose domain is the set (1, 2, ..., ).

The concept of sequence, in which elements follow each other, is fundamental in programming. The sequence appears in the line-by-line output of the code computer program, where the order of commands determines the actions performed by the program. The sequence of network packets constitutes a message email, since the message will only make sense if the packets are received in the same sequence in which they were sent. Sequences represent important relationships between objects such as "next" and "previous". In addition, sequences are often used to implement other data structures, that is, they represent the blocks on which the design of such structures is based.

¨ The set of possible values ​​is a finite sequence of elements of the same type.

¨ Set of operations:

§ Insert element into sequence.

§ Delete element from the sequence.

§ Look– a function that returns the value of a sequence element.

Varieties of this type of ADT differ in the way they access sequence elements and restrictions on where elements can be inserted and deleted.

For ADT of this type stack , queue And deque from Double Ended Queue - two-way queue ) typical destructive reading, because access to elements (for all three operations) is limited to one end of the sequence and the “look at another element” operation can be performed only by removing the interfering elements. For ATD vector(array, vector),file (file) And linear list access restrictions ensure non-destructive reading, therefore it is of particular importance ( derivative) sequence lookup operation.

Restrictions on access to sequence elements naturally affect the semantics of basic operations. Serial access based on the concept current position and allows access (movement, navigation) to one (or both) of the ends of the sequence and to an adjacent position (to the left, to the right, or both) relative to the current one. The place where the main operations are applied in this case is usually tied to the current position. Direct (positional, random) access based on a global concept position element in a sequence and provides immediate access to the element if its position is known. For example, in ATD dynamic vector (dynamic array, vector) , position is the index of the element. But in other implementations of other kinds of sequences, the position identifier may be implemented differently.

The concepts of “number” and “position” of an element are close, but may not coincide:

§ Number- this is the actual serial number of the element in the sequence. But the serial number of an element changes as a result of insertion and deletion operations of previous elements, this creates a number of inconveniences in identifying sequence elements.

§ Position- is similar to an ordinal in the sense that for an element at a given position it allows us to talk about the previous and next element of the sequence (and their position). But the element's position value does not change as a result of previous element insertions and deletions, so the element's position value can be saved and used to access that element in the future. For example, in a linked list implementation of a sequence, the concept of "position" may be represented by a pointer to an element, and in other implementations may be represented by another kind of identifier specifically supported by the implementation.

For the Sequence ADT, additional operations of the form are of interest: concatenate two sequences, decouple into two sequences. For example, in ATD string This type of operation is actually basic.

For different types of ADT “Sequence”, varying efficiency in the implementation of various operations is achievable. For example, if an implementation offers efficient direct access to elements of a sequence, then most likely the execution time of an insert operation in the middle of the sequence leaves much to be desired. Various types (and implementations) of the Sequence ADT make different proposals to the programmer both regarding the composition of operations and the effectiveness of their implementation. Therefore, in programming practice, it is usually not so much the universal versions of this (as well as other) ADTs that are of more interest, but rather the specialized ones, and the programmer must make the appropriate choice, taking into account their use in solving problems in the subject area.

2.2. Set.

¨ The set of possible values ​​is a finite set of elements of the same type.

¨ Set of operations:

§ Insert element into a set.

§ Delete element from a set.

§ Belong– a function that returns true if the element belongs to the set.

For such a fundamental concept of classical mathematics, it seems natural to expand the set of operations to the standard classical one. But for a number of pragmatic reasons in programming, such an ADT of a general (universal) type is of limited interest. For example, enabling the operation of combining intersecting sets requires the removal of intersection elements during implementation. This can significantly complicate the implementation of this operation. On the other hand, the presence of duplicates may not be critical from the perspective of the problem being solved; in this case, ADTs are multisets. The fundamental importance of the concept of set, of course, is manifested by the presence of a rich set of specialized extensions of this basic ADT “Set”, which are widely used in programming practice, both due to the powerful expressive power of this toolkit in developing models of problems and algorithms for solving them, and due to the presence effective methods implementation of these ADTs.

Specialized extensions of the ADT “Multiple” are considered in various directions:

§ Close to the concept of “set” is the concept of “set”. Set (Bag, MultiSet) – just as a set is a family of elements, regardless of whether the order relation is specified on the elements, but the elements in the set can be repeated in value. Generally speaking, a set can be represented as a set, for example, whose elements are pairs of [element value, number of occurrences in the set].

§ In practical applications, elements of sets are often identified, i.e. an element is a pair [the key of the element, the actual value of the element], the Dictionary ADT is an example of such a specialized extension of the Set ADT. The preferred case is when element key is unique, i.e. a set cannot contain two elements with the same key. But it is possible that the key used is non-unique, i.e. ambiguously identifying the actual value of the element. Generally speaking, a set (and set) with a non-unique key can be represented as a set with a unique key by complicating the element's value type, for example, by considering the set of values ​​of the previous type (with the same key) as the element's value.

§ It seems natural to define an order relation, partial or linear, on a set, the “Queue with Priority” ADT is an example of such a specialized extension of the “Set” ADT. Similarly, in the subject area of ​​the problem being solved, other relations on the set may be of interest.

§ The fundamental position in mathematics is occupied by the concept of an equivalence relation and, accordingly, the concept of partitioning a set into equivalence classes. Naturally, this concept is widely used in practical developments problem solving models subject areas. ADT “Family of disjoint sets” (Disjoint Sets, Partitions, Partitions) is an example of a corresponding specialized extension of the ADT “Set”.

For specialized extensions of the “Set” ADT, the above-mentioned operations are naturally refined accordingly and new operations of interest appear.

2.3. Dictionary, Map, another name – associative array.

¨ The set of possible values ​​is a finite set of elements of the same type, of the form , where Key is the unique key of the element, Value is the value itself.

¨ Set of operations:

§ Insert element (with key) into a set.

§ Delete an element (specified by a key) from a set.

§ Find element– a function that returns the value of an element by key or an “empty” value if an element with such a key is not in the set.

ADT "Dictionary" is a specialized version of the concept of (stored) mapping (keys to values), widely used in practical programming. But for some subject areas, it may be more convenient to design an ADT "Mapping" , closer to the classical mathematical definition.

2.4. Priority queue.

¨ The set of possible values ​​is a finite set of elements of the same type. On the sets (possible values) a linear order relation is specified, which is interpreted as a comparison of elements by priority. The priority level can be highlighted as component element values ​​or calculate the given function from the element value.

Note that such a set of possible values ​​can also be interpreted as a set of sequences (with a list of its elements in a given linear order).

¨ Set of operations:

§ Insert element in a (linearly ordered) set.

§ Remove minimal element from a set.

§ Find the minimum– a function that returns the value of the minimum element in a set.

(Significant) variations of this ADT with additional operations are also considered:

§ Decouple the queue into two according to the given value (priority) of the element - into a queue of elements with a lower priority and a queue of the rest.

§ Concatenate two queues, one of which has all its elements having a higher priority than all the elements of the other queue, into one priority queue without preserving the original concatenated queues.

§ Combine two disjoint ordered sets (merge two such queues) into one ordered set (one queue with priority), also without preserving the original merged ones.

§ Decrease the value (priority) of a given element.

§ Remove a (randomly) specified element from a set.

2.5. Disjoint Sets, Partitions, Partitions.

¨ The set of possible values ​​is finite sets (families) of disjoint finite sets. Family elements have been identified, i.e. each set in the family has a (unique) name.

¨ Set of operations:

§ Merge(A,B)– an operation of the form A:= A È B without preserving the original combined sets (which means the new value of the family will remain a family of disjoint sets, and their number will decrease).

§ Find set– a function that returns, for a given x, the name of a set X in the family such that x О X.

2.6. Trees, graphs and general relations.

In discrete mathematics, special attention is paid to (finite) relations of the form - tree, graph and network (multigraph, hypergraph), which have a clearly defined geometric interpretation:

¨ Graph – (finite) binary relation (symmetric – in the case of undirected graphs), E Í V 2, where V is the set of vertices, and E is the set of edges of the graph.

In discrete mathematics, E is usually defined not as a set, but as a set of edges of a graph; this allows us to consider graphs in which a pair of vertices can be connected by several edges (for example, marked differently in some way).

¨ Tree is a binary relation of (strict) partial order, additionally satisfying the requirements (hierarchy, arboreality):

§ from the fact that x<у,z следует, что у и z сравнимы, т.е. либо у£z либо z£у (х<у трактуется как: х встречается раньше у в пути к корню дерева, х – потомок, у - предок);

§ in the set V (tree vertices) there is a largest element (tree root).

Trees can be distinguished if the order of the sons of (at least one) tree vertex is different. Ordered tree – a tree in which for each vertex an order is specified on the set of child vertices, i.e. children can be defined as first, second, etc.

¨ Net – this is a relation of a general form, which can be interpreted as a generalization – E Í VÈV 2 È...V k , or can be interpreted as a relation (E Í V k) with a set of elements V having an “empty” (fictitious) element.

These concepts are, of course, widely used in the development of domain problem models. But just as in the case of sets, for a number of pragmatic reasons in programming, such an ADT of a general (universal) form is of limited interest. More precisely, various types of representation of trees, graphs and networks are, of course, widely used in programming practice. But combining them with a universal set of operations and designing such a universal ADT seems useful only in simple situations.

The fundamental role of trees and graphs appears rather in the context of the applied problem when choosing data structures for the effective implementation of the selected ADT and the algorithm for solving the problem as a whole. But in such a context, both their way of representing and the set of operations with these trees, graphs and networks are naturally specialized in accordance with the specific context.