#include<vector> #include<iostream> #define NULLKEY - 32768 using namespace std; class HashTable { public: HashTable(int n); ~HashTable(); void InsertHash(int key);//插入关键字进散列表 int SearchHash(int key);//查找关键字 void Show();//显示散列表 private: int Hash(int key);//散列函数 vector<int> elem;//数据元素 int count;//当前数据元素个数 int m;//散列表长度 }; HashTable::HashTable(int n = 30) :count(0), m(n) { for (int i = 0; i < n; i++) { elem.push_back(NULLKEY); } } HashTable::~HashTable() { } int HashTable::Hash(int key)//散列函数 { return key % m;//除留余数法 } void HashTable::InsertHash(int key)//插入关键字进散列表 { int addr = Hash(key); while (NULLKEY != elem[addr]) { addr = (addr + 1) % key; } elem[addr] = key; count++; } int HashTable::SearchHash(int key)//查找关键字 { int addr = Hash(key); while (elem[addr] != key) { addr = (addr + 1) % m; if (NULLKEY == elem[addr] || Hash(key) == addr) { return -1; } } return addr; } void HashTable::Show()//显示散列表 { for (int i = 0; i < m; i++) { cout << elem[i] << " "; } cout << endl; } int main() { int n, e, val; vector<int> vec; cout << "输入数据元素个数:"; cin >> n; cout << "输入数据元素:" << endl; for (int i = 0; i < n; i++) { cin >> e; vec.push_back(e); } HashTable H(n); for (int i = 0; i < n; i++) H.InsertHash(vec[i]); cout << "散列表:" << endl; H.Show(); cout << "输入要查找的数据元素:"; cin >> val; e = H.SearchHash(val); if (-1 == e) cout << "查找失败" << endl; else cout << "查找的数据元素在散列表中的位置下标:" << e << endl; system("pause"); return 0; }对这个代码进行注释
时间: 2024-04-01 13:32:16 浏览: 80
/*这是一个实现散列表的程序*/
#include<vector> //使用vector动态数组需要包含此头文件
#include<iostream> //使用cin和cout需要包含此头文件
#define NULLKEY -32768 //散列表中空关键字的标志
using namespace std;
class HashTable { //定义散列表类
public:
HashTable(int n); //构造函数,创建一个散列表对象
~HashTable(); //析构函数,释放散列表内存
void InsertHash(int key); //插入关键字进散列表
int SearchHash(int key); //查找关键字
void Show(); //显示散列表
private:
int Hash(int key); //散列函数,用于将关键字映射到散列表上
vector<int> elem; //数据元素
int count; //当前数据元素个数
int m; //散列表长度
};
HashTable::HashTable(int n = 30) :count(0), m(n) { //构造函数实现
for (int i = 0; i < n; i++) { //初始化散列表
elem.push_back(NULLKEY); //将空关键字插入到散列表中
}
}
HashTable::~HashTable() { //析构函数实现
}
int HashTable::Hash(int key) { //散列函数实现
return key % m; //采用除留余数法将关键字映射到散列表上
}
void HashTable::InsertHash(int key) { //插入关键字进散列表实现
int addr = Hash(key); //计算关键字在散列表中的地址
while (NULLKEY != elem[addr]) { //如果地址对应的散列表位置不为空
addr = (addr + 1) % key; //采用线性探测法寻找下一个空位置
}
elem[addr] = key; //将关键字插入到散列表中
count++; //更新当前数据元素个数
}
int HashTable::SearchHash(int key) { //查找关键字实现
int addr = Hash(key); //计算关键字在散列表中的地址
while (elem[addr] != key) { //如果地址对应的散列表位置存储的关键字不是要查找的关键字
addr = (addr + 1) % m; //采用线性探测法寻找下一个位置
if (NULLKEY == elem[addr] || Hash(key) == addr) { //如果遍历到空位置或者回到原点
return -1; //返回查找失败
}
}
return addr; //返回查找成功的地址
}
void HashTable::Show() { //显示散列表实现
for (int i = 0; i < m; i++) { //遍历散列表
cout << elem[i] << " "; //输出每个位置存储的关键字
}
cout << endl; //输出换行
}
int main() { //主函数
int n, e, val; //定义变量n表示数据元素个数,e表示遍历vector动态数组时使用的临时变量,val表示要查找的关键字
vector<int> vec; //定义vector动态数组,用于存储数据元素
cout << "输入数据元素个数:"; //提示用户输入数据元素个数
cin >> n; //读入用户输入的数据元素个数
cout << "输入数据元素:" << endl; //提示用户输入数据元素
for (int i = 0; i < n; i++) { //遍历vector动态数组
cin >> e; //读入用户输入的数据元素
vec.push_back(e); //将数据元素插入到vector动态数组中
}
HashTable H(n); //创建一个散列表对象
for (int i = 0; i < n; i++) H.InsertHash(vec[i]); //将vector动态数组中的数据元素插入到散列表中
cout << "散列表:" << endl; //输出散列表
H.Show(); //调用散列表显示函数进行输出
cout << "输入要查找的数据元素:"; //提示用户输入要查找的数据元素
cin >> val; //读入用户输入的要查找的数据元素
e = H.SearchHash(val); //在散列表中查找关键字
if (-1 == e) //如果查找失败
cout << "查找失败" << endl; //输出查找失败信息
else //如果查找成功
cout << "查找的数据元素在散列表中的位置下标:" << e << endl; //输出查找成功的信息
system("pause"); //暂停程序
return 0; //返回执行成功
} //程序结束
阅读全文