Лекция 3 3.1 Структуры ряда Последовательный набор записей цепочка
Работа добавлена на сайт samzan.net:
Лекция 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.
p=p1
p^.след<>nil
p=p^.след
p^.след=p2 p2^.пред=p
Где в алгоритме используется «непустота» строк?
Задача.
Реализовать операции над строками.
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 |
Создается пустой стек или очередь |
|
|
Пусто? |
SBoolean OBoolean |
s o |
истина или ложь |
Пуст ли стек, или очередь ? |
|
Первый |
ST OT |
(t, s) (t, o) |
t t |
Определение элемента подлежащего обслуживанию |
|
Выборка |
SS OO |
(t, s) (t, o) |
s o |
Из стека или очереди удален первый элемент |
|
Добавление |
TSS TOO |
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 |
2. задание ситуация
3. тема образов художественная структура
4. субъединицей рибосом что нарушает образование пептидных связей между молекулами аминокислот и блокирует с
5. Реферат- Институт возмещения вреда в XIX - начале XX века
6. Конституционное право Беларуси в XVI веке
7. Российская история как часть мировой истории
8. ТЕМА- Исторические типы культуры ЦЕЛЬ- закрепление обобщение систематизация пройденного материала;
9. 0194 Машинисты подъемников мачтовых стоечных или шахтных далее
10. либо отрасль промышленности в которой не использовались бы электронные приборы или электронные устройства.
11. Лев Семёнович Выготски
12. две взаимосвязанные но различающиеся концепции смерти традиционную классическую и нетрадиционную некл
13. реферат дисертації на здобуття наукового ступеня кандидата історичних наук ІваноФранк
14. космонавта О- Валентина Терешкова
15. Кремль - сердце Москвы
16. Внутренний аудит Задача 1
17. Реферат Рентгенодиагностика и лечение переломов
18. ДВОРЕЦ ТВОРЧЕСТВА ДЕТЕЙ И МОЛОДЕЖИ г
19. Из истории грузинской агиографии мученичество бидзины, шалвы и элисбара
20. Введение4 1 КИНЕМАТИЧЕСКИЙ РАСЧЕТ ПРИВОДА И ВЫБОР