Линейный список

Cтраница 4

Доступ к элементу осуществляется через адрес первого элемента и номер позиции искомого в рассматриваемом списке. Примером такого линейного списка может служить одномерный массив в программах или массив записей на магнитной ленте. При простоте программной реализации такая форма представления данных не удовлетворяет вышеперечисленным требованиям, так как всякое изменение информации связано с перезаписью массива с места на место. Также не выполняется требование входа в список в произвольном месте, ибо он возможен только с начала магнитной ленты. Заметим, что для ЭВМ, работающих с предварительно размеченной определенным образом магнитной лентой, например БЭСМ-6, М-222, возможен обмен с данными, записанными в любом месте носителя. [46]

Исключение из дерсяа. [47]

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

На рис. 14.1 приведен текст подпрограммы-функции и главной программы на Лиспе. Функции с именем LISTATOMS передается в качестве аргумента списковая сд-руктура Лиспа. Эта списковая структура представляет собой дерево, содержащее в качестве листьев атомы ( символы) Лиспа. LISTATOMS строит новый линейный список, содержащий только атомы исходного списка. [49]

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

Каждая внутренняя вершина содержит число и два поддерева. Упорядоченное бинарное дерево - это такое дерево, в котором для каждой внутренней вершины все элементы левого поддерева меньше или равны значению вершины, а все элементы правого поддерева больше значения вершины. Приведенные выше примеры являются упорядоченными бинарными деревьями. Разглаживание дерева состоит в таком преобразовании, при котором элементы дерева преобразуются в элементы линейного списка. [51]

Заметим, наконец, что элементы двоичного дерева поиска могут быть перечислены в правильной последовательности с помощью обратного просмотра. Единственной операцией, требующей значительных усилий, является операция исключения узла, не являющегося листом дерева. Двоичное дерево поиска представляет собой более удобную структуру для хранения и поиска данных, чем массив. При работе с таким деревом надо предварительно убедиться, что новые данные не поступают в порядке возрастания или убывания, так как в этом случае дерево выродится в линейный список. Во многих практических случаях, однако, данные поступают в существенно случайном порядке, что позволяет строить более или менее эффективные деревья поиска. [52]

Все рассмотренные выше структуры данных характеризуются сплошным расположением в памяти ЭВМ. Это часто неудобно из-за необходимости заранее фиксировать размер области оперативной памяти, отводимой под размещение этих структур. В большинстве случаев этот размер априорно неизвестен и определяется только в процессе выполнения программ. Поэтому более универсальны структуры данных, ориентированные на цепное представление в памяти ЭВМ. К ним относятся стек, очередь, линейный список, дерево и др. Объединение записей в эти структуры осуществляется с помощью переменных типа УКАЗАТЕЛЬ, размещаемых в полях записей. [53]

Страницы: 1 2 3 4