Перейти к содержанию

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

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