|
…/p>
next: pnode; { Ссылка на следующий элемент. } end; Сама очередь задается совокупностью указателя на первый элемент и переменной, хранящей текущее количество элементов. type queue = record first: pnode; { Указатель на первый элемент. } count: integer; { Количество элементов. } end; Инициализация очереди осуществляется путем присваивания пустой ссылки указателю на первый элемент очереди и обнуления переменной, хранящей количество элементов. { Операция инициализации очереди. } { Входные параметры: } { q - очередь. } procedure init(var q: queue); begin q.first := nil; q.count := 0; end; Операция добавления нового элемента зависит от того, пуста ли очередь. Если в очереди нет ни одного элемента, то добавление произойдет в начало. В противном случае циклом необходимо дойти до конца очереди, новый элемент будет последним. Здесь сложность операции, в отличие от реализации на массиве, составляет O(n), поскольку необходимо осуществлять поиск последнего элемента. { Операция добавления нового элемента. } { Входные параметры: } { q - очередь; } { item - новый элемент. } procedure add(var q: queue; item: integer); var i: pnode; begin { Если ссылка на первый элемент пуста, значит } { в списке нет ни одного элемента. Добавляемый } { элемент будет первым. } if (q.first = nil) then begin new(q.first); q.first^.data := item; q.first^.next := nil; end { В противном случае доходим до последнего элемента } { списка. Добавляем новый элемент в конец. } else begin i := q.first; while (i^.next <> nil) do i := i^.next; new(i^.next); i^.next^.next := nil; i^.next^.data := item; end; { После добавления увеличиваем количество элементов } { в списке на единицу. } inc(q.count); end; Операция удаления элемента также зависит от общего числа элементов. Если очередь пуста, ничего удалять не нужно. Сложность операции O(1), поскольку мы всегда храним указатель на первый элемент. { Операция удаления элемента. } { Входные параметры: } { q - очередь. } procedure remove(var q: queue); var i: pnode; begin { Если в очереди есть хотя бы один элемент, } { удаляем первый. На его место ставим второй элемент. } if (q.count > 0) then begin i := q.first^.next; dispose(q.first); q.first := i; { Уменьшаем количество элементов на 1. } dec(q.count); end; end; Для получения первого элемента очереди возвращаем его полезную информацию. Если очередь пуста, возвращаем 0. Сложность операции O(1). { Операция получения первого элемента очереди. } { Входные параметры: } { q - очередь. } function get_first(q: queue): integer; begin { Если в очереди есть хотя бы один элемент, } { возвращаем первый. } if (q.count > 0) then get_first := q.first^.data else { В противном случае возвращаем 0. } get_first := 0; end; Для получения последнего элемента очереди, необходимо циклом осуществить переход к нему и вернуть его содержимое. Если очередь пуста, возвращаем 0. Сложность операции O(n). { Операция получения последнего элемента очереди. } { Входные параметры: } { q - очередь. } function get_last(q: queue): integer; var i: pnode; begin { Если в очереди есть хотя бы один элемент, переходим } { к последнему элементу и возвращаем значение, } { в нем. } if (q.count > 0) then begin i := q.first; while (i^.next <> nil) do i := i^.next; get_last := i^.data; end { В противном случае возвращаем 0. } else get_last := 0; end; 4. Стеки. Реализации на базе массива и списка4.1. Понятие стека
Рис. 6. Стек. Для добавления и удаления элементов необходимо получить доступ к вершине стека. Доступ к другим элементам невозможен логически. Принцип доступа, реализуемый стеком называется LIFO (Last In, First Out), что по русски означает «Первым выйдет тот, кто пришел последним». Стек предоставляет три основные операции:
4.2. Реализация стека на базе массиваРеализация стека на основе массива делает ограничение на максимальное количество элементов, одновременно хранящихся в стеке. В качестве примера реализуем стек, хранящий целочисленные элементы. Стек представляется в виде структуры, содержащую массив элементов и переменную, хранящую количество элементов в стеке: type stack = record buf: array [1..max_size] { Массив элементов. } of integer; count: integer; { Количество элементов. } end; Инициализация стека осуществляется путем присваивания переменной count значения 0: { Операция инициализации стека. } { Входные параметры: } { s - стек; } procedure init(var s: stack); begin s.count := 0; end; При добавлении элемента в стек следует следить за текущим количеством элементов в стеке (оно должно быть больше максимального количества элементов). Сложность операции O(1): { Операция добавления нового элемента. } { Входные параметры: } { s - стек; } { item - новый элемент; } procedure push(var s: stack; item: integer); begin { Если текущее количество элементов меньше } { максимального, выполняем добавление элемента. } if (s.count < max_size) then begin s.buf[s.count + 1] := item; { Увеличиваем число элементов на 1. } inc(s.count); end; end; При просмотре верхнего элемента стека отдельно обрабатывается случай, когда число элементов равно 0. В данном случае возвращается некое фиксированное значение или код ошибки. Если стек содержит хотябы один элемент, то возвращается верхушка стека. Сложность операции O(1): { Операция просмотра вершины стека. } { Входные параметры: } { s - стек; } function peek(s: stack): integer; begin { Если нет ни одного элемента, возвращаем 0. } if (s.count <= 0) then peek := 0 { В противном случае возвращаем элемент из вершины. } else peek := s.buf[1]; end; Операция удаления элемента из стека производит выемку элемента из вершины с его возвратом. При этом, если стек пуст, возвращается код ошибки. Сложность операции O(n): { Операция удаления элемента из вершины стека. } { Входные параметры: } { s - стек; } function pop(var s: stack): integer; var i: integer; begin { Если в стеке нет элементов, возвращаем 0. } if (s.count <= 0) then pop := 0 else begin { Удаляем элемент из вершины. Все остальные } { сдвигаем влево на одну позицию. } pop := s.buf[1]; i := 1; while (i < s.count) do begin s.buf[i] := s.buf[i + 1]; inc(i); end; { Уменьшаем количество элементов на 1. } dec(s.count); end; end; 4.3. Реализация стека на базе связного спискаПреимущество реализации на базе связного списка заключено в том, что ограничение на максимальное число элементов отсутствует. Для реализации необходимо описать элемент стека. Это структура, содержащая полезную информацию и ссылку на следующий элемент: type pnode = ^node; { Тип: указатель на узел стека. } node = record { Объявление узла стека. } data: integer; { Полезная информация. } next: pnode; { Ссылка на следующий элемент. } end; Сам стек является структурой, содержащей указатель на первый элемент и переменную, хранящую количество элементов в стеке: type stack = record first: pnode; { Указатель на первый элемент. } count: integer; { Количество элементов. } end; Инициализация стека производится обнулением количества элементов в стеке и присваиванием пустой ссылки указателю на первый элемент: { Операция инициализации стека. } { Входные параметры: } { s - стек; } procedure init(var s: stack); begin s.first := nil; s.count := 0; end; Добавление элемента производится в начало стека. При этом ссылка на первый элемент должна указывать на новый элемент. Если стек пустой, то необходимо произвести инициализацию указателя на первый элемент. Сложнойсть операции O(1): { Операция добавления нового элемента. } { Входные параметры: } { s - стек; } { item - новый элемент; } procedure push(var s: stack; item: integer); var i: pnode; begin { Если ссылка на первый элемент пуста, значит } { в стеке нет ни одного элемента. Добавляемый } { элемент будет первым. } if (s.first = nil) then begin new(s.first); s.first^.data := item; s.first^.next := nil; end { В противном случае добавляем элемент в начало стека. } else begin i := s.first; new(s.first); s.first^.data := item; s.first^.next := i; end; { После добавления увеличиваем количество элементов } { в стеке на единицу. } inc(s.count); end; Операция просмотра первого элемента в стеке возвращает 0, если он пуст. В противном случае, возвращает элемент в вершине стека. Сложность операции O(1): { Операция просмотра вершины стека. } { Входные параметры: } { s - стек; } function peek(s: stack): integer; begin { Если нет ни одного элемента, возвращаем 0. } if (s.count <= 0) then peek := 0 { В противном случае возвращаем элемент из вершины. } else peek := s.first^.data; end; Операция удаления элемента очищает память, занимаемую первым элементов стека и переставляет указатель на вершину. Функция возвращает данные, хранимые в удаленном элементе. Следует обрабатывать ситуации, когда стек пуст. В данном случае функция возвращает 0 в качестве кода ошибки. Сложность операции O(1): { Операция удаления элемента из вершины стека. } { Входные параметры: } { s - стек; } function pop(var s: stack): integer; var i: pnode; begin { Если в стеке нет элементов, возвращаем 0. } if (s.count <= 0) then pop := 0 else begin { Удаляем элемент из вершины. Второй элемент } { становится на место первого. } pop := s.first^.data; i := s.first^.next; dispose(s.first); s.first := i; { Уменьшаем количество элементов на 1. } dec(s.count); end; end; 5. ЗаключениеВ данной главе мы рассмотрели понятие линейных динамических структур данных, в частности связанного списка, очереди и стека и их реализации. Кроме того, мы рассмотрели реализации основных операций, применяемых в работе с данными структурами. Понимание этих типов данных крайне важно в изучении теории программирования. Правильное применение структур данных определяет качество, производительность и надежность разрабатываемой программы. 6. Литература6.1. Использованные источники информации
6.2. Информационные ресурсы сети Интернет
|
|