哈希表排序和執行時間

Question

我編寫了一個程序來使用哈希表計算頻率字數，但我不知道如何對它進行排序。

我使用struct來存儲值和計數。

我的哈希碼生成函數正在使用模塊，我的哈希表正在使用鏈表。

1.我的問題是如何按頻率對它們進行排序？

2.我想知道爲什麼我的打印執行時間總是爲零，但我檢查了很多時間。錯誤的方式在哪裏？

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
#include <time.h> 
#include <ctype.h> 

#define HASHSIZE 29989 
#define FACTOR 31 
#define VOCABULARYSIZE 30 
typedef struct HashNode HashNode; 
struct HashNode{ 
    char* voc;//vocabulary 
    int freq;//frequency 
    struct HashNode *next;//pointed to the same hashcode 
          //but actually are different numbers 
}; 

HashNode *HashTable[HASHSIZE] = {NULL,0,NULL};//an array of pointers 

unsigned int HashCode(const char *pVoc){//generate hashcode 
    unsigned int index = 0; 
    int n = strlen(pVoc); 
    int i = 0; 
    for(; i < n; i ++) 
     index = FACTOR*index + pVoc[i]; 
    return index % HASHSIZE; 
} 

void InsertVocabulary(const char *pVoc){//insert vocabulary to hash table 
    HashNode *ptr; 
    unsigned int index = HashCode(pVoc); 
    for(ptr = HashTable[index]; ptr != NULL; ptr = ptr -> next){//search if already exist 
     if(!strcmp (pVoc, ptr -> voc)){ 
      (ptr->freq)++; 
      return;   
     }   
    } 
    ptr = (HashNode*)malloc(sizeof(HashNode));//if doesn't exist, create it 
    ptr -> freq = 1; 
    ptr -> voc = (char*)malloc(strlen(pVoc)+1); 
    strcpy(ptr -> voc, pVoc); 
    ptr -> next = HashTable[index]; 
    HashTable[index] = ptr; 
} 

void ReadVocabularyTOHashTable(const char *path){ 
    FILE *pFile; 
    char buffer[VOCABULARYSIZE]; 
    pFile = fopen(path, "r");//open file for read 
    if(pFile == NULL) 
     perror("Fail to Read!\n");//error message 
    char ch; 
    int i =0; 
    do{ 
     ch = fgetc(pFile); 
     if(isalpha(ch)) 
      buffer[i++] = tolower(ch);//all convert to lowercase     
     else{ 
      buffer[i] = '\0';//c-style string 
      i = 0; 
      if(!isalpha(buffer[0])) 
       continue;//blank line 
      else //printf("%s\n",buffer); 
       InsertVocabulary(buffer); 
     } 
    }while(ch != EOF); 
    fclose(pFile); 
} 

void WriteVocabularyTOHashTable(const char *path){ 
    FILE *pFile; 
    pFile = fopen(path, "w"); 
    if(pFile == NULL) 
     perror("Fail to Write\n"); 
    int i = 0; 
    for(; i < HASHSIZE; i++){ 
     HashNode *ptr = HashTable[i]; 
     for(; ptr != NULL; ptr = ptr -> next){ 
      fprintf(pFile, "Vocabulary:%s,Count:%d\n", ptr -> voc, ptr -> freq); 
      if(ptr -> next == NULL) 
       fprintf(pFile,"\n"); 
     } 
    } 
    fclose(pFile); 
} 

int main(void){ 
    time_t start, end; 
    time(&start); 
    ReadVocabularyTOHashTable("test.txt"); 
    WriteVocabularyTOHashTable("result.txt"); 
    time(&end); 
    double diff = difftime(end,start); 
    printf("%.21f seconds.\n", diff); 
    system("pause"); 
    return 0;  
} 

Answer 1

這是對您的第一個問題的答案，按頻率排序。表中的每個哈希節點都是一個不同的詞彙表項。一些哈希到相同的代碼（因此你的碰撞鏈），但最終你有一個HashNode每個條目獨特的條目。按照頻率對它們進行排序，並最小化對現有代碼的干擾，您可以相對容易地將qsort（）與指針列表（或任何其他類型的選擇）一起使用。

注意：最有效的有效的這樣做的方法是在vocab插入過程中維護排序的鏈接列表，您可能需要考慮這一點。這段代碼假設你已經有了一個哈希表，並且需要按照從高到低的順序排列頻率。

