学步园

1、使用分离链接法避免collision

参考代码：

#include<iostream>
#include<string>
#include<vector>
using namespace std;

class node
{
public:
	string word;
	int count;
	node * next;
};


node * hashTable[700]={};
void init()
{
	int i;
	for(i=0;i<700;i++)
	{
		hashTable[i] = new node;
		hashTable[i]->next=NULL;
	}
}

void insert(string s)
{
	const char *t =s.c_str();
	int i=0;
	int num=0;
	while(i<5 && (*t)!='\0')
	{
		num+=*t;
		t++;
		i++;
	}
	
	node *head = hashTable[num];
	while(head->next!=NULL)
	{
		if(head->next->word == s)
		{
			head->next->count++;
			return ;
		}
		else
			head=head->next;
	}

	if(head->next == NULL)
	{
		node *tail = new node;
		tail->count=1;
		tail->word=s;
		tail->next=NULL;
		head->next=tail;
	}
	return ;
}

int find(string s)
{
	const char *t =s.c_str();
	int i=0;
	int num=0;
	while(i<5 && (*t)!='\0')
	{
		num+=*t;
		t++;
		i++;
	}
	
	node *head = hashTable[num];
	while(head->next!=NULL)
	{
		if(head->next->word == s)
		{
			return head->next->count;
		}
		else
			head=head->next;
	}
	if(head->next ==NULL)
		return 0;
}
		
int main()
{
	init();
	int i;
	for(i=0;i<10;i++)
	{
		string w;
		cin>>w;
		insert(w);
	}
	string w("hello");
	cout<<find(w);
	return 0;
}

采用开放定址法-》线性探测：

#include<iostream>
#include<string>
#include<vector>
using namespace std;

class node
{
public:
	string word;
	int count;
};


node  hashTable[700];
void init()
{
	int i;
	for(i=0;i<700;i++)
	{
		hashTable[i].word = string("1");
		hashTable[i].count = 0;
		
	}
}

void insert(string s)
{
	const char *t =s.c_str();
	int i=0;
	int num=0;
	while(i<5 && (*t)!='\0')
	{
		num+=*t;
		t++;
		i++;
	}
	
	while(hashTable[num].word !=string("1"))
	{
		if(hashTable[num].word == s)
		{
			hashTable[num].count++;
			return;
		}
		else 
			num++;
	}

	hashTable[num].word=s;
	hashTable[num].count++;
	return ;
}

int find(string s)
{
	const char *t =s.c_str();
	int i=0;
	int num=0;
	while(i<5 && (*t)!='\0')
	{
		num+=*t;
		t++;
		i++;
	}
	
	while(hashTable[num].word !=string("1"))
	{
		if(hashTable[num].word == s)
		{
			return hashTable[num].count;
		}
		else 
			num++;
	}
	return 0;
}
		
int main()
{
	init();
	int i;
	for(i=0;i<10;i++)
	{
		string w;
		cin>>w;
		insert(w);
	}
	string w("hello");
	cout<<find(w);
	return 0;
}