1. DS哈希查找–链地址法
题目描述
给出一个数据序列，建立哈希表，采用求余法作为哈希函数，模数为11，哈希冲突用链地址法和表头插入
如果首次查找失败，就把数据插入到相应的位置中
实现哈希查找功能
输入
第一行输入n，表示有n个数据
第二行输入n个数据，都是自然数且互不相同，数据之间用空格隔开
第三行输入t，表示要查找t个数据
从第四行起，每行输入一个要查找的数据，都是正整数
输出
每行输出对应数据的查找结果
输入样例
6
11 23 39 48 75 62
6
39
52
52
63
63
52
输出样例
6 1
error
8 1
error
8 1
8 2
提示
注意，当两次输入要相同的查找数据，如果第一次查找不成功就会执行插入，那么第二次查找必然成功，且查找次数为1次（因为做表头插入）
例如示例数据中输入两次52，第一次查找失败就把52插入到位置8，第二次查找就成功了，所以第一次输出error，第二次就输出8 1
为什么第三次输入52会输出8 2
参考代码
#include<iostream> using namespace std; struct Node { int data; int key; struct Node* next; }; class HashCheck { Node *Data; int n; public: HashCheck(int n) { this->n = n; Data = new Node[20]; } void create(int data[]); void Check(int e); void insert(int a,int e); }; void HashCheck::insert(int a,int e) { Node* p = new Node(); p->next = Data[a].next; p->data = Data[a].data; Data[a].data = e; Data[a].next = p; } void HashCheck::create(int data[]) { for (int i = 0;i < n;i++) { Data[i].key = data[i]%11; Data[i].data = data[i]; Data[i].next = NULL; } } void HashCheck::Check(int e) { int mod = e % 11; int count = 0; int i; int flag=0; Node* p = new Node(); for (i = 0;i < n;i++) { if (Data[i].key == mod) { flag = 1; p = &Data[i]; while (p!= NULL) { count++; if (p->data == e) { cout << mod << " " << count << endl; break; } p = p->next; } if (p == NULL) { cout << "error\n"; insert(i,e); } break; } } if (flag==0) { cout << "error\n"; n = n + 1; Data[n-1].data = e; Data[n-1].key = e % 11; Data[n-1].next = NULL; } } int main() { int n; int* data; cin >> n; data = new int[n]; for (int i = 0;i < n;i++) cin >> data[i]; HashCheck hc(n); hc.create(data); int t; cin >> t; int e; while (t--) { cin >> e; hc.Check(e); } return 0; }
2. DS哈希查找—线性探测再散列
题目描述
定义哈希函数为H(key) = key%11，输入表长（大于、等于11）。输入关键字集合，用线性探测再散列构建哈希表，并查找给定关键字。
–程序要求–
若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件，不看代码，作0分处理
不允许使用第三方对象或函数实现本题的要求
输入
测试次数t
每组测试数据为：
哈希表长m、关键字个数n
n个关键字
查找次数k
k个待查关键字
输出
对每组测试数据，输出以下信息：
构造的哈希表信息，数组中没有关键字的位置输出NULL
对k个待查关键字，分别输出：0或1（0—不成功，1—成功）、比较次数、查找成功的位置（从1开始）
输入样例
1
12 10
22 19 21 8 9 30 33 4 15 14
4
22
56
30
17
输出样例
22 30 33 14 4 15 NULL NULL 19 8 21 9
1 1 1
0 6
1 6 2
0 1
参考代码
#include<iostream> using namespace std; int main(){ int t; cin>>t; while(t--){ int m; int n; cin>>m>>n; int array[m]; for(int i= 0; i< m ; i++) array[i]= -100000; for(int i= 0; i< n; i++){ int shu; cin>>shu; if(array[shu%11]== -100000){ array[shu%11]= shu; } else{ int d= 0; while(true){ if(array[(shu%11+ d)%(m)]== -100000){ array[(shu%11+ d)%(m)]= shu; break; } else d++; } } } for(int i= 0; i< m; i++){ if(array[i]!= -100000) cout<<array[i]; else cout<<"NULL"; if(i!= m- 1) cout<<' '; } cout<<endl; int k; cin>>k; while(k--){ int shu; cin>>shu; int times= 0; int pos= 0; int d= 0; while(true){ times++; if(array[(shu%11+ d)%m]== shu){ cout<<"1"<<' '<<times<<' '<<(shu%11+ d)%m+ 1<<endl; break; } else if(d== m||array[(shu%11+ d)%m]== -100000){ cout<<"0"<<' '<<times<<endl; break; } else d++; } } } return 0; }
3. DS哈希查找—二次探测再散列
题目描述
定义哈希函数为H(key) = key%11。输入表长（大于、等于11），输入关键字集合，用二次探测再散列构建哈希表，并查找给定关键字。
输入
测试次数t
每组测试数据格式如下：
哈希表长m、关键字个数n
n个关键字
查找次数k
k个待查关键字
输出
对每组测试数据，输出以下信息：
构造的哈希表信息，数组中没有关键字的位置输出NULL
对k个待查关键字，分别输出：
0或1（0—不成功，1—成功）、比较次数、查找成功的位置（从1开始）
输入样例
1
12 10
22 19 21 8 9 30 33 4 41 13
4
22
15
30
41
输出样例
22 9 13 NULL 4 41 NULL 30 19 8 21 33
1 1 1
0 3
1 3 8
1 6 6
参考代码
#include <iostream> using namespace std; int main() { int t; cin >> t; while (t--) { int m, n; cin >> m >> n; int* array= new int[m+ 5]; for (int i = 0; i < m + 5; i++) array[i] = -100000; for (int i = 0; i < n; i++) { int shu; cin >> shu; int d = 0; int flag = 0; while (d <= m / 2) { flag++; int sym; if (flag >= 2&&flag% 2== 0) d++; if (flag % 2 == 0) sym = 1; else sym = -1; int pos = (shu % 11 + sym * d*d) % m; if (pos < 0) pos = m + pos; if (array[pos] == -100000) { array[pos] = shu; break; } } } for (int i = 0; i < m; i++) { if (array[i] == -100000) cout << "NULL"; else cout << array[i]; if (i != m - 1) cout << " "; else cout << endl; } int k; cin >> k; while (k--) { int shu; cin >> shu; int pos = 0; int times = 0; int d = 0; int flag = 0; while (true) { times++; flag++; int sym; if (flag >= 2 && flag % 2 == 0) d++; if (flag % 2 == 0) sym = 1; else sym = -1; int pos = (shu % 11 + sym * d*d) % m; if (pos < 0) pos = m + pos; if (array[pos] == -100000|| d> m/ 2) { cout << "0" << ' ' << times << endl; break; } if (array[pos] == shu) { cout << "1" << ' ' << times <<" "<<pos + 1 << endl; break; } } } } return 0; }
4. DS哈希查找–Trie树
题目描述
Trie树又称单词查找树，是一种树形结构，如下图所示。
它是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。
输入的一组单词，创建Trie树。输入字符串，计算以该字符串为公共前缀的单词数。
（提示：树结点有26个指针，指向单词的下一字母结点。）
输入
测试数据有多组
每组测试数据格式为：
第一行：一行单词，单词全小写字母，且单词不会重复，单词的长度不超过10
第二行：测试公共前缀字符串数量t
后跟t行，每行一个字符串
输出
每组测试数据输出格式为：
第一行：创建的Trie树的层次遍历结果
第2~t+1行：对每行字符串，输出树中以该字符串为公共前缀的单词数。
输入样例
abcd abd bcd efg hig
3
ab
bc
abcde
输出样例
abehbcficddggd
2
1
0
参考代码
#include <iostream> #include <stdio.h> #include <vector> #include <queue> using namespace std; struct Node{ char date; struct Node *next[26]; //next指针有26个，代表26个字母 }; class Tire{ private: struct Node *m; public: Tire(){}; ~Tire(){}; void test(); int get_num(struct Node *t); void level_print(struct Node *t); }; void Tire::level_print(struct Node *t) //层序遍历输出结果,t默认取树根 { queue<struct Node*> q1; //设置一个队列，先将根结点不空的孩子加进来 for(int i = 0; i < 26; i++) { if(t[i].date != '0') { q1.push(&t[i]); } } while(!q1.empty()) //在队列不空的情况下，每次输出结点对应的字符，然后将结点的孩子中不空的结点加到队列中 { struct Node *t = q1.front(); q1.pop(); cout<<t->date; for(int i = 0; i < 26; i++) { if(t->next[i] != NULL) { q1.push(t->next[i]); } } } cout<<endl; } int Tire::get_num(struct Node *t) //获取该结点的子树的个数，需要递归实现 { int coun=0; for(int i=0;i<26;i++) { if(t->next[i] != NULL) //如果孩子结点不空，则计算此孩子结点的子树个数，加到父结点的子树个数中去 { coun += get_num(t->next[i]); } } if(coun == 0) //若最后的计算结果显示所有孩子结点都是空，证明只含有父结点这棵树，长度就是1 return 1; else return coun; } void Tire::test() { m = new Node[26]; for(int i=0; i<26; i++) //初始化结构体 { m[i].date='0'; for(int j=0;j<26;j++) m[i].next[j]=NULL; } char str[1024]; int num=0; while((str[num] = getchar()) != '\n') //读入第一行输入的所有单词 num++; for(int i=0;i<num;i++) { string t; //对单词进行分割，每次分割出来的单词存在t中 while(str[i] != ' ' && i<num) { t+=str[i]; i++; } struct Node *father = &m[t[0]-'a']; //设置父结点指针，方便单词加到字典树中 father->date = t[0]; for(int j = 1; j < t.length(); j++) { if(father->next[t[j]-'a'] != NULL) //如果单词的第i个字母已经存在字典树中，则父节点继续往下，如果不存在，则生成新的结点加入到字典树中去 { father=father->next[t[j]-'a']; continue; } struct Node* temp = new Node; temp -> date = t[j]; for(int k = 0; k < 26; k++) temp->next[k] = NULL; father->next[t[j]-'a'] = temp; father = father->next[t[j]-'a']; } } level_print(m); //层序遍历字典树输出结果 int n; //输入要检测的前缀的个数 cin>>n; string temp; for(int i=0;i<n;i++) { cin>>temp; //输入前缀 struct Node *father = &m[temp[0]-'a']; for(int j=1;j<temp.length();j++) //father指针取前缀的最后一个字母在树中的位置，如果不存在，则father指针为空 { father = father->next[temp[j]-'a']; if(father == NULL) break; } if(father==NULL) //若father指针为空，则前缀不存在字典树中，输出0 cout<<0<<endl; else //若father指针不为空，则调用计算子树个树函数，输出father指针的子树的个数，此个数即为具有此公共前缀的单词的个数 { int coun = get_num(father); cout<<coun<<endl; } } } int main() { Tire t; t.test(); return 0; }
