16.2. Работа со стеком
Стек – это структура данных, организованная по принципу «первый вошел – последний вышел». Образно это можно представить как запаянную с одной стороны трубку, в которую закатываются шарики:
Первый шарик всегда будет доставаться из трубки последним. Элементы в стек можно добавлять или извлекать только через его вершину. Программно стек реализуется в виде однонаправленного списка с одной точкой входа (вершиной стека).
Для работы со стеком можно определить следующий тип:
Type Tps=^Ts; // Указатель на запись
Ts=Record; // Сама запись элемента стека
inf:TInf; // Информационная часть элемента стека,
// например Tinf=String
Ps: Tps; // Указатель на предыдущий элемент стека
End;
Графически стек с тремя элементами можно представить следующим образом:
Рис.16.1. Структура стека
Здесь P – указатель на вершину стека. Самый первый элемент стека не имеет впереди себя других элементов, поэтому в указатель Ps записывается пустой указатель – Nil. Следует помнить, что процедуры освобождения памяти Dipose и FreeMem не полагают освобождаемый указатель константе Nil.
Рассмотрим пример программы, которая формирует стек из случайных целых чисел, затем его упорядочивает методом «пузырька», выводит на экран и одновременно освобождает стек. Приведем полный текст модуля Unit, соответствующего форме Form1, на которой размещены два текстовых редактора Memo и две кнопки: первая – для получения стека из случайных величин, а вторая – для упорядочения элементов стека в порядке возрастания его значений:
Inf3
Ps3
Inf2
Ps2
Inf1
Ps1=nil
P
unit Ustack;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
Type
TForm1 = class(TForm)
Memo1: TMemo;
Memo2: TMemo;
Button1: TButton;
Button2: TButton;
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
type Tps=^Ts; // Определяет тип элемента стека
Ts=record
inf:word; // Информационная часть элемента стека
ps:Tps; // Указатель на предыдущий элемент стека
end;
var p:Tps; // Указатель на вершину стека
const n=10; // Размерность стека
implementation
{$R *.dfm}
// Процедура добавления нового элемента в стек
Procedure AddStack(var P:Tps; n:word);
var pt:Tps;
Begin
new(pt); // Выделяем память для нового элемента стека
pt^.inf:=n; // Записываем новое число в элемент стека
pt^.ps:=p; // Запоминаем указатель на предыдущий элемент стека
p:=pt; // Возвращаем этот новый указатель на вершину стека
end;
// Процедура извлечения числа из стека с освобождением памяти
Procedure FromStack(var p:Tps;var n:word);
var pt:Tps;
Begin
if p<>nil then Begin
pt:=p; // Запоминаем старое значение вершины стека
n:=p^.inf; // Извлекаем число из текущего элемента стека
p:=p^.ps; // Устанавливаем новый указатель на вершину стека
dispose(pt); // Освобождаем память старого элемента стека
end else n:=0;
end;
// Процедура однократного прохода по стеку и замены значений соседних
// элементов стека, если их значения в направлении от вершины ко дну стека
// не возрастаютProcedure exchange(var p:Tps; var n:word);
var nt:word;
Begin
if p^.ps<>nil then Begin // Проверка наличия следующего элемента стека
if p^.inf>p^.ps^.inf then Begin // Проверка на возрастание значений стека
nt:=p^.inf; // Запоминаем значение числа в вершине стека
p^.inf:=p^.ps^.inf; // Переставляем числа соседних элементов стека
p^.ps^.inf:=nt;
inc(n); // Увеличиваем счетчик перестановок на единицу
end;
exchange(p^.ps,n); // Рекурсивно вновь вызываем процедуру перестановок
end;
end;
// Процедура упорядочения элементов стека методом «пузырька»
Procedure SortStack(var p:Tps);
var n:word;
Begin
Repeat // Открытие цикла упорядочений
n:=0;// Счетчик числа перестановок за один проход полагаем равным нулю
exchange(p,n); // Вызываем процедуру однопроходного упорядочения
// Продолжаем цикл, пока не будет ни одной перестановки
until n=0;
end;
// Процедура формирования начального стекаprocedure TForm1.Button1Click(Sender: TObject);
var i,j:integer;begin
randomize; // Инициируем датчик случайных чисел
memo1.Clear;// Очищаем текстовый редактор Memo1
p:=nil; // Указатель на вершину стека полагаем равным константе nil
for i:=1 to n do Begin // Открываем цикл записей в стек
j:=random(20); // Получаем случайное число
addstack(p,j); // Записываем его в стек
memo1.lines.Add(inttostr(j)); // Выводим его значение в Memo1
end;
end;
// Процедура упорядочения элементов стека и вывод результата
procedure TForm1.Button2Click(Sender: TObject);
var k:word;
begin
memo2.Clear; // Очистка Memo2
SortStack(p); // Сортировка стека
while p<>nil do Begin // Проход по стеку
Fromstack(p,k); // Извлечение элемента из стека и освобождение памяти
Memo2.Lines.Add(inttostr(k)); // Запись элемента стека в Memo2
end;
end;
end.
- Программирование в среде Delphi
- Программирование в среде Delphi
- 1. История развития вычислительной техники, системы счисления и единицы информации.................................................7
- 2. Структура персонального компьютера и операционные системы.........................................................................13
- 3. Основы алгоритмизации и работа в delphi..........................18
- 4. Базовые элементы delphi...................................................................26
- 5. Стандартные функции и подпрограммы................................30
- 6. Операторы delphi......................................................................................33
- 7. Операторы циклов....................................................................................35
- 18. Выделение памяти под объект и прародитель всех классов – tobject..........................................................................................84
- 19. Обработка исключительных ситуаций................................87
- 20. Основные классы и общие свойства компонентов...93
- 26. Технология com.....................................................................................129
- 1. История развития вычислительной техники, системы счисления и единицы информации
- 1.1. История развития вычислительной техники
- 1.2. Системы счисления
- 1.3. Единицы информации
- 2. Структура персонального компьютера и операционные системы
- 2.1. Структура персонального компьютера.
- 2.2. Операционные системы
- 3. Основы алгоритмизации и работа в delphi
- 3.1. Основы программирования
- 3.2. Программирование в среде Delphi
- 4. Базовые элементы delphi
- 4.1. Алфавит среды Delphi
- 4.2. Константы
- 4.3. Переменные
- 4.4. Основные типы переменных
- 4.5. Операции над переменными и константами
- 5. Стандартные функции и подпрограммы
- 5.1. Математические функции
- 5.2. Функции преобразования
- 5.3. Дополнительные системные подпрограммы и функции
- 6. Операторы delphi
- 6.1. Оператор присваивания
- 6.2. Оператор безусловной передачи управления
- 6.3. Условный оператор if
- 6.4. Оператор разветвления Case
- 6.5. Составной оператор
- 7. Операторы циклов
- 7.1. Оператор цикла For
- 7.2. Оператор цикла Repeat
- 7.3. Оператор цикла While
- 8. Работа с массивами
- 9. Работа со строками
- 9.1. Процедуры работы со строками
- 9.2. Функции работы со строками
- 10. Работа с записями
- 11. Процедуры и функции
- 12. Модуль unit
- 13. Работа со множествами
- 14. Работа с файлами
- 14.1. Текстовые файлы
- 14.2. Типированные файлы
- 14.3. Нетипированные файлы
- 15. Работа с файлами и каталогами
- 16. Динамические переменные и структуры данных
- 16.1. Динамические переменные
- 16.2. Работа со стеком
- 16.3. Работа со списками или очередями
- 16.4. Работа с деревьями
- 17. Основы объектно–ориентированного программирования
- 17.1. Объекты и классы
- 17.2. Области видимости класса
- 17.3. Свойства (Property) и инкапсуляция
- 17.4. Методы, наследование и полиморфизм
- 17.5. События (Events)
- 18. Выделение памяти под объект и прародитель всех классов – tobject
- 18.1. Выделение памяти под объект
- 18.2. Описание класса tObject
- 18.3. Операторы приведения типов классов
- 19. Обработка исключительных ситуаций
- 19.1. Два вида оператора Try
- 19.2. Программное создание исключительной ситуации
- 19.3. Основные исключительные ситуации
- 20. Основные классы и общие свойства компонентов
- 20.1. Класс tList
- 20.2. Класс tStrings
- 20.3. Общие свойства компонентов
- 21. Графические возможности delphi
- 21.1. Класс Tcanvas
- 21.2. Классы тGгарhic и тРicture
- 21.3. Классы tFont, tPen и tBrush
- 21.4. Работа с изображениями
- 22. Визуальные компоненты delphi
- 22.1. Компонент tBitBtn
- 22.2. Компоненты tDrawGrid и tStringGrid
- 22.3. Компонент tPageControl
- 22.4. Компонент tTimer
- 22.5. Компонент tGauge
- 22.6. Компонент tСolorGrid
- 23. Стандартные диалоговые окна и типовые диалоги
- 23.1. Стандартные диалоговые окна
- 23.2. Типовые диалоги
- 24. Форма, приложение и глобальные объекты
- 24.1. Форма и ее свойства
- 24.2. Объект Application
- 24.3. Глобальные объекты
- Объект ClipBoard
- Объект Screen
- Объект Printer
- 25. Межпрограммное взаимодействие
- 25.1. Обмен сообщениями
- 25.2. Динамический обмен данными
- 25.3. Совместное использование общей памяти
- 25.4. Каналы
- 25.5. Сокеты
- 26. Технология com
- 26.1. Интерфейс
- 27. Технология автоматизации
- 27.1. Основы ole Automation
- 27.2. Примеры использования серверов автоматизации
- 27.3. Компоненты ActiveX
- 28. Динамические библиотеки
- 28.1. Создание dll
- 28.2. Использование dll
- 28.3. Пример написания dll
- 29. Работа с базами данных
- 29.1. Основные определения
- 29.2. Взаимодействие приложения на Delphi с базами данных
- 29.3. Компоненты взаимодействия с базами данных
- If adoTable1.Locate(’fio,stag’,varArrayOf([’Иванов’,’10’]),[])Then …;
- 29.4. Работа с локальной базой данных
- 30. Основы языка sql
- 30.1. Составные части sql
- 30.2. Команда select
- 30.3. Пример использования запросов в Delphi
- 31. Создание собственных компонентов
- 32. Работа с реестром
- 33. Перспективы программирования в delphi
- Литература
- 220013, Минск, п.Бровки, 6