Как и все предыдущие задания, это было помечено как легкое. Что ж, это может быть легко, если вы решите ее на Java или любом другом языке, который имеет Map методы, но с C задача усложняется: вам нужно реализовать хеш-таблицу, а это само по себе проблема. Более того, этого недостаточно для прохождения всех тестов, но об этом позже :)

Вот код, который у меня получился (пока):

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    // declaring variables
    long long int n;
    char str[1000];
    
    // creating the structure
    struct phoneBook {
        char name[100];
        long long int number;
    } map[99999];
           
    // getting number of entries and saving the data to the structure
    scanf("%lld", &n);
    for (long long int i = 0; i < n; i++) {
        scanf("%s %lld\n", map[i].name, &map[i].number);
    }
   
    // reading the rest of entries, searching the phonebook, printing out search results
    while (scanf("%s", str) != EOF) {
        long long int counter = 0;
        for (long long int j = 0; j < n; j++) {
            if (!strcmp(str, map[j].name)) {
                printf("%s=%lld\n", map[j].name, map[j].number);
                counter = 1;
                } 
            }
        if (counter != 1) {
                printf("Not found\n");                    
                } 
        }
    return 0;
}

Почти построчное объяснение:

  • Сначала я создал структуру (phoneBook) с двумя членами, именем и номером;
  • Затем я использовал scanf(), чтобы получить количество строк, из которых мне нужно было бы читать и извлекать данные, и еще scanf() внутри цикла for для хранения данных в моем phoneBook;
  • На этом этапе кода я прочитал n строк ввода и создал phoneBook. Затем следует сложная часть: чтение неизвестного количества запросов и возврат либо сохраненной записи, либо Not found. Поскольку количество запросов неизвестно, цикл while, выполняемый до тех пор, пока не будет достигнут конец файла, кажется лучшим вариантом.

Сначала мой while цикл выглядел так:

while (scanf(“%s”, str) != EOF) {
for (long long int j = 0; j < n; j++) {
if (!strcmp(str, map[j].name)) {
printf(“%s=%lld\n”, map[j].name, map[j].number);
}
}
else {
printf(“Not found\n”);
}
}

Это работало не совсем правильно - вывод, хотя и содержал правильные записи, в основном состоял из Not found. Я подозревал, что проблема может быть не в цикле while, а в цикле for, поэтому я применил тестирование с пользовательским вводом и ввел что-то вроде этого:

4
alice 6758586
dina 754646
jane 3647587
kate 34967546
dina
alice
kate
jane

Тестовый прогон подтвердил, что цикл for работает прекрасно - все эти записи были правильно сохранены и распечатаны. Все пошло наперекосяк только тогда, когда я добавил имена, которых не было в списке. Между прочим, в этой задаче особенно удобно тестировать пользовательский ввод!

Я обратился к разделу «Обсуждения» и заметил, что пара (как сообщается, успешных) решений C содержала своего рода счетчик внутри цикла. Я тоже пробовал это, и это сработало:

while (scanf("%s", str) != EOF) {
        int counter = 0;
        for (long long int j = 0; j < n; j++) {
            if (!strcmp(str, map[j].name)) {
                printf("%s=%lld\n", map[j].name, map[j].number);
                counter = 1;
                } 
            }
        if (counter != 1) {
                printf("Not found\n");                    
                } 
        }

Вот как это работает: в начале цикла счетчик устанавливается на 0; если запрашиваемое имя было найдено в телефонной книге, счетчик устанавливается на 1, и результат запроса распечатывается; если, однако, счетчик не изменяется, печатается Not found, и цикл выполняется снова (пока не достигнет конца файла).

Обратите внимание, что в этом фрагменте моего кода что-то немного отличается от окончательной версии: я использую int, а не long long int. Это связано с тем, что, когда я запускал код с образцом тестового примера и своим пользовательским вводом, он более или менее работал, но когда я отправил свой код после успешного запуска с образцом тестового примера, он отказался от нескольких последующих тестовых случаев. Когда я загрузил второй тестовый пример, стало очевидно, что количество записей и запросов просто слишком велико, поэтому я заменил ints на long long ints.

Это помогло избавиться от ошибки сегментации, но теперь те же тестовые примеры показали ошибку тайм-аута. Действительно, если количество записей / запросов слишком велико и записи расположены в случайном порядке, поиск может занять очень много времени, поэтому реализация функции сортировки и, возможно, более эффективной функции поиска должна помочь.

И все это для якобы легкой задачи. Разве программировать на C не весело? :)