Реализация структурных типов.

Достаточно иметь в нашем языке единственную переменную - с некоторым стандартным именем Memory (память) - указывая все нужные значения как некоторые подстроки Memory[i, l] этой переменной. Далее мы используем обычные имена переменных вместо непривычных имен вида Memory[i, l].

Индекс i называется адресом значения Memory[i, l]. Понятно, что когда длина поля l заранее известна, то по значению i можно однозначно восстановить содержимое поля Memory[i, l]. Таким образом, каждое имя переменной имеет числовое значение - адрес начала поля соответствующей этой переменной.

Значения структурных типов представляется в виде совокупности полей. Так, массив array[1..n] of T - это последовательность n битовых полей, каждое длины Len(T) - т.е. некоторое битовое поле Memory[AdrA, L] длины L=Len(T)*n

Аналогично, запись record N₁: T₁; …; N_m: T_m end - последовательность m битовых полей разных длин Len(T₁), …, Len(T_m) - т.е. снова некоторое битовое поле Memory[AdrRec, L] длины L= Len(T₁)+…+Len(T_m). Нетрудно вычислить AdrRec+ Len(T₁)+…+Len(T_k-1) - адрес начала поля, содержащего значение r. N_k и таким образом реализовать операцию доступа по имени, для каждого имени N_k.

 

 

Инф Списки, стеки, очереди и их применение.

Рассмотрим некоторые общие принципы реализации абстрактных типов на примере двух простых и естественных типов - стек и очередь.

Основным множеством типа является множество всех (конечных) последовательностей f произвольной длины LenF над некоторым базовым типом T - f Î Nà T, Dom(f)=[1..LenF], LenF Î N. Т.е. оба типа, вообще говоря, - динамические; в случае фиксированной длины можно говорить о статических.

Интуитивная " идея" стека - " тот, кто пришел последним, уходит первым" или идея магазинной памяти.

Операторы и функции определения стека.

Create(r) - создать пустой стек с именем r. Начиная работать в любом состоянии s, оператор доопределяет s, добавляя в него пару rà < > (< > - пустая последовательность)

Destroy(r) - обратная к Create операция - убирает из текущего состояния пару rà R. Имя r перестает существовать, доступ к стеку теряется.

Внимание - важно понимать, что эти операторы добавляют и удаляют имена, не значения - т.е. изменяют область определения состояния Dom(s).

Push(r, x) - добавить компоненту x в верхушку стека - начиная работать в состоянии rà R, cо стеком длины Len(R) Dom(R)=[1..Len(R)], этот оператор неявно доопределяет Dom(R) до [1..Len(R)+1] и осуществляет присваивание R[Len(R)+1]: =x.

Pop(r, x) - осуществляет присваивание x: =R[Len(R)] (кладет верхнюю компоненту стека в x) и сокращает Dom(R) до [1..Len(R)-1] (уничтожает верхушку стека).

Empty(r)= true » Len(R)=0 (т.е. стек пуст)

Интуитивная идея очереди - " тот, кто пришел первым, первым и уйдет"

Операторы и функции определения очереди.

Create(r), Destroy(r) - тождественны соответствующим стековым операциям.

Put(r, x) - Поставить В Очередь - добавить компоненту x (базового типа T) в конец очереди - начиная работать в состоянии rà R, cо очередью длины Len(R) Dom(R)=[n..m], этот оператор неявно доопределяет Dom(R) до [n..m+1] и осуществляет присваивание R[m]: =x.

Get(r, x) - Вывести Из Очереди - осуществляет присваивание x: =R[n] (кладет первую компоненту очереди в x) и сокращает Dom(R) до [n+1..m] (уничтожает начало очереди).

Предикат Empty(r) (очередь пуста) - тождественен соответствующему предикату над стеком.

Реализация стеков и очередей (псевдодинамическими) массивами.

Псевдодинамические массивы - последовательности переменной длины m, m£ MaxLen, где MaxLen - константа.

const MaxLen=100;

type tIndex=1..MaxLen;

tArray=array[tIndex];

tPseudoArray=

record content: tArray;

top: tIndex;

end;

Содержимому стеков сопоставляется содержимое массивов, а стековым операциям - соответствующие алгоритмы обработки массивов.

