Задача: реализовать операции над строками, представляя строки с помощью массивов.
Динамическое представление строки.
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).
3.2 Обратная польская (постфиксная) запись
Привычное определение арифметического выражения:
Арифметическая константа или инициализированная арифметическая переменная является арифметическим выражением. Если А и В – арифметические выражения, то А#В и (А#В) – арифметические выражения.Привычная форма записи арифметического выражения
((a+b*(c-e)/(d+f))/(a*b))/c
Арифметическое выражение в форме обратной польской записи (ПФ):
Арифметическая константа или инициализированная арифметическая переменная является арифметическим выражением ПФ. Если А и В – арифметические выражения ПФ, то АВ # – арифметическое выражение ПФ.Постфиксная форма записи того же арифметического выражения
a b c e - * d f + / + a b * / c /
Как получить обратную польскую запись?
Рекурсивное решение: Если арифметическое выражение является арифметической константой или инициализированной арифметической переменной, то по определению это и есть арифметическое выражение ПФ. Если арифметическое выражение имеет вид А#В или (А#В), то нужно записать ПФ для А, далее приписать ПФ для В, а затем записать знак операции #.
((a+b*(c-e)/(d+f))/(a*b))/c
(((a+((b*(c-e))/(d+f)))/(a*b))/c)
(((a+((b*(c-e))/(d+f)))/(a*b))/c)
((a+((b*(c-e))/(d+f)))/(a*b))c/
((a+((b*(c-e))/(d+f)))/(a*b))c/
((a+((b*(c-e))/(d+f)))/(a*b))c/
(a+((b*(c-e))/(d+f)))(a*b)/c/
(a+((b*(c-e))/(d+f)))(a*b)/c/
(a+((b*(c-e))/(d+f)))(a*b)/c/
a((b*(c-e))/(d+f))+ab*/c/
a((b*(c-e))/(d+f))+ab*/c/
a((b*(c-e))/(d+f))+ab*/c/
a(b*(c-e))(d+f)/+ab*/c/
a(b*(c-e))(d+f)/+ab*/c/
a(b*(c-e))(d+f)/+ab*/c/
ab(c-e)*df+/+ab*/c/
ab(c-e)*df+/+ab*/c/
ab(c-e)*df+/+ab*/c/
abce-*df+/+ab*/c/
abce-*df+/+ab*/c/
Задача.
Вычислить значение арифметического выражения, записанного в виде обратной польской записи.
Решение.
Создаем пустой стек. Читаем арифметическое выражение ПФ слева направо. Если встречается константа или имя инициализированной переменной, то в стек вталкивается соответствующее значение. Если встречается знак арифметической операции, то из стека выбираются два значения, над ними выполняется операция (первое значение – правый операнд, второе значение – левый операнд), результат операции вталкивается в стек.
Докажите, что в результате такой обработки правильного выражения ПФ в вершине стека будет лежать значение арифметического выражения, других записей в стеке не будет.
Пусть a=1, b=2, c=3, d=4, e=5, f=6, тогда алгоритм вычисления выражения
a b c e - * d f + / + a b * / c / реализуется так:
Номер действия | Содержание стека | Обратная польская запись |
1,2,3,5,-,*,4,6,+,/,+,1,2,*,/,3,/ | ||
1 | 2,3,5,-,*,4,6,+,/,+,1,2,*,/,3,/ | |
1,2 | 3,5,-,*,4,6,+,/,+,1,2,*,/,3,/ | |
1,2,3 | 5,-,*,4,6,+,/,+,1,2,*,/,3,/ | |
1 | 1,2,3,5 | -,*,4,6,+,/,+,1,2,*,/,3,/ |
2 | 1,2,-2 | *,4,6,+,/,+,1,2,*,/,3,/ |
1,-4 | 4,6,+,/,+,1,2,*,/,3,/ | |
1,-4,4 | 6,+,/,+,1,2,*,/,3,/ | |
3 | 1,-4,4,6 | +,/,+,1,2,*,/,3,/ |
4 | 1,-4,10 | /,+,1,2,*,/,3,/ |
5 | 1,-0.4 | +,1,2,*,/,3,/ |
0.6 | 1,2,*,/,3,/ | |
0.6,1 | 2,*,/,3,/ | |
6 | 0.6,1,2 | *,/,3,/ |
7 | 0.6,2 | /,3,/ |
0.3 | 3,/ | |
8 | 0.3,3 | / |
0.1 |
Лекция 4
Повторение: Рекурсивная процедура или функция.
· Обязательно есть нерекурсивная ветка.
· Обязательно «когда-нибудь» на нерекурсивную ветку попадем.
Двойная рекурсия. Косвенная рекурсия.
4.1 Списковые структуры. Линейный список
Линейный список – структура данных, позволяющая учесть «вложенность». Используют линейные списки для описания выражений (арифметических, логических), структуры текста программы на алгоритмическом языке и т. д.
Пусть a, b,c,...,+,-,*,/ - элементы типа Т (атомы), скобки – особые символы, описывающие вложенность.
Определение 1 (рекуррентное) линейного списка:
1. атом есть линейный список (атомарный);
2. ( ) – линейный список (пустой);
3. если l1,l2,...,ln – линейные списки (n>0), то и (l1 l2 ...ln) – линейный список.
В непустом неатомарном списке (l1 l2 ...ln) l1- голова списка, (l2 ...ln) - хвост списка.
Примеры.
Пример | Описание | Степень вложенности (уровень) |
a | атомарный список | 0 (элемент а на уровне 0) |
(a) | список неатомарный | 1 (элемент а на уровне 1) |
( ) | пустой список | 1 (нет элементов на уровне 1) |
(()) | непустой список | 2 (элемент ( ) на уровне 1) |
ab | не список | - |
a(b) | не список | - |
(ab) | список | 1 (элементы а и b на уровне 1) |
(((ab)c)(de)) | список | 3 (элементы а и b на уровне 3) |
((a+b)/(c+d)*f) | список | 2 (элементы а, +, b, с, +, d – на уровне 3) |
Определение 2 (рекурсивное) линейного списка
Пусть S – линейный список, S+ – неатомарный список, S* – непустой неатомарный список.
1. атом есть линейный список (атомарный);
2. ( ) – линейный список (пустой);
3. S = (либо пустой, либо атомарный, либо S*);
4. S* = (голова:S, хвост:S+);
5. S+ = (либо пустой, либо S*);
Операции над структурой данных линейный список:
§ Создать атомарный список;
§ Создать пустой список;
§ Создать список из набора имеющихся списков по п.3 определения 1;
§ Список пуст?;
§ Список атом?;
§ Расчленение (выделение головы и хвоста);
§ Голова (функция с побочным эффектом);
4.2 Об операции "расчленение"
Операция определена на непустых неатомарных списках S*.
Голова - первый элемент первого уровня. Хвост - список без головы.
Примеры:
Список | Голова | Хвост |
(a) | a | ( ) |
(ab) | a | (b) |
(( )) | ( ) | ( ) |
(((ab)c)(de)) | ((ab)c) | ((de)) |
4.3 Логическое описание линейного списка.
pElem=^Elem;
Elem=record
след:pElem;
case R:0..1 of
0: (уров:pElem);
1: (атом:T)
end;
Поле R - поле тега (переключатель).
Примеры:
1. Пустой список ( ) 
2. Атом a 
3.(ab) 
4. (a( )b)
5. ((a+b)*(c-(b/a)))
4.4 Вычисление значения арифметического выражения
Функция «Голова(р)» с побочным эффектом (р указывает на непустой неатомарный линейный список).
Голова:=р^.уров;
p^.уров:=Голова^.след;
Голова^.след:=nil
{Серия картинок, иллюстрирующих работу функции Голова}
"Правильное" арифметическое выражение представлено как "правильный" линейный список. Атомы a, b,c,... – инициализированные переменные или константы, атомы + - * / – бинарные операции.
Функция VAL(p:pElem) возвращает значение арифметического выражения, заданного указателем p.
VAL(p:pElem)
Список пуст? | ||
Список атом? | ||
VAL=p^.атом | x=VAL(Голова(p)) | |
оп=Голова(p)^.атом | ||
y=VAL(p) | ||
если оп=+ VAL=x+y | ||
если оп=- VAL=x-y | ||
если оп=* VAL=x*y | ||
если оп=/ VAL=x/y |
Разъяснения:
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 |
