Лекция: Дайте характеристику структуры данных. Назовите классы структур данных и их отличительные особенности (ТП)

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

Статические структуры данных: вектор, массив, запись, таблицы.

Вектор – конечное упорядоченное множество простых данных или скаляров одного и того же типа. Между элементами вектора существуют единственные отношения следования.

Массив – вектор, каждый элемент которого вектор В свою очередь элементы вектора “вектора массива” могут быть вектором (3-х и более мерные массивы). Точным является скалярное определение массива: к-мерным массивом называется конечное упорядоченное множество (к-1) мерных массивов, все элементы которых принадлежат одному и тому же типу. При к=1 получаем вектор.

Запись – конечное упорядоченное множество элементов, характеризующихся различным типом данных. Элементы записи – поля.

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

Полустатические структуры данных — это последовательные линейные списки с переменной длиной, ограниченной фиксированной максимальной величиной и с ограниченным доступом.

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

Очередь – такой последовательный список с переменной длиной, включение элементов в который происходит с одной стороны, а исключение с другой стороны списка.

Особенности динамических структур данных: Непостоянство, непредсказуемость размера динамической структуры. Размер — это число элементов структуры в процессе ее обработки. Число элементов динамической структуры может изменяться от 0 до некоторого значения, определяемого спецификой задачи или доступным размером машинной памяти. Отсутствие физической смежности элементов структуры в физической памяти ЭВМ. Логическая последовательность элементов структуры задается в явном виде с помощью одного или нескольких указателей или связок, хранящихся в самих элементах. Следовательно, память, занимаемая динамической структурой не является непрерывной и может быть хаотически разбросана в области памяти. Часто динамические структуры физически представляются в форме связных списков.

Билет 7