Главные понятия и разновидности

Структура данных «класс», представляющая собой объектный тип данных, внешне похожа на типы данных процедурно-ориентированных языков, такие как структура в языке С, в которой поля могут сами быть не только данными, но и методами (то есть процедурами или функциями). Таким образом, в простейшем случае объектно-ориентированное программирование получается добавлением к процедурно-ориентированному процедурного типа данных, то есть, переменных, способных принимать значение функций и процедур. Вдобавок класс поддерживает такие свойства как наследование, полиморфизм и отчасти — инкапсуляцию. Объектное программирование противопоставляется процедурному программированию, где данные и подпрограммы (процедуры, функции) их обработки формально не связаны. Кроме того, в объектно-ориентированном программировании часто большое значение имеет понятие события.

Объекты представляют собою неполную информацию о реальных сущностях предметной области. Их модели адекватны решаемой задаче, работать с ними намного удобнее, чем с низкоуровневым описанием всех возможных свойств и реакций объекта. Абстракция данных — подход к обработке данных по принципу чёрного ящика. Данные обрабатываются функцией высокого уровня с помощью вызова функций низкого уровня. Обычно такой подход используется в объектно-ориентированном программировании, что позволяет работать с объектами, не вдаваясь в особенности их реализации.

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

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

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

· Объекты некоторым образом взаимодействуют между собой

· Каждый объект характеризуется своим состоянием и поведением

Данный подход реализован в огромном количестве языков программирования; основоположником является язык C++. Очень часто под объектно-ориентированным подходом понимается именно модель, реализованная в этом языке и клонированная в других. Дополнительные концепции этого подхода таковы:

//их 4 штуки нетрадиционных, о них лучше не заикаться, потому что деталей там – заебёсси

Стек (англ. stack — стопка) –смотри в 5ом билете. Там выделено.

Список — упорядоченная последовательность элементов данных, воспринимаемая как особая контейнерная структура данных. В качестве элементов списка могут выступать любые другие элементы данных, в том числе и сами списки. У определённой таким образом структуры данных имеются некоторые свойства:

Размер списка — количество элементов в нём, исключая последний «нулевой» элемент, являющийся по определению пустым списком.

· Тип элементов — тот самый тип A, над которым строится список; все элементы в списке должны быть этого типа.

· Отсортированность — список может быть отсортирован в соответствии с некоторыми критериями сортировки (например, по возрастанию целочисленных значений, если список состоит из целых чисел).

· Возможности доступа — некоторые списки в зависимости от реализации могут обеспечивать программиста селекторами для доступа непосредственно к заданному по номеру элементу.

· Сравниваемость — списки можно сравнивать друг с другом на соответствие, причём в зависимости от реализации операция сравнения списков может использовать разные технологии.

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

Очередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть dequeue, при этом выбранный элемент из очереди удаляется).

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

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

· Добавить элемент в конец последовательности

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

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

2. в каждый момент времени в этой линейной цепочке определена некоторая текущая позиция и нам разрешен доступ к элементу в этой текущей позиции (или к его непосредственным "соседям").

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

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

Структуры данных, обладающие указанными свойствами обычно называют списками. Наглядным примером списочной организации данных может служить работа с текстом в большинстве текстовых редакторов. Редактирование текста можно выполнять в окрестности текущей позиции, которая определяется положением курсора. Можно удалить текущую строку или вставить новую строку непосредственно перед текущей. Можно перемещаться по строкам по направлению к началу или концу текста. Таким образом, весь текст можно рассматривать как список строк. Точно так же каждую отдельную строку можно рассматривать как список символов, по которому можно перемещать текущую позицию редактирования к началу или концу строки и добавлять или удалять символы в окрестности текущей позиции.

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

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

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

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

• в каждый момент времени разрешен доступ только к двум соседним элементам списка (будем называть их элемент до указателя и элемент за указателем), пару указателей на позиции этих двух элементов будем называть указателем текущей позиции;

• удалять можно только те элементы, на которые показывает указатель текущей позиции (т.е. элементы до или за указателем), при этом соответствующая ссылка указателя списка перемещается на предыдущий (соответственно, следующий) элемент;

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

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

Понятие списка, которое мы рассмотрели в предыдущем разделе, естественным образом обобщается на структуры с множественными связями между отдельными элементами. Одной из таких структур является дерево. В математике дерево определяется как связный граф, не содержащий циклов. Если в этом графе выделена одна вершина, то говорят, что дерево имеет корень. Мы будем рассматривать именно такие деревья. Наличие корня в дереве сразу определяет некоторое отношение подчиненности вершин. Для большей четкости изложения введем несколько определений.

Определение 1. Расстоянием (или длиной пути) между двумя вершинами А и В дерева назовем количество ребер графа, содержащихся в связной цепочке ребер, соединяющих А и В. (Поскольку дерево — это граф без циклов, расстояние между двумя вершинами определяется однозначно.)

Определение 2. Вершина В называется потомком вершины А, если расстояние между А и В равно 1 и расстояние от А до корня меньше, чем расстояние от В до корня дерева. Вершину А будем также называть родителем вершины В.

Определение 3. Будем говорить, что вершина А принадлежит k-му уровню дерева, если расстояние от А до корня дерева равно к.

Очевидно, что уровень 0 дерева содержит только корень, а уровень к дерева образован потомками всех вершин уровня к — 1.

Определение 4. Ветвью дерева назовем связную последовательность вершин, начинающуюся в корне и оканчивающуюся

на вершине, не имеющей потомков. Длиной ветви назовем число вершин в этой ветви.

Определение 5. Дерево, в котором каждая вершина имеет не более двух потомков, называется бинарным, в противном случае будем дерево называть произвольным.

Чтобы реализовать хранение и работу с данными, содержащимися в вершинах дерева, нам необходимо каким-то образом представить существующие связи между между отдельными вершинами. Так как каждая вершина связана ребрами не более, чем с тремя другими вершинами, то мы можем естественным образом обобщить списочный подход и для представления вершины ввести следующий класс¹:

где указатели left и right показывают на потомков, a prev — на родителя. При этом, если вершина не имеет соседей в каком-нибудь направлении, то соответствующий указатель имеет нулевое значение.

Такой способ представления каждой отдельной вершины является исчерпывающим для бинарного дерева.

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: