Структуры и алгоритмы обработки данных (А.Н. Горитов, 2001 г., 33 с.)

КОНТРОЛЬНАЯ РАБОТА № 1

Лабораторная работа 1

Тема – перечислимые и интервальные типы.
Цель лабораторной работы – освоить основные способы работы с перечислимыми и интервальными типами данных на алгоритмиче-ском языке PASCAL.
Перечислимый тип задается перечислением тех значений, кото-рые он может получать. Каждое значение именуется некоторым иден-тификатором и располагается в списке, обрамленном в круглые скобки, например:
TYPE
COLORS = (RED, YELOOW, GREEN, BLUE);
Эти значения считаются упорядоченными. Так, для нашего при-мера
RED < YELOOW < GREEN < BLUE.
Переменная типа COLORS может принимать одно из перечислен-ных значений.
Ко всем переменным одного и того же перечислимого типа при-менимы операции отношения:
=, <>, <=, >=, <, >.
Использование перечисляемых типов повышает надежность про-грамм благодаря возможности контроля тех значений, которые полу-чают соответствующие переменные.
Интервальный тип. При описании переменных в программе, как правило, известно, что они будут использованы для представления подмножества значений некоторого типа. Это подмножество значений в языке программирования PASCAL может быть определено с помо-щью так называемого интервального типа данных.
Интервальный тип данных определяется посредством задания подмножества значений одного из ранее определенных типов. В языке программирования PASCAL диапазон значений переменных интер-вального типа задается с помощью любого простого типа данных за исключением вещественного.
При задании диапазона указывается наименьшее и наибольшее значение, которое может принимать переменная соответствующего типа (обе константы должны быть одного типа). Так, с помощью объ-явления:
Int = 0..1000;
создается новый интервальный тип данных, значения которого являют-ся целыми и лежат в интервале целых чисел [0..1000]. Такое объявле-ние типа указывает компилятору, что для переменных этого типа (ко-торые будут объявлены в программе далее) допустимы в качестве зна-чений только числа из указанного диапазона. Тем самым в программе могут быть автоматически организованы проверки корректности опе-раций присвоения для этих переменных.
При определении интервального типа нужно руководствоваться следующими правилами:
 два символа '..' рассматриваются как один символ, поэтому между ними недопустимы пробелы;
 левая граница диапазона не должна превышать его правую границу.
Интервальный тип необязательно описывать в разделе TYPE, а можно указать непосредственно при объявлении переменной, напри-мер:
VAR
DATE : 1..31;
MONTH: 1..12;
LCHR : 'A'..'Z';
Варианты заданий к лабораторной работе
1. Составить программу, печатающую для целого числа k от 1 до 99 фразу: 'мне k лет'. При этом учитывать, что при некоторых значе-ниях k слово 'лет' надо заменить на слово 'год' или 'года'.
2. Составить программу, печатающую для натурального числа k фразу: 'мы нашли k грибов в лесу', согласовав окончание слова 'гриб' с числом k.
3. Переменная W может принимать значения: степь, боль, тет-радь, дверь. Переменная P принимает значение падежа слова. Вывести на экран слово W в падеже P. Например, при W=степь и P=творит, на-до вывести 'степью'.
4. Корабль сначала шёл по курсу К1, а затем этот курс был изме-нен согласно приказу ПР. Определить К2 - новый курс корабля. Значе-ния курса могут быть: север, восток, юг, запад. Значение приказа: впе-ред, вправо, назад, влево.
5. Переменные y, m, d имеют смысл год, месяц, день. Перемен-ной t присвоить значение true, если тройка y, m, d образует правильную дату, и false – в противном случае.
6. Переменные y, m, d имеют смысл год, месяц, день. По дате d, m, y определить дату следующего дня: d1, m1, y1.
7. Определить k - порядковый номер дня года по дате d, m, y (день, месяц, год).
8. Для чисел от 1 до 99 напечатать их словесную запись. Напри-мер, 12 – двенадцать, 42 - сорок два.
9. По юлианской дате n - день от начала года и y - год. Опреде-лить и вывести дату в виде: день, месяц, год.
10. Учитывая, что 1991 г. начался со вторника, вывести на экран дисплея значения дней недели заданного месяца м.


Лабораторная работа 2

