Курс за второй семестр. Абстрактные типы данных

Вид материала

Содержание

Задача раскраски.
Делаем первые выводы относительно определения типа данных.
Перечисление последовательностей фиксированной длины.
Два взгляда на диаграммы – графы и автоматы.
Х – выделенная переменная, произвольный массив. Остальные переменные не определены. Выход: любое состояние, в котором Х
Как сократить перебор с возвратом. Перечисление последовательностей переменной длины
Словарный порядок на последовательностях произвольной длины
Переход к следующей раскраске при новом определении словарного порядка
Статическая реализация стеков.
Очереди. Статическая реализация.
Get(q:tQueue;var x:T)
Статическая реализация деревьев.
Автоматы как структуры данных
Статическая реализация графов. Проблема фрагментации памяти.
Общая схема реализации автомата как списка.
Обработка кучи.
Динамическая реализация абстрактных типов ссылками.
Синтаксис типов.
Реализация очередей.
Обработка деревьев. Деревья выражений.
...
Полное содержание

Подобный материал:

1 2 3 4 5 6 7 8

Программирование и алгоритмические языки.

Курс за второй семестр.

Абстрактные типы данных.

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

«Программы = алгоритмы (процедуры) + структуры данных»

Н. Вирт

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

Тип

Задача раскраски.

Выяснить, можно ли данную карту правильно раскрасить данным количеством цветов. Если да, то предъявить все возможные раскраски. Раскраска правильная, если никакие две соседние страны не окрашены в один цвет.

Делаем первые выводы относительно определения типа данных.

Type tСтраны = 1..n; {Можно взять произвольный порядковый тип}

tКарта = array [tСтраны,tСтраны] of Boolean; {На этом типе обязана быть определена единственная функция}

var карта: tКарта;

m:cardinal;

Можно: boolean;

Раскраска: tРаскраска; {Определение типа откладываем до определения операций, которые нужны в алгоритме}

Function Правильная (раскраска: tРаскраска):boolean;

{правильная:=i,jtСтраны (соседи (i,j)(i
{Стрелка – логическая связь – «если, то»}

{правильная:= }

Begin

Result:=true;

i:=первая страна;

while (i<=последняя страна) and (Result) do

begin

j:=succ(i);

while (j<=последняя страна) and Result do

begin

if соседи (i,j) then if раскраска (i) = раскраска (j) then Result:=false;

else j:=succ(j);

end;

i:=succ(i);

end;

Begin

{Можно:= раскраска – tРаскраска - правильная}

можно:=false;

раскраска:=первая раскраска;

while not (конечная раскраска) do

Begin

If (правильная раскраска) then

Begin

Можно:=true;

Write (Правильная раскраска);

End;

Раскраска:=следующая раскраска;

End;

End.

Мы отождествляем тип tКарта с функцией “Соседи”, задавая её в виде булевского массива. Не забудь переименовать в алгоритме Соседи на Карта!

tРаскраска: tСтранаtЦвет

array[tСтрана] of tЦвет

Однако основной алгоритм требует, чтобы тип tРаскраска был порядковым. Нам необходима возможность перечислять раскраску.

Перечисление последовательностей фиксированной длины.

n циклов дали бы нужный порядок, но мы не можем выразить такой оператор синтаксически, однако это даёт идею того, в каком порядке можно перебирать последовательности (конечные функции) – в словарном (лексикографическом).

a=a₁,…,a_n

b=b₁,…,b_n

ai₀i₀, где i₀ – наименьший символ i такой, что a_ib_i и i0 a_i=b_i

Procedure Следующая ({var Раскраска: tРаскраска;var Кончились:boolean});

{Выдаёт раскраску, следующую за данной, кладёт «Кончились» в true, если таковой нет}

Blog