2.5 Операции над указателями

Указатель может находиться в одном из трех состояний:

1. Указатель не инициализирован. Можно только инициализировать значением другого (инициализированного) указателя, процедурой NEW, или константой NIL;

2. Указатель инициализирован процедурой NEW. Можно использовать динамическую переменную q^, как переменную типа T, сам указатель сравнивать с другими указателями (только на совпадение или несовпадение), переинициализировать любым способом (см.1.);

3. Указатель инициализирован константой NIL. Можно указатель сравнивать с другими указателями (только на совпадение или несовпадение), переинициализировать любым способом (см.1.);

Операция взятия адреса.

program adres;

var x:real;

p:^real;

begin

x:=3.1415;

p:=@x;

writeln(integer(p),p^)

end.

2.6 Геометрическая интерпретация

Указатель q:^T;

NEW(q);

Куча;

Диспетчер Динамической Памяти;

q^:T;

2.7 Динамическая цепочка

Pelem=^Elem;

Elem=Record inf:Inform, next:PElem end

Считаем, что Inf=real;

Таблица задается инициализированным указателем p.

Задача: Распечатать третью запись цепочки, если она есть (печать p^.след^.след^.инф)

Задача: Распечатать k-ую запись цепочки.

q:=p;

i:=1;

while (q<>nil) and (i<k) do

begin

i:=i+1;

q:=q^.next;

end;

if q<>nil then writeln(q^.inf) else writeln(‘нет записи’);

2.8 Реализация операций для неупорядоченной таблицы с использованием динамической памяти

PElem = ^Elem;

Elem=record кл:Key; инф:Inf, след:Pelem end;

Заголовок	Действие
Создать (var p:PElem)	p:=NIL
Таблица пуста? (p:PElem): Boolean	Таблица пуста?:= p=NIL
Добавить в начало (var p:PElem,x:Key,i:Inf) (доп. перем p1:PElem)	NEW(p1); p1^.кл:=x; p1^.инф:=i; p1^.след:=p; p:=p1;
Добавить в конец (var p:PElem,x:Key,i:Inf) (доп. перем p1,p2:PElem) (можно обойтись одной доп. перем.)	p1:=p; p2:=p; while p1<>NIL do begin p2:=p1; p1:=p1^.след end; NEW(p1); p1^.кл:=x; p1^.инф:=i; p1^.след:=p; p2^.след:=p1;
Найти по ключу(p:PElem,x:Key) : PElem (доп. перем. p1:PElem)	p1:=p; while (p1<>NIL)and(p1^.кл<>x) do p1:=p1^.след; Найти по ключу:=p1
Удалить запись таблицы, заданную ключем, если она есть(var p:PElem,x:Key): (доп. перем. p1,p2:PElem)	p1:=p; p2:=p; while (p1<>NIL)and(p1^.кл<>x) do begin p2:=p1; p1:=p1^.след end; if p1<>NIL then if p1:=p2 then begin p:=p1^.след; DISPOSE(p1) end else begin p2^.след:=p1^.след; DISPOSE(p1) end

Задача

Реализовать операции для упорядоченной по ключу и упорядоченной по частоте обращения таблиц.

Лекция 3

3.1 Структуры ряда

Последовательный набор записей (цепочка). Доступ к записям структуры ряда осуществляется последовательным просмотром записей цепочки. Определена последующая запись для каждой записи цепочки, кроме последней, и определена предыдущая запись для каждой записи, кроме первой. Структуры ряда подразделяются на строки, очереди, стеки и деки.

3.1.1 Строки

Строка - структура ряда, в которой открыт доступ к любому элементу (любой записи) через последовательный просмотр как от начала цепочки к концу, так и от коца цепочки к началу. Пусть Е - множество элементарных данных, Е(К) - множество всех последовательностей, состоящих из К элементов множества Е, т.е. элементами множества Е(К) являются строки длиной К. В таблице приведены основные операции над строками (использованы обозначения аЕ(К1), вЕ(К2), сЕ(К3), авЕ(К1+К2), авсЕ(К1+К2+К3) и т.д., dЕ(К1-К2+К3))