Тема – множества.
Цель лабораторной работы – освоить основные способы работы с типом данных 'множество' на алгоритмическом языке PASCAL.
Множество является одной из фундаментальных статических структур. Множества – произвольный набор однотипных объектов, понимаемый как единое целое. Соответствующий тип описывается:
type T = set of T0,
где T0 - базовый тип элементов множества, который может быть только перечислимым или интервальным типом.
Значениями переменной X типа T являются множества элементов типа T0. Они составляют множества всех подмножеств T0. Такое мно-жество называется множеством-степенью. Т.е. можно сказать, что тип T – это множество-степень своего базового типа T0.
Порядок следования элементов для множества роли не играет.
Максимальное число элементов множества определяется реализа-цией. Для TURBO PASCAL количество элементов множества не долж-но превышать 256.
Пример определения и задания множеств:
type
DIGITCHAR = set of ' 0 ' . . ' 9 ' ;
DIGIT = set of 0 . . 9 ;
var
S1, S2, S3 : DIGITCHAR;
S4, S5, S6 : DIGIT;
begin
. . .
S1 := ['1', '2', '3'];
S2 := ['3', '2', '1'];
S3 := ['2', '3'];
S4 := [0..3, 6];
S5 := [4, 5];
S6 := [3..9];
. . .
end;
Над множествами определены следующие операции:
* пересечение множеств; результат содержит элементы, общие для обоих множеств; например, S4*S6 содержит [3], S4*S5- пустое множество (см. выше);
+ объединение множеств; результат содержит элементы первого множества, дополненные недостающими элементами из второго мно-жества:
S4+S5 содержит [0,1,2,3,4,5,6];
S5+S6 содержит [3,4,5,6,7,8,9];
- разность множеств; результат содержит элементы из первого множества, которые не принадлежат второму:
S6-S5 содержит [3,6,7,8,9];
S4-S5 содержит [0,1,2,3, 6] ;
= проверка эквивалентности; возвращает True, если оба множест-ва эквивалентны;
<> проверка неэквивалентности; возвращает True, если оба мно-жества неэквивалентны;
<= проверка вхождения; возвращает True, если первое множество включено во второе;
>= проверка вхождения; возвращает True, если второе множество включено в первое;
in проверка принадлежности; в этой бинарной операции первый элемент - выражение, а второй - множество одного и того же типа; воз-вращает True, если выражение имеет значение, при¬надлежащее множе-ству:
3 in S6 возвращает True;
2*2 in S1 возвращает False.
Варианты заданий к лабораторной работе
1. Ввести с клавиатуры текст до символа точки и слово из латин-ских букв. Определить, сколько в тексте содержится символов, совпа-дающих с символами в слове.
2. Идентификатор содержит три символа. Первый символ – про-писная латинская буква, второй – строчная латинская буква, а третий – цифра. Проверить правильность введенного идентификатора.
3. Дан текст из строчных латинских букв с точкой в конце. Вы-вести на экран первые вхождения букв в текст, сохраняя их взаимный порядок.
4. Дан текст из прописных латинских букв и цифр с точкой в конце. Вывести на экран монитора все буквы и цифры, входящие в текст не менее двух раз.
5. Ввести с клавиатуры целое число и вывести на экран монитора все цифры, не входящие в десятичную запись этого числа.
6. Дан текст из цифр и строчных латинских букв. Определить, ка-ких букв – гласных (a, e, i, o, u) или согласных – больше в этом тексте.
7. Ввести символьную строку длиной 100 символов и определить сколько в ней символов разделителей (' ', '.', ',', ':', '?', '!').
8. Ввести текст. В алфавитном порядке напечатать все строчные русские гласные буквы, входящие в этот текст.
9. В тексте, ограниченном точкой, определить сколько содержит-ся символов, отличных от латинских букв и знаков препинания.
10. Дан текст, содержащий буквы и знаки препинания. Заменить все символы препинания символом пробела.
Контрольные вопросы
1. Перечислимый тип. Представление в памяти.
2. Операции, выполняемые над перечислимым типом.
3. Интервальный тип.
4. Множество. Представление множества в памяти ЭВМ.
5. Операции, выполняемые над множествами.

КОНТРОЛЬНАЯ РАБОТА № 2

Лабораторная работа 3

