Категория
Информатика
Тип
реферат
Страницы
2 стр.
Дата
25.03.2009
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
20755.zip — 16.49 kb
  • sozdanie-jeffektivnoj-realizacii-sortirovannogo-spiska-s-ispolzovaniem-generics_20755_1.rtf — 101.75 Kb
  • Readme_docus.me.txt — 125 Bytes
Рейтинг
10  из 10
Оценок
1
Оцените работу
Хорошо  или  Плохо


Текст работы

ский
компаратор
internal int _count; // Количество элементов в объекте
bool _selected; // Выбран ли
элемент
internal int version=1; // Нужен для
перечислителей
public TwoLevelSortedDictionary(Generic.IKeyComparer Comp)
this._comparer = Comp;
CurrentLeafPage = new LeafPage(); // Выделяем страницу 1 уровня
_pageCount = 1;
Двухуровневый массив позволяет осуществлять навигацию по находящимся в
нем элементам. При этом возникает понятие текущего элемента, у которого
можно считывать или устанавливать значение, и читать значение ключа. Для
позиционирования на запись с некоторым ключом используется функция
NavigateKey.
Алгоритм работы этой функции таков. Поскольку информация в массиве всегда упорядочена, то поиск можно осуществлять с помощью алгоритма бинарного поиска (то есть половинного деления). Единственная проблема, не позволяющая использовать классический алгоритм напрямую – это то, что, что массив состоит из двух уровней. Поэтому алгоритм поиска разделяется на два
этапа. На первом этапе проверяется, есть ли массив верхнего уровня. Если есть, то в нем ищется страница, на которой может находиться искомый элемент. Если массива верхнего уровня нет, в качестве страницы, на которой будет
производиться дальнейший поиск, используется единственная существующая страница.
На втором этапе производится классический бинарный поиск по ключу в сортированном массиве.
public bool NavigateKey(K key)
// Устанавливаем индекс элемента в 0.
_currentElementIndex = 0;
// Если есть второй уровень...
if (_pageCount > 1)
// Перебираем грани
int hi = _pageCount - 1;
int lo = 0;
while (lo >



Ваше мнение



CAPTCHA