文章目录
第十四周 哈希查找
A. 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 提示
// 问题 A: DS哈希查找—线性探测再散列 #include <iostream> using namespace std; #define INF -99 int main() { int t; cin >> t; while (t--) { int m, n; cin >> m >> n; int *a = new int[m]; for (int i = 0; i < m; i++) a[i] = INF; // 建表 while (n--) { int num; cin >> num; int di = 1; int h = num % 11; if (a[h] == INF) { a[h] = num; continue; } while (true) { int temp = (h + di) % m; if (a[temp] == INF) { a[temp] = num; break; } else { di++; } } } for (int i = 0; i < m; i++) { if (a[i] == INF) cout << "NULL" << " "; else cout << a[i] << " "; } cout << endl; int k; cin >> k; while (k--) { int f; cin >> f; int h = f % 11; int times = 0; int di = 1; int flag = 0; int tf = 0; int temp = h; /************** * 查找分三种情况： * 1. 要找的关键字的hash地址为空 * 2. 要找的关键字的hash地址不为空且等于关键字 * 3. 要找的关键字的hash地址不为空，也不等于关键字，则进行线性探测 * * * **********/ if (a[h] == INF) { // 第一种情况 cout << 0 << " " << 1 << endl; } else { if (a[h] == f) { // 第二种情况 cout << 1 << " " << 1 << " " << h + 1 << endl; continue; } times++; while (true) { // 第三种情况 int temp = (h + di) % m; times++; if (a[temp] == f) { cout << 1 << " " << times << " " << temp + 1 << endl; flag = 1; break; } else if (a[temp] == INF) { break; } di++; } // while if (flag == 0) { cout << 0 << " " << times << endl; } } } } return 0; }
B. 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 提示
// 问题 B: DS哈希查找—二次探测再散列(关键字互不相同） #include<iostream> using namespace std; #define INF -99 int main() { int t; cin >> t; while( t-- ){ int m, n; cin >> m >> n; int * a = new int[m+5]; for( int i=0; i<m; i++) a[i] = INF; // 建表 while( n-- ){ int num ; cin >> num; int di = 1; int h = num%11; h %= m; if(a[h]==INF){ a[h] = num; continue; } while( true ){ int t1 = (h+di*di)%m; int t2 = (h-di*di)%m; while(t1>=m){ t1-=m; } while(t2<0){ t2+=m; } /******* * 重点： 这里一定要注意对t2的取值范围进行处理，小于0的时候要进行循环移位 * 博主在初学这个的时候，可是被他坑惨了呜呜 * * ******/ if( a[t1%m] == INF ){ a[t1] = num; break; } else if( a[t2%m] == INF ){ a[t2] = num; break; } else{ di++; } } } for(int i=0; i<m; i++){ if(a[i] == INF ) cout<<"NULL"<<" "; else cout<<a[i]<<" "; } cout << endl; int k; cin >> k; while(k--) { int f; cin >> f; int h = f%11; int times = 0; int flag = 0; // 没找到为0， 找到为1 int tf = 0; int di = 1; /************** * 查找分三种情况： * 1. 要找的关键字的hash地址为空 * 2. 要找的关键字的hash地址不为空且等于关键字 * 3. 要找的关键字的hash地址不为空，也不等于关键字，则进行二次探测（平方） * * #### 注意比较次数自加的位置 (在进行比较之前进行次数+1) * 1. 先和自身的hash地址比较 * 2. 和t1 = (h+di*di)%m; t1的地址比较 * 3. 和t2 = (h-di*di)%m; t2 的地址比较 * **********/ if(a[h]==INF){ // 第一种情况 cout<<0<<" "<<1<<endl; } else{ times ++; if( a[h]==f ){ // 第二种情况 cout<< 1 << " " << times << " " << h+1 <<endl; continue; } while(true){ // 第三种情况 int t1 = (h+di*di)%m; int t2 = (h-di*di)%m; while(t1>=m){ t1-=m; } while(t2<0){ t2+=m; } times++; if( a[t1%m]==f ){ cout<<1<<" "<<times<<" "<<t1+1<<endl; flag = 1; break; } if(a[t1%m]==INF ){ // 遇到NULL就跳出 break; } times++; if( a[t2%m]==f ){ cout<<1<<" "<<times<<" "<<t2+1<<endl; flag = 1; break; } if( a[t2%m]==INF ){ // 遇到NULL就跳出 break; } di ++; if(di>m/2) { break; }; } if( flag==0 ){ cout<<0<<" "<<times<<endl; } } } } return 0; }
关于表长的一个小tips
- 可以通过设置表长=
4k+3，来获取完全剩余系，规避重复搜索 - 如果表长不是
4k+3， 冲突次数达到一定的阈值，就需要重新建表
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ayxIdZYA-1623337233975)(C:\Users\dcs\Desktop\notes\study\MD\03数据结构与算法\pics\image-20210610153428027.png)]
C. 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 需要考虑有多轮数据输入的情况！也就是第一个cin或者scanf需要用while来进行循环，例如 while(cin>>...)
#include<iostream> using namespace std; const int is = 11; int a[is][99]; void move(int k){ for(int i=a[k][0]; i>0; i--){ a[k][i+1] = a[k][i]; } } void insert(int data){ int k = data%is; a[k][0] += 1; // 采用头插法 ，所以要移动数据 move(k); a[k][ 1 ] = data; } void search(int data){ int k = data%is; int flag = 0; for(int j=1, len = a[k][0]; j<=len; j++ ){ if(a[k][j]==data){ cout<<k<<" "<<j<<endl; flag = 1; break; } } if(flag==0){ cout<<"error"<<endl; insert(data); } } int main(){ int t; while(cin >> t){ for(int i=0; i<is; i++){ a[i][0] = 0; // 0位记录当前表项的数据元素 for(int j=1; j<99; j++){ a[i][j] = -1; } } while(t--){ int temp; cin>>temp; insert(temp); } int steps; cin >> steps; while(steps--){ /**************** * 要搜索的值情况分三种： * 1. 要搜索的值的记录表没有记录 * 2. 要搜索的值的记录表有记录，但没有要找的值 * 3. 要搜索的值的记录表有记录，但有要找的值 ****************/ int find; cin >> find; int k = find%is; if( a[k][0] == 0){ cout<<"error"<<endl; insert(find); } else{ search(find); } } } return 0; }
D. 问题 D: DS哈希查找与增补
题目描述 给出一个数据序列，建立哈希表，采用求余法作为哈希函数，模数为11，哈希冲突用链地址法和表尾插入 如果首次查找失败，就把数据插入到相应的位置中 实现哈希查找与增补功能 输入 第一行输入n，表示有n个数据 第二行输入n个数据，都是自然数且互不相同，数据之间用空格隔开 第三行输入t，表示要查找t个数据 从第四行起，每行输入一个要查找的数据，都是正整数 输出 每行输出对应数据的查找结果，每个结果表示为数据所在位置[0，11）和查找次数，中间用空格分开 样例输入 6 11 23 39 48 75 62 6 39 52 52 63 63 52 样例输出 6 1 error 8 1 error 8 2 8 1 提示
#include<iostream> using namespace std; const int is = 11; int a[is][99]; void insert(int data){ int k = data%is; a[k][0] += 1; a[k][ a[k][0] ] = data; } void search(int data){ int k = data%is; int flag = 0; for(int j=1, len = a[k][0]; j<=len; j++ ){ if(a[k][j]==data){ cout<<k<<" "<<j<<endl; flag = 1; break; } } if(flag==0){ cout<<"error"<<endl; insert(data); } } int main(){ int t; while(cin >> t){ for(int i=0; i<is; i++){ a[i][0] = 0; // 0位记录当前表项的数据元素 for(int j=1; j<99; j++){ a[i][j] = -1; } } while(t--){ int temp; cin>>temp; insert(temp); } int steps; cin >> steps; while(steps--){ /**************** * 要搜索的值情况分三种： * 1. 要搜索的值的记录表没有记录 * 2. 要搜索的值的记录表有记录，但没有要找的值 * 3. 要搜索的值的记录表有记录，但有要找的值 ****************/ int find; cin >> find; int k = find%is; if( a[k][0] == 0){ cout<<"error"<<endl; insert(find); } else{ search(find); } } } return 0; }
第十五周 DS排序
A. DS排序–直接插入排序
题目描述 给出一个数据序列，使用直接插入排序算法进行降序排序。 输入 第一行输入t，表示有t个测试示例 第二行输入n，表示第一个示例有n个数据(n>1) 第三行输入n个数据，都是正整数，数据之间用空格隔开 以此类推 输出 对每组测试数据，输出每趟排序结果。不同组测试数据间用空行分隔。 样例输入 2 5 111 22 6 444 333 6 21 25 49 25 16 8 样例输出 111 22 6 444 333 111 22 6 444 333 444 111 22 6 333 444 333 111 22 6 25 21 49 25 16 8 49 25 21 25 16 8 49 25 25 21 16 8 49 25 25 21 16 8 49 25 25 21 16 8 提示
#include<iostream> using namespace std; void show(int a[], int len){ for(int i=0; i<len; i++){ cout<<a[i]<<" "; } cout<<endl; }; void z_sort(int a[], int len){ for(int i=1; i<len; i++){ for(int j=i; (j>0) && ( a[j]>a[j-1]) ; j-- ){ a[j] ^= a[j-1]; a[j-1] ^= a[j]; a[j] ^= a[j-1]; } show(a, len); } } int main(){ int step; cin >> step; while(step--){ int t; cin >> t; int *a = new int[t+5]; for(int i=0; i<t; i++) cin>>a[i]; z_sort(a, t); cout<<endl; } return 0; }
B.DS排序–折半插入排序
题目描述 给出一个数据序列，使用折半插入排序算法进行降序排序。 输入 第一行输入t，表示有t个测试示例 第二行输入n，表示第一个示例有n个数据(n>1) 第三行输入n个数据，都是正整数，数据之间用空格隔开 以此类推 输出 对每组测试数据，输出每趟排序结果。不同组测试数据间用空行分隔。 样例输入 2 5 111 22 6 444 333 8 30 13 70 85 39 42 6 20 样例输出 111 22 6 444 333 111 22 6 444 333 444 111 22 6 333 444 333 111 22 6 30 13 70 85 39 42 6 20 70 30 13 85 39 42 6 20 85 70 30 13 39 42 6 20 85 70 39 30 13 42 6 20 85 70 42 39 30 13 6 20 85 70 42 39 30 13 6 20 85 70 42 39 30 20 13 6 提示
#include<iostream> using namespace std; void show(int a[], int len){ for(int i=0; i<len; i++){ cout<<a[i]<<" "; } cout<<endl; }; void z_sort(int a[], int len){ int low = 0,high = 0,mid; int temp = 0; for (int i=1; i<len; i++) { low=0; high=i-1; temp=a[i]; while (low<=high) { mid=(low+high)/2; if (a[mid]<temp) { high=mid-1; }else{ low=mid+1; } } for (int j=i; j>low; j--) { a[j]=a[j-1]; } a[low]=temp;//插入元素 show(a, len); } } int main(){ int step; cin >> step; while(step--){ int t; cin >> t; int *a = new int[t+5]; for(int i=0; i<t; i++) cin>>a[i]; z_sort(a, t); cout<<endl; } return 0; }
c. DS排序–希尔排序
题目描述 给出一个数据序列，使用希尔排序算法进行降序排序。 间隔gap使用序列长度循环除2直到1 输入 第一行输入t，表示有t个测试示例 第二行输入n，表示第一个示例有n个数据(n>1) 第三行输入n个数据，都是正整数，数据之间用空格隔开 以此类推 输出 对每组测试数据，输出每趟排序结果。不同组测试数据间用空行分隔。 样例输入 2 6 111 22 6 444 333 55 8 77 555 33 1 444 77 666 2222 样例输出 444 333 55 111 22 6 444 333 111 55 22 6 444 555 666 2222 77 77 33 1 666 2222 444 555 77 77 33 1 2222 666 555 444 77 77 33 1 提示
#include<iostream> using namespace std; void show(int a[], int len){ for(int i=0; i<len; i++){ cout<<a[i]<<" "; } cout<<endl; }; void Shell(int a[], int len){ for( int gap = len/2; gap >= 1; gap/=2 ){ for(int i = 0; i<gap; i++){ for (int j = i + gap; j < len; j += gap) if (a[j] > a[j - gap]) { int temp = a[j]; int k = j - gap; while (k >= 0 && a[k] < temp) { a[k + gap] = a[k]; k -= gap; } a[k + gap] = temp; } } show(a,len); } } int main() { int step; cin >> step; while(step--){ int t; cin >> t; int *a = new int[t+5]; for(int i=0; i<t; i++) cin>>a[i]; Shell(a, t); cout<<endl; delete []a; } return 0; }
D. DS排序–冒泡排序
题目描述 给定一个包含从0到n-1各一次的数组，若使用冒泡排序将其排为升序，问其中需要进行多少次交换 输入 测试数据有多组， 每组由两行组成：第一行包含正整数n（n <= 5000）; 下一行包含从0到n-1的n个整数的序列。 输出 对于每组测试数据， 输出交换次数 样例输入 10 1 3 6 9 0 8 5 7 4 2 样例输出 22 提示 需要考虑有多轮数据输入的情况！也就是第一个cin或者scanf需要用while来进行循环，例如 while(cin>>...)
#include<iostream> using namespace std; void show(int a[], int len){ for(int i=0; i<len; i++){ cout<<a[i]<<" "; } cout<<endl; } int main(){ int t; while( cin>>t){ int a[t+5]; int ans = 0; for(int i=0; i<t; i++) cin>>a[i]; for(int i=0; i<t-1; i++){ for(int j=i+1; j<t; j++){ if(a[i]>a[j]){ int temp = a[i]; a[i] = a[j]; a[j] = temp; ans++; } // show(a,t); } } cout<<ans<<endl; } return 0; }
E. DS排序–快速排序
题目描述 给出一个数据序列，使用快速排序算法进行从小到大的排序 排序方式：以区间第一个数字为枢轴记录 输出方式：每一步区间排序，都输出整个数组 --程序要求-- 若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio 程序中若include多过一个头文件，不看代码，作0分处理 不允许使用第三方对象或函数实现本题的要求 输入 第一行输入t，表示有t个测试示例 第二行输入n，表示第一个示例有n个数据 第三行输入n个数据，都是正整数，数据之间用空格隔开 以此类推 输出 每组测试数据，输出每趟快排的结果，即每次排好一个数字结果（长度为1的子序列，不用排，不用输出）。不同测试数据间用空行分隔。 样例输入 2 6 111 22 6 444 333 55 8 77 555 33 1 444 77 666 2222 样例输出 55 22 6 111 333 444 6 22 55 111 333 444 6 22 55 111 333 444 6 22 55 111 333 444 1 33 77 555 444 77 666 2222 1 33 77 555 444 77 666 2222 1 33 77 77 444 555 666 2222 1 33 77 77 444 555 666 2222 1 33 77 77 444 555 666 2222 提示
#include<iostream> using namespace std; int length; void show(int *a){ for(int i=0; i<length; i++){ cout<<a[i]<<" "; } cout<<endl; }; void q_sort(int a[], int left, int right){ // left, right 左闭右开， low、high闭区间 if(left >= right-1 ) return; int low = left, high = right-1, center = a[low]; while( low < high ){ while( low<high && a[high] >= center ) high --; a[low] = a[high]; while( low< high && a[low] <= center) low++; a[high] = a[low]; } a[low] = center; show(a); q_sort(a, left, low); q_sort(a, low+1, right ); } int main(){ int step; cin>>step; while(step--){ int t; cin >> t; int *a = new int[t+5]; length = t; for(int i=0; i<t; i++) cin>>a[i]; q_sort( a, 0, t); cout<<endl; } return 0; }
