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

НЕЛИНЕЙНЫЕ СВЯЗНЫЕ СТРУКТУРЫ

Обобщенные двусвязные списки

В предыдущем разделе были рассмотрены частные виды связных списков - линейные односвязные и двусвязные списки. Односвязный список всегда линейный. Двусвязный список может и не быть линейным, если второй указатель каждого элемента списка задает порядок произвольного вида, не являющийся обратным по отношению к порядку, устанавливаемому первым указателем элемента. Каждый элемент такого обобщенного двусвязного списка содержится одновременно в двух разных односвязных списках, как показано на рис.5.1. На этом рисунке переменные S1 и S2 являются указателями начала двух разных односвязных списков, в которые одновременно входит каждый из пяти элементов, а Р1 и Р2 - обозначения связок в первом и втором односвязных списках, соответственно. Указатели S1 и S2 являются компонентами двух разных дескрипторов односвязных списков.

Многосвязные списки

В еще более общем случае каждый элемент связного списка может содержать произвольное конечное число связок, одинаковое или разное в различных элементах. В результате такого обобщения получается многосвязный список, каждый элемент которого входит одновременно во столько разных односвязных списков, сколько имеется связок в соответствующем элементе. При этом не обязательно, чтобы каждый элемент непременно входил во все односвязные списки. Такой многосвязный список как бы прошит в разных направлениях многими связками. Поэтому многосвязные списки иногда называют прошитыми списками. Используется также еще одно название многосвязных списков - плексы [5].

Сетевые структуры

Наиболее общий вид многосвязной структуры - многосвязная структура, которая характеризуется следующими свойствами.

1. Каждый элемент структуры содержит произвольное число направленных связок с другими элементами (или ссылок на другие элементы).

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

3. Каждая связка в структуре имеет не только направление, но и вес.

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

Деревья

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

Деревом называется сетевая структура, которая характеризуется следующими свойствами.

1. Существует единственный элемент или узел, на который не ссылается никакой другой элемент и который называется корнем.

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

3. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем.

Определенная таким образом структура называется также корневым деревом.

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

Обычно дерево представляется в машинной памяти в форме многосвязного списка, в котором каждый указатель соответствует дуге. Это представление называется естественным представлением дерева. Существует несколько разновидностей такого представления. В одной из наиболее общих разновидностей каждому узлу дерева ставятся в соответствие элемент многосвязного списка, причем в каждом элементе отводятся следующие поля: поле данных, поле степени исхода и поля указателей, число которых равно степени исхода. На рис.5.2 дан пример дерева и представление этого дерева в виде многосвязного списка, начало которого, соответствующее корню дерева, адресуется указателем Р. Предполагается, что этот указатель входит в дескриптор, содержащий и другую общую информацию о списке (например, число его элементов). Обозначения A, B, C, D, E, F и G, записанные в первом поле каждого элемента списка, представляют собой данные о соответствующих узлах дерева.

В некоторых случаях используется и последовательное представление деревьев в памяти. Такой способ может быть рекомендован, например, в случае постоянства или редкой изменчивости структуры дерева.

Бинарные деревья

Весьма важный частный случай дерева - бинарное дерево. Бинарным деревом называется "m"-арное дерево при m=2. Иными словами, в бинарном дереве степень исхода для каждого узла не превышает 2. Любое "m"-арное дерево может быть преобразовано в эквивалентное ему бинарное дерево, которое проще исходного дерева с точки зрения изучения, представления в памяти и обработки. Для представления бинарного списка достаточен двусвязный список, который в общем случае не является линейным.

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

Важнейшие операции над бинарным деревом - обход его узлов, добавление и исключение некоторого поддерева.

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

1. Обработка (просмотр) корня дерева или поддерева.

2. Обход левого поддерева обработанного корня.

3. Обход правого поддерева обработанного корня.

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

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

Написание программ для организации и обработки связных списковых структур на языке программирования, в котором отсутствуют специальные средства манипулирования связными списками, требует обычно немалых усилий. И поэтому в тех программно- информационных системах, в которых связные списки играют ключевую роль, следует, по возможности, применять языки высокого уровня, содержащие средства работы со списками. К таким языкам относятся языки ЛИСП, IPL-V, СЛИП, FLPL, КОМИТ и др.

СТРОКОВЫЕ ДАННЫЕ

Строки

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