chazhao.rar_4 3 2 1_哈希表 查找_有序表查找

#include "Hash.h" #include <iostream> using namespace std; /*******************************************/ /* 哈希函数 */ /*******************************************/ int H(KeyType key, int m) { return key % m; } /*******************************************/ /* 初始化哈希表 */ /*******************************************/ void InitHashTable(HashTable HT) //把散列表HT中的每一单元的关键字key域都置为空标志 { // 初始化散列表 int i ; for (i=0; i<Hash_Max_Size; i++) HT[i].key = NULL; } /*******************************************/ /* 哈希表插入操作 */ /*******************************************/ int Insert(HashTable HT, int m, HashKey x) //向长度为m的散列表HT中插入一个元素x { // 向散列表插入一个元素 int d = H(x.key,m); //可选用任一种合适的构造散列函数的方法来计算散列地址 int temp = d; //用temp变量暂存散列地址 while (HT[d].key != NULL) // 用线性探测法处理冲突 { d = (d+1)%m; if (d == temp) { cout << "散列表的空间已被占满，应重建!\n"; return ERROR; // 返回0表示插入失败 } } HT[d] = x ; //将新元素插入到下标为d的位置，接着返回1表示插入成功 return TRUE; } /*******************************************/ /* 哈希表查找 */ /*******************************************/ int Search(HashTable HT, int m, KeyType k) //从长度为m的散列表HT中查找关键字为K的一个元素 { // 从散列表中查找一个元素 int d = H(k,m); int temp =d; //用于记录（元素）标志 while (HT[d].key != NULL) // 当散列地址中的关键字域不为空则循环 { if(HT[d].key == k) return d; // 查找成功返回下标d else d = (d+1)%m; if(d == temp) return FALSE; // 查找失败返回-1 } return FALSE; } /*******************************************/ /* 打印哈希表 */ /*******************************************/ void PrintHashTable(HashTable HT, int m) { int i ; char c = 15; //输出一个特殊符号，以表示空 cout << "建立的散列表为(若空则用★代替)：" <<endl; for (i=0; i<m ; i++) { if (HT[i].key == NULL) cout << "\t" << c; else cout << "\t" << HT[i].key; } cout <<endl; } /*******************************************/ /* 哈希表 */ /*******************************************/ void Hash() { int n,m,i; HashKey x; //输入关键字 KeyType e; //待查找的关键字 HashTable HT; //哈希表 InitHashTable( HT ); //初始化哈希表 cout << "\n请输入待散列元素的个数n和散列长度m：\n"; do { cin >> n >> m; if(n>m || m>Hash_Max_Size) cout << "输入不符合要求，请重新输入n和m的值："; }while(n>m || m>Hash_Max_Size); cout << "\n请向散列表输入" << n << "个元素的关键字：\n"; for(i=0; i<n; i++) { cin >> x.key; Insert(HT, m, x); //把输入的关键字插入哈希表 } PrintHashTable(HT , m); //输出建立的哈希表 cout << "请输入一个待查找的关键字：\n"; cin >> e; if(Search(HT, m, e) == -1) //查找关键字 cout << "不存在你要查找的元素\n\n"; else cout << "在第" << Search(HT, m, e)+1 << "个位置找到该关键字\n\n"; }