VPF::Б-деревья - Форум программистов

comp

Дата 3.6.2007, 20:27 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 61
Регистрация: 15.11.2006

Репутация: 1
Всего: 1

Читать Кормена, там всё описанно просто отлично!

pompei

Дата 18.10.2007, 08:01 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 155
Регистрация: 7.9.2007

Репутация: нет
Всего: 6

Могу предложить свою реализацию б-дерева (я его правда с явавского TreeMap слямзил)
Написан на чистом Си. Хорошо отлажен под Линуксом, думаю под Виндой работать будет также.

Работать с ним просто:
Например мы хотим хранить в дереве отсортированные по ФИО структуры типа

Код


typedef struct {
  int id;
  char *name;
  char *familyName;
  char *patronymic;
  int eyesColor;
} MyElement;

Тогда мы должны создать функцию сравнения:

Код


int fioCompare_MyElement( void *_a, void *_b, void *userData ) {
    if (_a == _b) return 0;
    MyElement *a = (MyElement *)_a;
    MyElement *b = (MyElement *)_b;
    int u = strcmp( a->familyName, b->familyName );
    if (u) return u;
    u = strcmp( a->name, b->name );
    if (u) return u;
    u = strcmp( a->patronymic, b->patronymic );
    if (u) return u;
    return a->id - b->id; // Пусть у нас будет уникальным только id
}

И создать дерево так:

Код


UTIL_BTREE my_tree = util_btree_new( fioCompare_MyElement, NULL );

Удалить дерево можно так:

Код


util_btree_free( my_tree, clearMyElement );

где clearMyElement - функция по удалению элемента MyElement, хотя можно передать NULL, если нам пофиг на память. Функция например такая:

Код


void clearMyElement( void *_v, void *userData ) {
    MyElement *e = (MyElement *)_v;
    free( e->familyName );
    free( e->name );
    free( e->patronymic );
    free( e );
}

Добавить элемент в дерево можно так:

Код


MyElement *pup = newMyElement( 10, "Пупкин", "Вася", "Петрович", GREEN );

MyElement *exists;
if (exists = util_btree_put( my_tree, pup )) {
    // обана, Пупкин то там уже есть
    // exists - это тот самый старый Пупкин, который сидел в дереве.
    // теперь в дереве сидит наш новый Пупкин pup
    делаем чё-то со старым Пупкиным exists
}

Надо когото найти в дереве:
делаем так:

Код



MyElement *gadya = newMyElement( 0, "Хренова", "Гадя", "Петрович", 0 );

MyElement *fnd = (MyElement *)util_btree_find( my_tree, gadya );

clearMyElement( gadya );

if (fnd == NULL) {
  // обана, Гадя потерялась
} else {
  // о-о-о, нашлась, ууаауу
  fnd->eyesColor - вот они какие глазки-та у нашей Гади!!!!
}

А вот как можно посмотреть всех:

Код


    //You may use iterator like:
    
    ITER_UBT iter; // This variable allocated in stack
    
    
    for (iter_ubt_init( &iter, tree ); iter_ubt_ok( &iter ); iter_ubt_next( &iter )) {
        void *value = iter_ubt_value( &iter );
        //working with current value
    }
    
    //or like:
    
    iter_ubt_init( &iter, tree );
    while (iter_ubt_ok( &iter )) {
        void *value = iter_ubt_value( &iter );
        //working with current value
        iter_ubt_next( &iter );
    }
    
    //NOTE!!!: when you deleted an item from tree, iterator would works wronge

В прикреплении реализация дерева с тестовым модулем

Это сообщение отредактировал(а) pompei - 18.10.2007, 08:56

Присоединённый файл ( Кол-во скачиваний: 67 )

btree.rar 4,28 Kb

--------------------

А всё оказывается гораздо проще: пассивные наноструктуры - активные наноструктуры - системы наносистем - молекулярные наносистемы - сингулярность! По пять лет на каждый этап.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »