#ifndef _HASH_H#define _HASH_H#include<string.h>#include<stdio.h>class HashTable{public:    HashTable(unsigned int size);    ~HashTable();    int get(const char *key,unsigned int *value);    int set(const char *key,unsigned int value);    int push(const char *key);    int MAXTopK(unsigned int k);    int MINTopK(unsigned int k);private:    struct Node    {        char *key;        unsigned int value;        Node *next;        Node(const char *str,unsigned int v)        {            key = new char[strlen(str)+1];            strcpy(key,str);            value = v;            next = NULL;        }        ~Node()        {            delete[] key;        }    };    int Init();    int Destroy();    int Hash(const char *key,unsigned int *hashcode);    int ClearChain(Node *Head);    Node **TableHead;    unsigned int TableSize;    char **kWords;};#endif

#include"Hash.h"#include"Heap.h"HashTable::HashTable(unsigned int size){    TableHead = NULL;    TableSize = size;    Init();}HashTable::~HashTable(){    Destroy();}int HashTable::Init(){    if(TableHead != NULL)    {        printf("HashTable has been initialized\n");        return -1;    }    TableHead = new Node*[TableSize];    for(unsigned int i=0;i<TableSize;i++)    {        TableHead[i]=NULL;    }    return 0;}int HashTable::Destroy(){    for(unsigned int i=0;i<TableSize;i++)    {        if(ClearChain(TableHead[i]) < 0)        {            printf("ClearChain error\n");            return -1;        }    }    delete[] TableHead;    TableHead = NULL;    return 0;}int HashTable::get(const char *key,unsigned int *value){    unsigned int hashcode=0;    if(Hash(key,&hashcode) < 0)    {        printf("generate hashcode error");        return -1;    }    unsigned int index = hashcode%TableSize;    Node *p = TableHead[index];    while(p!=NULL && (strcmp(key,p->key)!=0))    {        p=p->next;    }    if(p!=NULL)    {        *value = http://www.mamicode.com/p->value;    }    else    {        *value = http://www.mamicode.com/0;    }    return 0;}int HashTable::set(const char *key,unsigned int value){    unsigned int hashcode=0;    if(Hash(key,&hashcode) < 0)    {        printf("generate hashcode error");        return -1;    }    unsigned int index = hashcode%TableSize;    Node *p = TableHead[index];    while(p!=NULL && (strcmp(key,p->key)!=0))    {        p=p->next;    }    if(p!=NULL)    {        p->value =http://www.mamicode.com/ value;    }    else    {        Node *q = TableHead[index];        TableHead[index] = new Node(key,value);        TableHead[index]->next = q;    }    return 0;}int HashTable::push(const char *key){    unsigned int hashcode=0;    if(Hash(key,&hashcode) < 0)    {        printf("generate hashcode error");        return -1;    }    unsigned int index = hashcode%TableSize;    Node *p = TableHead[index];    while(p!=NULL && (strcmp(key,p->key)!=0))    {        p=p->next;    }    if(p!=NULL)    {        p->value = http://www.mamicode.com/p->value+1;    }    else    {        Node *q = TableHead[index];        TableHead[index] = new Node(key,1);        TableHead[index]->next = q;    }    return 0;}int HashTable::Hash(const char *str,unsigned int *hashcode){    *hashcode = 0;    unsigned int hashseed = 131;    while(*str != ‘\0‘)    {        *hashcode += *hashcode*hashseed + *str;        str++;    }    (*hashcode) & 0x7FFFFFFF;    return 0;}int HashTable::ClearChain(Node *Head){    Node *p=Head;    Node *q;    while(p != NULL)    {        q=p->next;        delete p;        p=q;    }    Head = NULL;    return 0;}int HashTable::MAXTopK(unsigned int k){    Pair *heap = new Pair[k];    for(unsigned int i=0;i<TableSize;i++)    {        Node *p=TableHead[i];        while(p!=NULL)        {            if(p->value > heap[0].cnt)            {                heap[0]=Pair(p->key,p->value);                minHeapIFY(0,heap,k);            }            p=p->next;        }    }    printf("MAX TopK:\n");    for(unsigned int j=0;j<k;j++)    {        printf("%s:%d\n",heap[j].word,heap[j].cnt);    }    delete[] heap;    return 0;}int HashTable::MINTopK(unsigned int k){    Pair *heap = new Pair[k];    int s=k;    for(unsigned int i=0;i<TableSize;i++)    {        Node *p=TableHead[i];        while(p!=NULL)        {            if(s>0)            {                s--;                heap[s]=Pair(p->key,p->value);            }            if(s == 0)            {                s--;                buildMaxHeap(heap,k);            }            else            {                if(p->value < heap[0].cnt)                {                    heap[0]=Pair(p->key,p->value);                    maxHeapIFY(0,heap,k);                }            }            p=p->next;        }    }    printf("MIN TopK:\n");    for(unsigned int j=0;j<k;j++)    {        printf("%s:%d\n",heap[j].word,heap[j].cnt);    }    delete[] heap;    return 0;}

