Системное программирование в UNIX средствами Free Pascal


         

Пример использования функции 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 не обнуляет выделяемую память. Поэтому при создании структуры



Содержание  Назад  Вперед