第七章学习小结

时间:2022-04-05 16:31:57

第七章主要学习了很多种查找方式,从最简单的线性表查找到树表的查找到散列表查找,不同的查找方式有不同的优点,下面根据练习来实际应用这些知识。


 

这个问题的任务很简单:将一个不同的正整数序列插入哈希表,并输出输入数字的位置。散列函数定义为h(key)=key%tsize,其中tsize是散列表的最大大小。二次探测(只有正增量)用于解决碰撞。
请注意,表的大小最好是素数。如果用户给定的最大大小不是质数,则必须将表大小重新定义为大于用户给定大小的最小质数。
输入规格:
每个输入文件包含一个测试用例。对于每种情况,第一行包含两个正数:msize(≤10^4)和n(≤msize),分别是用户定义的表大小和输入数。然后在下一行中给出n个不同的正整数。一行中的所有数字都用空格隔开。
输出规格:
对于每个测试用例,在一行中打印输入数字的相应位置(索引从0开始)。一行中的所有数字都用空格隔开,并且行尾不能有多余的空格。如果无法插入数字,请改为打印“-”。
样本输入:
4 4
10 6 4 4
样品输出:
0 1 4


这道题主要考察的是哈希表的构建,应用以及对于冲突的处理方法

#include <iostream>
#include <math.h>
using namespace std;

bool if_prime(int a) //判断一个数是不是素数 
{
	int i;	//定义参数 
	
	if(a==1||a==0)return false;	//如果a为1或0,不是素数返回flase 
	
	for(i=2;i<=sqrt(a);i++)
	{
		if(a%i==0)return false;	//a不为素数,返回flase 
	}
	
	return true;	//a为素数,返回true 
}

int get_prime(int a)	//得到一个大于等于a的最小素数 
{
	while(!if_prime(a))	//当a不为素数 
	{
		a++;	//a值+1 
	}
	
	return a;	//返回a 
}

int main()
{
	int m,n;	//定义参数 
	cin>>m>>n;	//输入表长与输入个数 
	
	m=get_prime(m);	//表长定义为大于等于m的最小素数 
	
	int visited[10007]={0};	//定义访问数组并全置0 
	int input[n];	//定义输入数组 
	
	int i,j,k;	//定义参数 
	
	for(i=0;i<n;i++)
	{
		cin>>input[i];	//输入正整数序列 
	}
		
	for(i=0;i<n;i++)
	{
		j=input[i]%m;	//得到应插入的位置值 
		
		if(visited[j]==0)	//若该位置未被插入 
		{
			cout<<j;	//输出该位置值 
			
			if(i<n-1)cout<<" ";	//判断是否输出空格 
			
			visited[j]=1;	//表示该位置已被插入 
		}
		else	//若该位置已被插入 
		{
			for(k=1;k<m;k++)
			{
				j=(k*k+input[i])%m;	//采用二次方探查法处理冲突 
				
				if(visited[j]==0)	//若处理后的位置未被插入 
				{
					cout<<j;	//输出位置值 
					
					if(i<n-1)cout<<" ";	//判断是否输出空格 
					
					visited[j]=1;	//表示该位置已被插入 
					
					break;	//跳出循环 
				}
			}
			
			if(k==m)	//若k=m,则无法插入 
			{
				cout<<"-";	//输出'-' 
				
				if(i<n-1)cout<<" ";	//判断是否输出空格 
			}
		}
	}
	
	
	return 0;
} 
 

这道题中要注意到表的大小并不一定是输入的数,所以要先经过一定的处理得到大于等于msize的最小素数,其次就是对于冲突的处理方法,二次方探测(正增量)这种方法就是把position(当前已被插入的位置)平方之后加上本身的数值,再去做一次求余,直到超出哈希表。


再看第二道题

实现QQ新帐户申请和老帐户登陆的简化版功能。最大挑战是:据说现在的QQ号码已经有10位数了。

输入格式:

输入首先给出一个正整数N(105​​),随后给出N行指令。每行指令的格式为:“命令符(空格)QQ号码(空格)密码”。其中命令符为“N”(代表New)时表示要新申请一个QQ号,后面是新帐户的号码和密码;命令符为“L”(代表Login)时表示是老帐户登陆,后面是登陆信息。QQ号码为一个不超过10位、但大于1000(据说QQ老总的号码是1001)的整数。密码为不小于6位、不超过16位、且不包含空格的字符串。

输出格式:

针对每条指令,给出相应的信息:

1)若新申请帐户成功,则输出“New: OK”;
2)若新申请的号码已经存在,则输出“ERROR: Exist”;
3)若老帐户登陆成功,则输出“Login: OK”;
4)若老帐户QQ号码不存在,则输出“ERROR: Not Exist”;
5)若老帐户密码错误,则输出“ERROR: Wrong PW”。

输入样例:

5
L 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
N 1234567890 myQQ@qq.com
L 1234567890 myQQ@qq
L 1234567890 myQQ@qq.com

输出样例:

ERROR: Not Exist
New: OK
ERROR: Exist
ERROR: Wrong PW
Login: OK

相比于第一道题,第二道题的思路就清晰了很多,主要根据不同的输入情况,分类处理即可。
#include <iostream>
#include <map>
using namespace std;

typedef struct
{
	string name;
	string secret;
}QQ;	//定义一个结构体包含账号与密码 

QQ a[100000];	//为结构体开辟最大空间 

int main()
{
	int n;	//定义参数 
	cin>>n;	//输入指令个数 
	
	map<string,string> search;	//创建一个map容器 方便账号与密码的匹配 
	
	int i,j;	//定义参数 
	
	char demand;	//定义字符参数判断'L'与'N' 
	
	for(i=0;i<n;i++)
	{
		cin>>demand;	//输入指令类型 
		
		if(demand=='N')	//若为新账号 
		{
			cin>>a[i].name>>a[i].secret;	//输入账号密码 
			
			if( search.find(a[i].name)==search.end() )	//若该账号未存在 
			{
				search[a[i].name]=a[i].secret;	//往map容器中插入账号与对应的密码 
				
				cout<<"New: OK"<<endl;	//输出语句 
			}
			else	//若该账号已存在 
			{
				cout<<"ERROR: Exist"<<endl;	//输出语句 
			}
		}
		
		else if(demand=='L')	//若为老账号 
		{
			cin>>a[i].name>>a[i].secret;	//输入账号密码 
			
			if( search.find(a[i].name)==search.end() )cout<<"ERROR: Not Exist"<<endl;	//若该账号未存在,输出语句 
			
			else	//若该账号存在 
			{
				if(search[a[i].name]==a[i].secret)cout<<"Login: OK"<<endl;	//输入密码正确,输出语句 
				else cout<<"ERROR: Wrong PW"<<endl;	//输入密码错误,输出语句 
			}
		}
	}
	
	return 0;
} 

在做这道题的时候本人一开始采用的是for循环去查找账号是否存在,但由于测试点和数据较大的问题会运行超时,最后采用的是map函数中的查找方法,这种方法能够简便地查找账号是否存在以及密码是否匹配。

 

以上是第七章学习之后的总结。