Тема – файлы.
Цель лабораторной работы – освоить основные способы работы с последовательными файлами.
Последовательность - это одна из наиболее фундаментальных структур данных. В области обработки данных для описания последо-вательности часто используется термин 'последовательный файл'. В языке PASCAL используется просто термин 'файл' для обозначения последовательности компонентов, причем все компоненты должны быть одного типа. Естественный порядок компонентов определяется самой последовательностью. В любой момент времени доступен толь-ко один компонент файла. Другие компоненты доступны путем после-довательного продвижения по файлу. Число компонентов, называемое длиной файла, не фиксируется при определении файла. Это обстоя-тельство является самым существенным отличием файла от массива. Файл, не содержащий ни одного компонента, называется пустым.
Формально (логически) определить структуру типа 'последова-тельный файл' можно следующим образом.
Последовательность с базовым типом Т0 – либо пустая последова-тельность, либо конкатенация последовательности элементов базового типа Т0 и элемента типа Т0.
Определенный таким образом тип Т логической структуры со-держит бесконечное число значений. Хотя, конечно, каждое конкрет-ное значение состоит из конечного числа компонент, но это число не ограничено. К любой сколь угодно длинной последовательности мож-но приписать еще один элемент, но только в конец.
Над файлами можно выполнять два явных вида действий.
 Просмотр файла. Он выполняется в результате последователь-ного продвижения по файлу, начиная с его начала. При этом в каждый момент времени доступен лишь один компонент файла. В процессе просмотра файла изменять значения компонентов на новые запрещает-ся.
 Создание файла. Оно выполняется в результате добавления новых компонентов в конец первоначально пустого файла. В процессе создания файла новые значения разрешается записывать только в са-мый конец файла.
Все остальные действия над последовательными файлами явля-ются композицией его просмотра и создания. Пусть необходимо обно-вить заключительную часть файла, стоящую за некоторым определен-ным компонентом. Задача обновления разбивается на две: найти за-данный компонент (просмотр файла), а вслед за ним записать новые компоненты (создание файла). Естественно, что при этом создается совершенно другой файл, поскольку писать новые компоненты можно только в конце файла.
Рассмотрим основные процедуры и функции, используемые в TURBO PASCALе для работы с функциями.
Процедура Assign. С помощью процедуры Assign связывается файловая переменная с конкретным именем файла.
Процедура Reset. Процедура Reset открывает существующий файл данных, имя которого перед этим было связано при помощи про-цедуры Assign с некоторой файловой переменной, указанной в проце-дуре Reset как параметр.
Процедура Rewrite. Процедура Rewrite создает новый файл и от-крывает его для записи. Если файл с таким именем уже существует, его содержимое стирается, а сам файл открывается заново.
Процедура Close. Процедура Close закрывает открытый ранее файл, связанный с указанной в качестве параметра файловой перемен-ной.
Процедура Rename. Процедура Rename позволяет переименовать существующий файл, связанный с указанной в качестве параметра файловой переменной.
Процедура Erase. Процедура Erase стирает существующий файл с диска.
Функция EOF. Используя логическую функцию EOF, в процессе считывания информации можно проверить, достигнут ли конец файла, т.е. находится ли указатель файла за последним элементом или нет.
Варианты заданий к лабораторной работе
1. Создать файл, содержащий записи о дате: день (1..31), месяц (1..12), год (00..99). Обработать этот файл и указать максимальную дату для второй половины года.
2. Создать файл, содержащий записи о дате: день (1..31), месяц (1..12), год (00..99). Переписать этот файл в два текстовых файла, дату представить в форме дд.мм.гг. В одну строку включить одну дату. В один текстовый файл включить даты для летних месяцев, в другой – для зимних.
3. Дан текстовый файл, разбитый на строки длиной не более 60 символов. Переписать текст в новый файл со строками длиной 60 сим-волов, добавив до конца каждой строки символ '!'.
4. Два упорядоченных файла целых чисел разной длины слить в один файл, чтобы в выходном файле числа были упорядочены. Одина-ковые числа включать в выходной файл один раз.
5. В файле содержится последовательность слов, разделенных пробелом. Текст заканчивается точкой. Вывести в новый файл все сло-ва, отличные от последнего слова.
6. Дан файл, компонентами которого являются действительные числа. Найти максимальное и минимальное значение среди компонент файла.
7. Пусть файлы c и d с компонентами, являющимися действи-тельными или целыми числами, упорядочены по невозрастанию ком-понент. Требуется собрать компоненты файлов c и d в упорядоченном виде в файле f. Количество сравнений не должно превосходить p+q, где p и q - число компонент в файлах c и d.
8. Пусть файлы А и В, компоненты которых являются целыми числами, упорядочены по неубыванию. Получить в файле С все числа файлов А и В без повторений. Файл С должен быть упорядочен по воз-растанию.
9. Дан файл f, компоненты которого являются целыми числами. Получить в файле g все нечетные числа, входящие в файл f. Числа в файле g должны следовать в порядке невозрастания.
10. Дан файл f, компоненты которого являются целыми числами. Получить в файле g все четные числа, входящие в файл f. Числа в фай-ле g должны следовать в порядке убывания, без повторений.
Контрольные вопросы
1. Понятие последовательного файла. Основные операции, выпол-няемые над файлами.
2. Основной метод сортировки последовательных файлов.
3. Двухфазное слияние.
4. Сбалансированное слияние.
5. Естественное слияние.

