前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >字典 原

字典 原

作者头像
青木
发布2018-10-09 15:59:18
4360
发布2018-10-09 15:59:18
举报
文章被收录于专栏:我是业余自学C/C++的

在这之前,先说一个概念:字典

字典(dictionary)是由一些形如(key,value)的数对所组成的集合,其中key是关键字,value是与关键字key对应的值(另一种说法是,value是值,这个值所对应的关键字就是key)。任意两个数对,其关键字都不等。有关字典的一些基本操作如下:

  • 确定字典是否为空
  • 确定字典有多少数对
  • 寻找一个指定了关键字的数对
  • 插入一个数对
  • 删除一个指定了关键字的数对

一个字典是数对的集合,每个数对都由一个词和它的值组成。一个词的值包括词的意思、发音、词源等。

比如字典中的单词date,在字典中的内容就是date,the point if time at which a transation or event takes place,其中,date就是关键字。

一个多重字典和上述的字典类似,不同的是,多重字典中,两个或多个数对可以具有相同的关键字。

下面是字典的具体实现:

代码语言:javascript
复制
#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;
}
代码语言:javascript
复制
/*
 * 数值对节点的定义
 * 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
代码语言:javascript
复制
/*
 * 字典的抽象类,定义了字典操作需要的基本函数
 * 其中,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
代码语言:javascript
复制
/*
 *
*/
#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

(adsbygoogle = window.adsbygoogle || []).push({}); function googleAdJSAtOnload() { var element = document.createElement("script"); element.src = "//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"; element.async = true; document.body.appendChild(element); } if (window.addEventListener) { window.addEventListener("load", googleAdJSAtOnload, false); } else if (window.attachEvent) { window.attachEvent("onload", googleAdJSAtOnload); } else { window.onload = googleAdJSAtOnload; }

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档