Claw.ru | Рефераты по информатике, программированию | Создание эффективной реализации сортированного списка с использованием generics Создание эффективной реализации сортированного списка с использованием generics | Категория реферата: Рефераты по информатике, программированию | Теги реферата: реферат мова, изложение язык | Добавил(а) на сайт: Bajdavletov. Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата     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.

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

На втором этапе производится классический бинарный поиск по ключу в сортированном массиве.