时间戳

首页 > 解决方案 > 如何在C中对哈希表进行排序

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

问题描述

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

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

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

使用以下哈希函数计算索引：组成type字符串的每个字符在转换为 后求和unsigned int，然后该函数返回该总和以 2 乘以数组中的成员数为模。

当一个新Object的被输入时（程序会先提示它type，然后是它val），它的散列位置被计算并且可能发生以下三种情况之一：

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

填完map后，需要降序排序val，遇到两个Object相同val字段的s时，需要按字典序排序。

最后，需要打印表格的前 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

查看hashmap的结构，不用排序，可以使用这段代码

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，然后打印它的typeand val，并且还将打印Object相同哈希计算位置中的所有 s （因此列表中第一个之后的那些）。

感谢任何会回应的人！

标签： carrayslinked-listhashtable

解决方案

看起来我设法找到了一种方法来完成这项工作。我通过将数据展平为一个数组，然后对该数组进行排序，找到了一个可行的解决方案。我基本上将所有元素复制到一个数组中，因此我将链表移开，然后调用qsort该数组。

代码

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

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

int cmpfun(const void* a, const void* b) { // used by qsort
    Object** x = (Object **) a;
    Object** y = (Object **) b;

    if ((*x)->val > (*y)->val)
        return -1;
    if ((*x)->val < (*y)->val)
        return 1;

    if (strcmp((*x)->type, (*y)->type) > 0) // vals were equal, compare types
        return 1;
    return -1;
}

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, int *objCount) {
    if(*lPtr == NULL) {
        *lPtr = newNode(type, val); // list is empty, append new element
        *objCount = *objCount + 1;
        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;
        *objCount = *objCount + 1;
        return;
    }

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

void flatten(Object **input, int n, Object **output) { // scans through the hashtable and copies the data to an array
    size_t j = 0;

    for(size_t i = 0; i < n; i++) {
        if(input[i] != NULL) {
            output[j++] = input[i];

            Object *nextChild = input[i]->nextPtr;
            while(nextChild != NULL) { // copy all the nodes of the list in the i-th position of the original array
                output[j++] = nextChild;
                nextChild = nextChild->nextPtr;
            }
        }
    }
}

int main() {
    int numObjects;
    int distinctObjs = 0;

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

    char thisType[100];
    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, &distinctObjs); // insert according to defined insertion rules
    }

    Object **flattenedDictionary = malloc(sizeof(Object *) * distinctObjs);
    if(flattenedDictionary == NULL) return EXIT_FAILURE;

    for(size_t i = 0; i < distinctObjs; i++) {
        flattenedDictionary[i] = malloc(sizeof(Object)); // allocate single rows
        if(flattenedDictionary[i] == NULL) return EXIT_FAILURE;
    }

    flatten(dictionary, numObjects*2, flattenedDictionary);

    qsort(flattenedDictionary, distinctObjs, sizeof(Object*), cmpfun);

    if(distinctObjs > 15) distinctObjs = 15; // If there are less than 15 distinct objects, printing the first 15 means printing the whole array

    for(size_t i = 0; i < distinctObjs; i++) {
        printf("%s\n", flattenedDictionary[i]->type);
    }

    return EXIT_SUCCESS;
}

推荐阅读