URL.rar_url

#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; }