Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Отступление на тему языка С. Быстрый поиск и сортировка в языке С

Читайте также:
  1. E - Ученики, которые не изучают ничего, кроме одного языка программирования
  2. GJ Camp 2013 приглашает в волшебный мир английского языка.
  3. Marilyn Manson: Ну, это – ссылка на фильм, «Chitty Chitty Bang Bang» (прим. На русский перевели как «Пиф-паф ой-ой-ой», как мне говорит кинопоиск), ты его смотрел?
  4. Rule # 2Чтобы задать вопрос в английском языке, вспомогательный глагол нужно поставить на первое место
  5. А.С. Пушкин – основоположник совр рус лит языка
  6. Автоматический поиск несоответствия в словах собеседника
  7. Алгоритм поиска подстроки Кнута-Морриса-Пратта (на основе префикс-функции)

В конкретных реализациях степень В-дерева может быть весьма большой. Поэтому поиск элемента в одной вершине при больших степенях В-деревьев следует производить с помощью двоичного поиска. В языке С есть стандартная функция для поиска в упорядоченном массиве bsearch. Например, в Microsoft Visual C эта функция имеет следующее описание

void *bsearch(const void * key, const void * base, size_t nmemb, size_t size, int (__cdecl * compare ) (const void * elem1, const void * elem2 ));

В других компиляторах описание этой функции аналогично, быть может, с точностью до тонкостей. Например, в компиляторе gcc описание этой функции имеет следующий вид

void *bsearch(const void * key, const void * base, size_t nmemb, size_t size, int (* compare )(const void * elem1, const void * elem2 ));

Здесь key – указатель на искомый элемент, base – указатель на массив с данными, nmemb – количество элементов в массиве, size – размер в байтах одного элемента массива, compare – указатель на функцию, получающую указатель на два элемента массива и возвращающую результат сравнения элементов: +1 – если первый элемент больше второго, -1 – если второй элемент больше первого, 0 – если элементы равны.

Для нашего случая – поиска целого числа в массиве функция сравнения может быть определена следующим образом

int compare (const void *v0,const void *v1)

{ return *(int*)v0>*(int*)v1? 1: *(int*)v0<*(int*)v1? -1: 0; }

 

К сожалению, если данный элемент в массиве не найдет, то функция bsearch возвращает NULL, при этом информация о том – между какими элементами находится искомый, теряется. Если нам все же хочется непременно воспользоваться функцией bsearch, то мы можем применить некоторый трюк: мы можем воспользоваться информацией о том, что реально – первый параметр bsearch это – адрес искомого элемента, а второй – адрес некоторого элемента в массиве. Исходя из алгоритма двоичной сортировки, если искомый элемент в массиве отсутствует, то последний элемент *v1 при вызове функции compare, для которого оказалось, что

*(int*)v0<*(int*)v1

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

int *v_gt_save=NULL;

int compare (const void *v0,const void *v1)

{

if(*(int*)v0>*(int*)v1)return 1;

if(*(int*)v0<*(int*)v1){v_gt_save=(int*)v1;return -1;}

Return 0;

}

 

Функция поиска вершины может тогда выглядеть следующим образом

 

BNode *BSearchQ(BNode *root, int v)

{

if(root==NULL)return NULL;

root->value[root->n]= INT_MAX;

if(bsearch(&v, root->value, root->n+1, sizeof(int),compare))return root;

return BSearchQ(root->child[v_gt_save-root->value], v);

}

Здесь константа INT_MAX обозначает максимальное число типа int. Данная константа (определяемая через #define) является, фактически, стандартной в разных версиях языка С. Так, например, в Microsoft Visual C и GCC эта константа определяются в стандартном файле include.h.

Отметим, что данный подход, возможно, не является оптимальным как в плане скорости счета (присутствует лишняя операция присваивания v_gt_save=(int*)v1), так и в плане выполнения правил хорошего тона (в алгоритме использовались глобальные переменные). Однако этот подход немного экономит время программиста (не надо программировать алгоритм двоичного поиска). В нашем же случае он, скорее, служит примером использования функции bsearch.

Еще одним примером использования указателей на функцию является использование функции быстрой сортировки. Функция имеет следующее описание в Microsoft Visual C

void qsort(void * base, size_t num, size_t size, int (__cdecl * compare )(const void * elem1, const void * elem2 ));

а в GCC:

void qsort ( void * base, size_t num, size_t size, int (* compar ) (const void*,const void*));

здесь base – указатель на массив с данными, num – количество элементов в массиве, size – размер в байтах одного элемента массива, compare – указатель на функцию, получающую указатель на два элемента массива и возвращающую результат сравнения элементов: +1 – если первый элемент больше второго, -1 – если второй элемент больше первого, 0 – если элементы равны.

Например, в нашем случае отсортировать массив элементов одной вершины node В-дерева можно следующим образом

Bnode *node;

qsort(node->value, node->n, sizeof(int),compare);


Дата добавления: 2015-10-30; просмотров: 139 | Нарушение авторских прав


Читайте в этой же книге: InsertData( value, head, current); | Реализация L2-списка на основе двух стеков | Поиск пути в графе с наименьшим количеством промежуточных вершин | Поиск кратчайшего пути в графе | Добавление элемента | Сбалансированные и идеально сбалансированные бинарные деревья поиска | Добавление элемента в дерево | Разбиение дерева по разбивающему элементу | Добавление элемента в красно-черное дерево | Однопроходное добавление элемента в красно-черное дерево |
<== предыдущая страница | следующая страница ==>
Удаление элемента из красно-черного дерева| Удаление вершины из B-дерева

mybiblioteka.su - 2015-2024 год. (0.011 сек.)