#include<iostream> #include<string> #include<fstream> using namespace std;
const int HashMaxSize = 350; //hash表大小 const int ItemsAmount = 425; //数据数量
void Input(string data[]) { ifstream hashdata("e:\\data.txt"); //打开data.txt for(int i=0; i<ItemsAmount; i++) { hashdata>>data[i]; } }
int Hash(string data,int m) //hashing函数 { unsigned int h=0; //类加变量 for(int i=0; i<data.length(); i++) { h<<=3; //循环一次移3位 h+=(int)data[i]; //把data[i]的int值累加到h上 } return h%m; }
struct LNode{ //单结点结构 string data; LNode* next; };
class HashList { private: LNode* HT[HashMaxSize]; //指针数组
public: void InitHashList(); //初始化hash表 int Insert(HashList &hl,string data[]); //插入数据 };
void HashList::InitHashList() { for(int i=0; i<HashMaxSize; i++) HT[i]=NULL; //把每个指针数组的头结点都赋初值 }
int HashList::Insert(HashList &hl,string data[]) { int key[ItemsAmount]; for(int i=0; i<ItemsAmount; i++) { key[i] = Hash(data[i],HashMaxSize); LNode* p=new LNode; if(p==NULL) return 0; p->data=data[i]; p->next=HT[key[i]]; HT[key[i]]=p; } return 1; }
void main() { HashList hl; //实例化一个hash表 hl.InitHashList(); //初始化
string data[ItemsAmount]; //定义读文件储存的string Input(data); //把data.txt的数据传给data数组变量 if(hl.Insert(hl,data)==0) //从data插入到hash exit(1); //若失败就退出程序 }
di=1,2,3...m-1,称线性探测再散列
再哈希法