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

Массивы

Мы все играли или знакомы с игрой в бильярд. Неудивительно, что 8ball pool скачали более 18 миллионов раз!! В игре в бильярд много 16 шаров, 15 с номерами от 1 до 15 и 1 белый шар. Эти мячи обычно поставляются в коробке для мячей, в которую можно поместить 16 мячей.

Что-то вроде этого.

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

Как он будет класть мячи обратно?

  • Он поднимает каждый шар один за другим с бильярдного стола.
  • Читает число на мяче.
  • Читает число в поле.
  • Кладет мяч в лунку с соответствующим номером. (он действительно хороший человек)

Фу!! Это была непростая задача. Давайте сделаем ретроспективу того, что мы видели выше.

  • Коробка для пула вмещает 16 шаров. Назовем это «n».
  • Каждое последовательное число записывается одно за другим непрерывно. Для простоты считайте, что все отверстия расположены на прямой линии.
  • Логика помещения шаров обратно в коробку отображается тем же номером, который написан на коробке. Определим это отображение fn как map(x). Здесь map(x) = x для x ≤16
  • Мы можем положить меньше или равное количество шаров вместимость ящика. Хотя в коробке по-прежнему 16 отверстий.

Эти сценарии реального мира, приведенные выше, заставили ученых-компьютерщиков задуматься о том, как заставить компьютер думать так же, как делает наш разум, не думая? Итак, строительные блоки для изготовления компьютерного робота. Страшно!!

Они определили так называемые массивы, которые являются набором элементов, хранящихся в смежных областях памяти. Идея состоит в том, чтобы хранить несколько элементов одного типа вместе.

Мы резервируем непрерывную ячейку памяти емкостью n и назначаем эту ячейку памяти переменной в языке программирования. Если мы не назначим это переменной, эта зарезервированная ячейка памяти будет потеряна для нашей программы.

Затем мы определили множество похожих структур реального мира вокруг нас и объединили их в семейство DataStructure. Теперь у Array счастливая семья. Ну наконец то!!

Мы обсудим другие структуры данных в следующей серии.

Осторожно: ниже слишком много технических деталей!!

Что мы подразумеваем под непрерывными ячейками памяти?

Чтобы понять это, сначала нам нужно посмотреть, что такое память в компьютерном мире.

Наш компьютер использует оперативную память для выполнения основных функций. Каждый из них имеет определенный размер, например 4 ГБ, 8 ГБ, 256 ГБ и т. Д. Эти числа количественно определяют объем памяти, который есть в компьютерной системе.

С какой основной единицей памяти связаны вышеуказанные размеры?
Пример: 4 килобайта, 8 гигабайт. Байт состоит из 8 бит (аналогично массиву). Основной единицей памяти является бит.

Мы, люди, имеем дело с числами от 0 до 9, также известными как десятичные числа (деци — 10 чисел). Каждое второе число является комбинацией этих чисел. С другой стороны, компьютер имеет дело с числами от 0 до 1, также известными как двоичные числа (bi-2 числа).

Таким образом, каждый бит может содержать либо 0, либо 1. Это означает, что 8-битный байт может содержать что угодно от 00000000 до 11111111. При преобразовании двоичного числа в десятичное оно преобразуется в число от 0 до 255. (Читайте о преобразовании двоичного числа в десятичное). Всего существует 2⁸ комбинаций для байта. (либо 0, либо 1 в любом месте).

Итак, если вы хотите сохранить массив целых чисел. Сколько памяти вам нужно?
В компьютерных системах диапазон целых чисел указывается от -2 147 483 648 до 2 147 483 647. Общее число в этом диапазоне составляет 42 949 672,96, что составляет 2³².

2³² = 2⁸ (1 байт)* 2⁸ (1 байт)* 2⁸ (1 байт) * 2⁸ (1 байт)

Для хранения целого числа требуется память объемом 4 байта. Когда мы определяем целое число, мы резервируем 4 байта памяти для хранения любого возможного целочисленного значения.

Возвращаясь к нашей проблеме, что мы подразумеваем под ячейками памяти, помните, мы говорили о том, что байт представляет собой последовательный набор из 8 битов в памяти. Рассмотрим набор байтов как непрерывный набор ячеек памяти.

Представьте всю оперативную память как непрерывный набор байтов (для простоты). Когда мы определяем массив емкостью n, наша компьютерная программа резервирует n блоков памяти по 4 байта. Напомним, что все эти блоки являются непрерывными ячейками памяти.

Упражнение: попробуйте написать программу, которая выделяет массив памяти, равный размеру ОЗУ вашего компьютера.