Связывание двух многомерных массивов с помощью указателей

Question

Мне нужно объединить двоичную кучу и Linear Probing Hashtable, чтобы создать «составную» структуру данных, которая обладает функциональностью кучи, с возможностью сортировки хэш-таблицы. Что мне нужно сделать, так это создать 2-х мерные массивы для каждой структуры данных (Binary Heap и Hash), а затем связать их друг с другом указателями, чтобы при изменении вещей, например, удалении значения в двоичной куче, он также получает удалены в таблице Hash. Поэтому мне нужно иметь одну строку массива кучи, указывающую от кучи к Hastable, и одну строку массива хеш-таблицы, указывающую от хэш-таблицы на кучу. Любая помощь только в том, как связать эти два вместе, оценивается, после некоторых идей, я могу, вероятно, понять это, просто возникли проблемы с запуском.

Answer 1

Зачем беспокоиться о ссылках?

У вас есть две ассоциативные структуры просто дублировать любую операцию на один к другому (гарантируя, что если одна операция excepts вы либо обрушить всю вещь или оставить объект в допустимом состоянии, если вы заботитесь о таких вещах)

Если вы не можете использовать структуру одного, чтобы помочь вам с другим (и я не вижу, как вы можете, так как либо он может полностью изменить его внутреннее состояние при любой операции модификации), это так же эффективно и намного проще.

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

Answer 2

Создайте контейнер, содержащий оба, с функциями/методами доступа (в зависимости от языка реализации), который выполняет все операции, необходимые для вашего алгоритма.

IE: Удалить из контейнера: удаляет из двоичного и из хэша.

Добавить к контейнеру: добавляется в бинарный файл и помещается в хэш.

EDIT: О, задание - весело! :)

Я бы это сделал: все еще реализует контейнер. Но вместо использования стандартной библиотеки для btree/hash реализуйте их следующим образом: Сделайте тип, который может быть помещен в ваш член данных, который имеет указатель на узел BTree и узел Hashtable, в котором находится элемент данных.

Чтобы удалить элемент данных, указав его, вы можете выполнить алгоритм удаления на btree (перейдите к родительскому указателю узла, удалите дочерний элемент (слева или справа), дерево реструктуризации) и в хеш-таблице (удалите из хеш-листа). При добавлении значения выполните алгоритм добавления на btree и хеш, но убедитесь, что вы обновили указатели узлов в данных перед возвратом.

Некоторые псевдокод (я буду использовать C, но я не уверен, что язык вы используете): ЬурейеЕ структуры { BTreeNode * ВТКЕЕ HashNode * хэш } ContianerNode;

поместить данные в контейнере:

typedef struct 
{ 
    ContainerNode node; 
    void* data; /* whatever the data is */ 
} Data; 

BTreeNode есть что-то вроде:

typedef struct _BTreeNode 
{ 
    struct _BTreeNode* parent; 
    struct _BTreeNode* left; 
    struct _BTreeNode* right; 
} BTreeNode; 

и HashNode есть что-то вроде:

typedef struct _HashNode 
{ 
    struct _HashNode* next; 
} HashNode; 
/* ala singly linked list */ 

и ваш BTree будет указатель на BTreeNode и ваш hastable будет массивом указателей на HashNodes. Как это:

typedef struct 
{ 
    BTreeNode* btree; 
    HashNode* hashtable[HASHTABLESIZE]; 
} Container; 

void delete(Container* c, ContainerNode* n) 
{ 
    delete_btree_node(n->btree); 
    delete_hashnode(n->hash); 
} 

ContainerNode* add(Container* c, void* data) 
{ 
    ContainerNode* n = malloc(sizeof(ContainerNode)); 
    n->btree = add_to_btree(n); 
    n->hash = add_to_hash(n); 
} 

Я дам вам выполнить эти и другие функции (не может делать все для тебя задание;))