【算法】海量数据处理：有一千万条短信，有重复，以文本形式保存，一行一条，找出重复最少的前10条

有一千万条短信，有重复，以文本形式保存，一行一条，找出重复最少的前10条"/>

【算法】海量数据处理：有一千万条短信，有重复，以文本形式保存，一行一条，找出重复最少的前10条

题目：有一千万条短信，有重复，以文本形式保存，一行一条，找出重复最少的前10条

思路：通过哈希表去重并统计出重复次数后，通过堆调整找出重复次数最少的前10条

参考文章：/，代码有改动。

关于从n（n很大）个数字中查找前k个最小的数的方法，用堆调整的方法，具体参见：

：【数据结构】堆排序

下面给出经过改动的代码，编译是通过的。如果任何地方有什么纰漏之处，敬请指正。

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