Пример выполнения задания. while not eof(fDat) do begin. while not Stack1.Empty do begin




Описать и реализовать в модуле LineStrs (линейные структуры) класс – стек. Сформировать стек из вещественных элементов, записанных в файле LW3Dat.txt. Исключить из стека элементы с введенным с терминала значением. Результаты работы записать в файл LW3Res.txt.

Программа решения задачи:

// Лабораторная работа 1. Стеки, очереди, деки.

// Выполнил Сергеев Андрей, группа 500.

// Формирование стека и исключение заданных элементов.

// Исходные данные - элементы стека - в файле LW1Dat.txt

// Результаты работы помещаются в файл LW1Res.txt

program LW1;

Uses

SysUtils,

Stacks in 'Stacks.pas';

function WinDOS(const s: string): string;

// Перекодировка русских символов строки s из ANSI (Windows) в ASCII (DOS)

Var

i: Word;

Begin

Result:=s; // копирование исходной Windows-строки в строку-результат

for i:=1 to Length(s) do begin

case Result[i] of

'А'..'п': Dec(Result[i],64); // уменьшение кода ANSI на 64

'р'..'я': Dec(Result[i],16); // уменьшение кода ANSI на 16

'Ё': Inc(Result[i],72); // увеличение кода ANSI на 72

'ё': Inc(Result[i],57); // увеличение кода ANSI на 57

end; // case

end; // for

end; // WinDOS

Var

Stack1, Stack2: tStack; // основной и вспомогательный стеки

fDat, fRes: Text; // файлы исходных данных и результатов

StVal, DelVal: tValue; // значения текущего и исключаемого элемента

quan: Word; // количество элементов стека

Begin

Try

Assign(fDat, 'LW1Dat.txt'); Reset(fDat);

Assign(fRes,' LW1Res.txt'); Rewrite(fRes);

// Вывод заголовков в файл результатов

WriteLn(fRes, 'Работа со стеком - поиск и удаление заданного элемента');

// Создание экземпляров Stack1, Stack2 класса tStack

Stack1:= tStack.Create; Stack2:= tStack.Create;

// Формирование стека 1

while not eof(fDat) do begin

Read(fDat, StVal); Stack1.Push(StVal);

end;

quan:= Stack1.Size;

// Вывод элементов стека 1 в файл результатов с помощью итератора

WriteLn(fRes, 'Сформирован стек из ',quan,' элементов:');

Stack1.IterInit;

while not Stack1.IterDone do Write(fRes, Stack1.IterNext:5:1);

Write(WinDos('Значение исключаемого элемента? '));

ReadLn(DelVal);

WriteLn(fRes);

WriteLn(fRes, 'Значение исключаемого элемента = ', DelVal:5:1);

// Исключение элементов из стека 1 и включение не равных DelVal в стек 2

while not Stack1.Empty do begin

StVal:= Stack1.Pop;

if StVal <> DelVal

then Stack2.Push(StVal);

end;

// Перезапись оставшихся после удаления элементов из стека 2 в стек 1

while not Stack2.Empty do begin

StVal:= Stack2.Pop; Stack1.Push(StVal);

end;

// Вывод элементов стека 1 в файл результатов с помощью итератора

WriteLn(fRes, 'Из стека исключено ',quan - Stack1.Size, ' элементов');

WriteLn(fRes, 'В стеке осталось ',Stack1.Size,' элементов:');

Stack1.IterInit;

while not Stack1.IterDone do Write(fRes, Stack1.IterNext:5:1);

WriteLn(fRes);

Stack1.Free; Stack2.Free;

Finally

Close(fDat); Close(fRes);

end;

end.

Тема 2. Односвязные и двусвязные
линейные списки

1. Линейный список

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

A D F B C
       

Начало

Число элементов списка не ограничено. Список, в котором нет ни одного элемента, называется пустым. Стеки, очереди и деки, рассмотренные в теме 1, являются частными случаями линейного списка, поскольку имеют ограниченную дисциплину обслуживания.

Списковые структуры находят широкое применение при решении следующих задач: топологическая сортировка, например в задачах сетевого планирования, арифметические действия с многочленами, операции с длинными числами, построение таблиц имен в трансляторах, моделирование ситуаций реального мира и т.д.

2. Операции над линейным списком

Над линейным списком l могут быть выполнены все операции, определенные для стека, очереди и дека (тема 1), а также следующие операции:

1) включение элемента со значением v в список после элемента с заданным адресом pInsertAfter (l, p, v);