Лабораторная работа 4

Тема –Стеки, очереди
Цель лабораторной работы – освоить основные способы работы со стеками и очередями.
Стек (stack) - линейный последовательный список, в котором дос-туп, включение и исключение элементов выполняется только с одного конца: т.е. доступен только последний элемент. Дисциплина обслужи-вания элементов стека выражается аббревиатурой
LIFO (Last – In – First – Out) –
'последний пришел – первым вышел'.
Примером стека может служить винтовочный патронный магазин (отсюда второе название стека – магазин), а также железнодорожный разъезд для сортировки вагонов (сортировочный тупик).
В силу указанной дисциплины обслуживания в стеке доступна единственная его позиция, называемая вершиной стека, – это позиция, в которой находится последний по времени поступления в стек эле-мент.
Очередь – линейный последовательный список, в котором все включения производятся в конце списка (в хвосте очереди), а исклю-чения – в начале (в голове очереди).
Дисциплина обслуживания в очереди выражается принципом
FIFO (First – In – First – Out) –
'первым пришел – первым вышел'.
По железнодорожной аналогии – линейный участок пути с одним направлением.
Основные операции над очередью – включение и исключение элемента.
Другие возможные операции – проверка текущей длины и очист-ка.
Варианты заданий к лабораторной работе
1. Используя очередь, решить следующую задачу. Содержимое текстового файла , разделенное на строки, переписать в текстовый файл g, перенося при этом в конец каждой строки все входящие в нее цифры (с сохранением исходного порядка как среди цифр, так и среди остальных литер строки).
2. Используя очередь, решить следующую задачу.
TYPE FR = FILE OF REAL;
За один просмотр файла f типа FR и без использования дополнитель-ных файлов напечатать элементы файла f в следующем порядке: снача-ла – все числа, меньшие a, затем – все числа из отрезка [a, b], и наконец – все остальные числа, сохраняя исходный взаимный порядок в каждой из этих групп чисел (a ,b – заданы, a 3. Описать функцию value (postfix), которая вычисляет как целое число значение выражения (без переменных), записанного в постфикс-ной форме в текстовом файле postfix.
Использовать следующий алгоритм вычисления. Выражение про-сматривается слева направо. Если встречается операнд (число), то его значение (как целое) заносится в стек, а если встречается знак опера-ции, то из стека извлекаются два последних элемента, над ними вы-полняется операция и её результат записывается в стек. В конце концов в стеке остается только одно число – значение выражения.
4. Разработать программу формирования стека, куда помещаются целые положительные числа, вводимые с клавиатуры. Процесс ввода должен прекращаться, как только среди вводимых чисел появляется отрицательное число. После этого программа должна вывести на экран монитора содержимое стека, при этом порядок выводимых чисел дол-жен быть обратным по сравнению с последовательностью их ввода.
5. Организовать очередь из n целых чисел. Изменить ссылки так, чтобы последний элемент очереди стал первым, первый – вторым, вто-рой – третьим и т.д.
6. Разработать программу формирования очереди, содержащей целые числа, и упорядочивания по возрастанию элементов в этой оче-реди. В процессе упорядочивания элементы очереди перемещаться не должны.
7. Последовательность символов, ограниченную точкой, занести в два стека, содержащих гласные и согласные буквы. Вывести текст и элементы из обоих стеков.
8. Последовательность символов, ограниченную точкой, занести в две очереди, содержащие гласные и согласные буквы русского алфа-вита. Вывести элементы очереди гласных и согласных букв.
9. Разработать программу, в которой для очереди, представлен-ной в виде массива, склеенного в кольцо (так, что если очередь дости-гает правого края массива, то новые элементы записываются в начало массива), описаны процедуры или функции:
создание пустой очереди Q (очистка очереди);
проверка, является ли очередь Q пустой;
добавление в конец очереди Q элемента х (inoch(Q,x));
удаление из очереди Q первого элемента с присвоением его значе-ния параметру х (outoch(Q,x)).
Если операция по каким-либо причинам не может быть выполнена, следует вызывать некоторую процедуру Error(k), где k - номер ошибки: 1- переполнение очереди, 2- исчерпание очереди.
10. Разработать программу, в которой для стека, представленного в виде массива из n компонент, написаны процедуры или функции:
создание пустого стека S (очистка стека);
проверка, является ли стек S пустым;
добавление в стек S элемента х (instack(Q,x));
удаление из стека S элемента с присвоением его значения параметру х (outstack(Q,x)).
Если операция по каким-либо причинам не может быть выполнена, следует вызывать некоторую процедуру Error(k), где k - номер ошибки: 1- переполнение стека, 2- исчерпание стека.
Контрольные вопросы
1. Понятие стека. Операции, выполняемые над стеком.
2. Понятие очереди. Операции, выполняемые над очередью.
3. Понятие дека. Операции, выполняемые над деком.
4. Представление стека с помощью массива. Выполнение основных операций.
5. Представление очереди с помощью массива. Выполнение основ-ных операций.

КОНТРОЛЬНАЯ РАБОТА № 3

Лабораторная работа 5

Тема – списки.
Цель лабораторной работы – освоить основные способы работы со стеками и очередями;
Связный список – структура, элементами которой служат записи с одним и тем же форматом, связанные друг с другом логически с по-мощью указателей, хранящихся в самих элементах.
Простейшие связные списки:
• односвязный (один указатель);
• двусвязный (два).
В односвязном списке каждый элемент состоит из двух полей: со-держательного и поля указателя.
Содержательное поле хранит данные (в общем случае это запись).
Поле указателя хранит адрес следующего элемента списка. По указателю получаем доступ к следующему элементу, от него – к оче-редному и т.д. Поле указателя последнего элемента должно содержать специальный признак нулевого или пустого указателя, свидетельст-вующего о конце списка (0 в нашем примере).
Кроме того, должен быть указатель начала списка. Он является частью его логической структуры.
Кольцевой связный список. В односвязном списке для доступа к желаемому элементу необходимо просматривать список с самого нача-ла. Это неудобно и занимает много времени. Если замкнуть элементы списка в кольцо, т.е. в последний элемент списка поместить указатель на первый элемент, то просмотр списка можно начинать с любого эле-мента и просмотреть весь список. Такой список называется кольцевым.
Линейный двусвязный список. Нередко при просмотре линейного списка возникает необходимость продвижения в любом направлении по цепочке элементов: как к концу списка, так и к его началу. Такую возможность обеспечивает линейный двусвязный список. Каждый эле-мент такого списка содержит два указателя:
1) прямой – на следующий элемент списка;
2) обратный – на предыдущий элемент списка.
Кроме указателя на начало списка в структуру двусвязного списка должен быть включен указатель на конец списка (т.е. на последний элемент).
Варианты заданий к лабораторной работе
1. В списке целых чисел удалить из каждой группы подряд иду-щих одинаковых элементов все, кроме одного.
2. Два списка упорядоченных по возрастанию целых чисел объе-динить в один так, чтобы результирующий список был упорядочен.
3. Составить программу, которая из кольцевого списка из n эле-ментов удаляет в порядке просмотра кольца каждый k-й элемент до тех пор, пока в списке не останется один элемент. Распечатать номера уда-ленных элементов.
4. Составить программу, которая в кольцевой список из n эле-ментов добавляет m новых элементов так, чтобы новый элемент встав-лялся через k элементов кольца.
5. Массив целых чисел представлен в виде динамического спи-ска. Изменить последовательность указателей так, чтобы отрицатель-ные числа находились в начале списка.
6. Последовательность символов, ограниченную точкой, занести в два списка, содержащих гласные и согласные. Вывести на экран оба списка.
7. Из динамического списка, содержащего последовательность символов, удалить все одинаковые символы, кроме одного.
8. Текст, заканчивающийся точкой, занести в динамический кольцевой список. Вывести на экран монитора текст из кольцевого списка n раз. n ввести с клавиатуры.
9. Создать список, содержащий целые числа. Перенести послед-ний элемент списка в его начало.
10. В связном списке, содержащем целые числа, удалить все ну-левые элементы списка.

