【数据结构入门精讲 | 第十五篇】散列表知识点及考研408、企业面试练习（2）

在上一篇文章中我们学习了散列表的相关知识点及进行了选择题、编程题的练习，这篇文章中我们将进行编程题的练习，带领读者以练代学、更好地掌握知识点。

R7-1 QQ帐户的申请与登陆

实现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<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
#include<string.h>
#define KEYLENGTH 16 //问题编号的最大长度
#define MAXTABLESIZE 10000 //散列表的最大大小

typedef char ElementType[KEYLENGTH + 1]; //定义问题编号和密码的类型
typedef struct LNode* PtrToLNode; //链表节点指针类型
typedef PtrToLNode List; //链表指针类型
struct LNode
{
    ElementType QNumber; //问题编号
    ElementType QPassword; //问题密码
    PtrToLNode Next; //指向下一个节点的指针
};
typedef struct HblNode* HashTable; //哈希表指针类型
struct HblNode
{
    int TableSize; //散列表大小
    List Heads; //链表头节点数组
};

//找到比num大的下一个素数
int NextPrime(int num)
{
    int p = (num % 2) ? (num + 2) : (num + 1); //从num+1或num+2开始判断
    int i = 0;
    while (p<MAXTABLESIZE) //不断增加p直到小于等于最大值
    {
        for (i = (int)sqrt(p); i > 2; i--) //从sqrt(p)到2之间枚举因子
            if (p % i == 0)break; //若p有因子，则break
        if (i == 2)break; //如果没有因子，则i一定等于2，跳出循环
        else
            p += 2; //增加2后重新判断
    }
    return p;
}

//哈希函数，将问题编号转换为哈希地址
int Hash(ElementType QNumber, int TableSize)
{
    return atoi(QNumber + 3) % TableSize; //将问题编号的后三位转换成整数并对表长取余
}

//创建哈希表
HashTable BuildHashTable(int TableSize)
{
    HashTable H = (HashTable)malloc(sizeof(struct HblNode)); //分配哈希表结构体内存
    H->TableSize = NextPrime(TableSize); //确定哈希表大小
    H->Heads = (List)malloc(H->TableSize * sizeof(struct LNode)); //分配链表头节点数组内存
    for (int i = 0; i < H->TableSize; i++)
    {
        H->Heads[i].QNumber[0] = '\0'; //初始化问题编号为空字符串
        H->Heads[i].QPassword[0] = '\0'; //初始化问题密码为空字符串
        H->Heads[i].Next = NULL; //初始化指向下一个节点的指针为空
    }
    return H;
}

//在哈希表中查找指定问题编号的节点
PtrToLNode Find(ElementType QNumber, HashTable H)
{
    int i = Hash(QNumber,H->TableSize); //计算哈希地址
    PtrToLNode P = H->Heads[i].Next; //指向链表的第一个节点
    while (P && strcmp(P->QNumber, QNumber)) //依次查找节点，直到找到或遍历完链表
        P = P->Next;
    return P;
}

//向哈希表中插入新的问题编号和密码节点
void Insert(ElementType QNumber,ElementType QPassword,HashTable H)
{
    PtrToLNode P, NewCell;
    P = Find(QNumber, H); //查找问题编号是否已存在
    if (!P) //如果不存在，则添加新节点
    {
        int i = Hash(QNumber, H->TableSize); //计算哈希地址
        NewCell = (PtrToLNode)malloc(sizeof(struct LNode)); //分配新节点内存
        strcpy(NewCell->QNumber, QNumber); //复制问题编号
        strcpy(NewCell->QPassword, QPassword); //复制问题密码
        NewCell->Next = H->Heads[i].Next; //将新节点插入到链表头部
        H->Heads[i].Next = NewCell;
    }
}

//处理登录操作，验证问题编号和密码是否匹配
void Order_L(HashTable H)
{
    ElementType QNumber;
    ElementType QPassword;
    scanf("%s %s", QNumber, QPassword); //读取输入的问题编号和密码
    PtrToLNode P = Find(QNumber, H); //查找问题编号对应的节点
    if (P) //如果找到，则验证密码是否正确
    {
        if (!strcmp(P->QPassword, QPassword))
            printf("Login: OK\n"); //密码正确，输出“Login: OK”
        else
            printf("ERROR: Wrong PW\n"); //密码错误，输出“ERROR: Wrong PW”
    }
    else
        printf("ERROR: Not Exist\n"); //未找到对应的问题编号，输出“ERROR: Not Exist”
}

