#include<iostream>
#include<fstream>
using namespace std;
const int M = 4889;
//记录URL信息的类
class URL
{
public:
char url[150]; //内容
int count; //次数
};
//qsort的比较函数
int compare(const void * elem1,const void * elem2)
{
return ((*(URL*)elem1).count - (*(URL*)elem2).count);
}
//散列表类
class hashdict
{
private:
URL* HT; //散列表
int m; //散列表长度
int current; //现有元素数目
int ELFhash(char* K); //字符串散列函数
public:
hashdict(int sz); //构造函数
bool hashinsert(URL elem); //插入函数
int size(); //散列表现有元素数目
void hashsort(); //散列表内部排序
void flush(); //将散列表内的元素输入文件
};
//构造函数
hashdict::hashdict(int sz)
{
m = sz;
current = 0;
HT = new URL[sz]; //动态申请数组
for(int i=0; i<sz; i++)
HT[i].count = 0; //清零
return;
}
//字符串散列函数
int hashdict::ELFhash(char* K)
{
unsigned long g, h=0;
while(*K)
{
h = (h<<4) + *K++;
g = h & 0xF0000000L;
if(g)
h^= g >> 24;
h&=~g;
}
return h % M;
}
//散列表现有元素数目
int hashdict::size()
{
return current;
}
//插入函数
bool hashdict::hashinsert(URL elem)
{
int home;
home = ELFhash(elem.url); //计算字符串的位置
int pos = home;
while(!( HT[pos].count == 0))
{
if(strcmp(HT[pos].url,elem.url) == 0)
{
break;
}
pos++; //线性探查
pos = pos % M;
}
if(HT[pos].count == 0)
{
current++; //如果以前没有该元素，则元素数目+1
strcpy(HT[pos].url, elem.url); //将元素写入散列表
}
HT[pos].count++; //该元素的个数+1
return true;
}
//散列表内部排序
void hashdict::hashsort()
{
qsort(HT, M, sizeof(URL), compare);
return;
}
//将散列表内的元素输入文件
void hashdict::flush()
{
FILE * output;
output = fopen("result.txt","w");
for(int i=0; i<M; i++) //排除排在前面不存在的元素
{
if(HT[i].count != 0)
break;
}
for(; i<M; i++)
{
fprintf(output,"Count:%d url:%s\n",HT[i].count,HT[i].url);
}
fclose(output);
return;
}
int main()
{
URL elem;
hashdict hash(M); //建hash表
FILE* input;
input = fopen("quiz_url.list.txt","r");
if(input == NULL)
{
cout<<"The file do not exist!"<<endl;
return 0;
}
while(1)
{
if((fscanf(input,"%s",elem.url)) == EOF) //判断跳出
break;
hash.hashinsert(elem); //将元素插入hash表
}
hash.hashsort(); //排序
hash.flush(); //输入文件
fclose(input);
cout<<"OK"<<endl; //程序运行结束
return 0;
}
