Итак, у меня есть таблица ha sh struct s (называемая Object), которая использует связанные списки для обработки коллизий. Структура имеет:
-
int поле с именем val - a
char[] поле с именем type - указатель на другой
struct с именем *nextPtr
Моя программа должна получить число Object с, которое пользователь собирается ввести, выделить массив списков Object с и получить это количество элементов ввода .
Индекс рассчитывается с использованием следующей функции ha sh: каждый символ, составляющий строку type, суммируется после приведения к unsigned int, затем функция возвращает эту сумму по модулю в 2 раза больше числа элементов в массиве.
Когда вводится новый Object (программа сначала запросит type, затем val), вычисляется его хешированная позиция, и одна из трех вещей может случается:
- , если цепочечный список в этой позиции не содержит
Object, который имеет тот же type, что и один вход, то Object вставляется в начало списка - , если связанный список в этой позиции содержит
Object с тем же type атрибут как один вход, и вход val больше, чем у Object в этой позиции, тогда поле val этого Object обновляется новым значением - - в противном случае никакие действия не выполняются.
После заполнения карты ее необходимо отсортировать по убыванию на val, а при обнаружении двух Object с одним и тем же полем val, их нужно отсортировать лексикографически.
Наконец, необходимо распечатать первые 15 элементов таблицы или, если имеется менее 15 элементов, распечатать весь массив.
Проблема в том, что я не уверен, как сортировать карту ха sh. Это буквально первый раз, когда я имею дело с ними. Я провел некоторое исследование, но не могу найти ответ. Я не могу просто отсортировать массив, потому что каждый член - это сам список.
Ниже вы можете найти код, который я написал до сих пор, и пример ввода / ожидаемого вывода. Строки - итальянские слова, надеюсь, это не проблема, поскольку значение не имеет значения.
Код:
#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;
}
}
}
. Он выведет вычисленную в ha sh позицию Object, затем ее type и val, и также напечатает все Object s в той же самой вычисленной позиции ha sh (поэтому те, которые следуют за первым, находящимся в списке).
Спасибо всем, кто ответит !