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

РЕАЛИЗАЦИЯ ОСНОВНЫХ ОПЕРАЦИИ НАД ДВУСВЯЗНЫМ СПИСКОМ

Включение элемента со значением V в двусвязный список справа от элемента с заданным адресом АйФ’ выполняется по схеме, приведенной на рис. 2.8.

Addr

Включение элемента со значением V в двусвязный список

Рис. 2.8. Включение элемента со значением V в двусвязный список

справа от элемента с адресом Аёйг

Предполагается, что значение Addr отлично от nil и элемент с адресом Addr присутствует в списке. Если список пуст, то новый элемент включается в начало списка. При включении в конец списка указатель Rear передвигается на включенный элемент.

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

// Включение эл-та со значением v справа от эл-та с адресом Addr var Newltem: pltem; //указатель на новый элемент

begin

Newltem:= New(pltem); //выделение памяти под новый элемент NewltemA.Valiie:= v; if Empty

then begin //если список пуст, включаем в его начало

NewltemA.Left:= nil;

NewltemA.Right:= nil; fHead:= Newltem; fRear:= Newltem; end else begin // список не пуст

NewltemA.Left:= Addr;

NewltemA.Right:= AddrA.Right; if Addr=fRear

then fRear:= Newltem //если включение в конец списка

else AddrA.RightA.Left:= Newltem; //если включение в середину AddrA.Right:= Newltem;

end;

Inc(fSize); //увеличение числа элементов списка на 1

end; //procedure tDCList.lnsertRight

Включение элемента в двусвязный список слева от элемента с адресом Addr выполняется подобно включению справа, но все левые указатели заменяются правыми и наоборот, и вместо ситуации включения в конец списка анализируется ситуация включения в начало списка.

Исключение из двусвязного списка элемента с указателем Addr. При реализации операции необходимо рассмотреть следующие случаи:

  • • если исключается элемент в начале списка (Addr = fHead), то расположенный справа от удаляемого элемент должен стать первым;
  • • если исключается элемент в конце списка (Addr = fRear), то расположенный слева от удаляемого элемент должен стать последним.

function tDCList.Delete(Addr: pltem): tValue;

// Исключение элемента с указателем Addr // и возвращение его значения

begin

Delete:= AddrA.Value;

if Addr=fHead

then fHead:=AddrA.Right // исключается первый элемент

else AddrA.LeftA.Right:=AddrA.Right; //исключается не первый эл-т if Addr=fRear

then fRear:=AddrA.Left // исключается последний эл-т

else AddrA.RightA.Left:=AddrA.Left; // исключается не последний эл-т Dispose(Addr);

Dec(fSize); //уменьшение числа элементов на 1

end; //function tDCList.Delete

Операция Delete неприменим к пустому списку; при ее реализации предполагается, что AddrOnil, и элемент с заданным адресом присутствует в списке.

Исключение из двусвязного списка элемента, расположенного справа от элемента с адресом Addr, можно выполнить следующим образом: передвинуть указатель Addr на элемент, который необходимо удалить, и исключить его из списка с помощью операции Delete.

function tDCList.DeleteRight(Addr: pltem): tValue;

// Исключение и возвращение значения элемента справа от Addr

begin

if AddrofRear then begin Addr:=AddrA.Right;

DeleteRight:= Delete(Addr);

end;

end; //function tDCList.DeleteRight

Операция DeleteRight неприменима к пустому списку; при ее реализации предполагается, что AddrOnil, и элемент с заданным адресом присутствует в списке.

Значение Addr=fRear означает, что элемент с адресом Addr является последним в списке и исключаемый элемент отсутствует; эта ситуация является исключительной и требует обработки средствами языка программирования.

Так же легко исключить элемент, стоящий слева от заданного. В этом случае необходимо проанализировать ситуацию Addr=fHead, которая означает, что исключаемый элемент отсутствует в списке.

Поиск элемента с заданным значением v в двусвязном списке выполняется так же как и поиск элемента в односвязном списке с той разницей, что указатель Next в функции Search заменяется на Right.

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

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