C двоичное дерево поиска с пользовательскими данными - PullRequest
Новая
       5

C двоичное дерево поиска с пользовательскими данными

0 голосов
/ 26 февраля 2012

Предположим, я получил внешнюю библиотеку bst, которая обрабатывает вставку пользовательских типов данных в bst

Вот функции new_node, insert и search: 

//new node

struct bst_node* new_node(void* data) 
{
    struct bst_node* result = malloc(sizeof(struct bst_node));
    assert(result);

    result->data = data;
    result->left = result->right = NULL;
    return result;
}

//insert node

void insert(struct bst_node** root, void* data) {
    struct bst_node** node = search(root, data);
    if (*node == NULL) {
        *node = new_node(data);
    }
}

//search node

    struct bst_node** search(struct bst_node** root, void* data) {
        struct bst_node** node = root;
        while (*node != NULL) {

        if (data, (*node)->data < 0)
            node = &(*node)->left;
        else if (compare_result > 0)
            node = &(*node)->right;
        else
            break;
    }
    return node;
}

и main.c, предположим, я прочитал модели из текстового файла: 

#include <stdio.h>
#include <stdlib.h>
#include "bst.h"
#include <string.h>

#define MAX 50

typedef struct data_t{
    int gg,mm,aaaa;    
}data;

typedef struct accesories_t{
    char name[MAX];
    int price;
    struct accesories_t *next;    
}accesories;

typedef struct model_t{
    //int index;
    char name[MAX];
    char file_a[MAX];
    data date;
    int price;
    accesories *acs;
}model;


int main(int argc, char *argv[])
{
    int menu=0;

    char nf[MAX];

    char name[MAX];
    char fa[MAX];
    int price,gg,mm,a;

    strcpy(nf,argv[1]);

    FILE *fp=fopen(nf,"+r");
    model m;
    struct bst_node* root = NULL;

    while(fscanf(fp,"%s %d//%d//%d %d %s",name,gg,mm,a,price,fa)!=EOF){
        strcpy(m.name,name);
        strcpy(m.file_a,fa);
        m.date.gg=gg;
        m.date.mm=mm;
        m.date.aaaa=a;
        m.price=price;
        m.index=index++;  

        insert(&root ,m);  
    }

  system("PAUSE");  
  return 0;
}

Итак, мой вопрос возникает в функции поиска, как я могу управлять компаратором для пользовательских данных (скажем, вставить модели, упорядоченные по имени (strcmp)? Я очень озадачен тем, как я могу передать имена в bst.c, учитывая, что bst.c понятия не имеет, как создается структура моей модели.

Должен ли я изменить библиотеку bst и, возможно, добавить в bst struct перед данными какой-нибудь индекс и использовать его в качестве компаратора?

ОК. Мне удалось это исправить, добавив строковый ключ в структуру bst

То, чего я сейчас пытаюсь добиться, - это вернуть тип void * data , приведенный в struct model, Предположим, что у меня есть дерево с узлами, содержащими данные, и после поиска я хочу вернуть Пример данных, содержащихся в узле и работа на нем, какие-либо подсказки ????

пробовал что-то вроде, но безуспешно предположим, что узел - это возвращенный узел из функции поиска 

model *m;
m=(model*)node->data;

как я мог этого достичь?

1 Ответ

0 голосов
/ 26 февраля 2012

Пример использования функций сравнения в качестве обратных вызовов.Определения для краткости опущены. 

int llist_cmp(struct llist *l, struct llist *r)
{
if (!l) return 1;
if (!r) return -1;
return strcmp(l->payload,r->payload);
}

struct llist * llist_split(struct llist **hnd, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *this, *save, **tail;

for (save=NULL, tail = &save; this = *hnd; ) {
        if (! this->next) break;
        if ( cmp( this, this->next) <= 0) { hnd = &this->next; continue; }
        *tail = this->next;
        this->next = this->next->next;
        tail = &(*tail)->next;
        *tail = NULL;
        }
return save;
}

struct llist * llist_merge(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *result, **tail;

for (result=NULL, tail = &result; one && two; tail = &(*tail)->next ) {
        if (cmp(one,two) <=0) { *tail = one; one=one->next; }
        else { *tail = two; two=two->next; }
        }
*tail = one ? one: two;
return result;
}

Кстати: вышеупомянутый фрагмент обрабатывает связанные списки, но механизм передачи указателей на функции, конечно, такой же, как и для деревьев.А ведь это была домашняя работа; -)

...