如何在C中对哈希表进行排序

Question

所以我有一个struct的哈希表（称为Object），该哈希表使用链接列表来处理冲突。该结构具有：

1. 一个名为int的val字段
2. 一个名为char[]的type字段
3. 指向另一个名为struct的*nextPtr的指针

我的程序需要获取用户要输入的Object的数量，分配Object的列表数组，并获取该输入成员的数量。

使用以下哈希函数计算索引：组成type字符串的每个字符在强制转换为unsigned int之后求和，然后该函数以模数的两倍返回该总和。]

当输入新的Object（程序将首先提示输入其type，然后提示其val）时，将计算其哈希位置，并且可能发生以下三种情况之一：

1. 如果该位置的链表中不包含与一个输入具有相同Object的type，则Object插入列表的开头
2. 如果该位置的链表包含与一个输入具有相同Object属性的type，并且该位置的输入val大于Object的输入，则val Object的字段用新值更新-
3. 否则，不执行任何操作。

[填满地图后，需要按val对其进行递减排序，并且当遇到具有相同Object字段的两个val时，需要按字典顺序对其进行排序。

最后，需要打印表的前15个元素，或者，如果少于15个元素，则将打印所有数组。

问题是我不确定如何对哈希图进行排序。从字面上看，这是我第一次与他们打交道。我已经做了一些研究，但找不到答案。我不能仅仅对数组进行排序，因为每个成员本身就是一个列表。

下面您可以找到我到目前为止编写的代码以及输入/预期输出的示例。字符串是意大利语单词，希望它不是问题，因为含义无关紧要。

代码：

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

typedef struct obj {
    char type[20];
    int val;
    struct obj *nextPtr;
} Object;


int hash(char a[], int mod) {
    mod *= 2;

    int sum = 0;

    for(size_t i = 0; i < strlen(a); i++) {
        sum += (unsigned int) a[i];
    }

    return sum % mod;
}

Object *newNode(char *type, int val) {
    Object *newPtr = malloc(sizeof(Object));
    if(newPtr == NULL) exit(EXIT_FAILURE);

    strcpy(newPtr->type, type);
    newPtr->val = val;
    newPtr->nextPtr = NULL;

    return newPtr;
}

void hashedInsert(Object **lPtr, char *type, int val) {
    if(*lPtr == NULL) {
        *lPtr = newNode(type, val); // list is empty, append new element
        return;
    }
    if(strcmp((*lPtr)->type, type)) { // list doesn't contain the input element, insert it at top
        Object *newPtr = newNode(type, val);
        newPtr->nextPtr = *lPtr;
        *lPtr = newPtr;
        return;
    }

    if(val > (*lPtr)->val) // update val if input val is greater than the existing one
        (*lPtr)->val = val;
}

int main() {
    int numObjects;

    scanf("%d", &numObjects); // get number of objects

    Object **dictionary = malloc(sizeof(Object*) * 2 * numObjects); // allocate memory for dictionary
    if(dictionary == NULL) return EXIT_FAILURE;

    for(size_t i = 0; i < (2*numObjects); i++) {
        dictionary[i] = malloc(sizeof(Object)); // allocate single rows
        if(dictionary[i] == NULL) return EXIT_FAILURE;

        dictionary[i] = NULL; // all lists are initialized as empty
    }

    char thisType[20];
    int thisVal, thisHashed;

    for(size_t i = 0; i < numObjects; i++) {
        while(getchar() != '\n');
        scanf("%s", thisType); // get object type field
        scanf("%d", &thisVal); // get object val field

        thisHashed = hash(thisType, numObjects); // calculate position of insertion using hash function

        hashedInsert(&(dictionary[thisHashed]), thisType, thisVal); // insert according to defined insertion rules
    }

    // HOW DO I SORT THE MAP???

    for(size_t i = 0; i < 15; i++) {
        if(dictionary[i] == NULL) break;
        else printf("%s\n", dictionary[i]->type);
    }

    return EXIT_SUCCESS;
}
示例输入/输出：

input: (first line is the number of objects)
21
Frigorifero
30
Frigorifero
60
Telefono
50
Asciugamano
10
Libro
5
Libro
100
Tovaglia
70
Computer
120
Scarpe
160
Ventilatore
1
Bilancia
1
Cestino
1
Tazza
1
Cuscino
1
Trolley
1
Appendiabiti
1
Termometro
1
Penna
1
Matita
1
Orologio
1
Abat-jour
1


--
output:

Scarpe
Computer
Libro
Tovaglia
Frigorifero
Telefono
Asciugamano
Abat-jour
Appendiabiti
Bilancia
Cestino
Cuscino
Matita
Orologio
Penna
要查看哈希图的结构而不进行排序，可以使用此代码

for(size_t i = 0; i < numObjects*2; i++) {
        if(dictionary[i] == NULL) printf("NULL\n");
        else {
         printf("(%d) %s - %d\n", hash(dictionary[i]->type, numObjects), dictionary[i]->type, dictionary[i]->val);
         Object *currPtr = dictionary[i]->nextPtr;
         while(currPtr != NULL) {
            printf("\t (%d) %s - %d\n", hash(currPtr->type, numObjects), currPtr->type, currPtr->val);
            currPtr = currPtr->nextPtr;
         }
        }
    }
它将先打印Object的哈希计算位置，然后打印其type和val，并且还将在相同的哈希计算位置打印所有Object（因此，第一个之后列表中的一个）。

谢谢您的回应！

因此，我有一个结构的哈希表（称为对象），该表使用链接列表来处理冲突。该结构具有：一个名为val的int字段和一个名为type的char []字段，该指针指向另一个名为* ...

Answer 1

你们中的大多数人都评论了这个问题的细节，几乎没有人试图回答我唯一的问题。我确实知道哈希图和排序是一种怪异的混合，但这是赋值文本要求我实现的。这是我的大学在2016年让学生进行的考试，如果当时我参加考试，我很可能会专注于实施解决方案，而不是认为这是一个愚蠢的问题。