Задание к лабораторной работе

1. Изучить теоретическую часть.

2. Выполнить «ручную» компиляцию (преобразование) нескольких арифметических выражений, включая проверку корректности.

3. Вычислить значение выражений при выбранных самостоятельно значениях переменных.

4. Составить программу преобразования арифметического выражения (целочисленные бинарные операции: сложение, вычитание, умножение, деление; операнды – однолитерные идентификаторы) в инфиксной форме обратную польскую запись, включая проверку его корректности. Предусмотреть возможность использования скобок. Реализовать следующие действия: ввод инфиксного выражения, проверка корректности выражения, преобразование инфиксного выражения в постфиксную форму записи, вычисление значения выражения, вывод сведений об авторе.

Вопросы и упражнения

1. Почему на этапе компиляции выражения, как правило, переводятся в постфиксную форму?

2. Сформулируйте алгоритм для вычисления значения выражения в префиксной форме.

3. Сформулируйте правило вычисления ранга и условие корректности префиксной формулы.

4. Приведите примеры одноместных и многоместных операций.

5. Запишите алгоритм преобразования произвольного арифметического выражения в обратную польскую запись.

6. Объясните необходимость использования стека при преобразовании выражения в обратную польскую запись.

7. Сформулируйте алгоритм проверки скобочной структуры арифметического выражения.

Рекомендуемая литература

1. Трамбле Ж., Соренсон П. Введение в структуры данных: пер. с англ. М.:Машиностроение, 1982.

Лабораторная работа №5 линейные динамические структуры данных. Топологическая сортировка

Линейные динамические структуры данных

Динамические структуры данных характеризуются тем, что в процессе работы количество элементов логической структуры постоянно меняется. Выбор конкретной структуры данных определяется характером задачи, алгоритмом ее решения и перечнем выполняемых операций. Поэтому, можно говорить, что каждой структуре данных соответствует свой набор операций.

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

Методы реализации динамических структур данных определяются выбранным языком программирования. В языках, не имеющих средств поддержки динамики, например, в Бейсике, пользователь вынужден размещать динамические структуры данных, как правило, в массивах. В этой ситуации на программиста ложится вся забота об эффективной организации таких структур и методах работы с ними.

В языках с динамикой, например, в Паскале имеются специальные ссылочные типы данных, и программисту предоставлен набор процедур, обеспечивающих выделение памяти и ее возврат. Однако, сбор "мусора" зачастую не реализуется. Располагая возможностью организации динамической структуры, программист должен реализовать методы работы с нею.

Кроме перечисленных языков имеются языки уже сразу содержащие средства работы с динамическими структурами данных. К таким языкам, например, можно отнести Пролог и Лисп.

К простейшим динамическим структурам относятся линейные структуры списки. Под списком понимается такая логическая организация данных, когда элементы упорядочены в линейном порядке. Каждый элемент несет некоторую информацию и связан с последующим. Первый элемент структуры называется головным. Последний элемент содержит признак конца списка.

В качестве примера рассмотрим задачу формирования и печати списка из N элементов. В информационном поле разместим номер элемента. Программа на Паскале будет иметь следующий вид:

Type ref = ^elem;

elem = record

inf : integer;

next : ref

end;

Var Head, T : ref;

N, i : integer;

Begin

readln(N); { количество элементов списка }

Head:=nil;

if N>0 then

begin

new(Head); { отдельно создаем первый элемент списка }

Head^.inf:=1;

T:=Head;

for i:=2 to N do

begin

{ создание всех последующих элементов списка }

new(T^.next);

T:=T^.next;

T^.inf:=i;

end;

T^.next:=nil

end;

{ список создан, приступаем к печати (не используя информации о     количестве элементов) }

T:=Head;

while T<>nil do

begin

writeln(T^.inf);

T:=T^.next

end

End.

Существуют различные типы списков: с заглавным элементом, односвязный, двухсвязный, кольцевой и т.п. По–прежнему, выбор логической структуры определяется характером задачи, алгоритмом и набором операций. Выбор физической структуры определяется логической структурой и языком реализации.

Топологическая сортировка

Топологическая сортировка – это одна из известных задач в программировании, в которой широко применяются списки. Под топологической сортировкой понимается сортировка элементов, для которых определен частичный порядок, то есть упорядочение задано не на всех, а только на некоторых парах элементов.

Пример. В институтской программе изложение одних курсов опирается на другие курсы. Скажем, для того, чтобы понять курс по структурам данных необходимо прежде прослушать курс по конструированию программ и языкам программирования. С другой стороны, на порядок изложения названных курсов никак не влияет курс по физике. Топологическая сортировка для набора курсов означает определение такого порядка чтения курсов, при котором ни один курс не читается раньше того, на материале которого он основан.

Частичный порядок элементов удобно представлять в графическом виде. При этом каждому элементу (в нашем примере – курсу) соответствует некоторый узел графа, а зависимость (частичный порядок) задана направленными дугами. Ниже приводится пример задания частичной зависимости на множестве восьми учебных дисциплин. В скобках обозначены их условные сокращения.

