题目：有一千万条短信，有重复，以文本形式保存，一行一条，找出重复最少的前10条
思路：通过哈希表去重并统计出重复次数后，通过堆调整找出重复次数最少的前10条
参考文章：http://gengning938.blog.163.com/blog/static/128225381201161994028740/，代码有改动。
关于从n（n很大）个数字中查找前k个最小的数的方法，用堆调整的方法，具体参见：
http://www.oschina.net/code/snippet_180974_6371和我之前的一篇博客：【数据结构】堆排序
下面给出经过改动的代码，编译是通过的。如果任何地方有什么纰漏之处，敬请指正。
#include<iostream> #include<fstream> #include<stdlib.h> #include<malloc.h> using namespace std; const int ERROR=0; struct LinkHash { LinkHash *next; //用来装填短信息的内容 char msg[10]; int count; }; struct SData { char msg[10]; int count; }; //哈希函数，将一条短信息转成0~99的某值：[0,99] = f(短信息) int Hash_Func(char const *p) { int value=0; while(*p!='\0') { value=*p+value; p++; } return value%100; } class CHashTable { private: LinkHash *HashTable[100]; public: CHashTable(); ~CHashTable(); void HashCollision(char const *p); void WriteToFile(); }; CHashTable::CHashTable() { int i; for(i=0;i<100;i++) { HashTable[i]=(LinkHash*)malloc(sizeof(LinkHash)); if(!HashTable[i]) exit(ERROR); //初始化 HashTable[i]->next=NULL; memset(HashTable[i]->msg, 0 , 10); HashTable[i]->count=0; } } CHashTable::~CHashTable() { //释放开辟的内存空间(释放链接表) int i; LinkHash* p,*q; for(i=0; i<100; i++) { p = HashTable[i]; while(p != NULL) { q = p; p = p->next; free(q); } } } void CHashTable::HashCollision(char const *p) { int pos; LinkHash *head,*mobile,*newNode,*last; pos = Hash_Func(p); head = HashTable[pos]; bool flag = false; if(head->count == 0) { strcpy(head->msg,p); head->count++; } else { mobile = head; while(mobile!=NULL) { if(flag==false && strcmp(mobile->msg,p) == 0) { mobile->count++; flag = true; //break;//不用break是为了取得链表尾部指针 } last = mobile; mobile = mobile->next; } if(flag == false) { newNode = (LinkHash *)malloc(sizeof(LinkHash)); if(!newNode) exit(ERROR); newNode->next = NULL; strcpy(newNode->msg,p); newNode->count = 1; last->next = newNode; } } } //将原短信去重后统计出重复次数后写入result.txt文件中 void CHashTable::WriteToFile() { int i; ofstream fout; LinkHash *p; fout.open("result.txt");//应写明正确路径 for(i=0; i<100; i++) { p=HashTable[i]; while(p) { fout<<p->msg<<" "<<p->count<<endl; p=p->next; } } fout.clear(); fout.close(); } //以下几个函数为完成查找n个数中（n很大）最小的前k个数 //最大堆调整 void swap(SData *a, SData *b) { SData temp; temp = *a; *a = *b; *b = temp; } void HeapAdjust(SData *a,int i,int size) //调整堆 { int lchild=2*i; //i的左孩子节点序号 int rchild=2*i+1; //i的右孩子节点序号 int max=i; //临时变量 if(i<=size/2) //如果i不是叶节点就不用进行调整 { if(lchild<=size&&a[lchild].count>a[max].count) { max=lchild; } if(rchild<=size&&a[rchild].count>a[max].count) { max=rchild; } if(max!=i) { swap(&a[i],&a[max]); HeapAdjust(a,max,size); //避免调整之后以max为父节点的子树不是堆 } } } void BuildHeap(SData *a,int size) //建立堆 { int i; for(i=size/2;i>=1;i--) //非叶节点最大序号值为size/2 { HeapAdjust(a,i,size); } } int main() { int i; const int k=10; char instr[10]; SData Array[k+1]; ifstream fin; ofstream fout; SData InData; /*fout.open("MessageData.txt"); for(i=0;i<10000000;i++)//随机生成重复的短信，短信简化为三个字母 { for(j=0;j<3;j++) str[j]='A'+rand()%10; str[3]='\0'; fout<<str<<"\r\n"; } fout.close();*/ CHashTable cht=CHashTable(); //MessageData.txt为存放海量信息的文本 fin.open("MessageData.txt"); if(fin.is_open()) { while(fin>>instr)//将原短信文档读入并通过hash表处理 { cht.HashCollision(instr); } } fin.close(); fin.clear(); //该函数将短信息以一定格式（如：我爱米老鼠 3453）写在result.txt中。 cht.WriteToFile(); //从result.txt中读取数据 fin.open("result.txt"); if(fin.is_open()) { for(i=1;i<=k;i++)//先读取前k个 { fin>>Array[i].msg>>Array[i].count; } cout<<"建堆:"<<endl; BuildHeap(Array,k); fin>>InData.msg>>InData.count; //继续读取文件中后面的数 while(fin.fail()==false)//如果没有到文件尾 { if(InData.count<Array[1].count)//如果读取的数小于现有的堆的堆顶元素，则交换 { Array[1]=InData; HeapAdjust(Array,1,k);//调整为堆 } fin>>InData.msg>>InData.count; } } //输出前k个数 for(i=1;i<=k;i++) cout<<Array[i].msg<<" ------ "<<Array[i].count<<endl; return 0; }
上面是求重复次数最少的前10条，如果要求重复次数最多的前10条则是建立一个小顶堆。