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

Структурой данных является реализация понятия множества элементов определенного типа. Под реализацией понимается способ хранения данных. Вместе со способом хранения задается набор операций (=алгоритмов) по добавлению, поиску, удалению элементов множества.

Вектор.

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

Создание исполнителя вектор предполагает наличие следующих функций

Ø создать вектор длины n

Ø положить элемент в вектор по индексу i

Ø взять элемент из вектора по индексу i

Ø уничтожить вектор

При использовании массивов для реализации структуры данных вектор, создание/уничтожение объекта происходит в соответствующие моменты автоматически. Если же этим процессом надо управлять, то следует использовать функции malloc() / free().

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

#ifndef N

#define N 100

#endif

int Array[N];

Если константа N не определена, то ее значение полагается равным 100. Далее создается массив из N элементов. У большинства компиляторов значение константы препроцессора можно передать через ключ ` D ’, например, для компилятора gcc это будет выглядеть так:

gcc –DN=200 prog.c

В получившейся программе с именем./a.out везде вместо идентификатора N будет подставляться 200.

Стек.

Стеком называется структура данных, организованная по принципу LIFO – last-in, first-out, т.е. элемент, попавшим в множество последним, должен первым его покинуть. При практическом использовании часто налагается ограничение на длину стека, т.е. требуется, чтобы количество элементов не превосходило N для некоторого целого N.

Создание исполнителя стек предполагает наличие следующих функций

Ø инициализация

Ø добавление элемента на вершину стека

Ø взятие/извлечение элемента с вершины стека

Ø проверка: пуст ли стек?

Ø очистка стека

Стек можно реализовать на базе массива или (в языке С) это можно сделать на базе указателей.

Стек. Реализация 1.

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

int stack[100], i0=0;

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

Стек. Реализация 2.

Для группировки различных переменных в один объект (например, чтобы впоследствии, так или иначе, передавать этот объект в функции за один прием) в языке С следует использовать структуры. Например, все данные, относящиеся к стеку можно поместить в структуру struct SStack:

Дата добавления: 2015-10-30