В этой статье мы представим основные термины и классификацию простейших структур и типов данных, расскажем про их особенности и нюансы применения. Также приведем примеры статических и динамических структур.
Классификации
Вряд ли кто-нибудь решится спорить с тем, что в памяти компьютера данные (data) представлены в виде последовательности битов. Эти последовательности структурированы недостаточно, что затрудняет их применение на практике. Именно поэтому широко используются специальные структуры данных.
Структурой данных можно назвать некое количество элементов, которые имеют между собой внутренние связи. Существуют как простые, так и интегрированные структуры данных. Простые организуются из битов, вот их примеры:
— числовые;
— символьные;
— битовые;
— логические;
— указатели.
Интегрированные организуются с помощью простых и других интегрированных структур. Также структуры бывают физические и логические.
Немаловажно знать и такой термин, как изменчивость структуры — речь идет об изменении количества элементов и связей между ними. Учитывая понятие изменчивости, можно разделить структуры на статические и динамические. Статические структуры данных мы все хорошо знаем — из основных можно вспомнить массив, множество, вектор, запись, таблицу. Программистам хорошо известны и динамические структуры данных (три наиболее популярные — очередь, стек, списки).
Как уже было сказано выше, структура состоит из элементов данных. Эти элементы бывают как упорядоченными, так и неупорядоченными. С учетом этого признака, структуры данных можно разделить на следующие группы:
— нелинейные (к примеру, многосвязные списки, графы, деревья с их корневыми узлами, потомками и т. д.);
— линейные с последовательным распределением (это вектор, массив, строка, очередь, стек);
— линейные, но уже с произвольным связным распределением (это односвязные и двусвязные списки).
Простейшие структуры и основные типы
Такие конструкции называют примитивами либо базовыми структурами данных. К примеру, в языках программирования они представлены простыми типами данных. В зависимости от языка набор типов может отличаться, но эти различия не очень существенны, поэтому можно говорить о наличии неких общих принципов.
Первый тип — целочисленный (целый тип), который применяется для обозначения целых чисел (int, integer). Из школьного курса математики мы знаем, что целые числа бывают отрицательными либо беззнаковыми. Во внутреннем машинном представлении целое число может занимать 1, 2 либо 4 байта.
Второй тип— вещественный. Он уже имеют вид числа с плавающей точкой. Такое число представляется посредством двух целых чисел – матиссы и порядка, плюс знака.
Третье — десятичный тип (decimal). Его поддерживает не каждый язык программирования. К примеру, такой тип есть в C# — он имеет разрядность 128 бит и может представлять числовые значения в пределах от 1Е-28 до 7,9Е+28. Применяется в финансовых расчетах.
Если предполагается работа с отдельными двоичными числовыми разрядами, существует битовый тип. Здесь данные — это набор битов, которые объединены в байты либо слова. При выполнении операций предполагается обращение к каждому биту отдельно.
Идем дальше. Переменная, имеющая логический тип, способна принимать одно из 2-х значений: либо истину, либо ложь. Для хранения такой переменной требуется 1 байт памяти. False кодируется нулевым значением байта, True — любым значением, отличным от нуля.
Символьный тип дает возможность представлять данные в виде последовательности символов какого-нибудь определенного заранее множества. Каждый символ хранится в памяти в качестве последовательности битов. Соответствие символов и последовательностей называют кодировкой. Разные кодировки представляют символы в форме битовых последовательностей разной длины.
Указатель — это переменная, ее значение — адрес ячейки памяти. В результате указатель ссылается на какой-нибудь блок данных и указывает на его первую ячейку.
Примеры статических структур данных
Вектор либо одномерный массив – структура, содержащая определенное количество элементов простого типа. У каждого элемента — свой уникальный индекс. Для обращения к элементу используют имя массива, а также индекс элемента. В памяти компьютера массивы размещаются я ячейках, причем эти ячейки располагаются одна за другой.
В двумерном массиве каждый элемент массива сам будет являться одномерным массивом. В результате у элемента существуют не один, а 2 индекса.
Записи (ассоциативные массивы или хэш-массивы) представляют собой массивы, индексируемые строками, а не натуральными числами. Индекс компонента здесь называют ключом.
Примеры динамических структур данных
В этом случае объем памяти не фиксируется заранее, а определяется «на ходу» в процессе исполнения программы. Чтобы работать с динамическими типами, во многих языках программирования предусмотрены указатели, причем сами по себе они имеют статический тип.
Яркий пример — стек. Это, по сути, вектор, где каждый следующий компонент адресуется указателем на текущий компонент. Ниже рассмотрено последовательное добавление компонентов в стек, а также последовательное извлечение. Стек организован по принципу LIFO (last in — first out).
Нельзя не вспомнить и про очередь — динамическую структуру, отличающуюся от стека наличием 2-х указателей. Эти указатели показывают на 1-й и последний компоненты очереди. Очередь организована по принципу FIFO (first in, first out).
Если хотите узнать про структуры данных подробнее, обратите внимание на следующую статью.
Источник: https://spravochnick.ru/bazy_dannyh/predstavlenie_dannyh_v_pamyati_kompyutera/tipy_i_struktury_dannyh/ .
