Грокаем а Иллюстрированное пособие для программистов и любопытствующих

СВЯЗАННЫЙ СПИСОК СО ВСЕМИ
II =4“ADA”| ...Л именами пользователей
-J ¹ —¹ ’ НА БУКВУ «А»
-Ц “BRENDA” I Ч-*.. Тт ИМЕНА ПОЛЬЗОВАТЕЛЕЙ — У НА БУКВУ «6»


“САП-

действительности Facebook не использует ни массив, ни связанный список для хранения информации о пользователях. Рассмотрим ги­бридную структуру данных: массив связанных списков. Имеется мас­сив из 26 элементов. Каждый элемент содержит ссылку на связанный список. Например, первый элемент массива указывает на связанный список всех имен пользователей, начинающихся на букву «А». Второй элемент указывает на связанный список всех имен пользователей, на­чинающихся на букву «В», и т. д.

МАССИВ
Предположим, пользователь с именем «Adit В» регистрируется в Facebook и вы хотите добавить его в список. Вы обращаетесь к эле­менту 1 массива, находите связанный список элемента 1 и добавляете
«Adit В» в конец списка. Теперь предположим, что зарегистрировать нужно пользователя «Zakhir Н». Вы обращаетесь к элементу 26, ко­торый содержит связанный список всех имен, начинающихся с «Z», и проверяете, присутствует ли «Zakhir Н» в этом списке.
Теперь сравните эту гибридную структуру данных с массивами и свя­занными списками. Будет она быстрее или медленнее каждой исход­ной структуры при поиске и вставке? Приводить время выполнения «О-большое» не нужно, просто выберите одно из двух: быстрее или медленнее.
Ответ'. Поиск — медленнее, чем для массивов, и быстрее, чем для связанных списков. Вставка — быстрее, чем для массивов, и с такой же скоростью для связанных списков. Итак, гибридная структура уступа­ет массиву по скорости поиска, но по крайней мере не хуже связанных списков для всего остального. Далее в книге будет рассмотрена другая гибридная структура данных, называемая хеш-таблицей. Она даст не­которое представление о том, как строить сложные структуры данных из более простых.
Что же в действительности использует сервис Facebook? Вероятно, десяток разных баз данных, за которыми стоят разные структуры данных: хеш-таблицы, в-деревья и т. д. Массивы и связанные списки становятся структурными элементами для построения более сложных структур данных.
Глава 3

1. 
   П
   GREET
   NAME: 1 МТюПГ V
   
   редположим, имеется стек вызовов следующего вида:
   

Что можно сказать о текущем состоянии программы на основании этого стека вызовов?
Ответ: Некоторые наблюдения, о которых вы могли бы упомянуть:

• 
  сначала вызывается функция greet для переменной name = maggie;
  
• 
  затем функция greet вызывает функцию greet2 для переменной name = maggie;
  
• 
  на этой стадии функция greet находится в незавершенном, при­остановленном состоянии;
  
• 
  текущим вызовом функции является вызов greet2;
  
• 
  после завершения этого вызова функция greet продолжит выпол­нение.
  

2. 
   Предположим, вы случайно написали рекурсивную функцию, которая бесконечно вызывает саму себя. Как вы уже видели, компьютер вы­деляет память в стеке при каждом вызове функции. А что произойдет со стеком при бесконечном выполнении рекурсии?
   

Ответ-. Стек будет расти бесконечно. Каждой программе выделяется ограниченный объем памяти в стеке. Когда все пространство будет исчерпано (а рано или поздно это произойдет), программа завершится с ошибкой переполнения стека.
Глава 4

1. 
   Напишите код для функции sum (см. выше).
   

Ответ: