Уровни представления структур данных.

Date: 2015-10-07; view: 550.

Понятие о структуре данного.

Структура данного (СД) – общее свойство информационного объекта с которым взаимодействует та или иная программа. Это общее свойство характеризуется:

1) множеством допустимых значений данной структуры;

2) набором допустимых операций;

3) характером организованности.

Вырожденные (простейшие) структуры данных называются также типами данных.

Различают следующие уровни описания данного:

1) абстрактный (математический) уровень;

2) логический уровень;

3) физический уровень.

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

Любая структура на абстрактном уровне может быть представлена в виде двойки <D,R>, где D – конечное множество элементов, которые могут быть типами данных, либо структурами данных, а R – множество отношений, свойства которого определяют различные типы структур данных на абстрактном уровне.

Основные виды (типы) структур данных:

1) Множество – конечная совокупность элементов, у которой R=Æ.

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

3) Матрица – структура, у которой множество R состоит из двух отношений линейного порядка.

4) Дерево – множество R состоит из одного отношения иерархического порядка.

5) Граф – множество R состоит из одного отношения бинарного порядка.

6) Гиперграф – множество R состоит из двух и более отношений различного порядка.