Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 3.6 Упражнения

## 3.6.1 Вопросы для самопроверки

### 1. Связи между данными в повседневных ситуациях

Для каждого из трех примеров выберите по характеру связей между данными один вариант: «линейная структура», «древовидная структура» или «сетевая структура». Объясните свой выбор.

1. Ученики стоят в ряд, и каждого интересуют только стоящие непосредственно перед ним и за ним;
2. школа организована по уровням «школа → параллель → класс»;
3. городские дороги соединяют множество перекрестков: из одного перекрестка можно попасть в несколько других, а дороги могут образовывать циклы.

Ответ

1. Это линейная структура. Кроме первого и последнего в ряду, каждый ученик соседствует ровно с одним человеком впереди и одним сзади, а связи вытянуты в одну линию.

2. Это древовидная структура. Каждый класс относится к одной параллели, а каждая параллель — к школе; связи образуют уровни сверху вниз.

3. Это сетевая структура. Один перекресток может быть связан с несколькими другими, а дороги могут образовывать циклы, поэтому связи нельзя выстроить в единую последовательность или строгую иерархию.

   Определяя структуру, сначала рассматривайте связи между элементами, а не объем памяти, который они занимают.

### 2. Как сохранить логический порядок в памяти

Логический порядок `A → B → C` можно сохранить в памяти двумя упрощенными способами:

- вариант 1: `A, B, C` размещены в ячейках памяти с номерами `20, 21, 22` соответственно;
- вариант 2: `A, B, C` размещены в ячейках с номерами `20, 7, 31` соответственно, причем `A` хранит расположение `B`, а `B` — расположение `C`.

1. Какой вариант использует хранение в непрерывном, а какой — в разрозненном пространстве памяти?
2. Какой вариант ближе к массиву, а какой — к связному списку?
3. Почему вариант 2 по-прежнему задает логический порядок `A → B → C`, хотя номера ячеек памяти не упорядочены по величине?

Ответ

1. Вариант 1 использует соседние ячейки памяти, поэтому хранение происходит в непрерывном пространстве. Узлы в варианте 2 находятся в разных местах, поэтому они хранятся в разрозненном пространстве.

2. Вариант 1 ближе к массиву, а вариант 2 — к связному списку.

3. Логический порядок задается связями, записанными между узлами, а не величиной номеров ячеек памяти. По адресу, который хранит `A`, можно найти `B`, а затем по адресу из `B` найти `C`, поэтому элементы по-прежнему доступны в порядке `A, B, C`.

   Это также показывает, что логическая и физическая структуры — два разных взгляда на одни и те же данные.

### 3. Типы данных и структура записей о домашних заданиях

Учебная группа записала в порядке рассадки, сдали ли домашнее задание 4 ученика:

`[true, false, true, true]`

1. Какой базовый тип данных подходит для каждого элемента?
2. Какую логическую структуру образуют эти 4 элемента, расположенные в ряд по порядку рассадки?
3. Если затем записывать оценки за задание каждого ученика как `[90, 0, 85, 100]`, изменится «тип содержимого» или «способ организации» данных? Объясните ответ.

Ответ

1. Каждый элемент выражает только «да» или «нет», поэтому подходит логический тип `bool`.

2. Элементы расположены по порядку рассадки и образуют линейную структуру, которую можно хранить в массиве.

3. Изменится тип содержимого: логические значения будут заменены целыми числами. Способ организации не изменится: данные по-прежнему расположены в ряд по порядку рассадки и могут храниться в массиве как линейная структура.

   Базовый тип данных описывает, «что хранится», а структура данных — «как организованы данные».

## 3.6.2 Задачи по программированию

### 1. Число единиц в двоичной записи

Дано неотрицательное целое число `n`. Подсчитайте количество единиц в его двоичной записи.

Используйте побитовые операции. Не преобразовывайте двоичную запись в строку и не применяйте встроенную функцию, которая напрямую подсчитывает единицы.

Подсказки

1. Выражение n & 1 извлекает крайний правый бит n и позволяет проверить, равен ли он 1
2. Сдвиг вправо на один разряд отбрасывает текущий крайний правый бит; в большинстве языков для этого используется оператор >>
3. Реализовав проверку каждого бита со сдвигом вправо, обратите внимание: n & (n - 1) превращает в 0 крайнюю правую единицу в n

LeetCode

##### Оставляйте свои идеи, вопросы и предложения в комментариях