Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Then begin. WriteLn('Исключаемый элемент отсутствует');






WriteLn('Исключаемый элемент отсутствует');

Halt;

End

Else begin

DisItem: = Addr^.Next;

DeleteAfter: = DisItem^.Value;

Addr^.Next: = DisItem^.Next;

Dispose(DisItem);

end;

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

end; // function tList.DeleteAfter

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

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

Var

Item: pItem; // вспомогательный указатель на элемент списка

Begin

if Addr=fHead

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

Delete: = Addr^.Value;

fHead: = Addr^.Next;

Dispose(Addr);

End

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

Item: = fHead;

while (Item^.Next< > Addr) and (Item< > nil) do Item: = Item^.Next;

if Item= nil

then WriteLn('Исключаемый элемент отсутствует')

Else begin

Delete: = Addr^.Value;

Item^.Next: = Addr^.Next;

Dispose(Addr);

end;

end;

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

end; // function tList.Delete

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

Поиск элемента с заданным значением v в списке:

function tList.Search(v: tValue): pItem;

// Возвращение адреса элемента со значением v

// или nil, если элемент отсутствует

Var

Item: pItem;

Begin

if Empty

then Search: = nil

Else begin

Item: = fHead;

while (Item^.Next< > nil) and (Item^.Value< > v) do Item: = Item^.Next;

if Item^.Value=v then Search: = Item else Search: = nil;

end;

end; // function tList.Search

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

procedure tList.InsertHead(v: tValue);

Var

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

Begin

NewItem: = New(pItem); // выделение памяти под новый элемент

NewItem^.Value: = v; // запись v в поле значения нового элемента

NewItem^.Next: = fHead; // fHead -> в поле ссылки нового элемента

fHead: = NewItem; // перемещение fHead на новый элемент

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

end; // procedure tList.InsertHead

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

procedure tList.InsertRear(v: tValue);

Var

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

Begin

if Empty

then InsertHead(v) // если список пуст, то включение в начало,

else begin // иначе поиск адреса последнего элемента

Item: = fHead;

while Item^.Next< > nil do Item: = Item^.Next;

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

end;

end; // procedure tList.InsertRear

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

function tList.DeleteHead: tValue;

Begin

DeleteHead: = Delete(fHead)

end; // function tList.DeleteHead

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

function tList.DeleteRear: tValue;

Var

Item: pItem;

Begin

Item: = fHead;

while Item^.Next< > nil do Item: = Item^.Next;

DeleteRear: = Delete(Item)

end; // function tList.DeleteRear

5. Циклический список

Для доступа к требуемому элементу линейного списка необходимо просматривать список с его начала независимо от положения исходной точки просмотра. Это замедляет операции доступа к элементам в списке. Замыкание элементов списка в кольцо позволяет устранить этот недостаток. Такой список называется циклическим. Просмотр циклического списка можно начинать с любого элемента, а не только с его начала, причем началом списка может служить любой из его элементов. Логическая структура циклического списка:

6. Операции над циклическим списком

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

Для циклического списка также вводится новая операция – сцепление двух циклических списков – Сoncat (с 1, с 2).

7. Односвязная реализация циклического списка

Реализация циклического списка с помощью динамических переменных:

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

Класс tCircleList может быть описан следующим образом:

Type

tValue= Real; // тип значения элемента списка - вещественный

pItem= ^tItem; // тип указателя на элемент списка

tItem= record // тип элемента списка

Value: tValue; // содержательная часть элемента списка

Next: pItem; // указатель на следующий элемент списка

end; // recordtItem

tCircleList= class // класс - циклический список






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.