2) включение элемента со значением v в список l перед элементом с заданным адресом pInsertBefore (l, p, v);

3) исключение из списка l элемента с адресом pDelete (l, p);

4) исключение из списка l элемента, следующего за элементом с адресом pDeleteAfter (l, p);

5) поиск в списке l элемента с заданным значением vSearch (l, v) и возвращение его адреса.

3. Реализация линейного списка в виде односвязной динамической структуры

Список, реализованный предложенным способом, называется односвязным линейным списком, т.к. каждый элемент этого списка содержит ссылку только на один соседний элемент. Описание класса tList:

Type

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

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

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

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

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

end; // recordtItem

tList = class // класс - список

Protected

fHead: pItem; // поле - указатель на начало списка

fSize: Word; // поле - число элементов списка

Public

// свойство – указатель на начало списка (доступ по чтению)

property Head: pItem read fHead;

// свойство - число элементов списка (доступ по чтению)

property Size: Word read fSize;

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

procedure InsertAfter(Addr: pItem; v: tValue);

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

procedure InsertBefore(Addr: pItem; v: tValue);

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

function DeleteAfter(Addr: pItem): tValue;

function Delete(Addr: pItem): tValue; // исключение элемента с адресом Addr

// Поиск в списке элемента со значением 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; // class tList

4. Реализация основных операций над односвязным списком

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

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

procedure tList.InsertAfter(Addr: pItem; v: tValue);

Var

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

Begin

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

NewItem^.Value:= v;

if Empty

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

NewItem^.Next:= nil;

fHead:= NewItem;

End

else begin // список не пуст - включаем после элемента с адресом Addr

NewItem^.Next:= Addr^.Next;

Addr^.Next:= NewItem;

end;

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

end; // procedure tList.InsertAfter

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

procedure tList.InsertBefore(Addr: pItem; v: tValue);

Var

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

Begin

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

if Empty

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

NewItem^.Value:= v;

NewItem^.Next:= nil;

fHead:= NewItem;

End

else begin // иначе обмен содержимым элементов NewItem^ и Addr^

NewItem^:= Addr^;

Addr^.Value:= v;

Addr^.Next:= NewItem;

end;

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

end; // procedure tList.InsertBefore

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

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

Var

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

Begin

if Addr^.Next= nil

Then begin

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 // класс - циклический список

Protected

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

fSize: Word; // поле - число элементов списка

Public

// Свойство - число элементов списка (доступ по чтению и записи)

property Size: Word read fSize write fSize;

// Свойство – указатель на начало списка (доступ по чтению и записи)

property Head: Word read fHead write fHead;

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

procedure InsertAfter(Addr: pItem; v: tValue);

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

procedure InsertBefore(Addr: pItem; v: tValue);

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

function DeleteAfter(Addr: pItem): tValue;

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

function Delete(Addr: pItem): tValue;

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

procedure InsertHead(v: tValue);

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

procedure InsertRear(v: tValue);

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

function DeleteHead:tValue;

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

function DeleteRear:tValue;

procedure Concat(var CList2: tCircleList); // сцепление со списком CList2

// Поиск в списке элемента со значением v и возвращение его адреса

function Search(v: tValue): pItem;

function Empty: Boolean; // возвращение true, если список пуст

procedure Clear; // очистка списка

constructor Create; // конструктор - создание пустого списка

destructor Destroy; override; // деструктор - удаление списка

end; // class tCircleList

Класс tCircleList не объявлен наследником класса tList поскольку реализация практически всех его методов отличается от реализации одноимённых методов для нециклического списка. Отличия, в основном, заключаются в следующем:

– для операций InsertAfter и InsertBefore по-другому осуществляются включение элемента в пустой список и включение в начало и конец циклического списка;

– применение операции DeleteAfter для циклического списка, состоящего из одного элемента, не должно приводить к исключению самого этого элемента;

– методы DeleteAfter и Delete должны восстанавливать указатель на последний элемент циклического списка, если он исключается при выполнении этих операций;

– в методах Search и Clear признаком завершения просмотра циклического списка является достижение вспомогательным указателем того элемента, с которого начался просмотр.

И только конструктор Create и деструктор Destroy реализуются так же как и одноимённые методы класса tList.

Очевидно, что операции включения и исключения справа и слева от текущего элемента (InsertHead, InsertRear, DeleteHead, DeleteRear) выполняют те же действия, что и одноимённые операции для нециклического списка. Отличие заключается в том, что новые операции изменяют значение указателя на последний элемент циклического списка, если список расширился влево или вправо либо сузился слева или справа.

