Краткие сведения из теории. Работа с динамической памятью

Лабораторная работа № 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 ≠a₁, надо:

• найти элемент списка, для которого b = a_k;

• при поиске сохранить в указателе значение адреса на предыдущий элемент списка.

Для того чтобы удалить элемент списка со значением 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; // К списку присоединяем новый узел. Для этого в правый