哈希表设计

1.1 针对某个集体中的人名设计一个哈希表，使得平均查找长度不超过R，完成相应的建立和查表程序. 1.2 人名为汉语拼音形式，最长不超过18个字符(如：庄双双 zhuangshuangshuang). 1.3 假设待填入哈希表的人名有30个，平均查找长度为2。哈希表用除留余数法构造，用伪随机探测在散列法处理冲突。 1.4 在输入人名过程中能自动识别非法输入，并给与非法输入的反馈信息要求重新输入。

#include “hashList.h“

 HashList_T::HashList_T（int numbers）
{
	m_numbers=numbers;
	m_name_ptr=new vector[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	{
		if（s[i]<‘a‘||s[i]>‘z‘）
			return false;
	}

	return true;
}

void HashList_T::show（bool lhs）const
{
	if（lhs）
		cout<<“查找成功“<	else
		cout<<“查找失败“<}

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=0numbers;
	string name;

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

	while（i	{
		if（1）
		{
			string s;
	    	cout<<“输入人名:“<		    cin>>s;
			name=s;
		}

		bool result=isLegal（name）;

		while（!result）
		{
			if（1）
			{
				string s;
		     	cout<<“输入非法输入人名:“<			    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<<“输入查找人名“<	        cin>>s;
			name=s;
		}

	bool result=isLegal（name）;

	while（!result）
	{
		if（1）
		{
			string s;
		    cout<<“输入非法再次输入人名“<		    cin>>s;
			name=s;
			result=isLegal（name）;
		}
	}

	findName（name）;

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

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

	bool result=isExistence（is）;

	show（result）;
	cout<
}

bool HashList_T::isExistence（int istring&s）
{
	if（m_name_ptr[i].empty（））
		return false;

	 vector::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;
}











































	
	

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       6672  2008-08-20 11:21  哈希表源码\Debug\BuildLog.htm

     文件     540632  2008-08-20 11:21  哈希表源码\Debug\hashList.obj

     文件         67  2008-08-20 11:21  哈希表源码\Debug\mt.dep

     文件      33596  2008-08-14 16:34  哈希表源码\Debug\test.obj

     文件     232448  2008-08-20 11:21  哈希表源码\Debug\vc80.idb

     文件     176128  2008-08-20 11:21  哈希表源码\Debug\vc80.pdb

     文件     659456  2008-08-20 11:21  哈希表源码\Debug\哈希表.exe

     文件        146  2008-08-14 16:34  哈希表源码\Debug\哈希表.exe.embed.manifest

     文件        212  2008-08-14 16:34  哈希表源码\Debug\哈希表.exe.embed.manifest.res

     文件        145  2008-08-20 11:21  哈希表源码\Debug\哈希表.exe.intermediate.manifest

     文件    1776000  2008-08-20 11:21  哈希表源码\Debug\哈希表.ilk

     文件    3042304  2008-08-20 11:21  哈希表源码\Debug\哈希表.pdb

     文件       2685  2008-08-20 13:50  哈希表源码\hashList.cpp

     文件        992  2007-07-10 14:18  哈希表源码\hashList.h

     文件        113  2007-07-09 17:10  哈希表源码\test.cpp

     文件         82  2007-07-08 22:21  哈希表源码\哈希表.dep

     文件       4404  2007-07-09 18:20  哈希表源码\哈希表.dsp

     文件        537  2007-07-08 22:21  哈希表源码\哈希表.dsw

     文件       4351  2007-07-09 18:20  哈希表源码\哈希表.mak

     文件      53760  2008-04-02 15:31  哈希表源码\哈希表.opt

     文件       3425  2007-07-12 20:55  哈希表源码\哈希表.plg

     文件        882  2008-08-14 16:33  哈希表源码\哈希表.sln

    ..A..H.     10752  2008-08-20 16:04  哈希表源码\哈希表.suo

     文件       5566  2008-08-14 16:33  哈希表源码\哈希表.vcproj

     文件       1411  2008-08-20 16:04  哈希表源码\哈希表.vcproj.CPLH-BJ.siliang.user

     文件      97792  2007-07-11 16:19  哈希表课程设计报告.doc

     目录          0  2008-08-20 11:21  哈希表源码\Debug

     目录          0  2008-08-20 13:50  哈希表源码

     文件    2149376  2008-08-20 16:04  哈希表源码\哈希表.ncb

----------- ---------  ---------- -----  ----

............此处省略2个文件信息