В нашем примере порядок может быть таким: О, Ф, К, Х, Д, С, Б, Т. Понятно, что этот вариант не является единственным. Более того, реальная задача может оказаться гораздо более громоздкой. Возможны варианты, когда топологическая сортировка может вовсе не иметь решения.

Проверка найденного решения очень проста: достаточно в полученной последовательности провести дуги, связывающие частично упорядоченные элементы. Если все дуги будут направлены слева направо, то найденный порядок допустим.

Если хотя бы одна дуга направлена в обратную сторону, то решение неверно.

Алгоритм топологической сортировки

Для упорядоченной пары элементов АВ элемент А будем называть предшественником, а элемент В преемником. Суть алгоритма заключается в следующем.

а) Для каждого элемента определяем его преемников и подсчитываем количество его предшественников. В дальнейшем работаем не с исходным графом, а с множеством элементов, каждому из которых приписан счетчик предшественников и список преемников.

б) Выбираем из построенного множества и помещаем в выходной список элементы, не имеющие предшественников (с нулевым счетчиком).

в) Каждое извлечение элемента (см. пункт б) сопровождаем пересчетом количества оставшихся предшественников. Причем, эта операция затрагивает только те элементы, которые являются преемниками удаляемого.

Пункты б) и в) повторяем до тех пор пока это возможно. Если в очередной раз пункт б) не выполним, а множество непусто, то топологическая сортировка невозможна. Если же множество исчерпано, то топологическая сортировка выполнена "удачно" и в выходном списке перечислены элементы в допустимом порядке.

По нашему алгоритму для каждого элемента необходимо хранить список преемников и счетчик числа предшественников, поэтому представим наше множество массивом по количеству элементов:

Const max=...; {количество элементов графа}

Type Ref : ^Elem;

Elem = record

N: 0..max; {количество предшественников или номер элемента–преемника}

next: Ref { ссылка на список преемников }

end;

Var A : array [1..max] of record

name: string; {наименование элемента}

data: Elem;

end;

Причем поле N можно использовать трояко: как счетчик предшественников для данного элемента и как номер элемента, являющегося преемником данного. Кроме того, для организации выборки элементов с нулевыми счетчиками, целесообразно такие элементы связать в список. Для этого можно вновь задействовать поле N.

Пример. Выпишем связи из предыдущего примера: КС, КТ, КБ, СТ, СБ, ДТ, ОФ, ОД, ОТ. Описанный выше массив A графически будет выглядеть так, как изображено на рисунке ниже.

	A[1]:	С	1		5		6		nil
	A[2]:	К	0		1		5		6		nil
	A[3]:	Ф	1		nil
	A[4]:	О	0		3		8		5		nil
	A[5]:	Т	4		nil
	A[6]:	Б	2		nil
	A[7]:	Х	0		nil
	A[8]:	Д	1		5		nil

Здесь значения, проставленные в прямоугольниках, означают следующее. Первый числовой столбец (1, 0, 1, 0, 4, 2, 0, 1) – счетчики числа предшественников. Все последующие числовые значения задают номера элементов, являющихся преемниками данного.

В начальном состоянии имеются три элемента: 2, 4, 7 – с нулевыми счетчиками. Свяжем их в отдельный список. Через Q будем обозначать указатель на начальный элемент списка. Через R обозначим последний элемент. Определим типы:

Q, R : integer

Таким образом, информация об исходном частично упорядоченном множестве примет вид: Q=2, R=7. Для связывания элементов списка Q будем использовать опять же поле N. После чего наша структура примет вид:

A[1]:	С	1		5		6		nil
A[2]:	К	4		1		5		6		nil
A[3]:	Ф	1		nil
A[4]:	О	7		3		8		5		nil
A[5]:	Т	4		nil
A[6]:	Б	2		nil
A[7]:	Х	0		nil
A[8]:	Д	1		5		nil

Сейчас A[Q].N – это уже не счетчик, а указатель на следующий элемент списка Q. Соответственно, A[R].N принимает нулевое значение, которое можно трактовать как пустую ссылку. Случай, когда список Q пуст задается значениями Q=0, R=0.

Укрупненная блок схема алгоритма топологической сортировки выглядит следующим образом:

1. Инициализация массива A.

2. Ввод исходных данных вида М  K.

3. Подсчет количества предшественников и формирование списков преемников.

4. Организация списка Q и задание его хвоста R

5. L:= 0. { Количество элементов, выведенных на печать }

6. Если Q=0, то переход на п13.

7. Извлечение и печать первого элемента списка Q.

8. L:=L+1

9. Если L=max, то переход к п14.

10. Просмотр преемников элемента с номером Q, пересчет числа предшественников этих элементов. Если у какого–либо элемента P число предшественников стало равным нулю, то включить данный элемент в список Q с конца: A[R].data.N:=P; R:=P.

11. Перестроение начала списка: Q:=A[Q].data.N

12. Переход к п6.

13. Вывод: «полное решение не существует»

14. Конец работы.