Печатать книгуПечатать книгу

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

Сайт: Информатикс
Курс: Структуры данных
Книга: Теоретический материал: стеки, очереди, кольца (Паскаль)
Напечатано:: Гость
Дата: Пятница, 27 Июнь 2025, 17:59

Оглавление

Стек. Отличия стека от списка. Основные операции со стеком

Сейчас Вы познакомитесь с одной из разновидностей обычного линейного списка – стеком. Этот вид списка очень часто используется в программировании.

Стек – это линейный список, в котором добавление новых элементов и удаление существующих производится только с одного конца, называемого вершиной стека.

Стек часто называют структурой LIFO (сокращение LIFO означает Last In – First Out, т.е. последним пришел – первым вышел). Это сокращение помогает запомнить механизм работы стека.

Изобразим стек графически:

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

Стек предполагает вставку и удаление элементов, поэтому он является динамической, постоянно меняющейся структурой.

Стеки довольно часто встречаются в практической жизни. Простой пример: детская пирамидка. Процесс ее сборки и разборки подобен процессу функционирования стека.

Итак, стек – это такой список, добавление или извлечение элементов которого происходит с начала и только с начала (или, возможно, с конца и только с конца) списка.

Значением указателя, представляющего стек, является ссылка на вершину стека, и каждый элемент стека содержит поле ссылки на соседний, "нижний" элемент.

Таким образом, описать стек можно следующим образом:

Type
  EXST = ^ST;
  ST = record
       Data : integer;
       Next : EXST;
  end;
Var
  Stack : EXST; {Текущая переменная}

Если стек пуст, то значение указателя равно Nil.

Рассмотрим возможные операции со стеком.

Занесение элемента в стек

Занесение элемента в стек производится аналогично вставке нового элемента в начало списка. Процедура занесения элемента в стек должна содержать два параметра: первый задает вершину стека, в который нужно занести элемент, второй – заносимое значение элемента стека.

Процедура формирования стека будет иметь следующий вид:

Procedure FormStack;
Var
  Stack : EXST; {Текущая переменная}
  Digit : integer;
Procedure writeStack(Var u : EXST; Digit : integer);
Var
  x : EXST;
Begin
  new(x); {выделяем память под хранение нового элемента стека}
  x^.Data := Digit; {заполняем поле данных элемента}
  x^.Next := u; {новый элемент "связываем" со стеком}
  u := x; {созданный элемент определяем как вершину стека}
End;
Begin
  Stack := Nil; {инициализация стека}
  writeln('Введите элементы стека. Окончание ввода – 0');
  read(Digit);
  while Digit <> 0 do
    begin
      writeStack(Stack, Digit);
      read(Digit);
    end;
End;

Извлечение элемента из стека

В результате выполнения этой операции некоторой переменной i должно быть присвоено значение первого элемента стека, и значение указателя на начало списка должно быть перенесено на следующий элемент стека.

Procedure readStack(Var u : EXST; Var i : integer);
Var
  x : EXST;
Begin
  i := u^.Data; {считываем значение поля данных в переменную}
  x := u; {запоминаем адрес вершины стека}
  u := u^.Next; {переносим вершину стека на следующий элемент}
  dispose(x); {освобождаем память, занятую уже ненужным элементом стека}
End.

Недостатком описанной процедуры является предположение о том, что стек не пуст. Для его исправления следует разработать логическую функцию, определяющую, пуст ли обрабатываемый стек.

Function FreeStack(u : EXST) : boolean;

Задание. Описать функцию и закончить программу, для чего описать процедуру вывода значений элементов стека на экран (она аналогична выводу списка). Протестировать программу, дополнить комментарием.

Примеры решения задач

Пример 1. Используя стек, напечатать содержимое текстового файла, выписывая литеры каждой его строки в обратном порядке.

Program MordovskihK;
Type
  EXST = ^ST;
  ST = record
       Data : char;
       Next : EXST;
  End;
Var
  Stack : EXST; {Текущая переменная}
  i : integer;
  f : text;
  Stroka : string;
  c : char;
Procedure writeStack(Var u : EXST; Simvol : char);
Var
  x : EXST;
Begin
  new(x);
  x^.Data := Simvol;
  x^.Next := u;
  u := x;
End;
Procedure Print(Var u : EXST);
Begin
  while u <> Nil do
    Begin
      write (u^.Data);
      u := u^.Next;
    End;
  End;
