C - Нужна помощь в реализации ADT

Question

Я работаю над назначением школы, и у меня возникли проблемы с пониманием того, как использовать ADT. В принципе, мне нужно реализовать таблицу символов ADT, в которой хранятся пары <key, value>. Значение, связанное с ключом, представляет собой произвольный объект, определенный пользователем, который передается ADT указателем void. У меня уже есть файл заголовка, мне просто нужно сделать для него исходный файл.

Декларация, на которую я застрял, относится к самой структуре. Это объект таблицы символов, указатель которого имеет указатель типа SymTable_T. Он должен иметь возможность вставлять в него копии вставленных пар <key, value>, и эти копии должны быть уничтожены при удалении из таблицы или когда сама таблица уничтожена.

Реализация должна использовать хеш-таблицу, которая использует цепочку для разрешения конфликтов. Я уже знаком с хешированием, поэтому проблем там нет.

Это то, что я придумал:

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include "symTable.h" 
#define DEFAULT_TABLE_SIZE 61 
#define HASH_MULTIPLIER 65599 

typedef struct SymTable *SymTable_T; 
{ 
    char *key; 
    int value; 
    struct SymTable *next; //linked list 
}; 

Может кто-то мне точку в правильном направлении? Может ли кто-нибудь объяснить мне суть внедрения ADT? Огромное спасибо заранее!

Answer 1

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

В вашем примере это означает, что вы не определяют struct в файле заголовка, а просто используйте декларацию forward. Для обхода вы также можете определить одинаково непрозрачный тип итератора, например.

struct symtable; 
struct symtable_iterator; 

... а затем набор функций, работающих со столом, например.

/* Create symtable, destroy it, insert values. */ 
void symtable_alloc(struct symtable **table); 
void symtable_free(struct symtable *table); 
void symtable_insert(struct symtable *table, const char *key, void *value); 

/* Create symtable iterator, destroy it, access key/value. */ 
void symtable_iterator_alloc(struct symtable *table, struct symtable_iterator **it); 
void symtable_iterator_free(struct symtable_iterator *it); 
bool symtable_iterator_next(struct symtable_iterator **it); 
const char *symtable_iterator_key(struct symtable_iterator *it); 
void *symtable_iterator_value(struct symtable_iterator *it); 

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

Вы можете использовать их как

struct symtable *table; 
symtable_alloc(&table); 
symtable_insert(table, "one", "eins"); 
symtable_insert(table, "two", "zwei"); 
symtable_insert(table, "three", "drei"); 

struct symtable_iterator *it; 
symtable_iterator_alloc(table, &it); 
while (symtable_iterator_next(&it)) { 
    printf("%s: %s\n", symtable_iterator_key(it), symtable_iterator_value(it)); 
} 
symtable_iterator_free(it); 
symtable_free(table); 

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