Динамические структуры данных (списки)

Динамическая память позволяет реализовать широко используемую организацию данных в виде списков. На рис. 14.1 показан однонаправленный список.

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

У казатель на начало списка

-

---------

Информа-

Информа-

і

Информа-

ционное

ционное

і

і

ционное

ноле 1- го

поле 2-го

і

і

ноле N-vо

звена

звена

і

і

звена

Указатель

Указатель

і

• • •

NULL

Рис. 14.1. Однонаправленный (односвязный) список

значение) — это является признаком конца списка. Тип каждого звена однонаправленного списка определяется следующим образом:

Struct <имя_типа_звена_списка>

{<тип_1> <имена_полей_информационной_части_1> ;

<тип_2> <имена_полей_информационной_части_2> ;

• • •

<тип_к> <имена_полей_информационной_части_к>;

<имя_типа_указателя_на_звено_списка>

<имя_указателя_на_следующее_звено>;

};

где <имя_типа...>, < имена_полей...>, <имя_указате-

ля. . . > — идентификаторы пользователя;

<тип_звена> — структурный тип, определяемый пользователем; одним из полей в структуре должен быть <указатель на следующее звено списка>; количество информационных полей не ограничено;

<тип_указателя_на_звено_списка> — ссылочный тип, базовым для него является <тип_ звена>.

Например, тип списка с целой информационной частью звеньев задается следующим образом:

//структурный тип "звено списка " //информационное поле звена //указатель на следующее звено списка

struct Spisok{

int Elem;

Spisok *Next;

};

Базовым типом указателя на звено является тип звена, который, в свою очередь, содержит в адресной части звена (указателе на следующее звено) тип указателя на звено.

Использование указателей в такой организации данных позволяет достаточно просто вносить в нее изменения. Так, например, легко вставить новое звено на любое место, расширить список, удалить звено с любого места и т. д. Подобные операции для элементов массива могут встретить огромные трудности.

 
< Пред   СОДЕРЖАНИЕ     След >