Списки (основные виды и способы реализации).

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

В информатике линейный список обычно определяется как абстрактный тип данных (АТД), формализующий понятие упорядоченной коллекции данных.

На практике линейные списки обычно реализуются при помощи массивов и связных списков. Иногда термин «список» неформально используется также как синоним понятия «связный список».

К примеру, АТД нетипизированного изменяемого списка может быть определён как набор из конструктора и четырёх основных операций:

операция, проверяющая список на пустоту;

операция добавления объекта в список;

операция определения первого (головного) элемента списка;

операция доступа к списку, состоящему из всех элементов исходного списка, кроме первого.

Характеристики

Длина списка. Количество элементов в списке.

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

Список может быть сортированным или несортированным

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

15. Структуры данных «Стеки и очереди». Принципы работы.

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

Стек (англ. stack – стопка) – это структура данных, в которой новый элемент всегда записывается в ее начало (вершину) и очередной читаемый элемент также всегда выбирается из ее начала (рис. 30.1). В стеках используется метод доступа к элементам LIFO (Last Input – First Output, "последним пришел – первым вышел"). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно сначала взять верхнюю.

Стек как динамическую структуру данных легко организовать на основе линейного списка. Поскольку работа всегда идет с заголовком стека, то есть не требуется осуществлять просмотр элементов, удаление и вставку элементов в середину или конец списка, то достаточно использовать экономичный по памяти линейный однонаправленный список. Для такого списка достаточно хранить указатель вершины стека, который указывает на первый элемент списка. Если стек пуст, то списка не существует, и указатель принимает значение NULL.

Очередь – это структура данных, представляющая собой последовательность элементов, образованная в порядке их поступления. Каждый новый элемент размещается в конце очереди; элемент, стоящий в начале очереди, выбирается из нее первым. В очереди используется принцип доступа к элементам FIFO (First Input – First Output, "первый пришёл – первый вышел"). В очереди доступны два элемента (две позиции): начало очереди и конец очереди. Поместить элемент можно только в конец очереди, а взять элемент только из ее начала. Примером может служить обыкновенная очередь в магазине.

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

16. Структуры данных «Графы и деревья». Принципы работы.

Неориентированные графы

Граф - это двойка <V, E>, где V - непустое множество вершин, а Е - множество ребер, соединяющих эти вершины попарно. Две вершины, связанные между собой ребром, равноправны, и именно поэтому такие графы называются неориентированными: нет никакой разницы между "началом" и "концом" ребра.

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

Например, три графа насовпадают, а два графа на- различны.

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

Ребро е и вершина v называются инцидентными друг другу, если вершина v является одним из концов ребра е.

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

Две вершины называются смежными, если они являются разными концами одного ребра (иными словами, эти вершины инцидентны одному ребру). Аналогично, два ребра называются смежными, если они инцидентны одной вершине.

Путь в графе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны. Например, в графе, изображенном на, есть два различных пути из вершины a в вершину с: adbc и abc.

Вершина v достижима из вершины u, если существует путь, начинающийся в u и заканчивающийся в v.

Граф называется связным, если все его вершины взаимно достижимы.

Компонента связности - это максимальный связный подграф. В общем случае граф может состоять из произвольного количества компонент связности. Заметим, что любая изолированная вершина является отдельной компонентой связности. Наизображен граф, состоящий из четырех компонент связности: [abhk], [gd], [c] и [f].

Длина пути - количество ребер, из которых этот путь состоит. Например, длина уже упомянутых путей adbc и abc - 3 и 2 соответственно.

Ориентированные графы

Орграф - это граф, все ребра которого имеют направление. Такие направленные ребра называются дугами. На рисунках дуги изображаются стрелочками.

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

Если в графе присутствуют и ребра, и дуги, то его называют смешанным.

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

Степень вершины в орграфе - это не одно число, а пара чисел: первое характеризует количество исходящих из вершины дуг, а второе - количество входящих дуг.

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

Взвешенные графы

Взвешенный (другое название: размеченный) граф (или орграф) - это граф (орграф), некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа. Наиболее часто встречаются графы с помеченными ребрами. Числа-пометки носят различные названия: вес, длина, стоимость.

Замечание: Обычный (не взвешенный) граф можно интерпретировать как взвешенный, все ребра которого имеют одинаковый вес 1.

Длина пути во взвешенном (связном) графе - это сумма длин (весов) тех ребер, из которых состоит путь. Расстояние между вершинами - это, как и прежде, длина кратчайшего пути. Например, расстояние от вершины a до вершины d во взвешенном графе, изображенном на, равно 6.

N-периферия вершины v - это множество вершин, расстояние до каждой из которых (от вершины v) не меньше, чем N.

Дерево - это частный случай графа, наиболее широко применяемый в программировании.

Основные определения

Существует довольно много равносильных определений деревьев, вот лишь некоторые из них.

Дерево - это связный граф без циклов.

Дерево - это связный граф, в котором при N вершинах всегда ровно N-1 ребро.

Дерево - это граф, между любыми двумя вершинами которого существует ровно один путь.

Аналогичным образом определяется и ориентированное дерево - как орграф, в котором между любыми двумя вершинами существует не более одного пути.

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

Предок вершины v - это вершина, из которой исходит дуга, заходящая в вершину v. Потомок вершины v - это вершина, в которую заходит дуга, исходящая из вершины v. В этих терминах можно дать другие определения понятиям корень и лист: у корня нет предков, у листа нет потомков.

Бинарное дерево - это корневое дерево, каждая вершина которого имеет не более двух потомков. В таком случае иногда говорят о левом потомке и правом потомке для текущей вершины.

Высота корневого дерева - это максимальное количество дуг, отделяющих листья от корня. Если дерево не взвешенное, то его высота - это просто расстояние от корня до самого удаленного листа.

И в заключение мы приведем определение, связывающее произвольные графы с деревьями более плотно.

Каркас графа - это дерево, полученное после выбрасывания из графа некоторых ребер.

Примером каркаса является (корневое) дерево кратчайших путей от некоторой выделенной вершины (она будет корнем каркаса) до всех остальных вершин графа.

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