简介

本文为SZU 数据结构 课程 哈希表与排序章节 第一节课哈希查找的AC代码

内容包括：哈希查找，插入排序，字典树

仅供学习与参考

代码具体解题思路已写在内部

推荐复制至编辑器使用

---

A. DS哈希查找—线性探测再散列

题目描述：

输入样例：

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

// A. DS哈希查找—线性探测再散列
// 思路：通过哈希函数计算出插入值的坐标，如果坐标有被别的元素占用了则往后找（找到数组末尾则从头开始找），直到找到空位
// #include <iostream>
// #include <vector>

// using namespace std;

// int main(){
//     int t;
//     cin>>t;
//     while(t--){
//         int n,m;
//         cin>>n>>m;
//         vector<int> hash(n,-1);
//         for(int i = 0;i<m;i++){
//             int num;
//             cin>>num;
//             if(hash[num%11]==-1){
//                 hash[num%11] = num; // 有空位
//             }else{
//                 int pl = num%11+1;
//                 while(hash[pl%n]!=-1){
//                     pl++; //没空位，往后找空位
//                 }
//                 hash[pl%n] = num;
//             }
//         }
//         for(int i = 0;i<n;i++){
//             if(hash[i]!=-1){
//                 cout<<hash[i];
//             }else{
//                 cout<<"NULL";
//             }
//             if(i!=n-1){
//                 cout<<" ";
//             }
//         }
//         cout<<endl;
//         int k;
//         cin>>k;
//
//         for(int i = 0;i<k;i++){
//             int search;
//             cin>>search;
//             int pl = search%11;
//             int cnt = 0;
//             while(hash[pl%n]!=search&&hash[pl%n]!=-1){
//                 pl++; //找到目标元素或者遇到空位则退出循环
//                 cnt++;
//             }
//             if(hash[pl%n]==search){
//                 cout<<1<<" "<<cnt+1<<" "<<(pl%n)+1<<endl;;
//             }else{
//                 cout<<0<<" "<<cnt+1<<endl;
//             }
//         }
//     }
//     return 0;
// }

---

B. DS哈希查找—二次探测再散列

题目描述：

输入样例：

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

// B. DS哈希查找—二次探测再散列
// 思路：通过哈希函数算出插入值的坐标，如果有空位则直接插入元素，否则通过往前和往后的二次函数计算寻找空位坐标
//      查找时
// #include <iostream>
// #include <vector>

// using namespace std;

// int main() {
//     int t;
//     cin >> t;  
//     while (t--) { //插入元素
//         int m, n;
//         cin >> m >> n;  
//         vector<int> map(m, -1);  
//         for(int i = 0;i<n;i++){
//             int val;
//             cin>>val;
//             int pos = val%11;
//             if(map[pos]==-1){
//                 map[pos] = val;
//             }else{
//                 int k = 1;
//                 while(1){  //往前和后找空位
//                     if(map[(pos+k*k)%m]==-1){
//                         map[(pos+k*k)%m] = val;
//                         break;
//                     }else if(pos-k*k>=0&&map[(pos-k*k)%m]==-1){
//                         map[(pos-k*k)%m] = val;
//                         break;
//                     }else{
//                         if(map[m+(pos+k*k)%m]==-1){
//                             map[m+(pos+k*k)%m] = val;
//                             break;
//                         }else if(map[m+(pos-k*k)%m]==-1){
//                             map[m+(pos-k*k)%m] = val;
//                             break;
//                         }
//                     }
//                     k++;
//                 }
//             }
//         }
//         for(int i = 0;i<m;i++){
//             if(map[i]!=-1){
//                 cout<<map[i];
//             }else{
//                 cout<<"NULL";
//             }
//             if(i!=m-1){
//                 cout<<" ";
//             }
//         }
//         cout<<endl;
//
//         int k; //查找
//         cin>>k;
//         while(k--){
//             int search;
//             cin>>search;
//             int pos = search%11;
//             int cnt = 0;
//             int i = 1;
//             int flag = 1,t = pos;     //t表示前后位置的查找
//             while(1){
//                 cnt++;
//                 if(map[t]==search){
//                     cout<<1<<" "<<cnt<<" "<<t+1<<endl;
//                     break;
//                 }else if(map[t]==-1){
//                     cout<<0<<" "<<cnt<<endl;
//                     break;
//                 }
//                 if(flag){
//                     flag = 0;
//                     t = (pos+i*i)%m;
//                 }else{
//                     flag = 1;
//                     t = (pos-i*i+m)%m;
//                     i++;
//                 }
//             }
//         }
//     }
//     return 0;
// }

---

C. DS哈希查找--链地址法(表头插入)

题目描述：

输入样例：

6
11 23 39 48 75 62
6
39
52
52
63
63
52

输出样例：

6 1
error
8 1
error
8 1
8 2

// C. DS哈希查找--链地址法(表头插入)
// 思路：哈希函数计算坐标，属于该坐标的元素都放在一个数组中，每次插入时从头插入，查找时从头查找
// #include <iostream>
// #include <vector>