8. Реализация основных операций над односвязным циклическим списком

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

procedure tCircleList.InsertHead(v:tValue);

Var

NewItem: pItem;

Begin

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

NewItem^.Value:= v;

if Empty

then begin // включение в пустой список

NewItem^.Next:= NewItem;

fHead:= NewItem; end

else begin // включение в непустой список

NewItem^.Next:= fHead^.Next;

fHead^.Next:=NewItem

end;

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

end; // procedure tCircleList.InsertHead

Включение элемента в конец циклического списка. При реализации метода можно использовать следующий прием – включить элемент в начало списка, а затем перенести указатель последнего элемента на включенный (следующий за ним) элемент:

procedure tCircleList.InsertRear(v: tValue);

Begin

InsertHead(v); // включение элемента в начало

// Перенос указателя последнего элемента на следующий элемент:

fHead:= fHead^.Next;

end; // procedure tCircleList.InsertRear

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

function tCircleList.DeleteHead: tValue;

Var

DisItem: pItem;

Begin

DisItem:= fHead^.Next; // исключаемый элемент - первый

DeleteHead:= DisItem^.Value; // чтение первого элемента списка

if fHead=DisItem // если в списке был один элемент,

then fHead:= nil // то после исключения список пуст,

else fHead^.Next:= DisItem^.Next; // иначе первым становится второй эл-т.

Dispose(DisItem); // удаление из памяти исключаемого эле мента

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

end; // function tCircleList.DeleteHead

Исключение элемента из конца циклического списка. Поскольку список является циклическим, то можно применить следующий прием. Сначала передвинуть указатель последнего элемента списка fHead на предшествующий ему элемент (предварительно определив указатель на этот элемент). При этом бывший последний элемент (который и нужно исключить) становится первым. Этот элемент можно исключить из списка с использованием метода исключения из начала DeleteHead.

function tCircleList.DeleteRear: tValue;

Var

Item: pItem;

Begin

// Перемещение указателя Item на предпоследний элемент списка

Item:= fHead;

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

fHead:= Item; // сдвиг fHead на предпоследний элемент

DeleteRear:= DeleteHead;

end; // function tCircleList.DeleteRear

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

Сцепление циклического списка с другим циклическим списком CList2 (подключение списка CList2 справа).

При реализации этой операции в виде метода класса tCircleList в метод Concat циклического списка необходимо передавать не указатель на первый элемент второго списка, а указатель на сам подсоединяемый список (CList2). При этом в методе нужно избежать прямого обращения к полям fHead и fSize класса CList2. Для обеспечения доступа к этим полям по чтению и записи в классе tCircleList свойства Head и Size должны быть доступны не только по чтению, но и по записи.

Метод класса tCircleList, реализующий сцепление описываемого списка с другим списком, реализуется следующим образом:

procedure tCircleList.Concat(var CList2: tCircleList);

Var

Head2, // указатель на начало второго списка

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

Begin

Head2:=CList2.Head; // получение указателя на начало второго списка

Item:= fHead^.Next; // сохранение указателя на начало общего списка

fHead^.Next:= Head2^.Next; // включение списка с указ. Head2 справа

fHead:= Head2; // перемещение fHead на последний элемент

fHead^.Next:= Item; // восстановление связи с первым элемен том

fSize:=fSize + CList2.Size; // вычисление размера общего списка

CList2.Head:= nil; CList2.Size:= 0; // список CList2 становится пустым

end ;//tCircleList.Concat

Если в приведенном выше методе исключить операцию перемещения указателя fHead на последний элемент включенного списка (fHead:= Head2), то список CList2 будет включен в список tCircleList слева.

9. Реализация линейного списка в виде двусвязной динамической структуры

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

Динамическая реализация линейного двусвязного списка имеет вид:

Переменные ссылочного типа Head и Rear указывают соответственно на начало и конец списка (на его крайний левый и крайний правый элементы). В конце каждого направления содержится указатель nil.

Работа с двусвязным линейным списком предполагает выполнение всех операций, определенных для односвязного линейного списка.

Описание класса tDCList (DCList – DoublyConnectedList):

Type

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

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

tItem= record // тип элемента двусвязного списка

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

Left, Right: pItem; // указатели на элементы слева и справа от текущего

end; // recordtItem

tDCList = class // класс – двусвязный список

Protected

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('Исключаемый элемент отсутствует')