Имя операции	Функциональные спецификации	Аргументы	Результат	О п и с а н и е
Конкатенация	Е(К1)Е(К2) Е(К1+К2)	а, в	ав	Строка, полученная склейкой строк а и в
Вычеркивание подстроки	Е(К1+К2+К3) Е(К1+К3)	авс	ас	Строка, полученная из авс отбрасыванием в
Разделение	Е(К1+К2) Е(К1)Е(К2)	ав	а, в	Разделение на две строки
Подстановка	Е(К1+К2)Е(К3) Е(К1+К3+К2)	ав, с	асв	Подстановка
Контекстный поиск?	Е(К1)Е(К2) Boolean	а, в	истина или ложь	Истина, если в строке а есть подстрока в
Контекстная замена	Е(К1)Е(К2)Е(К3) Е(К1-К2+К3)	а, в, с	либо d, либо а	Если контекст в найден в а, то он заменяется на контекст с, иначе без изменения

Представление с помощью массивов

N - максимальная длина строки, s1,s2,... :array[1..N] of Inf.

Задача: реализовать операции над строками, представляя строки с помощью массивов.

Динамическое представление строки.

PAtom=^Atom; Atom = record инф:Inf; пред,след:PAtom end

Пример:

конкатенация(p1,p2:PAtom),

причем p1 и p2 - непустые строки,

результат - строка p1,

p:PAtom.

Где в алгоритме используется «непустота» строк?

Задача.

Реализовать операции над строками.

3.1.2 Очередь, стек, дек

Всем перечисленным структурам свойственна операция "выборка" (чтение с удалением).

Очередью называется структура данных, добавление записи в которую производится в конец цепочки, а выборка осуществляется из начала цепочки. Очередь работает по принципу

FIFO (First-In, First-Out) – поступивший первым, обслуживается первым.

Стеком называется структура данных, добавление записи в которую и выборка записи из которой производится из начала цепочки (вершины стека). Стек работает по принципу LIFO (Last-In, First-Out) – поступивший последним, обслуживается первым.

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

Логические описания.

Пусть записи принадлежат типу Inf; S - стек; S' - непустой стек; О - очередь; О'- непустая очередь.

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

Стек

S=(пусто¦S');

S'=(i:Inf,s:S)

Oчередь

О=(пусто¦О');

О'=(i:Inf,o:O¦o:O,i:Inf).

Это рекурсивные определения структур стек и очередь. Рекурсивное определение предполагает использование рекурсивных алгоритмов при реализации операций.

Операции над деком включают все операции, перечисленные в таблице, учитывая, что S и O есть частные случаи дека.

Имя операции	Функциональ-ные спецификации	Аргументы	Результат	Описание
Создать	S O		пустой s пустая o	Создается пустой стек или очередь
Пусто?	SBoolean OBoolean	s o	истина или ложь	Пуст ли стек, или очередь ?
Первый	ST OT	(t, s) (t, o)	t t	Определение элемента подлежащего обслуживанию
Выборка	SS OO	(t, s) (t, o)	s o	Из стека или очереди удален первый элемент
Добавление	TSS TOO	t, s t, o	(t, s) (t,o)	Добавлен новый элемент

Задача.

Представить структуры очереди, стека и дека с помощью массивов и реализовать операции.

При динамическом представлении структур записи можно представить так:

PElem=^Elem;

Elem = (инф:Inf; след:PElem).

Для удобства реализаций стек задается одним указателем на голову, а очередь и дек - двумя (на первый и последний элемент)

Задачи

Выборка(p:Pelem,i:Inf) - из структуры p (очередь или стек) выбрать в i данное.

Пусть p не пуст, тогда

i=p^.инф; p1=p; p=p^.след; DISPOSE(p1)

Распечатать информационные части стека p.

Традиционное решение	Рекурсивное решение
Распечатать(p:PElem): q=p while p<>NIL do begin печ(p^.инф); p=p^.след end	Распечатать(p:PElem): if p<>NIL then begin печ(p^.инф); Распечатать(p^.след) end

1. Распечатать информационные части стека в обратном порядке.

2. Превратить стек p в очередь p,q.

3. Перевернуть файл (используем стек p).