// using namespace std;

// void insert(vector<vector<int>>& mp,int val){
//     int pl = val%11;
//     mp[pl].insert(mp[pl].begin(),val); //计算坐标，并插入元素
// }
// void search(int val,vector<vector<int>>& mp){
//     int pl = val%11;
//     for(int i = 0;i<mp[pl].size();i++){
//         if(mp[pl][i]==val){
//             cout<<pl<<" "<<i+1<<endl;
//             return; //查找成功立刻返回
//         }
//     }
//     cout<<"error"<<endl; //查找失败插入元素
//     insert(mp,val);
// }
// int main(){
//     int n;
//     vector<vector<int>> mp(11);
//     cin>>n;
//     for(int i = 0;i<n;i++){
//         int val;
//         cin>>val;
//         insert(mp,val);
//     }
//     int m;
//     cin>>m;
//     while(m--){
//         int val;
//         cin>>val;
//         search(val,mp);
//     }
//     return 0;
// }

---

D. DS哈希查找与增补（表尾插入）

题目描述：

输入样例：

6
11 23 39 48 75 62
6
39
52
52
63
63
52

输出样例：

6 1
error
8 1
error
8 2
8 1

//D. DS哈希查找与增补（表尾插入）
// 思路：与上一题一样，元素插入在对于坐标数组的末尾
// #include <iostream>
// #include <vector>

// using namespace std;

// void insert(vector<vector<int>>& mp,int val){
//     int pl = val%11;
//     mp[pl].push_back(val);
// }
// void search(int val,vector<vector<int>>& mp){
//     int pl = val%11;
//     for(int i = 0;i<mp[pl].size();i++){
//         if(mp[pl][i]==val){
//             cout<<pl<<" "<<i+1<<endl;
//             return;
//         }
//     }
//     cout<<"error"<<endl;
//     insert(mp,val);
// }
// int main(){
//     int n;
//     vector<vector<int>> mp(11);
//     cin>>n;
//     for(int i = 0;i<n;i++){
//         int val;
//         cin>>val;
//         insert(mp,val);
//     }
//     int m;
//     cin>>m;
//     while(m--){
//         int val;
//         cin>>val;
//         search(val,mp);
//     }
//     return 0;
// }

---

E. DS内排—直插排序

题目描述：

输入样例：

7 34 23 677 2 1 453 3

输出样例：

23 34 677 2 1 453 3
23 34 677 2 1 453 3
2 23 34 677 1 453 3
1 2 23 34 677 453 3
1 2 23 34 453 677 3
1 2 3 23 34 453 677

// E. DS内排—直插排序 
// 思路：每次遍历待插元素，寻找第一个小于待插元素的元素，并将大于待插元素的元素都往后排
// #include <iostream>
// using namespace std;

// int main() {
//     int n;
//     cin >> n;  

//     int nums[n]; 

//     for (int i = 0; i < n; i++) {
//         cin >> nums[i];
//     }

//     for (int i = 1; i < n; i++) {
//         int key = nums[i];  //待插元素key 
//         int j = i - 1;

//         while (j >= 0 && nums[j] > key) {
//             nums[j + 1] = nums[j]; // 找到第一个比key小的元素，j前面的元素都往后挪一位
//             j--;
//         }
//         nums[j + 1] = key; // 插入key
//         for (int k = 0; k < n; k++) { //每次循环都要输出一遍数组内容
//             cout << nums[k];
//             if (k!= n - 1) {
//                 cout << " ";
//             }
//         }
//         cout << endl;
//     }
//     return 0;
// }

---

F. 逆散列问题

题目描述：

输入样例：

11
33 1 13 12 34 38 27 22 32 -1 21

输出样例：

1 13 12 21 33 34 38 27 22 32

//F. 逆散列问题
// 思路： 最优考虑需要输入的数组中每次插入的元素越小越好，所以进行排序从小到大遍历数组
//       题目可以理解成往一个全新空数组中填入nums[i]，让他还原成nums
//       用一个答案数组ans记录结果，一个合法数组arr表示原数组nums中存在的数(非-1)，并对arr进行排序
//       vis数组表示nums上各个位置的占用情况，st记录是否处理过某个元素
//       对于arr中的一个元素x，其通过哈希函数H(x)的下标为 pos：
//       1.nums[pos]==x 并且vis[pos]=false 说明该位置为空，可以直接占用，并将x加入到st中。
//       2.nums[pos]!=x 并且vis[pos]=false 该位置为空，但原数组中pos的位置填入的数不是x，不能占用。x需要往后线性探测
//       3.vis[pos] = true, 该位置不是空位，x要往后找位置 pos = pos+1
//     通过一层循环枚举合法nums元素arr[i]， 一层循环查找ans[i]，一层循环查找 ans[i]的合法位置

// #include <iostream>
// #include <vector>
// #include <algorithm>
// #include <unordered_set>
// using namespace std;