Else begin

Addr:= Addr^.Right; DeleteRight:= Delete(Addr);

end;

end; // function tDCList.DeleteRight

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

Операции исключения элементов из двусвязного списка DeleteRight и Delete неприменимы к пустому списку; при их реализации предполагается, что Addr<>nil, и элемент с заданным адресом присутствует в списке.

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

11. Циклический двусвязный список

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

Над циклическим двусвязным списком могут быть выполнены все операции, определенные для циклического односвязного списка.

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

Type

tDCCircleList= class // класс - циклический двусвязный список

Protected

fHead: pItem; // поле - указатель на начало списка

fSize: Word; // поле - число элементов списка

Public

// Свойство - число элементов списка (доступ по чтению и записи)

property Size: Word read fSize write fSize;

// Свойство - указатель на начало списка (доступ по чтению и записи)

property Head: Word read fHead write fHead;

// Включение элемента со значением 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 в начало списка

procedure InsertHead(v: tValue);

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

procedure InsertRear(v: tValue);

function DeleteHead: tValue; // исключение из начала

function DeleteRear: tValue; // исключение из конца

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

function Search(v: tValue): pItem;

function Empty: Boolean; // возвращение true, если список пуст

procedure Clear; // очистка списка

// Присоединение списка DCList2 справа

procedure Concat(var DCList2: tDCCircleList);

constructor Create; // конструктор - создание пустого списка

destructor Destroy; override; // деструктор - удаление списка

end; // tDCCircleList

Класс tDCCircleList не является в данном описании наследником класса tDCList по следующим причинам:

– поле Rear класса tDCList не используется;

– вводится новая процедура Concat;

– все методы класса tDCCircleList реализуются иначе, чем одноименные методы класса tDCList.

12. Реализация основных операций над двусвязным циклическим списком

В этом разделе рассмотрим только новые для двусвязного циклического списка операции, реализацию методов, одноименных с методами класса tDCList, предлагается выполнить самостоятельно.

Метод класса tDCCircleList, реализующий включение элемента в конец двусвязного циклического списка, имеет вид:

procedure tDCCircleList.InsertRear(v: tValue);

Var

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

Begin

NewItem:= New(pItem);

NewItem^.Value:= v;

if Empty

then begin // включение в пустой список

NewItem^.Left:= NewItem;

NewItem^.Right:= NewItem;

fHead:= NewItem; end

else begin // включение в непустой список

NewItem^.Left:= fHead^.Left;

NewItem^.Right:= fHead;

fHead^.Left^.Right:=NewItem;

fHead^.Left:=NewItem;

end;

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

end; // procedure tDCCircleList.InsertRear

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

procedure tDCCircleList.InsertHead(v: tValue);

Begin

InsertRear(v); // включение элемента в конец

fHead:= fHead^.Left;

end; // procedure tDCCircleList.InsertHead

Метод класса tDCCircleList, реализующий исключение элемента из конца двусвязного циклического списка, имеет вид:

function tDCCircleList.DeleteRear: tValue;

Var

DisItem: pItem;

Begin

DisItem:= fHead^.Left; // исключаемый элемент - последний

DeleteLast:= DisItem^.Value; // чтение последнего элемента списка

if fHead=DisItem

then fHead:= nil // исключается единственный элемент

Else begin

fHead^.Left:= DisItem^.Left;

DisItem^.Left^.Right:=fHead; // последним становится предпоследний эл-т

end;

Dispose(DisItem);

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

end; // function tDCCircleList.DeleteRear

Исключение элемента из начала двусвязного циклического списка. При реализации этой операции сначала указатель первого элемента списка fHead передвигается на элемент, стоящий справа от него – бывший первый элемент (который и нужно исключить) становится последним. Его можно исключить из списка с использованием метода исключения справа DeleteRear. Метод класса tCDCircleList, реализующий исключение элемента слева, имеет вид:

function tDCCircleList.DeleteHead: tValue;

Begin

fHead:= fHead^.Right;

DeleteHead:= DeleteRear;

end; // function tDCCircleList.DeleteHead

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

Лабораторная работа 2.
Односвязные и двусвязные
линейные списки

Задание

Опишите классы-списки, необходимые для решения задачи, указанной в вашем варианте задания, и реализуйте его методы.

Составьте программу решения задачи с использованием динамических структур данных, реализованных в виде классов.

Варианты заданий

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

2. Сложение длинных чисел. Используя двусвязные циклические списки



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-26 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: