2.2.2. Очереди
Очередь – упорядоченный набор элементов, в котором элементы всегда добавляются в начало, а изымаются только из конца.
(
Для
очереди допустима вставка только в
начало. Не вводится операция поиска
элемента. Операция удаления применяется
только к последнему элементу)
Использование очередей: множество запросов к ресурсу; в программах, моделирующих алгоритмы теории массового обслуживания и т.д.
Реализация: (список на основе указателей)
Процедура добавления элемента в конец списка (начало очереди):
var Head,Tail:Link;
…
procedure AddItem(A:Link);
begin
if Head=nil then Head:=A; {если
очередь пустая}
else Tail^.Next:=A;
Tail:=A;
end;
Процедура извлечения элемента из очереди:
var Head, Tail:Link;
…
procedure DellItem(Var A:Link);
begin
A:=Head;
Head:=Head^.Next
end;
2.2.3. Стеки
С
тек
– (динамическая структура)
упорядоченный список, в котором элементы
добавляются в начало и изымаются из
начала.
Push – добавить, Pop – извлечь эл-т, Empy – проверка стека на пустоту (true - пуст), SP-переменная, хранящая текущее значение индекса стека.
Использование: везде, где используются подпрограммы (обработка прерываний).
Пример реализации стека на основе списка, реализованного на основе массива:
type
NameStr=string[15];
Student=record;
Name:NameStr;
Mark:integer;
…
end;
Const StackSize=100; {max размер стека}
Var
List:array[1..StackSize] of Student;
SP:integer; {указатель (вершины) стека}
…
SP:=1; {пустому стеку соответствует значение указателя 1}
…
Процедура добавления элемента:
procedure Push(Item:Student);
begin
if SP>StackSize then Exit; {стек переполнен}
List[SP]:=Item;
SP:=SP+1;
end;
Определение: пуст ли стек:
function Empty: Boolean;
begin
if SP=1 then Empty:=True;
else Empty:=False;
end;
Извлечение элемента из стека:
procedure Pop (Var Item:Student);
begin
if Empty then Exit;
SP:=SP-1;
Item:=List[SP]
end;
Реализация стека на основе динамических переменных:
Процедура добавления – AddFirst.
Процедура удаления – DelFirst.
Функция Empty: (if SP=1) заменить на (First=nil).
2.2.4. Множества
М
ножество
– (в контексте программирования)
это неупорядоченный набор элементов
данных одного типа.
Операции: добавление элемента, удаление, операция определения вхождения в множество (Member) (это логическая ф-ция).
В Pascal’е есть стандартный множественный тип:
С
интаксическая
диаграмма:
Примеры:
1) Мн-во целых чисел от 0 до 7:
Opcode: set of 0..7;
2) Мн-во символов (букв):
Letter: set of char;
Операции над мн-вами:
1)
2)
3)
4)
,
где
- некоторый элемент (переменная) 5)
равенство, неравенство –
,
6) операции включения –
(
подмн-во
),
(
подмн-во
).
Реализация мн-ва на основе списка:
Добавление эл-та (
)
–
(можно и в конец списка)
Удаление эл-та (
)
–
,
где
- удаление не 1-го эл-та.
получается из ф-ции
с исправлениями:
вместо
пишем
вместо
пишем
