Файл: Обзор языков программирования высокого уровня (Современные языки программирования).pdf
Добавлен: 31.03.2023
Просмотров: 78
Скачиваний: 2
К недостаткам можно отнести менее эффективный доступ к элементам по сравнению с массивом, ведь для того, чтобы добраться до элемента, нужно пройти всю цепочку узлов. Также динамические структуры накладывают дополнительные расходы на память, которая выделяется для хранения указателей на другие элементы.
Из динамических структур в программах чаще всего используются различные линейные списки, стеки, очереди и бинарные деревья [12]. Они и будут рассматриваться.
Связный (связанный) список является динамической структурой данных, представляющую собой последовательность элементов (узлов). Каждый узел содержит как сами данные, так и одну или две ссылки на предыдущие и/или последующие элементы. Не смотря на свою простоту, связный список является основной для множества задач, относящихся к обработке динамических данных.
Связный список — это фундаментальная структура данных, без понимания которой нельзя переходить к рассмотрению более сложных структур. Существуют три основные разновидности связных списков: односвязный, двусвязный и кольцевой [10].
Данный вид списка еще называют линейным однонаправленным списком. Визуально его можно представить следующим образом (рисунок 1):
Рисунок 1 – Односвязный список
На начало списка указывает head. Если список пустой, то значение head будет равно NULL, в противном случае — адрес первого элемента. Все элементы списка имеют одинаковый тип, а сами данные (DATA) могут быть представлены в произвольном формате. Указатель на следующий элемент находится в поле next. В последнем элементе списка поле next будет пустым (NULL).
Передвигаться по односвязному списку можно только в одну сторону, начиная с головы. Добавлять элементы можно в любую позицию списка. На рисунке 2 изображено добавление элемента в середину списка.
Рисунок 2 – Добавление элемента в список
При добавлении элемента необходимо динамически выделить для него память, присвоить полю next нового элемента значение next предыдущего элемента (или head, если вставляем в начало), а потом указателю next предыдущего элемента (если он имеется) присвоить адрес нового элемента. Если новый элемент добавляется в начало списка, указателю head присваиваем его адрес, если в конец списка, то поле next выставляем в NULL.
При удалении элемента (рисунок 3) сначала меняется значение указателя предыдущего элемента, а потом освобождается занимаемая память. Следует заметить, что для этой операции требуется указатель на предыдущий элемент.
Рисунок 3 – Удаление элемента из списка
При удалении первого элемента списка значение указателя head меняется на поле next удаляемого элемента, то есть на следующий элемент, который станет первым. В случае отсутствия других элементов в списке указатель head станет нулевым.
При перестановке элементов, которая требуется, например, для сортировки списка, не требуется менять местами сами данные, меняются лишь поля указателей. В общем случае перестановка двух соседних элементов представлена на рисунке 4.
Рисунок 4 – Перестановка соседних элементов
Если какой-нибудь элемент однонаправленного списка пройден, доступ к нему возможен только при повторном прохождении списка, начиная с головы (указатель head). Для устранения этого недостатка в последнем элементе линейного списка в поле next устанавливается указатель на первый элемент списка. Получается замкнутый список, который называется кольцевым или циклическим. В этом списке любой элемент можно достичь из любого другого элемента.
Визуально кольцевой список представлен на рисунке 5.
Рисунок 5 – Кольцевой список
В некоторых случаях указатель устанавливается на последний элемент, тогда появляется возможность эффективно добавлять элементы в конец и начало списка, так как есть быстрый доступ как к концу списка, так и к его началу (поле next последнего элемента).
Операции с элементами циклического списка аналогичны таковым односвязного списка, но есть и особенности. Если список состоит из единственного элемента, поле next будет указывать на него самого. Если необходимо проходить все элементы списка по одному разу (например, для поиска данных), то есть несколько вариантов:
- сравнивать каждый элемент с головным (head) или с тем элементом, откуда начинается проход;
- поместить в конец списка специальный узел, который легко может быть распознан;
- хранить общее количество элементов, а при проходе списка использовать счетчик.
Рассмотренные списки имеют недостаток, заключающийся в невозможности просмотра в обратном направлении. Например, имея указатель только на заданный элемент, его не получится так просто удалить или вставить на это место новый, так как для данных операций требуется модификация поля next предыдущего элемента [2]. Если нужно обойти указанные ограничения, используется двусвязный (двунаправленный) список. В этих списках добавляется еще одно поле, указывающее на предыдущий элемент (рисунок 6).
Рисунок 6 – Двусвязный список
В линейном двусвязном списке поля prev первого элемента и next последнего будут иметь нулевые указатели. Обычно поля next и prev находятся после данных, но для удобства восприятия было выбрано именно такое отображение. Строго говоря, в рисунке 6 есть неточность, заключающаяся в том, что указатели next и prev указывают на поля данных, на самом деле они должны указывать на сам элемент, а его началом является именно адрес поля prev. Но эта неточность также допущена лишь для удобства восприятия.
Операции удаления, добавления и перестановки элементов аналогичны таковым для односвязного списка, только нужно учитывать второе поле (prev).
Разобрав основные виды списков, продемонстрируем, как они применяются. Для этого рассмотрим реализацию на основе списков таких динамических структур как очередь, стек и дек.
Очередь — это структура данных, организованная по принципу первым вошел, первым вышел (FIFO — first in, first out) [14]. То есть добавление элементов осуществляется в конец очередь, а извлечение с начала. Очереди широко используются в самых различных задачах, от низкоуровневых вещей вроде очередей событий в операционной системе до обычной очереди в магазине.
При работе с очередью удобно хранить два указателя – на ее начало и конец, а также переменную количества элементов в очереди. Эта концепция хорошо ложится на линейный односвязный список, операции с которым были рассмотрены ранее. В качестве интерфейсов для работы с очередью можно предоставить методы создания очереди, ее удаления, вывода количества элементов, добавления элемента (в конец) и извлечения элемента (удаление узла и возврата его значения).
Стек – это структура данных, организованная по принципу последним пришел, первым вышел (LIFO — last in, first out). В отличие от очереди извлечение и добавление элементов осуществляется с одного конца, который называется вершиной стека. Стек нашел широкое применение не только в компьютерной области вроде программного стека для размещения локальных переменных, параметров функций, адреса возврата, но и в повседневной жизни. Типичным примером является почта, когда и новые сообщения «заталкивают» в верхнюю часть списка при их поступлении, и просмотр писем мы тоже начинаем сверху, чтобы прочитать самые свежие поступления [14].
Стек, так же как и очередь, легко реализуется на основе линейного списка, в котором все операции производятся с одним концом.
Дек является своеобразной комбинацией очереди и стека, когда операции с элементами (добавление и удаление) возможны как с начала, так и с конца. Слово дек (deque) происходит из выражения double-ended queue (двусторонняя очередь), точно описывающего свой смысл [16]. Можно организовать дек на основе однонаправленного списка, но в этом случае для удаления элемента с конца списка придется проходить весь список, что явно неэффективно. Гораздо удобнее оперировать деком на основе двусвязного списка и хранить указатели как на начало, так и на конец списка.
В зависимости от решаемых задач могут применяться нелинейные структуры, в которых у элементов может быть несколько связей, и переход от одного элемента к другому может зависеть от определенного условия.
Дерево является основным представителем нелинейных структур, являясь совокупностью узлов (вершин) и соединяющих их направленных ребер (дуг), причем в каждый узел за исключением корня ведет ровно одна дуга. Корнем называется начальный узел дерева, в который не ведет ни одна дуга [22]. Вершины, не имеющие последующих узлов, называют листьями. Как видно, линейные односвязные списки представляет собой вырожденный случай дерева, в котором каждая вершина имеет не более одного поддерева.
На практике часто используются двоичные (бинарные) деревья. В них каждый узел имеет не более двух потомков, которые образуют левое и правое поддерево. Типичным примером бинарного дерева является генеалогическое дерево. Если двоичное дерево упорядочить таким образом, чтобы корневой элемент имел большее значение, чем любой элемент в левом поддереве, но в то же время меньшее или равное значение, чем элементы в правом поддереве, то получится бинарное дерево поиска. Как следует из названия, оно широко применяется в алгоритмах поиска, используется для построения больших поисковых индексов.
Существует множество типов деревьев, применяемых в различных областях. По мнению экспертов, деревья являются наиболее важными нелинейными структурами, которые встречаются при работе с компьютерными алгоритмами [5].
Рассмотренные динамические структуры нередко часто служат базовыми элементами, комбинация которых позволяет решать самые сложные задачи. Но даже в простых задачах выбор правильной структуры оказывает ощутимое влияние на производительность решения [7]. Как показывают проведенные эксперименты [11], даже относительно медленные сценарные языки программирования при выборе наиболее подходящей структуры данных для конкретной задачи показывают более высокую производительность, чем компилируемые языки, использующие не самую оптимальную структуру.
Организация данных в списковые структуры
Особенности реализации
Разобравшись с теоретическими аспектами в динамических структурах, рассмотрим организацию данных в списковые структуры на практике. В качестве примера напишем программу, которая работает со списком из целых чисел – добавляет новые значения в указанную позицию, удаляет имеющиеся, производит поиск элемента с заданным значением.
В качестве основы взят односвязный список, так как он является простой базовой динамической структурой, на которой удобно демонстрировать основные операции работы со списками.
Как говорилось в конце первой главы, в качестве языка программирования был выбран C++, потому что он позволяет работать не только на относительно низком уровне, что необходимо для полноценной демонстрации внутренней организации списка, так и естественным образом представить список в виде класса, имеющего удобные публичные методы, предназначенные для взаимодействия с ним. Такой подход также повышает безопасность и надежность программы. Ведь при возможном расширении функциональности программы достаточно будет воспользоваться проверенными внутренними методами, обернув их в необходимый публичный метод.
Элементом списка является следующая структура:
struct Node {
int val;
Node *next;
};
Node *head;
int node_counter;
В ней поле val содержит полезные данные, ради которых и строится список. Поле next указывает на следующий элемент. Также нам понадобится указатель на первый элемент списка head и счетчик элементов в списке node_counter. Без последнего можно обойтись, но он дает весомые преимущества.
- Упрощение проверок перед выполнением операций. К примеру, если поступит запрос на удаление элемента 10, то без использования счетчика мы должны перебрать все элементы, пока не дойдем до нужного элемента. И тут может оказаться, что в списке всего 9 элементов. Использование счетчика позволяет сразу сказать об этом, без прохода по списку.
- Значительное ускорение части операций со списком. Например, в случае запроса на количество элементов в списке достаточно вернуть значение счетчика.
Но самих элементов и вспомогательных переменных недостаточно, нужны еще и методы, которые будут оперировать этими элементами и предоставлять доступ к ним. И здесь уже стоит задуматься об архитектуре приложения.