Списковые структуры

Форма представления структур данных в памяти ЭВМ зависит от предполагаемого использования данных, поскольку для различных типов структур эффективность выполнения тех или иных операций обработки данных различна. Элементы структуры данных в памяти ЭВМ могут адресоваться двумя способами - по месту или по содер­жимому. В первом случае указываются логические или физические адреса данных, определяющие место расположения данных в памяти машины. Во втором случае размещение данных и их выборка осущест­вляются по известному значению ключа, т.е. определяются содержи­мым самих данных. Этот случай реализуется в специальной ассоциа­тивной памяти ЭВМ. Некоторый аналог ассоциативной памяти может быть реализован средствами специального программного обеспечения в обычной памяти ЭВМ.

Наиболее простой формой хранения данных в памяти ЭВМ явля­ется одномерный линейный список, обеспечивающий линейное упорядо­чение элементов данных (вектора данных). Это удобно и с точки зрения свойств оперативной памяти ЭВМ. Здесь байты упорядочены по возрастанию их адресов от 0 до наивысшего (проидентифицированы адресом), образуя вектор памяти.

Отображение логической структуры данных на физическую струк­туру хранения называют адресной функцией. При реализации адрес-Ной функции использует два основных метода: последовательное распределение памяти; связное распределение памяти.

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

,

где i - индекс элемента (i= 1,N); b - адрес базы начала вектора в памяти; m - размер элемента (записи) списка.

С помощью линейного списка при последовательном распределе­нии памяти можно реализовать регулярное двоичное дерево (рис. 9.1).

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

Рис. 9.1. Пример реализации регулярного двоичного дерева

с помощью линейного списка

Другой способ размещения в памяти сбалансированного (регу­лярного) двоичного дерева заключается в следующем. Если для представления двоичного дерева используется вектор памяти от элемента i до элемента j включительно, то корень дерева раз­мещается в элементах памяти с адресом g= [(i+j)/2], где знак [] обозначает округление до ближайшего меньшего целого.

Корень дерева размещается в середину вектора. В элементах памяти от i-го до (m-1)-го включительно размещается левое поддерево. В элементах памяти от (m+1)-го до j-го включительно размещается правое поддерево. Аналогично процесс повторя­ется для размещения каждого поддерева. При этом корень левого поддерева размещается в элемент (квант) g_п = [i+(g - 1)]/2, а корень правого поддерева в элемент g_п = [(g + 1) + j]/2. Адре­са элементов вычисляются по формуле a( g) = b+ (g -1)m.

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

Связанное распределение - более сложный, но и более гибкий способ хранения линейного списка. Здесь не требуется, чтобы список хранился в последовательных элементах памяти, а линейная структура списка (цепи) обеспечивается указателями (рис. 9.2). Окончание списка кодируется (обозначается) специальным шифром, например, NIL или ^.

Рис. 9.2. Пример связанного линейного списка

Частными случаями линейного связного списка являются стек, очередь, дек. В стеке записи вводятся и удаляются только с одного конца. Стековую структуру еще называют структурой с магазинной памятью (последним пришел, первым ушел), а также LIFO-cпис­ком. Стек имеет один конец и для него требуется всего один указа­тель.

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

Дек - логическая структура, в которой удаление и добавление узлов происходит на обоих концах.

Для достижения большей гибкости при работе с линейными спис­ками в каждый узел X[i] вводятся два указателя. Один из ука­зателей реализует связь X[i] с узлом X[i+1], а другой с узлом X[i-1] (рис. 9.3).

Рис. 9.3. Пример двунаправленного линейного списка

Удобством связанных списков является то, что при изменении порядка записей, сокращении или расширении вектора данных не тре­буется перемещение записей в памяти ЭВМ. Достаточно лишь изменить значения полей связи (указателей). Однако доступ к конкретному узлу может сказаться намного длительнее, чем при последовательном распределении памяти (т.к. надо просмотреть все предшествующие узлы). Компромиссом является организация связанного линейного списка с пропусками (рис. 9.4).

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

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

а)

б)

Рис. 9.4. Способы ускорения доступа к узлам линейного связанного списка: а) организация линейного списка с пропусками; б) то же с использованием индекса

Оптимальный размер группы при равновероятном нахождении уз­ла в любой из групп: nг = Ön , где n - количество элемен­тов списка. Число групп: l = [ n/nг ].

При равновероятном нахождении узла в любой из групп при до­ступе к узлу необходимо просмотреть в среднем l/2 групп, а в каждой группе nг/2 узлов. Следовательно, общее количество про­смотров

А = l/2 + nг /2 = 0.5 ( [n/nг] + nг ).

Разновидностью представления в памяти линейного списка яв­ляется циклический список(кольцевая структура, кольцо), который обладает той особенностью, что связь от последнего узла идет к первому узлу списка. Это позволяет получить доступ к любому узлу списка, отправляясь от любого заданного узла. Иногда используют двунаправленные циклические списки (рис. 9.5).

В ряде случаев удобно использовать циклический список с указателями на голову списка из каждого узла. Связанные линейные списки позволяют реализовать в памяти ЭВМ и более сложные нелинейные структуры, в частности, древовидные и сетевые. Такие представления структур называются многосвязанными списками (не­сколько указателей).

а)

б)

Рис. 9.5. Примеры двунаправленного циклического списка:

а-обычное кольцо; б- кольцо с головкой списка

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

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

Различают встроенные указатели и справочник указателей. Если указатели образуют часть записи, то они называются встроенны­ми. Если указатели хранятся отдельно от записей, то они образуют справочник.