Теоретический материал: списки (Паскаль)

Пример задачи, решаемой с помощью списка

Задание. Ознакомьтесь с предложенной программой и объясните алгоритм решения задачи. Если необходимо, наберите программу на компьютере и просмотрите, как она работает.

Задача 1. Проверить встречается ли (и сколько раз)  непустой список М1 в непустом списке М2.

Program BaranovA;
Uses
  Crt;
Type
  EXS = ^S;
  S = Record
       Data : integer;
       Next : EXS;
  End;
Var
  m1, m2 : EXS;
  Kol : integer;
Procedure Poisk(Var x1, x2 : EXS);
Var
  m3, m4 : EXS;
Begin
  Kol := 0;
  m3 := x1;
  m4 := x2;
  while m4 <> Nil do
    Begin
      if m4^.Data = m3^.Data
        then
          Begin
            m3 := m3^.Next;
            m4 := m4^.Next;
            if m3 = Nil
              then
                Begin
                  Kol := Kol+1;
                  m3 := x1;
                End;
          End
        else
          Begin
            m3 := x1;
            m4 := m4^.Next;
          End;
      End;
End;
Procedure Init (Var u : EXS);
Var
  x, y : EXS;
  Digit : integer;
Begin
  Writeln('Введите список. Конец ввода – 0');
  u := Nil;
  Read(Digit);
  while Digit <> 0 do
    Begin
      New(y);
      y^.Next := Nil;
      y^.Data := Digit;
      if u = Nil
        then
          u := y
        else
          x^.Next := y;
      x := y;
      Read(Digit);
    End;
  Writeln;
End;
Procedure Print(X : EXS);
Begin
  while X <> Nil do
    Begin
      Write(X^.Data : 5);
      X := X^.Next;
    End;
  Readln;
  Writeln;
End;
Begin
  ClrScr;
  Init(m1);
  Init(m2);
  Writeln('***Список 1***');
  Print(m1);
  Writeln('***Список 2***');
  Print(m2);
  Poisk(m1, m2);
  Writeln('Список 1 встречается в списке 2 ', Kol, ' раз(а)');
  Readln;
End.