Структуры данных Классификация структур данных

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

В языках программирования понятие «структуры данных» тесно связано с понятием, "типы данных".

Классификация структур данных

(с точки зрения отведения памяти)

Статические

Динамические

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

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

(по составу)

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

Структуры данных
Статические СД			Динамические СД
Простые типы		Составные типы
Стандартные	Переменные
целочисленные вещественные логические Boolean символьные char	диапазонные перечисляемые	массив array строка string файл file запись record множественный set

При задании типа однозначно определяется:

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

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

• множество допустимых значений, которые может иметь тот или иной объект описываемого типа;

Например, переменная булевого (логического) типа может принимать только два значения: значение true (истина) и значение false (ложь) и никакие другие.

• множество допустимых операций, которые применимы к объекту описываемого типа.

Число различных значений, входящих в тип Т, называется мощностью Т. Мощность задает размер памяти, необходимой для размещения переменной х типа Т.