Списки, стеки и очереди.

Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом. Списки бывают с одной связью (указатель только на следующий элемент) и двухсторонней связью (указатель на следующий и предыдущий элемент). Рассмотрим первый вариант - односвязный список.

Функции работы со списками (см. http://informatics.mccme.ru/moodle/mod/book/view.php?id=535):

ADD - вставка в начало списка (добавление элементов)

INS - вставка в середину списка по возрастанию ключа
DELFIRST- удаление первого элемента
DEL - удаление элемента списка по ключу
SHOW- вывод (просмотр) списка.
ERASE - освобождение списка

Задача: вывести целые числа в порядке возрастания.
program project1;
type PtrSpisok=^RecSpisok;
RecSpisok = record
Data:integer;
next:PtrSpisok;
end;
var head:PtrSpisok;
a:integer;
procedure Show(head:PtrSpisok);
var tmp:PtrSpisok;
begin
tmp:=head; {Запомним адрес первого элемента списка}
while tmp<> nil do {Пока список не пустой}
begin
write(tmp^.data,' '); {выведем элемент списка}
tmp:=tmp^.next; {Перейдем на следующий элемент списка}
end;
end;
Procedure Add(D : integer; Var Head : PtrSpisok );
Var
tmp : PtrSpisok ;
Begin
New(tmp); {выделим место в памяти для переменной типа указатель на список PtrSpisok}
tmp^.data := D; {заполним поле Data первого элемента}
tmp^.Next := Head; {заполним поле Next на указатель первого элемента Head}
Head:= tmp;{установим указатель головы списка Head на первый элемент}
end;
Procedure Delfirst(Var Head : PtrSpisok );
Var
tmp : PtrSpisok ;
Begin
if Head<> nil then begin
tmp := Head; {Запомним адрес первого элемента списка}
Head := Head^.Next; {Теперь Head указывает на второй элемент списка}
Dispose(tmp); {Освободим память, занятую переменной tmp^}
end;
end;
Procedure Erase(Var Head : PtrSpisok );
Var
tmp : PtrSpisok ;
Begin
while Head<> nil do begin {До тех пор, пока список не пустой удаляем элемент с начала списка}
tmp := Head;
Head := Head^.Next;
Dispose(tmp);
end;
end;
Procedure Del(D: integer; Var Head : PtrSpisok);
Var
tmp, dx : PtrSpisok ;
Begin
tmp := head;
dx := Head;
while tmp<>Nil do
if tmp^.Data=D {Найдем адрес нужного элемента списка}
then begin
if tmp=head {Если это в начале списка}
then
delfirst(head)
else begin {Если в середине или в конце списка}
dx^.Next := tmp^.Next;
Dispose(tmp);
tmp := dx^.Next;
end;
end
else begin {Переходим к следующему элементу}
dx := tmp;
tmp := tmp^.Next;
end;
End;
Procedure Ins(D : integer; Var Head : PtrSpisok );
Var
tmp,dx,px : PtrSpisok ;
Begin
New(tmp);
tmp^.data := D;
tmp^.Next := Nil;
if Head = Nil {Если список пуст, то вставляем в начало}
then
Head := tmp
else Begin
dx := Head;
px := Head;
while (dx<>Nil) and (dx^.data<=D) do {Проверяем условие для вставки элемента в список, упорядоченный по возрастанию}
Begin
px := dx;
dx := dx^.Next;
End;
if dx=Nil {Если вставляем в конец списка}
then
px^.Next := tmp
else begin
tmp^.Next := dx;
if dx=Head {Если вставляем в начало списка}
then
Head := tmp
else {Если вставляем в середину списка}
px^.Next := tmp;
end;
end;
end;

begin
head:=nil;
read(a);
add(a,head);
while not eoln() do begin
read(a);
ins(a,head);
end;
readln;
write('spisok:'); show(head); readln;
erase(head);
end.

Задача.

В каждой строке сначала записан номер класса (число, равное 9, 10 или 11), затем (через пробел) – фамилия ученика. Необходимо вывести список школьников по классам: сначала всех учеников 9 класса, затем – 10, затем – 11. Внутри одного класса порядок вывода фамилий в алфавитном порядке. Окончание ввода данных с клавиатуры обеспечивается по нажатию клавиш Ctrl+Z, Enter.

Пример

Входные данные	Выходные данные
9 Иванов 10 Петров 11 Сидоров 9 Григорьев 9 Сергеев 10 Яковлев	9 Григорьев 9 Иванов 9 Сергеев 10 Петров 10 Сидоров 11 Яковлев

type string25=string[255];
PtrSpisok=^student;
student = record
 klass:integer;
 fio:string25;
 next:PtrSpisok;
end;

var
 first:PtrSpisok;
 a:integer;
 f:string25;

procedure show(var head:PtrSpisok);
var tmp:PtrSpisok;
begin
   tmp:=head;
   while tmp<> nil do
    begin
      writeln(tmp^.klass,' ',tmp^.fio);
      tmp:=tmp^.next;
      dispose(head);
      head:=tmp;
    end;
end;

Procedure Ins(Digit : integer;fio:string25; Var Head : PtrSpisok );
Var
  dx, px, x : PtrSpisok ;
Begin
  New(x);
  x^.klass := Digit;
  x^.fio:=fio;
  x^.Next := Nil;
  if Head = Nil
    then
      Head := x
    else
      Begin
        dx := Head;
        px := Head;
        while (dx<>Nil) and ((dx^.klass<Digit)or ((dx^.klass=Digit) and (dx^.fio<=fio)) )do
          Begin
            px := dx;
            dx :=dx^.Next;
          End;
        if dx=Nil
          then
            px^.Next := x
          else
            Begin
              x^.Next := dx;
              if dx=Head
                then
                  Head := x
                else
                  px^.Next := x;
            End;
      End;
end;

begin
 first:=nil;
 while not eof() do begin
   readln(a,f);
   ins(a,f,first);
 end;
 show(first);
end.

Стек - это организация данных по принципу последний вошел-первый вышел (Last In - First Out (LIFO )). Стек можно представить как узкий стакан или колодец, куда помещаются шарики, или в виде пирамидки в игре Баше, или нанизывание бусин на нитку.

Организация типа "стек" так же как для односвязного списка, но к этому виду списка неприменима операция обхода элементов.

Функции работы со стеком (см. http://informatics.mccme.ru/moodle/mod/book/view.php?id=543):
POP - втолкнуть в стек (добавление элемента вверх стека)

PUSH - вытолкнуть из стека (удалить элемент из вершины).

Задача: Правильная скобочная последовательность.
Рассмотрим последовательность, состоящую из круглых, квадратных и фигурных скобок. Программа дожна определить, является ли данная скобочная последовательность правильной.
Пустая последовательность явлется правильной. Если A – правильная, то последовательности (A), [A], {A} – правильные. Если A и B – правильные последовательности, то последовательность AB – правильная.
Если данная последовательность правильная, то программа должна вывести строку Yes, иначе строку No.

Пример

Входные данные	Выходные данные
([{}])	Yes
([)]	No
()()	Yes
())(	No

Type
PtrStack = ^RecStack; {описание стека}
RecStack = record

Data : char;
Next : PtrStack;
end;

Var
top: PtrStack;{указатель на начало (вершину) стека}

Procedure Pop(D : char; Var A : PtrStack);{"втолкнуть" (добавить) в стек}

Var
tmp : PtrStack;{временная переменная}
Begin
new(tmp); {выделяем память под хранение нового элемента стека}
tmp^.Data := D; {заполняем поля данных элемента}
tmp^.Next := A; {новый элемент "связываем" со стеком}

A := tmp; {созданный элемент определяем как вершину стека}

End;
Function Push(Var A : PtrStack) : char; {"вытолкнуть" (удалить) из стека}

Var
tmp : PtrStack;{временная переменная}
Begin
if A<>nil then begin {если стек не пустой}
push:= A^.Data; {возвращаем значение поля данных Data}
tmp := A; {запоминаем адрес вершины стека}
A := A^.Next; {переносим вершину стека на следующий элемент}
dispose(tmp); {освобождаем память, занятую уже ненужным элементом стека}
end else
push:=#0;

End;

Procedure Solve;
var tmp:char;{временная переменная}
Begin
top:= Nil; {инициализация стека}
while not eoln() do
begin

read(tmp);
case tmp of
'{','(','[':pop(tmp,top);
'}':if push(top)<>'{' then begin write('No'); exit; end;
']':if push(top)<>'[' then begin write('No'); exit; end;
')':if push(top)<>'(' then begin write('No'); exit; end;
end;
end;
if top=nil {если стек пустой, то это правильная скобочная последовательность}
then
write('Yes')
else begin
write('No');
while top<> nil do push(top);{очищаем память}
end;
end;

BEGIN
  Solve;
END.

Задача: Постфиксная запись числа.

В постфиксной записи (или обратной польской записи) операция записывается после двух операндов. Например, сумма двух чисел A и B записывается как A B +. Запись B C + D * обозначает привычое нам (B + C) * D, а запись A B C + D * + означает A + (B + C) * D. Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения. Необходимо вывести значение записанного выражения.

Пример

Входные данные	Выходные данные
8 9 + 1 7 - *	-102

Type
  PtrStack = ^RecStack;
  RecStack = record
             Data : integer;
             Next : PtrStack;
         end;
Var
  top: PtrStack;

Procedure Pop(D : integer; Var A : PtrStack);
Var
  tmp : PtrStack;
Begin
  new(tmp);
  tmp^.Data := D;
  tmp^.Next := A;
  A := tmp;
End;

Function Push(Var A : PtrStack) : integer;
Var
  tmp : PtrStack;
Begin
  if A<>nil then begin
    push:= A^.Data;
    tmp := A;
    A := A^.Next;
    dispose(tmp);
  end else
     push:=0;
End;

Procedure Solve;
var tmp:char;a,b,c:integer;
Begin
   c:=0;
   top:= Nil;
   while not eoln() do
   begin
        read(tmp);
        case tmp of
           '0'..'9':begin
             val(tmp,c,a);
             pop(c,top);
           end;
           '+':begin
            a:=push(top);
            b:=push(top);
            c:=a+b;
            pop(c,top);
           end;
           '-':begin
            a:=push(top);
            b:=push(top);
            c:=b-a;
            pop(c,top);
           end;
           '*':begin
            a:=push(top);
            b:=push(top);
            c:=a*b;
            pop(c,top);
           end;
        end;
   end;
   write(push(top));
   end;

BEGIN
   Solve;
END.  

 

Очередь – линейный список, элементы в который добавляются только в конец, а исключаются из начала (First In - First Out (FIFO)).  Очередь – это вид связанного списка, в котором извлечение элементов происходит с начала списка, а добавление новых элементов – с конца. Как и для стека к этому виду списка неприменима операция обхода элементов.

 

Функции работы с очередью (см. http://informatics.mccme.ru/moodle/mod/book/view.php?id=543&chapterid=278):

ADD - вставка в начало очереди (добавление элементов)

DEL - извлечение элемента из очереди

Задача: Игра в пьяницу.

В игре в пьяницу карточная колода раздается поровну двум игрокам. Далее они вскрывают по одной верхней карте, и тот, чья карта старше, забирает себе обе вскрытые карты, которые кладутся под низ его колоды. Тот, кто остается без карт – проигрывает. Для простоты будем считать, что все карты различны по номиналу, а также, что самая младшая карта побеждает самую старшую карту ("шестерка берет туза"). Игрок, который забирает себе карты, сначала кладет под низ своей колоды карту первого игрока, затем карту второго игрока (то есть карта второго игрока оказывается внизу колоды).

Напишите программу, которая моделирует игру в пьяницу и определяет, кто выигрывает. В игре участвует 10 карт, имеющих значения от 0 до 9, большая карта побеждает меньшую, карта со значением 0 побеждает карту 9.

Программа получает на вход две строки: первая строка содержит 5 карт первого игрока, вторая – 5 карт второго игрока. Карты перечислены сверху вниз, то есть каждая строка начинается с той карты, которая будет открыта первой.

Программа должна определить, кто выигрывает при данной раздаче, и вывести слово first или second, после чего вывести количество ходов, сделанных до выигрыша. Если на протяжении 10⁶ ходов игра не заканчивается, программа должна вывести слово botva.

Пример Входные данные   Выходные данные
1 3 5 7 9                    second 5
2 4 6 8 0

type
  PtrQueue = ^RecQueue;
  RecQueue = record
       Data : integer;
       Next : PtrQueue;
  end;

var x01,x02,x1,x2:PtrQueue;a:integer;

Procedure add(Var BeginO, EndO : PtrQueue; c : integer);
Var
  tmp : PtrQueue;
Begin
  new(tmp);
  tmp^.Data := c;
  tmp^.Next := Nil;
  if BeginO = Nil {проверяем, пуста ли очередь}
    then
      BeginO := tmp {ставим указатель начала очереди на первый созданный элемент}
    else
      EndO^.Next := tmp; {ставим созданный элемент в конец очереди}
  EndO := tmp; {переносим указатель конца очереди на последний элемент}
End;

function del(Var BeginO : PtrQueue; Var c : integer):boolean;
Var
  tmp : PtrQueue;
Begin
  del:=false;
  if BeginO = Nil
    then
      del:=true
    else
      begin
        c := BeginO^.Data; {считываем искомое значение в переменную с}
        tmp := BeginO; {ставим промежуточный указатель на первый элемент очереди}
        BeginO := BeginO^.Next;{указатель начала переносим на следующий элемент}
        dispose(tmp); {освобождаем память, занятую уже ненужным первым элементом}
        if begino=nil then del:=true;
      end;
End;

var a1,a2,i,k:integer;t1,t2:boolean;
begin
 x01:=nil;x02:=NIL;
 x1:=nil;x2:=NIL;
 for i:=1 to 5 do
 begin
   read(a);
   add(x01,x1,a);
 end;
 readln;
 for i:=1 to 5 do
 begin
   read(a);
   add(x02,x2,a);
 end;
  k:=0;
  for i:=0 to 1000001 do
  begin   inc(k);
   t1:=del(x01,a1);
   t2:=del(x02,a2);
   if ((a1>a2)and (a2<>0))or ((a1>a2)and (a1<>9))or((a1=0)and(a2=9))
     then begin
       add(x01,x1,a1);
       add(x01,x1,a2);
       if t2 then begin writeln('first ', k);exit; end;
   end else begin
       add(x02,x2,a1);
       add(x02,x2,a2);
       if t1 then begin writeln('second ', k);exit;end;
   end;
  end;
  writeln('botva');
end.

Задача.  Из заданного текста перенести все цифры в конец каждой строки, сохранив их порядок.

Type
PtrQueue = ^RecQueue;
RecQueue = record
  Data : char;
  Next : PtrQueue;
end;

Var
f1, f2 : text;
Stroka, NewStroka : string;

Procedure add(Var BeginO, EndO : PtrQueue; c : char);
Var
tmp : PtrQueue;
Begin
  new(tmp);
  tmp^.Data := c;
  tmp^.Next := Nil;
  if BeginO = Nil
  then
   BeginO := tmp
  else
   EndO^.Next := tmp;
  EndO := tmp;
End;

function del(Var BeginO: PtrQueue; Var c : char):boolean;
Var
tmp : PtrQueue;
Begin
  del:=false;
  if BeginO = Nil
  then
   del:=true
  else begin
   c := BeginO^.Data;
   tmp := BeginO;
   BeginO := BeginO^.Next;
   dispose(tmp);
   if begino=nil then del:=true;
  end;
End;

Procedure ModifyStr(St : string; var NewSt : string);
Var
i : integer;
l : char;
O1, EndO1, O2, EndO2 : PtrQueue;
begin
O1 := Nil;
EndO1 := Nil;
O2 := Nil;
EndO2 := Nil;
NewSt := '';
for i := 1 to Length(St) do
if St[i] in ['0'..'9']
then
add(O2, EndO2, St[i])
else
add(O1, EndO1, St[i]);
while O1 <> Nil do
begin
del(O1, l);
NewSt := NewSt + l;
end;
while O2 <> Nil do
begin
del(O2, l);
NewSt := NewSt + l;
end;
End;

Begin
  assign(f1,'input.txt');reset(f1);
  assign(f2, 'output.txt');rewrite(f2);
  while not Eof(f1) do
  begin
   readln(f1, Stroka);
   ModifyStr(Stroka, NewStroka);
   writeln(f2, NewStroka);
  end;
  close(f1);
  close(f2);
End.