原 数据结构-散列表(Hash Table

No BB, just show you the code.

/**hash_chaining.h
 * The Chaining Hash Table Data Structure in C++
 * Time Cost : Search / Insert / Delete : Θ(1)
 * Thanks to Introduction to Algorithms (CLRS) Chapter 11
 * Thanks to Stanford MOOC of "Algorithms : Part I"
 * Author: Zheng Chen / Arclabs001
 * Email : chenzheng17@yahoo.com
 * Copyright 2015 Xi'an University of Posts & Telecommunications. All rights reserved.
 */
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Node     //The hash chaining node
{
    int key;
    string name;
    Node * next;
};

class hash_table
{
private:
    vector<Node *> _map;
    int _hash(int _key) {return (_key*73)%101;}  //The hash function

public:
    hash_table() {_map.reserve(105); for(int i=0;i<=100;i++) _map[i]=nullptr;}  //Constructor

    void hash_insert(int _key, string _name);
    void hash_insert(Node* New_Node);

    void hash_delete(int _key);
    void hash_delete(int _key, string _name);
    void hash_delete(Node* node);

    Node* hash_search(int _key);
    Node* hash_search(int _key, string _name);
};
/**
 * Insert a node into the hash table
 * @param _key  : The key value
 * @param _name : One of the satelitte data 
 */
void hash_table::hash_insert(int _key, string _name)
{
    Node * New_Node = new Node;
    New_Node->key = _key;
    New_Node->name = _name;
    hash_insert(New_Node);
}
/**
 * Insert a node into the hash Table
 * @param New_Node : The node to be inserted
 */
void hash_table::hash_insert(Node* New_Node)
{
    New_Node->next = _map[_hash(New_Node->key)];
    _map[_hash(New_Node->key)] = New_Node;
}
/**
 * Delete all of the node which value equals to key
 * @param _key : The key value
 */
void hash_table::hash_delete(int _key)
{
    if(_map[_hash(_key)] == nullptr)
       return;

    int num = _hash(_key);
    Node* p = _map[num];
    while(_map[num])
    {
        p = _map[num];
        _map[num] = p->next;
        delete p;
    }
}
/**
 * Delete a node which valued _key and name = _name
 * @param _key  : The key value
 * @param _name : One of the satelitte data 
 */
void hash_table::hash_delete(int _key, string _name)
{
    if(_map[_hash(_key)] == nullptr)
        return;

    int num = _hash(_key);
    Node * p = _map[num];
    Node * q = _map[num];
    while(p!=nullptr)
    {
        if(p->name == _name)
            break;
        q = p;
        p = p->next;
    }

    if(q == _map[num] && p == q)
        _map[num] = p->next;
    else
        q->next = p->next;
}
/**
 * Delete a node from the hash table which equals to node
 * @param node : The node to be deleted
 */
void hash_table::hash_delete(Node* node)
{
    hash_delete(node->key, node->name);
}
/**
 * Search the node which valued key
 * @param  _key : The key value
 * @return      : a pionter to the first node
 */
Node* hash_table::hash_search(int _key)
{
    return _map[_hash(_key)];
}
/**
 * Find a node which valued key and its name equals to _name
 * @param  _key  : The key value
 * @param  _name : One of the satelitte data 
 * @return       : A pionter to the target node
 */
Node* hash_table::hash_search(int _key, string _name)
{
    if(_map[_hash(_key)] == nullptr)
    {
        return nullptr;
    }

    Node* p = _map[_hash(_key)];
    while(p)
    {
        if(p->name == _name)
            return p;
        p = p->next;
    }
    return nullptr;
}
#include "hash_chaining.h"

int main()
{
    hash_table _hash_table;
    Node *_node = _hash_table.hash_search(3);   //此时表为空,测试search
    if(_node == nullptr)
        cout<<"Now _node is a nullptr!"<<endl;

    string name = "asdfg";

    for(int i=0; i<5; i++)  //插入节点
    {
        name[i]++;
        _hash_table.hash_insert(i,name);
    }

    _node = _hash_table.hash_search(3);     //测试search(int _key)接口
    cout<<_node->name<<endl;

    _hash_table.hash_delete(3,"btegg");     //测试delete(int _key, string _name)接口
    _node = _hash_table.hash_search(3);
    if(_node == nullptr)
        cout<<"Now _node is a nullptr!"<<endl;
    else
        cout<<_node->name<<endl;

    _hash_table.hash_insert(2,"b");     //测试insert(int _key, string _name)接口

    _node = _hash_table.hash_search(2,"btefg");     //测试search(int _key, string _name)接口
        cout<<_node->name<<endl;

    _node = _hash_table.hash_search(2,"b"); 
        cout<<_node->name<<endl;

    _hash_table.hash_delete(2,"btefg");
    _node = _hash_table.hash_search(2);
    if(_node == nullptr)
        cout<<"Now _node is a nullptr!"<<endl;
    else
        cout<<_node->name<<endl;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

算法模板——二分图匹配

实现功能为二分图匹配 原理:匈牙利算法,核心思想——匹配上了就配,没直接匹配上也要通过前面的腾出位置让这个匹配上(详见:趣写算法系列之——匈牙利算法) 本程序以...

3674
来自专栏龙首琴剑庐

Java基准测试利器OpenJDK-JMH

5779
来自专栏耕耘实录

Linux三剑客之grep

版权声明:本文为耕耘实录原创文章,各大自媒体平台同步更新。欢迎转载,转载请注明出处,谢谢

1825
来自专栏互联网高可用架构

伪共享和缓存行

1622
来自专栏HansBug's Lab

1293: [SCOI2009]生日礼物

1293: [SCOI2009]生日礼物 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1096  Solv...

2777
来自专栏鸿的学习笔记

records包源码解析

核心类有三个 Record, RecordCollection, Database。在做源码分析时,先从入口类Database开始:

882
来自专栏salesforce零基础学习

salesforce 零基础学习(六十八)http callout test class写法

此篇可以参考: https://developer.salesforce.com/docs/atlas.en-us.apexcode.meta/apexcode...

3097
来自专栏菩提树下的杨过

VisualTreeHelper

Silverlight中只有可视化树,没有WPF中的逻辑树,这一点可从SL的sdk文档中得到印证: 可视化树概念也存在于 WPF 中,它与 Silverligh...

2357
来自专栏calmound

D3DXCreateTextureFromFile

HRESULT D3DXCreateTextureFromFile( __in LPDIRECT3DDEVICE9 pDevice, _...

3145
来自专栏三丰SanFeng

无锁编程(三) - 忙等待

概念 忙等待可以认为是一种特殊的忙等待 忙等待分类 Peterson算法 xchg解法 TSL解法 自旋锁 Peterson算法 Peterson算法是一个实现...

2856

扫码关注云+社区

领取腾讯云代金券