Как и все предыдущие задания, это было помечено как легкое. Что ж, это может быть легко, если вы решите ее на 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
. Это связано с тем, что, когда я запускал код с образцом тестового примера и своим пользовательским вводом, он более или менее работал, но когда я отправил свой код после успешного запуска с образцом тестового примера, он отказался от нескольких последующих тестовых случаев. Когда я загрузил второй тестовый пример, стало очевидно, что количество записей и запросов просто слишком велико, поэтому я заменил int
s на long long int
s.
Это помогло избавиться от ошибки сегментации, но теперь те же тестовые примеры показали ошибку тайм-аута. Действительно, если количество записей / запросов слишком велико и записи расположены в случайном порядке, поиск может занять очень много времени, поэтому реализация функции сортировки и, возможно, более эффективной функции поиска должна помочь.
И все это для якобы легкой задачи. Разве программировать на C не весело? :)