数据结构 | 字典

  本博文中引入的：

• 类AList-参见数据结构 | 线性表：顺序表 链表。

一些术语：

• 关键码-数据元素中能起标识作用的数据项。
• 可比对象-如果一个集合的两个元素x和y在给定的关系下有xRy或yRx，则称x和y是可比的。
• 偏序-如果一个二元关系是反对称的和传递的（例如小于、等于、大于等二元关系），那么这个关系就称为一个偏序。
• 全序-如果偏序中每一对不同元素都是可比的，则称该偏序为全序。
• 键值对-字典的基本元素，包含一条记录及其相关的关键码。

  为了实现检索功能，要求检索关键码是可比的，也就是说，对于至少两个关键码，必须能够正确地确定他们是否相等，这样便能顺利找出与关键码值相匹配的记录。一般而言，要求能对关键码定义一个全序，这样能更好地组织数据库、更有效地检索数据。实际上，大多数数据类型都拥有自然顺序，比如intger，float，double等。

单击此处查看字典的抽象类声明

  下面是从教材中摘录的字典的抽象类声明。

// The Dictionary abstract class.
template <typename Key, typename E>
class  Dictionary {
private:
  void operator =(const Dictionary&) {}
  Dictionary(const Dictionary&) {}

public:
  Dictionary() {}          // Default constructor
  virtual ~Dictionary() {} // Base destructor

  // Reinitialize dictionary
  virtual void clear() = 0;

  // Insert a record
  // k: The key for the record being inserted.
  // e: The record being inserted.
  virtual void insert(const Key& k, const E& e) = 0;

  // Remove and return a record.
  // k: The key of the record to be removed.
  // Return: A maching record. If multiple records match
  // "k", remove an arbitrary one. Return NULL if no record
  // with key "k" exists.
  virtual E remove(const Key& k) = 0;

  // Remove and return an arbitrary record from dictionary.
  // Return: The record removed, or NULL if none exists.
  virtual E removeAny() = 0;

  // Return: A record matching "k" (NULL if none exists).
  // If multiple records match, return an arbitrary one.
  // k: The key of the record to find
  virtual E find(const Key& k) const = 0;

  // Return the number of records in the dictionary.
  virtual int size() = 0;
};

  注意函数removeAny的作用。它完全任意地选择一条记录进行删除并返回该记录的操作，允许用户随意遍历整个字典。如果没有这个函数，用户将无法获取关键码未知的记录。下面的函数可以得到字典的所有记录：

while (dict.size > 0) {
  it = dict.removeAny();
  doSomething(it);
}

  下面来构造一个键值对类。

单击此处查看键值对的实现

  下面是从教材中摘录的键值对的实现。

// Container for a key-value pair
template <typename Key, typename E>
class KVpair {
private:
  Key k;
  E e;
public:
  // Constructors
  KVpair() {}
  KVpair(Key kval, E eval)
    { k = kval; e = eval; }
  KVpair(const KVpair& o)  // Copy constructor
    { k = o.k; e = o.e; }

  void operator =(const KVpair& o) // Assignment operator
    { k = o.k; e = o.e; }

  // Data member access functions
  Key key() { return k; }
  void setKey(Key ink) { k = ink; }
  E value() { return e; }
};

  顺序表和链表都可以用以实现字典。教材中使用的是顺序表（链表的实现与其十分相似，不再赘述），并采用了两种顺序表来实现它——无序顺序表和有序顺序表。

单击此处查看使用无序顺序表实现的字典的实现

  下面是从教材中摘录的使用无序顺序表实现的字典的实现。

// Dictionary implemented with an unsorted array-based list
template <typename Key, typename E>
class UALdict : public Dictionary<Key, E> {
private:
  AList<KVpair<Key,E> >* list;
public:
  UALdict(int size=defaultSize)   // Constructor
    { list = new AList<KVpair<Key,E> >(size); }
  ~UALdict() { delete list; }         // Destructor
  void clear() { list->clear(); }     // Reinitialize

  // Insert an element: append to list
  void insert(const Key&k, const E& e) {
    KVpair<Key,E> temp(k, e);
    list->append(temp);
  }

  // Use sequential search to find the element to remove
  E remove(const Key& k) {
    E temp = find(k); // "find" will set list position
    if(temp != NULL) list->remove();
    return temp;
  }

  E removeAny() { // Remove the last element
    Assert(size() != 0, "Dictionary is empty");
    list->moveToEnd();
    list->prev();
    KVpair<Key,E> e = list->remove();
    return e.value();
  }

