Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Protected. fHead, fRear: pItem; // поля – указатели на начало и конец списка
fHead, fRear: pItem; // поля – указатели на начало и конец списка fSize: Word; // поле – число элементов списка Public // Свойство - число элементов списка (доступ по чтению и записи) property Size: Word read fSize write fSize; // Свойство – указатель на начало списка (доступ по чтению и записи) property Head: pItem read fHead write fHead; // Свойство – указатель на конец списка (доступ по чтению и записи) property Rear: pItem read fRear write fRear; // Включение элемента со значением v справа от элемента с адресом Addr procedure InsertRight(Addr: pItem; v: tValue); // Включение элемента со значением v слева от элемента с адресом Addr procedure InsertLeft(Addr: pItem; v: tValue); // Исключение элемента справа от элемента с указателем Addr function DeleteRight(Addr: pItem): tValue; // Исключение из списка элемента с указателем Addr function Delete(Addr: pItem): tValue; // Возвращение адреса элемента со значением v function Search(v: tValue): pItem; // Включение элемента со значением v в начало списка procedure InsertHead(v: tValue); // Включение элемента со значением v в конец списка procedure InsertRear(v: tValue); function DeleteHead: tValue; // исключение из начала function DeleteRear: tValue; // исключение из конца function Empty: Boolean; // возвращение true, если список пуст procedure Clear; // очистка списка constructor Create; // конструктор - создание пустого списка destructor Destroy; override; // деструктор - удаление списка end; // tDCList Для двусвязного списка справедливо следующее правило: если Addr есть указатель на любой его элемент, то Addr^.Left^.Right = Addr = Addr^.Right^.Left. 10. Реализация основных операций над двусвязным списком Включение элемента со значением v в двусвязный список справа от элемента с заданным адресом Addr выполняется по следующей схеме: Реализация операции приведена ниже. Предполагается, что значение Addr отлично от nil и элемент с адресом Addr присутствует в списке. Если список пуст, то новый элемент включается в начало списка. При включении в конец списка указатель Rear передвигается на включенный элемент. procedure tDCList.InsertRight(Addr: pItem; v: tValue); Var NewItem: pItem; // указатель на новый элемент Begin NewItem: = New(pItem); // выделение памяти под новый элемент списка NewItem^.Value: = v; if Empty then begin // если список пуст, включаем в его начало NewItem^.Left: = nil; NewItem^.Right: = nil; fHead: = NewItem; fRear: = NewItem; end else begin // список не пуст NewItem^.Left: = Addr; NewItem^.Right: = Addr^.Right; if Addr=fRear then fRear: = NewItem // если включение в конец списка else Addr^.Right^.Left: = NewItem; // если включение в середину Addr^.Right: = NewItem; end; Inc(fSize); // увеличение числа элементов списка на 1 end; // procedure tDCList.InsertRight Включение элемента в двусвязный список слева от элемента с адресом Addr выполняется подобно включению справа, но все левые указатели заменяются правыми и наоборот, и вместо ситуации включения в конец списка анализируется ситуация включения в начало списка. Исключение из двусвязного списка элемента с указателем Addr. При реализации операции необходимо рассмотреть следующие частные случаи: – если исключается элемент в начале списка (Addr=fHead), то расположенный справа от удаляемого элемент должен стать первым; – если исключается элемент в конце списка (Addr=fRear), то расположенный слева от удаляемого элемент должен стать последним. function tDCList.Delete(Addr: pItem): tValue; Begin Delete: = Addr^.Value; if Addr=fHead then fHead: =Addr^.Right // исключается первый элемент else Addr^.Left^.Right: =Addr^.Right; // исключается не первый элемент if Addr=fRear then fRear: =Addr^.Left // исключается последний элемент else Addr^.Right^.Left: =Addr^.Left; // исключается не последний элемент Dispose(Addr); Dec(fSize); // уменьшение числа элементов на 1 end; // function tDCList.Delete Исключение из двусвязного списка элемента, расположенного справа от элемента с адресом Addr можно выполнить следующим образом: передвинуть указатель Addr на элемент, который необходимо удалить, и исключить его из списка с помощью операции Delete. function tDCList.DeleteRight(Addr: pItem): tValue; Begin if Addr=fRear then WriteLn('Исключаемый элемент отсутствует')
|