//处理新增问题操作，判断问题编号是否已存在
void Order_N(HashTable H)
{
    ElementType QNumber;
    ElementType QPassword;
    scanf("%s %s", QNumber, QPassword); //读取输入的问题编号和密码
    PtrToLNode P = Find(QNumber, H); //查找问题编号对应的节点
    if (P) //如果找到，则问题编号已存在，输出“ERROR: Exist”
        printf("ERROR: Exist\n");
    else //如果未找到，则添加新节点并输出“New: OK”
    {
        Insert(QNumber, QPassword, H);
        printf("New: OK\n");
    }
}

//创建哈希表并根据输入的指令进行相应操作
void CreateHashTable()
{
    int N;
    scanf("%d\n", &N); //读取问题数量
    HashTable H = BuildHashTable(N); //构建哈希表
    while (N--)
    {
        char Order[2];
        scanf("%s", Order); //读取指令
        switch (Order[0]) //根据指令进行相应操作
        {
        case 'L':Order_L(H); break;
        case 'N':Order_N(H); break;
        }
    }
}

int main()
{
    CreateHashTable();
    return 0;
}

R7-2 词频统计

请编写程序，对一段英文文本，统计其中所有不同单词的个数，以及词频最大的前10%的单词。

所谓“单词”，是指由不超过80个单词字符组成的连续字符串，但长度超过15的单词将只截取保留前15个单词字符。而合法的“单词字符”为大小写字母、数字和下划线，其它字符均认为是单词分隔符。

输入格式:

输入给出一段非空文本，最后以符号#结尾。输入保证存在至少10个不同的单词。

输出格式:

在第一行中输出文本中所有不同单词的个数。注意“单词”不区分英文大小写，例如“PAT”和“pat”被认为是同一个单词。

随后按照词频递减的顺序，按照词频:单词的格式输出词频最大的前10%的单词。若有并列，则按递增字典序输出。

输入样例：

This is a test.

The word "this" is the word with the highest frequency.

Longlonglonglongword should be cut off, so is considered as the same as longlonglonglonee.  But this_8 is different than this, and this, and this...#
this line should be ignored.

输出样例：（注意：虽然单词the也出现了4次，但因为我们只要输出前10%（即23个单词中的前2个）单词，而按照字母序，the排第3位，所以不输出。）

23
5:this
4:is

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<algorithm>
 
using namespace std;
 
map<string, int> mp;
 
struct Words {//定义了一个word结构体
	string str;
	int count;
};
 
bool cmp(const Words &w1, const Words &w2) {//排序用到的比较函数
	if (w1.count > w2.count) {
		return true;
	}
	if (w1.count == w2.count) {
		return w1.str < w2.str;
	}
	return false;
}
 
int main() {
	string word;
	char c;
	while (true) {
		scanf("%c",&c);//一个一个字母往里输入
		if (c >= 'A'&&c <= 'Z' || c >= 'a'&&c <= 'z' || c >= '0'&&c <= '9' || c == '_') {
			if (c >= 'A'&&c <= 'Z') {
				c = (c - 'A' + 'a');//将大写字母转化为小写字母，统计词频不分大小写
			}
			if (word.length() < 15) {
				word += c;//如果这个单词长度小于15，就把这个字母加到这个单词的末尾
			}
		}
		else if (c == '#' || word.length() > 0) {
			if (!mp[word]) {//如果map里面没有这个单词，就插入这个单词，并把key（单词出现的次数）设为1
				mp[word] = 1;
			}
			else {
				mp[word]++;//如果已经有了，就把频率+1
			}
			word.clear();//把word清空，方便下一个单词输入
			if (c == '#') {
				break;//如果输入等于#，则输入结束
			}
		}
	}
	map<string, int>::iterator iter;//迭代器
	vector<Words> vec;//定义一个Words类型的vector，方便排序
	Words w;
	for (iter = mp.begin(); iter != mp.end(); iter++) {//通过迭代器遍历map
		//cout << iter->first << " " << iter->second << endl;
		if (iter->first.length()>0)
		{
			w.str = iter->first;
			w.count = iter->second;
			vec.push_back(w);
		}
		
	}
	sort(vec.begin(), vec.end(), cmp);//对vector进行排序
	int count = vec.size()*0.1;
	cout << vec.size() << endl;
	for (int i = 0; i < count; i++) {
		cout << vec[i].count << ":" << vec[i].str << endl;
	}
	return 0;
}

R7-3 新浪微博热门话题

新浪微博可以在发言中嵌入“话题”，即将发言中的话题文字写在一对“#”之间，就可以生成话题链接，点击链接可以看到有多少人在跟自己讨论相同或者相似的话题。新浪微博还会随时更新热门话题列表，并将最热门的话题放在醒目的位置推荐大家关注。

本题目要求实现一个简化的热门话题推荐功能，从大量英文（因为中文分词处理比较麻烦）微博中解析出话题，找出被最多条微博提到的话题。

输入格式:

