Структуры данных

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

- композиция или следования;

- ветвления (альтернатива, если - то - иначе);

- итерация или цикл (с предусловием, с постусловием, с конечным числом повторений).

Циклический алгоритм – это алгоритм, некоторые шаги которого повторяются N-количество раз.

Тело цикла – шаги алгоритма, которые повторяются.

Параметр цикла – величина, от которой зависит число повторений в цикле.

Цикл с предусловием:

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

Цикл с постусловием:

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

Цикл с конечным числом повторений:

Данный цикл также называют циклом «Для» (for). В его заголовке указывается три параметра: начальное значение переменной (от), конечно значение (до) и ее изменение с помощью арифметической операции на каждом «обороте» цикла (шаг).

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

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

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

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

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

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

К примеру, АТД нетипизированного изменяемого списка может быть определён как набор из конструктора и четырёх основных операций:

- операция, проверяющая список на пустоту;

- операция добавления объекта в список;

- операция определения первого (головного) элемента списка;

- операция доступа к списку, состоящему из всех элементов исходного списка, кроме первого.

Дата добавления: 2015-08-27