首先，保持所有獨特插入的運行計數。夠簡單了，只需添加一個計數器，以您的分配款：

gVocabCount++; // increment with each unique entry. 
ptr = (HashNode*)malloc(sizeof(HashNode));//if doesn't exist, create it 
ptr -> freq = 1; 
ptr -> voc = (char*)malloc(strlen(pVoc)+1); 
strcpy(ptr -> voc, pVoc); 
ptr -> next = HashTable[index]; 
HashTable[index] = ptr; 

下一頁分配指針的列表HashNodes一樣大，你的總獨特的詞彙計數。然後遍歷整個散列表（包括衝突鏈），並將每個節點放入此列表中的一個插槽中。該列表更好是大小爲您的總節點數相同或者你做錯了什麼：

HashNode **nodeList = malloc(gVocabCount * sizeof(HashNode*)); 

int i; 
int idx = 0; 
for (i=0;i<HASHSIZE;++i) 
{ 
    HashNode* p = HashTable[i]; 
    while (p) 
    { 
     nodeList[idx++] = p; 
     p = p->next; 
    } 
} 

所以現在我們都唯一的節點指針列表。我們需要一個比較函數來發送到qsort（）。我們希望最大號碼的項目位於列表的頭部。

int compare_nodeptr(void* left, void* right) 
{ 
    return (*(HashNode**)right)->freq - (*(HashNode**)left)->freq; 
} 

最後，用fire qsort（）對你的指針列表進行排序。

qsort(nodeList, gVocabCount, sizeof(HashNode*), compare_nodeptr); 

HashNode指針的節點列表陣列將所有按降序排序頻率的節點：

for (i=0; i<gVocabCount; ++i) 
    printf("Vocabulary:%s,Count:%d\n", nodeList[i]->voc, nodeList[i]->freq); 

最後，不要忘記釋放名單：

free(nodeList); 

由於我在開始時說過，最有效的方法是使用一個已排序的鏈接列表來提取遞增的值（按定義，所有新條目都可以結束）並運行插入排序滑回到正確的地方。最後，這個列表看起來實際上與上面的代碼會產生相同的結果（類似於計數順序不能承受，即a-> freq = 5和b-> freq = 5，可能發生a-b或b-a）。

希望這會有所幫助。

編輯：更新以顯示OP的是什麼輸出排序的數據的寫入功能可能看起來像一個想法：

static int compare_nodeptr(const void* left, const void* right) 
{ 
    return (*(const HashNode**)right)->freq - (*(const HashNode**)left)->freq; 
} 

void WriteVocabularyTOHashTable(const char *path) 
{ 
    HashNode **nodeList = NULL; 
    size_t i=0; 
    size_t idx = 0; 

    FILE* pFile = fopen(path, "w"); 
    if(pFile == NULL) 
    { 
     perror("Fail to Write\n"); 
     return; 
    } 

    nodeList = malloc(gVocabCount * sizeof(HashNode*)); 
    for (i=0,idx=0;i<HASHSIZE;++i) 
    { 
     HashNode* p = HashTable[i]; 
     while (p) 
     { 
      nodeList[idx++] = p; 
      p = p->next; 
     } 
    } 

    // send to qsort() 
    qsort(nodeList, idx, sizeof(HashNode*), compare_nodeptr); 

    for(i=0; i < idx; i++) 
     fprintf(pFile, "Vocabulary:%s,Count:%d\n", nodeList[i]->voc, nodeList[i]->freq); 

    fflush(pFile); 
    fclose(pFile); 
    free(nodeList); 
} 

類似的東西，反正。從OP的測試文件來看，這些是輸出的前幾行：

Vocabulary:the, Count:912 
Vocabulary:of, Count:414 
Vocabulary:to, Count:396 
Vocabulary:a, Count:388 
Vocabulary:that, Count:260 
Vocabulary:in, Count:258 
Vocabulary:and, Count:221 
Vocabulary:is, Count:220 
Vocabulary:it, Count:215 
Vocabulary:unix, Count:176 
Vocabulary:for, Count:142 
Vocabulary:as, Count:121 
Vocabulary:on, Count:111 
Vocabulary:you, Count:107 
Vocabulary:user, Count:102 
Vocabulary:s, Count:102