hash.cpp

在存储大量数据是节约时间和空间

#include<iostream>
#include<string>
#include<fstream>
using namespace std;


struct node                  //定义3001个结点，每个结点中，word表示字符串长度
							 //count用来计数，*p用来开散列
{
	string word;
	int count;
	node *p;
}a[3001];


int ELFhash(string key)      //哈希函数，来源于书上
{
	unsigned long h=0;
	for(int i=0;i<key.length();i++)
	{
		h=(h<<4)+key[i];
		unsigned long g=h&0xF0000000L;
		if(g)
			h^=g>>24;
		h&=~g;
	}
	return h%3001;
}


int compare(const void *e1,const void *e2)  //qsort中要用到的函数
{
	node *e3=(node *)e1;
	node *e4=(node *)e2;
	return e3->count-e4->count;
}


int main()
{
	for(int i=0;i<3001;i++)              //所有结点初始化
	{
		a[i].count=0;
		a[i].p=NULL;
	}
	int x;                               //记录当前结点哈希函数值
    ifstream infile("quiz_url.list");    //开输入流文件
	ofstream outfile("a.txt");           //开输出流文件
	char temp[120];
	while(!infile.eof())                 //只要文件还没读完
	{
		infile.getline(temp,100);        //输入
		x=ELFhash(temp);                 //计算当前值的哈希函数值
		if(a[x].count==0)                //若没有聚集，则直接加一，并记录
		{
			a[x].word=temp;
			a[x].count++;
		}
		else                             //否则若出现聚集
		{
			if(temp==a[x].word)          //若为重复出现的字符串，则a[x].count++
			{
				a[x].count++;
			}
			else                         //否则，开散列表
			{
				a[x].p=new node;
				a[x].p->count=1;
				a[x].p->word=temp;
			}
		}
	}
	qsort(a,3001,sizeof(a[0]),compare);  //用qsort排序
	int j=1;
	for(i=0;i<3001;i++)                  //输出到文件"a.txt"中
	{
		if(a[i].count!=0)
		outfile<<j++<<"  count:"<<a[i].count<<"     "<<a[i].word<<endl;
	}
	return 0;
}