Begin
  Stack := Nil;
  Assign(f, 'c:\autoexec.bat');
  Reset(f);
  while Not Eof(f) do
    Begin
      readln (f, Stroka);
      For i := 1 to Length(Stroka) do
        writeStack(Stack, Stroka[i]);
      Print(Stack);
      writeln;
    End;
  close(f);
End.

Пример 2. Написать программу, проверяющую своевременность закрытия скобок в строке символов.

Для решения задачи определим стек, элементами которого являются символы:

Type
  EXST = ^ST;
  ST = record
       Data : char;
       Next : EXST;
  End;

Будем двигаться по строке а : string до ее конца. Если в процессе просмотра встретится одна из открывающих скобок ({, (, [ ), занесем ее в стек. При обнаружении закрывающей скобки, соответствующей скобке, находящейся в вершине стека, последняя удаляется. При несоответствии скобок выдается сообщение об ошибке.

Пусть факт наличия ошибки хранится в переменной логического типа f, то есть f=True, пока ошибка не найдена и f=False в противном случае. Тогда условие работы цикла будет выглядеть так:

while (i<>Length(a)) and f do ...

Осталось выяснить, как определить, соответствует ли очередная закрывающая скобка скобке, находящейся в вершине стека. Можно заметить, что коды соответствующих друг другу скобок отличаются не более чем на 2, что можно проверить с помощью функции Ord(x)):

{ } 123–125
[ ] 91–93
( ) 40–41,

причем код открывающей скобки меньше. Таким образом, можно записать следующее условие соответствия:

if (Ord(a[i])–Ord(stack^.Data))<=2
  then
    . . .

А теперь просмотрите полный текст программы:

Program Skobki;
Type
  EXST = ^ST;
  ST = record
       Data : char;
       Next : EXST;
  end;
Var
  a : string;
  f : boolean;
  i : integer;
Procedure writeStack(Var x1 : EXST; c : char);
Var
  u : EXST;
Begin
  new(u); {создание нового элемента стека}
  u^.Data := c;
  u^.Next := x1;
  x1 := u; {созданный элемент определить как вершину стека}
End;
Procedure DelStack(Var x1 : EXST); {процедура удаления верхнего элемента стека}
Var
  u : EXST;
Begin
  u := x1;
  x1 := x1^.Next;
  dispose(u);
End;
Procedure Solve(a : string); {проверка правильности расстановки скобок}
Var
  Stack : EXST;
Begin
  Stack := Nil;
  i := 1;
  while (i<=Length(a)) and f do
    begin
      if (a[i]='(') or (a[i]='{') or (a[i]='[')
        then
          writeStack(Stack , a[i])
        else
          if (a[i]=')') or (a[i]='}') or (a[i]=']')
            then
              if (Stack <> Nil) And (Ord(a[i]) - Ord(Stack ^.Data) <= 2)
                then
                  DelStack(Stack)
                else
                  f := False;
      Inc(i);
  end;
end;
Begin
  writeln('Введите строку');
  readln(a);
  f := True;
  if a<>''
    then
      begin
        Solve(a);
        if f
          then
            writeln('Все скобки расставлены верно')
          else
            writeln('Скобка ',a[i-1],' закрыта преждевременно');
      end
    else
      writeln('Строка пуста');
  readln;
End.

Задание. Разберите алгоритмы решения предложенных задач.

Очередь. Основные операции над очередью

Очередь – линейный список, элементы в который добавляются только в конец, а исключаются из начала.

Изобразим очередь графически:

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

Очередь является динамической структурой – с течением времени изменяется и колчество, и набор составляющих ее элементов.

Опишем очередь на языке программирования:

Type
  EXO = ^O;
  O = record
       Data : integer;
       Next : EXO;
  end;

Над очередью определены две операции: занесение элемента в очередь и извлечение элемента из очереди.

В очереди, в силу ее определения, доступны две позиции: ее конец, куда заносятся новые элементы, и ее начало, откуда извлекаются элементы. Поэтому для работы с очередью необходимо описать две переменные:

Var
BeginO, EndO : EXO;

где BeginO – соответствует началу очереди и будет использоваться для удаления элемента из очереди, EndO – соответствует концу очереди и будет использоваться для добавления новых элементов в очередь.

Занесение элемента в очередь

Занесение элемента в очередь реализуется как добавлению элемента в конец списка. Рассмотрите процедуру, описанную ниже.

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

Задание. Создайте программу формирования очереди с использованием предложенной процедуры.

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

Процедура извлечения элемента из очереди аналогична удалению элемента из начала списка. Поскольку извлечение элемента из пустой очереди осуществить нельзя, опишем логическую функцию, проверяющую, есть ли элементы в очереди.

Procedure readO(Var BeginO : EXO; Var c : integer);
Var
  u : EXO;
Function FreeO(x1 : EXO): boolean;
Begin
  FreeO := (x1 = Nil);
End;
Begin
  if FreeO(BeginO)
    then
      writeln('Очередь пуста')
    else
      begin
        c := BeginO^.Data; {считываем искомое значение в переменную с}
        u := BeginO; {ставим промежуточный указатель на первый элемент очереди}
        BeginO := BeginO^.Next;{указатель начала переносим на следующий элемент}
        dispose(u); {освобождаем память, занятую уже ненужным первым элементом}
      end;
End;

Задание. Напишите программу, содержащую все необходимые процедуры и функции работы с очередью.

Примеры решения задач

Задание. Рассмотрите приведенные программы. Наберите их на компьютере, дополните комментарием и протестируйте. Имейте в виду, что уже рассмотренные выше подпрограммы в текстах задач пропущены.

Пример 1. За один просмотр файла действительных чисел напечатать элементы файла в следующем порядке: сначала – все числа, меньшие а, затем – все числа из отрезка [а, b], и наконец – все остальные числа, сохраняя исходный порядок в каждой из этих трех групп чисел. Числа а и b задает пользователь.

Program MordovskihK;
Type
  EXO = ^O;
  O = record
       Data : real;
       Next : EXO;
  End;
Var
  i, a, b : Real;
  Min, Vibr, Other, EndMin, EndVibr, EndOther : EXO;
  f : File of real;
  Stroka : string;
Procedure writeO(Var BeginO, EndO : EXO; c : real);
  . . .
Procedure Print(u : EXO);
  . . .
Begin
  Min := Nil;
  Vibr := Nil;
  Other := Nil;
  EndMin := Nil;
  EndVibr := Nil;
  EndOther := Nil;
  writeln ('Введите имя файла >');
  readln(Stroka);
  writeln ('Введите промежуток >');
  readln(a, b);
  assign(f, Stroka);
  reset(f);
  while not Eof(f) do
    begin
      read(f, i);
        if i<a
          then
            writeO(Min, EndMin, i)
          else
            if (i>=a) and (i<=b)
              then
                writeO(Vibr, EndVibr, i)
              else
                writeO(Other, EndOther, i)
    end;
  close(f);
  writeln('Числа, меньшие ', а);
  Print(Min);
  writeln('Числа из промежутка [', а, ',' , b, ']');
  Print(Vibr);
  writeln('Числа, большие ', b);
  Print(Other);
End.

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

Program BaranovA;
Type
  EXO = ^O;
  O = record
       Data : char;
       Next : EXO;
  End;
Var
  O1, EndO1, O2, EndO2 : EXO;
  f1, f2 : text;
  Name, NewName, Stroka, NewStroka : string;
Procedure writeO(Var BeginO, EndO : EXO; c : char);
  . . .
Procedure readO(var u : EXO, var c: char);
  . . .
Procedure ModifStr(St : string; var NewSt : string);
Var
  i : integer;
  l : char;
begin
  O1 := Nil;
  EndO1 := Nil;
  O2 := Nil;
  EndO2 := Nil;
  NewSt := '';
  for i := 1 to Length(St) do
    if St[i] in ['1', '2', '3', '4', '5', '6', '7', '8', '8', '9', '0']
      then
        writeO(O2, EndO2, St[i])
      else
        writeO(O1, EndO1, St[i]);
  while O1 <> Nil do
    begin
      readO(O1, l);
      NewSt := NewSt + l;
    end;
  while O2 <> Nil do
    begin
      readO(O2, l);
      NewSt := NewSt + l;
    end;
End;
Begin
  write('Введите имя исходного файла: ');
  readln(Name);
  write('Введите имя файла-результата: ');
  readln(NewName);
  assign(f1, Name);
  assign(f2, NewName);
  reset(f1);
  rewrite(f2);
  while not Eof(f1) do
    begin
      readln(f1, Stroka);
      ModifStr(Stroka, NewStroka);
      writeln(f2, NewStroka);
    end;
  close(f1);
  close(f2);
End.

Кольцо. Формирование кольца. Основные операции над кольцом

Koльцо - это вид связанного списка, в котором указатель последнего элемента ссылается на первый элемент.

Рассмотрите его графическое представление.

К кольцу применим обход элементов, доступ возможен к любому элементу структуры.

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

Опишем кольцо на языке программирования:

Type
  TypeCircle = ^K;
  K = record
        Data : integer;
        Next : TypeCircle;
  End;
Var
  Circle1 : TypeCircle;

Формирование кольца

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

Procedure FofmK(Var u : TypeCircle);
Var
  x, y : TypeCircle;
  i, N, d : integer;
Begin
  write('Введите количество звеньев кольца: ');
  readln(N);
  for i := 1 to N do
    begin
      new(x); {выделяем память для хранения нового элемента кольца}
      write('Введите данные в звено: ');
      readln(d);
      x^.Data := d; {заносим информацию в поле данных}
      if u=nil {если кольцо еще не создано}
        then
          u := x {то указатель первого элемента ставим на новый элемент}
        else
          y^.Next := x; {присоединяем новый элемент к последнему элементу}
      y := x; {переносим указатель у на последний элемент}
    end;
  x^.Next := u; {преобразуем получившийся список в кольцо}
End;

Над кольцом определены три операции: занесение элемента в кольцо, извлечение элемента из кольца и обход кольца.

Задание. Составьте программу, содержащую две процедуры: процедуру занесения элемента в кольцо и процедуру извлечения элемента из кольца по какому-либо условию. (Можно воспользоваться текстом предыдущей программы.)

Обход кольца

Для того чтобы обойти кольцо и вывести на экран содержащуюся в нем информацию, необходимо в локальной переменной типа TypeCircle запомнить адрес первого выводимого элемента. В этом случае можно избежать повторения и зацикливания программы. Вывод данных можно начинать с любого элемента кольца; это зависит от адреса первого элемента, переданного в процедуру обхода.

Рассмотрите процедуру обхода кольца.

Procedure PrintК(u : TypeCircle);
Var
  x : TypeCircle;
Begin
  x := u;
  repeat
    write(x^.Data,' ');
    x := x^.Next;
  until x = u;
  readln;
End;

Задание. Составьте программу, использующую процедуры формирования и обхода кольца, дополните ее процедурой освобождения динамической памяти, выделенной для хранения кольца.

Решение задач с применением динамической структуры кольцо

Задание. Рассмотрите приведенную программу, наберите ее на компьютере, вставьте комментарий.

Задача 1.  N ребят располагаются по кругу. Начав отсчет от первого, удаляют каждого k-го, смыкая при этом круг. Определить порядок удаления ребят из круга.

Program Schitalka;
Type
  Children = ^Child;
  Child = record
       Name : string;
       Next : Children;
  end;
Var
  Circle, p, Temp : Children;
  k, i, j, NumName : integer;
  text : string;
Function NumSlov(Var S : string) : integer;
Var
  i, d : integer;
Begin
  d := 0;
  i := 1;
  while i <= Length(S) do
    begin
      while (S[i] = ' ') and (i <= Length(S)) do
        Inc(i);
      while (S[i] <> ' ') and (i <= Length(S)) do
        Inc(i);
      d := d+1;
    end;
  if S[Length(S)] = ' '
    then
      d := d-1;
  NumSlov := d;
End;
Procedure AddName(Var Old, Young : Children);
Begin
  Young^.Next := Old^.Next;
  Old^.Next := Young;
End;
Begin
  new(Circle);
  Circle^.Next := Circle;
  writeln('Считалка');
  writeln('Введите текст считалки >');
  readln(text);
  k := Numslov(text);
  writeln('Сколько человек в кругу? >');
  readln(NumName);
  temp := Circle;
  for i:= 1 to NumName do
    begin
      write('Введите ',i,'-е имя:');
      if i = 1
        then
          readln(Circle^.name)
        else
          begin
            new(p);
            readln(p^.name);
            AddName(temp, p);
            temp:=p;
          end;
    end;
  temp := Circle;
  for i := 1 to NumName-1 do
    begin
      for j := 1 to k-1 do
        begin
          p := temp;
          temp := temp^.next;
        end;
      writeln(temp^.name, '- вышел');
      p^.next:= temp.Next;
      dispose (temp);
      temp:=p^.Next;
    end;
  writeln(temp^.name, '- остался');
  dispose (temp);
end.