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: %sn", symtable_iterator_key(it), symtable_iterator_value(it));
}
symtable_iterator_free(it);
symtable_free(table);

请注意，函数集如何明确定义数据结构的API，但实际类型是抽象的-没有任何信息可以泄露表的实现，例如，它是链表还是哈希表或其他什么。