输入说明：输入首先给出一个正整数N（≤105），随后N行，每行给出一条英文微博，其长度不超过140个字符。任何包含在一对最近的#中的内容均被认为是一个话题，输入保证#成对出现。

输出格式:

第一行输出被最多条微博提到的话题，第二行输出其被提到的微博条数。如果这样的话题不唯一，则输出按字母序最小的话题，并在第三行输出And k more ...，其中k是另外几条热门话题的条数。输入保证至少存在一条话题。

注意：两条话题被认为是相同的，如果在去掉所有非英文字母和数字的符号、并忽略大小写区别后，它们是相同的字符串；同时它们有完全相同的分词。输出时除首字母大写外，只保留小写英文字母和数字，并用一个空格分隔原文中的单词。

输入样例:

4
This is a #test of topic#.
Another #Test of topic.#
This is a #Hot# #Hot# topic
Another #hot!# #Hot# topic

输出样例:

Hot
2
And 1 more ...

#include<bits/stdc++.h> //万能头文件，里面包含了大部分标准库
using namespace std;
map<string,int> mp; //定义字符串-整数映射，用于存储每个单词出现的次数
string s; //定义字符串s，用于存储出现次数最多的单词
string set_string(string ss) //定义函数set_string，用于将字符串转换为小写字母、去除标点符号、去除多余空格
{
    string cnt; //定义字符串cnt，用于存储去除标点符号、多余空格后的结果
    bool is_repeat=false; //定义布尔变量is_repeat，用于判断多余空格是否已经去除
    for(int i=0; i<ss.length(); i++) //遍历字符串ss的所有字符
    {
        if(ss[i]>='A'&&ss[i]<='Z') //如果是大写字母
        {
            cnt+=(ss[i]-'A'+'a'); //转换为小写字母并添加到cnt中
            is_repeat=false; //重置is_repeat为false
        }
        else if((ss[i]>='a'&&ss[i]<='z')||(ss[i]>='0'&&ss[i]<='9')) //如果是小写字母或数字
        {
            cnt+=ss[i]; //添加到cnt中
            is_repeat=false; //重置is_repeat为false
        }
        else if(!is_repeat) //如果是标点符号或多余空格，并且is_repeat为false
        {
            cnt+=' '; //添加一个空格到cnt中
            is_repeat=true; //设置is_repeat为true
        }
    }
    if(cnt[cnt.length()-1]==' ') //如果cnt末尾是空格
        cnt.erase(cnt.end()-1); //删除末尾的空格
    return cnt; //返回去除标点符号、多余空格后的字符串
}
string cmp(string s1,string s2) //定义函数cmp，用于比较两个字符串大小
{
    return s1<s2?s1:s2; //返回字典序较小的那个字符串
}
int main()
{
    int n;
    cin>>n; //读取输入的字符串数量
    getchar(); //吞掉cin读取的回车符
    while(n--) //循环读取每个字符串并统计其中的单词出现次数
    {
        map<string,int> small_map; //定义map类型变量small_map，用于存储当前字符串中每个单词出现的次数
        string ss; //定义字符串ss，用于存储从当前字符串中提取的单词
        getline(cin,s); //读取当前字符串，注意要使用getline函数，否则会导致读取不完整
        for(int i=0; i<s.length(); i++) //遍历当前字符串中的所有字符
        {
            ss=""; //重置ss为空字符串
            if(s[i]=='#') //如果当前字符是'#'
            {
                i++; //将i向后移动一位
                while(s[i]!='#') //将i不断向后移动，并将所有不为'#'的字符添加到ss中
                    ss+=s[i++];
                ss=set_string(ss); //调用set_string函数，将字符串转换为小写字母、去除标点符号、去除多余空格
            }
            if(ss=="") //如果ss为空字符串，则跳过当前单词
                continue;
            small_map[ss]++; //在small_map中增加当前单词的出现次数
        }
        map<string,int>::iterator it; //定义map迭代器it
        for(it=small_map.begin(); it!=small_map.end(); it++) //遍历当前字符串中的所有单词
        {
            mp[it->first]++; //在mp中增加当前单词的出现次数
        }
    }
    int maxn=0,repeat=0; //定义maxn和repeat变量，分别表示出现次数最多的单词数量和与之出现次数相同的单词数量
    map<string,int>::iterator it; //定义map迭代器it
    for(it=mp.begin();it!=mp.end();it++) //遍历mp中的所有单词
    {
        if(it->second>maxn) //如果当前单词出现次数大于maxn
        {
            maxn=it->second; //更新maxn
            s=it->first; //更新出现次数最多的单词
            repeat=0; //重置repeat为0
        }
        else if(it->second==maxn) //如果当前单词出现次数等于maxn
        {
            s=cmp(s,it->first); //比较s和当前单词，更新s为字典序较小的那个字符串
            repeat++; //增加repeat的值
        }
    }
    cout<<(char)(s[0]-'a'+'A'); //将出现次数最多的单词首字母转换为大写，并输出
    for(int i=1;i<s.length();i++)
        cout<<s[i]; //输出出现次数最多的单词剩下的部分
    cout<<endl<<maxn<<endl; //输出出现次数最多的单词的出现次数
    if(repeat)
        cout<<"And "<<repeat<<" more ..."<<endl; //如果还有与之出现次数相同的单词，则输出相应信息
}

