Ç - 需要帮助实现一个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，但实际类型是抽象的 - 有没有信息这给走表的实现，例如无论是链表还是哈希表或别的东西。