Классификации структур данных
Данные в памяти компьютера представляются в виде последовательности битов. Последовательности битов недостаточно структурированы, что затрудняет их практическое использование. Поэтому на практике применяются структуры данных.
Структурой данных называется множество элементов данных и внутренних связей между ними.
Существуют простые и интегрированные структуры данных. Простые структуры данных сводятся к битам и организуются непосредственно из битов. К простым структурам относятся:
- числовые;
- битовые;
- символьные;
- логические;
- указатели.
Интегрированные структуры данных организуются из простых и других интегрированных структур.
Следует различать физическую и логическую структуру данных. Когда говорят о физической структуре простых типов, то под этим понимают их размер и способ размещения битов в памяти. С точки зрения логической структуры простой тип является неделимой элементарной единицей.
Изменчивостью структуры называется изменение числа элементов и связей между ними.
В соответсвии с признаком изменчивости структуры делятся на
- Статические ( векотр, массив, множество, запись, таблица);
- Динамические (стек, очередь, строка, линейные связанные списки, разветвленные связанные списки, графы, деревья.).
Элементы в структуре могут быть упорядоченными и неупорядоченными. В соответствии с этим признаком структуры делятся на
- Нелинейные( многосвязный список, граф, дерево);
- Линейные с последовательным распределением (вектор, строка, массив, стек, очередь);
- Линейные с произвольным связным распределением (односвязный, и двусвязный список).
Простые структуры и типы данных
Простые структуры данных называют также примитивами или базовыми структурами. В языках программирования простые структуры данных представлены простыми типами данных. В различных языках программирования набор типов данных несколько отличается, но имеются некоторые общие принципы.
Целый тип используется для представления количества дискретных объектов. Целые числа могут быть беззнаковыми или отрицательными. Внутреннее представление целого числа может занимать 1, 2 или 4 байта.
Вещественные числа представляются в виде формата с плавающей точкой. Число с плавающей точкой представляется с помощью двух целый чисел – порядка и матиссы, а также знака.
В случае двоичной системы счисления B=2.
Десятичный тип поддерживают не все языки программирования. Число такого типа представляется в виде m десятичных цифр из которых d цифр находятся справа от десятичной точки.
Для случаев, когда нужно работать с отдельными двоичными разрядами числа, предусмотрен битовый тип данных. Данные в нем представляются набором битов, объединенных в байты или слова. Все операции с битовым типом предполагают обращение к каждому биту по отдельности.
Переменная логического типа может принимать одно из двух значений: истина или ложь. Для хранения переменной логического типа нужен один байт памяти. При этому значение «ложь» кодируется нулевым значением байта, а значение «истина» любым отличным от нулевого значением.
Символьный тип позволяет представить данные в виде последовательности символов некоторого заранее предопределенного множества. Каждый символ множества хранится в памяти в виде последовательности битов. Соответствие символов и таких последовательностей называется кодировкой. Различные кодировки представляют символы в виде битовых последовательностей различной длины.
Указатель представляет собой переменную, значением которой является адрес ячейки памяти. Таким образом, указатель ссылается на некий блок данных, указывая его первую ячейку.
Примеры статических структур
Вектор или одномерный массив – структура данных, содержащая фиксированное число элементов одинакового простого типа. При этом каждый элемент имеет свой уникальный индекс.
Для того чтобы обратиться к элементу нужно использовать имя массива и индекс элемента. В памяти массивы размещаются я ячейках, расположенных одна за другой.
Пусть дан массив с именем A.
Тогда элемент А[3] равен 30.
Двумерный массив – это массив, каждый элемент которого сам является одномерным массивом.
В двумерном массиве у каждого элемента есть два индекса.
Записи (хеш-массивы, ассоциативные массивы) – это массивы, которые индексируются не натуральными числами, а строками.
Индекс элемента в таком массиве называется ключом. Для обращения к элементу используется имя массива и индекс.
Пусть дан хеш-массив с именем B.
Тогда элемент массива B[‘овощ’] равен ‘огурец’.
Примеры динамических структур
Для динамических структур память отводится «на ходу» в процессе выполнения программы. Для работы с динамическими типами данных в разных языках программирования широко используются указатели. Сами указатели имеют статический тип.
Стек представляет собой вектор, в котором каждый следующий элемент адресуется указателем на текущий элемент. На рисунках показано последовательное добавление элементов в стек и последовательное извлечение.
Для того чтобы извлечь элемент, нужно сначала последовательно извлечь все элементы, добавленные после него. Элемент, добавленный первым, можно извлечь только в самую последнюю очередь.
Очередь также динамическая структура, которая отличается от стека наличием двух указателей: на первый и последний элемент очереди. Новые элементы записываются вслед за последним записанным элементом. А выборка элементов начинается с первого. При таком алгоритме первым можно получить тот элемент, который был добавлен первым.
