Работа с памятью при использовании динамических структур

В программах, в которых необходимо использовать динамические структуры данных, работа с памятью происходит стандартным образом. Выделение динамической памяти производится с помощью операции new или с помощью библиотечной функции malloc (calloc). Освобождение динамической памяти осуществляется операцией delete или функцией free.

Например, объявим динамическую структуру данных с именем Node с полями Name, Value и Next, выделим память под указатель на структуру, присвоим значения элементам структуры и освободим память.

struct Node {char *Name;

int Value;

Node *Next

};

Node *PNode; //объявляется указатель

PNode = new Node; //выделяется память

PNode->Name = "STO"; //присваиваются значения

PNode->Value = 28;

PNode->Next = NULL;

delete PNode; // освобождение памяти

Стеки

Стек (англ. stack – стопка) – это структура данных, в которой новый элемент всегда записывается в ее начало (вершину) и очередной читаемый элемент также всегда выбирается из ее начала (рис. 1). В стеках используется метод доступа к элементам LIFO (Last Input – First Output, "последним пришел – первым вышел"). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно сначала взять верхнюю.

Стек – это список, у которого доступен один элемент (одна позиция). Этот элемент называется вершиной стека. Взять элемент можно только из вершины стека, добавить элемент можно только в вершину стека. Например, если записаны в стек числа 1, 2, 3, то при последующем извлечении получим 3,2,1.

Рис. 1. Стек и его организация

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

struct имя_типа {

информационное поле;

адресное поле;

};

где информационное поле – это поле любого ранее объявленного или стандартного типа;

адресное поле – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента стека.

Например:

struct list {

type pole1;

list *pole2;

} stack;

Стек как динамическую структуру данных легко организовать на основе линейного однонаправленного списка, поскольку работа всегда идет с заголовком стека. Для такого списка достаточно хранить указатель вершины стека, который указывает на первый элемент списка. Если стек пуст, то списка не существует, и указатель принимает значение NULL.

Описание элементов стека аналогично описанию элементов линейного однонаправленного списка. Поэтому объявим стек через объявление линейного однонаправленного списка:

struct Stack {

Single_List *Top;//вершина стека

};

..........

Stack *Top_Stack;//указатель на вершину стека

Основные операции, производимые со стеком:

• создание стека;
• печать (просмотр) стека;
• добавление элемента в вершину стека;
• извлечение элемента из вершины стека;
• проверка пустоты стека;
• очистка стека.

Очереди

Очередь – это структура данных, представляющая собой последовательность элементов, образованная в порядке их поступления. Каждый новый элемент размещается в конце очереди; элемент, стоящий в начале очереди, выбирается из нее первым. В очереди используется принцип доступа к элементам FIFO (First Input – First Output, "первый пришёл – первый вышел") (рис. 2). В очереди доступны два элемента (две позиции): начало очереди и конец очереди. Поместить элемент можно только в конец очереди, а взять элемент только из ее начала. Примером может служить обыкновенная очередь в магазине.

Рис. 2. Очередь и ее организация

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

struct имя_типа {

информационное поле;

адресное поле1;

адресное поле2;

};

где информационное поле – это поле любого, ранее объявленного или стандартного, типа;

адресное поле1, адресное поле2 – это указатели на объекты того же типа, что и определяемая структура, в них записываются адреса первого и следующего элементов очереди.

Например:

1 способ: адресное поле ссылается на объявляемую структуру.

struct list2 {

type pole1;

list2 *pole1, *pole2;

}

2 способ: адресное поле ссылается на ранее объявленную структуру.

struct list1 {

type pole1;

list1 *pole2;

}

struct ch3 {

list1 *beg, *next;

}

Очередь как динамическую структуру данных легко организовать на основе линейного списка. Поскольку работа идет с обоими концами очереди, то предпочтительно будет использовать линейный двунаправленный список. Хотя для работы с таким списком достаточно иметь один указатель на любой элемент списка, здесь целесообразно хранить два указателя – один на начало списка (откуда извлекаем элементы) и один на конец списка (куда добавляем элементы). Если очередь пуста, то списка не существует, и указатели принимают значение NULL.

Описание элементов очереди аналогично описанию элементов линейного двунаправленного списка. Поэтому объявим очередь через объявление линейного двунаправленного списка:

struct Queue {

Double_List *Begin;//начало очереди

Double_List *End; //конец очереди

};

..........

Queue *My_Queue;//указатель на очередь

Основные операции, производимые с очередью:

• создание очереди;
• печать (просмотр) очереди;
• добавление элемента в конец очереди;
• извлечение элемента из начала очереди;
• проверка пустоты очереди;
• очистка очереди.

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

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

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

Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.

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

Операции над деком:

• включение элемента справа;
• включение элемента слева;
• исключение элемента справа;
• исключение элемента слева;
• определение размера;
• очистка.

Физическая структура дека в статической памяти идентична структуре кольцевой очереди. Динамическая реализация является очевидным объединением стека и очереди.

Вопрос №22. Динамические структуры данных. Список. Двунаправленный список. Кольцевой список. Кольцевой двунаправленный список.

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

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

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

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

• однонаправленные (односвязные) списки;
• двунаправленные (двусвязные) списки;
• циклические (кольцевые) списки.

Date: 2016-07-25; view: 601; Нарушение авторских прав