首页 > 代码库 > TopK代码
TopK代码
Hash表
#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;}
TopK代码
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。