Пример использования функции malloc: связные списки
В информатике существует множество типов динамических структур данных. Одним из классических примеров таких структур является связный список, в котором группа одинаковых объектов связывается в единый логический объект. В этом разделе составляется простой пример, использующий односвязный список для демонстрации применения функций семейства malloc.
(* list.inc - заголовочный файл для примера. *)
uses strings,stdio;
(* Определение основной структуры *)
type
pMEMBER=^MEMBER;
MEMBER=record
m_data:pchar;
m_next:pMEMBER;
end;
ppMEMBER=^pMEMBER;
(* Определение функций *)
function new_member(data:pchar):pMEMBER;forward;
procedure add_member(head:ppMEMBER; newmem:pMEMBER);forward;
procedure free_list (head:ppMEMBER);forward;
procedure printlist (listhead:pMEMBER);forward;
Оператор type вводит тип MEMBER, имеющий два поля. Первое поле, m_data, в экземпляре типа MEMBER будет указывать на произвольную строку. Второе поле, m_next, указывает на другой объект типа MEMBER.
Каждый элемент в связном списке структур типа MEMBER будет указывать на следующий в списке объект MEMBER, то есть если известен один элемент списка, то следующий можно найти при помощи указателя m_next. Поскольку на каждый объект MEMBER в списке ссылается только один указатель, список можно обходить только в одном направлении. Такие списки называются односвязными (singly linked). Если бы был определен еще один указатель m_prev, то список можно было бы обходить и в обратном направлении, и в этом случае он был бы двусвязным (doubly linked).
Адрес начала, или головы, списка обычно записывается в отдельном указателе, определенным следующим образом:
const
head:pmember = nil;
Конец списка обозначается нулевым значением поля
m_next последнего элемента списка.
На рис. 12.1 показан простой список из трех элементов. Его начало обозначено указателем head.
Теперь представим небольшой набор процедур для работы с этими структурами. Первая функция называется new_member. Она отводит память под структуру MEMBER с помощью вызова malloc. Обратите внимание, что указателю m_next присвоено нулевое значение, в данном случае обозначенное как nil. Это связано с тем, что функция malloc не обнуляет выделяемую память. Поэтому при создании структуры
MEMBER поле m_text может содержать ложный, но правдоподобный адрес.
Рис. 12.1. Связный список объектов MEMBER
{$i list.inc}
(* Функция new_member - выделить память для нового элемента *)
function new_member (data:pchar):pMEMBER;
var
newmem:pMEMBER;
begin
newmem := malloc (sizeof (MEMBER));
if newmem = nil then
writeln (stderr, 'new_member: недостаточно памяти')
else
begin
(* Выделить память для копирования данных *)
newmem^.m_data := malloc (strlen (data) + 1);
(* Скопировать данные в структуру *)
strcopy (newmem^.m_data, data);
(* Обнулить указатель в структуре *)
newmem^.m_next := nil;
end;
new_member:=newmem;
end;
Следующая процедура add_member добавляет в список, на который указывает head, новый элемент
MEMBER. Как видно из текста процедуры, элемент MEMBER добавляется всегда в начало списка.
{$i list.inc}
(* Процедура add_member - добавить новый элемент MEMBER *)
procedure add_member (head:ppMEMBER; newmem:pMEMBER);
begin
(* Эта простая процедура вставляет новый
* элемент в начало списка
*)
newmem^.m_next := head^;
head^ := newmem;
end;
Последняя процедура – free_list. Она принимает указатель на начало списка head^ и освобождает память, занятую всеми структурами MEMBER, образующими список. Она также обнуляет указатель head^, гарантируя, что в указателе head^ не содержится прежнее значение (иначе при случайном использовании head^ могла бы возникать трудноуловимая ошибка).
{$i list.inc}
(* Процедура free_list - освободить занятую списком память *)
procedure free_list (head:ppMEMBER);
var
curr, next:pMEMBER;
begin
curr := head^;
while curr <> nil do
begin
next := curr^.m_next;
(* Освободить память, занятую данными *)
free (curr^.m_data);
(* Освободить память, отведенную под структуру списка *)
free (curr);
curr := next;
end;
(* Обнулить указатель на начало списка *)
head^ := nil;
end;
Следующая простая программа использует описанные процедуры. Она создает односвязный список, изображенный на рис. 12.1, а затем удаляет его. Обратите внимание на способ обхода списка процедурой
printlist. Используемый в ней цикл while типичен для программ, в которых применяются связные списки.
{$i list.inc}
(* Обход и вывод списка *)
procedure printlist (listhead:pMEMBER);
var
m:pMEMBER;
begin
writeln (#$a'Содержимое списка:');
if listhead = nil then
writeln (#9'(пусто)')
else
begin
m := listhead;
while m <> nil do
begin
writeln (#9, m^.m_data);
m := m^.m_next;
end;
end;
end;
const
strs:array [0..2] of pchar=('again', 'world', 'Hello');
(* Программа для проверки процедур работы со списком *)
var
head, newm:pMEMBER;
j:integer;
begin
(* Инициализация списка *)
head := nil;
(* Добавление элементов к списку *)
for j:=0 to 2 do
begin
newm := new_member (strs[j]);
add_member (@head, newm);
end;
(* Вывести элементы списка *)
printlist (head);
(* Удалить список *)
free_list (@head);
(* Вывести элементы списка *)
printlist (head);
end.
Следует обратить внимание и на то, как в начале программы был инициализирован список присвоением указателю head значения nil. Это важно, так как иначе список мог оказаться заполненным «мусором», что неизбежно привело бы к ошибочной работе или к аварийному завершению программы.
Рассматриваемая программа должна выдать такой результат:
Содержимое списка:
Hello world again
Содержимое списка:
(пусто)
