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

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

Включение элемента со значением V после элемента с адресом Лййг (см. рис. 2.3):

Addr

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

Рис. 2.3. Включение элемента со значением v после элемента с адресом Addr

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

procedure tList.lnsertAfter(Addr: pltem; v: tValue);

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

var

Newltem: pltem; //указатель на новый элемент

begin

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

// если список пуст, включаем в его начало NewltemA.Next:= nil; fHead:= Newltem;

end

else begin

// список не пуст - включаем после элемента с адресом Addr NewltemA.Next:= AddrA.Next;

AddrA.Next:= Newltem;

end;

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

end; //procedure tList.lnsertAfter

Включение элемента со значением v в список перед элементом с адресом Addr может быть выполнено следующим образом. Сначала новый элемент включается после элемента с адресом Addr, а затем происходит обмен содержательными полями между включенным элементом и элементом с адресом Addr. Предполагается, что адрес Addr отличен от nil, и элемент с адресом Addr присутствует в списке. Если список пуст, то новый элемент включается в начало списка.

procedure tl_ist.lnsertBefore(Addr: pltem; v: tValue);

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

var

Newltem: pltem; //указатель на новый элемент

begin

Newltem:= New(pltem); //выделение памяти под новый элемент if Empty then begin //если список пуст, включаем в его начало NewltemA.Value:= v;

NewltemA.Next:= nil; fHead:= Newltem; end

else begin

// иначе обмен содержимым элементов NewltemA и AddrА NewltemA:= AddrA;

AddrA.Value:= v;

AddrA.Next:= Newltem;

end;

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

end; //procedure tList.lnsertBefore

Исключение элемента, следующего за элементом с адресом Addr. function tl_ist.DeleteAfter(Addr: pltem): tValue;

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

var

Dis I tern: pltem; //указатель на исключаемый элемент

begin

if AddrA.Next<>nil

then begin Disltem:= AddrA.Next;

DeleteAfter:= DisltemA.Value;

AddrA.Next:= DisltemA.Next;

Dispose(Disltem);

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

end;

end; //function tList.DeleteAfter

Операция tList.DeleteAfter неприменима к пустому списку, поэтому перед ее выполнением необходимо анализировать значение признака «список пуст».

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

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

Исключение из списки элемента с указателем Addr. В этом случае необходимо определить адрес элемента, предшествующего исключаемому, что выполняется проходом по списку от его начала с помощью передвигаемого по элементам списка вспомогательного указателя Item типа pltem.

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

// Исключение элемента с указателем Addr

var

Item: pltem; //указатель на элемент списка

begin

if Addr=fHead

then begin // исключается первый элемент

Delete:= AddrA.Value; fHead:= AddrA.Next;

Dispose(Addr);

end

else begin // поиск элемента, предшествующего исключаемому ltem:= fHead;

while ltemA.Next<>Addr do ltem:= ltemA.Next;

Delete:= AddrA.Value; ltemA.Next:= AddrA.Next;

Dispose(Addr);

end;

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

end; //function tList.Delete

Операция tList.Delete неприменима к пустому списку, поэтому перед ее выполнением необходимо анализировать значение признака «список пуст». При выполнении операции предполагается, что адрес Addr отличен от nil, и элемент с заданным адресом присутствует в списке.

Поиск элемента с заданным значением v в списке: function tList.Search(v: tValue): pltem;

//Возвращение адреса эл-та со значением v (nil, если эл-та нет)

begin

Result:= fHead; while Result<>nil do if ResultA.Value=v then Break

else Result:= ResultA.Next; end; //function tList.Search

Включение элемента со значением v в начало списка:

procedure tList.lnsertHead(v: tValue);

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

var

Newltem: pltem; //указатель на новый элемент

begin

Newltem:= New(pltem); //выделение памяти под новый элемент NewltemA.Value:= v; //запись у/ в поле значения нового элемента NewltemA.Next:= fHead; //fHead -> в поле ссылки нового элемента fHead:= Newltem; //перемещение fHead на новый элемент

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

end; //procedure tList.lnsertHead

Включение элемента со значением v в конец списка:

procedure tList.lnsertRear(v: tValue);

// Включение элемента со значением v в конец списка

var

Item: pltem; //указатель на последний элемент

begin

if Empty

then InsertHead(v) //если список пуст, то включение в начало, else begin // иначе поиск адреса последнего элемента

ltem:= fHead;

while ltemA.Next<>nil do

ltem:= ltemA.Next;

lnsertAfter(ltem, v); // и вставка после последнего элемента

end;

end; //procedure tList.InsertRear

Исключение элемента из начала списка:

function tList.DeleteHead: tValue;

// Исключение элемента из начала списка:

begin

DeleteHead:= Delete(fHead) end; //function tList.DeleteHead

Исключение элемента из конца списка:

function tList.DeleteRear: tValue;

// Исключение элемента из конца списка:

var

ltem:pltem;

begin

ltem:= fHead; while ltemA.Next<>nil do ltem:= ltemA.Next;

DeleteRear:= Delete(ltem) end; //function tList.DeleteRear

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

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