hashtable.h

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

#include "Onelink.h"                   //单链表类

class HashTable                        //拉链法的哈希表类
{
  public:
    OnelinkNode *table;                //指向哈希表数组的指针
    int size;                          //哈希表的数组容量
    
    HashTable(int n);                  //构造函数，分配哈希表的存储单元
    ~HashTable();                      //析构函数

    int hash(int k);                   //哈希函数
    void insert(int k);                //哈希表中插入数据元素
    OnelinkNode* hashsearch(int k);    //哈希查找
    friend ostream& operator<<(ostream& out,HashTable &h1);
                                       //输出哈希表及全部哈希链表
    bool remove(int k);                //删除数据元素k
};

HashTable::HashTable(int n)            //构造函数，分配哈希表的存储单元
{
    size=n;
    table=new OnelinkNode[size];       //结点的data初值为0,next初值为NULL
}

int HashTable::hash(int k)             //哈希函数
{
    return k % size;
}

void HashTable::insert(int k)          //哈希表中插入k值
{
    OnelinkNode *q;
    int i=hash(k);
    if(table[i].data==0)               //该位置上没有数据元素
        table[i].data=k;               //k值存入哈希基表
    else
    {                                  //产生冲突时
        q=new OnelinkNode(k);          //k值结点插入哈希链表
        q->next=table[i].next;         //q结点作为哈希链表的首结点
        table[i].next=q;               //哈希链表的头指针存入哈希基表
    }
}

ostream& operator<<(ostream& out,HashTable &ht1) 
{                                      //输出哈希表及全部哈希链表
    for(int i=0;i<ht1.size;i++)
    {
        cout<<"table["<<i<<"]= "<<ht1.table[i].data;
        Onelink link1;                 //创建空单链表
        link1.head=ht1.table[i].next;  //指向哈希链表
        link1.output();                //输出单链表
        link1.head=NULL;               //设置单链表为空
    }
    return out;
}

OnelinkNode* HashTable::hashsearch(int k)   //哈希查找
{
    int i=hash(k);
    if(table[i].data==0)
        return NULL;
    else
        if(k==table[i].data)           //k在哈希基表中
            return &table[i];          //返回结点地址
        else                           //k在哈希链表中
        {
            Onelink link1;
            link1.head=table[i].next;
            OnelinkNode *p=link1.search(k);    //哈希链表中查找k
            link1.head=NULL;           //设置单链表为空
            return p;                  //返回在哈希链表中查找k的结果
        }
} 

HashTable::~HashTable()                //析构函数
{
    cout<<"调用HashTable类的析构函数\n";
    for(int i=0;i<size;i++)
    {
        if(table[i].next!=NULL)
        {
            Onelink link1;             //创建空单链表
            link1.head=table[i].next;  //指向哈希链表
            cout<<"table["<<i<<"]= "<<table[i].data;
            table[i].next=NULL;        //设置哈希链表为空
            cout<<"  调用Onelink类的析构函数"<<endl;
        }                              //调用Onelink类的析构函数释放link1
    }
    delete []table;
}