Контрольные вопросы
1. Отличие динамических структур от статических и полустатических.
2. Основные операции, выполняемые над списками.
3. Что такое кольцевой список?

Лабораторная работа 6

Тема – деревья.
Цель лабораторной работы – освоить основные способы пред-ставления деревьев в оперативной памяти ЭВМ и практически реали-зовать алгоритмы работы с деревьями.
Деревом называется структура, которая характеризуется следую-щими свойствами:
a) существует единственный элемент, на который не ссылается никакой другой элемент. Этот элемент называется корнем;
b) каждый элемент связан с несколькими элементами следующе-го уровня иерархии. Эти элементы могут быть в свою очередь деревь-ями (поддеревьями);
c) каждый элемент промежуточного уровня порожден только од-ним элементом более высокого уровня.
Элементы дерева, которые не ссылаются на другие элементы, яв-ляются терминальными (т.е. конечными) или листьями. А элементы, не являющиеся терминальными, называются внутренними узлами.
Таким образом, дерево отражает иерархически упорядоченную структуру данных, в которой прослеживаются связи между элементами предыдущего (верхнего) уровня или предками и элементами следую-щего уровня – потомками.
Узлы располагаются по уровням. Корень – нулевой уровень и т.д. Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой.
Число непосредственных потомков внутреннего узла называется его степенью. Максимальная степень всех узлов есть степень дерева.
Большую роль в прикладных задачах играют упорядоченные де-ревья второй степени. Они называются бинарными деревьями или дво-ичными. Бинарное дерево – это конечное множество элементов (уз-лов), каждый из которых либо пуст (не связан с нижним уровнем, не имеет потомков, т.е. лист), либо является корнем (или узлом) с двумя различными бинарными поддеревьями – левым и правым.
Деревья, имеющие степень больше двух, называются сильно вет-вящимися деревьями.
Во многих задачах, связанных с деревьями, требуется осуществ-лять систематический перебор всех их узлов в определенном порядке. Такой просмотр называется обход дерева. Существует три способа об-хода деревьев, которые называются соответственно обходом сверху, обходом слева направо и обходом снизу.
Над деревьями выполняются такие операции: пройти все узлы в определенном порядке, найти узел с заданным свойством, определить отца данного узла, определить сыновей данного узла, удалить опреде-ленный узел (поддерево), добавить новый узел и т.д.
Для представления деревьев в памяти ЭВМ используются после-довательный и связанный методы хранения.
Последовательное хранение произвольного дерева получается на основе какого-нибудь из его линейных представлений, т.е. задания де-рева в 'строку'.
Связанная стандартная форма хранения деревьев состоит в том, что задается связь от отца к сыновьям, поэтому в каждом узле дерева степени N необходимо иметь N указателей на его сыновей. Отсутствие какого-либо сына обозначается указателем со значением Nil.
Допускается обратная форма связного хранения графа, которая состоит в задании связей от сыновей к отцу; здесь для каждого узла достаточно иметь один указатель на отца. Как правило, эта форма хра-нения используется для неупорядоченных деревьев.
Варианты заданий к лабораторной работе
1. Используя очередь или стек, напишите программу, опреде-ляющую число вхождений элемента Е в дерево Т.
2. Вычислить среднее арифметическое всех элементов непустого двоичного дерева Т.
3. Подсчитать число вершин на n-ом уровне непустого дерева T (корень считать вершиной нулевого уровня).
4. Напишите программу, определяющую число вхождений эле-мента Е в дерево Т.
5. Напишите программу, находящую величину наибольшего эле-мента дерева Т.
6. Напишите программу, определяющую максимальную глубину непустого дерева Т, т.е. число ветвей в самом длинном из путей от корня дерева до листьев.
7. Разработать программу, которая определяет, равны ли два би-нарных дерева.
8. Напишите программу, определяющую самое большое число на n-ом уровне непустого дерева Т (корень считать вершиной нулевого уровня).
9. Разработать программу, формирующую динамическую струк-туру данных для хранения генеалогического дерева. Каждая вершина дерева должна содержать следующую информацию: имя и год рожде-ния.
10. В непустом дереве T найти длину пути (число ветвей) от кор-ня до ближайшей вершины с элементом Е. Если элемент Е не входит в Т, то за ответ принять '-1'.
Контрольные вопросы
1. Степень дерева.
2. Бинарное дерево.
3. Основные операции, выполняемые над бинарными деревьями.
4. Обход двоичного дерева.
5. Сильно ветвящиеся деревья.
КОНТРОЛЬНАЯ РАБОТА № 4

