Page 278 - Bkhargava_-_Grokaem_algoritmy

Ответы к упражнениям 277

Ответ: В виде отсортированного массива. Массивы обеспечивают
произвольный доступ - вы можете мгновенно получить элемент из
середины массива. Со связанными списками это невозможно. Чтобы
получить элемент из середины связанного списка, вам придется начать
с первого элемента и переходить по ссылкам до нужного элемента.

2.4 Пользователи также довольно часто создают новые учетные записи на
Facebook. Предположим, вы решили использовать массив для хране­
ния списка пользователей. Какими недостатками обладает массив для
выполнения вставки? Допустим, вы используете бинарный поиск для
нахождения учетных данных. Что произойдет при добавлении новых
пользователей в массив?

Ответ: Вставка в массив выполняется медленно. Кроме того, если вы
используете бинарный поиск для нахождения имен пользователей,
массив необходимо отсортировать. Предположим, пользователь по
имени Adit В регистрируется на Facebook. Его имя будет вставлено
в конец массива. Следовательно, массив нужно будет сортировать при
каждой вставке нового имени!

2.5 В действительности Facebook не использует ни массив, ни связанный
список для хранения информации о пользователях. Рассмотрим ги­
бридную структуру данных: массив связанных списков. Имеется мас­
сив из 26 элементов. Каждый элемент содержит ссылку на связанный
список. Например, первый элемент массива указывает на связанный
список всех имен пользователей, начинающихся на букву «А~. Второй
элемент указывает на связанный список всех имен пользователей, на­
чинающихся на букву «В~, и т. д.
C6JIJAHHЬIK СПИСОК СО &СЕ.МИ
Г"AZiz3 нADIТ"I :Н"АDА"\ + .. " "s ИМЕНАМИ ПОЛЬJО&АТЕЛЕ~
l - - - - - НА 5УК6У •А•
". "\- ММЕ.НА ПОЛЬ.306ПЕ.ЛЕ.К
.---..~ } НА БУК&У «&•

~
МАССИ&
Предположим, пользователь с именем «Adit в~ регистрируется
в Facebook и вы хотите добавить его в список. Вы обращаетесь к эле­
менту 1 массива, находите связанный список элемента 1 и добавляете

www.trk.kg