Решаем задачи Абрамян на Паскале. Pointer25

Pointer25. Даны две непустые очереди; адреса начала и конца первой равны $$P_1$$ и $$P_2$$, а второй — $$P_3$$ и $$P_4$$. Элементы каждой из очередей упорядочены по возрастанию (в направлении от начала очереди к концу). Объединить очереди в одну с сохранением упорядоченности элементов. Вывести указатели на начало и конец полученной очереди. Операции выделения и освобождения памяти не использовать, поля Data не изменять.

Решение:

program Pointer25;
type
  PNode=^TNode;
  TNode=record
    Data: Integer;
    Next: PNode;
//    Prev: PNode;
  end;

procedure CreateQueue(var P1,P2:PNode);
var
 pt1,pt2:PNode;
 i,N:integer;
begin
 Write('NumEl:');
 Readln(N);
 new(p1);
 Write('num: ');
 Readln(P1^.Data);
 pt2:=p1;

 for i:=1 to N-1 do
  begin
   new(pt1);
   Write('num: ');
   Readln(pt1^.Data);
   pt2.Next:=pt1;
   pt2:=pt2.Next;
  end;
 pt2.Next:=nil;
 p2:=pt2;
end;

procedure Blend(var P1,P2,P3,P4:PNode);
var
 Head,Tree :PNode;

begin
 if P1^.Data<P2^.Data then
  begin
   Head:=P1;
   P1:=P1^.Next;
  end
 else
  begin
   Head:=P2;
   P2:=P2^.Next;
  end;
 Tree:=Head;
 While(P1<>nil) and (P3<>nil) do
    begin
     if P1^.Data<P3^.Data then
      begin
       Tree^.Next:=P1;
       Tree:=Tree^.Next;
       if P1=P2 then
        begin
         P1:=nil;
         P2:=nil;
        end
       else P1:=P1^.Next;
      end
     else
      begin
       Tree^.Next:=P3;
       Tree:=Tree^.Next;
       if P3=P4 then
        begin
         P3:=nil;
         P4:=nil;
        end
       else P3:=P3.Next;
      end;
    end;
 if P1=nil then
  begin
   Tree^.Next:=P3;
   Tree:=P4;
  end
 else
  begin
   Tree^.Next:=P1;
   Tree:=P2;
  end;
 P1:=Head;
 P4:=Tree;
end;

var
 P1,P2,P3,P4:PNode;
 a:^Word;
begin

 CreateQueue(P1,P2);
 CreateQueue(P3,P4);

 blend(P1,P2,P3,P4);

 if p1=nil then Writeln('P1: nil')
 else
  begin
   a:=Addr(P1);
   Writeln('P1: ',a^);
  end;

 if p2=nil then Writeln('P4: nil')
 else
  begin
   a:=Addr(P4);
   Writeln('P4: ',a^);
  end;
end.

100

101

102

103

104

105

106

107

108

109

110

111

112

program Pointer25;

type

PNode=^TNode;

TNode=record

Data: Integer;

Next: PNode;

// Prev: PNode;

end;

procedure CreateQueue(var P1,P2:PNode);

var

pt1,pt2:PNode;

i,N:integer;

begin

Write('NumEl:');

Readln(N);

new(p1);

Write('num: ');

Readln(P1^.Data);

pt2:=p1;

for i:=1 to N-1 do

begin

new(pt1);

Write('num: ');

Readln(pt1^.Data);

pt2.Next:=pt1;

pt2:=pt2.Next;

end;

pt2.Next:=nil;

p2:=pt2;

end;

procedure Blend(var P1,P2,P3,P4:PNode);

var

Head,Tree :PNode;

begin

if P1^.Data<P2^.Data then

begin

Head:=P1;

P1:=P1^.Next;

end

else

begin

Head:=P2;

P2:=P2^.Next;

end;

Tree:=Head;

While(P1<>nil) and (P3<>nil) do

begin

if P1^.Data<P3^.Data then

begin

Tree^.Next:=P1;

Tree:=Tree^.Next;

if P1=P2 then

begin

P1:=nil;

P2:=nil;

end

else P1:=P1^.Next;

end

else

begin

Tree^.Next:=P3;

Tree:=Tree^.Next;

if P3=P4 then

begin

P3:=nil;

P4:=nil;

end

else P3:=P3.Next;

end;

if P1=nil then

begin

Tree^.Next:=P3;

Tree:=P4;

end

else

begin

Tree^.Next:=P1;

Tree:=P2;

end;

P1:=Head;

P4:=Tree;

end;

var

P1,P2,P3,P4:PNode;

a:^Word;

begin

CreateQueue(P1,P2);

CreateQueue(P3,P4);

blend(P1,P2,P3,P4);

if p1=nil then Writeln('P1: nil')

else

begin

a:=Addr(P1);

Writeln('P1: ',a^);

end;

if p2=nil then Writeln('P4: nil')

else

begin

a:=Addr(P4);

Writeln('P4: ',a^);

end;

end.

Другие задачи из раздела Pointer можно посмотреть здесь.

Комментарии 1

1. Решение для электронного задачника PT4:

program Dynamic25; //pabc.net
  
uses PT4;

type
  TQueue = record
    head, tail: PNode;
  end;

function QueueIsEmpty(Q: TQueue) := Q.head = nil;

function Peek(Q: TQueue) := Q.head^.data;

