Фундаментальные структуры данных. Массивы, стеки, очереди

Фундаментальные структуры данных

Массивы, Стеки, Очереди

Определения

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

Определения

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

Пример. Массив (вектор)

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

Линейные структуры данных

• Массивы
• Стеки
• Очереди
• Деки
• Линейные списки

Стек (stack)

Стек – линейная структура данных, в которой все вставки и удаления элементов выполняются на одном конце, называемом вершиной стека. Стеки также иногда называют «магазинами», а в англоязычной литературе для обозначения стека еще используется аббревиатура LIFO (Last In First Out – последний вошел – первый вышел). Примеры. 1. Рожок автомата Калашникова. 2. Стопка подносов в столовой.

Стек (stack)

АДТ STACK обычно использует следующие операции: PUSH (S, x) – вставляет элемент x в вершину стека S. POP (S) – удаляет элемент из вершины стека S. EMPTY (S) – проверяет является ли стек S пустым. TOP (S) – показывает элемент в вершине стека S (без удаления). MAKENULL (S) – делает стек S пустым.

Стек (stack)

Реализация стека с помощью статического массива (векторная память). #define MAX 100 // Размер стека int tos = 0; // Индекс вершины стека double stack [MAX]; // Стек void push (double f) { if (tos < MAX) stack[tos++] = f; else { printf(“Стек полон\n”); exit (1); } }

Стек (stack)

double pop (void) { if (tos > 0) return stack[--tos]; else { printf (“Стек пуст\n”); return 0.0; } } Задание. Написать другие функции работы со стеком.

Стек (stack)

Реализация динамического стека (списковая память). struct node { // Структура узел (node) double data; struct node *p; }; struct node *sp; // Указатель на вершину стека sp = NULL; // Стек пуст

Стек (stack)

void PUSH ( double f) { struct node *temp = (struct node *) malloc(sizeof(struct node)); if (temp == NULL) { printf(“Нет свободной памяти\n”); exit(1); } temp->data = f; temp->p = sp; sp = temp; }

Стек (stack)

double POP (void) { struct node *temp; double x; if (stack == NULL) { printf(“Стек пуст\n”); exit(1); } temp = sp; sp = temp->p; x = temp->data; free(tmp); return x; }

Стек (stack)

Пример 1. Постфиксный калькулятор В постфиксной форме записи выражений (обратная польская запись) операнды предшествуют своему знаку операции. (5+3)*4  5 3 + 4 * 5+3*4  5 3 4 * + Для записи любого выражения не требуется скобок. Порядок следования операндов то же, что и инфиксной формы записи выражения. Используя стек, легко реализовать алгоритм вычисления выражения.

Стек (stack)

• Алгоритм:
• Из исходной строки выделяется очередной элемент.
• Если элемент – операнд, то он заносится в стек операндов и переход к п. 1.
• Если элемент – знак операции, то из стека операндов последовательно извлекаются два элемента, над ними выполняется операция и результат операции заносится в стек. Переход к п. 1.
• Пункты 1 – 3 выполняются до тех пор, пока в исходной строке не встретится признак конца выражения. В этом случае число, находящееся в стеке, является результатом вычисления.

Стек (stack)

• Пример 2. Преобразование инфиксной формы выражения в постфиксную форму.
• Алгоритм:
• Из исходной строки выделяется очередной элемент.
• Если элемент – операнд, то он отправляется в выходную последовательность и переход к п. 1.
• Если элемент – знак операции или открывающая скобка, то они направляются в стек скобок и знаков операций. Переход к п. 1.
• Если элемент – закрывающая скобка, то из стека выталкиваются в выходную последовательность знаки операций до открывающей скобки, а скобки уничтожаются.

Стек (stack)

5. Если элемент – знак операции с более высоким приоритетом, то из стека выталкиваются в выходную последовательность все знаки операций с более низким приоритетом. 6. Пункты 1 – 5 выполняются до тех пор, пока в исходной строке не встретится признак конца выражения. В этом случае в выходной последовательности получается обратная польская запись исходного выражения.

Очередь (queue)

Очередь – линейная структура данных, в которой все вставки элементов выполняются на одном конце, называемым хвостом (tail) очереди, а все удаления элементов выполняются на другом конце, называемым головой (head) очереди. Произвольный доступ к отдельным элементам очереди не разрешается. В англоязычной литературе для обозначения очереди используется аббревиатура FIFO (First In First Out – первый вошел – первый вышел). Примеры. 1. Очередь в библиотеку. 2. Очередь в столовую.

Очередь (queue)

Очереди могут быть реализованы с помощью статических массивов