C++哈希表头文件

#ifndef _HASHTABLE_H_
#define _HASHTABLE_H_
#include <iostream>
#include <cstdlib>
using namespace std;

typedef
enum {
    Empty, Active, Deleted
}kindofitem;

typedef struct
{
    int key;
}datatype;

typedef struct{
    datatype data;
    kindofitem info;
}hashitem;

typedef struct{
    hashitem* arr;
    int table_size;
    int current_size;
}hashtable;

int initiate(hashtable* hash, int size);//初始化哈希表
int find(hashtable* hash, datatype x);//查找x元素对应的关键字
int insert(hashtable* hash, datatype x);//像哈希表中插入数组元素x,及设置它对应的关键字
int deleted(hashtable* hash, datatype x);//从哈希表中删除x数据元素
void destroy(hashtable* hash);//撤销函数
/*
int main()
{

system("pause");
return 0;
}
*/
int initiate(hashtable* hash, int size)
{
    hash->arr = (hashitem*)malloc(sizeof(hashitem)*size);//初始化,该数组
    hash->table_size = size;
    if (hash->arr == NULL)
    {
        cout << "初始化失败" << endl;
        return 0;
    }
    else
    {
        hash->current_size = 0;
        return 1;
    }
}

int find(hashtable* hash, datatype x)//查找x元素对应的关键字
{
    int i = x.key%hash->table_size;
    int j = i;
    while (hash->arr[j].info == Active&&hash->arr[j].data.key != x.key)
    {
        j = (j + 1)&hash->table_size;//用哈希冲突方法继续查找
        if (j == i)
        {
            cout << "遍历此哈希表,没有找到" << endl;
            return -hash->table_size;
        }
    }
    if (hash->arr[j].info == Active)
    {
        return j;
    }
    else{
        return -j;
    }
}

int insert(hashtable* hash, datatype x)
{
    int i = find(hash, x);
    if (i > 0)
    {
        cout << "该数据元素已经存在了!" << endl;
        return 0;
    }

    else if (i != -hash->table_size)
    {
        hash->arr[-i].data = x;
        hash->arr[-i].info = Active;
        hash->current_size++;
        return 1;
    }
    else{
        return 0;
    }
}

int deleted(hashtable* hash, datatype x)
{
    int i = find(hash, x);
    if (i > 0)
    {
        hash->arr[i].info = Deleted;
        hash->current_size--;
        return 1;
    }
    else{
        cout << "没有这个元素,无法删除!" << endl;
        return 0;
    }
}

void destroy(hashtable* hash)
{
    delete[]hash->arr;
}
#endif
相关文章
相关标签/搜索