数据结构— —哈希表顺序实现

哈希表的初始化

bool initHash(Hash& hash, int size)
{
	//int n = HashFound(hash, key);
	hash.size = size;
	hash.list = new Sqlist[size];
 
	for (int i = 0; i < hash.size; i++)
	{
		hash.list[i].data = new Data[30];
		if (hash.list[i].data == NULL)
		{
			return false;
		}
		hash.list[i].length = 0;
	}
 
	return true;
}

哈希表的插入

bool insert(Hash& hash, int key, int value)
{
	if (found(hash, key))
	{
		return false;
	}
	else
	{
		Data D;
		D.data1 = value;
		D.key = key;
 
		int n = HashFound(hash, key);
		hash.list[n].data[hash.list[n].length] = D;
		hash.list[n].length++;
		return true;
	}
	
}

哈希表的查询

bool found(Hash& hash, int key)
{
	int n = HashFound(hash, key);
 
	for (int i = 0; i < hash.list[n].length; i++)
	{
		if (hash.list[n].data[i].key == key)
		{
			return true;
		}
	}
 
	return false;
}

哈希表的删除

bool Delete(Hash& hash, int key)
{
	int n = HashFound(hash, key);
	int pos = -1;
 
	for (int i = 0; i < hash.list[n].length; i++)
	{
		if (hash.list[n].data[i].key == key)
		{
			pos = i;
		}
	}
 
	if (pos != -1)
	{
		for (int j = pos; j < hash.list[n].length - 1; j++)
		{
			hash.list[n].data[j] = hash.list[n].data[j + 1];
		}
		hash.list[n].length--;
	}
 
	return true;
	
}

哈希表的桶查找

int HashFound(Hash& hash, int key)
{
	int n = key % hash.size;
	return n;
}

哈希表的销毁

bool Destory(Hash& hash)
{
	for (int i = 0; i < hash.size; i++)
	{
		delete (hash.list[i].data);
	}
 
	delete (hash.list);
	return true;
}

哈希表的代码实现

#include 
#include 
 
using namespace std;
 
typedef struct _Data
{
	int data1;
	int key;
}Data;
 
typedef struct _Sqlist
{
	Data* data;
	int length;
}Sqlist;
 
typedef struct _Hash
{
	int size;
	Sqlist* list;
}Hash;
 
bool initHash(Hash& hash, int size);
bool insert(Hash& hash, int key, int value);
int HashFound(Hash& hash, int key);
bool Delete(Hash& hash, int key);
bool Destory(Hash& hash);
bool found(Hash& hash, int key);
void Print(Hash& hash);
 
bool Destory(Hash& hash)
{
	for (int i = 0; i < hash.size; i++)
	{
		delete (hash.list[i].data);
	}
 
	delete (hash.list);
	return true;
}
 
bool Delete(Hash& hash, int key)
{
	int n = HashFound(hash, key);
	int pos = -1;
 
	for (int i = 0; i < hash.list[n].length; i++)
	{
		if (hash.list[n].data[i].key == key)
		{
			pos = i;
		}
	}
 
	if (pos != -1)
	{
		for (int j = pos; j < hash.list[n].length - 1; j++)
		{
			hash.list[n].data[j] = hash.list[n].data[j + 1];
		}
		hash.list[n].length--;
	}
 
	return true;
	
}
 
int HashFound(Hash& hash, int key)
{
	int n = key % hash.size;
	return n;
}
 
bool insert(Hash& hash, int key, int value)
{
	if (found(hash, key))
	{
		return false;
	}
	else
	{
		Data D;
		D.data1 = value;
		D.key = key;
 
		int n = HashFound(hash, key);
		hash.list[n].data[hash.list[n].length] = D;
		hash.list[n].length++;
		return true;
	}	
}
 
bool found(Hash& hash, int key)
{
	int n = HashFound(hash, key);
 
	for (int i = 0; i < hash.list[n].length; i++)
	{
		if (hash.list[n].data[i].key == key)
		{
			return true;
		}
	}
 
	return false;
}
 
bool initHash(Hash& hash, int size)
{
	//int n = HashFound(hash, key);
	hash.size = size;
	hash.list = new Sqlist[size];
 
	for (int i = 0; i < hash.size; i++)
	{
		hash.list[i].data = new Data[30];
		if (hash.list[i].data == NULL)
		{
			return false;
		}
		hash.list[i].length = 0;
	}
 
	return true;
}
 
void Print(Hash& hash)
{
	for (int i = 0; i < hash.size; i++)
	{
		for (int j = 0; j < hash.list[i].length; j++)
		{
			cout << "key：" << hash.list[i].data[j].key << " data：" << hash.list[i].data[j].data1 << endl;
		}
	}
}
 
int main(void)
{
	Hash hash;
 
	int size = 5;
	initHash(hash, size);
 
	insert(hash, 1, 11);
	insert(hash, 2, 12);
	insert(hash, 3, 13);
	insert(hash, 4, 14);
	Print(hash);
 
	Delete(hash, 2);
	Print(hash);
 
	Destory(hash);
 
	system("pasue");
	return 0;
}