C - 需要帮助实现 ADT

Question

我正在完成一项学校作业，但无法理解如何使用 ADT。基本上，我需要实现一个存储<key, value>的符号表ADT。对。与键关联的值是用户定义的任意对象，通过 void 指针传递给 ADT。我已经包含了头文件，我只需要为其制作源文件。

我坚持的声明是针对结构本身的。它是由 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，而只是使用前向声明。对于遍历，您可能还想定义一个同样不透明的迭代器类型，例如

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，但实际类型是抽象的 - 没有任何信息泄露表的实现，例如无论是链表、哈希表还是其他东西。