hello-algo/ru/docs/chapter_data_structure/summary.md

Резюме

Основные моменты

• Структуры данных можно классифицировать с точки зрения логической структуры и физической структуры. Логическая структура описывает логические отношения между элементами данных, а физическая структура описывает способ хранения данных в памяти компьютера.
• К распространенным логическим структурам относятся линейные, древовидные и сетевые. Обычно мы делим структуры данных на линейные (массивы, связные списки, стеки, очереди) и нелинейные (деревья, графы, кучи) в зависимости от логической структуры. Реализация хеш-таблицы может одновременно включать линейные и нелинейные структуры данных.
• Во время выполнения программы данные хранятся в памяти компьютера. Каждое пространство памяти имеет соответствующий адрес памяти, программа обращается к данным через эти адреса памяти.
• Физическая структура в основном делится на хранение в непрерывном пространстве (массивы) и хранение в разреженном пространстве (связные списки). Все структуры данных реализуются на основе массивов, связных списков или их комбинации.
• Основные типы данных в компьютере включают целые числа byte, short, int, long, числа с плавающей запятой float, double, символы char и логический тип bool. Их диапазон значений зависит от занимаемого объема памяти и способа представления.
• Прямой код, обратный код и дополнительный код -- это три метода кодирования чисел в компьютере, которые могут быть преобразованы друг в друга. Старший бит прямого кода целого числа является знаковым битом, остальные биты представляют значение числа.
• Целые числа хранятся в компьютере в виде дополнительного кода. При представлении в дополнительном коде компьютер может одинаково обрабатывать сложение положительных и отрицательных чисел, не требуя специальных аппаратных схем для операции вычитания, и не существует проблемы неоднозначности положительного и отрицательного нуля.
• Кодирование числа с плавающей запятой состоит из 1 знакового бита, 8 битов экспоненты и 23 битов мантиссы. Благодаря наличию битов экспоненты диапазон значений чисел с плавающей запятой намного больше, чем у целых чисел, ценой чего является потеря точности.
• ASCII -- это самая ранняя кодировка английских символов длиной 1 байт, включающая 127 символов. Кодировка GBK -- это часто используемая китайская кодировка, включающая более 20 тысяч иероглифов. Unicode стремится предоставить полный стандарт набора символов, включающий символы различных языков мира, тем самым решая проблему искажения текста из-за несогласованности методов кодирования символов.
• UTF-8 -- самый популярный метод кодирования Unicode с очень хорошей универсальностью. Это метод кодирования переменной длины с хорошей расширяемостью, эффективно повышающий эффективность использования памяти. UTF-16 и UTF-32 -- это методы кодирования фиксированной длины. При кодировании китайских символов UTF-16 занимает меньше места, чем UTF-8. Такие языки программирования, как Java и C#, по умолчанию используют кодировку UTF-16.

Вопросы и ответы

В: Почему хеш-таблица одновременно включает линейные и нелинейные структуры данных?

В основе хеш-таблицы лежит массив, а для решения коллизий хеширования мы можем использовать «метод цепочек» (об этом будет рассказано в последующей главе «Коллизии хеширования»): каждая ячейка массива указывает на связный список, и когда длина списка превышает определенный порог, он может быть преобразован в дерево (обычно красно-черное дерево).

С точки зрения хранения, в основе хеш-таблицы лежит массив, где каждая ячейка может содержать значение, связный список или дерево. Поэтому хеш-таблица может одновременно включать линейные структуры данных (массивы, связные списки) и нелинейные структуры данных (деревья).

В: Длина типа char составляет 1 байт?

Длина типа char определяется методом кодирования, используемым языком программирования. Например, Java, JavaScript, TypeScript, C# используют кодировку UTF-16 (сохраняют кодовые точки Unicode), поэтому длина типа char составляет 2 байта.

В: Не является ли неоднозначным называть структуры данных, реализованные на основе массивов, «статическими структурами данных»? Стек также может выполнять операции выталкивания и проталкивания, эти операции являются «динамическими».

Стек действительно может реализовывать динамические операции с данными, но структура данных остается «статической» (длина неизменна). Хотя структуры данных на основе массивов могут динамически добавлять или удалять элементы, их емкость фиксирована. Если объем данных превышает предварительно выделенный размер, необходимо создать новый больший массив и скопировать содержимое старого массива в новый.

В: При создании стека (очереди) не указывается его размер, почему они являются «статическими структурами данных»?

В языках программирования высокого уровня нам не нужно вручную указывать начальную емкость стека (очереди), эта работа выполняется автоматически внутри класса. Например, начальная емкость ArrayList в Java обычно составляет 10. Кроме того, операция расширения также реализуется автоматически. Подробнее см. в последующей главе «Списки».

В: Метод преобразования прямого кода в дополнительный -- «сначала инвертировать, затем добавить 1», тогда преобразование дополнительного кода в прямой должно быть обратной операцией «сначала вычесть 1, затем инвертировать», но дополнительный код также можно преобразовать в прямой через «сначала инвертировать, затем добавить 1», почему так?

Это связано с тем, что взаимное преобразование прямого и дополнительного кодов фактически является процессом вычисления «дополнения». Сначала дадим определение дополнения: предположим, что a + b = c, тогда мы называем a дополнением b до c, и наоборот, b является дополнением a до c.

Дано двоичное число 0010 длиной n = 4 бита. Если рассматривать это число как прямой код (не учитывая знаковый бит), то его дополнительный код получается через «сначала инвертировать, затем добавить 1»:

0010 \rightarrow 1101 \rightarrow 1110

Мы обнаружим, что сумма прямого и дополнительного кодов равна 0010 + 1110 = 10000, то есть дополнительный код 1110 является «дополнением» прямого кода 0010 до 10000. Это означает, что вышеупомянутая операция «сначала инвертировать, затем добавить 1» фактически является процессом вычисления дополнения до $10000$.

Тогда каково «дополнение» дополнительного кода 1110 до 10000? Мы по-прежнему можем использовать «сначала инвертировать, затем добавить 1», чтобы получить его:

1110 \rightarrow 0001 \rightarrow 0010

Другими словами, прямой и дополнительный коды являются взаимными дополнениями друг друга до 10000, поэтому «преобразование прямого кода в дополнительный» и «преобразование дополнительного кода в прямой» могут быть выполнены одной и той же операцией (сначала инвертировать, затем добавить 1).

Конечно, мы также можем использовать обратную операцию для получения прямого кода дополнительного кода 1110, то есть «сначала вычесть 1, затем инвертировать»:

1110 \rightarrow 1101 \rightarrow 0010

В итоге, обе операции «сначала инвертировать, затем добавить 1» и «сначала вычесть 1, затем инвертировать» вычисляют дополнение до 10000, они эквивалентны.

По сути, операция «инвертирования» фактически вычисляет дополнение до 1111 (поскольку всегда прямой код + обратный код = 1111); а дополнительный код, полученный добавлением 1 к обратному коду, является дополнением до 10000.

Приведенный выше пример с n = 4 может быть обобщен на двоичные числа любой разрядности.