Лабораторная работа 7

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

где V - множество вершин, а E - множество ребер, причем
– для ориентированного графа и
– для неориентированного графа.
Будем использовать также обозначения | V | = n, | E | = m (мощ-ность множества).
В теории графов классическим способом представления графа яв-ляется матрица инциденций. Это матрица А с n строками, соответст-вующими вершинам, и m столбцами, соответствующими ребрам. Для ориентированного графа столбец, соответствующий дуге (x, y)E, со-держит '+1' в строке, соответствующей вершине x, '-1' в строке, соот-ветствующей вершине y, и нули во всех остальных строках. Петлю, т.е. дугу вида (x, x), удобно представлять другим значением, например, 2, в строке x. Для неориентированного графа столбец, соответствующий ребру {x, y}, содержит 1 в строках, соответствующих x и y, и 0 - во всех остальных строках.
Второй способ представления графа – с помощью матрицы смеж-ности размера n x n, где = 1, если существует ребро из x и y, и = 0 в противном случае. При этом подразумевается, что ребро {x, y} неориентированного графа идет как от x к y, так и от y к x. По-этому матрица смежности для неориентированного графа всегда сим-метрична.
Более экономным в отношении памяти (особенно для неплотных графов, когда m гораздо меньше ) является способ представления графа с помощью списка пар, соответствующих его ребрам. Пара (x, y) соответствует дуге (x, y), если граф ориентированный, и ребру {x, y}, если граф неориентированный.
Лучшим решением во многих случаях является структура данных, которую назовем списками инцидентности. Она содержит для каждой вершины список вершин u, между которыми существуют дуги (v, u) для ориентированного графа, и ребра {v, u} – для неориентиро-ванного графа.
Типичные задачи, связанные с графами, – это сравнение графов (скажем, чертежей при распознавании изображений), нахождение кратчайшего пути по карте дорог, составление совместной системы уравнений по электронной цепи, нахождение критического ребра в графе, удаление которого приведет к расщеплению графа на две от-дельные, не связанные между собой области.
Варианты заданий к лабораторной работе
1. Проверьте, содержит ли граф, заданный с помощью списков инцидентности, вершину, в которую входят дуги от всех остальных вершин графа, но из которой не исходит ни одна дуга.
2. Напишите и используйте в программе процедуру поиска в глу-бину в графе, заданном списками инцидентности. Выведите на экран номера вершин в том порядке, в котором они просматриваются проце-дурой.
3. Напишите и используйте в программе процедуру поиска в ши-рину в графе, заданном списками инцидентности. Выведите на экран номера всех вершин в порядке очередности просмотра.
4. Напишите и используйте в программе процедуру, реализую-щую метод, отличающийся от поиска в ширину только тем, что вновь достигнутая вершина помещается не в очередь, а в стек.
5. С помощью метода поиска в глубину найдите стягивающее де-рево для произвольного связного неориентированного графа, заданно-го списками инцидентности.
6. Используя метод поиска в ширину, найдите стягивающее дере-во для произвольного связного неориентированного графа, заданного списками инцидентности.
7. Используя метод поиска в ширину, найдите кратчайший путь от начальной до любой произвольной вершины связного неориентиро-ванного графа, заданного списками инцидентности (веса всех ребер примите равными единице).
8. Используя алгоритм поиска в глубину, найдите множество фундаментальных циклов связного неориентированного графа, задан-ного списками инцидентности.
9. Найдите эйлеров цикл в графе, не содержащем вершин нечет-ной степени и заданном списками инцидентности.
10. Найдите эйлеров путь в графе, содержащем две вершины не-четной степени и заданном списками инцидентности.