链表实现字典

字典

字典是一些元素的集合，每个元素都有一个成为key的域。不同元素的key各不相同。有关字典的操作有：
-1:插入给定关键字值得元素
-2:在字典中寻找具有给定关键字值得元素
-3:删除给定关键字值得元素

如果仅按照一个字典元素本身的关键字来访问该元素，则称为随机访问。而顺序访问是按照关键字的递增顺序逐个访问字典中的元素。顺序访问需要借助Begin(用来返回关键字最小的元素)和Next(用来返回下一个元素)等操作来实现。

有重复元素的字典，只是允许多个元素有相同的关键字。在有重复元素的字典中，在进行搜索和删除时需要一个规则来消除歧义。也就是说，如果要搜索（或删除）关键字为k的元素，那么在所有的关键字为k值得元素中应该返回哪一个。

下面我们使用链表来实现一个字典：

//============================================================================
// Name        : Dict.cpp
// Author      : 陈洪波
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include "Exception.h"
#include <iostream>
using namespace std;

template<class E, class K>
class ChainNode {
public:
    E data;   //数据元素
    K key;    //关键字
    ChainNode<E, K> *link;  //链表的下一个节点
};

template<class E, class K>
class SortedChain {
public:
    SortedChain() {  //构造函数
        first = 0;
    }
    ~SortedChain();  //析构函数
    bool IsEmpty() const {
        return first == 0;   //当first为0的时候，该字典为空
    }
    int Length() const;   //返回字典的长度
    bool Search(const K& k, E& e) const;   //查询指定关键字的元素，并赋值给e
    SortedChain<E, K>& Delete(const K& k, E& e);  //删除指定关键字的元素，将元素赋值给e
    SortedChain<E, K>& DistinctInsert(const K&k, E& e);  //插入不同关键字的元素
private:
    ChainNode<E, K> *first;
};

template<class E, class K>
SortedChain<E, K>::~SortedChain() {
    ChainNode<E, K> *p;

    /**
     * 删除每一个节点
     */
    while (first) {
        p = first->link;
        delete first;
        first = p;
    }
}

template<class E, class K>
int SortedChain<E, K>::Length() const {
    ChainNode<E, K> *p = first;
    int count = 0;

    /**
     * 每经过一个节点，count加一
     */
    while (p) {
        count++;
        p = p->link;
    }

    return count;
}

template<class E, class K>
bool SortedChain<E, K>::Search(const K& k, E& e) const {
    ChainNode<E, K> *p = first;

    /**
     * 从小到大开始遍历，及时停止
     */
    for (; p && p->key < k; p = p->link)
        ;

    if (p && p->key == k) {
        e = p->data;
        return true;
    }

    return false;
}

template<class E, class K>
SortedChain<E, K>& SortedChain<E, K>::Delete(const K &k, E &e) {
    ChainNode<E, K> *p = first;
    ChainNode<E, K> *tp = 0; //跟踪p

    /**
     * 原理和搜索差不多，只不过就是找到之后删除这个元素
     * 所以需要有一个元素来追踪元素p
     */
    for (; p && p->key < k; tp = p, p = p->link)
        ;

    if (p && p->key == k) { //找到匹配的元素
        e = p->data;

        if (tp) {
            tp->link = p->link;
        } else {
            first = p->link;
        }

        delete p;

        return *this;
    } else {
        throw BadInput();
    }
}

template<class E, class K>
SortedChain<E, K>& SortedChain<E, K>::DistinctInsert(const K& k, E& e) {
    ChainNode<E, K> *p = first;
    ChainNode<E, K> *tp = 0;

    /**
     * 同样，找到插入点的位置，再新建一个Node,将元素插入进去
     */
    for (; p && p->key < k; tp = p, p = p->link)
        ;

    if (p && p->key == k)
        throw BadInput();

    ChainNode<E, K> *q = new ChainNode<E, K>;
    q->data = e;
    q->key = k;

    q->link = p;

    if (tp)
        tp->link = q;
    else
        first = q;

    return *this;
}

int main() {
    SortedChain<int, int> sc;

    int i = 1;
    int j = 2;
    sc.DistinctInsert(i, i);
    sc.DistinctInsert(j, j);

    int m;
    sc.Search(1,m);

    cout << m << endl;
    return 0;
}