hashlist.cpp

数据结构课程设计

#include "hashList.h"

 HashList_T::HashList_T(int numbers)
{
	m_numbers=numbers;
	m_name_ptr=new vector<string>[m_numbers];
}

HashList_T::~HashList_T(void)
{
	delete []m_name_ptr;
}

bool HashList_T::isLegal(string&s)
{
	if(s.size()>18)
		return false;

	for(int i=0;i<s.size();i++)
	{
		if(s[i]<'a'||s[i]>'z')
			return false;
	}

	return true;
}

void HashList_T::show(bool lhs)const
{
	if(lhs)
		cout<<"查找成功"<<endl;
	else
		cout<<"查找失败"<<endl;
}

bool HashList_T::isFull(int i)const
{
	if(m_name_ptr[i].size()==2)
		return true;

	else
		return false;
}

int HashList_T::getNumber(string&s)
{
	int i=s.size()%m_numbers;
	
	bool result=isFull(i);

	if(!result)
		return i;
	else
	{
		int j;
		if(m_numbers%2==0)
			j=m_numbers-1;
		else
			j=m_numbers-2;

		i=(i+j)%m_numbers;

		result=isFull(i);

		while(result)
		{
			i=(i+j)%m_numbers;
			result=isFull(i);
		}

		return i;
	}
}


void HashList_T::createHashList(void)
{
	int i=0,numbers;
	string name;

	cout<<"输入要输入的人名总数:"<<endl;
	cin>>numbers;

	while(i<numbers)
	{
		if(1)
		{
			string s;
	    	cout<<"输入人名:"<<endl;
		    cin>>s;
			name=s;
		}

		bool result=isLegal(name);

		while(!result)
		{
			if(1)
			{
				string s;
		     	cout<<"输入非法,输入人名:"<<endl;
			    cin>>s;
				name=s;
			}

			result=isLegal(name);

		}

		int j=getNumber(name);
		m_name_ptr[j].push_back(name);
		i++;
	}
}


void HashList_T::findName(void)
{
	string name;

	int i=1;

	while(i>0)
	{
		if(1)
		{
			string s;
	        cout<<"输入查找人名"<<endl;
	        cin>>s;
			name=s;
		}

	bool result=isLegal(name);

	while(!result)
	{
		if(1)
		{
			string s;
		    cout<<"输入非法,再次输入人名"<<endl;
		    cin>>s;
			name=s;
			result=isLegal(name);
		}
	}

	findName(name);

	cout<<"继续?yes--1.no--0"<<endl;
	cin>>i;
	}
}

void HashList_T::findName(string&s)
{
	int i=s.size()%m_numbers;

	bool result=isExistence(i,s);

	show(result);
	cout<<endl;

}

bool HashList_T::isExistence(int i,string&s)
{
	if(m_name_ptr[i].empty())
		return false;

	 vector<string>::iterator p;

	 int j;
	 if(m_numbers%2==0)
		 j=m_numbers-1;
	 else
		 j=m_numbers-2;


	 while(!m_name_ptr[i].empty())
	 {

	   p=m_name_ptr[i].begin();
	
    	while(p!=m_name_ptr[i].end())
		{
		if(*p==s)
			return true;
		p++;
		}

		i=(i+j)%m_numbers;
	 }

	 return false;
}