Читайте также:
|
|
В конкретных реализациях степень В-дерева может быть весьма большой. Поэтому поиск элемента в одной вершине при больших степенях В-деревьев следует производить с помощью двоичного поиска. В языке С есть стандартная функция для поиска в упорядоченном массиве 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 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Удаление элемента из красно-черного дерева | | | Удаление вершины из B-дерева |