Реферат: Создание эффективной реализации сортированного списка с использованием generics
}
PriorPage, NextPage нужны для навигации по дереву.
Основную функциональность двухуровневого массива реализует класс TwoLevelSortedDictionary:
|
using Generic = System.Collections.Generic; public class TwoLevelSortedDictionary<K,V>: Generic.IDictionary<K,V> { internal LeafPage<K,V> CurrentLeafPage; // Текущаястраницасданными internal struct NodeItem // Структура элементов верхнего уровня { internal K Key; internal LeafPage<K,V> ChildPage; } internal NodeItem[] NodeArray; // Массивэлементов 2 уровня internal int _pageCount; // Количество страниц 1 уровня internal int _currentPageIndex; // Текущий индекс элемента в массиве 2 уровня internal int _currentElementIndex; // Текущийиндексв CurrentLeafPage internal Generic.IKeyComparer<K> _comparer; // Пользовательскийкомпаратор internal int _count; // Количествоэлементоввобъекте bool _selected; // Выбранлиэлемент internal int version=1; // Нужендляперечислителей public TwoLevelSortedDictionary(Generic.IKeyComparer<K> Comp) { this._comparer = Comp; CurrentLeafPage = new LeafPage<K,V>(); // Выделяемстраницу 1 уровня _pageCount = 1; } |
Двухуровневый массив позволяет осуществлять навигацию по находящимся в нем элементам. При этом возникает понятие текущего элемента, у которого можно считывать или устанавливать значение, и читать значение ключа. Для позиционирования на запись с некоторым ключом используется функция NavigateKey.
Алгоритм работы этой функции таков. Поскольку информация в массиве всегда упорядочена, то поиск можно осуществлять с помощью алгоритма бинарного поиска (то есть половинного деления). Единственная проблема, не позволяющая использовать классический алгоритм напрямую – это то, что, что массив состоит из двух уровней. Поэтому алгоритм поиска разделяется на два этапа. На первом этапе проверяется, есть ли массив верхнего уровня. Если есть, то в нем ищется страница, на которой может находиться искомый элемент. Если массива верхнего уровня нет, в качестве страницы, на которой будет производиться дальнейший поиск, используется единственная существующая страница.
На втором этапе производится классический бинарный поиск по ключу в сортированном массиве.
|
К-во Просмотров: 516
Бесплатно скачать Реферат: Создание эффективной реализации сортированного списка с использованием generics
|