Переменная. Массив. Стек

tux 2012.09.18 Структуры данных https://tux.org.ua/?p=562 3659 0

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

Переменная

Переменная — именованный элемент программы, который может менять свое значение. Перед употреблением переменная должна быть объявлена в разделе переменных var. При объявлении должен быть указан тип переменной, задающий размер памяти для нее. Переменные могут быть:

Глобальные. Объявляются в главной программе. Место под них выделяется компилятором в статической памяти на все время выполнения программы. Они доступны и во вложенных подпрограммах, если там нет локальных переменных с таким же именем.
Локальные. Действуют в пределах подпрограммы, где они объявлены. Место под них выделяется в стеке на время выполнения подпрограммы. Стек – память для отложенных значений. При завершении подпрограммы переменная освобождается, а при повторном обращении к подпрограмме создается заново.
Динамические. Создаются при исполнении программы в динамической памяти. Компилятор в статической памяти создает под них указатель для занесения адреса начала данных. Размер указателя 4 байта.

Переменные получают значения с помощью операторов присваивания.

Массив

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

Стек

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

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

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

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

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

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

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;

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.

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	Function FreeStack(u : EXST) : boolean;

Практическая часть

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

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

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

Type

EXST = ^ST;

ST = record

Data : char;

Next : EXST;

End;

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

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

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

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

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

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

{ } 123–125

[ ] 91–93

( ) 40–41,

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

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

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.

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;

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.

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

Program Obratka;
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, '--== ПУТЬ К ФАЙЛУ ==--');
   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.

Program Obratka;

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, '--== ПУТЬ К ФАЙЛУ ==--');

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.

pascal, массив, переменная, стек

Очередь

#:

Переменная. Массив. Стек

Содержание

Переменная

Массив

Стек

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

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

Практическая часть

Похожие материалы:

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