c - 哈希表 - 使用 qsort 排序结构

Question

好吧，很抱歉提出了另一个问题，但最后一个问题变得不知所措和困惑。 所以我正在制作一个哈希表，它从文件( token )中插入单词，插入它们后我需要对它们进行排序。程序模板已给出，唯一不完整的函数是:insert_ht()、clear_ht() 和compare。尽管我已经使用比较进行了大量有关 qsort 的搜索，但该程序不会对频率(每个单词插入的次数)进行排序。我希望它们从最高到最低排序。

这里是代码:“请注意，除了 insert_ht() 、clear_ht() 和 Compare 之外，我不应该更改任何函数

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

#define HTABLE_SIZ 1001
#define MAX_LINE_SIZ 1024

/* Hash Table */
typedef struct node* link;
struct node { char *token; int freq; link next; };

link htable[HTABLE_SIZ] = { NULL }; /* Table of lists (#buckets) */
int size = 0; /* Size (number of elements) of hash table */

unsigned int hash (char *tok );
void insert_ht (char *data);
void clear_ht ( );
void print_ht ( );

void Process(FILE *fp);


int main(int argc, char *argv[])
{
    int i;
    FILE *fp;
    printf("prin tin for \n");
    for (i=1; i < argc; i++)
    {
        printf("prin tin fopen \n");
        fp = fopen(argv[i],"r");
        if (NULL == fp)
        {
            fprintf(stderr,"Problem opening file: %s\n",argv[i]);
            continue;
        }
        printf("prin tin process \n");
    Process(fp);
    fclose(fp);
    }
    print_ht();
    //clear_ht();
    return 0;
}


void Process(FILE *fp)
{
    const char *seperators = " ?!'\";,.:+-*&%(){}[]<>\\\t\n";

    char line[MAX_LINE_SIZ];
    char *s;
    while((fgets(line,MAX_LINE_SIZ, fp)) != NULL)
    {
        for (s=strtok(line,seperators); s; s=strtok(NULL,seperators)){
            printf("prin tin insert %s \n",s);
            insert_ht(s);
        }
            
        }
    }
    
/* Hash Function */
unsigned int hash(char *tok)
{
    printf("bike stin hash \n");
    unsigned int hv = 0;
    while (*tok)
        hv = (hv << 4) | toupper(*tok++);
    printf("VGAINEIIIIIIIIIIIIII %d \n",hv);
    return hv % HTABLE_SIZ;
}



void insert_ht(char *token)
{
    printf("bike stin insert %s \n",token);
    unsigned int hashval = hash(token);
    struct node *new_list;

    if (htable[hashval]==NULL){
        printf("mesa stin prwti if %u %s \n",hashval,token);
        //token = strdup(token);
        new_list = malloc(sizeof(link));
        new_list->token = strdup(token) ;
        new_list->freq = 1;
        new_list->next = htable[hashval];
        htable[hashval] = new_list;
        size++;
        
    }else {
        htable[hashval]->freq++;
    }
    printf("ta evale epitixws \n");
    
}

void clear_ht()
{
    int i;
    
    
    
    
    for(i=0;  i<HTABLE_SIZ; i++) {
        
        while(htable[i]->token!=NULL) {
            
            htable[i]->token=NULL;
            htable[i]->freq=NULL;
            free(htable[i]);
        }
    }

  
}


int compare(const void *elem1, const void *elem2)
{
    const struct node *p1 = elem1;
    const struct node *p2 = elem2;
    if (p1->freq > p2->freq)
        return(+1);
    else if (p1->freq < p2->freq)
        return(-1);
    else
        return(0);
}
void print_ht()
{
    int i, j=0;
    link l, *vector = (link*) malloc(sizeof(link)*size);
    
    for (i=0; i < HTABLE_SIZ; i++)
        for (l=htable[i]; l; l=l->next)
            vector[j++] = l;
        
    qsort(vector,size,sizeof(link),compare);
    for (i=0; i < size; i++)
        printf("%-50s\t%7d\n",vector[i]->token,vector[i]->freq);
    free(vector);
} 

Answer 1

我找到了解决方案。显然由于某种原因我的 compare 函数是错误的。 我仍然不明白为什么，但这是正确的，希望其他人会发现这篇文章有帮助!

int compare(const void *elem1, const void *elem2)
{
    
     return (*(link*)elem2)->freq - (*(link*)elem1)->freq;
}