字典 原

#include<iostream>
#include"sortedchain.h"

using namespace std;

int main(void)
{
    sortedChain<int,int> z;
    pair<int,int> p;

    p.first = 2;p.second = 10;
    z.insert(p);
    p.first = 10;p.second = 50;
    z.insert(p);
    p.first = 6;p.second = 30;
    z.insert(p);
    p.first = 8;p.second = 40;
    z.insert(p);
    p.first = 1;p.second = 5;
    z.insert(p);
    p.first = 12;p.second = 60;
    z.insert(p);

    cout<<"The chain is" << z <<endl;
    cout <<"Its size is"<<z.size() <<endl;

    cout<<"Element associated with 1 is "<<z.find(1)->second<<endl;
    cout<<"Element associated with 6 is "<<z.find(6)->second<<endl;
    cout<<"Element associated with 12 is "<<z.find(12)->second<<endl;

    z.erase(1);
    z.erase(2);
    z.erase(6);
    z.erase(12);
    cout<<"Deleted 1,2,6,12"<<endl;
    cout<<"The chain is "<<z<<endl;
    cout<<"Its size is "<<z.size()<<endl;

    return 0;
}

/*
 * 数值对节点的定义
 * pairNode.h
*/


#ifndef PAIRNODE_H
#define PAIRNODE_H
#include<iostream>

using namespace std;

template<class K,class E>
struct pairNode
{
    typedef pair<const K,E> pairType;
    pairType element;
    pairNode<K,E> *next;

    pairNode(const pairType& thePair):element(thePair) {}
    pairNode(const pairType &thePair,pairNode<K,E>* theNext)
        :element(thePair){next = theNext;}
};

#endif // PAIRNODE_H

/*
 * 字典的抽象类，定义了字典操作需要的基本函数
 * 其中，K代表关键字，E代表值
 * dictionary.h
 *
*/
#ifndef DICTIONARY_H
#define DICTIONARY_H

#include"pairnode.h"
#include"iostream"
using namespace std;

template<class K,class E>//K代表关键字，E代表值
class dictionary
{
  public:
    virtual ~dictionary(){}
    virtual bool empty() const = 0;//如果字典为空，返回true
    virtual int size() const = 0;//返回字典中数值对的数量

    //返回某关键字所对应的值
    virtual pair<const K,E>* find(const K&) const = 0;

    //删除某关键字对应的数值对
    virtual void erase(const K&) = 0;

    //将某对数值对插入字典中
    virtual void insert(const pair<const K,E>&) = 0;
};


#endif // DICTIONARY_H

/*
 *
*/
#ifndef SORTEDCHAIN_H
#define SORTEDCHAIN_H

#include<iostream>
#include"dictionary.h"
#include"pairnode.h"

using namespace std;

template<class K,class E>
class sortedChain : public dictionary<K,E>
{
  public:
    sortedChain() {firstNode = NULL;dSize = 0;}
    ~sortedChain();

    bool empty() const{return dSize == 0;}//有序链表是否为空
    int size() const{return dSize;}//返回有序链表元素个数
    pair<const K,E>* find(const K&) const;//查找K值对应的某个元素对
    void erase(const K&);//删除K值对应的某个元素对
    void insert(const pair<const K,E>&);//插入元素对
    void output(ostream& out) const;//输出链表元素

protected:
    pairNode<K,E>* firstNode;//指向链表中的第一个节点
    int dSize;//字典中元素的个数，一个元素等于一个数对
};

template<class K,class E>
sortedChain<K,E>::~sortedChain()//析构函数，删除所有节点
{
    while(firstNode != NULL)//顺次删除所有节点
    {
        pairNode<K,E>* nextNode = firstNode->next;
        delete firstNode;
        firstNode = nextNode;
    }
}

template<class K,class E>
pair<const K,E>* sortedChain<K,E>::find(const K& theKey) const//查找theKey对应的数对
{
    pairNode<K,E>* currentNode = firstNode;

    while(currentNode != NULL &&
          currentNode->element.first != theKey)
        currentNode = currentNode->next;

    if(currentNode != NULL && currentNode->element.first == theKey)
        return &currentNode->element;

    return NULL;
}

template<class K,class E>
void sortedChain<K,E>::insert(const pair<const K, E>& thePair)
{
    pairNode<K,E> *p = firstNode,
                  *tp = NULL;

    while (p != NULL && p->element.first < thePair.first)
    {
        tp = p;
        p = p->next;
    }

    if(p != NULL && p->element.first == thePair.first)
    {
        p->element.second = thePair.second;
        return;
    }

    pairNode<K,E> *newNode = new pairNode<K,E>(thePair,p);

    if(tp == NULL)
        firstNode = newNode;
    else
        tp->next = newNode;

    dSize++;
    return;
}

template<class K,class E>
void sortedChain<K,E>::erase(const K& theKey)
{
    pairNode<K,E> *p = firstNode,
                  *tp = NULL;

    while(p != NULL && p->element.first < theKey)
    {
        tp = p;
        p = p->next;
    }

    if(p != NULL && p->element.first == theKey)
    {
        if(tp == NULL)
            firstNode = p->next;
        else
            tp->next = p->next;

        delete p;
        dSize--;
    }
}

template<class K,class E>
void sortedChain<K,E>::output(ostream &out) const
{
    for(pairNode<K,E>* currentNode = firstNode;
                       currentNode != NULL;
                       currentNode = currentNode->next)
        out <<currentNode->element.first<<" "
           <<currentNode->element.second<<" ";
}


template<class K,class E>
ostream& operator<<(ostream& out,const sortedChain<K,E>& x)
{
    x.output(out);
    return out;
}

#endif // SORTEDCHAIN_H