Инструменты и приборы для поиска и устранения неисправностей ПК

 end

end;

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

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

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

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

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

Данные четыре операции покроются  тремя вариантами вставки: в начало списка, в конец списка и между  двумя элементами списка. Общий алгоритм процедуры должен выглядеть следующим образом (ниже Тек_Ссылка означает ссылку на текущий элемент, а Пред_Ссылка √ значение ссылки на предшествующий):

1.    Установить значение Тек_Ссылка так, чтобы оно указывало на начало списка, положить значение Пред_Ссылка = nil и установить признак того, что положение вставляемого элемента не определено.

2.    Пока в списке остаются еще не просмотренные элементы и положение нового элемента не определено выполнять следующее: - если новый элемент следует за тем, на который указывает Тек_Ссылка, то положить значение Пред_Ссылка равным Тек_Ссылка и изменить значение Тек_Ссылка так, чтобы оно указывало на следующий элемент; - иначе установить признак того, что положение вставляемого элемента не определено.

3.    Если Пред_Ссылка= nil, то вставить элемент в начало списка. Если и Пред_Ссылка и Тек_Ссылка не равны nil, то вставить новый элемент между теми элементами, на которые указывают Пред_Ссылка и Тек_Ссылка. Если Пред_Ссылка не равна nil, а Тек_Ссылка= nil, то вставить новый элемент в конец списка.

procedure InclWithSort( NewElem: DynStr; var HeadOfStr: Pointer);

var

CurrAssoc, PredAssoc: DynStr; {соответственно Тек_Ссылка и Пред_Ссылка}  

IsFounded: Boolean;

begin  

CurrAssoc:= HeadOfStr;  

PredAssoc:= nil;  

IsFounded:= False;  

while ( CurrAssoc <> nil ) and not IsFounded do begin    

if NewElem^.Elem > CurrAssoc^.Elem then begin      

 {перейти к следующему элементу}      

PredAssoc:= CurrAssoc;      

 CurrAssoc:= CurrAssoc^.NextElem    

end      

else IsFounded:= True  

 end;  

{позиция вставки нового элемента  найдена}  

if PredAssoc= nil then begin    

{вставка нового элемента в  начало списка}    

 NewElem^.NextElem:= HeadOfStr;    

HeadOfStr:= NewElem  

end;  

if ( PredAssoc <> nil ) and ( CurrAssoc <> nil ) then begin    

 {вставка элемента между элементами, на которые указывают ссылки PredAssoc      

 CurrAssoc}    

NewElem^.NextElem:= PredAssoc^.NextElem;    

PredAssoc^.NextElem:= NewElem  

end;  

if ( PredAssoc <> nil ) and ( CurrAssoc= nil ) then begin    

{вставка в конец списка}    

PredAssoc^.NextElem:= NewElem;    

NewElem^.NextElem:= nil  

end

end;

2.2 Двунаправленные списки

Линейный список неудобен тем, что при попытке вставить некоторый элемент перед текущим  элементом, требуется обойти почти весь список, начиная с заголовка, чтобы изменить значение указателя в предыдущем элементе списка. Чтобы устранить данный недостаток вводится второй указатель в каждом элементе списка. Первый указатель связывает данный элемент со следующим, а второй √ с предыдущим. Такая организация динамической структуры данных получила название линейного двунаправленного списка (двусвязного списка). На рис. 2 приведена графическая интерпретация двунаправленного списка.

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

2.3 Циклические списки

Линейные списки характерны тем, что в них можно выделить первый и последний элементы, причем для однонаправленного линейного списка обязательно нужно иметь указатель на первый элемент. Циклические списки также как и линейные бывают однонаправленными и двунаправленными. Основное отличие циклического списка состоит в том, что в списке нет пустых указателей (см. рис 3).

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

В двунаправленном циклическом  списке система указателей аналогична системе указателей двунаправленного линейного списка (см. рис 4).

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

Разберем решение типичной задачи, связанной с обработкой списков.

Текст задания

С использованием списков, заданный во входном файле текст (за которым  следует точка) распечатать в  обратном порядке.

Решение

program reverse;

type   List= ^Elem;  

Elem= record    

Info: Char;    

Next: List  

end;

var  

L, p: List;  

 c: char;

begin  

{ввод литер текста  и запись их в обратном порядке  в список L (без заглавного звена)}  

L:= nil; {ссылка на построенную  часть списка}  

 read( c );  

while c <> '.' do begin    

 {добавить с в начало списка}    

 new( p );    

p^.Info:= c;    

