It is customary to call an abstract type a data type that is not explicitly available in a programming language; in this sense, this concept is relative - a data type that is absent in one programming language may be present in another.
Abstract data type (ADT) is determined regardless of how it is implemented:
the set of possible values \u200b\u200bof this type,
and a set of operations on values \u200b\u200bof this type.
The use of ADT can be limited to the stage of software development, but for its explicit use in the program, you must have its implementation based on the already existing (and previously implemented) data types in the programming language:
a way of representing values \u200b\u200bof this type,
and the implementation of operations on values \u200b\u200bof this type.
ADT is not predefined in the programming language, and even more, the operations for constructing such types, predefined in the language, shift the question of how to represent values \u200b\u200bof this type and how to implement operations with values \u200b\u200bof this type on the programmer-developer. Therefore, for such data types, the question of the choice of definitions and methods of implementing operations of the form constructor (values \u200b\u200band data stores) of this type, selector and modifier components (values \u200b\u200band data stores) of this type are the responsibility of the developer-programmer.
In the concept of ATD, the concepts interface open to the user, and realization hidden from him. The special role of these concepts in the concept of ADT is associated with the fundamental provision on the independence of the concept of ADT from the method of its implementation.
In modern "practical programming languages", the predefined type construction operation is usually used to construct ADTs 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 the way of constructing and accessing such data. 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 data types, at an early stage, the important role of the concept “ type parameterization ". Indeed, for example, the "Stack" ADT does not depend on the type of stack elements, but it is impossible to implement this ADT by pointing to "elements of the same type". In the Ada programming language, the corresponding means for constructing parameterized data types were included initially, and in modern "practical programming languages" which means have appeared only since the advent of the development of the STL library. Today the concept of "generic programming" occupies a significant position in practical programming due to the inclusion in "practical programming languages" constructors of parameterized data types (templates, template , generic) .
All of the above means that from a methodological and theoretical point of view, a more detailed and precise definition of the concept of "abstract data type" is needed. In theory, the concept of "abstract data type" is usually defined as multi-sorted (multi-base) algebraic system , in which, in addition to the set of possible values \u200b\u200b(carrier) and a 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 by their types (for operations, by the types of their arguments and return values).
Predicates are relations on the elements of the carrier. This makes it possible to determine the range of possible values \u200b\u200bby imposing restrictions (requirements) on admissible values, as well as to work with arbitrary logical expressions in a natural interpretation, without forcing them to interpret them as membership functions for sets or as multivalued operations.
On this basis, it is possible to consider abstract data types from a single integral 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 somewhat similar. You can, of course, assume that these concepts are just two views of the same thing. The way of representing ADT values \u200b\u200bis always based on some data structure, less or more complex, and the implementation of operations with such values \u200b\u200bnaturally depends on this selected data structure. On the other hand, if we want to, we can always design the data structure that interested us as an ADT.
But still we will distinguish between these two concepts, given:
An abstract data type implies a certain level of abstraction for the purpose of fixing an applied (domain-specific) data type, regardless of how it is implemented, and it is possible to include this data type in an application library, well, at least for a specific development of a specific software system. An ADT can have several alternative implementations based on different data structures.
Data structure is rather some scheme of data organization and management, which assumes appropriate concretization when it is used in specific situations when solving specific problems.
First of all, the abstract data types naturally include mathematical basic algebraic systems - sequences, sets, relations and maps (functional relations, functions). But in programming, the foreground is not the study of the general properties of these mathematical concepts, but the possibilities of their use 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 ADTs, on the one hand, limited versions of these basic algebraic systems are formed, and on the other hand, they are extended with specialized sets of operations that are of pragmatic interest from the point of view of the field of application.
The data type describes many objects with similar properties. All traditional programming languages \u200b\u200buse a set of basic data types (real, integer, string, character). Base data types obey a predefined set of operations. For example, the basic data type integer allows you to perform operations such as addition, subtraction, multiplication, division.
Traditional programming languages \u200b\u200binclude 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. Operations such as WRITE, READ, DELETE, UPDATE can be performed on a record. You cannot define new operations for basic data types.
Like basic data types, abstract data types (ATDs) 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 implementation of methods.
In some OO systems (such as Smalltalk), basic data types are implemented as abstract.
To create an abstract data type, you must provide:
· Type name;
· Representation of data or variables of an instance of an object belonging to ATD; each instance variable has a data type that can be either a base type or a different ATD;
· ATD operations and restrictions are implemented using methods.
The ATD definition rebuilds the class definition. Some OO systems use the type keyword to distinguish between classes and types when referring to data structures and class methods, and the class keyword when referring to a set of object instances. Type is a more static concept, while class is mostly about runtime. The difference between an OO class and an OO type can be illustrated with an example. Let's assume you 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 (class).
ATD together with inheritance allows you to create complex objects. A complex object is formed by combining other objects that are in complex relationships with each other. An example of a complex object can be found in security systems that use different types of data:
1. standard (tabular) data about the employee (full name, Tab. No., etc.);
2. bitmap for storing the employee's photo;
The ability to handle such a complex data environment with relative ease increases the value of OO systems in today's database market.
Abstract data type
Abstract data type (ATD) 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 whole 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 implementation-independent functions of the type to operate on its values. Specific implementations of ADTs are called data structures.
In programming, abstract data types are usually represented as interfaces that hide the corresponding type implementations. Programmers work with abstract data types exclusively through their interfaces, as the implementation may change in the future. This approach is consistent with the principle of encapsulation in object-oriented programming. The strong point of this technique is implementation hiding. Once only the interface is published outside, then as long as the data structure supports this interface, all programs working with the given structure of the abstract data type will continue to work. Developers of data structures try, without changing the external interface and semantics of functions, to gradually refine the implementations, improving the algorithms in terms of speed, reliability and used memory.
The difference between abstract data types and data structures that implement abstract types can be illustrated by the following example. The abstract data type list can be implemented using an array or a linear list using various dynamic memory allocation methods. However, each implementation defines the same set of functions, which should work the same (in performance, not speed) for all implementations.
Abstract data types allow you to achieve modularity of software products and have several alternative interchangeable implementations of a separate module.
Examples of ADT
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 enumerating its methods and properties, without creating their concrete implementation. Information technology topics in general EN Abstract Data TypeADT ... Technical translator's guide
In programming theory, any type whose values \u200b\u200bare values \u200b\u200bof 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, integer data type (English Integer), in computer science, one of the simplest and most common data types in programming languages. Serves to represent whole numbers. A lot of numbers of this type represent ... ... Wikipedia
This term has other meanings, see set (meanings). A set, a type and data structure in computer science, is an implementation of a mathematical object set. Data type set allows you to store a limited number of values \u200b\u200b... ... Wikipedia
Some programming languages \u200b\u200bprovide a special data type for complex numbers. The built-in type makes it easy to store and calculate complex values. Contents 1 Arithmetic over complex 2 Support in languages \u200b\u200b... Wikipedia
This term has other meanings, see Index. Pointer diagram A pointer (pointer) is a variable whose value range consists of memory addresses and a 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 \u200b\u200bthat are not of their own type. This concept is implemented in several programming languages, in particular in ML and Haskell, and in ... ... Wikipedia
A trait is an abstract type used in computer science as "a simple conceptual model for structuring object-oriented programs." Traits are similar to mixins, but can include class method definitions. ... ... 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 as just a top or a "fixed" symbol (⊤), a universal type, that is, a type that contains every possible object in the desired type system. The highest type is sometimes called ... ... Wikipedia
Good day, Khabrav residents!
The following post is a summary of my thoughts on the nature of classes and ADTs. These reflections are complemented by interesting quotes from books by software development gurus.
Introduction
Let's start by smoothly approaching the definition of ADT. ADT is primarily a data type, which means the following: the presence of certain available operations on elements of this type;
as well as the data on which these operations are performed (range of values).
What does the word “abstract” mean? First of all, the concept of "abstractness" means focusing on something important and, at the same time, we need to distract ourselves from unimportant, at the moment, details. The definition of abstraction is well covered in the book by Grady Booch. The definition sounds like this:
Abstraction is the selection and imparting of a set of objects with common properties that define their conceptual boundaries and distinguish them from all other types of objects.
In other words, abstraction allows us to “shed light” on the data of objects we need and, at the same time, “shade” those data that are not important to us.
So what happens if you merge the concepts of “data type” and “abstraction” together? We will get 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. From here, we come to the concept of ADT:
An ADT is a data type that hides its internal implementation from clients.
Surprisingly, by applying abstraction, the ADT allows us not to think about the 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 constitute the interface, you need to focus on the data that will implement the specified behavior of the ADT. As a result, we will get some kind of data structure - a mechanism that allows you to store and process data. At the same time, the beauty of ADT is that if we want to change the internal representation of the data, then 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. The ADT encapsulates this data, which allows you to change the behavior of objects of this type, and not the entire program.
ADT advantages
The use of ADT has many advantages (all described advantages can be found in the book by Steve McConnell "Code Perfect"):
- Encapsulation of implementation details.
This means that once we encapsulate the details of the implementation of the ADT operation, we provide the client with an interface with which he can interact with the ADT. By changing the implementation details, the customer perception of ADT will not change.
- Reduced complexity.
By abstracting from implementation details, we focus on the interface, which is what the ADT can do, rather than how it is done. Moreover, ADT allows us to work with the essence of the real world.
- Limiting the scope of data use.
Using the 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 represent the entire interface in terms of domain entities, which, you see, increases the readability and information content of the interface.
Steve McConnell recommends representing low-level data types, such as stack or list, as ADTs. Ask yourself what the list is. If it presents a list of bank employees, then consider 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 primarily about the ADT. At the same time, as Steve McConnell said, you program not in the language, but with the help of the language. That is, you will program outside the language, not limited to thoughts in terms of arrays or simple data types. Instead, you will think at a high level of abstraction (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 \u003d ADT + Inheritance + Polymorphism.
So why should one think about ADTs when designing classes. Because, first, we must decide which operations will make up the interface of the future class, which data to hide, and to which to provide public access. We need to think about making the interface highly informative, easy to optimize and validate the code, and how we can provide the correct abstraction so that we can think about real-world entities rather than low-level implementation details. I believe that it is after the definition of the ADT that we should think about the issues of inheritance and polymorphism.
It should be noted that the concept of ADT has found a wide application in OOP, because it is this concept that complements OOP and allows you 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.
Used sources:
Steve McConnell - Code Perfect;
Robert Sedgwick - "Algorithms in Java".
Appendix to the working program for the discipline "Structures and algorithms for data processing in a computer"
The abstract data type "List".
List - a sequence of elements of a certain type a1 , a2 , ..., a n, where nhttps://pandia.ru/text/78/308/images/image001_307.gif "width \u003d" 13 "height \u003d" 16 "\u003e 1, then a1
Is called the first element and an - the last element of the list. The items in the list are linearly ordered according to their position in the list. Ai element preceded element ai+1 for i = 1,2, n-1 and ai should behind ai-1 for i = 2,3, n. Each list item ai It has position i, i=1,2, n. Position exists in the list , signifying the end of the list - nil. It follows the last item in the list.
Operators of the ADT "List":
1. INSERT ( x, R,L). This statement inserts an object x in position r in the list L, moving elements from position p and further to the next higher position. So if the list L consists of elements a1 , a2 , ..., andn a1, a2, ..., ap-1, x, ap, ..., an.... If p takes the value nil , then we will have a1 , a2 , ..., an , , x... If the list L no position r, then the result of this statement is undefined.
2. LOCATE(x , L ). This function returns the position of the object x in the list L. If the object is in the list x occurs several times, then the position of the first object from the beginning of the list is returned x. If the object x not on the list Lthen returns nil.
3. RETRIEVE(p , L ). This function returns the element at position r in the list L. The result is undefined if p \u003d 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 , ..., andn , then after executing this operator it will look like a1, a2, ...,, ap- i , ap+ i, ..., andn. The result is undefined if the list contains L no position r or r = nil.
5. NEXT ( p, L ) and PREVIOUS (p, L ). These functions return respectively the next and previous positions from the position r in the list L. If a r - last position in the list L, then NEXT (p, L) = nil... NEXT function is undefined when p \u003dnil... PREVIOUS function is undefined if p \u003d 1. Both functions are undefined if 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.
List view using an array:
List view using singly linked list:
Legend:
- a pointer to the beginning of the list,
· last - pointer to the last item in the list ,
· maxlenght - maximum length (number of elements) in the list.
List view with doubly linked list:
Exercises:
1. Write programs for inserting, deleting and searching elements of a sorted list, using to implement the list
§ array,
§ pointers.
2. Write a program to merge
§ two sorted linked lists,
§ n sorted linked lists,
3. Given a polynomial of the form
p (x) = c1 xe1 + c2 xe2 + + fromnxn, Where e1\u003e e2\u003e ...\u003e en> 0.
Such a polynomial can be represented as a linked list, where each element has three fields: one for the coefficient fromi 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 addition and multiplication of polynomials using this representation.
4. Implement the LIST ADT for any data type and its INSERT, LOCATE, RETRIEVE, DELETE, NEXT, PREVIOUS, MAKENULL, PRINTLIST statements:
§ the list is given 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
The abstract data type "Stack".
Stack - it is a special type of list in which all insertions and deletions are done at only one end called top , (top). The access method is used for the stack LIFO (last-in-first-out - last in - first out).
Operators of ATD "Stack":
1. MAKENULL(S). Empty the S stack.
2. TOP(S). Returns the item from the top of the stack S. Usually 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 item from the top of the stack (pops from the stack), in terms of list statements this statement can be written as DELETE (FIRST (S), S).
4. PUSH(x, S ). Inserts an element x to the top of the stack S (pushes the item onto the stack). The item that was previously at the top of the stack becomes the item next to the top, and so on. In terms of general list operators, this statement can be written as INSERT (; c, FIRST (S), S).
5. EMPTY(S) ... This function returns true if the 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 set as an array,
The stack is set as a singly linked list.
Work program section 2.1.2
The abstract data type "Queue".
Turn (queue) is a special type of list where items are inserted from one end called hind (rear), but removed from another, front (front). Queues are also called "FIFO Lists" (FIFO stands for first-in-first-out: first in, first out). Operators performed on queues are similar to stack operators. The essential difference between them is that new elements are inserted in end of list rather than at the beginning, as in stacks.
Operators of the ADT "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 at the end of the queue Q.
With list operators, this operator can be executed as follows: INSERT (x, END (Q), Q ).
4. DEQUEUE(Q) removes the first element of the queue Q . Also implementable with list statements like DELETE (FIRST (Q), Q).
5. EMPTY(Q) returns true if and only if Q is an empty queue.
cyclical array:
Legend:
Q - turn,
Q. front - pointer to the beginning of the queue,
Q. rear - a pointer to the end of the queue.
Queue representation with singly linked list:
Exercises:
Implement the QUEUE ADT for any data type and its MAKENULL, FRONT, ENQUEUE, DEQUEUE, EMPTY statements.
The queue is specified as a circular array,
The queue is specified as a doubly linked list.
Abstract data type "Tree".
Tree is a collection of elements called knots (one of which is defined as root ), and relationships ("parent") that form a hierarchical structure of nodes. Nodes, just like list items, can be any type of item. Formally, a tree can be defined recursively as follows.
1. One node is a tree. The 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 p parent of nodes n1 . n2 , ..., nk ... In this tree p 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 null tree , that is, a "tree" without nodes, such a tree is denoted by the word nill .
Example: Aboutchapter of the book can be schematically represented by a tree. The parent-son relationship is displayed as a line. Trees are usually drawn from top to bottom so that the parents are above the "children".
DIV_ADBLOCK135 "\u003e
Node height tree is the length of the longest path from this node to any leaf. In the example, the height of the node Chapter 1 is equal to 1, node Chapter 2 - 2, and node 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.
Sons of a node are usually ordered from left to right. Therefore, the two trees in the figure are different, since the order of the sons of the node and different. If the order of sons is ignored, then such a tree is called disordered , otherwise the tree is called orderly .
Operators of ATD "Tree":
1. PARENT(n, T). This function returns the parent of the node p in the tree T. If a p is a root that has no parent, then in this case it returns nill... Here nill indicates that an out-of-bounds tree has occurred.
2. LEFTMOST__ CHILD(n , T). This function returns the leftmost child of the node. n in the tree T. If a n is a leaf (and therefore does not have a son), then it returns nill.
3. RIGHT_ SIBLING(n , T). This function returns the node's right sibling p in the tree Tor value nill,. if it does not exist. This is what the parent is for r node p and all the sons of the node r, then among these sons is the node immediately to the right of. node p.
4. LABEL(n , T ). Returns the label of the node n... wood T.This function requires labels to be defined on the tree nodes.
5. CREATE(v , T 1 , T 2 , ..., Ti ,) is a family of functions that create a new root for each i \u003d 0, 1, 2, ... r with label v and then for this root creates i sons who become the roots of subtrees T1 , T2, ....Ti;. These functions return a rooted tree r... Note that if i \u003d 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 a T - empty tree then returns nill.
7. MAKENULL(T ). This operator makes the tree T empty tree.
Representing a tree using an array of parents:
Tree view using linked lists:
Representing the tree by means of left sons and right brothers.
Designations in the figure:
nodespace – an array of tree nodes,
- label
–
node label, header
–
the index of the left son in the list of sons,
cellspase – an array of lists of sons of nodes,
- node
–
pointer to a node in an arraynodespace
,
next
–
the index of the right son in the list of sons.
Exercises:
1. Given a tree:
DIV_ADBLOCK137 "\u003e
§ the tree is given as an array of node records containing the index of the leftmost son, the index of the right sibling and a label,
A connected binary tree is specified using pointers to 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
The abstract data type "Set".
Lots of is usually depicted as a sequence of its elements, enclosed in curly 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 essential, so you can write (4, 1) in the same way as (1, 4), when writing the same set. The set is not a list (at least because of the arbitrary order of elements). There are no duplicate elements in the set ((1, 4, 1) is not a set).
The fundamental concept of set theory is the concept of the relation belonging to the set indicated by the symbol. Thus, the entry x x does not belong to the set AND", i.e. x not a member of the set AND... There is a special set, denoted by a symbol called empty, many , and which has no elements. Set DIV_ADBLOCK138 "\u003e
They say that the multitude AND contains in the set IN (or turns on in a lot IN), written A IN or IN ANDif any element of the set AND is also an element of the set AT. When A IN also say that the set ANDis an a subset of the set AT.
For example, (1, 2) https://pandia.ru/text/78/308/images/image019_36.gif "width \u003d" 15 "height \u003d" 15 src \u003d "\u003e IN and AB, then the set A is called own, true or a strict subset multitudes AT.
The main operations performed on sets are union, intersection, and difference. Consolidation sets AND and IN (denoted AND IN) is called a set consisting of elements belonging to at least one of the sets A and AT.
Intersection sets AND and IN (denoted AND IN)is called a set consisting only of those elements that belong to the set AND, and the set AT. Difference sets ANDand IN (denoted A\ B) is called a set consisting only of those elements of the set ANDthat do not belong to the set IN.
For example, if A \u003d (a, b, c) and B \u003d (b, a), then A B \u003d (a, b, c, d), A B \u003d (b) and A \\ B \u003d (a, c ).
Operators of ADT "Set":
1. UNION(A, B, C) AND and IN FROM, equal AND AT.
2. INTERSECTION(A, B, C) has "input" arguments set AND and IN, and as a result - the "output" set FROM, equal AND AT..
3. DIFFERENCE(A, B, C) has "input" arguments set AND and IN, and as a result - the "output" set FROM, equal A \\ B.
4. MERGE( A , B, C) operator performs 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 have no common elements). The operator assigns to the set FROM value AND IN, but the result will be undefined if A B, i.e., in the case when the sets AND and IN have common elements.
5. member(x, A ) has arguments set AND and object x of the same type as the elements of the set AND, and returns a boolean value true (true) if xa "," b "," c ")) \u003d "and". The operator MAX.
11.EQUAL(A , IN ) returns the value true if and only if the sets AND 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 name (singular) of the set that has an element x.
Set representation:
The set can be specified using an array or a linked list.
Exercises:
1. Two sets A \u003d (1, 2, 3) and B \u003d (3, 4, 5) are given. What will be the result of executing the following statements?
UNION (A. B. 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 MAKENULL, UNION, INTERSECTION, MEMBER, MIN operators.
The set is specified using a fixed-length array and a pointer to the last occupied position in the array,
The set is specified using an unsorted linked list,
The set is specified using a sorted linked list,
Work program section 2.1.3
Special kinds of sets
Binary Search Tree Abstract Data Type
Binary search tree - a data structure for representing sets, whose elements are ordered by some linear ordering relation. Binary search trees can implement set operators INSERT, DELETE, MEMBER and MIN, and their execution time on average is of the order of O (log n) for sets consisting of p elements.
A characteristic 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 the elements stored in the nodes of the node's right subtree x, more than the element contained in the node x.
Binary tree examples:
https://pandia.ru/text/78/308/images/image023_7.jpg "width \u003d" 277 "height \u003d" 122 src \u003d "\u003e
The AVL tree view is the same as the binary search tree view.
Another kind of balanced search tree is 2-3 wood. The structure of a 2-3 tree differs from the structure of a binary search tree. For 2-3 trees, it is characteristic that all nodes have 2 or 3 sons, all paths from root to leaf have the same length, and all elements of the set are contained in leaves. Nodes 2-3 of the tree are divided into internal and terminal (leaves). Internal nodes are used only for routing tree searches. Each internal node contains the keys of the smallest elements of the second and third sons (if there is a third son) and pointers to the nodes of sons.
Binary search connected tree view:
A balanced connected 2-3 tree view:
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 an 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 will result from inserting elements 5, 2, 7, 0, 3, 4, 6, 1, 8, 9 into the empty set (represented as 2-3 tree).
5. Show the result of deleting element 3 from 2-3 of the tree obtained in the previous exercise.
3. Implement the Search Tree ADT for any data type and its INSERT, DELETE, MEMBER, and MIN statements.
The tree is given as a connected binary tree
Tree is given as 2-3 trees
Work program section 2.1.3
Abstract data type "Dictionary".
Dictionary - a set intended for storing "current" objects with periodic insertion or deletion of some of them. From time to time, it also becomes necessary to find out if a particular element is present in a given set. The dictionary is implemented using the Dictionary ADT with operators INSERT,DELETE and MEMBER... The dictionary operator set also includes the operator MAKENULL to initialize the 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 IN 1, under construction hash function h such that for any element x original set function h (x) takes an integer value from the interval 0, ..., IN - 1, which corresponds to the class the element belongs to x. Element x often call key, h ( x) - hash-value x, and "classes" - segments ... How to resolve hashing collisions (two elements of a set have the same value h (x)), open and private hashing are applied.
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 :) \u003di.
Dictionary representation with private hash table
The segment table stores directly the elements of the dictionary. Therefore, only one dictionary element can be stored in each segment. With private hashing, the technique is used re-hashing ... When trying to place an element x to 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 the element can be placed. The occupancy of each of these segments is sequentially checked until a free segment is found. The element is placed in it x ... Various collision resolution methods are used to set segment numbers when re-hashing. For example, linear hashing method, mid-square method, random hashing method
Exercises:
1. Suppose you use the hash function h (i) \u003d i% 7 to hash integers into a 7-segment hash table.
· Give the resulting hash table if the 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. Suppose you have a private hash table with 5 segments, a hash function h (i) \u003d i% 5, and a linear collision resolution technique. Show the result of inserting the sequence of numbers 23, 48, 35, 4, 10 into the 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
The abstract data type "Display".
Display - is a set, on the elements of which the function of displaying elements of the same type is defined ( areas of definition ) to elements of another type ( range of values ) of another type. Display M matches an element d of type domaintype from scope to element r of type rangetype from range: M(d) = r.Empty display does not contain any elements
Operators of ADT "Display":
1. MAKENULL(M ). Makes 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 a value to r M(d), if the latter is defined, and returns false otherwise.
Display view:mapping can be efficiently implemented using hash tables. Here x sets the value from the scope of the mapping definition, and the table element with h ( x ) - an element from the range.
Work program section 2.1.3
Priority Queue Abstract Data Type
Priority queue is a set for the elements of which the priority function is set, that is, for each element x set, you can calculate the function r( x )- element priority x , which usually takes values \u200b\u200bfrom a set of real numbers, or, more generally, from some linearly ordered set.
ADT "Priority queue" based on ADT "Set" with operators INSERT and DELETEMINand also with the operator MAKENULL to initialize the data structure. Operator INSERT for a priority queue is understood in the usual sense, while DELETEMIN is a function that returns the element with the lowest priority and, as a side effect, removes it from the set.
Queue representation with an ordered doubly linked list.
Queue representation with partially ordered connected tree:
The basic idea behind this implementation is to organize the elements of the queue in a binary tree. At the lower level, where some leaves may be missing, all missing leaves can be located only to the right of the present lower level leaves. More significantly, the tree partially ordered . This means that the priority of the node v no greater than the priority of any son of the node v, where node priority is the priority value of the item stored in this node. It can be seen from the figure that small priority values \u200b\u200bcannot appear at a higher level, where there are large priority values.
The DELETEMIN function returns the lowest priority item that must be the root of the tree. In order not to destroy the tree and to preserve the partial ordering of the priority values \u200b\u200bin the tree after the root is removed, the following actions are performed: the rightmost node is located at the lowest level and temporarily placed in the root of the tree. This element then descends down the branches of the tree (to lower levels), swapping places with the sons of lower priority along the way, until this element becomes a leaf or gets into a position where its sons will have at least no less priority.
Representation of a queue using an array containing the nodes of a partially ordered tree:
In an 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, is in the cell A, and the right son, if he exists, is in the cell A. Conversely, if the son is in the cell A[ i], then its parent in the cell A[ i%2] ... Tree nodes fill cells A, A, … A[ n] sequentially level by level, starting from the root, and inside 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 by inserting integers 5, 6, 4, 9, 3, 1, and 7 into an empty tree. What will be the result of successively applying three DELETEMIN statements to this tree?
2. Implement a Priority Queue ADT for any data type and its INSERT, DELETEMIN and MAKENULL statements
§ a partially ordered tree is implemented using pointers,
§ A partially ordered tree is implemented using an array.
Work program section 2.1.3
The abstract data type "Union of Sets".
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 in a certain order, as well as to check whether a certain object belongs to a particular set. These tasks are solved using operators MERGE (Drain) and FIND (To find). MERGE operator ( A, B, C) makes the set FROM equal to the union of sets AND and INif these sets do not intersect (that is, do not have common elements); this operator is undefined if the sets AND and IN intersect. FIND function ( x) returns the set that the element belongs to x; in the case when x belongs to several sets or does not belong to any one, the value of this function is undefined.
Operators of the ADT “Union of Sets”:
1. MERGE(A , IN) combines components ANDand ... IN, the result is assigned to either A or AT.
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 union of sets using arrays:
The set name is the same as the array index value setheaders (name 0 )
Legend:
setheaders - array of set headers:
§ from ount - the number of elements in the set,
§ firstelement - array indexnames with the first element of the set,
names – array of lists of elements of sets:
- setname
- the name of the set to which the element belongs, nextelement
- index of the next element in the list of this 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 many arcs E. Vertices are also called knots , and arcs - oriented ribs . The arc can be represented as an ordered pair of vertices ( u, w), where is the top and called 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.
Digraph example 1:
Digraph vertices can be used to represent objects, and arcs can be used to represent relationships between objects.
By in a digraph we mean a sequence of vertices v1 , v2 , … , vn , , for which there are arcs v1 -> v2 , v2 , -> v3, , ..., vn-1 , -> vn. This path starts at the top v1 and passing through the tops v2 , v3 , ..., vn-1 ends at the top vn. Path length - the number of arcs that make up the path, in this case the path length is p - 1 ... Consider one vertex as a special case of the path v as a path of length 0 from the vertex v to the 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 the last, are different. Cycle - it 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 is used tagged digraph , that is, a digraph in which each arc and / or each vertex has corresponding labels. The label can be a name, weight or value (arcs), or a data value of some given type.
Example 2 of a labeled digraph:
DIV_ADBLOCK149 "\u003e
3. Transitive closure algorithm (Warshall's algorithm):
For the graph 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 be and - arbitrary vertex of a digraph G = (V, E). Eccentricity (maximum removal) tops and defined as
max (minimum path length from the top w to the top v }
w V
Digraph center G called the top with the minimum 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
Eccentr-t |
||
| ||
5. Algorithm for traversing a digraph in depth (depth-first search):
When solving many problems related to directed graphs, an efficient method of systematic traversal of vertices and arcs of digraphs is required. This method is the so-called depth-first search - generalization of the preorder tree traversal method. Depth-first search begins by selecting the starting vertex v count 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 applied recursively. When all the peaks that can be reached from the peak v, will be "honored" with a visit, the search ends. If some vertices have not been visited, then one of them is selected and the search is repeated. This process continues until all the vertices of the digraph are traversed G.
6. Algorithm for constructing a deep spanning tree of a graph:
When traversing a graph using the depth-first search method, only certain arcs lead to unvisited vertices. Such arcs leading to new vertices are called tree arcs and form for the graph dFS spanning forest – deep spanning forest ... When constructing a forest, three types of arcs are also distinguished: reverse, direct, and transverse. Reverse arcs - such arcs that go from descendants to ancestors in the spanning forest. Straight arcs arcs are called that go from ancestors to true descendants, but which are not tree arcs.
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 also added to the forest from left to right, then all transverse arcs go from right to left.
For example, arcs D-\u003e C and G-\u003e D - transverse, arc C-> A - backward, there are no straight arcs.
When traversing a tree deeply, it is often convenient to number the vertices in the order they are visited. Such numbers are called depth numbers.
Digraph representation:
§ Representation of a digraph using an adjacency matrix:
Adjacency matrix for digraph G - this is a matrix AND 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 a representation of a labeled digraph also using an adjacency matrix, but for which the element A[ i, j] equal to arc label i -\u003ej. If arcs from the top i to the top j does not exist, then the value A [ i, j] cannot be the value of any valid label, but can be regarded as an "empty" cell.
Adjacency matrix for a labeled digraph (example 2):
§ Representation of a digraph using adjacency lists:
Vertex adjacency list i called the list of all vertices adjacent to the vertex i, moreover ordered in a certain way. Digraph G can be represented by means of an array HEAD (Title) whose element HEAD[i] is a pointer to the vertex adjacency list i.
 |
Operators of ATD "Orgraph":
The most common operators performed on directed graphs include read vertex and arc label, vertex and arc insertion and deletion, and arc sequence traversal.
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 a "zero" vertex is returned nil.
2. NEXT ( v, i) returns the index of the vertex adjacent to the vertex v, following index i. If a i - this is the index of the last vertex adjacent to the vertex v, then it returns 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 \u003d" 125 "height \u003d" 100 src \u003d "\u003e
An example of a disconnected graph:
Cycle (simple) is a path of (simple) length at least 3 from some 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 a "regular" tree if some vertex is designated as a root, and all edges are oriented in the direction from this root.
Loose trees have two important properties:
1. Each 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 be G = (V, E) -connected graph in which each edge ( r, w) marked with a number from(v, w), which is called cost of rib . Spanning tree count Gcalled a free tree containing all vertices V Count G. The cost the spanning tree is calculated as the sum of the costs of all edges included in this tree
The main algorithms for processing undirected graphs:
1. Building a minimum cost spanning tree (Prim's algorithm):
Many peaks are being built Ufrom which the spanning tree "grows". Let be V \u003d (1, 2, ...,n}. First U \u003d (1). At each step of the algorithm, an edge of least cost is found ( u, v) such that u U and v V \\ Uthen top v is carried over from the set V \\ U in a lot U... This process continues until the set U will not be equal to the set V.
The spanning tree construction sequence is given below.
https://pandia.ru/text/78/308/images/image048_12.gif "width \u003d" 501 "height \u003d" 384 src \u003d "\u003e
3. DFS traversal of undirected graphs:
Depth-first search is used to systematically traverse all the vertices of the 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 the undirected edge (v, w) can be represented as a pair of oriented arcs v -> w and w -> v.
Depth traversal can be used to construct a spanning tree.
The graph and the spanning tree obtained by traversing its vertices by the depth-first search method are shown below:
4. Breadth First Search on undirected graphs
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 during the traversal of any vertex v further we consider all vertices adjacent to the vertex v, that is, the vertices are scanned "in width". This technique can also be applied to directed graphs.
Just as with depth-first search, a spanning forest is created by traversing a graph using breadth-first search. If after reaching the top x when considering the rib (x, y) vertex at has not been visited before, then this edge is considered a tree edge. If the top at has already been visited, the rib (x, y) will be a transverse edge, since it connects vertices that are not related by inheritance to each other.
The Breadth First Spanning Tree is shown below.
Representation of 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 vand w seen 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 \u003d" 159 "height \u003d" 106 "\u003e
Representing an undirected graph using adjacency lists:
https://pandia.ru/text/78/308/images/image053_12.gif "width \u003d" 339 "height \u003d" 115 src \u003d "\u003e
1. Build:
minimum cost spanning tree using Prim's algorithm;
minimum cost spanning tree using Kruskal's algorithm;
spanning tree by depth-first search, starting from vertices a and d;
spanning tree by breadth-first search, starting from vertices a and d.
2. Implement the Prim and Kruskal algorithms.
3. Implement the spanning tree construction using depth-first search
§ for an undirected graph represented by an adjacency matrix,
§ for undirected graph represented by adjacency lists.
4. Implement spanning tree construction using breadth-first search
§ for an undirected graph represented by an adjacency matrix,
§ for undirected graph represented by adjacency lists.
