Динамические структуры данных. Задание практикума. Язык Паскаль. Вылиток А.А - 32 стр.

UptoLike

- 32 -
Для решения данной задачи достаточно изменить ссылки так, чтобы
звенья в цепочке расположились в обратном порядке. Для этого в поле next
первого звена следует записать nil, тем самым сделав его последним; в поле
next второго звена записать ссылку на бывшее первое звено и далее
аналогично поступать с остальными звеньями, пока не дойдём до последнего.
Чтобы бывшее последним звено стало первым, надо присвоить ссылку на него
переменной L, представляющей список.
procedure reverse(var L:list);
{ переворачивает список L, т.е. изменяет ссылки в этом
списке так, чтобы его элементы оказались расположенными
в обратном порядке }
var p,q:link;
begin
if L<>nil {если L=nil, результатом будет пустой список}
then
begin p:=L; q:=L.next;
L.next:=nil; {первое звено становится последним}
while q<>nil {пока есть следующее звено} do
begin L:=q; {перешли к новому звену; L – указы-
вает на текущее звено, p – на предыдущее }
q:=q.next; {запомнили ссылку на хвост
списка }
L.next:=p; {соединили текущее звено с
предыдущим}
p:=L {запомнили ссылку на текущее звено}
end
end
end;
Задача 6. Описать процедуру in_order(L,x), которая в список L
упорядоченных по неубыванию целых чисел вставляет элемент x, сохраняя
упорядоченность.
Решение
procedure in_order(var L:list; x:elemtype);
{вставляет x в список L упорядоченных по неубыванию целых
чисел, сохраняя упорядоченность(elemtype=integer)}
var p,q:link;
begin
{создать звено для хранения элемента}
new(p);
if L = nil then {вставка в пустой список}
begin p.elem:= x;
p.next:= nil;
L:= p
end
      Для решения данной задачи достаточно изменить ссылки так, чтобы
звенья в цепочке расположились в обратном порядке. Для этого в поле next
первого звена следует записать nil, тем самым сделав его последним; в поле
next второго звена записать ссылку на бывшее первое звено и далее
аналогично поступать с остальными звеньями, пока не дойдём до последнего.
Чтобы бывшее последним звено стало первым, надо присвоить ссылку на него
переменной L, представляющей список.

procedure reverse(var L:list);
{ переворачивает список L, т.е. изменяет ссылки в этом
  списке так, чтобы его элементы оказались расположенными
  в обратном порядке }
var p,q:link;
begin
  if L<>nil {если L=nil, результатом будет пустой список}
    then
      begin p:=L; q:=L↑.next;
        L↑.next:=nil; {первое звено становится последним}
        while q<>nil {пока есть следующее звено} do
          begin L:=q; {перешли к новому звену; L – указы-
                вает на текущее звено, p – на предыдущее }
                q:=q↑.next; {запомнили ссылку на хвост
                             списка }
                L↑.next:=p; {соединили текущее звено с
                             предыдущим}
                p:=L {запомнили ссылку на текущее звено}
          end
      end
end;

Задача 6. Описать процедуру in_order(L,x), которая в список L
упорядоченных по неубыванию целых чисел вставляет элемент x, сохраняя
упорядоченность.
                                Решение
procedure in_order(var L:list; x:elemtype);
{вставляет x в список L упорядоченных по неубыванию целых
 чисел, сохраняя упорядоченность(elemtype=integer)}
var p,q:link;
begin
{создать звено для хранения элемента}
  new(p);
  if L = nil then {вставка в пустой список}
    begin p↑.elem:= x;
          p↑.next:= nil;
          L:= p
    end


                                  - 32 -