Множества

Стеки

Стек – (динамическая структура) упорядоченный список, в котором элементы добавляются в начало и изымаются из начала.

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).

Множество – (в контексте программирования) это неупорядоченный набор элементов данных одного типа.

Операции: добавление элемента, удаление, операция определения вхождения в множество (Member) (это логическая ф-ция).

В Pascal’е есть стандартный множественный тип:

Синтаксическая диаграмма:

Примеры:

1) Мн-во целых чисел от 0 до 7:

Opcode: set of 0..7;

2) Мн-во символов (букв):

Letter: set of char;

Операции над мн-вами:

1) 2) 3) 4) , где - некоторый элемент (переменная) 5) равенство, неравенство – , 6) операции включения – (подмн-во ), (подмн-во ).

Реализация мн-ва на основе списка:

Добавление эл-та () –(можно и в конец списка)

Удаление эл-та () – , где - удаление не 1-го эл-та.

получается из ф-ции с исправлениями:

вместо пишем

вместо пишем

Дата добавления: 2014-01-07