6. Статичні і динамічні структури даних.

Структуры данных могут быть статическими и динамическими.

Статические структуры относятся к разряду структур, которые представляют собой структурированное множество примитивных (базовых) структур. Поскольку по определению статические структуры отличаются отсутствием изменчивости, память для них выделяется автоматически – как правило, на этапе компиляции или при выполнении, в момент активизации того программного блока, в котором они описаны.

Массив – упорядоченный набор данных, для хранения данных одного типа, идентифицируемых с помощью одного или нескольких индексов. Массив имеет постоянную длину и хранит единицы данных одного и того же типа.

Связанные динамические структуры данных отличаются от статических тем, что могут, иметь бесконечное число элементов. Они характеризуются высокой гибкостью создания структур данных различной конфигурации за счет возможности выделять и освобождать память под элементы в любой момент времени работы программы и возможности установить связь между любыми двумя элементами с помощью указателей.

Среди динамических структур данных выделяют: стек, очередь, списки, деревья.

Стек – структура вида LIFO (last in, first out). В стеке имеется доступ только последнему поступившему элементу – вершине стека. Она является его первым звеном. Каждое звено стека содержит ссылку на следующее звено, причем «дно», т.е. элемент, занесенный в стек раньше всего, имеет ссылку null.

Очередь – структура, в которой элемент, который вошел первый, будет извлечен из очереди также первым ( FIFO - first in, first out).

Для создания очереди и работы с ней необходимо, как минимум два указателя: на начало очереди (BegQ) и на конец очереди (EndQ).

Линейные списки – данные с рекурсивной структурой. Применяется в случаях, когда надо обработать данные, количество элементов которых заранее не определено, а взаимный порядок следования играет важную роль.

Линейный однонаправленный список – данные, которые представляют собой линейно связанные элементы, которые можно добавлять между любыми двумя другими, и удалять любой элемент.

Линейные двунаправленные списки – списки, в каждом звене которых присутствуют ссылки как на следующее, так и на предыдущее звено, что позволяет от каждого звена двигаться по списку в любом направлении.

Кольцевые списки имеют дополнительные связи между первым и последним элементами списка.

Двоичное дерево – это динамические данные иерархической структуры произвольной конфигурации. Элементы дерева называются вершинами (узлами). В нем одинаково эффективно реализуются все три основные операции: поиска, записи и удаления информации.

7. Об’єктно-орієнтоване програмування.

Объектно-ориентированное программирование (ООП) – метод программирования, основанный на представлении программы в виде совокупности взаимодействующих объектов, каждый из которых является экземпляром определённого класса, а классы – членами определенных иерархических наследований. В таких программах классы обычно считаются статичными сущностями, а объекты имеют динамическую природу, поддерживаемую механизмами динамического связывания и полиморфизма.

Класс – множество объектов, обладающих общей структурой, поведением и семантикой. Класс объектов представляет собой программную структуру, в которой данные и функции образуют единое целое и отражают свойства и поведение этого целого в рамках моделируем ситуации.

Объект – экземпляр класса. Является сущностью в адресном пространстве вычислительной системы, которая появляется при создании экземпляра класса.

Основными понятиями ООП являются:

• Инкапсуляция – принцип, согласно которому любой класс должен рассматриваться как чёрный ящик. Пользователь класса должен видеть и использовать только интерфейсную часть класса (т. е. список декларирующих свойств и методов класса) и не вникать в его внутреннюю реализацию. Поэтому данные принято инкапсулировать в классе таким образом, чтобы доступ к ним по чтению или записи осуществлялся не напрямую, а с помощью методов.

• Наследование – отношение между классами, при котором класс использует структуру или поведение, которые определены в другом классе (одиночное наследование) или нескольких других классах (множественное наследование). Наследование определяет иерархию классов «общее/частное», в которой подкласс наследует свойства одного или нескольких более общих суперклассов. Подкласс обычно конкретизирует суперкласс, дополняя или переопределяя его структуру и поведение.

• Полиморфизм – концепция теории типов, согласно которой имена могут обозначать объекты разных классов, имеющих общий суперкласс. Полиморфизм позволяет использовать одно имя для обозначения действий, общих для родственных классов. При этом конкретизация выполняемых действий производится в зависимости от типа обрабатываемых данных. К примеру, в С++ можно выделить следующие свойства:

  • перегрузка функций

  • виртуальные функции

  • обобщенные функции (шаблоны)

Перегрузка функций и операций является статическим полиморфизмом, т.е. поддерживаемым на этапе компиляции.

Виртуальные функции относятся к динамическому полиморфизму, так как выполняется во время выполнения программы.

Типичными языками, поддерживающими парадигму объектно-ориентированного программирования, являются C++, C# и Java.