Лабораторная работа № 7
Работа с динамической памятью.
Цель работы
Овладеть практическими навыками работы с односвязными и двусвязными списками. Научиться формировать списки, освоить технику программирования операций над списками.
Краткие сведения из теории
Односвязные списки относятся к динамическим структурам данных, которые характеризуются следующим:
1) память под данные выделяется по мере необходимости;
2) из этой структуры можно исключить элемент, который по тем или иным условиям задачи в дальнейшем не будет востребован. Элементом (узлом, звеном) списка является структура, в которой обязательно присутствует поле указателя на эту структуру. Односвязный список представляет собой множество таких узлов. При этом каждый элемент данного списка содержит адрес следующего элемента – ссылку на следующий элемент списка.
Чтобы сформировать список, надо следовать такому алгоритму:
• определить структуру, в которой обязательно присутствует поле указателя на эту структуру;
• определить некоторый набор переменных, необходимых для работы программы;
• сформировать новый элемент структуры;
• инициализировать поля нового элемента;
• если список пуст, то объявить этот элемент головным (или последним) элементом списка (в зависимости от задачи);
• если список не пустой, то новый элемент присоединить к списку;
• новый элемент списка объявить последним.
Определим структуру следующим образом:
struct node
{
int inf; // Поле для записи целых чисел.
node *next; // Поле указателя для записи адресов элементов типа node.
};
Для формирования списка нам потребуются три переменные типа node. Переменная fr – для адреса первого элемента списка; переменная r – для адреса нового узла списка; переменная er – для адреса последнего узла списка. При объявлении переменных node *fr = NULL, *r, * er; выделяется три области памяти fr, r, er для адресов переменных типа node.
Для формирования первого элемента списка надо использовать код r = new node.
После того как создан первый элемент списка, его надо инициализировать, т. е. заслать информацию в поля inf и node нового объекта. Код r -> inf = a в поле inf первого элемента списка пересылает значение из переменной a.
При выполнении кода r -> next = NULL в поле указателя next первого элемента засылается значение NULL.
Далее при следующем выполнении кода r = new node выделится новая область памяти для нового (второго) элемента списка типа node. При выполнении директивы r -> inf = a в поле inf второго элемента списка пересылается значение из переменной a. При выполнении директивы r -> next = NULL в поле указателя next второго элемента засылается значение NULL.
Теперь нам надо присоединить новый (второй) сформированный узел списка к предыдущему (первому) узлу списка. Это достигается выполнением кода:
er -> next = r.
Удаление элемента из списка. Решение данной задачи зависит от расположения элемента в списке. Способ удаления головного (первого) элемента списка отличается от способа удаления любого другого элемента.
Для того чтобы удалить первый элемент списка, надо выполнить следующие директивы:
r = fr;
fr = fr -> next;
delete r;
Напомним, что директива delete r освобождает использованный программой участок памяти, адрес которого содержался в указателе r.
Для того чтобы удалить элемент со значением b ≠a1, надо:
• найти элемент списка, для которого b = ak;
• при поиске сохранить в указателе значение адреса на предыдущий элемент списка.
Для того чтобы удалить элемент списка со значением ak = b, необходимо выполнить следующие две директивы:
rp->next = r->next;
delete r;
Двусвязный список есть динамическая структура данных (ДСД). Каждый его узел связан как с предыдущим, так и с последующим элементом.
Структура для элемента двусвязного списка определяется следующим образом:
struct node
{ int inf;
node *lt;
node *rt;
};
Приведем фрагмент программы для формирования первого элемента списка. Смысл параметров, которые используются во фрагменте, следующий: r – указатель типа node для формирования нового узла списка, или указатель на текущий (новый) элемент списка; fr – указатель типа node для адреса последнего элемента списка, или указатель на последний элемент списка; en – указатель типа node для адреса последнего элемента списка, или указатель на последний элемент списка.
r = new node; // Выделяется память под первое звено списка.
// Адрес звена засылается в указатель r.
r -> lt = NULL; // Определяется поле указателя lt первого звена.
r -> rt = NULL; // Определяется поле указателя rt первого звена.
r -> inf = nz; // Определяется поле inf первого звена.
fr = r; // Определяется указатель на первое звено списка.
en = r; // Определяется указатель на последнее звено списка.
Приведем фрагмент программы, который демонстрирует, как новый элемент присоединяется к существующему списку. Каждый код фрагмента поясняется в комментариях. Смысл параметров, которые используются во фрагменте, следующий: r – указатель типа node для формирования нового узла списка, или указатель на текущий (новый) элемент списка; en – указатель типа node для адреса последнего элемента списка, или указатель на последний элемент списка.
r = new node; // Выделяется память под новое текущее звено.
// Адрес нового звена заносится в указатель r.
r -> inf = nz; // В поле inf нового узла засылается его значение.
r -> rt = NULL; // Правый указатель нового звена должен иметь
// значение NULL.
r -> lt = en; // К новому узлу присоединяется сформированная
// часть двусвязного списка. Для этого в левый
// указатель нового узла пересылаем адрес на
// последний элемент списка.
// Заметим, что по отношению к новому узлу эта часть
// является левой частью списка.
en -> rt = r; // К списку присоединяем новый узел. Для этого в правый
// указатель последнего элемента списка засылаем адрес
// нового звена.
en = r; // Новое звено объявляем последним.
Порядок выполнения работы
