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

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

0 голосов
/ 22 апреля 2009

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

Ответы [ 2 ]

1 голос
/ 22 апреля 2009

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

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

Добавить в контейнер: добавляет в двоичный файл и в хэш.

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

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

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

Какой-то псевдокод (я буду использовать C, но я не уверен, какой язык вы используете): typedef struct { BTreeNode * btree HashNode * hash } 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);
}

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

0 голосов
/ 22 апреля 2009

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

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

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

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

...