c - 符号表与集合

Question

来自 sedgewick course ，我了解到，

Symbol table

Symbol table is a key-value pair abstraction

where, given a key, search for the corresponding value.

value is not null

get() returns null if key not present

put() overwrites old value with new value.

引入Symbol table抽象后，不清楚，为什么引入Dictionary抽象和Map抽象？堆栈溢出维护这些标签。

使用List实现的符号表表示，

typedef struct{
  void **array;
  int size;
}List;

typedef struct{
  void *key;
  void *value; // cannot be null
}Pair;

typedef struct ST{

  List *keyValuePairList;
}ST;

---

来自 wiki ，我了解到，

A Set is an abstract data type that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite set.

根据 Set 的 wiki 定义，我得出结论，

Set is an abstraction that contains distinct items,

where, each item has a key,

maintaining corresponding value does not violate Set property,

value can be null,

get() returns null if key not present,

put() overwrite old value with new value, if value is not null.

---

从操作和数据方面看，Set和Symbol Table看起来很相似。很难理解，什么时候用什么？

使用 List 实现设置表示，

typedef struct{
  void **array;
  int size;
}List;

typedef struct{
  void *key;
  void *value; // can be null
}Pair;

typedef struct{

  List *keyValuePairList;
}Set;

---

问题:

区分Set和Symbol Table的是put()操作吗？我仍然看到这两个是一样的。

Answer 1

Set 只存储值，不存储键值对。

本类(class)描述为符号表的内容通常称为 map 。使用“符号表”作为抽象的名称是不合适的，因为它可能不会以表格的方式实现并且它可能不存储符号。

所以Set和Map的区别在于，Map将键映射到值，可以查找键对应的值，而Set只存储值，只能测试值(value)就在自己身上。尽管 Set 可以通过使用 Map 并将要插入的每个元素映射到自身或映射到 null 来简单地实现，正如您所建议的那样。

具有单独的 Set 抽象的目的是向其他程序员发出映射不重要的信号，并抽象出“虚拟”值(空值或值的副本)，从而节省输入并减少程序员的认知负担。