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

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

Содержание



Переменная

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

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

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

Массив

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

Стек

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

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

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

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

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

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

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

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

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

занести элемент, второй — заносимое значение элемента стека.

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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