Переменная. Массив. Стек
Структура данных — программная единица, позволяющая хранить и обрабатывать множество однотипных и/или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих её интерфейс. Рассмотрим некоторые структуры данных.
Содержание
Переменная
Переменная — именованный элемент программы, который может менять свое значение. Перед употреблением переменная должна быть объявлена в разделе переменных var. При объявлении должен быть указан тип переменной, задающий размер памяти для нее. Переменные могут быть:
- Глобальные. Объявляются в главной программе. Место под них выделяется компилятором в статической памяти на все время выполнения программы. Они доступны и во вложенных подпрограммах, если там нет локальных переменных с таким же именем.
- Локальные. Действуют в пределах подпрограммы, где они объявлены. Место под них выделяется в стеке на время выполнения подпрограммы. Стек – память для отложенных значений. При завершении подпрограммы переменная освобождается, а при повторном обращении к подпрограмме создается заново.
- Динамические. Создаются при исполнении программы в динамической памяти. Компилятор в статической памяти создает под них указатель для занесения адреса начала данных. Размер указателя 4 байта.
Переменные получают значения с помощью операторов присваивания.
Массив
Массив — это одно- или многомерная таблица данных одного типа. Каждая ячейка таблицы имеет свой индекс (в одномерном случае) или набор индексов (в многомерном). Массив называют структурой данных со случайным доступом, поскольку к любому элементу массива можно обратиться, просто указав его индексы, т.е. все элементы одинаково доступны в любой момент времени. Массив определяется, прежде всего, общим типом его элементов и их количеством. Количество элементов массива, в свою очередь, определяется количеством индексов и диапазоном их изменения.
Стек
Стек — структура данных, представляющая собой последовательность элементов. Добавление и удаление элементов происходит только с одного конца последовательности, т.е. при изменении структуры предыдущая последовательность остается неизменной. Т.о. стек работает по принципу FILO (First-In, Last-Out).
Стеки довольно часто встречаются в практической жизни. Простой пример: детская пирамидка. Процесс ее сборки и разборки подобен процессу функционирования стека.
Итак, стек – это такой список, добавление или извлечение элементов которого происходит с начала и только с начала (или, возможно, с конца и только с конца) списка.
Значением указателя, представляющего стек, является ссылка на вершину стека, и каждый элемент стека содержит поле ссылки на соседний, «нижний» элемент.
Таким образом, описать стек можно следующим образом:
1 2 3 4 5 6 7 8 |
Type EXST = ^ST; ST = record Data : integer; Next : EXST; end; Var Stack : EXST; {Текущая переменная} |
Если стек пуст, то значение указателя равно Nil.
Рассмотрим возможные операции со стеком.
Занесение элемента в стек
Занесение элемента в стек производится аналогично вставке нового элемента в начало списка. Процедура занесения элемента в стек должна содержать два параметра: первый задает вершину стека, в который нужно
занести элемент, второй — заносимое значение элемента стека.
Процедура формирования стека будет иметь следующий вид:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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 должно быть присвоено значение первого элемента стека, и значение указателя на начало списка должно быть перенесено на следующий элемент стека.
1 2 3 4 5 6 7 8 9 |
Procedure readStack(Var u : EXST; Var i : integer); Var x : EXST; Begin i := u^.Data; {считываем значение поля данных в переменную} x := u; {запоминаем адрес вершины стека} u := u^.Next; {переносим вершину стека на следующий элемент} dispose(x); {освобождаем память, занятую уже ненужным элементом стека} End. |
Недостатком описанной процедуры является предположение о том, что стек не пуст. Для его исправления следует разработать логическую функцию, определяющую, пуст ли обрабатываемый стек.
1 |
Function FreeStack(u : EXST) : boolean; |
Практическая часть
Написать программу, проверяющую своевременность закрытия скобок в строке символов.
Для решения задачи определим стек, элементами которого являются символы:
1 2 3 4 5 6 |
Type EXST = ^ST; ST = record Data : char; Next : EXST; End; |
Будем двигаться по строке а : string до ее конца. Если в процессе просмотра встретится одна из открывающих скобок ({, (, [ ), занесем ее в стек. При обнаружении закрывающей скобки, соответствующей скобке, находящейся в вершине стека, последняя удаляется. При несоответствии скобок выдается сообщение об ошибке.
Пусть факт наличия ошибки хранится в переменной логического типа f, то есть f=True, пока ошибка не найдена и f=False в противном случае. Тогда условие работы цикла будет выглядеть так:
1 |
while (i<>Length(a)) and f do ... |
Осталось выяснить, как определить, соответствует ли очередная закрывающая скобка скобке, находящейся в вершине стека. Можно заметить, что коды соответствующих друг другу скобок отличаются не более чем на 2, что можно проверить с помощью функции Ord(x)):
1 2 3 |
{ } 123–125 [ ] 91–93 ( ) 40–41, |
причем код открывающей скобки меньше. Таким образом, можно записать следующее условие соответствия:
1 2 3 |
if (Ord(a[i])–Ord(stack^.Data))<=2 then . . . |
А теперь просмотрите полный текст программы:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
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. |
Используя стек, напечатать содержимое текстового файла, выписывая литеры каждой его строки в обратном порядке.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
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. |