Обратимся к моделированию очередей. Определяются " псевдодинамические" массивы с двумя концами.

tPseudoArray2=

record content: tArray; {содержимое/компоненты массива}

start, finish: tIndex; {начало+1 и конец-1 массива -}

{начало правой кучи и конец левой кучи}

end; tQueue=tPseudoArray2;

Реализация операций - класть значения в конец, а брать - из начала массива - порождает частный случай проблемы динамического распределения памяти: Вводя в конец и выводя из начала массива значения компонент, мы весьма скоро можем оказаться в ситуации, когда свободной памяти много, а класть компоненты некуда! В этом частном случае ее нетрудно решить, объединяя две части кучи, мысленно рассматривая массив как кольцо.

Проблема распределения памяти. Списочные структуры.

Проблема ее фрагментированности (" проблема кучек" ):

необходимо сохранить некоторую последовательность f; но нет ни одной кучки, достаточной для хранения всех элементов последовательности f в естественном порядке; хотя совокупного объема свободной памяти для этого достаточно.

Необходимое и одновременно изящное решение - хранить f в виде функции F: Nà N´ T c произвольной (т.е. " дырявой" и не упорядоченной) областью определения Dom(F)= {n₁ , n₂.,..., n_k}, такой, что

(*) F(n₁)=< n₂, f(1)>, F(n₂)=< n₃, f(2)>,.., F(n_i)=< n_i+1, f(i)>, … F(n_k)=< n_k+1, f(k)>

Такой способ хранения последовательностей называется списковой организацией памяти, или просто списком. По определению, список F хранит значения f и индекс следующего ее значения. Указатель n₁ называют головой списка, указатель n_k+1, не принадлежащий Dom(F) - признаком конца списка. Обычно, в качестве признака выделяют специальный " пустой" указатель 0, единственный смысл которого - ни на что не указывать.

Основные операции над списками - перечисление, вставка и удаление компонент - никак не используют арифметические операции на Dom(F), т.е. тот факт, Dom(F)Ì N, а лишь то, что они, в качестве имен, указывают (ссылаются) на значения. Это и делает возможным реализацию списков ссылочным типом.

type

tComponent=record value: T; next: p: pComponent end;

pComponent=^tComponent;

pList=pComponent;

Реализация стеков и очередей списками.

Общее решение проблемы распределения памяти в виде списков в реализации абстрактных линейных типов - поставить значениям стека список с одной, а очереди - с двумя активными компонентами.

 

10. Инф Алгоритмы полного перебора на примере задачи о перечислении всех правильных раскрасок графа.

Пусть T - множество значений некоторого порядкового типа, T={Первый< Второй< …Последний}, succ - соответствующая функция следования, а Seq(L)=Seq(T, L)=[1..L]à T - множество всех последовательностей длины L.

Лексикографический, или словарный порядок на Seq(L) определяется следующим образом. Пусть a, b Î Seq(n), a¹ b и N=N(a, b)=min {n: a(n) ¹ b(n)}- наименьший номер i, на котором они различаются. Тогда a считается меньшей b, если у а на N-ом месте стоит меньшая (в смысле порядка на T) компонента, чем у b: a< b »def a(N)< _T b(N).

Алгоритм определения следующей последовательности.

Следующая(a)=b » найдется число N такое, что для всех i, i Î [1..N], b(i)=a(i), b(N)=succ(a(N)) и b(j)=Первый, для всех j, j Î [N+1..L]. N=max{i: a(i) ¹ Последний}.

a) Вынимай из конца последовательности а все последние (в T) значения, пока не найдешь меньшего значения с. Если такого значения с нет, то а - это последняя последовательность.

б) Положи в конец a значение succ(c)

в) Доложи в конец последовательности необходимое число первых значений.

Обработка последовательностей " с одного конца", реализуется в терминах стеков.

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

Задача о раскраске графа. Найти (" распечатать" ) все правильные раскраски произвольного графа с фиксированным числом вершин n в m цветов. Раскраска правильная, если никакие две соседние вершины не окрашены в один цвет.

Предварительный анализ

found=$ r Î tРаскраска (правильная(r))

где Правильная(r)= " i, jÎ Вершины (Соседи(i, j)à Цвет(r, i)¹ Цвет(r, j))

⇐ Предыдущая123Следующая ⇒

Поделиться: