Машина Тьюринга

Списки - Динамические структуры данных.

Очереди

Построение деревьев кратчайших путей.

В общем случае строятся p деревьев кратчайших путей. Нам нужно построить 5 деревьев.

Построим эти деревья, зная длины кратчайших путей (они стоят в матрице D₅) и ориентируясь по диаграмме на рис. 9.

Деревья показаны на рис. 10.

Замечание. Если в графе отсутствуют контуры отрицательной длины, то в каждой строке и каждом столбце матрицы D_p по крайней мере одна длина сохраняется такой же, какой она была в матрице D₀ (длина кратчайшего пути из одной дуги). В нашем случае имеем:

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

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

Очередь - линейный список, доступ к элементам которого происходит по принципу FIFO (First In and First Out - первым пришел и первым ушел).

Для очереди характерны две операции - Занесение элемента в очередь и выбор элемента из очереди. В очереди доступны две позиции - начало (из этой позиции происходит выбор) и конец (в эту позицию заносится входящий элемент).

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

Применение:

диспетчеризация задач операционной системой (системная задача);

буферизация ввода/вывода (системная задача);

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

Пример программы с процедурами постановки и выбора из очереди - Queue_Test.

Функция qretrieve() извлекает из очереди первый элемент; хранившиеся в этом элементе данные разрушаются. Если из очереди удалены все элементы, она становится пустой. На самом деле qretrieve() в этом примере не разрушает информацию, но информацию можно считать удаленной, так как дальнейший доступ к ней невозможен.

Программа создания очереди на языке "Паскаль"

// FIFO First In - First Out Очередь

// Queue

Programm Queue_Test;

var

q:array[0..30] of Integer;

qnext,qindex,qlength:Integer;

procedure qstore(i:Integer);

begin

if (qnext+1)<qlength then

begin

qnext:=qnext+1;

q[qnext]:=i

end

else

writeln('Мест нет')

end;function qretrieve():Integer;

begin

if qindex=qnext then

begin

writeln('Очередь пуста');

qretrieve:=0;

end

else

begin

qindex:=qindex+1;

qretrieve:=q[qindex]

end;

end;begin Содержимое очереди

qlength:=30;

qnext:=0;

qindex:=0;

qstore(1); 1

qstore(2); 1 2

qstore(3); 1 2 3

qretrieve(); {возвращает 1} 2 3

qstore(4); 2 3 4

qretrieve(); {возвращает 2} 3 4

qretrieve(); {возвращает 3} 4

qretrieve(); {возвращает 4} Очередь пуста

end.