R7-4 航空公司VIP客户查询

不少航空公司都会提供优惠的会员服务，当某顾客飞行里程累积达到一定数量后，可以使用里程积分直接兑换奖励机票或奖励升舱等服务。现给定某航空公司全体会员的飞行记录，要求实现根据身份证号码快速查询会员里程积分的功能。

输入格式:

输入首先给出两个正整数N（≤105）和K（≤500）。其中K是最低里程，即为照顾乘坐短程航班的会员,航空公司还会将航程低于K公里的航班也按K公里累积。随后N行，每行给出一条飞行记录。飞行记录的输入格式为：18位身份证号码（空格）飞行里程。其中身份证号码由17位数字加最后一位校验码组成，校验码的取值范围为0~9和x共11个符号；飞行里程单位为公里，是(0, 15 000]区间内的整数。然后给出一个正整数M（≤105），随后给出M行查询人的身份证号码。

输出格式:

对每个查询人，给出其当前的里程累积值。如果该人不是会员，则输出No Info。每个查询结果占一行。

输入样例:

4 500
330106199010080419 499
110108198403100012 15000
120104195510156021 800
330106199010080419 1
4
120104195510156021
110108198403100012
330106199010080419
33010619901008041x

输出样例:

800
15000
1000
No Info

#include<iostream>
#include<map>
using namespace std;
map<string,int>p;
int main()
{
	int n,m,c,k;
	char s[100];
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++)
	{
        scanf("%s %d",s,&k);
		if(k>=m) p[s]+=k;
		else    p[s]+=m;
	}
	scanf("%d",&c);
	while(c--)
    {
       scanf("%s",s);
       if(p.find(s)!=p.end())
	   printf("%d\n",p[s]);
	   else
       printf("No Info\n");
	}
    return 0;
}

R7-1 字符串关键字的散列映射

给定一系列由大写英文字母组成的字符串关键字和素数P，用移位法定义的散列函数H(Key)将关键字Key中的最后3个字符映射为整数，每个字符占5位；再用除留余数法将整数映射到长度为P的散列表中。例如将字符串AZDEG插入长度为1009的散列表中，我们首先将26个大写英文字母顺序映射到整数0~25；再通过移位将其映射为3×322+4×32+6=3206；然后根据表长得到3206%1009=179，即是该字符串的散列映射位置。

发生冲突时请用平方探测法解决。

输入格式:

输入第一行首先给出两个正整数N（≤500）和P（≥2N的最小素数），分别为待插入的关键字总数、以及散列表的长度。第二行给出N个字符串关键字，每个长度不超过8位，其间以空格分隔。

输出格式:

在一行内输出每个字符串关键字在散列表中的位置。数字间以空格分隔，但行末尾不得有多余空格。

输入样例1:

4 11
HELLO ANNK ZOE LOLI

输出样例1:

3 10 4 0

输入样例2:

6 11
LLO ANNA NNK ZOJ INNK AAA

输出样例2:

3 0 10 9 6 1

#include<iostream> // 包含输入输出流的头文件
#include<map>  // 包含map容器的头文件
using namespace std;

map<string, int> p; // 定义一个键为字符串、值为整数的map容器p

int main()
{
    int n, m, c, k; // 定义整数变量n、m、c和k
    char s[100]; // 定义字符数组s，用于存储字符串

    scanf("%d %d", &n, &m);  // 读取n和m的值

    for(int i = 0; i < n; i++) // 循环读取n个数据
    {
        scanf("%s %d", s, &k); // 读取字符串s和整数k

        if(k >= m) // 如果k大于等于m
            p[s] += k; // 在map p中，键为s的值增加k
        else
            p[s] += m; // 在map p中，键为s的值增加m
    }

    scanf("%d", &c); // 读取查询次数c
    while(c--) // 循环进行c次查询
    {
        scanf("%s", s); // 读取字符串s

        if(p.find(s) != p.end()) // 在map p中查找键为s的值
            printf("%d\n", p[s]); // 输出找到的值
        else
            printf("No Info\n"); // 输出未找到信息
    }

    return 0;
}

以上就是本篇的全部内容，在注释中理解思路即可。在下一篇中我们将进行并查集的学习。