#ifndef _HEAP_H#define _HEAP_H#include<string.h>struct Pair{    char *word;    unsigned int cnt;    Pair()    {        word = NULL;        cnt = 0;    }    Pair(const char *str,unsigned int num)    {        word = new char[strlen(str)+1];        strcpy(word,str);        cnt = num;    }    ~Pair()    {        delete[] word;        word=NULL;    }    const Pair& operator=(const Pair& p)    {        delete[] word;        if(p.word != NULL)        {            word = new char[strlen(p.word)+1];            strcpy(word,p.word);        }        else        {            word = NULL;        }        cnt = p.cnt;        return *this;    }};unsigned int Parent(unsigned int i);unsigned int Left(unsigned int i);unsigned int Right(unsigned int i);void maxHeapIFY(unsigned int i,Pair *p,unsigned int len);void minHeapIFY(unsigned int i,Pair *p,unsigned int len);void buildMaxHeap(Pair *p,unsigned int len);void bulidMinHeap(Pair *p,unsigned int len);#endif

#include"Heap.h"unsigned int Parent(unsigned int i){    return (i-1)>>1;}unsigned int Left(unsigned int i){    return (i<<1)+1;}unsigned int Right(unsigned int i){    return (i<<1)+2;}void maxHeapIFY(unsigned int i,Pair *p,unsigned int len){    if(i>=len)    {        return;    }    unsigned int largest = i;    unsigned int leftidx = Left(i);    if(leftidx<len && p[i].cnt<p[leftidx].cnt)    {        largest = leftidx;    }    unsigned int rightidx = Right(i);    if(rightidx<len && p[largest].cnt<p[rightidx].cnt)    {        largest = rightidx;    }    if(largest != i)    {        Pair temp(p[i].word,p[i].cnt);        p[i] = p[largest];        p[largest]=temp;        maxHeapIFY(largest,p,len);    }}void minHeapIFY(unsigned int i,Pair *p,unsigned int len){    if(i>=len)    {        return;    }    unsigned int smallest = i;    unsigned int leftidx = Left(i);    if(leftidx<len && p[i].cnt>p[leftidx].cnt)    {        smallest = leftidx;    }    unsigned int rightidx = Right(i);    if(rightidx<len && p[smallest].cnt>p[rightidx].cnt)    {        smallest = rightidx;    }    if(smallest != i)    {        Pair temp(p[i].word,p[i].cnt);        p[i] = p[smallest];        p[smallest]=temp;        maxHeapIFY(smallest,p,len);    }}void buildMaxHeap(Pair *p,unsigned int len){    for(int i=len/2-1;i>=0;i--)    {        maxHeapIFY(i,p,len);    }}void buildMinHeap(Pair *p,unsigned int len){    for(int i=len/2-1;i>=0;i--)    {        minHeapIFY(i,p,len);    }}

#include<stdio.h>#include"Hash.h"int main(){    char *A[]={"hello","world","spicy","hot","delete","great","spicy","great","great","hello","hot","hello"};    unsigned int len=sizeof(A)/sizeof(char*);    HashTable oTable(len);        for(unsigned int i=0;i<len;i++)    {        if(oTable.push(A[i])<0)        {            printf("push error\n");            return -1;        }    }    for(unsigned int i=0;i<len;i++)    {        unsigned int cnt;        if(oTable.get(A[i],&cnt)<0)        {            printf("get error\n");            return -1;        }        printf("%s:%d\n",A[i],cnt);    }    oTable.MAXTopK(3);    oTable.MINTopK(3);    return 0;}