Списки
Список - это линейная динамическая структура данных. Каждый элемент такой структуры, в простейшем случае содержит два поля (поле данных и поле - указатель на следующий элемент, SFP). С помощью указателя каждый из элементов списка связывается со следующим элементом (в случае однонаправленного списка) или со следующим и предыдущим (в случае двунаправленного). Для доступа к элементам такого списка, необходимо сначала осуществить его поиск, начиная с первого (головного) элемента. Таким образом, для работы со списком обязательно хранится указатель на первый элемент (голову) списка.
Основным отличием списка от массива является то, что список является динамической структурой. Это позволяет создавать список, не резервируя лишнего места в памяти и той длины, которая необходима программе на данный момент времени (например, если подключен медиаконвертер), не опасаясь его переполнения. Однако в списке отсутствует возможность сразу обратиться к произвольному элементу, что существенно замедляет поиск (в массиве доступ к любому элементу может быть получен с использованием индекса).
Добавление элементов, как правило, осуществляется в конец списка, поэтому желательно также всегда хранить указатель и на последний элемент - хвост списка (add/drop).
При удалении некоторого элемента списка необходимо найти предыдущий и следующий элементы и связать их (указатель предыдущего должен теперь указывать на следующий, а не на удаляемый). Только после этого можно освободить память от удаляемого элемента.
Бинарные деревья
В случае если бинарное дерево упорядочено, т.е. для каждого поддерева выполняется условие Ц значение каждого узла левого поддерева меньше значения корневого узла, а значение любого узла правого поддерева больше или равно значения корневого узла — такое дерево называется бинарным деревом поиска. Упорядоченность дерева накладывает свои особенности на процедуры создания дерева, добавления и удаления элементов (узлов), а также поиска.
Очевидно, что бинарное дерево поиска будет иметь существенные преимущества перед линейным списком по времени поиска данных. Действительно, если для поиска в линейном списке, содержащем N элементов, в худшем случае нужно выполнить N операций сравнения, то в случае полного бинарного дерева поиска, содержащего такое же количество элементов, наибольшее количество сравнений - Iog2(N). Очевидно, что чем больше N, тем более выгодно использование при поиске бинарного дерева поиска по сравнению с линейным списком.
| html-cсылка на публикацию |
|
| BB-cсылка на публикацию |
|
| Прямая ссылка на публикацию |
|
| 