数据结构_成绩查询

数据结构_成绩查询_cjcx

问题描述

录入 n 个学生的成绩,并查询。
★数据输入
第一行输入包括 n、 m(1<=n<=50,000,1<=m<=100,000)两个数字。
接下来 n 行,每行包含名字和成绩,名字用字符串表示,长度不超过 4.成绩为不
超过 100 的非负整数,名字仅由小写字母组成。
接下来 m 行,每行包括一个名字。

★数据输出
输出 m 行,如果查询的学生不存在,输出”not,exist!”,否则输出学生的成绩。

　　输入示例

　　　　3 4
　　　　hbb 90
　　　　vayh 80
　　　　loog 85
　　　　leaf
　　　　loog
　　　　vayh
　　　　vyah

　　输出示例

　　　　not,exist!

★提示
n 个名字各不相同
60%的数据
1<=n,m<=2,000
100%的数据
1<=n<=50,000,1<=m<=100,000

解题思路

　　注意到名字为不超过4的字符串

　　将名字中的字符转换为数字，a为1，b为2......，若长度不足4，则补0

　　这样每个名字都可以与四个数字abcd对应

　　这时候有两种做法

　　　　（1）开四维数组arr[27][27][27][27]，用arr[a][b][c][d]存成绩

　　　　（2）开一维数组arr，对abcd分别附权值 26^0、26^1、26^2、26^3，用arr[a*26^0+b*26^1+c*26^2+d*26^3]存

　　　　用第二种做法会省一些空间，不会出现例如0233、0011这样前面有0的情况

　　　　补0是在后面补的233->2330 11->1100

　　　　而第一种会浪费掉这一部分空间

　　由于题目给出的成绩 0<=k<=99，对数组初始化时全部初始化为0，当作空，存的时候+1存，读取时候-1

code（第一种做法）

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 
 5 char arr[27][27][27][27]={0};
 6 int pos[4];
 7 
 8 void init(char *str, int &data)
 9 {
10     memset(pos,0,sizeof(int)*4);
11     int len = strlen(str);
12     int i;
13     for(i=0;i<len;i++)
14     {
15         pos[i] = str[i]-'a'+1;
16     }
17     arr[pos[0]][pos[1]][pos[2]][pos[3]] = (char)(data+1);
18 }
19 
20 void find(char *str)
21 {
22     memset(pos,0,sizeof(int)*4);
23     int len = strlen(str);
24     int i;
25     for(i=0;i<len;i++)
26     {
27         pos[i] = str[i]-'a'+1;
28     }
29     if(arr[pos[0]][pos[1]][pos[2]][pos[3]] == 0)
30     {
31         printf("not,exist!
");
32     }
33     else
34     {
35         printf("%d
",(int)(arr[pos[0]][pos[1]][pos[2]][pos[3]])-1);
36     }
37 }
38 
39 int main()
40 {
41     int i;
42     int n,m;
43     char str[5]={0};
44     int data;
45     
46     scanf("%d %d",&n,&m);
47     getchar();
48     for(i=0;i<n;i++)
49     {
50         scanf("%s %d",str,&data);
51         getchar();
52         init(str,data);
53     }
54     for(i=0;i<m;i++)
55     {
56         scanf("%s",str);
57         getchar();
58         find(str);
59     }
60 
61     return 0;
62 }