Классификация структур данных.

Раздел 1. Классификация структур данных. Программируя решение любой задачи, необходимо выбрать уровень абстрагирования. Иными словами, определить множество данных, представляющих предметную область решаемой задачи. При выборе следует руководствоваться проблематикой решаемой задачи и способами представления информации. Здесь необходимо ориентироваться на те средства, которые предоставляют системы программирования и вычислительная техника, на которой будут выполняться программы. Во многих случаях эти критерии не являются полностью независимыми. Вопросы представления данных часто разбиваются на различные уровни детализации. Уровню языков программирования соответствуют абстрактные типы и структуры данных. Рассмотрим их реализацию в языке программирования Turbo-Pascal. Простейшим типом данных является переменная. Существуют несколько встроенных типов данных. Например, описание Var i, j : integer; x : real; s: string; объявляет переменные i, j целочисленного типа, x - вещественного и s - строкового. Переменной можно присвоить значение, соответствующее ее типу I:=46; X:=3.14; S:="строка символов"; Такие переменные представляют собой лишь отдельные элементы. Для того чтобы можно было говорить о структурах данных, необходимо иметь некоторую агрегацию переменных. Примером такой агрегации является массив. Тема 1.1 Массивы, записи, множества, динамические структуры данных. Массивы. Массив объединяет элементы одного типа данных. Более формально его можно определить как упорядоченную совокупность элементов некоторого типа, адресуемых при помощи одного или нескольких индексов. Частным случаем является одномерный массив Var l : array [1..100] of integer; В приведенном примере описан массив l, состоящий из элементов целочисленного типа. Элементы могут быть адресованы при помощи индекса в диапазоне значений от 1 до 100. В математически х расчетах такой массив соответствует вектору. Массив не обязательно должен быть одномерным. Можно описать в виде массива матрицу 100*100 Var M : array [1..100,1..100] of real; В этом случае можно говорить уже о двумерном массиве. Аналогичным образом можно описать массивс большим числом измерений, например трехмерный Var M_3_d : array [0..10,0..10,0..10] of real; Теперь можно говорить уже о многомерном массиве. Доступ к элементам любого массиваосуществляется при помощи индексов как к обычной переменной. М_3_d [0,0,10]:=0.25; M[10,30]:=m_3_d[0,0,10]+0.5; L[i]:=300; Записи. Более сложным типом является запись. Основное отличие записи заключается в том, что она может объединять элементы данных разных типов. Рассмотрим пример простейшей записи Type Person = record Name: string; Address: string; Index: longint; end; Запись описанного типа объединяет четыре поля. Первые три из них символьного типа, а четвертое -целочисленного. Приведенная конструкция описывает тип записи. Для того чтобы использовать данные описанного типа, необходимо описать сами данные. Один из вариантов использования отдельных записей - объединение их в массив, тогда описание массива будет выглядеть следующим образом Var Persons : array[1..30] of person; Следует заметить, что в Turbo-pascal эти два описания можно объединить в виде описания так называемого массива записей Var Persons : array[1..30] of record Name: string; Address: string; Index: longint; end; Доступ к полям отдельной записи осуществляется через имя переменной и имя поля. Persons[1] . Name:="Иванов"; Persons[1] . Adress:='город Санкт-Петербург ┘"; Persons[2] . Name:="Петров"; Persons[2] . Adress:='город Москва ┘"; Разумеется, что запись можно использовать в качестве отдельной переменной, для этого соответствующая переменная должна иметь тип, который присвоен описанию записи Type Person = record Name: string; Address: string; Index: Longint; end; Var Person1: person; Begin Person1.index:=190000; Множества. Наряду с массивами и записями существует еще один структурированный тип - множество. Этот тип используется не так часто, хотя его применение в некоторых случаях является вполне оправданным. Тип множество соответствует математическому понятию множества в смысле операций, которые допускаются над структурами такого типа. Множество допускает операции объединения множеств (+),пересечения множеств (*), разности множеств (-) и проверки элемента на принадлежность к множеству (in). Множества также как и массивы объединяют однотипные элементы. Поэтому в описании множества обязательно должен быть указан тип его элементов. Var RGB, YIQ, CMY : Set of string; Здесь мы привели описание двух множеств, элементами которых являются строки. В отличие от массивов и записей здесь отсутствует возможность индексирования отдельных элементов. CMY:= ["M ","C ","Y "]; RGB:= ["R","G","B"]; YIQ:=[ "Y ","Q ","I "]; Writeln ("Пересечение цветовых систем RGB и CMY ", RGB*CMY); Writeln ("Пересечение цветовых систем YIQ и CMY ",YIQ*CMY); Операции выполняются по отношению ко всей совокупности элементов множества. Можно лишь добавить, исключить или выбрать элементы, выполняя допустимые операции. Динамические структуры данных. Мы ввели базовые структуры данных: массивы, записи, множества. Мы назвали их базовыми, поскольку из них можно образовывать более сложные структуры. Цель описания типа данных и определения некоторых переменных как относящихся к этому типу состоит в том, чтобы зафиксировать диапазон значений, присваиваемых этим переменным, и соответственно размер выделяемой для них памяти. Поэтому такие переменные называются статическими. Однако существует возможность создавать более сложные структуры данных. Для них характерно, что в процессе обработки данных изменяются не только значения переменных, но и сама их структура .Соответственно динамически изменяется и размер памяти, занимаемый такими структурами. Поэтому такие данные получили название данных с динамической структурой. Тема 1.2 Списки. Линейные списки. Наиболее простой способ связать некоторое множество элементов - это организовать линейный список. При такой организации элементы некоторого типа образуют цепочку. Для связывания элементов в списке используют систему указателей. В рассматриваемом случае любой элемент линейного списка имеет один указатель, который указывает на следующий элемент в списке или является пустым указателем, что означает конец списка. В языке Turbo Pascal предусмотрены два типа указателей - типизированные и не типизированные указатели. В случае линейного списка описание данных может выглядеть следующим образом. type element = record data:string; next: pointer; end; var head: pointer; current, last : ^element; В данном примере элемент списка описан как запись, содержащая два поля. Поле data строкового типа служит для размещения данных в элементе списка. Другое поле next представляет собой не типизированный указатель, который служит для организации списковой структуры. В описании переменных описаны три указателя head, last и current. Head является не типизированным указателем. Указатель current является типизированным указателем, что позволяет через него организовать доступ к полям внутри элемента, имеющего тип element. Для объявления типизированного указателя обычно используется символ ^, размещаемый непосредственно перед соответствующим типом данных. Однако описание типизированного указателя еще не означает создание элемента списка. Рассмотрим, как можно осуществить создание элементов и их объединение в список. В системе программирования Turbo Pascal для размещения динамических переменных используется специальная область памяти "heap-область". Heap-область размещается в памяти компьютера следом за областью памяти, которую занимает программа и статические данные, и может рассматриваться как сплошной массив, состоящий из байтов. Попробуем создать первый элемент списка. Это можно осуществить при помощи процедуры New New(Current); После выполнения данной процедуры в динамической области памяти создается динамическая переменная, тип которой определяется типом указателя. Сам указатель можно рассматривать как адрес переменной в динамической памяти. Доступ к переменной может быть осуществлен через указатель. Заполним поля элемента списка. Current^.data:= "данные в первом элементе списка " ; Сurrent^.next:=nil; Значение указателя nil означает пустой указатель. Обратим внимание на разницу между присвоением значения указателю и данным, на которые он указывает. Для указателей допустимы только операции присваивания и сравнения. Указателю можно присваивать значение указателя того же типа или константу nil. Данным можно присвоить значения, соответствующие декларируемым типам данных. Для того чтобы присвоить значение данным, после указателя используется символ ^. Поле Сurrent^.next само является указателем, доступ к его содержимому осуществляется через указатель Current. В результате выполнения описанных действий мы получили список из одного элемента. Создадим еще один элемент и свяжем его с первым элементом. Head:=Current; New(last); Last^.data:= "данные во втором элементе списка " ; Last^.next:=nil; Сurrent^.next:=nil; Непосредственно перед созданием первого элемента мы присвоили указателю Head значение указателя Current. Это связано с тем, что линейный список должен иметь заголовок. Другими словами, первый элемент списка должен быть отмечен указателем. В противном случае, если значение указателя Current в дальнейшем будет переопределено, то мы навсегда потеряем возможность доступа к данным, хранящимся в первом элементе списка. Динамическая структура данных предусматривает не только добавление элементов в список, но и их удаление по мере надобности. Самым простым способом удаления элемента из списка является переопределение указателей, связанных с данным элементом (указывающих на него). Однако сам элемент данных при этом продолжает занимать память, хотя доступ к нему будет навсегда утерян. Для корректной работы с динамическими структурами следует освобождать память при удалении элемента структуры. В языке TurboPascal для этого можно использовать функцию Dispose. Покажем, как следует корректно удалить первый элемент нашего списка. Head:=last; Dispose(current); Рассмотрим пример более сложной организации списка. Линейный список неудобен тем, что при попытке вставить некоторый элемент перед текущим элементом требуется обойти почти весь список, начиная с заголовка, чтобы изменить значение указателя в предыдущем элементе списка. Чтобы устранить данный недостаток введем второй указатель в каждом элементе списка. Первый указатель связывает данный элемент со следующим, а второй - с предыдущим. Такая организация динамической структуры данных получила название линейного двунаправленного списка (двусвязного списка). Интересным свойством такого списка является то, что для доступа к его элементам вовсе необязательно хранить указатель на первый элемент. Достаточно иметь указатель на любой элемент списка. Первый элемент всегда можно найти по цепочке указателей на предыдущие элементы, а последний - по цепочке указателей на следующие. Но наличие указателя на заголовок списка в ряде случаев ускоряет работу со списком. Наличие указателя на заголовок списка ускоряет процесс поиска, так как не требуется сначала найти первый элемент, а затем - сделать обход списка. Циклические списки Линейные списки характерны тем, что в них можно выделить первый и последний элементы, причем для однонаправленного линейного списка обязательно нужно иметь указатель на первый элемент. Циклические списки также как и линейные бывают однонаправленными и двунаправленными. Основное отличие циклического списка состоит в том, что в списке нет пустых указателей. Рис. Однонаправленный циклический список Последний элемент списка содержит указатель, связывающий его с первым элементом. Для полного обхода такого списка достаточно иметь указатель только на текущий элемент. В двунаправленном циклическом списке система указателей аналогична системе указателей двунаправленного линейного списка. Рис. Двунаправленный циклический список Двунаправленный циклический список позволяет достаточно просто осуществлять вставки и удаления элементов слева и справа от текущего элемента. В отличие от линейного списка, элементы являются равноправными и для выделения первого элемента необходимо иметь указатель на заголовок. Однако во многих случаях нет необходимости выделять первый элемент списка и достаточно иметь указатель на текущий элемент. В данном примере указатель на первый элемент списка отсутствует. Для предотвращения зацикливания при обходе списка во время поиска указатель на текущий элемент предварительно копируется и служит ограничителем. Мультисписки. Иногда возникают ситуации, когда имеется несколько разных списков, которые включают в свой состав одинаковые элементы. В таком случае при использовании традиционных списков происходит многократное дублирование динамических переменных и нерациональное использование памяти. Списки фактически используются не для хранения элементов данных, а для организации их в различные структуры. Использование мультисписков позволяет упростить эту задачу. Мультисписок состоит из элементов, содержащих такое число указателей, которое позволяет организовать их одновременно в виде нескольких различных списков. За счет отсутствия дублирования данных память используется более рационально. Рис. Объединение двух линейных списков в один мультисписок. Экономия памяти - далеко не единственная причина, по которой применяют мультисписки. Многие реальные структуры данных не сводятся к типовым структурам, а представляют собой некоторую комбинацию из них. Причем комбинируются в мультисписках самые различные списки - линейные и циклические, односвязные и двунаправленные. Раздел 2. Типы данных линейной структуры. Тема 2.1 Данные элементарных типов. Данные элементарных типов представляют собой единое и неделимое целое. В каждый момент времени они могут принимать только одно значение. Набор элементарных типов в разных языках программирования несколько различаются, однако есть типы, которые поддерживаются практически везде. Рассмотрим их на примере языка Паскаль: var i, j: integer; x: real; s: char; b: boolean; p: pointer; Здесь объявлены переменные i, j целочисленного типа, x – вещественного, s – символьного, b – логического типа и p – указатель. К данным элементарных типов можно обращаться по их именам: i := 46; x := 3.14; s := ’А’; b := true; Тема 2.2 Данные числового, вещественного, символьного, логического типов. Данные числовых типов. С помощью целых чисел может быть представлено количество объектов, являющихся дискретными по своей природе (т. е. счетное число объектов). Диапазон возможных значений целых типов зависит от их внутреннего представления, которое может занимать 1, 2 или 4 байта. В таблице приводится перечень целых типов, размер памяти для их внутреннего представления в битах, диапазон возможных значений. Операции над данными числовых типов Над числовыми типами, как и над всеми другими возможны, прежде всего, четыре основных операции: создание, уничтожение, выбор, обновление. Специфическими операциями над числовыми типами являются арифметические операции: сложение, вычитание, умножение, деление. Операция возведения в степень в некоторых языках также является базовой и обозначается специальным символом или комбинацией символов, в других – выполняется встроенными функциями. Следует обратить внимание на то, что операция деления по-разному выполняется для целых и вещественных чисел. При делении целых чисел дробная часть результата отбрасывается, как бы близка к 1 она ни была. В связи с этим в языке Паскаль имеются даже разные обозначения для деления вещественных и целых чисел – операции «/» и «div» соответственно. В других языках оба вида деления обозначаются одинаково, а тип деления определяется типом операндов. Для целых операндов возможна еще однаоперация – остаток от деления (в языке Паскаль операция «mod»). Еще одна группа операций над числовыми типами – операции сравнения >, <, ≥, ≤, =, <>. Существенно, что хотя операндами этих операций являются данные числовых типов, результат их имеет логический тип – «истина» или «ложь». Говоря об операциях сравнения, следует обратить внимание на особенность выполнения сравнений на равенство/неравенство вещественных чисел. Поскольку эти числа представляются в памяти с некоторой (не абсолютной) точностью, сравнения их не всегда могут быть абсолютно достоверны. Поскольку одни и те же операции допустимы для разных числовых типов, возникает проблема арифметических выражений со смешением типов. В реальных задачах выражения со смешанными типами встречаются довольно часто. Поэтому большинство языков допускает выражения, операнды которых имеют разные числовые типы, но обрабатываются такие выражения в разных языках по-разному. В одних языках все операнды выражения приводятся к одному типу, а именно к типу той переменной, в которую будет записан результат, а затем уже выражение вычисляется. В других (например, язык Си) преобразование типов выполняется в процессе вычисления выражения, при выполнении каждой отдельной операции, без учета других операций; каждая операция вычисляется с точностью самого точного участвующего в ней операнда. Данные вещественного типа Данные вещественного типа в отличие от целочисленных типов, значения которых всегда представляются в памяти ЭВМ абсолютно точно, значение вещественных типов определяет число лишь с некоторой конечной точностью, зависящей от внутреннего формата вещественного числа. Суммарное количество байтов, диапазоны допустимых значений чисел вещественных типов, а также количество значащих цифр после запятой в представлении чисел приведены в таблице. Данные символьного типа Значением символьного типа char являются символы из некоторого предопределенного множества. В качестве примеров этих множеств можно назвать ASCII (American Standard Code for Information Interchange). Это множество состоит из 256 разных символов, упорядоченных определенным образом, и содержит символы заглавных и строчных букв, цифр идругих символов, включая специальные управляющие символы. Значение символьного типа char занимает в памяти 1 байт. Код от 0 до 255 в этом байте задает один из 256 возможных символов ASCII таблицы. ASCII включает в себя буквенные символы только латинского алфавита. Символы национальных алфавитов занимают «свободные места» в таблице кодов и, таким образом, одна таблица может поддерживать только один национальный алфавит. Этот недостаток преодолен во множестве UNICODE. В этом множестве каждый символ кодируется двумя байтами, что обеспечивает более 216 возможных кодовых комбинаций и дает возможность иметь единую таблицу кодов, включающую в себя все национальные алфавиты. UNICODE, безусловно, является перспективным, однако, повсеместный переход к двухбайтным кодам символов может вызвать необходимость переделки значительной части существующего программного обеспечения. Специфические операции над символьными типами – только операции сравнения. При сравнении коды символов рассматриваются как целые числа без знака. Кодовые таблицы строятся так, что результаты сравнения подчиняются лексикографическим правилам: символы, занимающие в алфавите места с меньшими номерами, имеют меньшие коды, чем символы, занимающие места с большими номерами. Данные логического типа Значениями логического типа может быть одна из предварительно объявленных констант false (ложь) или true (истина). Данные логического типа занимают один байт памяти. При этом значению false соответствует нулевое значение байта, а значению true –любое ненулевое значение байта. Над логическими типами возможны операции булевой алгебры – НЕ (not), ИЛИ (or), И (and), ИСКЛЮЧАЮЩЕЕ ИЛИ (xor). Последняя операция реализована для логического типа не во всех языках. Кроме того, следует помнить, что результаты логического типа получаются при сравнении данных любых типов. Интересно, что в языке Си данные логического типа отсутствуют, их функции выполняют данные числовых типов, чаще всего типа int. В логических выражениях операнд любого числового типа, имеющий нулевое значение, рассматривается как «ложь», а ненулевое – как «истина». Результатами выражений логического типа являются целые числа 0 (ложь) или 1 (истина). Тема 2.3 Данные типа указатель. Тип указателя представляет собой адрес ячейки памяти. Физическое представление адреса существенно зависит от аппаратной архитектуры вычислительной системы. В языках программирования высокого уровня определена специальная константа nil, которая означает пустой указатель или указатель, не содержащий какой-либо конкретный адрес. При решении прикладных задач с использованием языков высокого уровня наиболее частые случаи, когда могут понадобиться указатели, следующие: 1) при необходимости представить одну и ту же область памяти, а следовательно, одни и те же физические данные как данные разной логической структуры. В этом случае вводятся два или более указателей, которые содержат адрес одной и той же области памяти, но имеют разный тип. Обращаясь к этой области памяти по тому или иному указателю, можно обрабатывать ее содержимое как данные того или иного типа; 2) при работе с динамическими структурами данных. Память под такие структуры выделяется в ходе выполнения программы, стандартные процедуры/функции выделения памяти возвращают адрес выделенной области памяти – указатель на нее. К содержимому динамически выделенной области памяти можно обращаться только через такой указатель. В языках высокого уровня указатели могут быть типизированными и нетипизированными. При объявлении типизированного указателя определяется и тип данного в памяти, адресуемого этим указателем. Приведем пример объявления в языке Паскаль различных типизированных указателей: var ipt: ^integer; cpt: ^char; Здесь переменная ipt содержит адрес области памяти, в которой хранится целое число, а cpt – адрес области памяти, в которой хранится символ. Хотя физическая структура адреса не зависит от типа и значения данных, хранящихся по этому адресу, считается, что указатели ipt и cpt имеют разный тип. Нетипизированный указатель служит для представления адреса, по которому содержатся данные неизвестного типа. В Паскале это тип pointer. Работа с нетипизированными указателями существенно ограничена, они могут использоваться только для сохранения адреса, а обращение по адресу, задаваемому нетипизированным указателем, невозможно. Основными операциями, в которых участвуют указатели, являются присваивание, получение адреса, выборка. Присваивание является двухместной операцией, оба операнда которой указатели. Как и для других типов, операция присваивания копирует значение одного указателя в другой, в результате оба указателя будут содержать один и тот же адрес памяти. Если оба указателя, участвующие в операции присваивания типизированные, то оба они должны указывать на данные одного и того же типа. Операция получения адреса – одноместная, ее операнд может иметь любой тип. Результатом является типизированный (в соответствии стипом операнда) указатель, содержащий адрес операнда. Операция выборки – одноместная, ее операндом является типизированный указатель. Результатом этой операции являются данные, выбранные из памяти по адресу, заданному операндом. Тип результата определяется типом указателя. Перечисленных операций достаточно для решения задач прикладного программирования, поэтому набор операций над указателями, допустимых в языке Паскаль, этим и ограничивается. Системное программирование требует более гибкой работы с адресами, поэтому, например, в языке Си доступны также операции адресной арифметики. Раздел 3. Алгоритмы сортировки массивов. Задача сортировки является такой же базовой, как задача поиска. В практических условиях эти задачи взаимосвязаны. Решению проблем, связанных с сортировкой, посвящено множество фундаментальных научных исследований, разработано множество алгоритмов. В общем случае сортировку следует понимать как процесс перегруппировки заданного множества объектов в определенном порядке. Часто при сортировке больших объемов данных нецелесообразно переставлять сами элементы, поэтому для решения задачи выполняется упорядочивание элементов по индексам. То есть индексы элементов выстраивают в такой последовательности, что соответствующие им значения элементов оказываются отсортированными по условию задачи. Сортировка применяется для облегчения поиска элементов в упорядоченном множестве. Задача сортировки одна из фундаментных в программировании. Сортировка – это упорядочивание набора однотипных данных по возрастанию или убыванию. Тема 3.1 Сортировка массивов методом выбора. Это наиболее естественный алгоритм упорядочивания. При данной сортировке из массива выбирается элемент с наименьшим значением и обменивается с первым элементом. Затем из оставшихся n - 1 элементов снова выбирается элемент с наименьшим ключом и обменивается со вторым элементом, и т.д. (риc.) Шаги алгоритма: - находим минимальное значение в текущей части массива; - производим обмен этого значения со значением на первой неотсортированной позиции; - далее сортируем хвост массива, исключив из рассмотрения уже отсортированные элементы. Исходная последовательность N=6: 3 1 7 5 6 4 2 max =6 из a[0]…a[N-1] 3 1 2 5 6 4 7 max =5 из a[0]…a[N-2] 3 1 2 5 4 6 7 max =4 из a[0]…a[N-3] 3 1 2 4 5 6 7 max =3 из a[0]…a[N-4] 3 1 2 4 5 6 7 max =2 из a[0]…a[N-5] 2 1 2 4 5 6 7 max =1 из a[0]…a[1] 1 1 2 4 5 6 7 //Описание функции сортировки методом простого выбора void SelectionSort (int k,int x[max]) { int i,j,min,temp; for (i=0;i0;i--) for (j=0;jx[j+1]) { buf=x[j]; x[j]=x[j+1]; x[j+1]=buf; } } В пузырьковой сортировке количество сравнений всегда одно и то же, поскольку два цикла for повторяются указанное количество раз независимо от того, был список изначально упорядочен или нет. Это значит, что алгоритм пузырьковой сортировки всегда выполняет сравнений, где n – количество сортируемых элементов. Данная формула выведена на том основании, что внешний цикл выполняется раз, а внутренний выполняется в среднем раз. Пузырьковая сортировка имеет такую особенность: неупорядоченные элементы на «большом» конце массива занимают правильные положения за один проход, но неупорядоченные элементы в начале массива поднимаются на свои места очень медленно. Поэтому, вместо того чтобы постоянно просматривать массив в одном направлении, в последовательных проходах можно чередовать направления. Таким образом, элементы, сильно удаленные от своих положений, быстро станут на свои места. Данная версия пузырьковой сортировки носит название шейкер-сортировки (shaker sort сортировка перемешиванием, сортировка взбалтыванием, сортировка встряхиванием), поскольку действия, производимые ею с массивом, напоминают взбалтывание или встряхивание. Ниже показана реализация шейкер-сортировки. //Описание функции шейкер-сортировки void Shaker(int k,int x[max]){ int i,t; bool exchange; do { exchange = false; for(i=k-1; i > 0; --i) { if(x[i-1] > x[i]) { t = x[i-1]; x[i-1] = x[i]; x[i] = t; exchange = true; } } for(i=1; i < k; ++i) { if(x[i-1] > x[i]) { t = x[i-1]; x[i-1] = x[i]; x[i] = t; exchange = true; } } } while(exchange); //сортировать до тех пор, пока не будет обменов } Хотя шейкер-сортировка и является улучшенным вариантом по сравнению с пузырьковой сортировкой, она по-прежнему имеет время выполнения порядка . Это объясняется тем, что количество сравнений не изменилось, а количество обменов уменьшилось лишь на относительно небольшую величину. Тема 3.3 Сортировка челночным методом. При сортировке массива a[0], a[1], ..., a[N-1] челночным методом, начиная с первого элемента сравнивают два соседних элемента (a[i] и a[i+1]), если порядок не нарушен (a[i]<=a[i+1]), то продвигаются на один элемент вперед (i=i+1), если порядок нарушен (a[i]>a[i+1]), то производится перестановка и сдвигаются на один элемент назад (i=i-1). Таким образом сравнивая и переставляя элементы доходят до конца массива (i=N-1), при этом массив становится упорядоченным. Работа алгоритма иллюстрируется следующим примером: Исходная последовательность N=5 3 1 7 5 2 i=0 (порядок нарушен) 3 1 7 5 2 i=0 (порядок не нарушен) 1 3 7 5 2 i=1 (порядок не нарушен) 1 3 7 5 2 i=2 (порядок нарушен) 1 3 7 5 2 i=1 (порядок не нарушен) 1 3 5 7 2 i=2 (порядок не нарушен) 1 3 5 7 2 i=3 (порядок нарушен) 1 3 5 7 2 i=2 (порядок нарушен) 1 3 5 2 7 i=1 (порядок нарушен) 1 3 2 5 7 i=0 (порядок не нарушен) 1 2 3 5 7 i=1 (порядок не нарушен) 1 2 3 5 7 i=2 (порядок не нарушен) 1 2 3 5 7 i=3 (порядок не нарушен) 1 2 3 5 7 i=4: Итоговая последовательность 1 2 3 5 7 Программная реализация этого метода на языке Си, будет выглядеть следующей: #include #include #include main() { const N=5; int A[N]; int i; for (i=0; i>A[i]; //ввод значений массива int swap; i=0; while (iA[i+1]) {swap=A[i+1]; A[i+1]=A[i]; A[i]=swap; i--; if (i<0) i=0; } else i++; cout <A[j+1]), поменять знак операции сравнения на меньше (<), то последними элементами в подмассивах будут оказываться наименьшие значения и сортировка массива будет осуществляться по убыванию. Тема 3.4 Сортировка методом вставок. Данный метод сортировки массива основан на вставке элементов из неупорядоченной части массива в упорядоченную. Считается, что первоначально массив a[0], a[1], ..., a[N-1] является не отсортированным, поэтому упорядоченная часть будет состоять из одного первого элемента a[0], а неупорядоченная из всех элементов массива a[1], ..., a[N-1]. На каждом шаге метода из неупорядоченной части извлекается первый элемент и помещается в упорядоченную, так чтобы не нарушался порядок. При этом количество элементов в упорядоченной части увеличивается на 1, а в неупорядоченной уменьшается на 1. Процесс вставки элементов происходит до тех пор, пока весь массив не окажется отсортированным. Программная реализация этого метода на языке Си++, будет выглядеть следующей: #include #include #include main() { const N=6; int A[N]; int i,j,element; for (i=0; i>A[i]; //ввод значений массива { element=A[i]; j=i; while (A[j-1]>element) {A[j]=A[j-1]; j--; if (j<1) break; } A[j]=element; } for (i=0; i Real :: x=5.2 Write(*,’(f6.2)’) x Write(0,’(f6.2)’) x Write(6,’(f6.2)’) x Все операторы это – вывод на экран. Отсоединяются эти устройства автоматически после окончания работы программы. Эти устройства могут присоединяться к любому файлу. Каждый внешний файл имеет имя. Оно должно удовлетворять правилам именования операционной системы: ‘c\users\A123\f1.txt’ – это спецификация внешнего файла или, если это устройства - зарезервированные имена, например con, prn. Внешний файл присоединяется к устройству ввода/вывода в результате выполнения оператора OPEN . Теперь доступ к внешнему файлу выполняется по номеру устройства, к которому он присоединен. OPEN (unit=2, file = ‘c\users\A133\f1.txt’) Устройство не может быть присоединено более, чем к одному файлу и наоборот. Файл состоит из записей. Под словом «запись» понимается «логическая запись». Записью называют единицу обмена данными между программой и внешней памятью. Запишем в файлы по два целых числа различными способами: program main Integer::x=25, y=10 open(1, file='numbers1.txt') write(1,*) x write(1,*) y close(1) open(2, file='numbers2.txt') write(2,*) x, y close(2) end ! В файле number1.txt будет: 25 10 !в файле number2.txt будет: 25 10 Запишем в файл 5 чисел, используя различные форматы при записи: program main integer i open(10, file='number1.txt') do i=1,5 write (10, '(I3\)') i enddo close(1) end В файле получим: __1__2__3__4__5 program main integer i open(10, file='number1.txt') do i=1, 5 write (10, '(I3)') i enddo close(1) end В файле получим: __1 __2 __3 __4 __5 Все записи в файле имеют одинаковый вид. В Фортране различают следующие виды записей (в зависимости от представления данных): форматные – они состоят из символов кодовой таблицы. При вводе данные преобразуются из внешнего (символьного) представления - во внутреннее представление, а при выводе – из внутреннего во внешнее; неформатные (бесформатные), которые содержат данные во внутреннем машинном представлении, служат в основном для запоминания результатов в промежуточных вычислениях. конец файла. Вид записи задается в операторе (теперь говорят в утверждении) open спецификаторами form=’formated’ или form=’unformated’ Запись ''конец файла” не содержит данных и ставится автоматически за последней записью файла. Раздел 6. Типы данных нелинейной структуры. . Тема 6.1 Деревья. Корневое дерево (rooted tree) – это структура данных, которая представляет собой совокупность связанных узлов (nodes), один из которых является корнем дерева (root). Ребра (edges) связывают узлы дерева и устанавливают между ними отношение .родитель-дочерний. (parent-child). На рис. 1 приведен пример корневого дерева. Узел, который не имеет дочерних вершин, называется внешним узлом (external node), или листом (leaf node). На рис. это узлы: 4, 8, 9, 6 и 7. Аналогично, узел дерева, имеющий дочерние вершины называется внутренним узлом (internal node). Рис. Корневое дерево из 9 элементов (высота дерева 3). Любой внутренний узел по отношению к своим дочерним вершинам (child nodes) называется родительским (parent node). Узлы, имеющие общего родителя называются родственными, или сестринскими узлами (sibling nodes). Любой узел в поддереве некоторой вершины называется ее потомком (descendant), а вершина для этих узлов является предком (ancestor). Степень узла (node degree) – это количество его дочерних узлов. Высота узла (node height) – количество ребер в длиннейшем пути от узла до листа. Высота дерева (tree height) – количество ребер в длиннейшем пути от корня до листа. Глубина узла (node depth) или уровень узла (node level) – количество ребер в пути от узла до корня. Рассмотрим подробнее введенные определения. На рис. приведено дерево из 9 узлов. Вершина 2 является родителем для вершин 4 и 5, а также предком для узлов 4, 5, 8 и 9. Узлы 4 и 5 является сестринскими. Высота дерева равна 3, а количество уровней – 4. Степень узла 5 равна 2, а его высота 1. Тема 6.2 Бинарные деревья. Бинарное дерево (двоичное дерево, binary tree) – это корневое дерево, в котором каждый узел имеет не более двух дочерних вершин (0, 1 или 2 вершины). Полное бинарное дерево (full binary tree) – это бинарное дерево, в котором каждый узел имеет 0 или 2 дочерних узла. Пример такого дерева приведен на рис. Завершенное бинарное дерево (complete binary tree) – это бинарное дерево, в котором каждый уровень, возможно за исключением последнего, полностью заполнен узлами, а заполнение последнего уровня осуществляется слева направо (рис.). Совершенное бинарное дерево (perfect binary tree). Это бинарное дерево, в котором все листья имеют одинаковую глубину (рис.). При числе узлов n минимальной высотой n = log2(n + 1) − 1 обладает совершенное бинарное дерево, а максимальной высотой – бинарное дерево, в котором каждый внутренний узел имеет единственную дочернюю вершину (дерево вырождается в цепочку высоты n − 1). Следовательно, высота n любого бинарного дерева из n узлов ограничена снизу и сверху nlog2(n + 1)n − 1 ≤ n ≤ n − 1. Обход бинарных деревьев. Во многих алгоритмах, использующих деревья, возникает необходимость перебрать все узлы дерева начиная с корня. Такая процедура называется обходом дерева (tree traversal). Каждая вершина должна быть посещена один раз. Посещение вершины может быть связано с выполнением некоторых вычислений и или обработкой данных, хранящихся в ней. Обход бинарного дерева можно выполнять в ширину и в глубину. Все способы обходов дерева начинают свою работу с корня. При обходе в ширину (breadth first search, BFS) узлы дерева посещаются слева направо, уровень за уровнем. Например, при обходе в ширину дерева на рис. вершины будут посещены в следующем порядке: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. При обходе в глубину (depth first search, DFS) сперва посещаются все дочерние вершины левого поддерева и уже потом происходит переход к правому поддереву текущего узла. Существует три способа обхода дерева в глубину, различающихся порядком посещения вершин и их дочерних узлов. 1. Обход в прямом порядке (префиксный обход, preorder traversal) – каждый узел посещается до того, как рекурсивно посещены его потомки. Для каждого узла х рекурсивно выполняется последовательность действий посетить узел х; обойти левое поддерево; обойти правое поддерево. При таком обходе узлы дерева на рис. будут посещены в следующем порядке: 1, 2, 4, 8, 9, 5, 10, 3, 6, 7. 2. Симметричный обход (инфиксный обход, in-order traversal) – сперва посещаются потомки левого поддерева узла, затем сам Результат симметричного обхода дерева: 8, 4, 9, 2, 5, 10, 1, 6, 3, 7. 3. Обход в обратном порядке (постфиксный обход, post-order traversal) – каждый узел посещается после того, как рекурсивно посещены его потомки. Для каждого узла х рекурсивно выполняется последовательность действий: обойти левое поддерево, обойти правое поддерево, посетить узел х. Результат обхода в обратном порядке дерева на рис.: 8, 9, 4, 10, 5, 2, 6, 7, 3, 1. Тема 6.3 Пирамиды. Представляемые массивами деревья находят применение в имеющих большое значение приложениях с пирамидами (heaps), являющимися законченными бинарными деревьями, имеющими упорядочение узлов по уровням. В максимальной пирамиде (maximum heap) родительский узел больше или равен каждому из своих сыновей. В минимальной пирамиде (minimum heap) родительский узел меньше или равен каждому из своих сыновей. Эти ситуации изображены на рис. В максимальной пирамиде корень содержит наибольший элемент, а в минимальной — наименьший. Пирамида является списком, который хранит некоторый набор данных в виде бинарного дерева. Пирамидальное упорядочение предполагает, что каждый узел пирамиды содержит значение, которое меньше или равно значению любого из его сыновей. При таком упорядочении корень содержит наименьшее значение данных. Как абстрактная списковая структура пирамида допускает добавление и удаление элементов. Процесс вставки не подразумевает, что новый элемент занимает конкретное место, а лишь требует, чтобы поддерживалось пирамидальное упорядочение. Однако при удалении из списка выбрасывается наименьший элемент (корень). Пирамида используется в тех приложениях, где клиенту требуется прямой доступ к минимальному элементу. Как список пирамида не имеет операции поиска и осуществляет прямой доступ к минимальному элементу в режиме "только чтение". Все алгоритмы обработки пирамид сами должны обновлять дерево и поддерживать пирамидальное упорядочение. Пирамидальная сортировка. Пирамидальная сортировка (heap sort) основывается на организации элементов в массиве по типу двоичного (бинарного) дерева. Двоичным деревом называют иерархическую структуру данных, в которой каждый элемент имеет не более двух потомков: Рис Пример бинарного дерева. Пирамида представляет собой особый вид бинарного дерева, в котором значение каждого элемента больше, чем значение каждого из его потомков. Непосредственные потомки каждого узла не упорядочены, поэтому иногда левый потомок может оказаться больше правого, а иногда – наоборот. Пирамида представляет собой полное дерево, в котором заполнение нового уровня начинается только после того, как предыдущий уровень полностью заполнен, а все узлы на одном уровне заполняются последовательно: Рис. Пример пирамиды. Сортировка начинается с построения пирамиды, содержащей все элементы исходной последовательности. Ясно, что максимальный элемент окажется в вершине дерева, поскольку все её потомки обязательно должны быть меньше. Затем, вершина пирамиды записывается в конец последовательности, а пирамида с удаленным максимальным элементом переформировывается. В результате, на её вершине оказывается максимальный из оставшихся элементов, он записывается на соответствующее место, и процедура продолжается до тех пор, пока пирамида не опустеет. Таким образом, основную нагрузку алгоритма несут две процедуры: начальное построение пирамиды и переформирование пирамиды на каждом шаге. Для построения пирамиды можно воспользоваться её свойством – у каждого внутреннего узла ровно два непосредственных потомка, за исключением, быть может, одного узла на предпоследнем уровне. Следовательно, можно пронумеровать узлы, начиная с вершины по правилу: если узел имеет номер i, то его потомкам назначим номера 2*i и 2*i+1. В результате все узлы пирамиды получат уникальные номера в диапазоне 1 ~ N, что дает возможность хранить пирамиду в виде последовательности: При удалении наибольшего элемента пирамиды из вершины, корневой узел остается свободным. После перестроения пирамиды в него должен попасть больший из двух непосредственных потомков, в свою очередь аналогично нужно определить, кто встанет на его место и т.д. При этом пирамида должна оставаться настолько близкой к полному дереву, насколько возможно. С этой целью переформирование пирамиды будем начинать с крайнего правого элемента на нижнем уровне, перенося его на вершину. Затем к вершине применим процедуру, называемую «просеиванием вниз»: - если элемент не имеет потомков, то конец; - иначе меняем местами значения элемента и максимального из двух его непосредственных потомков; - переходим к изменившемуся потомку и выполняем для него ту же процедуру с шага 1. Такой подход к перестроению пирамиды можно использовать также и для построения её начального состояния: любые два элемента можно считать потомками некоторого свободного узла. Поскольку все элементы являются «листьями», со второй половиной последовательности можно ничего не делать. Начиная с набора листовых элементов, можно соединять их попарно до тех пор, пока не будет сформирована общая большая пирамида. Первый добавляемый корень в последовательности из N элементов будет иметь индекс N / 2 - 1. В итоге алгоритм начального построения пирамиды будет заключаться в последовательном применении процедур «просеивания вниз» ко всем элементам с индексами от N / 2 - 1 до 0. // Функция "просеивает" элемент номер i вниз в пирамиде heap размера size void fixHeap( double * heap, int i, const int size ) { // Индекс максимального элемента в текущей тройке элементов: int maxIdx = i ; // Значение текущего элемента: double value = heap[i]; while ( true ) { int childIdx = i * 2 + 1; //Индекс левого потомка // Если есть левый потомок и он больше текущего элемента, if ( ( childIdx < size ) && ( heap[ childIdx ] > value ) ) maxIdx = childIdx; // то он считается максимальным childIdx = i * 2 + 2; //Индекс правого потомка // Если есть правый потомок и он больше максимального, if ( ( childIdx < size ) && ( heap[ childIdx ] > heap[ maxIdx ] ) ) maxIdx = childIdx; // то он считается максимальным // Если текущий элемент является максимальным из трёх // (т.е. если он больше своих детей), то конец: if ( maxIdx == i ) break; // Меняем местами текущий элемент с максимальным: heap[i] = heap[ maxIdx ]; heap[ maxIdx ] = value; // Переходим к изменившемуся потомку i = maxIdx; } } // Пирамидальная сортировка массива heap размера size void heapSort( double * heap, int size ) { // Построение пирамиды из массива: for( int i = size / 2 - 1; i >= 0; --i ) fixHeap( heap, i, size ); // Сортировка с помощью пирамиды while( size > 1 ) // пока в пирамиде больше одного элемента { --size; // Отделяем последний элемент // Обмениваем местами корневой элемент и отделённый: double firstElem = heap[0]; heap[0] = heap[ size ]; heap[ size ] = firstElem; // "Просеиваем" новый корневой элемент вниз: fixHeap( heap, 0, size ); } } Раздел 7. Графы. . Тема 7.1 Основные понятия теории графов. Граф (graph) – объект, состоящий из множества кружков (точек) и множество соединяющих их линий. Кружки (точки) называются вершинами графа (nodes), линии со стрелками – дугами (arcs), без стрелок – ребрами (edges). Т.е. граф – это пара G=(V,E), где V - множество вершин, а E - семейство пар ребер ei=(vi1, vi2), vij принадлежит V. Вершины графа можно использовать для представления объектов, а дуги — для отношений между объектами. Графы обычно изображаются в виде геометрических фигур. В классическом графе отсутствуют петли, то есть ребра, соединяющие вершину саму с собой. Граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным (орграф). В отличие от ребер, дуги соединяют две неравноправные вершины: одна из них называется началом дуги (дуга из нее исходит), вторая - концом дуги (дуга в нее входит). Пример: G=(V,E): V={1, 2, 3, 4, 5}; E={(1,2), (1,5), (3,1), (5,2), (5,3), (5,4)}. Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным (две вершины равноправны, нет никакой разницы между "началом" и "концом" ребра). Чаще всего рассматривают графы, в которых все ребра имеют один тип – либо ориентированные, либо неориентированные. Две вершины v и u называются смежными, если они соединены ребром (дугой) е: e=(v,u). Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) - инцидентным соответствующим вершинам. Любому ребру инцидентно ровно две вершины, а вершине может быть инцидентно произвольное количество ребер. Два ребра называются смежными, если они инцидентны одной вершине. Степенью вершины в неориентированном графе называется число инцидентных ей ребер. Для ориентированного графа различают исходящую степень, определяемую как число выходящих из него ребер, и входящую степень, определяемую как число входящих в нее ребер. Сумма исходящей и входящей степеней называется степенью вершины. Изолированная вершина – это вершина со степенью 0 (нуль-граф). Мультигаф – из одной вершины в другую можно перейти разными способами (граф с кратными ребрами). Путем называется последовательность вершин v1, v2, …, vn, для которой существуют ребра (или дуги в орграфе) v1  v2, v2  v3, ..., vn-1  vn. Этот путь начинается в вершине v1 и, проходя через вершины v2, v3, ..., vn-1, заканчивается в вершине vn. Длина пути— количество дуг (ребер), составляющих путь, в данном случае длина пути равна n – 1. Путь называется простым, если все вершины на нем, за исключением, может быть, первой и последней, различны. Для неориентированного графа на рис. путями будут adbc и abc. Замкнутый путь без повторяющихся ребер называется циклом (или контуром в орграфе); без повторяющихся вершин (кроме первой и последней) - простым циклом. Полным называется граф, в котором проведены все возможные ребра. Для графа, имеющего n вершин, таких ребер будет n(n-1)/2. Вершина v достижима из вершины u, если существует путь, начинающийся в u и заканчивающийся в v. Граф называется связным, если все его вершины взаимно достижимы. На рисунке изображен связный граф. Если граф не является связным, то его можно разбить на связные подграфы, называемые компонентами. Компонента связности – это максимальный связный подграф. В общем случае граф может состоять из произвольного количества компонент связности. Любая изолированная вершина является отдельной компонентой связности. Например, в приведённом ниже графе содержится 4 компоненты связности: abhk, gd, c, f. Взвешенный граф – это граф, некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа. Числа-пометки носят названия вес, длина, стоимость. Длина пути во взвешенном графе – это сумма весов ребер (дуг), из которых состоит путь. Тема 7.2 Основные процедуры работы с графами. Добавление вершины Процедура AddNode добавляет в граф вершину с заданным номером n и весом x. Предполагается, что уникальность номера обеспечивается вызывающей программой. Procedure AddNode(Var graph: refnode; n,x:integer); Var p:refnode; Begin new(p); With p^ do Begin id:=n; Infnode:=x; Arclist:=nil; Next:graph End; graph:=p; end; Добавление дуги Процедура добавления дуги AddArc в граф использует в качестве входной информации ссылки на соединяемые вершины и значения вес создаваемой дуги. Обе вершины должны существовать к моменту выполнения процедуры. Procedure AddArc(u,v:refnode; y:integer); Var a:refarc; Begin if u=nil or v=nil then writeln(‘Отсутствует вершина’) Else begin New(a); With a^ do begin Infarc:=y; Adj:=v; Next:=u^.arclist End; u^.arclist:=a end end; Удаление дуги вершин Для удаления дуги указываются две ссылки на вершины, которые эта дуга соединяет. Приведенная ниже процедура удаляет элемент из списка дуг, выходящих из вершины u, если в нем записана ссылка на вершину v. Если таких элементов несколько, то удаляется первый встретившийся. Procedure DeleteArc(u,v:refnode); Var a,before:refarc; Run:boolean; Begin If u<>nil then Begin a:=u^.arclist; run:=truel while a<>nil and run do if a^.adj=v then run:=false else begin before:=a; a:=a^.next end; if a<>nil then begin if a=u^.arclist then u^.arclist:=a^.next else before^.next:=a^.next; dispose(a) end end end; Процедура удаления вершины более сложная, так как кроме удаления дескриптора вершины и подцепленного к ней списка выходящих дуг, необходимо просмотреть всю оставшуюся часть графа в поисках висячих ссылок. Эти ссылки удаляются с помощью процедуры DeleteArc. Procedure DeleteNode(Var graph:refnode; v:refnode); Var before,p,q:refnode; a,after:refarc; begin p:=graph; while p<>nil do {цикл по всем вершинам графа} begin q:=p^.next; if p<>v then begin DeleteArc(p,v) {удаление дуг, направленных удаляемой вершине} before:=p; end else Begin {удаление вершины v и всех дуг, исходящих из нее} if p=graph then graph:=q; {если это первая вершина} a:=p^.arclist; {удаление списка дуг вершины v} while a<>nil do begin after:=a^.next; dispose(a); a:=after end; if p=graph then graph:=q else before^.next:=q; dispose(p); end; p:=q; end end; Просмотр графа Просмотр графа заключается в посещении всех вершин и дуг графа и выводе в стандартный файл всей информации о графе. Для непустого графа информация группируется по вершинам (списки смежности). Procedure BrowseGraph(graph:refnode); Var a:refarc; Nn,na: integer; {счетчики количества вершин и дуг} Begin Nn:=0; na:=0; while graph<>nil do begin writeln(‘Вершина ’, graph^.id,’ с весом ’ ,graph^.infnode); writeln(‘Список дуг:’); a:=graph^.arclist; if a=nil then writeln(‘пуст’); while a<>nil do begin writeln(‘Дуга к вершине ’, (a^.adj)^.id,’, вес дуги ’,a^.infarc); na:=na+1; a:=a^.next; end; nn:=nn+1; graph:=graph^.next; end; writeln(‘В графе ’, nn, ‘вершин и ‘, na,’ дуг’) end; Тема 7.3 Алгоритмы на графах: поиск в глубину и поиск в ширину. Обход (поиск) в глубину Метод поиска в глубину (depth first search, DFS) — обобщение метода обхода дерева в прямом порядке. Обход в глубину (называемый иногда стандартным обходом), есть обход графа по следующим правилам: 1. Добавляет начальную вершину в стек и помечает её как использованную. 2. Рассматривает верхнюю вершину стека и добавляет в стек первую попавшуюся смежную ей неиспользованную вершину, помечая её как использованную. Если такой вершины нет, извлекает вершину стека. 3. Если стек не пуст, переходит к пункту 2. Таким образом, этот алгоритм обходит все вершины, достижимые из начальной, и каждую вершину обрабатывает не более одного раза. Текст процедуры обхода в глубину (рекурсивный вариант): var a:array[1..nmax,1..nmax]of integer;// матрица смежности used:array[1..nmax]of boolean; // список меток n:integer; // количество вершин графа procedure dfs(v:integer); var i:integer; begin used[v]:=true; // помещенная в стек вершина помечается использованной for i:=1 to n do // рассматриваются все ребра, исходящие из этой вершины // проверка, использована ли вершина, в которую ведет выбранное ребро, если да, то поиск продолжается из этой вершины. if (a[v,i]=1)and(not used[i]) then dfs(i); end; ... dfs(X); // здесь X - номер начальной вершины При выполнении обхода графа по этим правилам стремимся проникнуть "вглубь" графа так далеко, как это возможно, затем отступаем на шаг назад и снова стремимся пройти вперед и так далее. Обход (поиск) в ширину Обход графа в ширину (breadth first search, BFS) основывается на замене стека очередью: 1. Добавляет начальную вершину в очередь и помечает её как использованную. 2. Извлекает следующую вершину из очереди и добавляет в очередь смежные ей неиспользованные вершины, помечая их как использованные. 3. Если очередь не пуста, переходит к пункту 2. После такой модификации чем раньше посещается вершина (помещается в очередь), тем раньше она используется (удаляется из очереди). Использование вершины происходит с помощью просмотра сразу всех еще не просмотренных вершин, смежных этой вершины. Таким образом, "поиск ведется как бы во всех возможных направлениях одновременно". Очередность просмотра вершин при поиске в ширину: procedure bfs(v:integer); var Og:array[1..nn]of integer; yk1,yk2:integer; i:integer; begin // в элементе og[i] хранится номер группы вершины i. Изначально номер группы всех вершин кроме стартовой равен 0, это значит, что они ещё не были использованы. for i:=1 to n do og[i]:=0; // Инициализация очереди, т.е. добавление в неё начальной вершины с номером v yk2:=0; yk1:=1; Og[yk1]:=v; used[v]:=true; // пометка вершины использованной while yk2 < yk1 do // цикл работает, пока очередь не пуста begin inc(yk2);v:=Og[yk2]; write(v:2); // просматриваются все рёбра, исходящие из первой вершины очереди for i:=1 to n do // использована ли вершина, в которую ведёт выбранное ребро, если нет , то вершина добавляется в очередь if (a[v,i] <> 0) and not used[i] then begin // сдвигается указатель конца очереди inc(yk1); Og[yk1]:=i; used[i]:=true; end; end; end; Чаще всего поиск в ширину используется для нахождения кратчайшего пути от одной вершины X до другой – Y: нужно запустить поиск в ширину из вершины X и при добавлении новой вершины в очередь смотреть, не является ли она вершиной Y. Если программа не завершит работу в условном цикле, это значит, что пути из X в Y не существует.