p^.Next:= L;    

L:= p;    

read( c )  

end;  

{печать литер из L}  

 while L <> nil do begin    

write( L^.Info );    

L:= L^.Next  

end;  

writeln

end.

 

 

 

 

 

 

3. Очереди и стеки

Очередь и стек представляют собой структуры данных с фиксированными механизмами занесения и выбора элементов. Возможны реализации очереди и стека на базе регулярных или списковых структур данных. Соответственно представлению изменяется реализация механизмов обработки структур. Однако определяющими являются следующие принципы: очередь предполагает занесение нового элемента в конец, а выбор с начала списка (FIFO √ First In First Out); в стек элемент заносится в начало и выбирается также сначала (LIFO √ Last In First Out).

3.1 Очередь на базе списка 

Из механизма FIFO следует, что в очереди доступны два элемента √ первый и последний простая очередь (см. рис. 5).

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

type 

TypeOfElem= {}; 

Assoc= ^ElementOfQueue; 

ElementOfQueue= record   

Elem: TypeOfElem;   

NextElem: Pointer 

end; 

 Queue= Assoc;

3.2 Создание (очистка) очереди

Для создания новой пустой или очистки существующей очереди  достаточно присвоить  указателям на первый и последний элементы значение nil.

procedure CreateQueue ( var FirstElem, LastElem: Queue);

begin 

FirstElem:= nil; 

LastElem:= nil

end;

3.3 Проверка очереди на пустоту

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

function QueueIsClear( var FirstElem, LastElem: Queue ): Boolean;

begin 

QueueIsClear:= ( FirstElem= nil ) and ( LastElem= nil )

end;

3.4 Включение элемента в очередь

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

procedure IncludeInQueue( var FirstElem, LastElem: Queue; NewElem: TypeOfElem);

var  

ServiceVar: Queue;

begin  

{создание нового элемента}  

new( ServiceVar );  

ServiceVar^.Elem:= NewElem;  

ServiceVar^.NextElem:= nil;  

if ( FirstElem= nil ) and ( LastElem= nil ) then begin    

 {создать очередь из одного элемента}    

 FirstElem:= ServiceVar;    

LastElem:= ServiceVar  

end    

else begin      

 {созданный элемент поместить в конец очереди}      

 LastElem^.NextElem:= ServiceVar;      

LastElem:= ServiceVar    

end

end;

3.5 Выбор элемента из очереди

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

procedure SelectFromQueue( var FirstElem, LastElem: Queue; var Result: TypeOfElem);

var  

ServiceVar: Queue;

begin  

if not ( ( FirstElem= nil ) and ( LastElem= nil ) ) then begin    

Result:= FirstElem^.Elem;    

ServiceVar:= FirstElem;    

 {убираем 1-ый элемент из очереди}    

 FirstElem:= FirstElem^.NextElem;    

{был ли это последний элемент}    

if FirstElem= nil then      

LastElem:= nil;    

dispose( ServiceVar )  

end

end;

3.6 Стек на базе списка

Из механизма LIFO следует, что в стеке доступен только последний занесенный его элемент √ так называемая вершина стека. Главный элемент, представляющий весь список как единый объект, в случае стека оказывается лишним, его роль выполняет вершина стека. Элемент, занесенный в стек раньше других имеет ссылку nil (см. рис. 6).

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

type  

TypeOfElem= {};  

Assoc= ^ElementOfStack;  

ElementOfStack= record    

Elem: TypeOfElem;    

NextElem: Pointer  

end;  

 Stack= Assoc;     

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

3.7 Создание (очистка) стека

Для создания нового пустого  или очистки существующего стека  достаточно присвоить  указателю на первый его элемент (вершину) значение nil.

procedure CreateStack ( var StackHead: Stack);

begin  

StackHead:= nil

end;

3.8 Проверка стека на пустоту

Условием пустоты стека  является значение его вершины, равное nil.

function StackIsClear( var StackHead: Stack ): Boolean;

begin  

StackIsClear:= ( StackHead= nil )

end;

3.9 Занесение элемента в стек

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

procedure IncludeInStack( var StackHead: Stack; NewElem: TypeOfElem );

var  

ServiceVar: Stack;

begin  

{создание нового элемента}

&nbspnew( ServiceVar );  

 ServiceVar^.Elem:= NewElem;  

{созданный элемент  сделать вершиной стека}  

 ServiceVar^.NextElem:= StackHead;  

StackHead:= ServiceVar

end;

3.10 Выбор элемента из стека

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