c - 哈希表排序和执行时间

Question

我编写了一个程序来使用哈希表来计算频率单词数，但我不知道如何对其进行排序。

我使用结构来存储值和计数。

我的哈希码生成函数使用模块，我的哈希表通过链表使用。

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() 和指针列表(或您选择的任何其他类型)。

注意:最有效的方法是在词汇插入期间维护一个排序的链表，您可能需要考虑这一点。此代码假设您已经填充了一个哈希表，并且需要按照从高到低的排序顺序获取频率。

首先，对所有唯一插入进行持续统计。很简单，只需在分配部分添加一个计数器即可:

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;

接下来分配一个指向 HashNode 的指针列表，其大小与您的唯一词汇总数一样大。然后遍历整个哈希表，包括冲突链，并将每个节点放入该列表中的一个槽中。该列表最好与您的总节点数相同，否则您做错了什么:

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

最后，触发 qsort() 对指针列表进行排序。

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

HashNode 指针的 nodeList 数组将按频率降序排列所有节点:

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展示输出排序数据的Write函数可能是什么样子:

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