procedure MoveQueue(var Q1, Q2: TQueue);
begin
  if Q2.head <> nil then
  begin
    if Q1.head = nil then
      Q1.head := Q2.head
    else
      Q1.tail^.next := Q2.head;
    Q1.tail := Q2.tail;
    Q2.head := nil;
    Q2.tail := nil;
  end;
end;

procedure EnqueueNode(var Q: TQueue; p: PNode);
begin
  if p = nil then exit;
  if Q.tail = nil then
  begin
    Q.tail := p;
    Q.head := p
  end
  else
  begin
    Q.tail^.next := p;
    Q.tail := p;
  end;
end;

function DequeueNode(var Q: TQueue): PNode;
begin
  if Q.head = nil then exit;
  Result := Q.head;
  Q.head := Q.head^.next;
  if Q.head = nil then
    Q.tail := nil;
  Result^.next := nil;
end;

begin
  Task('Dynamic25');
  var Q1, Q2: TQueue;
  Read(Q1.head, Q1.tail, Q2.head, Q2.tail);
  var Q3: TQueue := (head: nil; tail: nil);
  
  while not QueueIsEmpty(Q1) do
  begin
    if QueueIsEmpty(Q2) then
      MoveQueue(Q3, Q1)
    else
    begin
      if Peek(Q1) < Peek(Q2) then
        EnqueueNode(Q3, DequeueNode(Q1))
      else
        EnqueueNode(Q3, DequeueNode(Q2))
    end
  end;
  
  MoveQueue(Q3, Q2);

  Writeln(Q3.head, Q3.tail)
end.

program Dynamic25; //pabc.net

uses PT4;

type

TQueue = record

head, tail: PNode;

end;

function QueueIsEmpty(Q: TQueue) := Q.head = nil;

function Peek(Q: TQueue) := Q.head^.data;

procedure MoveQueue(var Q1, Q2: TQueue);

begin

if Q2.head <> nil then

begin

if Q1.head = nil then

Q1.head := Q2.head

else

Q1.tail^.next := Q2.head;

Q1.tail := Q2.tail;

Q2.head := nil;

Q2.tail := nil;

end;

procedure EnqueueNode(var Q: TQueue; p: PNode);

begin

if p = nil then exit;

if Q.tail = nil then

begin

Q.tail := p;

Q.head := p

end

else

begin

Q.tail^.next := p;

Q.tail := p;

end;

function DequeueNode(var Q: TQueue): PNode;

begin

if Q.head = nil then exit;

Result := Q.head;

Q.head := Q.head^.next;

if Q.head = nil then

Q.tail := nil;

Result^.next := nil;

end;

begin

Task('Dynamic25');

var Q1, Q2: TQueue;

Read(Q1.head, Q1.tail, Q2.head, Q2.tail);

var Q3: TQueue := (head: nil; tail: nil);

while not QueueIsEmpty(Q1) do

begin

if QueueIsEmpty(Q2) then

MoveQueue(Q3, Q1)

else

begin

if Peek(Q1) < Peek(Q2) then

EnqueueNode(Q3, DequeueNode(Q1))

else

EnqueueNode(Q3, DequeueNode(Q2))

end

end;

MoveQueue(Q3, Q2);

Writeln(Q3.head, Q3.tail)

end.

2. Решение с заполнением очередей.
Все типы и подпрограммы описаны в модуле MyQueue. Большинство используемых подпрограмм можно увидеть выше, в решении для электронного задачника PT4. Остальные в Pointer22.

program Dynamic25; //pabc.net

uses MyQueue;

begin
  var Q1: TQueue := (head: nil; tail: nil);
  var Q2: TQueue := (head: nil; tail: nil);
  var Q3: TQueue := (head: nil; tail: nil);
  
  // создаем первую очередь
  foreach var data in Range(1, 20, 2) do
    Enqueue(Q1, data);
  
  // создаем вторую очередь
  foreach var data in Range(2, 10, 2) do
    Enqueue(Q2, data);
  
  while not QueueIsEmpty(Q1) do
  begin
    if QueueIsEmpty(Q2) then
      MoveQueue(Q3, Q1)
    else
    begin
      if Peek(Q1) < Peek(Q2) then
        EnqueueNode(Q3, DequeueNode(Q1))
      else
        EnqueueNode(Q3, DequeueNode(Q2))
    end
  end;
  
  MoveQueue(Q3, Q2);
  
  Writeln(Q3.head, ' ', Q3.tail)  
end.

program Dynamic25; //pabc.net

uses MyQueue;

begin

var Q1: TQueue := (head: nil; tail: nil);

var Q2: TQueue := (head: nil; tail: nil);

var Q3: TQueue := (head: nil; tail: nil);

// создаем первую очередь

foreach var data in Range(1, 20, 2) do

Enqueue(Q1, data);

// создаем вторую очередь

foreach var data in Range(2, 10, 2) do

Enqueue(Q2, data);

while not QueueIsEmpty(Q1) do

begin

if QueueIsEmpty(Q2) then

MoveQueue(Q3, Q1)

else

begin

if Peek(Q1) < Peek(Q2) then

EnqueueNode(Q3, DequeueNode(Q1))

else

EnqueueNode(Q3, DequeueNode(Q2))

end

end;

MoveQueue(Q3, Q2);

Writeln(Q3.head, ' ', Q3.tail)

end.

Ответить

Решаем задачи Абрамян на Паскале. Pointer25

Комментарии:

Комментарии 1

Добавить комментарий Отменить ответ