学步园

#include <iostream>
#include <cmath>
#include <cstdlib>
#include <time.h>
#include <windows.h>
#define slot_size 20000		//散列槽的大小
#define arr_size 100000		//动态关键字集合
#define min_size 0			//动态关键字集合的最小值
#define max_size 999 
#define total_size 999999	//动态关键字集合的最大值
using namespace std;

struct node
{
	long key;
	node* next;
};
long* arr_set;
node link_hash[slot_size];
long suc_count=0;
long unsuc_count=0;


/*
* 除法散列函数
*/
long hash_function(long key)
{
	return key%slot_size;
}

/*
* 产生不重复的自定义范围的随机数
*/
long* ran_arr(long size, long min=0, long max=999)
{
	if(max<=min)
		return NULL;
	long* arr;
	long up_th=0;
	long down_th=0;
	arr=new long[size];
	srand((unsigned)time(NULL));
	for(long i=0; i<size; i++)
	{
		long check=1;
		while(check)
		{
			up_th=rand()*(max-min)/32767+min;
			down_th=rand()*(max-min)/32767+min;
			arr[i]=up_th*(max+1)+down_th;
			long j=0;
			while(j<i)
			{
				if(arr[i]==arr[j])
				{
					j=0;
					break;
				}
				j++;
			}
			if(j==i)
				check=0;
		}
	}
	return arr;
}

/*
* 打印数组函数
*/
void print_arr(long* set,long size)
{
	for(long i=0;i<size;i++)
	{
		cout<<set[i]<<endl;
	}
}

/*
* 链接法插入操作，在散列表指向的链表头前添加一个元素(节点)
*/
void hash_insert(long k)
{
	long temp_index=hash_function(k);
	node* new_node=new node;
	new_node->key=k;
	new_node->next=link_hash[temp_index].next;
	link_hash[temp_index].next=new_node;
}

/*
* 查找函数
*/
bool hash_find(long k)
{
	long temp_index=hash_function(k);
	node* temp_node=new node;
	if(link_hash[temp_index].next==NULL)
		return false;
	else
	{
		temp_node=link_hash[temp_index].next;
		while(temp_node->key!=k)
		{
			if(temp_node->next!=NULL)
				temp_node=temp_node->next;
			else
				return false;
		}
	}
	return true;
}

/*
* 删除函数
*/
bool hash_delete(long k)
{
	long temp_index=hash_function(k);
	if(link_hash[temp_index].next==NULL)
		return false;
	else
	{
		node* temp_node=new node;
		temp_node=link_hash[temp_index].next;
		node* pre_node=new node;
		pre_node=&link_hash[temp_index];
		while(temp_node->key!=k)
		{
			if(temp_node->next!=NULL)
			{
				pre_node=temp_node;
				temp_node=temp_node->next;
			}
			else return false;
		}
		pre_node->next=temp_node->next;
	}
	return true;
}

/*
* 打印散列表的函数，可以设置打印的开始索引到结束索引
*/
void print_hash(long start,long end)
{
	node *temp;
	long count=0;
	for(long j=start;j<end;j++)
	{
		cout<<j<<"[--]";
		if(link_hash[j].next==NULL)
		{
			cout<<endl;
		}
		else
		{
			temp=&link_hash[j];
			while(temp->next!=NULL)
			{
				cout<<"-->"<<temp->next->key;
				temp=temp->next;
				count++;
			}
			cout<<endl;
		}
	}
	cout<<endl;
	return;
}

/*
* 主函数
*/
int main(int argc, char* argv[])
{
	
	
	//cout<<"please input the size of the key that you want to store:";
	//cin>>arr_size;

	arr_set=ran_arr(arr_size,min_size,max_size);//to generate arr_size from 1 to 1000 random number
	//print_arr(arr_set,arr_size);

	//初始化散列表的槽
	
	for(long n=0;n<slot_size;n++)
	{
		link_hash[n].next=NULL;
		link_hash[n].key=-1;
	}
	cout<<"befor the insertion:"<<endl<<endl;
	print_hash(220,232);
	

	//插入操作
	DWORD insert_start = GetTickCount(); 
	for(long m=0; m<arr_size;m++)
	{
		hash_insert(arr_set[m]);
	}
	DWORD insert_time=GetTickCount() - insert_start;
	cout<<"the size of n is: "<<arr_size<<endl;
	cout<<"the size of m is: "<<slot_size<<endl;
	cout<<"the value of a=n/m is: "<<float(arr_size)/float(slot_size)<<endl;
	cout<<"the total insert running time is: "<<insert_time<<" milliseconds"<<endl;
	cout<<"the average insert time is: "<<float(insert_time)/float(arr_size)<<" milliseconds"<<endl<<endl;
	cout<<"***********************************************************"<<endl<<endl;
	cout<<"after the insertion:"<<endl<<endl;
	print_hash(220,232);
	
	//查找操作
	DWORD find_start=GetTickCount();
	for(long n=0;n<arr_size;n++)
	{
		if(hash_find(arr_set[n]))
		{
			suc_count++;
		}
		else
		{
			unsuc_count++;
		}

	}
	DWORD find_time=GetTickCount()-find_start;
	cout<<"the total finding running time is: "<<find_time<<" milliseconds"<<endl;
	cout<<"the average finding runnig time is: " <<float(find_time)/float(arr_size)<<" milliseconds"<<endl;
	cout<<"the success finding count is :"<<suc_count<<endl;
	cout<<"the unsuccess finding count is :"<<unsuc_count<<endl<<endl;
	cout<<"***********************************************************"<<endl<<endl;
	suc_count=unsuc_count=0;//计数清零；
	//删除操作
	DWORD delete_start=GetTickCount();
	for(long j=0;j<arr_size;j++)
	{
		if(hash_delete(arr_set[j]))
		{
			suc_count++;
		}
		else
		{
			unsuc_count++;
		}
	}
	DWORD delete_time=GetTickCount()-delete_start;
	cout<<"the total deleting running time is: "<<delete_time<<" milliseconds"<<endl;
	cout<<"the average deleting runnig time is: " <<float(delete_time)/float(arr_size)<<" milliseconds"<<endl;
	cout<<"the success deleting count is :"<<suc_count<<endl;
	cout<<"the unsuccess deleting count is :"<<unsuc_count<<endl<<endl;
	suc_count=unsuc_count=0;//计数清零；
	cout<<"***********************************************************"<<endl<<endl;
	cout<<"after the deletion:"<<endl<<endl;
	print_hash(220,232);
	
	
	int a;
	cin>>a;

	return 0;
}