0

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

我使用 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;     
}
4

1 回答 1

2

这是您的第一个问题的答案，按频率排序。表中的每个哈希节点都是一个不同的词汇条目。一些哈希到相同的代码（因此您的冲突链），但最终每个唯一条目都有一个 HashNode。要在对现有代码的干扰最小的情况下按频率对它们进行排序，您可以相对轻松地将 qsort() 与指针列表（或您选择的任何其他类型）一起使用。

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

首先，记录所有独特的插入。很简单，只需在分配小节中添加一个计数器：

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

最后，触发 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，ab 或 ba 都可能发生）。

希望这可以帮助。

编辑：更新以向 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
于 2012-10-20T18:43:56.523 回答