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