// void func(vector<int>& nums) {
//     vector<int> arr;  //表示合法元素
//     for (int i = 0; i < nums.size(); i++) {
//         if(nums[i]!=-1)
//             arr.push_back(nums[i]);
//     }
//     sort(arr.begin(),arr.end()); //排序，保证每次枚举都是nums里的最小元素
//     int m = arr.size(),n = nums.size();
//     unordered_set<int> st; //记录是否使用了 arr[i]
//     vector<int> vis(n,false);  //记录nums的pos位置是否被占用了
//     vector<int> ans(m); //记录答案

//     for(int i = 0;i<m;i++){  //枚举答案ans[i]
//         for(int j = 0;j<m;j++){    //枚举可能放在nums[pos]位置的arr[j]
//             bool find = false;
//             if(st.count(arr[j])) continue;  //如果arr[j]已经访问过了则访问下一个元素
//             int pos = arr[j]%n;
//             while(1){   //枚举pos
//                 if(!vis[pos]&&nums[pos]==arr[j]){
//                     st.insert(arr[j]);  //如果nums[pos] = arr[j] 并且 pos 没被占用
//                     vis[pos] = true; 
//                     ans[i] = arr[j];   //说明 arr[j]为 ans[i]
//                     find = true;
//                     break;
//                 }
//                 if(!vis[pos])   //arr[j]需要后续探测
//                     break;
//                 pos = (pos+1)%n; // pos位置被占用，继续往后探测空位
//             }
//             if(find) break;  //找到了，枚举下一个ans[i]
//         }
//     }

//     for(int i = 0;i<m;i++){
//         cout<<ans[i];
//         if(i!=m-1){        //输出答案ans
//             cout<<" ";
//         }
//     }
// }

// int main(){
//     int n;
//     cin>>n; //初始化数组
//     vector<int> nums(n,-1);
//     for(int i = 0;i<n;i++){
//         cin>>nums[i];
//     }
//     func(nums);
//     return 0;
// }

---

G. DS哈希查找--Trie树

题目描述：

输入样例：

abcd abd bcd efg hig
3
ab
bc
abcde

输出样例：

abehbcficddggd
2
1
0

//G. DS哈希查找--Trie树
// 思路：字典树用于记录查找相同前缀的字符串。
//    例如a="abce",b="abcd"，a,b拥有相同前缀"abc"，'e','d'则为同一前缀abc的不同后缀分支
//    对于字符串s中的i位置，s[i-1]是s[i]的父节点，s[i]是s[i+1]的父节点
//    当前字符节点为p，下一个插入的字符节点为q
//    如果在当前字符串s中 q是p的下一位字符，则q会是p的子节点，否则q会是p的兄弟节点
//    计算有多少个以查找字符为前缀的字符串本质为寻找查找字符串最后一个字符的叶子数量
// #include <iostream>
// #include <vector>
// #include <queue>
// #include <string>
// #include <algorithm>
// #include <functional>

// using namespace std;
// struct TrieNode{
//     char val;
//     vector<TrieNode*> children;
//     TrieNode(char val):val(val),children(26,nullptr){}
// };
// void bfs(TrieNode* root){
//     queue<TrieNode*> q;
//     for(int i = 0;i<26;i++){
//         if(root->children[i]){
//             q.push(root->children[i]);
//         }
//     }
//     while(!q.empty()){
//         TrieNode* node = q.front();
//         q.pop();
//         cout<<node->val;
//         for(int i = 0;i<26;i++){
//             if(node->children[i]){
//                 q.push(node->children[i]);
//             }
//         }
//     }
//     cout<<endl;
// }

// int search(string target,TrieNode* root){
//     TrieNode* cur = root;
//     for(int i = 0;i<target.size();i++){
//         if(cur->children[target[i]-'a']){
//             cur = cur->children[target[i]-'a'];
//         }else{
//             return 0;
//         }
//     }

//     function<int(TrieNode*)> dfs = [&](TrieNode* node) -> int {
//         if (all_of(node->children.begin(), node->children.end(), [](TrieNode* child){ return child == nullptr; })) {
//             return 1;
//         }
//         int cnt = 0;
//         for (int i = 0; i < 26; i++) {
//             if (node->children[i]) {
//                 cnt += dfs(node->children[i]);  
//             }
//         }
//         return cnt;
//     };
//     return dfs(cur);
// }
// int main(){
//     string s;
//     TrieNode* root = new TrieNode(' ');
//     while(cin>>s){
//         if(isdigit(s[0]))
//             break;
//         TrieNode* cur = root;
//         for(int i = 0;i<s.size();i++){
//             if(!cur->children[s[i]-'a']){
//                 cur->children[s[i]-'a'] = new TrieNode(s[i]);
//             }
//             cur = cur->children[s[i]-'a'];
//         }
//     }
//     bfs(root);
//     int t = stoi(s);
//     while(t--){
//         cin>>s;
//         cout<<search(s,root)<<endl;
//     }
//     return 0;
// }

---

手写不易，有问题疑问欢迎评论区指正orz