VPF::Хэш таблицы - Форум программистов

madbizarre

Дата 7.1.2011, 19:39 (ссылка)

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

Загрузка ...

Новичок

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

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

Задание преобразовать бинарное дерево в ХЭШ таблицу

Код


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

#define N 14 //размер таблицы
typedef struct sHashTable{ 
    struct sHashTable* next; 
    int      key; 
    int      value; 
}HashTable; 
 
typedef struct tree
{
  int value;    //данные
  struct tree *left;  //левое дерево
  struct tree *right; //правое дерево
} typTree;

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

HashTable *AddNode(int key, int value) 
{ 
    HashTable *AddNode = (HashTable*)malloc(sizeof(HashTable)); 
    if(AddNode != NULL) 
    { 
        AddNode->next = NULL; 
        AddNode->key   = 0; 
        AddNode->value = 0; 
 
        AddNode->key = key; 
        AddNode->value = value;
    printf(" %4d | %d \n",AddNode->value,AddNode->key);
    } 
    return AddNode; 
}

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 ObrabTree(typTree *root, int a[])
{
    if (root==NULL) return;  // Если дерево пустое 

  ObrabTree(root->left, a);  // Распечатать левое поддерево
  AddNode(HF(root->value),root->value);
  ObrabTree(root->right, a); // Распечать правое поддерево 
}

void zap_tree(int a[])        
{   typTree *root;
    int i;   
    root = NULL;   
    for (i=0;i<N;i++)
       root = add_to_tree(root, a[i]);
    ObrabTree(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: \nValue | Node\n");
zap_tree(a);
printf("\n");
    return 0;
}

Подскажите плиз, правельно ли я реализовал?

ValeryLaptev

Дата 10.1.2011, 02:03 (ссылка)

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

Загрузка ...

Препод

Профиль
Группа: Участник
Сообщений: 41
Регистрация: 19.8.2010
Где: Астрахань

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

Не совсем понятно, почему ваша хеш-таблица - это список? Смысл хеш-таблицы как раз в прямом доступе по индексу. Индекс вычисляется хеш-функцией. Вы его вычисляете, как остаток от деления. В этом случае лучше брать простое число, например 23 - чтобы не было общих делителей у value и делителем.

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