  // Find "k" using sequential search
  E find(const Key& k) const {
    for(list->moveToStart();
        list->currPos() < list->length(); list->next()) {
      KVpair<Key,E> temp = list->getValue();
      if (k == temp.key())
        return temp.value();
    }
    return NULL; // "k" does not appear in dictionary
  }
  int size() // Return list size
    { return list->length(); }
};

  使用有序线性表来实现时，不能直接继承List ADT。这是因为原本的List ADT在插入元素时实际上是在表末添加元素。为了保证有序线性表的有序性，需要重新定义insert函数。其余函数不变，可以直接使用AList中的函数。

单击此处查看有序顺序表的实现

  下面是从教材中摘录的有序顺序表的实现。

// Sorted array-based list
// Inherit from AList as a protected base class
template <typename Key, typename E>
class SAList: protected AList<KVpair<Key,E> > {
public:
  SAList(int size=defaultSize) :
    AList<KVpair<Key,E> >(size) {}

  ~SAList() {}                    // Destructor

  // Redefine insert function to keep values sorted
  void insert(KVpair<Key,E>& it) { // Insert at right
    KVpair<Key,E> curr;
    for (moveToStart(); currPos() < length(); next()) {
      curr = getValue();
      if(curr.key() > it.key())
        break;
    }
    AList<KVpair<Key,E> >::insert(it); // Do AList insert
  }

  // With the exception of append, all remaining methods are
  // exposed from AList. Append is not available to SAlist
  // class users since it has not been explicitly exposed.
  AList<KVpair<Key,E> >::clear;
  AList<KVpair<Key,E> >::remove;
  AList<KVpair<Key,E> >::moveToStart;
  AList<KVpair<Key,E> >::moveToEnd;
  AList<KVpair<Key,E> >::prev;
  AList<KVpair<Key,E> >::next;
  AList<KVpair<Key,E> >::length;
  AList<KVpair<Key,E> >::currPos;
  AList<KVpair<Key,E> >::moveToPos;
  AList<KVpair<Key,E> >::getValue;
};

单击此处查看使用有序顺序表实现的字典的实现

  下面是从教材中摘录的使用有序顺序表实现的字典的实现。

// Dictionary implemented with a sorted array-based list
template <typename Key, typename E>
class SALdict : public Dictionary<Key, E> {
private:
  SAList<Key,E>* list;
public:
  SALdict(int size=defaultSize)   // Constructor
    { list = new SAList<Key,E>(size); }
  ~SALdict() { delete list; }         // Destructor
  void clear() { list->clear(); }     // Reinitialize

  // Insert an element: Keep elements sorted
  void insert(const Key&k, const E& e) {
    KVpair<Key,E> temp(k, e);
    list->insert(temp);
  }

  // Use sequential search to find the element to remove
  E remove(const Key& k) {
    E temp = find(k);
    if (temp != NULL) list->remove();
    return temp;
  }

  E removeAny() { // Remove the last element
    Assert(size() != 0, "Dictionary is empty");
    list->moveToEnd();
    list->prev();
    KVpair<Key,E> e = list->remove();
    return e.value();
  }

  // Find "K" using binary search
  E find(const Key& k) const {
    int l = -1;
    int r = list->length();
    while (l+1 != r) { // Stop when l and r meet
      int i = (l+r)/2; // Check middle of remaining subarray
      list->moveToPos(i);
      KVpair<Key,E> temp = list->getValue();
      if (k < temp.key()) r = i;        // In left
      if (k == temp.key()) return temp.value(); // Found it
      if (k > temp.key()) l = i;        // In right
    }
    return NULL; // "k" does not appear in dictionary
  }
  int size() // Return list size
    { return list->length(); }
};

  使用无序顺序表实现字典时，insert和removeAny操作需要常数时间，find和remove操作则需要$\Theta(n)$。而使用有序顺序表实现时，注意到insert操作时间代价变为$\Theta(n)$，find操作时间代价变为$\Theta(\log n)$。这是因为使用有序顺序表实现时，函数find的实现使用了二分法来检索——这种方法相比依次查找效率高得多。因此，选用哪一种方式实现，取决于插入操作和查询操作的相对次数。

  使用有序顺序表实现字典时，一个比较关键的地方是对关键码进行比较。这在关键码是int类型时很容易实现。但是，关键码也可能是字符串指针等等。有以下两个办法解决这个问题：

• 使用特殊的比较方法-重载== <= >=运算符，但是由于它没有体现在接口中，常常被忽略。
• 传入一个较泛化的比较函数-让用户自己定义比较类来比较关键码。该定义作为模板的一个参数，在使用字典时，必须将这个定义传入。这样的设计称为“策略”设计模式，因为用户要明确提供做某些操作的策略。
• 将关键码与值绑定-某些情况下，利用比较类从记录中抽取关键码，比存储键值对更合适。博主认为，这是说关键码的确定来源于记录，记录的相对大小（由用户定义）确定了关键码的相对大小（由用户定义），这使得关键码和记录的相对大小总是一致，这样能更好地管理以有序顺序表实现的字典。（若有误，还望在评论区指出，谢谢！）