数据结构（四）字典

• 字典--c++实现
• • 字典原型（链表描述）
  • Dictionary类的实现

在Dictionary.h文件中定义了节点，声明了字典类的原型

template
struct node {
    K key;
    E value;
    node *next;
};

template
class Dictionary {
private:
    node *head;
    int size;
public:
    Dictionary();

    ~Dictionary();

    bool isEmpty() const;

    int getSize() const;

    node *find(const K&) const;

    void del(const K&);

    void insert(const node&);
};

#include "Dictionary.h"

template
Dictionary::Dictionary() {
    head = nullptr;
    size = 0;
}

template
Dictionary::~Dictionary() {
    node *pd = head;
    while (pd->next != nullptr){
        node *p = pd;
        pd = pd->next;
        delete p;
    }
    delete pd;
}

template
bool Dictionary::isEmpty() const {             //判断字典是否为空
    return size == 0;
}

template
int Dictionary::getSize() const {               //返回字典元素个数
    return size;
}

template
node *Dictionary::find(const K & key) const {   //返回匹配关键字的节点指针
    node* pd = head;                       //如果匹配失败则返回nullptr
    while (pd != nullptr && pd->key != key){
        pd = pd->next;
    }
    if(pd != nullptr && pd->key == key)
    return pd;
    else return nullptr;
}

template
void Dictionary::del(const K & key) {          //删除对应关键字的元素
    node* pd = head;
    while (pd->key != key){
        pd = pd->next;
    }
    pd->key = pd->next->key;
    pd->value = pd->next->value;
    node* p = pd->next;
    pd->next = p->next;
    delete p;
    size -- ;
}

template
void Dictionary::insert(const node< K, E> & nd) { //插入字典元素
    if(head == nullptr){
        head = new node;
        head->key = nd.key;
        head->value = nd.value;
        head->next = nullptr;
    } else{
        node *nod = head;
        while (nod->next != nullptr){
            nod = nod->next;
        }
        nod -> next = new node;
        nod->next->next = nullptr;
        nod->next->key = nd.key;
        nod->next->value = nd.value;
    }
    size++;
}

测试程序如下：

#include 
int main(){
    Dictionary dictionary;
    for (int i = 0; i < 10; i++) {
        node n ;
        n = {i,i, nullptr};
        dictionary.insert(n);
    }
    std::cout << "key = 3 value = " << dictionary.find(3)->value << std::endl;
    std::cout << "size = " << dictionary.getSize() << std::endl;
    dictionary.del(4);
    std::cout << "size = " << dictionary.getSize() << std::endl;
    return 0;
}

测试结果：

key = 3 value = 3
size = 10
size = 9