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

简介: 【数据结构入门精讲 | 第十五篇】散列表知识点及考研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;
}

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

目录
相关文章
|
1月前
|
存储 算法 数据处理
数据结构从入门到精通——栈
栈,作为一种后进先出(LIFO)的数据结构,在计算机科学中扮演着重要的角色。它的特性使得它在处理函数调用、括号匹配、表达式求值等问题时具有得天独厚的优势。然而,如果我们跳出传统思维的束缚,会发现栈的用途远不止于此。
49 0
|
1月前
|
存储 缓存 算法
数据结构从入门到精通——链表
链表是一种常见的数据结构,由一系列节点组成,每个节点包含数据和指向下一个节点的指针。链表的一个显著特点是,它不需要在内存中连续存储,因此可以高效地插入和删除节点。这种灵活性使得链表在许多应用中成为理想的选择,尤其是在需要动态调整数据结构大小的场景中。
69 0
|
1月前
|
存储 消息中间件 算法
数据结构从入门到精通——顺序表
顺序表是一种常见的线性数据结构,它使用一段连续的存储单元依次存储数据元素。这种数据结构的特点是逻辑上相邻的元素在物理存储位置上也相邻,因此可以快速地访问表中的任意元素。 顺序表的实现通常依赖于数组,数组是一种静态的数据结构,一旦创建,其大小就是固定的。这意味着在顺序表中插入或删除元素可能会导致空间的浪费或不足。例如,如果在一个已经满了的顺序表中插入一个新元素,就需要重新分配更大的数组空间,并将原有元素复制到新数组中,这是一个相对耗时的操作。
51 0
|
20天前
|
存储 NoSQL Java
Redis 数据结构操作入门
Redis 数据结构操作入门
15 0
|
1月前
|
机器学习/深度学习 存储 缓存
数据结构从入门到精通——队列
队列是一种特殊的线性数据结构,遵循先入先出(FIFO)的原则。它只允许在队列的末尾添加元素(称为入队操作),并从队列的开头移除元素(称为出队操作)。队列在多种应用中发挥着重要作用,如计算机系统的任务调度、打印机作业管理以及多线程编程中的线程同步等。
46 0
|
8天前
|
消息中间件 存储 搜索推荐
深入理解栈和队列(二):队列
深入理解栈和队列(二):队列
27 0
|
1月前
【栈】数据结构栈的实现
【栈】数据结构栈的实现
|
1月前
|
存储
数据结构--栈和队列
数据结构--栈和队列
|
1月前
|
C语言
数据结构之栈详解(C语言手撕)
数据结构之栈详解(C语言手撕)
35 1