The development of abstract models for data and how to process that data is a critical component in the process of solving problems with 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 a connectivity problem using a union-search forest in "Introduction") ... In this lecture, abstract data types (hereinafter ADT) are considered, which allow you to create programs using high-level abstractions. Abstract data types allow you to separate the abstract (conceptual) transformations that programs perform on data from any particular representation of the data structure and any particular implementation of the algorithm.
All computing systems are based on levels of abstraction: certain physical properties of silicon and other materials allow an abstract model of a bit to be adopted, which can take binary values \u200b\u200b0-1; then, an abstract model of the machine is built on the dynamic properties of the values \u200b\u200bof a certain set of bits; further, on the basis of the principle of operation of a machine under the control of a program in a machine language, an abstract model of a programming language is constructed; and, finally, an abstract concept of an algorithm is constructed, implemented as a program in the C ++ language. Abstract data types make it possible to continue this process further and develop abstract mechanisms for certain computational problems at a higher level than that provided by the C ++ system, develop abstract mechanisms oriented to specific applications and suitable for solving problems in numerous application areas, and also create abstract higher level mechanisms that 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; we implement other abstractions in software; and use additional abstractions provided by previously written system software. High-level abstract designs are often based on simpler designs. At all levels, the same basic principle operates: it is necessary to find the most important operations in programs and the most important characteristics of the data, and then precisely define both at an abstract level and develop effective concrete mechanisms for their implementation. 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 to manipulate and the operations to be performed on them; (2) represent data in some data structure and implement operations; (3) and (most importantly) to ensure that these objects are convenient to use for solving applied problems. These points apply to simple data types as well, 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 of the structure mechanism called a class. Classes are extremely useful for creating levels of abstraction and are therefore considered the primary tool used for this purpose throughout the remainder of this book.
Definition 4.1. An abstract data type (ADT) is a data type (a set of values \u200b\u200band a set of operations for those values) that is accessed only through an interface. The program that uses the ADT will be called the client, and the program containing the specification of this data type is called the implementation.
It is the word that only makes the data type abstract: in the case of ADT, client programs do not have access to data values \u200b\u200bin any other way, except for the operations described in the interface. The representation of this data and the functions that implement these operations are in implementation and are completely separated by the interface from the client. We say that the interface is opaque: the client cannot see the implementation through the interface.
In C ++ programs, this distinction is usually a little clearer, since the easiest way to create an interface is to include data presentationbut specifying that client programs are not allowed direct access to the data. In other words, developers of client programs may know data presentationbut can't 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 software systems: we develop a set of conventions for the presentation of data (and also define a number of associated operations) and make these rules available through an interface so that they can be used by client programs that are part of a large system. The data type ensures that all parts of the system are consistent with the representation of the underlying system-wide data structures. As good as this strategy is, it has one flaw: if you need to change data presentation, then all client programs will need to be changed. Program 3.3 again gives us a simple example: one of the reasons for developing this type of data is the convenience of client programs with points, and we expect clients to have access to individual point coordinates when needed. But we cannot move to a different data representation (say, polar coordinates, or 3D coordinates, or even other data types for individual coordinates) without changing all 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 ++ class that immediately defines both the data and its associated operations. Program 4.2 is a client program that works with this data type. These two programs perform the same calculations as Programs 3.3 and 3.8. They illustrate some of the 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 \u200b\u200bmemory for (built-in) int data that can be accessed by the name i. In the C ++ language, there is the term object for such entities. When you write a definition such as POINT p in a program, you are said to create an object of class POINT, which you can refer to by name p. In our example, each object contains two data items, named x and y. As with structs, they can be referenced by names like p.y.
The data members x and y are called class data members. A class can also define member functions that implement the operations associated with that 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 member functions associated with an object by specifying their names in the same way as the names of data 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 in Program 4.1, is a special member function called a constructor: it has the same name as a class and is called whenever an object of that class needs to be created.
Program 4.1. Implementation of the POINT class (point)
This class defines a datatype that consists of a set of values \u200b\u200bthat are "floating point pairs" (assuming they are interpreted as points on a Cartesian plane), and two member functions defined for all instances of the POINT class: function POINT (), which is a constructor that initializes coordinates to random values \u200b\u200bfrom 0 to 1, and a distance (POINT) function that calculates the distance to another point. Data presentation is private, and only member functions can access or modify it. The member functions themselves are public and available to any client. The code can be saved, for example, in a file named POINT .cxx.
#include
Program 4.2. Client program for class POINT (finding the nearest point)
This version of program 3.8 is a client that uses the POINT ADT defined in program 4.3. The new operation creates an array of POINT objects (by calling the POINT () constructor to initialize each object with random coordinates). 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 memory area for a new object and then (using the POINT () function) assigns each of its two data items a random value in the range from 0 to 1.
This style of programming, sometimes referred to as object-oriented programming, is fully supported by the C ++ class construct. A class can be considered an extension of the concept of structure, where not only data is combined, but also operations with this data are defined. There can be many different objects belonging to the same class, but they are all similar in that their data members can take the same set of values, and the same set of operations can be performed on these data members - in general , they 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 the data stored in objects).
We are looking at the small class example described above just to get familiar with the basic features of classes; therefore it is far from complete. In real code for the point class, we will have a lot more operations. For example, Program 4.1 does not even have operations that allow you to find out the values \u200b\u200bof the x and y coordinates. As we'll see, adding these and other operations is a fairly straightforward task. In Part 5, we'll take a closer look at classes for point and other geometric abstractions, such as lines and polygons.
In C ++ (but not C), structs can also have functions associated with them. The key difference between classes and structs has to do with access to information, which is characterized by keywords.
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 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. 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 the 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, rather than 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, 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's worth noting that when developing classes in OOP, you should think about ADTs first of all. 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 defining the ADT that we should think about inheritance and polymorphism.
It is worth noting 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".
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 than that - the operations of 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 value).
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 implies appropriate concretization when it is used in specific situations when solving specific problems.
First of all, mathematical basic algebraic systems - sequences, sets, relations and maps (functional relations, functions) - naturally belong to abstract data types. 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.
Ministry of Education and Science of the Russian Federation
Federal State Budgetary Educational Institution
higher professional education
NATIONAL RESEARCH NUCLEAR UNIVERSITY "MEPHI"
Dimitrovgrad Engineering Technological Institute
Department Information Technology
To admit to protection "" 2012
Head chair Rakova O.A.
Course work
by discipline"Object Oriented Programming"
Topic:“Abstract data types. Lists "
Completed: student gr. VT-31
Shayakov A.F.
Head: Art. lecturer at the IT Department
Alenin V.A.
Norm controller: Art. lecturer at the IT Department
Alenin V.A.
Rating:
Protection date:
Dimitrovgrad, 2012
Ministry of Education and Science of the Russian Federation
Federal State Budgetary Educational Institution
higher professional education
NATIONAL RESEARCH NUCLEAR UNIVERSITY "MEPHI"
Dimitrovgrad Engineering Technological Institute
for term paper
Discipline: Object Oriented Programming
Topic: Abstract data types. Lists
Executor: Shayakov A.F.
Head: V.A. Alenin
1.Theoretical part:
Abstract data types. Object-oriented programming concept. Linear singly linked lists.
2.Practical part:
In C ++, write a program with an object-oriented structure to implement linear singly linked lists.
Terms of completion of work on schedule:
Theoretical part - 15% by week 5
Practical part - 80% by week 7
Experimental section - ____% by ____ week
Protection - 100% by week 10
Requirements for registration:
The settlement and explanatory note of the term paper should be submitted to electronic and hard copies;
The volume of the report must be at least 20 typewritten pages excluding attachments
RPZ is signed by the person responsible for regulatory control
Work manager _________________
Contractor ________________________
Date of issue "_____" ___________ 2012
A. F. SHAYAKOV THEME: ABSTRACT DATA TYPES. LISTS, Coursework / DITI, No. 230105.65-Dimitrovgrad, 2012. - 29 pages, fig. 11, bibl. name 10, applications 1.
Keywords: linear singly linked lists, C ++, object-oriented programming.
The object of research is linear singly linked lists.
The purpose of the work is to study linear singly linked lists and write a program in C ++ with an object-oriented structure for their implementation.
Conclusions: in this work, we have fully studied linear singly linked lists, as well as the methods of their representation in memory. The program written in C ++ fully complies with the object-oriented structure, correctly and efficiently performs its main task - it implements linear singly linked lists.
Introduction 6
1 Theoretical part 7
1.1 Abstract data types. Linear Lists 7
1.2 Concept of Object-Oriented Programming 8
2 Practical part 15
3 Testing 23
Conclusion 25
References 26
Appendix A 27
Introduction
Often in the process of working with data it is impossible to determine how much memory is required to store them; memory should be allocated during program execution in separate blocks as needed. Blocks are linked to each other using pointers. This way of organizing data is called a dynamic data structure because it resides in heap and resizes during program execution.
Linear lists are used in this work from dynamic structures. A dynamic structure, unlike an array or record, can occupy non-contiguous areas of RAM.
Dynamic structures are also widely used for more efficient work with data, the size of which is known, especially for solving sorting problems.
An element of any dynamic structure consists of two parts: informational, for the sake of storage of which the structure is created, and pointers that ensure the connection of elements with each other.
Theoretical part
1.1 Abstract data types. Linear Lists
Abstract data types are key in programming. Abstraction implies separation and independent consideration of interface and implementation.
Data abstraction involves the definition and consideration of abstract data types (ADTs) or, equivalently, new data types introduced by the user.
An abstract data type is a collection of data, along with many operations that can be performed on that data.
Linear Lists
In a linear list, each item is associated with the next and possibly the previous one. In the first case, the list is called simply connected, in the second - doubly connected. If the last element is linked by a pointer to the first, you get a circular list.
Each item in the list contains a key that identifies that item. The key is usually either an integer or a string and is part of the data field. Different parts of the data field can act as a key in the process of working with the list. The keys of different elements of the list can be the same.
You can perform the following operations on lists:
initial formation of the list (creation of the first element);
adding an item to the end of the list;
reading an element with a given key;
inserting an element at a given place in the list (before or after an element with a given key);
deleting an element with a given key;
ordering the list by key.
To work with a list in a program, you need to define a pointer to its beginning. You can also hover the pointer to the end of the list to make it easier to add new items to the end of the list.
1.2 Concept of object-oriented programming
According to the definition of the authority in the field of object-oriented methods of program development Grady Booch, “object-oriented programming (OOP) is a programming methodology that is based on representing a program as a collection of objects, each of which is an implementation of a certain class (type of a special kind), and classes form a hierarchy based on the principles of inheritance. "
The object-oriented methodology, like the structural methodology, was created with the aim of disciplining the process of developing large software packages and thereby reducing their complexity and cost.
An object-oriented methodology pursues the same goals as a structural methodology, but addresses them from a different starting point and in most cases allows you to manage more complex projects than a structured methodology.
As you know, one of the principles of project complexity management is decomposition. Grady Booch distinguishes two types of decomposition: algorithmic (as he calls decomposition supported by structural methods) and object-oriented, the difference between which, in his opinion, is as follows: “Separation by algorithms focuses on the order of events, and separation by objects gives special importance to factors, either causing actions, or being the objects of application of these actions ”.
In other words, algorithmic decomposition takes into account more the structure of relationships between parts of a complex problem, while object-oriented decomposition focuses more on the nature of relationships.
In practice, it is recommended to use both types of decomposition: when creating large projects, it is advisable to first apply an object-oriented approach to create a general hierarchy of objects that reflect the essence of the programmed task, and then use algorithmic decomposition into modules to simplify the development and maintenance of the software package.
OO programming is undoubtedly one of the most interesting areas for professional software development.
Objects and Classes
The basic building blocks of an object-oriented program are objects and classes. Substantially, an object can be represented as something felt or imagined and has well-defined behavior. Thus, an object can either be seen or touched, or at least know that it is, for example, represented as information stored in the computer's memory. Let's give the definition of the object, adhering to the opinion of GradiBuch: "An object is a tangible entity that clearly manifests its behavior."
An object is a part of the reality that surrounds us, that is, it exists in time and space (for the first time the concept of an object in programming was introduced in the Simula language). Formally, the object is difficult to define. This can be done through some properties, namely: an object has state, behavior and can be uniquely identified (in other words, has a unique name).
A class is a set of objects that have a common structure and common behavior. A class is a description (abstraction) that shows how to construct a variable of this class that exists in time and space, called an object. The meaning of the sentences "description of class variables" and "description of class objects" is the same.
The object has a state, behavior and passport (means for its unique identification); the structure and behavior of objects are described in the classes of which they are variables.
Let us now define the concepts of state, behavior and identification of an object.
The state of an object combines all its data fields (static component, i.e. unchanging) and the current values \u200b\u200bof each of these fields (dynamic component, i.e. usually changing).
Behavior expresses the dynamics of changes in the states of an object and its reaction to incoming messages, i.e. how an object changes its states and interacts with other objects.
Object identification (recognition) is a property that allows you to distinguish an object from other objects of the same or different classes. Identification is carried out by means of a unique name (passport), which is assigned to the object in the program, however, like any other variable.
It has already been said above that the procedural (as well as modular) approach allows you to build programs consisting of a set of procedures (subroutines) that implement specified algorithms. On the other hand, the object-oriented approach represents programs as a collection of objects interacting with each other. The interaction of objects is carried out through messages. Let's assume our object is a circle. Then the message sent to this object could be "draw yourself." When we say that a message is passed to an object, then in fact we are calling some function of this object (component-function). So, in the above example, we will call a function that will draw a circle on the display screen.
Encapsulation
Encapsulation is one of the fundamental principles of object-oriented programming, the idea of \u200b\u200bwhich is that all properties and methods are combined within an object.
The very name of the term "encapsulation" comes from the English word encapsulate, which literally means "to seal in a capsule" or "to cover with a shell". Thus, an object (capsule) contains methods and properties (content).
Encapsulation can be viewed in a broader sense, far beyond object-oriented programming in general. If we talk about encapsulation at the highest possible level of abstraction, then encapsulation can be thought of as the ability of an object to contain a variety of other objects. So in relation to a computer program, we can say that it encapsulates several modules, each of which in turn encapsulates some objects that encapsulate methods and properties, which, by the way, can also be objects, and so on.
Based on all of the above, another representation of encapsulation can be any tree structure in which any node of the tree encapsulates all of its immediate children, which can be both leaves (primitives that cannot encapsulate anything in themselves) and other nodes.
And yet, if we talk about object-oriented programming, then encapsulation is the union of data and methods within an object.
Sometimes speaking of encapsulation in object-oriented programming, the concept of encapsulation is equated with the concept of "black box" or data hiding, but they are not the same thing. Yes, in some object-oriented programming languages, using encapsulation, the developer can make his object a black box, but this is implemented using access modifiers, which are not available in all object-oriented programming languages. The very concept of encapsulation is much broader. And even more than that, we can make all properties and methods accessible from outside, that is, there can be no question of any black box, but encapsulation will still be present in any object. Therefore, hiding data by means of access modifiers is a consequence of encapsulation, but they are in no way identical concepts.
First, thanks to encapsulation, objects are no longer just user-defined data structures, the main purpose of which is simply to be logical to combine several separate data types within a new composite data type. Thanks to encapsulation, each object can now contain data that describes the state of the object, and its behavior, described in the form of methods. In other words, an object in object-oriented programming has ceased to be a primitive passive data type, the control of which is completely at the mercy of the external environment, but began to have its own behavior, one might even say, some will and reason, the ability to actively respond to external influences and change its state, and according to their own laws and regulations.
Second, encapsulation gives us the ability to control access to object data. Visibility limitation can also be viewed as a manifestation of the object's own will - the object itself decides what of its behavior or properties to make available to everyone, what to make available only to a certain range of objects, and what to make completely intimate, about which it will not know no other object. Why, but because only the object itself knows exactly how to work with it and how not. You can even say about a new philosophy of programming, where objects are more on objects on which some actions are performed, and, if I may say so, a new form of abstract synthetic mind, interacting with which you can achieve the desired result.
And I repeat once again that it is thanks to encapsulation that an object can be endowed with some will, reason, the ability to respond to external influences, and not be a passive data store.
Inheritance
Inheritance is one of the four most important mechanisms of object-oriented programming (along with encapsulation, polymorphism and abstraction), which allows you to describe a new class based on an existing (parent) class, while the properties and functionality of the parent class are borrowed by the new class.
In other words, the inherited class implements the specification of an already existing class (base class). This allows you to treat objects of the derived class in the same way as with objects of the base class.
Inheritance types
Simple inheritance
The class from which inheritance originated is called base or parent (eng. Baseclass). Classes that descend from the base are called descendants, descendants or derived classes (eng. Derivedclass).
Some languages \u200b\u200buse abstract classes. An abstract class is a class that contains at least one abstract method, it is described in the program, has fields, methods and cannot be used to create an object directly. That is, you can only inherit from an abstract class. Objects are created only on the basis of derived classes inherited from the abstract.
For example, an abstract class can be the base class "university employee", from which the classes "graduate student", "professor", etc. are inherited. Since derived classes have common fields and functions (for example, the field "year of birth"), these members of a class can be described in the base class. The program creates objects based on the classes "graduate student", "professor", but there is no point in creating an object based on the class "university employee".
Multiple inheritance
With multiple inheritance, a class can have more than one ancestor. In this case, the class inherits the methods of all ancestors. The advantage of this approach is greater flexibility. Multiple inheritance is implemented in C ++. Other languages \u200b\u200bthat provide this capability include Python and Eiffel. Multiple inheritance is supported in the UML.
Multiple inheritance is a potential source of errors that can arise due to the presence of the same method names in ancestors. In languages \u200b\u200bthat are positioned as inheritors of C ++ (Java, C #, etc.), it was decided to abandon multiple inheritance in favor of interfaces. You can almost always do without using this mechanism. However, if such a need nevertheless arose, then, to resolve conflicts of using inherited methods with the same names, it is possible, for example, to apply the visibility extension operation - "::" - to call a specific method of a specific parent.
An attempt to solve the problem of the presence of the same method names in ancestors was undertaken in the Eiffel language, in which, when describing a new class, it is necessary to explicitly indicate the imported members of each of the inherited classes and their naming in the child class.
Most modern object-oriented programming languages \u200b\u200b(C #, C ++, Java, Delphi, etc.) support the ability to simultaneously inherit from an ancestor class and implement methods of several interfaces with the same class. This mechanism allows you to largely replace multiple inheritance - interface methods must be overridden explicitly, which eliminates errors when inheriting the functionality of the same methods of different ancestor classes.
Practical part
To solve this problem, an object-oriented program structure is used. The program is represented by two classes and a main cpp-file containing a user interface for the convenience of working with lists.
The cList class is a linear, singly-linked list of objects of the cElement class.
The cElement class has the following structure:
cElement * next;
~ cElement (void);
void setdata (int);
void setref (cElement *);
cElement * getref ();
The data field of the int type contains the numeric value of the list item, the next field of the cElement * type contains the link to the next item in the list. The setdata and getdata methods are used to access the private data field of the class in order to get and, accordingly, set the value of this field. The setref method is used to set a link from the current to the next item in the list, and getref is used to navigate to the next item.
void cElement :: setdata (int sd)
int cElement :: getdata ()
returnthis-\u003e data;
void cElement :: setref (cElement * rf)
cElement * cElement :: getref ()
returnthis-\u003e next;
The implementation of these methods is extremely simple, as can be seen from their program codes presented above.
Now let's look at the structure of the cList class
#include "cElement.h"
cElement * head;
void Add (int);
void Insert (int, int);
void Remove (int);
void RemoveAll ();
This class contains a link to the head element of the list - head, of type cElement *. Storing this link is necessary for the correct execution of operations for adding, deleting data and printing the list. The fact is that when performing any of the above operations, the list items are iterated over to get to the desired one, since the list does not have random access to the elements, so it is more rational to start the enumeration from the "head" of the list. In addition to the link to the beginning of the list, each object of this class will have an elcount field that contains the number of elements in the list.
Let's continue our review of this class by examining the methods implemented in it for working with lists.
Add method - adding data to the end of the list.
As a parameter, this method accepts a numeric value (variable xd), which must be stored in the added list item.
void cList :: Add (int xd)
This is how a new element is created and the value of its numeric field is set:
cElement * temp \u003d newcElement;
temp-\u003e setdata (xd);
After that, the number of elements in the list is checked, if the list is empty, then the head element is created, otherwise the "ordinary" component of the list:
if (elcount \u003d\u003d 0)
temp-\u003e setref (NULL);
temp-\u003e setref (NULL);
p-\u003e setref (temp);
You can notice that the above construction uses the setref method of the cElement class, which is necessary to set a link to the next element in the list, otherwise the list will be unbound, which is fraught with data loss and incorrect program operation.
At the first start of the program, the method described above is used to sequentially add items to the list, which you can then work with; to stop input in the command line, you must enter the "stop" command instead of the numeric value of the item (see Figure 1).
Figure 1 - The process of adding items to the list
After entering the "stop" command, the list is printed and the program goes into command waiting mode (see Figure 2).
Figure 2 - Printed list
Print method - prints the list.
For printing, it is important to know the beginning of the list in order to consistently print the values \u200b\u200bof all the elements of the list, so a reference to the "head" of the list is set in the temp variable, after which the fact of the existence of the list is checked and the corresponding message is displayed, if it is not confirmed, if the list is not empty, then it is displayed:
void cList :: Print ()
cElement * temp \u003d head;
if (temp \u003d\u003d NULL) cout while (temp! \u003d NULL)
temp \u003d temp-\u003e getref ();
Del method - deleting the starting element of the list.
To remove the initial element, you must first move the link to the next component of the list, making it the first in this way and then delete the required element:
voidcList :: Del ()
cElement * temp \u003d head;
head \u003d head-\u003e getref ();
RemoveAll method - removes the entire list.
This method is based on the above and consists of sequentially removing the initial elements of the list until the entire list is removed.
void cList :: RemoveAll ()
while (elcount! \u003d 0)
To run this method, enter the "dellist" command in the menu for working with the list (see Figure 3).
Figure 3 - Entering the command to clear the list
And if the user is really confident in his actions, it is necessary to accept the program's offer, after which the entire list will be deleted (see Figure 4).
Figure 4 - Empty list
Remove method - removes a specific item from the list.
Less radical method than the previous one. Only one list item specified as a parameter is removed. This happens as follows: the program first checks the correctness of the entered parameter, if the number of the deleted element is less than one or more than the total number of elements in the list, then it displays an error message, but if the program has no complaints about the entered parameter, then the necessary links of the elements located nearby are transferred with the removed one so that the list remains linked, after which the required element is removed.
void cList :: Remove (int del)
cElement * cur \u003d head, * de;
if ((del\u003e \u003d 1) && (del
head \u003d head-\u003e getref ();
while (j! \u003d del-1)
cur \u003d cur-\u003e getref ();
de \u003d cur-\u003e getref ();
cur-\u003e setref (de-\u003e getref ());
coutsystem ("pause");
To run this method, enter the "delete" command in the menu for working with the list. Then enter the number of the element to be deleted or the "back" command to cancel the deletion (see Figure 5).
Figure 5 - The process of deleting a list item
The list after removing the fourth element will look like this (see Figure 6).
Figure 6 - List after deleting one element
Insert method - inserting a new item at a specified location in the list.
This method takes as parameters: the position of the added element and its numeric value. The new element will stand exactly at the specified place, thus, the elements to the right of the current one will be shifted by one position. When adding a new element to the beginning of the list, you just need to transfer the link from this element to the next, thereby linking the list and providing a link to the initial element. A slightly different situation arises when adding a new element between two existing ones, for this, using a loop, go to the insertion point of the element, then associate the components located to the right and left of it with the new element. After all, what, for example, needs to be done if it is necessary to lengthen the chain: you need to open it, then attach a new link to the first part of the chain, attach the second to the same link, something similar is implemented in this method. It is worth noting that if you specify an incorrect addition position, which is less than one or more than the total number of elements, the program will display an appropriate error message.
void cList :: Insert (int pos, int val)
cElement * cur \u003d head;
cElement * temp \u003d new cElement;
temp-\u003e setdata (val);
if ((pos\u003e \u003d 1) && (pos
temp-\u003e setref (head);
while (j! \u003d pos-1)
cur \u003d cur-\u003e getref ();
p \u003d cur-\u003e getref ();
cur-\u003e setref (temp);
temp-\u003e setref (p);
coutsystem ("pause");
To run this method, enter the "insert" command in the menu for working with the list. Then enter the position and numeric value of the added element or the "back" command to cancel the deletion (see Figure 7).
Figure 7 - The process of inserting an element
The list after adding an element with the value 111 to the third position, the list will look like this (see Figure 8).
Figure 8 - List after adding an element
During the description, the menu for working with the list was mentioned more than once, it remains to be noted that this menu greatly facilitates the work with the list. The algorithm of its work consists in cyclically calling the same methods, printing a list, for example, until a certain command is entered. The list of available commands can be seen by typing "help" in the console (see figure 9)
Figure 9 - Available commands
The complete menu code is shown in Appendix A.
Testing
Often in the course of work, situations arise associated with incorrect data entry, which can cause the program to fail. Of course, each program must implement protection algorithms from an inexperienced user, preventing the program from crashing. Let's consider how such algorithms function in the created program.
The initial input of the list is done with the following code:
if (atoi (ss)! \u003d NULL)
mylist.Add (atoi (ss));
Before calling the add method to add a new item to the list, the input string is checked. The atoi function converts a string to a numeric value and returns NULL if the input string is not a number. Thus, when entering, any lines that are not numbers will be ignored, except for the line with the command to stop input (see Figure 10).
Figure 10 - Entering incorrect data
After entering such data, the list will look like this (see Figure 11).
Figure 11 - Received list
The program continues to work correctly after, even after entering erroneous data. Similar methods of dealing with incorrect data are used for other input operations present in the program.
Conclusion
In this work, concepts were obtained about abstract data types, about the principles of their representation in modern programming languages, in C ++ in particular. In most modern imperative languages, the main concept used to describe abstractions in program code is the object-oriented approach. Object-oriented programming (OOP), like the ADT-based approach to programming, is, to some extent, a development of ideas about modular programming. Modules are program components that have two important properties:
Modules hide implementation details.
Modules can be reused in different parts of the program.
David Parnas, in his 1972 work, presented modules as abstract machines that store states within themselves and allow changing this state through a specific set of operations. This concept is basic, both for the concept of abstract data types and for object-oriented programming. Drawing parallels between the work of Parnas and modern OOP concepts, it is easy to see the relationship between the concepts of class and module.
In this work, linear singly-linked lists, which are an abstract data type, are represented by the developed modules, for accessing the states of which special operations are also implemented, called methods in object-oriented programming.
Bibliography
1. Ian Graham Object Oriented Methods. Principles and Practice \u003d Object-Oriented Methods: Principles & Practice. - 3rd ed. - M .: "Williams", 2004. - S. 880.
2. Anthony Sintes Learn Object-Oriented Programming in 21 Days \u003d Sams Teach Yourself Object-Oriented Programming in 21 Days. - M .: "Williams", 2002. - P. 672.
3. Bertrand Meyer Object-oriented design of software systems + CD. Internet University of Information Technologies - INTUIT.ru, Russian Edition, 2005
4. Billig V.A. The basics of programming in C #. Internet University of Information Technologies - INTUIT.ru, 2006
5. “New programming languages \u200b\u200band trends in their development”, V. Ushkova, 2005
6. Bjarne Stroustrup "The C ++ Programming Language" Special Edition or 3rd Edition ed. Binom, Nevsky Dialect, ISBN 5-7989-0226-2, 5-7940-0064-3, 0-201-70073-5
7. Bjarne Stroustrup "Design and evolution of the C ++ language". DMK-Press, Peter, ISBN 5-469-01217-4, 0-201-54330-3
8. Bjarne Stroustrup "Programming principles and practice of using C ++". "ID Williams", 2011, ISBN 978-5-8459-1621-1 (Russian)
9. Grady Booch et al. Object Oriented Analysis and Design with Sample Applications 2nd or 3rd edition. Binom, Nevsky dialect, Williams ISBN 978-5-8459-1401-9, 0-201-89551-X, 0-8053-5340-2, 5-7989-0067-3, 5-7940-0017-1
10. Scott Meyers "Using C ++ Effectively. 50 Best Practices for Improving Your Programs and Projects" DMK, Peter, ISBN 0-201-92488-9, 5-93700-006-4, 5-469-01213-1
Appendix A
Menu program code
#include "cList.h"
#include "string.h"
using namespace std;
coutwhile (strstr (ss, "stop") \u003d\u003d NULL)
if (atoi (ss)! \u003d NULL)
mylist.Add (atoi (ss));
system ("cls");
while (strstr (com, "exit") \u003d\u003d NULL)
coutmylist.Print ();
if (strstr (com, "help")! \u003d NULL) com_ind \u003d 1;
if (strstr (com, "add")! \u003d NULL) com_ind \u003d 2;
if (strstr (com, "insert")! \u003d NULL) com_ind \u003d 3;
if (strstr (com, "delete")! \u003d NULL) com_ind \u003d 4;
if (strstr (com, "dellist")! \u003d NULL) com_ind \u003d 5;
switch (com_ind)
system ("cls");
system ("cls");
coutcoutcoutcoutcoutcoutcoutcom_ind \u003d 0;
if (strstr (ss, "back") \u003d\u003d NULL)
if (atoi (ss)! \u003d NULL)
mylist.Add (atoi (ss));
system ("cls");
// insert elements
if (strstr (ss, "back") \u003d\u003d NULL)
if (atoi (ss)! \u003d NULL)
system ("cls");
if (strstr (ss, "back") \u003d\u003d NULL)
if (atoi (ss)! \u003d NULL)
mylist.Insert (pos, atoi (ss));
system ("cls");
// delete elements
if (strstr (ss, "back") \u003d\u003d NULL) is defined by a set of values given and a set of operations ... connected structures data – lists... Structure data Is a collection of elements data, between which ... in the computer memory is called abstract or logical. More often ...
Multiple a type data... The sets
Lecture \u003e\u003e Computer science, programming... a type similar to simple types data... Plural types described in section types ... VU can be described. Abstract computational structures describing input ... other cases types all components list must match type file components. ...
Object-oriented databases dataworking in distributed networks
Abstract \u003e\u003e InformaticsDeveloping areas of programming languages \u200b\u200bwith abstract types data and object-oriented programming languages. ... types data - list and array. Each literal is uniquely identified by an index in the array and an ordinal in the list ...
Abstract information security models
Abstract \u003e\u003e InformaticsInformation protection ……………………………………………… ..17 Abstract information security models ... governing interactions with both types data (Certification Rules): All ... various variations and additions to existing the list... Security levels - certain ...
All built-in data types are abstract, although they are rarely called that.
Abstraction concept
Abstraction is a judgment or representation about an object that contains only properties that are essential in a given context. Abstraction allows you to combine object instances into groups, within which the general properties of objects can be ignored, i.e. abstract from them. Abstraction is an effective tool against the complexity of programming, allowing the programmer to focus on the essential properties of objects. Types of abstractions: process abstraction and data abstraction.
Process abstraction.All subroutines are abstractions of processes, they define the way in which the program determines that some process needs to be done, without specifying the details of exactly how to do it. The ability to abstract away the many details of the algorithm that the subroutine runs allows you to create, read, and understand large programs. Any data abstraction are operations, defined as process abstractions.
Data abstraction.An abstract data type is an encapsulation that contains only representations of data of one particular type and routines that perform operations on data of that type. By using access control, non-essential details of a type description can be hidden from external modules that use the type. Program modules that use an abstract data type can declare variables of that type even though the actual representation of the type is hidden from them. An instance of an abstract data type is called an object.
The reason for creating data type abstraction and process abstraction is a means against complexity, a way to make large and / or complex programs more manageable.
Encapsulation
Dividing a program into syntactic containers that contain groups of logically related routines and data. These syntax containers are called modules, and the development process is modularization.
Composing a program from sets of routines and data, each of which can be compiled separately, without recompiling the rest of the program. This set is called a compilation unit.
Encapsulation is a way of integrating subroutines and the data they process into a coherent whole. Encapsulation, which is compiled either separately or independently of the others, is the basis of an abstract system and the logical organization of a set of related computations.
Abstract user-defined data types
Abstract user-defined data types must have the following properties:
1) type definition, which allows program modules to declare variables of this type, while creating a real representation of these variables in memory.
2) a set of operations for manipulating objects of this type.
Formal definition of an abstract data type in the context of user-defined types: An abstract data type is a data type that satisfies the following two conditions.
Representation (type definition) and operations on objects of this type are contained in one syntactic unit, variables of this type can be created in other modules.
The representation of objects of this type is hidden from program modules using this type; operations on objects that are directly provided in the type definition can be performed.
Packing the type representation and operations into a separate syntactic unit allows you to organize your program as logical units that can be compiled separately. Secondly, it becomes possible to modify the representations of objects of a given type or operations with them in a separate part of the program. There are advantages to hiding the details of a type's presentation. Clients cannot "see" the details of an object's view, and their code is independent of that view. In this way, object representations can be changed at any time without requiring changes to client code. Another obvious and important benefit of information hiding is increased reliability. Clients cannot directly change the basic representations of objects, either intentionally or accidentally, therefore, the integrity of such objects increases. Objects can only be modified using the operations provided for this.
Type design issues
It should be possible to make the type name and subroutine headers visible in the abstraction clients. This allows clients to declare variables of an abstract type and manipulate their values. Although the type name must be visible from the outside, its definition must be hidden.
There are very few general built-in operations that can be performed on objects of abstract types, as opposed to those provided by a type definition. Such operations include assignments, and equality and inequality tests. If the language does not allow users to overload the assignment operation, then it should be inline. Equality and inequality checks must be predefined in some cases, and not in others. The type designer must define the operations for most abstract data types himself.
Smalltalk, C ++, and Java directly support abstract data types.
Abstract data types in C ++
The Ada and Modula-2 languages \u200b\u200bprovide encapsulation that can be used to model abstract data types, while C ++ introduces the concept of a class that directly supports abstract data types. In C ++, classes are types, but Ada packages and Modula-2 modules are not types. Packages and modules are imported, allowing the importing program unit to declare variables of any type defined in the package or module. In a C ++ program, variables are declared as entities of the type of this class. Thus, classes are much more like built-in types than packages or modules. A program unit that sees a package in Ada language or a module in Modula-2 language has access to any open entities simply by their names. A C ++ program unit that declares an instance of a class also has access to any public entities in that class, but only through an instance of that class.
