请设计一个整型闭散列表,散列函数为除留余数法,处理冲突时的探查方法为线性探查法,其中散列表的长度、除留余数法的模和关键码的个数由键盘输入,再根据输入由键盘输入所有的关键码。分别对三个待查值在散列表中进行查找,如果找到了输出位置,如果没找到,输出“none”并把该待查值插入到散列表中,如果散列表满输出“full”。
输入描述
各个命令以及相关数据的输入格式如下: 第一行输入闭散列表的长度n 第二行输入除留余数法的模m 第三行输入关键码的个数num 第四行输入num个整型关键码 第五行输入三个待查整型值
输出描述
输出三行,每行格式为: 如果找到待查值,输出找到待查值的位置,如果没找到,输出“none”,并将待查值插入到散列表中,如果散列表满,则输出“full”,每个待查值占一行
输入样例
11 11 9 2 6 8 9 13 17 10 12 20 3 7 11
输出样例
none none full
思路:水
通关代码:
#include<iostream>#define MAX 20using namespace std;int Data[MAX] = {0};//散列表int length;//表长int mod;//模int num;//元素个数int Count = 0;int H(int k)//Hash函数
{return k % mod;
}void Insert(int k)//插入函数
{int i, j = H(k);i = j;while (Data[i] != 0){if (Data[i] == k) return;else i = (i + 1) % MAX;}Data[i] = k;Count++;
}bool isFull()
{if (Count == length) return true;return false;
}void Search(int k)//查找函数
{int i, j = H(k);i = j;while (Data[i] != 0){if (Data[i] == k){cout << i;return;}i = (i + 1) % MAX;}if (!isFull()){cout << "none";Insert(k);}elsecout << "full";
}int main()
{cin >> length >> mod >> num;int a[MAX];for (int i = 0; i < length; i++)Data[i] = 0;for (int i = 0; i < num; i++)cin >> a[i];for (int i = 0; i < num; i++)Insert(a[i]);int find[MAX];for (int i = 0; i < 3; i++){cin >> find[i];Search(find[i]);}//for (int i = 0; i <= length; i++)//cout<<endl<<Data[i]<<' ';return 0;
}