русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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


Дата добавления: 2013-12-23; просмотров: 811; Нарушение авторских прав


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

Очереди

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

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

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

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

 


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

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

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

 

 

 

 

 

 

 

Очередь - линейный список, доступ к элементам которого происходит по принципу 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.

 



<== предыдущая лекция | следующая лекция ==>
Алгоритм Флойда определения кратчайших путей между всеми парами вершин данного графа | Связные списки


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.006 сек.