Линейные и нелинейные структуры

При разработке программного обеспечения сложность реализации и качество работы программ существенно зависит от правильного выбора структур данных.

Различают линейные и нелинейные структуры.

К линейным структурам относятся:

§ массив;

§ таблица,

§ стек.

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

Одномерный массив (линейная таблица) - массив, элементами которого являются атомарные переменные, например, одномерный массив вещественных чисел (рис.4.2.1). Элементы массива записаны в ячейках таблицы. Над ячейками проставлены индексы.

	-3			-2		-6

Рис. 4.2.1. Одномерный массив

Список допустимых действий над массивом:

o создать массив;

o присвоить значение элементу массива;

o запросить значение элемента массива.

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

					-2

Рис. 4.2.2. Двумерный массив

Изображенный на рис. 4.2.2 двумерный массив имеет n=3 строк и m=5 столбцов.

К элементам массива можно обращаться в произвольном порядке, используя значения индексов. Действия над элементами массива определяются типом этих элементов.

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

В программировании применяется сравнительно большое количество таблиц различного назначения. Особой разновидностью таблиц являются так называемые хеш-таблицы.

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

§ добавления новой пары;

§ поиска;

§ удаления пары по ключу.

Простейшим примером хеш-функций может служить контрольная сумма.

Контрольная сумма — некоторое значение, рассчитанное из последовательности данных путём применения определённого алгоритма преобразования.

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

Хеш –таблицы используются для ускорения поиска данных в сложных структурах.

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

Стек (англ. stack — стопка) — структура данных с методом доступа к элементам LIFO (англ. Last In — First Out, «последним пришел — первым вышел»).

Начало последовательности называется дном стека, конец последовательности, в который производится добавление элементов и их исключение - вершиной стека.

Переменная, которая указывает на последний элемент последовательности в вершине стека - указатель стека.

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

Добавление элемента, называемое также проталкиванием, возможно только в вершину стека, при этом добавленный элемент становится первым сверху.

Выталкивание элемента возможно только из вершины стека, при этом второй сверху элемент становится верхним.

В некоторых случаях стек еще называют магазином - по аналогии с магазином в огнестрельном оружии – патроны последовательно проталкиваются в магазин при заряжании, а стрельба начинается с патрона, заряженного последним.

Вход Выход

Рис. 4.2.3. Стек

О́чередь — структура данных с порядком доступа к элементам FIFO (First In — First Out) - «первый пришёл — первый вышел»).

Добавление элемента возможно лишь в конец очереди, выборка — только из начала очереди.

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

Рис. 4.2.4. Очередь.

К нелинейным структурам относятся:

§ связные списки;

§ графы;

§ деревья.

С вя́зный спи́сок — структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки («связки») на следующее и/или предыдущее поле.

В отличие от массива список обладает структурной гибкостью: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями.

Информация в списках представлена множество узлов (элементов). Каждый узел состоит из одной или нескольких последовательных ячеек оперативной памяти, разделенных на именуемые части, называемые полями. Адрес узла является адресом первого слова в узле. Адрес узла называют связью, указателем, стрелкой, ссылкой на этот узел.

Рис. 4.2.5. Связный список

Дата добавления: 2014-12-10