Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Последовательный набор записей (цепочка). Доступ к записям структуры ряда осуществляется последовательным просмотром записей цепочки. Определена последующая запись для каждой записи цепочки, кроме последней, и определена предыдущая запись для каждой записи, кроме первой. Структуры ряда подразделяются на строки, очереди, стеки и деки.
Строка - структура ряда, в которой открыт доступ к любому элементу (любой записи) через последовательный просмотр как от начала цепочки к концу, так и от коца цепочки к началу. Пусть Е - множество элементарных данных, Е(К) - множество всех последовательностей, состоящих из К элементов множества Е, т.е. элементами множества Е(К) являются строки длиной К. В таблице приведены основные операции над строками (использованы обозначения аЕ(К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
Где в алгоритме используется «непустота» строк?
Реализовать операции над строками.
Всем перечисленным структурам свойственна операция "выборка" (чтение с удалением).
Очередью называется структура данных, добавление записи в которую производится в конец цепочки, а выборка осуществляется из начала цепочки. Очередь работает по принципу
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).
Привычное определение арифметического выражения:
Привычная форма записи арифметического выражения
((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 |