Динамические структуры: однонаправленные (односвязные) списки

Ответы:
1. Динамические структуры:

• 
  однонаправленные (односвязные) списки;
  
• 
  двунаправленные (двусвязные) списки;
  
• 
  циклические списки;
  
• 
  стек;
  
• 
  дек;
  
• 
  очередь;
  
• 
  бинарные деревья.
  

2. Отличия особенность динамических объектов можно считать следующих:

• 
  порождаются непосредственно перед выполнением программы;
  
• 
  возникают уже в процессе выполнения программы (верный);
  
• 
  задаются в процессе выполнения программы.
  

3.
Экземпляры объктного типа, подобно переменным, могут размещаться в динамической области (heap). В этом случае принято говорить о динамических объектах. Кроме того, объектный тип можно использовать в качестве компонент динамических (рекурсивных) структур данных, если среди полей данных предусмотрено поле, которое является ссылкой на этот же тип объекта.

4.
Элемент динамической структуры состоит из двух полей: Информационног поля или поля данных. В котором содержится те данные, ради которых и создается структура. Информационное поле само является интегрированной структурой – вектором, массивом, другой динамической структурой. Поле связок, в котором содержится один или несколько указателей, связываюших данных элемент с другими элементами структуры. С этого можно сделать вывод что элементы связываются между собой с помошью ссылок. Переменная типа «указатель» в качестве своего значения содержит адрес участка динамической памяти, с которой связан этот указатель.

5.

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

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

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

8.
Операции над двусвязными списками:

— cоздание элемента списка;
— поиск элемента в списке;
— вставка элемента в указанное место списка;
— удаление из списка заданного элемента.
Простейшие операции, производимые над односвязными списками
1) Вставка в начало односвязного списка.
Надо вставить в начало односвязного списка элемент с информационным полем D. Для этого необходимо сгенерировать пустой элемент (P=GetNode). Информационному полю этого элемента присвоить значение D (INFO(P)=D), значению указателя на этот элемент присвоить значение указателя на начало списка (Ptr(P) = Lst), значению указателя начала списка присвоить значение указателя P (Lst = P).
2) Удаление элемента из начала односвязного списка.
Надо удалить первый элемент списка, но запомнить информацию, содержащуюся в поле Info этого элемента. Для этого введем указатель P, который будет указывать на удаляемый элемент (P = Lst). В переменную X занесем значение информационного поля Info удаляемого элемента (X=Info(P)). Значению указателя на начало списка присвоим значение указателя следующего за удаляемым элемента (Lst = Ptr(P)). Удалим элемент (FreeNode(P)).

9.

10.
По указателю осуществляется обращение (доступ) к объекту.
Определение переменной типа указатель:
type *имя_указателя ;
где type – обозначение типа, на который будет указывать переменная с именем
(идентификатором) имя_указателя. Символ ‘*’ - это унарная операция раскрытия
ссылки (операция разыменования, операция обращения по адресу, операция
доступа по адресу), но в данном контексте служит признаком типа указатель.

11.
Стековые операции, применимые к спискам

1). Чтобы добавить элемент в стек, надо в алгоритме заменить указатель Lst на указатель Stack (операция Push(S, X)).
P = GetNode
Info(P) = X
Ptr(P) = Stack
Stack = P
2) Проверка стека на пустоту (Empty(S))
If Stack = Nil then Print “Стек пуст”
Stop
3) Выборка элемента из стека (POP(S))
P = Stack
X = Info(P)
Stack = Ptr(P)
FreeNode(P)
Реализация на Паскале:
Стек
Вместо указателя Lst используется указатель Stack
Процедура Push (S, X)
procedure Push(var Stack: PNode; X: Integer);
var
P: PNode;
begin
New(P);
P^.Info:=X;
P^.Next:=Stack;
Stack:=P;
end;
Проверка на пустоту (Empty)
function Empty(Stack: PNode): Boolean;
begin
If Stack = nil then Empty:=True Else Empty:=False;
end;
Процедура Pop
procedure Pop(var X: Integer; var Stack: PNode);
var
P: PNode;
begin
P:=Stack;
X:=P^.Info;
Stack:=P^.Next;
Dispose(P);
end;


12.
Операции с очередью, применимые к спискам.
Указатель начала списка принимаем за указатель начала очереди F, а указатель R, указывающий на последний элемент списка — за указатель конца очереди.
1) Операция удаления из очереди (Remove(Q, X)).
Операция удаления из очереди должна проходить из ее начала.
P = F
F = Ptr(P)
X = Info(P)
FreeNode(P)
2) Проверка очереди на пустоту. (Empty(Q))
If F = Nil then Print “Очередь пуста”
Stop
3) Операция вставки в очередь. (Insert(Q, X))
Операция вставки в очередь должна осуществляться к ее концу.
P = GetNode
Info(P) = X
Ptr(P) = Nil
Ptr(R)= P
R = P
Реализация на Паскале:
procedure Remove(var X: Integer; Fr: PNode);
var
P: PNode;
begin
New(P);
P:=Fr;
X:=P^.Info;
Fr:=P^.Next;
Dispose(P);
end;
function Empty(Fr: PNode): Boolean;
begin
If Fr = nil then Empty:=True Else Empty:=False;
end;
procedure Insert(X: Insert; var Re: PNode);
var
P: PNode;
begin
New(P);
P^.Info:=X;
P^.Next:=nil;
Re^.Next:=P;
end;

13. Операции над списками:

— cоздание элемента списка;
— поиск элемента в списке;
— вставка элемента в указанное место списка;
— удаление из списка заданного элемента;
— вставка в начало односвязного списка;
— удаление элемента из начала односвязного списка.

14.
Пусть нам необходимо создать пустой список по типу стека с указателем начала списка — AVAIL. Разработаем процедуры, которые позволят нам создавать пустой элемент списка и освобождать элемент из списка.

Операция GetNode. Разработаем процедуру, которая будет создавать пустой элемент списка с указателем Р.
Для реализации операции GetNode необходимо указателю сгенерированного элемента присвоить значение указателя начала свободного списка, а указатель начала перенести к следующему элементу.
P = Avail
Avail = Ptr(Avail)
Перед этим надо проверить, есть ли элементы в списке. Пустота свободного списка (Avail = Nil), эквивалентна переполнению функционального списка.
If Avail = Nil then Print “Переполнение” Stop
Else
P = Avail
Avail = Ptr(Avail)
Endif
Операция FreeNode. При освобождении элемента Nod(P) из функционального списка операцией FreeNode(P), он заносится в свободный список.
Ptr(P) = Avail
Avail = P


15.