VPF::Преобразовать бинарное дерево в хэш-таблицу

madbizarre

Дата 1.12.2010, 22:11 (ссылка)

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

Загрузка ...

Новичок

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

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

Вот такое вот задание:
Преобразовать бинарное дерево в хэш-таблицу (хэш-функция h(k)=k mod n, где k - элемент, n - количество строк таблицы)

Код


#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define N 14 //размер таблицы
typedef struct hashtable
{
    int table;
    int key;
} typHashTable;

typedef struct tree
{
  struct hashtable value;    //данные
  struct tree *left;  //левое дерево
  struct tree *right; //правое дерево
} typTree;

int HF(int k)
{
int h;
return h = (k % N);
}

typTree *add_to_tree(typTree *root, int new_value)
{   
    if (root==NULL)  // если нет сыновей - создаем новый элемент     
    {        
        root = (typTree *)malloc(sizeof(typTree));        
        root->value.table = new_value;
        root->value.key = HF(new_value);
        root->left = root->right = 0;        
        return root;     
    }   
    if (root->value.table < new_value)          // добавлем ветвь     
             root->right = add_to_tree(root->right, new_value);   
    else     root->left  = add_to_tree(root->left,  new_value);   
    return root;
}


void printTree(typTree *root, int a[])
{
    if (root==NULL) return;  // Если дерево пустое 

    printTree(root->left, a);  // Распечатать левое поддерево
    printf("%d %d \n",root->value.table,root->value.key); // Распечатать корень дерева
    printTree(root->right, a); // Распечать правое поддерево 
  free(root);
}

void zap_tree(int a[])        
{   typTree *root;
    int i;   
    root = NULL;   
    for (i=0;i<N;i++)
       root = add_to_tree(root, a[i]);
    printTree(root,a);
}


int main()
{
int i;   /* Это будем сортировать */   
int a[N]={ 2,7,8,3,52,14,16,18,15,13,42,30,35,26 };        
printf("Ishodniy massiv:\n");   
    for (i=0;i<N;i++) 
        printf("%d ",a[i]);
printf("\nHash table: \n");
zap_tree(a);
printf("\n");
    return 0;
}

Вот мой код, работает без ошибок, но у меня вопрос есть, правильно ли я сделал smile

Или я не так понял задание?

baldina

Дата 2.12.2010, 19:24 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

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

Цитата

Преобразовать бинарное дерево в хэш-таблицу

это значит, что надо взять данные из дерева (путем обхода дерева) и поместить в хэш-таблицу, а не хранить значения хэш-функции в узлах дерева, как у Вас.
т.е. надо
1. построить дерево
2. для каждого элемента дерева поместить этот элемент в хэш-таблицу

madbizarre

Дата 6.12.2010, 19:55 (ссылка)

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

Загрузка ...

Новичок

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

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

Чтото у меня не получается, я понимаю что по хэш таблице надо перемещаться после заполения элемента, но как это сделать не получается...

Код


#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define N 14 //размер таблицы
typedef struct hashtable
{
    int table;
    int key;
    struct hashtable *next; 
} typHashTable;
typHashTable *tHT;

typedef struct tree
{
  int value;    //данные
  struct tree *left;  //левое дерево
  struct tree *right; //правое дерево
} typTree;

int HF(int k)
{
int h;
return h = (k % N);
}

typTree *add_to_tree(typTree *root, int new_value)
{   
    if (root==NULL)  // если нет сыновей - создаем новый элемент     
    {        
        root = (typTree *)malloc(sizeof(typTree));        
        root->value = new_value;
        root->left = root->right = 0;        
        return root;     
    }   
    if (root->value < new_value)          // добавлем ветвь     
             root->right = add_to_tree(root->right, new_value);   
    else     root->left  = add_to_tree(root->left,  new_value);   
    return root;
}


void printTree(typTree *root, int a[])
{
    if (root==NULL) return;  // Если дерево пустое 

    printTree(root->left, a);  // Распечатать левое поддерево
  tHT->table = root->value;
  tHT->key = HF(root->value);
  printf("%d %d\n",tHT->table,tHT->key); // Распечатать корень дерева
  printTree(root->right, a); // Распечать правое поддерево 

  //free(root);
}

void zap_tree(int a[])        
{   typTree *root;
    int i;   
    root = NULL;   
    for (i=0;i<N;i++)
       root = add_to_tree(root, a[i]);
    printTree(root,a);
}


int main()
{
int i;   /* Это будем сортировать */   
int a[N]={ 2,7,8,3,52,14,16,18,15,13,42,30,35,26 };        
printf("Ishodniy massiv:\n");   
    for (i=0;i<N;i++) 
        printf("%d ",a[i]);
printf("\nHash table: \n");
zap_tree(a);
printf("\n");
    return 0;
}

madbizarre

Дата 10.12.2010, 19:09 (ссылка)

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

Загрузка ...

Новичок

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

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

Да реал, помогите, не получается решить :(

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