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

3.5   Резюме

1.   Ключевые выводы

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

2.   Q & A

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

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

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

Q: Длина типа char равна 1 байту?

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

Q: Не является ли двусмысленным утверждение, что структуры данных, реализованные на основе массива, также называются "статическими структурами данных"? Ведь стек тоже поддерживает операции push и pop, а они явно "динамические".

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

Q: При построении стека (очереди) его размер не задается явно, почему же его относят к "статическим структурам данных"?

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

Q: Если метод преобразования из прямого кода в дополнительный - это "сначала инвертировать, затем прибавить 1", то обратное преобразование из дополнительного кода в прямой, по идее, должно быть обратной операцией "сначала вычесть 1, затем инвертировать". Почему же дополнительный код также можно перевести в прямой тем же способом "сначала инвертировать, затем прибавить 1"?

Это связано с тем, что взаимное преобразование прямого и дополнительного кодов по сути является вычислением "дополнения". Сначала дадим определение дополнения: если \(a + b = c\) , то говорят, что \(a\) является дополнением числа \(b\) до \(c\) ; аналогично, \(b\) является дополнением числа \(a\) до \(c\) .

Для двоичного числа длины \(n = 4\) со значением \(0010\) , если рассматривать его как прямой код (не учитывая знаковый бит), то его дополнительный код получается правилом "сначала инвертировать, затем прибавить 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\) , но его можно обобщить на двоичные числа любой длины.

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