c++ 建立哈希表
新人。。刚注册。。。你们不要笑话我。。。非常基础的数据结构，建立一个简单的哈希表
采取除留余数法构造哈希表，采用链地址法处理冲突
#include<iostream>
#include<fstream>
#include<map>
#define MOD 11
#define SIZE 11
using namespace std;
struct ElemType{
string name;
double score;
ElemType *next;
};
struct HashTable{
ElemType *elem;
int count;
int sizeindex;
};
map<int,int> hash_tc; //建立num与key关系
int hash(string name)
{
int mod=0;
if(name!="")
mod=toascii(name+name+name+name)%MOD;
return mod;
}
void create(HashTable & HT)
{
ifstream fin("name.txt"); //从name.txt中读取
int count;
fin>>count; //读取count
HT.count=count;
HT.sizeindex=SIZE;
HT.elem=new ElemType;
//初始化
for(int i=0;i<HT.sizeindex;i++)
{
HT.elem.name="";
HT.elem.next=NULL;
}
for(int i=0;i<count;i++)
{
ElemType e;
fin>>e.name;
int searchn=1;
int mod=hash(e.name);
ElemType *p=&HT.elem;
while(p->name!="")
{
searchn++;
if(p->next==NULL)
{
p->next=new ElemType;
p->next->next=NULL;
p->next->name="";
}
p=p->next;
}
p->name.assign(e.name);
hash_tc=searchn;
}
}
int jc(int x)
{
int y=x;
while(x--)
y+=x;
return y;
}
float average_searchlength(const HashTable & HT)
{
float x=0;
for(map<int,int>::iterator it=hash_tc.begin();it!=hash_tc.end();it++)
{
//cout<<it->first<<":"<<it->second<<endl;
x+=jc(it->second);
}
return x/HT.count;
}
void search(HashTable & HT,string name)
{
int mod=hash(name);
if(name==HT.elem.name) cout<<"在第"<<mod<<"行"<<"第1位";
else
{
int i=1;
ElemType *p=&HT.elem;
while(p->name!=name)
{
i++;
p=p->next;
if(p==NULL)
{
i=0;
break;
}
}
if(i) cout<<"在第"<<mod<<"行"<<"第"<<i<<"位";
else cout<<"不在该哈希表中";
}
}
void print(HashTable & HT) //输出hash表
{
for(int i=0;i<HT.sizeindex;i++)
{
cout<<i<<" ";
ElemType *p = &HT.elem;
int mod=hash(p->name);
int j=hash_tc;
while(j--)
{
cout<<p->name<<" ";
p=p->next;
}
cout<<endl;
}
}
int main()
{
HashTable HT;
create(HT);
cout<<"输出hash表为：\n";
print(HT);
cout<<"平均查找长度为："<<average_searchlength(HT);
cout<<"\n请输入要查询的姓名";
string name;
cin>>name;
cout<<name;
search(HT,name);
return 0;
}
运行时需要另外一个 name.txt 文件，记录要录入的名字
格式如下：
//name.txt
10
caddf
chvfdv
lnhngg
lsfbr
nsghsh
nrtsnr
agdaew
sdvadf
sfgbs
afbadfb
页:
[1]