Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Алгоритмы и структуры данных

РЕАЛИЗАЦИЯ ЛИНЕЙНОГО СПИСКА В ВИДЕ ДВУСВЯЗНОЙ ДИНАМИЧЕСКОЙ СТРУКТУРЫ

Односвязный список имеет ряд недостатков. Такой список нельзя просматривать в обратном направлении. Располагая только значением указателя на данный элемент, удалить последний невозможно.

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

При описании двусвязных списков используют термины «левый» и «правый» для определения элементов, расположенных соответственно слева и справа от текущего элемента.

Динамическая реализация линейного двусвязного списка приведена на рис. 2.7.

Head Left Value Right Rear

nil

—•

nil

*

•—

Рис. 2.7. Динамическая реализация линейного двусвязного списка

Переменные ссылочного типа Head и Rear указывают соответственно на начало и конец списка (на его крайний левый и крайний правый элементы). В конце каждого направления содержится указатель nil.

Работа с двусвязным линейным списком предполагает выполнение всех операций, определенных для односвязного линейного списка.

Описание класса tDCList (DCList — Doubly Connected List):

type

tValue= Real; //тип значения элемента списка - вещественный pltem= Atltem; //тип указателя на элемент двусвязного списка tltem= record //тип элемента двусвязного списка Value: tValue; //содержательная часть элемента списка Left, Right: pltem; //указатели на соседние элементы end; //record tltem

tDCList = class //класс- двусвязный список

protected

fHead, fRear: pltem; //поля - указатели на начало и конец списка fSize: Word; //поле - число элементов списка

public

// Свойство - число эл-тов списка (доступ по чтению и записи) property Size: Word read fSize write fSize;

// Свойство - указ, начало списка (доступ по чтению и записи) property Head: pltem read fHead write fHead;

// Свойство - указ, на конец списка (доступ по чтению и записи) property Rear: pltem read fRear write fRear;

//Включение эл-та со значением v справа от эл-та с адресом Addr

procedure lnsertRight(Addr: pltem; v: tValue);

//Включение эл-та со значением v слева от эл-та с адресом Addr procedure lnsertLeft(Addr: pltem; v: tValue);

// Исключение элемента справа от элемента с указателем Addr function DeleteRight(Addr: pltem): tValue;

// Исключение из списка элемента с указателем Addr function Delete(Addr: pltem): tValue;

// Возвращение адреса элемента со значением v function Search(v: tValue): pltem;

// Включение элемента со значением v в начало списка procedure lnsertHead(v: tValue);

// Включение элемента со значением v в конец списка procedure lnsertRear(v: tValue);

function DeleteHead: tValue; //исключение из начала function DeleteRear: tValue; //исключение из конца function Empty: Boolean; //возвращение true, если список пуст procedure Clear; //очистка списка

constructor Create; //конструктор - создание списка

destructor Destroy; override; //деструктор - удаление списка end; //tDCList

Для двусвязного списка справедливо следующее правило: если Addr есть указатель на любой его элемент, то

AddrALeftA Right = Addr = AddrARightALeft.

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ   След >
 

Популярные страницы