кащенко Практикум по МПр(27.09.11) 1

МИНИСТЕРСТВО ОБРАЗОВАНИЯ
РОССИЙСКОЙ ФЕДЕРАЦИИ

Воронежский государственный технический университет

Кафедра "Системы информационной безопасности"

Г.А. Кащенко



МЕТОДИЧЕСКИЕ УКАЗАНИЯ
по проведению практических занятий
по дисциплинам "Методы программирования" и "Средства и методы программирования"












Воронеж 2011
УДК 681.3.06
Кащенко Г.А. Методические указания по проведению практических занятий по дисциплинам "Методы программирования" и "Средства и методы программирования": Учеб. пособие. Воронеж: Воронеж, гос.
техн. ун-т, 2011. с.

Издание соответствует требованиям Государственного образовательного стандарта высшего профессионального образования по направлению "Информационная безопасность" для студентов специальностей 090102 "Компьютерная безопасность", 090106 "Информационная безопасность телекоммуникационных систем" очной формы обучения

В учебном пособии изложены методические указания по проведению практических занятий по дисциплинам "Методы программирования" и "Средства и методы программирования". Содержащаяся в пособии информация является базовой для углубленного изучения теоретического материала соответствующих дисциплин.

Табл. 1. Ил.23 . Библиогр.: 17 назв.

Научный редактор д-р техн. наук, проф. А.Г. Остапенко

Рецензенты:


© Кащенко Г.А., 2011
© ГОУВПО "Воронежский государственный технический университет", 2011



ВВЕДЕНИЕ
Одним из основных этапов профессиональной подготовки специалистов по направлению «Информационная безопасность» является изучение дисциплин «Методы программирования» (МП) и «Средства и методы программирования» (СрМП), закладывающих основание в их специальную подготовку.
Изучение дисциплин осуществляется путем чтения лекций, проведения лабораторных и практических занятий, выполнения курсовой работы и самостоятельной подготовки обучаемых.
Учебное пособие по практическим занятиям ориентировано на программы по дисциплинам МП и СрМП, рассчитано на часа и охватывает проектирование все основные темы, изучаемые в соответствующих дисциплинах.

1. Практическое занятие № 1.
Конструирование структур данных

Целью данного практического занятия является приобретение навыков в определении и использовании структур. Для более уверенного овладения материалом рекомендуется решить 2, 3 задачи.

1.1. Примеры решения задач

Задача 1.1.1. Определить структуру, описывающую понятие комплексное число. Написать и протестировать функции для ввода, вывода комплексного числа, а также для сложения двух комплексных чисел, заданных в алгебраической форме.

#include
typedef struct
{
int real;
int imag;
} Complex;
void main()
{
Complex c1, c2, c3, read();
void add(Complex, Complex, Complex*); print(Complex);
c1=read(); c2=read();
add(c1, c2, &c3);
printf("При сложении");print(c1);printf(“и”); print (c2);
printf("\n получилось "); print(с3);
}
Complex read ()
{
Complex c;
puts("Введите действительную и мнимую части числа:");
scanf("%d %d", &(с.real), &(с.imag));
return с;
}
void print (Complex с)
{ printf(“%d+i*(%d)”, c.real, c.iaiag); }
void add (Complex c1, Complex c2, Complex* c3)
{
c3->real=c1.real+c2.real;
c3->imag=c1.imag+c2.imag;
}

Задача 1.1.2. Определить структуру, описывающую понятие рациональное число. Написать и протестировать функции для сокращения, печати рационального числа, а также для деления двух рациональных чисел.

#include
#include typedef struct
{
int chis;
int znam;
} Racion;
void put(Racion A)
{
if (A.chis*A.znam<0) printf(“-”);
A.chis=abs(A.chis);
A.znam=abs(A.znam);
printf ("%d / %d", A.chis, A.znam);
}
Racion SOKR (Racion A)
{
int i, min;
if(abs(A.chis) > abs(A.znam)) min=аbs(A.znam);
else min=abs(A.chis);
for(i=min; i>1; i--)
if(A.chis%i == 0 && A.znam%i == 0) break;
A.chis/=i;
A.znam/=i;
return A;
}
void DIV (Racion A, Racion B, Racion *C)
{
A=SOKR(A);
B=SOKR(B);
C->chisa=A.chis*B.znam;
С->znam=А.znan*B.chis;
*C=SOKR(*C) ;
}
void main()
{
Racion А, В, С;
puts("Введите числит. и знамен. 1-й, а затем - 2-й дроби : ");
scanf("%d%d%d%dn, &A.chis, &A.znam, %B.chis, %B.znam);
DIV (A, B, &C);
printf("При делении "); put(A); printf(" на "); put(В);
printf("\n получилось "); put(С);
}
Задача 1.1.3. По введенному году, месяцу и числу, определить порядковый номер дня в году.
typedef struct
{
int year;
int month;
int day;
} DATE;
int tab_days[2][13]={ {0,31,28,31,30,31,30,31,31,30,31,30,31},
{0,31,29,31,30,31,30,31,31,30,31,30,31}
};
int day_of_year (DATE d)
{
int i, k;
k=d.year%4=0&&d.year%100!=0||d.year%400=0;
//високосный год
if(d.month12) return -1;
if(d.daytab days[k][d.month]) return -1;
for(i=1; i d.day+=tab_days[k][i];
return d.day;
}
#include
void main()
{
DATE d;int N;
puts("Введите число, номер месяца и год.");
scanf("%d%d%d", &d.day, &d.month, &d.year);
N=day_of_year (d) ;
if(N<0) puts("Неверно введена дата!");
else printf("B %d году этот день имеет номер %d\n", d.year, N);
}

1.2. Задания для самоконтроля

Задача 1.2.1. Ввести перечислимые типы масть, достоинство. С их помощью описать как структуру переменную карта. Составить и протестировать функцию БЬЁТ (K1, K2, КМ), которая проверяет, бьёт ли карта К1 карту К2, с учетом того, что масть КМ является козырной.
Задача 1.2.2. Описать как структуру переменную время (полями часы, минуты, секунды). Составить и протестировав функции:
а) СЛЕД_СЕК (t, t1, d), которая присваивает параметру tl время на d секунд большее, чем время t (может происходить смена суток);
б) ИНТЕРВАЛ (t1, t2, d), которая вычисляет время d, прошедшее от времени t1 до времени t2.
Задача 1.2.3. Ввести перечислимые типы вертикаль, горизонталь для обозначения клеток шахматной доски. Составить и протестировать функции:
а) ХОД ФЕРЗЯ (K1, K2), которая проверяет, может ли ферзь за один ход перейти с поля К1 на поле К2;
б) ХОД КОНЯ (K1, K2), которая вычисляет, за сколько ходов конь может перейти с поля К1 на поле К2.
Задача 1.2.4. Ввести структуру (с полями числитель и знаменатель) для описания понятия рациональное число. Составить и протестировать функции:
а) РАВНО (А, В), которая проверяет, равны ли друг другу рациональные числа А, В;
б) МАКС (Х, N), которая возвращает наибольшее из массива X(N] рациональных чисел;
в) СЛОЖ (А, В, С), которая записывает в С результат сложения рациональных чисел А и В;
г) МИН (А, В), которая возвращает наименьшее из двух рациональных чисел А и В;
д)УМН (А, В, С), которая записывает в С результат перемножения рациональных чисел А и В.
Задача 1.2.5. Ввести структуру (с полями число, месяц, год) для описания понятия дата. Составить и протестировать функцию, которая:
а) вычисляет интервал (в днях), прошедший между двумя датами;
б) по порядковому номеру дня в году определяет число и месяц года, соответствующее этому дню;
в) по введенной дате распечатывает дату на N дней вперед.
Задача 1.2.6. Определить структуры, описывающие шар, точку в трехмерном пространстве. Составить и протестировать функцию, которая проверяет, находится ли точка внутри данного шара.
Задача 1.2.7. Ввести структуру для описания комплекса числа. Составить и протестировать функции для:
а) преобразования комплексного числа из алгебраической формы в показательную;
б) преобразования комплексного числа из показатель ной формы в алгебраическую;
в) получения сопряженного комплексного числа;
г) возведения комплексного числа в целую положительную степень;
д) умножения комплексных чисел в алгебраической
форме;
с) умножения комплексных чисел в показательной форме;
ж) деления комплексных чисел в показательной форм;
з) деления комплексных чисел в алгебраической форм;
Задача 1.2.8. Ввести структуру для описания понятия алгебраический полином. Составить и протестировать функции для:
а) ввода полинома;
б) вывода полинома;
в) нормализации полинома;
г) сложения полиномов;
д) вычитания полиномов;
с) умножения полиномов;
ж) деления полиномов;
з) дифференцирования полинома;
и) интегрирования полинома.
Задача 1.2.9. Ввести структуру для регистрации автомашин. Она должна иметь следующие поля: дату регистрации (структура с полями - день, месяц год);
марку машины;
год выпуска;
цвет;
номер;
Написать и протестировать функции;
регистрация новой машины;
удаление машины из регистрационного списка;
поиск машины по любой из комбинаций признаков.
Задача 1.2.10. Массив структур содержит информацию о студентах группы: в первом поле стоит фамилия, во втором -возраст, в третьем - рост, в четвертом - средний балл в сессию и т.д. (i-и элемент массива описывает 1-го студента).
Студент называется среднестатистическим по k-му параметру, если на нем достигается минимум модуля разности среднего арифметического чисел Л-го столбца и значения k-гo параметра этого студента. Аналогично определяется уникальный по k-му параметру студент (на нем достигается максимум).
Студент называется самым средним, если он является среднестатистическим по самому большому количеству параметров. Аналогично определяется самый уникальный студент.
Выяснить, кто в группе является:
а) самым средним,
6) самым уникальным,
в) самым средним среди самых уникальных,
г) самым уникальным среди самых средних.
Задача 1.2.11. В доме N этажей и три лифта. Каждый лифт может быть свободным или занятым. Человек стоит на одном из этажей и собирается вызвать либо ближайший свободный лифт, либо ближайший занятый, направляющийся в сторону этажа, где находится человек.
Распечатать начальную конфигурацию (расстановку, занятость и направление движения лифтов, местоположение человека), а также номер лифта, который будет вызван.
Использовать функции ВВОД, ВЫВОД, ВЫБОР_ЛИФТА.
Задача 1.2.12. Пусть ЭВМ не умеет работать с вещественными числами, а имеет только операции и функции для работы с символами, строками и целыми числами.
Реализовать функции для:
а) ввода;
б) вывода;
в) сложения;
г) вычитания;
д) умножения.
вещественных чисел. (Числа вводятся как строки, разделяются на целую и дробную части, и над ними, как над целыми числами, с учетом меж разрядных переносов, выполняются операции.)
Задача 1.2.13. Определить структуру, описывающую равнобедренный прямоугольный треугольник с катетами, параллельными осям координат, и нижним левым прямым углом.
Написать и протестировать функцию, возвращающую указатель на новый треугольник - область пересечения двух данных. Если пересечения нет - возвращается NULL.
Задача 1.2.14. Определить структуры, описывающие точку в полярной и декартовой системах координат. Составить протестировать функции для:
а) получения декартовых координат точки, если заданы ее полярные координаты;
б) вычисления расстояния между двумя точками, заданными в декартовой системе координат;
в) получения полярных координат точки, если заданы ее декартовы координаты;
г) вычисления расстояния между двумя точками, заданными в полярной системе координат.
Задача 1.2.15. Определить структуру - важнейшие исторически с даты. Её поля - год, событие.
Написать и протестировать функции:
сортирующую структуры по любому из полей;
подсчитывающую средний интервал между датами;
определяющую наиболее часто встречающуюся первую) букву в названии события.
Задача 1.2.16. Определить структуру, описывающую прямоугольник со сторонами, параллельными осям координат (прямоугольник задастся двумя точками - левой нижней и правой верхней).
Написать и протестировать функцию, возвращающую указатель на новый прямоугольник область пересечения двух
прямоугольников. Если пересечения нет - возвращается-NUUL.

2. Практическое занятие № 2.
Сортировка и поиск данных

2.1. Алгоритмы сортировки

Концепция упорядоченного множества элементов является одной из тех концепций, которые имеют существенное влияние на многие стороны нашей жизни.
В общем сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определённом порядке. Цель сортировки - облегчить поиск элементов в таком упорядоченном множестве.
Уточним задачу сортировки.
Пусть надо упорядочить n элементов
R1, R2, , Rn,
которые назовём записями. Каждая запись Rj имеет свой ключ kj, который и управляет процессом сортировки. Помимо ключа, запись может содержать дополнительную "сопутствующую информацию", которая не влияет на сортировку, но всегда остаётся в этой записи.
Задача сортировки - найти такую перестановку записей p(1)p(2)... p(n), после которой ключи расположились бы в неубывающем порядке
KР(1) ( КР(2) ((( КР(n)
При сортировке либо перемещаются сами записи, либо создаётся вспомогательная таблица, которая описывает перестановку и обеспечивает доступ к записям в соответствии с порядком их ключей.
Обычно сортировку подразделяют на два класса: внутреннюю, когда все записи хранятся в оперативной памяти, и внешнюю, когда они там все не помещаются. Мы будем рассматривать только внутреннюю сортировку.
Основное требование к методам сортировки – экономное использование времени процессора и памяти. Хорошие алгоритмы затрачивают на сортировку n записей время порядка n log n.
Существующие методы сортировки обычно разбивают на три класса, в зависимости от лежащего в их основе приема:
а) сортировка выбором;
б) сортировка обменами;
в) сортировка включениями (вставками).
Рассмотрим основные алгоритмы сортировки на приме ре сортировки целочисленного массива.
Линейный выбор. Метод предполагает, использование рабочего массива, в который помещается, отсортированный массив. Количество просмотров определяется количество элементов массива. Сортировка посредством линейного выбора сводится к следующему:
1. Найти наименьший элемент, переслать его в рабочий массив и заменить его в исходном массиве величиной, которая больше любого реального элемента.
2. Повторить шаг 1. На этот раз будет выбран нам меньший из оставшихся элементов.
3. Повторять шаг 1 до тех пор, пока не будут выбраны все n элементов.
Функция, реализующая алгоритм линейного выбора имеет следующий вид:
#iinclude
void lin_wib(int *a, int n)
{
int i, j, imin, amin, *p; p=(int*)malloc(n*sizeof(int)); // выделяем память под
//рабочий массив
for (j=0; j{
for (amin=INT_MAX, i=0; i // ищем минимальный элемент
if(a[i]p[j]=amin; a[imin]=INT_AX;
}
for (j=0; j на место
a[j]=p[j]; // исходного
free(p);
}
Линейный выбор с обменом. В этом методе рабочий массив не используется. Общая схема алгоритма следующая. Просмотрим элементы а1, а2,..., аn, найдем среди них минимальный элемент и переставим его на первое место. Теперь просмотрим элементы а2,...,аn, найдем среди них минимальный элемент и поставим его на второе место. И так до тех пор, пока не останется один элемент.
Стандартный обмен (метод "пузырька"). Просматриваем элементы а1,..., аn и попутно меняем местами те соседние элементы, для которых выполнено неравенство аi> ai+1. В результате первого просмотра максимальный элемент станет последним ("он вниз - пузыри вверх"). На следующем просмотре аналогичную процедуру проведем над элементами а1,..., aп-1 и т.д. Сортировку необходимо закончить, если будет выполнено одно из двух условий:
после очередного прохода не сделано ни одного обмена;
сделан проход для элементов а1, а2.
Челночная сортировка. Челночная сортировка, называемая также "сортировкой просеиванием" или "линейной вставкой с обменом" является наиболее эффективной из всех рассмотренных выше методов и отличается от сортировки обменом тем, что не сохраняет фиксированной последовательности сравнений.
Алгоритм челночной сортировки действует точно так же, как стандартный обмен до тех пор, пока не возникает необходимость перестановки элементов исходного массива. Сравниваемый меньший элемент поднимается, насколько это возможно, вверх. Этот элемент сравнивается в обратном порядке со своими предшественниками по направлению к первой позиции. Если он меньше предшественника, то выполняется обмен и начинается очередное сравнение. Когда элемент, передвигаемый вверх, встречает меньший элемент, этот процесс прекращается и нисходящее сравнение возобновляется с той позиции, с которой выполнялся первый обмен.
Сортировка заканчивается, когда нисходящее сравнение выходит на границу массива.
Процесс челночной сортировки можно проследить на следующем примере:
Исходный массив: 2 7 9 5 4
Нисходящие сравнения: 2 7; 7 9; 9 5;
После перестановки: 2 7 5 9 4
Восходящие сравнения и обмен: 7 5 -> 5 7; 2 5- конец восходящего сравнения; получен массив 2 5 7 9 4
Нисходящие сравнения: 9 4
После перестановки: 2 5 7 4 9
Восходящие сравнения и обмен: 7 4 -> 4 7: 5 4 - > 4 5:
2 4 - конец восходящего сравнения; получен массив 2 4 5 7 9.
Сортировка Шелла. Все рассмотренные выше метод обмена были не столь эффективны при реализации на ЭВМ, из-за сравнений и возможных обменов только соседних элементов. Лучших результатов следует ожидать от метода, котором пересылки выполняются на большие расстояния. Один из таких методов предложил D.L.Shеll.
Сортировка Шелла, называемая также "слиянием обменом", является расширением челночной сортировки.
Идея метода заключается в том, что выбирается интервал h между сравниваемыми элементами, который уменьшается после каждого прохода. Для последовательных интервалов выполняются условия:
Hp=1, hi+1Таким образом, вначале сравниваются (и, если нужно переставляются) далеко стоящие элементы, а на последнем проходе - соседние элементы.
Выигрыш получается за счет того, что на каждом этапе сортировки либо участвует сравнительно мало элементов, либо эти элементы уже довольно хорошо упорядочены, и требуется небольшое количество перестановок. Последний просмотр сортировки Шелла выполняется по тому же алгоритму, что и в челночной сортировке. Предыдущие просмотры подобны просмотрам челночной обработки, но в них сравниваются не соседние элементы, а элементы, отстоящие на заданное расстояние h. Большой шаг на начальных этапах сортировки позволяет уменьшить число вторичных сравнений на более поздних этапах.
При анализе данного алгоритма возникают достаточно сложные математические задачи, многие из которых еще не решены. Например, неизвестно, какая последовательность расстояний даст лучшие результаты, хотя выяснено, что расстояния hi не должны быть множителями один другого.
Можно рекомендовать следующие последовательности (Они записаны в обратном порядке):
а) 1, 4, 13, 40, 121, ... ,
где hk-1 = 3hk +1, hp = 1 и р = [log2 n] - 1;
6) 1, 3, 7, 15, 31, ... ,
где hk-1 = 2hk +1, hp=l и p = [log2 n] – 1
Линейная (простая) вставка основана на последовательной вставке элементов в упорядоченный рабочий массив. Линейная вставка чаще всего используется тогда, когда процесс, внешний к данной сортировке, динамически вносит изменения в массив, все элементы которого известны и который все время должен быть упорядоченным.
Алгоритм линейной вставки следующий. Первый элемент исходного массива помещается в первую позицию рабочего массива. Следующий элемент исходного массива сравнивается с первым. Если этот элемент больше, он помешается во вторую позицию рабочего массива. Если этот элемент меньше, то первый элемент сдвигается на вторую позицию, а новый элемент помещается на первую. Далее все выбираемые из исходного массива элементы последовательно сравниваются с элементами рабочего массива, начиная с первого, до тех пор, пока не встретится больший. Этот больший элемент и все последующие элементы рабочего массива перемешаются на одну позицию вниз, освобождая место для нового элемента.
Центрированной и двоичная вставки. Введение "структуры" в упорядочиваемый рабочий mucchjb в общем случае сокращает количество сравнений, выполняемых при поиске позиции элемента в упорядочиваемом массиве. При использовании "структуры" в сортировке вставкой обычно применяют либо центрированную, либо двоичную вставки. Эти алгоритмы просты, но обладают особенностями реализации, характерными для нелинейных алгоритмов сортировки
Центрированная вставка. Представим рабочий массив состоящим как бы из двух ветвей - нисходящей (левой) и восходящей (правой). Центральный элемент этого массива называется медианой. Приведем описание алгоритма центрированной вставки.
В позицию, расположенную в середине рабочего массива, помешается первый элемент (он и будет медианой). Нисходящая и восходящая ветви имеют указатели, которые показывают на ближайшие к началу и концу занятые позиции. После загрузки первого элемента в центральную позицию оба указателя совпадают и показывают на него. Следующий элемент исходного массива сравнивается с медианой. Если новый элемент меньше, то он размещается на нисходящей ветви, в противном случае - на восходящей ветви. Кроме того, соответствующий концевой указатель продвигается на единицу вниз (нисходящая ветвь) или единицу вверх (восходящая ветвь).
Каждый последующий элемент исходного массива сравнивается вначале с медианой, а затем с элементами на соответствующей ветви до тех пор, пока не займет нужную позицию. Если область памяти, выделенная для одной ветви, будет исчерпана, то все элементы рабочего массива сдвигаются в противоположном направлении. Величина сдвига может варьироваться.
Двоичная (бинарная) вставка в отличии от линейной использует для отыскания места вставки алгоритм двоичного (бинарного) поиска, т.е. при вставке j-го элемента он сравнивается вначале с элементом [j/2], затем, если он меньше, сравнивается с элементом [j/4], а если больше - с [j/2+j/4] и т.д. до тех пор, пока он не найдет свое место. Все элементы рабочего массива, начиная с позиции вставки и ниже, сдвигаются на одну позицию вниз, освобождая место для j-го элемента.
Быстрая сортировка (метод Хоара). Метод "пузырька” является не самым эффективным из рассмотренных алгоритмов, поскольку требует большого количества сравнений и обменов. Однако оказалось, что сортировку, основанную на принципе обмена, можно усовершенствовать таким образом, что получится самый хорошим из известных на сегодняшний день методов.
Алгоритм быстрой сортировки, предложенный Xoapом использует тот факт, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях.
Суть метода заключается в следующем. Найдем такой элемент массива, который разобьет весь массив на два подмножества: т.е. элементы, которые меньше делящего элемента, и те, которые по величине не меньше его (т.е. как бы “отсортируем” один элемент, определив его окончательное местоположение). Далее применим эту же процедуру к более коротким левому и правому подмножествам.
Таким образом, надо реализовать рекурсивный алгоритм, который сортирует элементы множества, начиная с элемента с индексом left и завершая элементом с индексом right. Условие окончания данного алгоритма - совладение левой и правой границ подмножества (т.е. когда в подмножестве остается один элемент).
Точка деления массива может быть определена следующим образом.
Вводятся два указателя i и j, причём вначале i = left, a j = right. Сравниваются i-и и j-й элементы и, если обмен не требуется, то j = j - 1 и этот процесс повторяется. После первого обмена i увеличивается на единицу (1 = i + 1) и
сравнения продолжаются с увеличением i до тех пор, пока не произойдёт ещё один обмен. Тогда опять уменьшим j и т.д. пока не станет i =j. К моменту, когда i = j, элемент Ai
займет свою окончательную позицию, так как слева от него не будет больших элементов, а справа - меньших. Таким образом, поставленная задача решена.
Для повышения эффективности быстрой сортировки можно использовать следующий прием: не применяя рекурсивной процедуры к ставшему коротким подмножеству, для его сортировки перейти к другому методу, например, челночной сортировке. Т.е. рекурсивная процедура применяется только для массивов, длина которых не менее определенного размера.
2.2. Алгоритмы поиска

Алгоритмы поиска, как и алгоритмы сортировки, являются основными алгоритмами обработки данных как системных, так и прикладных задач.
Дан аргумент поиска К. Задача поиска состоит в отыскании записи, имеющей К своим ключом. Существуют две возможности окончании поиска: либо поиск оказался удачным, т.е. позволил определить местонахождение записи, содержащей ключ К, либо он оказался неудачным, т.е. показал, что ни одна из записей не содержит ключ К.
Рассмотрим основные алгоритмы поиска. Так как нас интересует в первую очередь сам процесс поиска, а не обнаруженные данные, будем считать, что ключ и запись совпадают и имеют тип int.
Последовательный (линейный) поиск. Для массива, данные в котором не упорядочены сортировкой или каким-либо другим способом, единственный путь для поиска заданного элемента состоит в сравнении каждого элемента массива с заданным. При совпадении некоторого элемента массива с заданным его позиция в массиве фиксируется. Этот алгоритм называется последовательным или линейным поиском. Эффективность этого метода очень низкая, так как для отыскания одного элемента в массиве размерности N в среднем нужно сделать N/2 сравнений.
Бинарный (двоичный) поиск. Бинарный или двоичный поиск может быть использован в качестве алгоритма поиска в упорядоченном массиве: K1 ( К2 ( ... ( Kn.
Схема алгоритма следующая. Сначала сравнивают К cо средним элементом массива. Результат сравнения позволяет определить, в какой половине массива следует продолжать поиск, применяя к ней ту же процедуру, и т.д. После не более чем [log2 n] + 1 сравнений ключ либо будет найден, либо будет
установлено его отсутствие.
Интерполяционный поиск. По-видимому, бинарный поиск не является самым лучшим методом поиска, доказательством чему служит то обстоятельство, что в повседневной жизни им мало пользуются. Гораздо чаще используется интерполяционный поиск. Его схема следующая. Если известно, что К находится между K1 и Кr, то номер очередного элемента для сравнения определяется формулой m = 1 + (r - 1) * (к – к1) / (кг – к1).
Последующая процедура аналогична процедуре, используемой в бинарном поиске.
Интерполяционный поиск асимптотически предпочтительнее бинарного; по существу один шаг бинарного поиска уменьшает количество "подозреваемых" записей от n до n/2 а один шаг интерполяционного - от n до 13 EMBED Equation.3 1415. В среднем интерполяционный поиск требует log2 log2 n шагов.

2.3. Примеры решения задач

Задача 2.3.1. Написать и протестировать функцию сортировки целочисленного массива методом стандартного обмена.
Определить время сортировки массива объемом 1000, 5000 и 10000 элементов. Для контроля за сортировкой организовать выдачу 10 элементов из начала, середины и конца исходного и отсортированного массивов.

#include
#include
#include
#include
// функция st_obmen( ) - сортировка методом "пузырька"
void st_obmen(int *a, int n)
{
int i, pp, buf;
do
{n-- ;
for(pp=i=0; iif (a[i]>a[i+1])
{ buf=a[i]; a[i]=a[i+1]; a[i+1]=buf; pp=1; }
}
while (pp) ;
}
// функия printm( ) - печать 10 первых, средних и последних
// элементов массива
void printm (char *str, int *a, int n)
{
int i, j, in;
printf ("\n\n\t\t\t %s \n", str);
for(j=0; j<3; j++, printf(“\n”))
{
switch (j)
{
case 0 : in=0 ; printf ( " начало : " ) ; break;
case 1 : in=n/2-5; printf (" середина : "); break;
case 2 : in=n-10; printf (" конец : ");
}
for(i=in; i printf ("%6d", a[i]);
}
}
void main ()
{
int i,j3, x[10000], n[3]={ 1000, 5000, 10000 };
time_t t1, t2, t;
double dt[3];
clrscr();
srand(2213);
for(3=0; j<3;j++)
{
for(i=0; i*(x+i)=rand()%n[j];
if(!j)= printm(n исходный массив (1000 эл.)", x, n[j]);
t1=time(&t);
st_obmen(x, n[j]);
t2=time(&t);
dt[j]=difftime(t2, t1);
if(!j) printm("Отсортированный массив", х, n[j]);
}
printf("\n\n \t Время сортировки ");
for(j=0;j<3; j++)
printf("\n %5d элементов --> %4.11f c ", n[j], dt[j]);
}
Задача 2.3.2. Написать и протестировать функцию поиска ключа в целочисленном массиве методом бинарного поиска.
Тест: поиск т ключей в целочисленном массиве объема n элементы массива - случайные числа из интервала (о, n - 1); ключи для поиска - случайные числа из интервала (0,n + m-1).
#include
#include
#include
#include
#include

//функция bin_poisk() - бинарный поиск в целочисленном //массиве
int bin_poisk(int *а, int n, int v)
{
int 1=0, k=n-l, m;
while (1<=k)
{
m=(1+k)/2;
if(velse if(v>a[m]) l=m+1;
else return m; // нашли!
}
return -1; // не нашли...
}
// функция st_obmen() - сортировка методом "пузырька"
void st_obmen(int *a, int n)
{
int i, pp, buf;
do .
{ n --;
for(pp=i=0; iif(a([i]>a[i+1])
{ buf=a[i]; a[i]=a[i+1]; a[i+1]=buf; pp=1; }
}
while(pp);
}
void main()
{
int i, n, m, *a, k, pk;
srand(2213);
m1:
clrscr();
printf(“Введите размер массива : ”);
scanf("%d", &n);
a=(int *) malloc(n*sizeof (int));
printf(" Введите число разыскиваемых ключей : ");
scanf("%d", &m);
for(i=0; i*(a+i)=rand()%n;
st_obmen(a , n);
printf("\n\t Аргумент \t Позиция " );
for(i=0); i{
k=rand()%(n+m) ;
pk=bin_poisk(a, n, k) ;
printf("\n\t %6d ", k);
if(pk== -l) printf ("\t\t не найден ");
else printf("\t\t %5d", pk);
}
printf("\n\n Продолжим? Да - введи 7 : ");
scanf("%d", &i);
if(i==7) goto m1;
}

2.4. Задания для самоконтроля

Задача 2.4.1. Провести сравнительный анализ эффективности методов сортировки вставками: линейной, двоичной, центрированной.
Предлагаемый тест: сортировка целочисленного массива размера w, элементы которого - случайные величины, распределённые в интервале (о, n - 1).
Задача 2.4.2. Исследовать эффективность методов поиска: последовательного, бинарного, интерполяционного.
Предлагаемый тест: поиск т элементов в целочисленном массиве длины п.
Элементы массива - случайные величины, распределённые в интервале (о, n - 1). Ключи поиска – случайные величины, распределённые в интервале (о, n+m - 1).
Задача 2.4.3. Провести сравнительный анализ эффективности следующих методов сортировки:
1) линейный выбор с обменом, челночная сортировка, двоичная вставка;
2) сортировка Шелла, центрированная вставка;
3) стандартный обмен, быстрая сортировка, линейна вставка.
Предлагаемый тест: сортировка целочисленного массива размера n, элементы которого - случайные величины, распределённые в интервале (о, n - l).
Задача 2.4.4. Написать и протестировать функции сортировки целочисленных массивов и поиска ключей в них следующим методам:
1) челночная сортировка, бинарный поиск;
2) сортировка Шелла, бинарный поиск (рекурсивная функция);
3) быстрая сортировка, бинарный поиск;
4) центрированная вставка, интерполяционный поиск. Тест сортировки: сортировка целочисленного массива
размера n, элементы которого - случайные величины, распределённые в интервале (о, n - 1).
Тест поиска: поиск т элементов в отсортированном массиве.
Задача 2.4.5. Написать и протестировать функции сортировки записей и поиска их по ключам для следующих методов:
1) линейный выбор с обменом, бинарный поиск;
2) челночная сортировка, бинарный поиск;
3) сортировка Шелла, бинарный поиск; 4) быстрая сортировка, бинарный поиск;
5) стандартный обмен, интерполяционный поиск;
6) линейная вставка, интерполяционный поиск;
7) центрированная вставка, бинарный поиск. Запись имеет три поля, например, фамилия, имя, номер телефона. Иметь не менее 30 записей. Поиск - по любому ключу, задаваемому из меню.
Задача 2.4.6. Провести сравнительный анализ эффективности не менее двух вариантов быстрой сортировки целочисленных массивов большого размера (n > 5000).
Задача 2.4.7. Написать и протестировать функцию челночной сортировки целочисленного массива с управляемым направлением (возрастание/убывание) сортировки по признаку.
Заголовок функции должен иметь вид:
void shatl(int *a, int n, char *pr) , где a - сортируемый массив;
n - размер массива;
рr - признак, управляющий направлением сортировки: pr=”incr” - сортировка по возрастанию;
pr=”decr” - сортировка по убыванию.
Задача 2.4.8. Исследовать возможности адаптации различных методов сортировки к структуре исходного массива. С этой целью определить время сортировки целочисленного массива объёма n для следующих вариантов представления исходного массива:
неупорядоченный,
почти упорядоченный,
упорядоченный в противоположном направлении.
Методы, подлежащие исследованию:
1) линейный выбор с обменом, центрированная вставка;
2) челночная сортировка, линейная вставка;
3) сортировка Шелла, линейная вставка;
4) быстрая сортировка, бинарная вставка;
5) стандартный обмен, бинарная вставка.
Задача 2.4.9. Написать функцию, которая вставляет в упорядоченный линейный список новый элемент. Линейный список хранится связанно.
Задача 2.4.10. Написать функцию сортировки N целых чисел методом квадратичной выборки.
Задача 2.4.11. Пусть заданны на входе неупорядоченные списки студентов четырёх клубов С1, С2, С3, С4. Никакой клуб не имеет более 250 членов. Написать программу для определения всех студентов являющихся членами по крайней мере трех клубов. (Для упрощения предположить, что члены клубов перечисляются не по фамилиям, а целыми положительными числами по номерам их студенческих билетов.)
Задача 2.4.12. Пусть на входе заданно число N, за которым следует N целых чисел G1, G2, , GN. Написать программу для сортировки последовательности G1, G2, , GN слияния и печати результирующей последовательности. (Числа для сортировки хранятся с использованием связанного хранения; слияние делается не реальным перемещением, а изменением связей.)
Задача 2.4.13. Конечное множество целых чисел можно представить упорядоченным линейным списком целых чисел. Написать программу для:
нахождения пересечения двух конечных множеств целых чисел, представленных связанными линейными списками;
б) объединения двух конечных множеств целых чисел, представленных связанными линейными списками.
Задача 2.4.14. Написать рекурсивную функцию сортировки N чисел, используя бинарную сортировку.
Задача 2.4.15. Написать функцию сортировки N Т-разрядных чисел методом битовой распределяющей сортировки, используя только один вспомогательный массив, последовательно доступной с обоих концов.

3. Практическое занятие № 3.
Конструирование динамических структур данных

3.1. Общие сведения

В языках программирования определены следующие структуры данных: одиночное данное (простая переменная);
массив однотипных данных;
структура (совокупность разнородных данных, относящихся к одному объекту).
Цель описания типа данных и последующего определения некоторых переменных, как относящихся к этому типу, состоит в том, чтобы раз и навсегда зафиксировать диапазон значений, присваиваемых этим переменным, и размер выделяемой для них памяти. Поэтому о таких переменных говорят, как о статических переменных.
Однако не всегда такие средства работы с информацией оказываются достаточными и удобными. Некоторые задачи исключают использование структур данных фиксированного размера и требуют введения динамических структур, способных увеличиваться и уменьшаться в размерах в процессе работы программы. Каждая структура данных характеризуется, первых, взаимосвязью элементов и, во-вторых, набором типовых операции над этой структурой. В случае динамической структуры важно:
каким образом может расти и сокращаться данная структура данных;
каким образом можно включить в структуру новый и удалить существующий элемент;
как можно обратиться к конкретному элементу структуры для выполнения над ним определенной операции (доступ по индексу здесь, очевидно, менее удобен, чем это было в случае массивов, так как любой элемент при изменении размеров структуры может изменить свою позицию. Поэтому обычно доступ к элементам динамической структуры относительный: найти следующий (предыдущий) элемент по отношению к текущему, найти последний элемент и т.п.).
Одной из простейших и в то же время типичных структур данных является очередь. Проблема очереди возникает, когда имеется некоторый механизм обслуживания, который может выполнять заказы последовательно, один за другим. Если при поступлении нового заказа данное устройство свободно, оно немедленно приступает к выполнению этого заказа; если же оно уже выполняет какой-то ранее полученный заказ, то новый заказ поступает в конец очереди других заказов, ожидающих выполнения. Когда устройство освобождается, оно приступает к выполнению заказа из начала очереди (этот заказ удаляется из очереди, и первым в ней становится следующий заказ). Если заказы поступают нерегулярно, очередь то удлиняется, то укорачивается, и даже может оказаться пустой (рис. 3.1).


Рис. 3.1.
Очередь часто называют системой, организованной и работающей по принципу FIFO (first in - first out). Основными операциями с очередью являются добавление нового элемента в конец и удаление элемента из начала очереди.
Рассмотрим, как может быть реализована работа с очередью на С, с использованием структур, указателей на структуры и функций динамического выделения или освобождения памяти.
В программе, приведенной ниже, работа с очередью ведется с помощью двух функций:
функция insert() отводит память под очередной элемент, заносит в него нужную информацию и ставит в конец очереди;
функция take_off() удаляет из очереди ее первый элемент, освобождает память из-под него и перемещает указатель начала очереди на следующий элемент. В случае попытки удаления элемента из пустой очереди параметр ошибки error получает значение 1.
#include
#include
#define QUEUE struct queue
QUEUE
{ int info; // поле информации элемента очереди QUEUE *next; // поле ссылки на следующим элемент
}; // очереди
void insert (QUEUE **q, int item)
{
QUEUE *tek=*q; //указатель на текущее звено очереди
QUEUE *pred=0; // pred содержит адрес последнего
//элемента
QUEUE *new_n;
while(tek) // просматриваем очередь до конца
{ pred=tek; tek=tek->next; } new_n=(QUEUE*)malloc(sizeof(QUEUE));
new_n->info=item;
if(pred) // если очередь была не пуста
{
new_n->next=pred->next;
pred->next=new n; }
else ( *q=new_n; (*q)->next=0; }
}
int take_off (QUEUE **q, int *error)
{ int value=0; //значение возвращаемого элемента очереди
QUEUE *old=*q; //указатель на старую голову очереди
if (*q) // если очередь не пуста
{ value=old->info; *q=(*q)->next;
free(old); *error=0; // элемент удалён из очереди
}
else *error=1;
return value;
}
void main ()
{
int error, j;
QUEUE *q1, *q2;
for(j=12; j<=15; j++)
insert(&q1, j);
for(j=l; j<=4; j++)
insert(&q2, take_off(&q1, &error));
for(j=l; j<=4; j++)""
printf("\n Удален из q2:%d",take_off(&q2, &error) );
}
Другая часто встречающаяся структура данных это – стек (магазин - отличается от очереди тем, что она организована по принципу LIFO(last in-first out).Операции в ключе) и удаления элемента в стеке выполнится: только с одного конца, называемого вершиной стека. Когда новый элемент помещается в стек, то прежний верхний элемент как бы "проталкивается" вниз и становится временно недоступным. Когда же верхний элемент удаляется с

Рис. 3.2.
вершины стека, предыдущий элемент "выталкивается" наверх и опять является доступным (рис. 3.2).
Потребность в организации стека возникает при решении, например, такой задачи. Пусть имеется текст, сбалансированный по круглым скобкам. Необходимо построить таблицу, в каждой строке которой будут находиться координаты соответствующих пар скобок, т.е. для текста
(. . . .(. . . . . . . . .). . .( . . . . . . . . . . ) . . . . .)
0 17 42 61 84 95 таблица должна быть такой
17 42
61 84
0 95
Поскольку текст сбалансирован по круглым скобкам, то как только встретится ')', это будет пара для последней пройденной '('. Поэтому алгоритм решения данной задачи может быть следующим: будем идти по тексту и как только встретим '(', занесем её координату в стек; как только встретится ')', возьмем из стека верхнюю координату и распечатаем ее вместе с координатой данной ')'.
Рассмотрим программу, в которой реализована работа со стеком. В ней использованы функции:
Push() - положить элемент на вершину стека,
рор() - вытолкнуть верхний элемент из стека,
peek() - прочитать значение верхнего элемента, не удаляя сам элемент из стека.
#include
#include
#define STACK struct stack
STACK
{ int info; // поле значений элемента стека
STACK *next; // поле ссылки на следующим элемент стека
};


void push ( STACK **s, int item)
{
STACK *new_n;
new_n = (STACK*)malloc(sizeof(STACK));
// запросили память под новый элемент
new_n->info=item; // заносим значение в новый элемент
new_n->next=*s; // новый элемент стал головой стека
*s=new_n; // указателю *s присвоили адрес головы стека
}
int pop (STACK **s, int *error)
{
STACK *old=*s; int info=0;
if(*s) // стек не пуст
{ info=old->info; *s=(*s)->next;
free(old); //освобождаем память из-под выбранного элем.
*error=0; // элемент удален успешно
}
else *error=l;
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·rintf("\n pop(&s2)=%d", pop(&s2, &error));
}
13 EMBED Word.Picture.8 1415
Рис 3.3.
Стеки и очереди являются одними из разновидностей более широкого класса структур данных - списков. Связанный список - это структура следующего вида (рис. 3.3).
Это простой однонаправленный список, в котором каждый элемент (кроме последнего) имеет ссылку на следующий эле-1мент и поле информации. Можно организовать также кольцевой список (в нем последний элемент будет содержать ссылку на первый) или двунаправленный список (когда каждый элемент кроме первого и последнего, имеет две ссылки: на предыдущий; и следующий элемент) и т.д. Кроме того, можно помещать в начале списка дополнительный элемент, называемый заголовком списка. Как правило, заголовок списка используется для храпения информации обо всём списке. В частности, он может со держать счётчик числа элементов в списке. Наличие заголовка приводит к усложнению одних и упрощению других программ, работающих со списками.
При работе со списком могут быть полезны следующие базовые функции:
insert() - добавить новый элемент в список таким образом, чтобы список оставался упорядоченным в порядке возрастания по значению одного из полей;
take_out() - удалить элемент с заданным полем (если он есть в списке);
is_present() - определить, имеется ли в списке заданный элемент;
display() - распечатать значения всех полей элементов списка;
destroy_list() - освободить память, занимаемую cписком.
Довольно часто при работе с данными бывает удобно использовать структуры с иерархическим представлением, которые хорошо изображаются с помощью дерева (рис. 3.4).

Рис 3.4.
Дерево состоит из элементов, называемых узлами (вершинами). Узлы соединены между собой направленными дугами. В случае X->Y вершина X называется предшественником (родителем), a Y - преемником (сыном). Дерево имеет единственный узел - корень, у которого нет предшественников. Любой другой узел имеет ровно одного, предшественника. Узел, не имеющий преемника, называется листом.
Рассмотрим работу с бинарным деревом (в котором у каждого узла может быть только два преемника - левый и правый сын). Необходимо уметь:
построить дерево;
выполнить поиск элемента с указанным значением узле;
удалить заданный элемент;
обойти все элементы дерева (например, чтобы над каждым из них провести некоторую операцию).
Обычно бинарное дерево строится сразу упорядоченным, т.е. узел левого сына имеет значение меньшее, чем значение родителя, а узел правого сына - большее. Например, если приходят числа 17, 18, 6, 5, 9, 23, 12, 7, 8, то построенное по ним дерево будет выглядеть так (рис. 3.5).

Рис. 3.5.
Для того, чтобы вставить новый элемент в дерево, надо найти для него место. Для этого, начиная с корня, будем сравнивать значения узлов (Y) со значением нового элемента (NEW). Если NEW < Y , то пойдем по левой ветви; в противном случае - по правой. Когда дойдем до узла, из которого выходит нужная ветвь для дальнейшего поиска, это означает что место под новый элемент найдено.
Путь поиска места для числа 11 в построенном выше дереве показан на рис. 3.6.
При удалении узла из дерева возможны три ситуации:
а) исключаемый узел - лист (в этом случае надо просто удалить ссылку на данный узел);
б) из исключаемого узла выходит только одна ветвь;

Рис 3.6.
в) из исключаемого узла выходят две ветви (в таком случае на место удаляемого узла надо поставить либо самый правый узел левой ветви, либо самый левый узел правой ветви для сохранения упорядоченности дерева). Например, построенное ранее дерево после удаления узла 6 может стать таким (рис. 3.7).

Рис. 3.7.
Рассмотрим задачу обхода дерева. Существуют три способа обхода, которые естественно следуют из самой структуры дерева.
1) Обход слева направо: A, R, В (сначала посещаем левое поддерево, затем - корень и, наконец, правое поддерево).
2) Обход сверху вниз: R, А, В (посещаем корень до поддеревьев).
3) Обход снизу вверх: А, В, R (посещаем корень после поддеревьев).
Интересно проследить результаты этих трех обходов на примере записи формул в виде дерева.
Например, формула (а+b/с)*(d-e*f) будет подставлена так (рис. 3.8).
(дерево формируется по принципу: операция - узел, операнды - поддеревья).
Обход 1 даст обычную инфиксную запись выражения (правда, без скобок).
Обход 2 - префиксную запись *+a/bc-d*еf.
Обход 3 - постфиксную (ПОЛИЗ - польская инверсная запись): abc/+dеf*-*.

Рис. 3.8.
В качестве примера работы с древовидной структурой данных рассмотрим решение следующей задачи.
Вводятся фамилии абитуриентов; необходимо распечатать их в алфавитном порядке с указанием количества повторений каждой фамилии.
В программе будет использована рекурсивная функция dеr(), которая строит дерево фамилий, а также рекурсивная функция для печати дерева print_der(), в которой реализован первый способ обхода дерева.
#include
#include
#define TREE struct der
TREE
{ char *w;
int c;
TREE *l;
TREE *r;
};
TREE *der(TREE *kr, char *word)
{
int sr;
if(kr==NULL)
{
kr=(TREE *)malloc(sizeof(TREE));
kr->w=word; kr->c=l;
kr->l =)tr->r=NULL;
}
else if ((sr=strcmp(word, kr->w) )==0) kr->c++;
else if(sr<0) kr->l = der(kr->l, word);
else kr->r = der(kr->r, word);
return kr;
}
void print_der(TREE *kr)
{
if(kr)
{ print_der(kr->l);
printf("слово - %-20s \tкoл-во повтор.- %d\n", kr->w,
kr->c);
print_der(kr->r); )
}
}
void main()
{ int i; TREE *kr;
static char word[40][21];
kr=NULL; i=0;
puts("Введите <40 фамилий длиной <20 каждая");
scanf("%s" word[i]);
while(word[i][0]!='\0')
{ kr=der(kr,word[i]);
scanf("%s", word[++i]);
}
print_der(kr);
}
Рассмотрим еще один пример использования динамических структур данных. По введенной формуле необходимо построить се ПОЛИЗ. (При записи формулы используются только операции +, , *, / и буквы - операнды.)
#include "stack.h" // в файле stack.h - описанные выше функции
#include // работы со стеком
#include
#include
#include
#define ZNAK (c==’*’ | | c=='/')
void main( )
{ char s[50], s1[80], c;
int er, i, l, k=0;
STACK *st=NULL;
puts("Введите инфиксную запись формулы, операндами в которой");
puts("являются буквы, а знаками - символы +, , *, /");
gets(s);
l=strlen(s);
push(&st, '(' ); // заносим '(' в стек и
for (i=0; iif(isalpha(s[i]))
s1[k++]=s[i] ; // операнд заносим в выходной массив
else if(s[i] = ( ) push(&st, ( ); // ' (' кладется в стек
else if (s[i]== ) ’ )
while((с=рор(&ist, &er))'= ( )

s1[k++]=c; //извлекаем из стека все до ближайшей '(',
// которую тоже удаляем из стека
else switch (s[i]) // см. ком-рий после программы
{
case +’ :
case - ’ : while((c=peek(&st, &er)) != ( ’)
sl[k++]=pop(&st, &er);
push(&st, s[i]); break;
case * ’:
case / ’ : while((c=peek(&st, &er)) != ( ’ )
{ if( ! ZNAK) break;
sl[k++]=pop(&st, &er);
}
push(&st, s[i]); break;
default: printf ("Неверный символ s[%d] : %c !", i+1, s[i]);
exit(-l);
// в заключение выполняются также же действия, как
// если бы встретилась закрывающая скобка
while((c=pop(?st, ?er)) !=’( ’ )
sl [k++]=c;
s1[ k]= \0 ’;
puts (" \ n \ t \ t ПОЛИЗ: \n\n\t); puts(s1);
}
Комментарии: когда в записи формулы встречается знак операции - не скобка и не операнд - то с вершины стека извлекаются (до ближайшей скобки, которая сохраняется в стеке) знаки операций, старшинство которых больше или равно старшинству данной операции, и они заносится в выходной массив, после чего рассматриваемый знак заносится в стек.

3.2. Задания для самоконтроля

Задача 3.2.1. В файле находится текст программы на языке FORTRAN. Написать, используя стек, препроцессор, проверяющий правильность вложений циклов в этой программе.
Задача 3.2.2. В файле находится текст, в котором используются скобки трех типов: ( ), | |, { }. Используя стек, проверить, соблюден ли баланс скобок в тексте.
Задача 3.2.3. Используя очередь и стек. Решить задачу: в файле записан текст, сбалансированный по круглым скобкам. Требуется для каждой пары соответствующих открывающей и закрывающей скобок напечатать номера их позиции в тексте, упорядочив пары номеров по возрастанию номеров по лиши:
а) закрывающих скобок (например, для текста a+(45-f(x)*(b-c)) надо напечатать 8 10; 12 16; 3 17);
б) открывающих скобок (например, для текста a+(45-f(x)*(b-c)) надо напечатать 3 17; 8 10; 12 16).
Задача 3.2.4. Используя стек, проверить, является ли содержимое текстового файла правильной записью формулы следующего вила:
<формула>::=<терм> | <терм>+<формула> | <терм>-<формула>
<терм>::=<имя> | (<формула>)
<имя>::=х|у|z
Задача 3.2.5. В текстовом файле записана без ошибок формула следующего вила:
<формула>::=<цифра> | M (<формула>,<формула>) |
m(<формула>,<формула>)
<цифра>::=0 | 1 | 2 | 3 | 4 | 5 | б | 7 | 8 | 9
(М обозначает функцию max , a m - функцию min).
Используя стек, вычислить как целое число значение данной формулы. Например, М(5,m(6,8))=6.
Задача 3.2.6. В текстовом файле записано без ошибок логическое выражение следующего вида:
<лог.выр.>::*true|!false|<лог.выр.>|<лог.выр.>| <лог.вьф.> |
<лог.выр.> || <лог.выр.>
Используя стек, вычислить значение этого выражения с учетом общепринятого приоритета операции.
Задача 3.2.7. Написать и протестировать функции включения, удаления и чтения очередного элемента стека объёмом я элементов. В случае невозможности включения (переполнения стека), удаления из пустого стека выставлять флаг.
Задача 3.2.8. Написать и протестировать функции для включения, исключения и поиска элемента кругового списка для:
а) списка без заголовка;
б) списка с заголовком (заголовок может содержать некоторую информацию о списке, например, число элементов в списке).
Задача 3.2.9. Используя двунаправленный список, написать и протестировать функции, реализующие отдельные действия при игре в "новое домино", в котором кроме традиционных правил игрок может на каждом ходу заменить любую конечную кость на свою. Необходимы следующие функции:
а) проверить, можно ли сделать ход;
б) сделать ход;
и) проверить, можно ли сделать замену;
г) заменить кость;
д) определить, закончена ли игра.
Задача 3.2.10. Написать и протестировать функции поиска, включения и исключения элемента бинарного дерева с за данным ключом.
Задача 3.2.11. Используя стек, написать не рекурсивную версию алгоритма Хоара быстрой сортировки [1,7].
Задача 3.2.12. Напишите программу сложения двух длинных целых чисел, представленных в виде строк, используй:
а) круговые списки;
б)двунаправленные списки.
Задача 3.2.13. Два бинарных дерева подобны, если либо оба они пусты, либо оба не пусты, и при этом их левые и правые поддеревья подобны. Определить, являются ли два дерева подобными.
Задача 3.2.14. Два бинарных дерева зеркально подобны, если либо оба они пусты, либо оба не пусты, и при этом левое поддерево одного из них подобно правому поддереву другого и наоборот. Определить, являются ли два дерева зеркально подобными.
Задача 3.2.15. Дли организации вычислении значении выражения на ЭВМ удобнее вместо обычной (инфиксной) записи использовать постфиксную (пли польскую инверсную) запись ПОЛИЗ. При вычислении выражении, записанного в ПОЛИЗе операции выполняются в том порядке, в котором они встречаются при просмотре выражении слева направо; поэтому отпадает необходимость использовании скобок и многократного сканирования выражения из-за различного старшинства операций.
Например, выражению 2+3*4 соответствует





Рис. 3.9.
ПОЛИЗ 234*+, а выражению Используя стек:
а) вычислить как целое число значение выражения, записанного в ПОЛИ3е;
б) выражение, записанное в ПОЛИЗе, перевести в инфиксную форму и распечатать.
Задача 3.2.16. Многочлен от одной переменной X можно представить как связанный список с узлами вида

Например, многочлен -Зх6 + 4x3 + бх2 + 9 будет храниться в виде списка, в котором узлы расположены в порядке убывания степеней X. Используя список:
а) по введенной безошибочной записи многочлена построить его представление в виде списка;
б) сложить два многочлена, представленных в виде списка (нулевые слагаемые исключить из результирующего списка);
в) проверить на равенство два многочлена;
г) вычислить значение многочлена s(x), представленного в виде списка, в целочисленной точке X;
д) по многочлену s(x) построить его производную – многочлен р(х);
е) привести подобные члены в многочлене и расположить его у по убыванию степеней X (например, из
-8х4 - 74х + 8х4 + 5 - х3 получить -х3 - 74х + 5);
ж) перемножить два многочлена, заданных в виде списков;
з) распечатать многочлен, заданный в виде списка, в обычном виде (например, так: 52у^3 - 6у^2 + у).
Задача 3.2.17. Составить программу, которая читает произвольный С-файл и печатает в алфавитном порядке каждую группу имен переменных, совпадающих в первых N символах, но различающихся где-либо дальше. Параметр N задается из командной строки. При решении задачи использовать дерево с узлами вида:
struct NODE
{
char *word;
int k;
NODE *left;
NODE *right;
};
(He рассматривать слова внутри символьных строк комментариев!)
Задача 3.2.18. Формулу вида:
<формула>:: -<цифра> | (<формула><знак><формула>)
<знак>::= + | - | *
<цифра>::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
можно представить в виде бинарного дерева по следующим правилам:
формула из одной цифры представляется деревом из одной вершины с этой цифрой;
формула вида f1 # f2 представляется деревом, в котором корень - это знак # соответствующей операции, а левое и правое поддеревья - это представления формул f1, f2 в виде бинарных деревьев.
Например, формуле 5*(3+8) соответствует дерево


Рис. 3.10.
Требуется:
а) построить дерево по формуле указанного выше вида;
б) вычислить как целое число значение дерева-формулы;

в) по заданному дереву распечатать соответствующую формулу.
Задача 3.2.19. С использованием структуры "стек" переписать содержимое текстового файла, разделенного на строки, в другой файл. Причем, необходимо переносить в конец каждой строки все входящие в нее цифры в обратном порядке.
Задача 3.2.20. С использованием структуры "очередь" за один просмотр файла, содержащего целые числа, распечатать
файл в следующем виде: сначала - все числа, меньшие А; затем - все числа из [А, В]; потом - все остальные числа.
Задача 3.2.21. Пусть имеется ЭВМ, у которой один регистр и шесть команд:
LD А загрузить А в регистр;
ST А запомнить содержимое регистра в А;
AD А сложить содержимое регистра с А;
SB А вычесть А из содержимого регистра;
ML А умножить содержимое регистра на А;
DV А разделить содержимое регистра на А.
Напечатать последовательность машинных команд, необходимых для вычисления выражения, задаваемого в постфиксной форме. Выражение может состоять из однобуквенных операндов и знаков операций сложения, вычитания, умножения и деления. В качестве рабочих использовать переменные вида Тn.
Например, выражению ABC*+DE--/ будет соответствовать следующая последовательность команд:
LD В
ML С
AD A
ST Т1
LD D
SB E
ST T2
LD T1
DV T2
ST Т1
Задача 3.2.22. Составить программу, формирующую "перекрестные ссылки", т.е. печатающую список слов, которые встречаются в анализируемом файле, а для каждого слова - список номеров строк, в которых это слово встречается. При решении задачи рекомендуется использовать следующие структуры данных:
struct LIST // список номеров строк для данного слова
{
int num;
struct LIST *p;
}
struct NODE // узел дерева с информацией об очередном слове
{
char *word;
struct LIST *lines;
struct NODE *lef t;
struct NODE * right;
}
Задача 3.2.23. Закодировать введённое сообщение с использованием алгоритма Хаффмена [8].
Задача 3.2.24. Распечатать слова текста, отсорти-рованный в порядке убывания частоты их встречаемости (радом с каждым словом выводить значение счетчика частоты его вхождении текст). При решении задачи использовать дерево следующей структуры:
struct NОDE
{
char *word;
int k;
struct NODE *left;
struct NODE *right;
}
Задача 3.2.25. Последовательность целых чисел А1, А2, , Аn задана как линейный список в связанном хранении и задан указатель первого элемента. Написать функцию для обращения этого списка, т.е. получить список An, An-1, , A1 в связанном хранении.
Задача 3.2.26. Написать функцию, которая, исследуя элементы линейного списка К1, К2, Кn в связанном хранении. Упорядочивает их в список элементов К’1, K’2, , K’s, K1, K”1,, K”t, где s + t + 1=n, K’I < K1, K”i ( K1 в связанном хранении (указатель на первый элемент списка задан).
Задача 3.2.27. Последовательность F=( А1, А2, , Аk( целых чисел А1 ( А2 ( ( Аk и стек V свободной памяти хранятся как простые связанные структуры с указателями AF и AV на их начало. Написать фрагмент программы, который для каждого I, 1 ( i ( k-1, такого, что Ai=Ai+1, удаляет число Ai+1 из списка и добавляет освободившийся участок памяти к стеку V свободной памяти.
Задача 3.2.28. На входе задана последовательность целых положительных чисел. Написать программу, которая запоминает эту последовательность как связанную структуру W и затем печатает ее в возрастающем порядке путем повторного определения наименьшего число в W, печати и удаления его из W, пока структура не станет пустой.
Задача 3.2.29. Из упорядоченного списка исключить все элементы, значения ключей которых находятся в заданных пределах. Из исключенных элементов образовать новый список.
Задача 3.2.30. По заданной фамилии выдать телефоны всех однофамильцев.
Задача 3.2.31. Написать и протестировать функции для включения, исключения и поиска элемента кругового списка для:
а) списка без заголовка;
б) списка с заголовком (заголовок может содержать некоторую информацию о списке, например, число элементов в списке).
Задача 3.2.32. Используя двунаправленный список, написать и протестировать функции, реализующие отдельные действия при игре в "новое домино", в котором кроме традиционных правил игрок может на каждом ходу заменить любую конечную кость на свою. Необходимы следующие функции:
а) проверить, можно ли сделать ход;
б) сделать ход;
и) проверить, можно ли сделать замену;
г) заменить кость;
д) определить, закончена ли игра
Задача 3.2.33. Написать функцию копирования очереди, реализованной в виде циклического списка.
Задача 3.2.34. Написать функцию копирования двусторонней очереди, которая реализована в виде списка с двумя связями.
Задача 3.2.35. Пусть два целых положительных числа N и K даны на входе. Предположим, что числа 1,2,,N расположены упорядоченно по кругу. Составить программу, которая, начиная с 1 и продолжая по часовой стрелке, печатает текущее число, удаляет его из круга и затем рассматривает K-е следующие число в списке, причем процесс продолжается до тех пор, пока список не станет пустым. Так для значений N=10, K<>3 получаем выход: 1,4,7,10,5,9,6,3,8,9.
Задача 3.2.36. Пусть задан одномерный массив из 100 элементов, используемых для последовательного хранения очереди. На входе заданна последовательность целых чисел, Если число n>0, то его нужно добавить в очередь; если n=-1, то очередной элемент из очереди следует удалить; если n=0, то имеем конец списка. Написать фрагмент программы, который работает с очередью как с циклической структурой и печатает сообщения об ошибках каждый раз при обнаружении аварийной ситуации.
Задача 3.2.37. Разработать программу для одновременного хранения пяти стеков в одномерном массиве из M элементов. При необходимости перераспределения стеки следует упорядочить так, чтобы свободные участки памяти были поровну распределены между ними. С начала все стеки пустые. Вход содержит пары целых чисел (i,j), 1(abs(5, причем пара (i,j), где j>0, указывает, что элемент со значением i добавляется в j-й стек; пара (i,j), где j<0, указывает, что очередной элемент j-го стека нужно удалить(i здесь не используется). Программа должна печатать расположение стеков до и после каждого перераспределения.



4. Практическое занятие № 4.
Алгоритмы на графах


4.1. Некоторые основные определения

Граф - это пара (V, Е), где V - конечное непустое множество точек, называемых вершинами, а Е - множество неупорядоченных пар вершин (эти пары называются ребрами). Графы удобно изображать с помощью рисунков, которые состоят из точек и линий, соединяющих некоторые из этих точек. При этом точки соответствуют вершинам графа, а линии - его ребрам (рис. 4.1). Пусть и, v - вершины, а е - ребро, их соединяющее. В этом случае вершины и ребро называются инцидентными. Степень вершины - это число ребер, инцидентных ей. Ребра, инцидентные одной вершине, а также вершины, соединенные одним ребром, называются смежными.
Ребро графа называется ориентированным, если существенен порядок расположения его концов. Граф, все ребра которого ориентированные, называется орграфом, а его ребра - дугами.
Граф называется полным, если любые две его вершины соединены ребром (рис. 4.2).
Дополнением графа G называется граф G' с тем же множеством вершин, что и у G, причем, две вершины в G' смежны тогда и только тогда, когда они не смежны в G. Ребра графов G и G* вместе образуют полный граф (рис. 4.3).


Два графа G и Н изоморфны, если существует взаимно однозначное отображение множества вершин графа G на множество вершин графа Н, сохраняющее смежность (рис. 4.4).

Подграфом G' называется такая часть графа G, которая вместе с каждой парой вершин из G содержит и ребро, соединяющее эту пару, если только это ребро есть в G (рис. 4.5).

Множество вершин графа называется независимым, если никакие две вершины из этого множества не смежны (т.е подграф, порожденный этим множеством вершин, является пустым). Множество вершин графа называется кликой, если любые две входящие в него вершины смежны.
Путь, соединяющий вершины и и v, - это последовательность вершин v0, vl ,..., vn (n ( 0) такая, что vo=u, vn=( и (i:0( i (Ј n-1 вершины Vi и Vi+1 соединены ребром. Длина пути равна количеству его ребер. Путь замкнут, если v0 = vn. Вершина и достижима из вершины v, если существует путь из v в u.
Цикл - это замкнутый путь, в котором ни одно ребро не повторяется дважды. Простой цикл - это замкнутый путь, ни одна вершина в котором (кроме v0 и vn ) не повторяется дважды.
Гамильтоновым называется путь, содержащий все вершины графа (рис. 4.6). Если этот путь является простым циклоид то такой цикл называется гамильтоновым. Эйлеровым называется цикл, проходящий через каждое ребро графа ровно один раз (рис. 4.7)
Расстояние между двумя вершинами - это длина кратчайшего пути, соединяющего эти вершины.
Обод - это граф, вершины которого v0,vi,...,vn (n(0) можно занумеровать так, что Vi:1 <= i <= n - 1 вершина vi соединена ребрами с vi -1 и vi+1, v0 - с vn, а других ребер нет.



Граф называется сетным, если для любой пары вершин существует соединяющий их путь. Максимальный связный подграф называется компонентой связности данного графа.
Граф допускает правильную вершинную раскраску в k цветов, если любые две смежные вершины раскрашены в разные цвета.
Мультиграфом (рис. 4.8) называется граф, в котором пара вершин соединяется несколькими различными ребрами (дугами).

Деревом называется связный граф без циклов.
Корневое дерево (рис. 4.9) - это связный орграф без циклов, удовлетворяющий условиям:
1) имеется единственная вершина, называемая корнем, в которую не входит ни одна дуга;
2) к каждой некорневой вершине ведет ровно одна дуга.
Вершины, из которых не выходит ни одна дуга, называются листьями.
Система дорог - это размеченный мультиграф, в котором вершины соответствуют городам, а ребра - дорогам. Односторонним дорогам соответствуют дуги, а двусторонним - ребра. Каждой дороге приписано некоторое положительное вещественное число - длина дороги. Длина пути в системе дорог - это сумма длин дорог данного пути. Расстояние между двумя городами - это длина минимального пути между ними.
Источник орграфа - это вершина, от которой достижимы все остальные вершины. Сток орграфа - это вершина, достижимая со всех других вершин.

4.2. Способы машинного представления графов

1. Классическим способом представления графа является матрица инциденций А(m, n) - [аij] , где п - число вершин, а т - число ребер графа.
а) для неориентированного графа: вершина i инцендентна ребру j,
|1 - вершина i инцидентна ребру j;
a i j = |

| O - вершина i не инцидентна ребру j.
В каждом столбце такой матрицы ровно две единицы. Равным столбцов нет. Пример матрицы инциденций для графа (рис. 4.10):


б) для орграфа:
|1, если вершина i является началом дуги j;
a i j = | -1, если вершина i является концом дуги j;
|О, если вершина i и дуга j не инцендентны.


Для орграфа, приведенного на рис. 4.11, имеем:
Недостаток данного способа представления состоит в том, что требуется т*п ячеек памяти, большинство из которых будет занято повторяющимися значениями (нулями). Кроме того, не удобен доступ к информации: для ответа на элементарные вопросы типа "Есть ли в графе дуга.(x, у)? , "К каким вершинам ведут ребра из вершины х? может потребоваться перебор всех столбцов матрицы.
2. Более удачный способ представления графов - матрица смежности
В(n, n) = [bk j] ,
где п - число вершин графа:

Эта матрица является симметрической с нулями на главной диагонали. Число единиц в строке равно степени соответствующей вершины.
Пример матрицы смежности (рис. 4.12):

Преимуществом такого представления является "прямой доступ" к ребрам графа, т.е. имеется возможность за один шаг получить ответ на вопрос "существует ли в графе ребро (xfy)T. Недостаток же заключается в том, что независимо от числа ребер объем занимаемой памяти составляет (n*n)/2-n.
3. Еще один способ задания графов - составление списка ребер. Для описания каждого ребра требуется по 2 ячейки памяти (по одной на каждую концевую вершину ребра), поэтому объем занимаемой памяти составляет в этом случае 2т. Неудобством является большое (порядка т) число шагов, необходимое для получения множества вершин, к которым ведут ребра из данной вершины.
Пример задания списка ребер (для графа на рис. 4.10):

4. Во многих случаях лучшим решением оказывается представление графа с помощью динамических списков инцидентности: каждой вершине vi ставится в соответствие список nVi вершин, смежных с v.
Пример списков инцидентности (для графа на рис.4.10):
13 EMBED Word.Picture.8 1415
Рис. 4.13.

Выбор того или иного способа задания графа зависит от конкретной решаемой задачи.
4.3. Некоторые теоремы и алгоритмы из теории
графов

Теорема 1
Графы изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга произвольными перестановками строк и столбцов.
Графы изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одинаковыми перестановками строк и столбцов.
Теорема 2
Граф является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины.
Теорема 3
Множество вершин графа является кликой тогда и только тогда, когда оно независимо в дополнительном графе G'.
Теорема 4
Эйлеров путь существует в графе тогда и только тогда, когда граф связен и имеет не более двух вершин нечетной степени (эти вершины - концы пути; если вершин нечетной степени нет, то каждый эйлеров путь является эйлеровым циклом).
Алгоритм распознавания двудольности графа (основан на приеме "поиска в ширину")
начнем с произвольной вершины и припишем ей но-мер 0;
каждой вершине из окружения данной вершины припишем номер 1;
рассмотрим теперь поочередно окружения всех вершин с номерами 1 и каждой из входящих в эти окружения вершин, еще не занумерованных, припишем номер 2;
продолжая подобным образом, занумеруем все вершины (если граф связен);
отнесем ко множеству М все вершины с четными номерами, а ко множеству К - остальные и рассмотрим порожденные подграфы G(M) и G(K); если они пусты (достаточно проверить, что все пары вершин с равными номерами не смежны), то граф - двудольный; в противном случае - нет.
Алгоритм Флери нахождения эйлерова цикла в графеначав с любой вершины и, присвоим каждому ребру (u,v) номер 1;
вычеркнем это ребро и перейдем в вершину v;
пусть в результате выполнения предыдущего шага мы присвоили некоторому ребру номер k и перешли в вершину w; выберем произвольное ребро, инцидентное этой вершине (причем, мост выберем только тогда, когда других возможностей нет); присвоим этому ребру номер Л+1 и вычеркнем его;
процесс закончится, когда все ребра графа будут вычеркнуты (т.е. занумерованы).
Алгоритм построения правильной раскраски графа произвольной вершине v припишем цвет 1;
если вершины v1 v2,..., vk раскрашены k цветами (1, 2,..., k, k<=i ), то новой произвольно взятой вершине и припишем минимальный цвет, не использованный при раскраске вершин из ее окружения.

4.4. Пример решения задачи

Задача 4.4.1. Найти все истоки и стоки заданного орграфа.
#include #include
int istok(void), int stok(void);
int a[10][10];
int j, i, k=0, n;
void main( )
{
clrecr( );
textbackground(CYAN); textcolor(RED);
cputs("Введите количество вершин графа (<10) : ");
cscanf("%d", &n); puts{“\n”);
cputs("Будем искать истоки и стоки в этом графе \n\r");
cputs("Заполните элементы матрицы инцидентности: \n\r");
textcolor(RED+BLINK);
cputs("Проверка корректности графа не производится !\n\r");
textcolor(RED);
cputs("--------------------------------------------------------------\n\r");
cputs(" a(i, j) равно : 1, если i-начало, j-конец; \n\r");
cputs(" : -1, если i-конец, j-начало; \n\r");
cputs(" : 0, если i и j не инцидентны \n\r");
cputs(" или i == j \n\r");
cputs("--------------------------------------------------------------\n\r");
for(i=l; i<=n; i++)
for(j=l;j<=n;j++)
{
cprintf(“a(%d,%d)=”, i, j);
scanf("%d", &a[i][j]);
delline();
}
getch();
textbackground(BLUE); textcolor(WHITE);
cputs("OTBET:");
for(i=1; i<=n; i++)
if(istok()) { cprintf (''\nИСТОК %d'', i); k++; }
else if(stok())
{ cprintf("\nCTOK %d", i); k++; }
if(k==0) cputs("ИСТОКОВ И СТОКОВ НЕ СУЩЕСТВУЕТ");
getch() ; }
// функция определяет является ля вершина истоком
int istok(void)
{
for(j = 1; j<=n; j++)
if (a[i][j] == -1) return 0;
return 1;
}
// функция определяет, является ля вершина стоком
int stok()
{
for (j = 1; j<=n; j++)
if (a[i][j] == 1) return 0;
return 1;
}

Задача 4.4.2. По заданной матрице смежности ADJ вершин графа найти его матрицу путей PATH (транзитивное замыкание матрицы ADJ).
Пояснения к задаче.
Пусть задан граф из N вершин и имеется его матрица смежности ADJ. Рассмотрим выражение ADJ[i][k] * ADJ[k][j]. Оно истинно тогда и только тогда, когда истинны оба входящие в него сомножителя, т.е., когда существует путь длины 2 из вершины i в вершину j (через вершину k). Аналогично, выражение
ADJ[i][l]*ADJ[l][j]+
+ADJ[i][2]*ADJ[2][j]+...+ADJ[i][N]*ADJ[N][j] (4.1) истинно тогда и только тогда, когда существует какой-нибудь путь длины 2 из i в у (через любую другую вершину).
Рассмотрим матрицу А2, у которой элементы задаются выражениями вида (4.1). Это матрица путей длины 2. В ней элемент [i][k] равен 1, если имеется путь длины 2 из вершины i в вершину k. Можно заметить, что A2=ADJ*ADJ.
Аналогично можно построить матрицу путей длины 3: АЗ=А2*АDJ. И т.д. Если необходимо узнать, существует ли какой-нибудь путь из вершины i в вершину k (путь какой угодно длины, меньшей N), то можно построить матрицу PATH, в которой элемент [i] [к] будет равен 1 в том случае, когда из вершины i можно добраться до вершины k, и 0 - если пути из i в k не существует. Такая матрица называется матрицей путей (или транзитивным замыканием матрицы ADJ). Легко видеть, что
РАТH[i][к] = ADJ[i][k] + A2[i][k] + A3[i][k]++ AN[i][k].
Отсюда становится ясно, как можно вычислить матрицу путей.
#define MEMORY (int*) calloc (N*N sizeof(int))
#include
#include
#include
// функция PROIZV ( ) для нахождения булева произведения // двух квадратных матриц
void PROIZV(int *A, int *B, int *C, int N)
{
int i, j, k, elem;
for(i=0; ifor(j=0; j{
for(elem=k=0; kif(A[i*N+k]*B[k*N+j]) elem=1;
С [i*N+j] =elem;
}
}
// функция TRANZ( ) для нахождения матрицы путей PATH
void TRANZ(int *ADJ, int *PATH, int N)
{
int *A, *C, i, j, rang;
A=MEMORY; C=MEMORY;
for(i=0;ifor(j=0; jC[i*N+j] = A[i*N+j] = PATH[i*N+j] =ADJ[i*N+j];
for(rang=l; rang {
PROIZV(A, ADJ, С, N);
for(i=0; ifor(j=0; jif (A[i*N+j] = C[i*N+j] ) PATH[i*N+j] = 1;
}
free(A); free(C);
}
// функция для ввода матрицы смежности
void vvod(int *ADJ, int N)
{
int i, j;
puts (“Введите значения элементов матрицы смежности для вершин графа:");
for(i=0; ifor(j=0; j{
if(i == j) continue;
printf ("ADJ [%d] [%d]=", i+1, j+1);
scanf("%d", ADJ+i*N+j);
}
void print (int *A, int N)
{
int i , j;
for(i=0; ifor(j=0; jprintf ("%3d", A[i*N+j]) ;
}
void main()
{
int *ADJ, *PATH, N;
clrscr() ;
puts("Сколько вершим в графе?");
scanf("%d",&N) ;
ADJ =MEMORY;
vvod (ADJ, N);
puts ("Матрица смежности:"); print (ADJ, N);
PATH = MEMORY;
TRANZ(ADJ, PATH, N);
puts("Матрица путей:"); print(PATH, N);
}
Приведенный способ нахождения матрицы путей очень неэффективен. Более хороший метод построения транзитивного замыкания дает алгоритм Уоршела.
Для его реализации определим матрицу pk таким образом: ее элемент PK[ i ][ j ] равен 1, если существует путь из i в j через вершины с номерами, не большими k. В таком случае элемент матрицы PK+1[ i ][ j ] равен 1 тогда и только тогда, когда выполнено хотя бы одно из двух условий:
а) Pk[i][j] = 1;
б) Pk[i] [k + 1] = 1 и Pk[k + 1][j] = 1.
Поэтому элемент Pk[i] [j] можно вычислить как
Pk-1[i] [j] + Pk-1W [k + 1] * Pk-1[k+1] [j].
Далее для каждого i = 0, , n - 1 очередной элемент Pk[i] [j] исчисляется следующим образом: если Pk[i][k] < > 0, то каждый
Pk[i][j]=Pk-1[i][j]+Pk-1[k][j], j = 0, N - 1.
Ясно, что P0[i] [j] = ADJ[i] [j] (так как путь из i в j, не проходящий ни через какие другие вершины, - это просто дуга между i и j). Кроме того, рn[i][j] = -раth[i][j] (так как любой путь из i в j проходит через вершины с номерами 1,2,...,N).
Функция, реализующая алгоритм Уоршела, может иметь вид
void TRANZ(int *ADJ, int *P, int N)
{
int i, j, k;
for(i=0; ifor(j=0; jP[i*N+j] = ADJ[i*N+j];
for(k=0; kfor(i=0; iif (P[i*N+k])
for(j=0; jif(P[k*N+j]) P[i*N+j] = 1;
}
Задача 4.4.3. Найти в графе все вершины, недостижимые из заданной вершины.
#define SI sizeof(int)
#include
#include
#include
int n; // число вершин графа
int *spisok; // указатель на массив номеров вершин; нулевыми
// останутся элементы, соответствующие недоступным
struct VER // вершинам

{
int kol; // сколько вершин смежно с данной
int *v; // указатель на массив номеров вершин, смежных с
}; // данной
struct VER *ver; // указатель на массив номеров вершин графа
// функция ввода информации о структуре графа
void vvod_graf ( )
{
int i, j, H, kol;
puts ("Сколько вершин у графа?");
scanf("%d", &n) ;
ver = (struct VER*) calloc(n, sizeof(struct VER) );
spisok=(int*) calloc(n, SI);
for(i=0; i{
printf("Сколько связей у вершины %d?", i+1);
scanf("%d", &ver[i].kol);
kol = ver[i].kol;
ver[i].v={int*) calloc(kol, SI);
if(kol)
{
printf("С какими вершинами связана вершина %d?\n", i+1);
or(j=0; j { scanf(“%d", &N); ver[i] .v[j]=N-l; }
}
}
}
// рекурсивная функция нахождении недостижимых вершин
// (заполняется массив spisok[ ])
void proverka (int k)
{
int i, elem;
for(i=0; i {
elem=ver[k].v[i];
if(!spisok[elem])
{ spisok[elem] = l; proverka(elem); }
}
}
void mai()
{
int i, k, flag, da;
clrscr();
vvod_graf ();
do
{
flag =1;
for(i=0; iputs("\n Kакую вершину будем рассматривать?") ;
scanf("%d", &k);
k--;
proverka(k);
for(i = 0; iif(i!=k && !spisok[i])
{ printf("%d,", i+1); flag = 0; }
if(flag) puts("Недостижимых вершин нет");
else printf("\b\n (Это вершины, недостижимые из
вершины %d)", k+1) ;
printf ("\n Будем смотреть еще одну вершину? (Y/N) ") ;
dagetche();
}
while (da == Y’ | | da == y’);
}
Можно написать не рекурсивную версию функции, заполняющей массив spisok[ ]:
void vvod_graf ( )
{
int i, j, N, kol;
puts("Сколько вершин у графа?");
scanf("%d", &n);
ver=(struct VER*) calloc(n, siceof(struct VER) );
spisok=(int*) calloc(n, SI);
for(i=0; i {
printf("Сколько связей у вершины %d? “, i+1);
scanf("%d", &kol); getchar( );
ver[i].kol=kol+1; // вершина i связана сама с собой
ver[i] .v(int*) calloc(kol+1, S1);
verti].v[0]=i;
if(kol)
{

printf("С какими вершинами связана вершина %d?\n", i+1);
for(j=l; j<=kol; j++)
{
scanf("%d", &N);
ver[i].v[j]=N-1;
}
getchar( ) ;
}
}
}
void proverka (int k)
{
int flag =1, p, i;
spisok[k]=2; // эти элементы больше не рассматриваются
// (в них уже были);
while(flag)
{
for(i=0; i{
p=ver[k] .v[i]; // номер вершины, смежной с k-ой
if (spisok[p ==1) spisok[p] =2;
else if (!spisok[p]) spisok[p]=l;
}
for(i=0; iif(spisok[i] == 1) //вершина i еще не рассматривалась
{
k=i; // теперь пойдем по вершинам, смежным с этой
goto dalee;
}
flag =0; //все вершины рассмотрены => выходим яз цикла
dalee:
}
}

4.5. Задания для самоконтроля

Задача 4.5.1. В заданном графе найти все его подграфы, которые являются обходами.
Задача 4.5.2. Известно, что заданный граф - не дерево. Выяснить, можно ли из него удалить одну вершину (вместе с инцидентными ей ребрами) так, чтобы в результате получилось дерево.
Задача 4.5.3. Подсчитать количество компонент связности в дополнении заданного графа.
Задача 4.5.4. По графу G построить граф K(G) с тем же множеством вершин, что и у G; вершины в K(G) смежны тогда и только тогда, когда расстояние между ними в G меньше или равно 2. Проверить, совпадают ли степени всех вершин в K(G), и если нет, то нельзя ли удалить из него одну вершину так, чтобы полученный граф удовлетворял этому требованию.
Задача 4.5.5. Найти диаметр графа, т.е. максимум расстояний между всевозможными парами его вершин.
Задача 4.5.6. Вершина графа называется точкой сочленения, если ее удаление приводит к увеличению числа компонент связности. Найти все точки сочленения заданного графа.
Задача 4.5.7. Найти медиану графа, т.е. такую его вершину, что сумма расстояний от нее до остальных вершин минимальна.
Задача 4.5.8. Гамаком называется подграф заданного графа с таким непустым множеством вершин А, что существует не более одной вершины в А, к которой ведут ребра от вершин вне А, и не более одной вершины вне А, к которой ведут ребра от вершин множества А. Найти количество различных гамаков в заданном графе.
Задача 4.5.9. Определить, изоморфны ли два заданных графа.

Задача 4.5.10. Определить, изоморфен ли заданный граф своему дополнению.
Задача 4.5.11. Изобразить графически заданный планарный граф так, чтобы его ребра не пересекались.
Задача 4.5.12. Пусть фиксирована нумерация вершин орграфа. Дуга называется обратной при этой нумерации, если она ведет от вершины с большим номером к вершине с меньшим номером. Построить такую нумерацию вершин заданного орграфа, при которой число обратных дуг минимально.
Задача 4.5.13. Подмножество вершин графа называется доминирующим, если каждая вершина вне его смежна хотя бы с одной вершиной этого подмножества. Найти минимальное по числу вершин доминирующее подмножество вершин заданного графа.
Задача 4.5.14. В заданном графе найти максимальный по количеству вершин полный подграф (клику).
Задача 4.5.15. Назовем треугольником графа всякую тройку различных и попарно смежных вершин этого графа. Склеиванием треугольника называется следующая операция: вершины, составляющие треугольник, удаляются из графа вместе со всеми инцидентными им ребрами; добавляется новая вершина v, a ребро (v, w) добавляется тогда и только тогда, когда вершина w была смежна хотя бы с одной вершиной удаленного треугольника. Последовательным применением операции склеивания треугольника преобразовать исходный граф в такой, в котором нет треугольников.
Задача 4.5.16. По графу G построить орграф G' таким образом: к G последовательно (пока возможно) применяется следующая операция. Если v - вершина из G с единственным предшественником и единственным преемником (u и w соответственно), то она удаляется из G вместе с дугами (u,v) , (v,w) и добавляется новая дуга (u,w).

Задача 4.5.17. Выяснить, имеется ли в заданном графе эйлеров путь или эйлеров цикл, и найти эйлеров цикл (если он есть).
Задача 4.5.18. Мостом графа называется такое ребро, удаление которого приводит к увеличению числа компонент связности графа. Найти все мосты в заданном графе.
Задача 4.5.19. Выяснить, имеется ли в заданном графе гамильтонов путь или гамильтонов цикл, и найти гамильтонов цикл (если он есть).

Задача 4.5.20. Граф называется двудольным, если множество его вершин можно разбить на два подмножества так, чтобы каждое ребро соединяло вершины из разных подмножеств. Определить, является ли заданный граф двудольным.
Задача 4.5.21. Найти правильную раскраску заданного графа.
Задача 4.5.22. В системе двусторонних дорог для каждой пары городов указать длину кратчайшего пути между ними.
Задача 4.5.23. Система двусторонних дорог называется трисвязной, если для любой четверки разных городов А, В, С, D существуют два различных пути из А в D, причем, один из них проходит через В, а другой - через С. Определить, является ли трисвязной данная система двусторонних дорог.
Задача 4.5.24. Заданная система двусторонних дорог такова, что для любой пары городов можно указать соединяющий их путь. Найти такой город, сумма расстояний от которого до остальных городов минимальна.
Задача 4.5.25. По заданной системе двусторонних дорог определить, можно ли, закрыв какие-нибудь три дороги,добиться того, чтобы из города А нельзя было попасть в город В.
Задача 4.5.26. Задана система двусторонних дорог. N-периферией называется множество городов, расстояние от которых до выделенного города (столицы) больше N. Для заданного N определить N-периферию.
Задача 4.5.27. Ломаная линия называется уникурсаль-ной, если ее можно начертить, не отрывая карандаша от бумаги и не проходя 2 раза по одному звену. Линия является уникурсальной тогда и только тогда, когда число узлов, из которых выходит нечетное число звеньев, не больше двух. По заданной матрице смежности выяснить, является ли линия уникурсальной, и если да, то получить путь обхода узлов.
Задача 4.5.28. Определить, можно ли в заданной системе односторонних дорог проехать из города А в город В таким образом, чтобы посетить город С и не проезжать никакой дороги более одного раза.
Задача 4.5.29. В системе двусторонних дорог за проезд каждой дороги взимается некоторая пошлина. Найти путь из города А в город В с минимальной величиной S+P, где S - сумма длин дорог пути, а Р - сумма пошлин проезжаемых дорог.
Задача 4.5.30. Заданы две системы двусторонних дорог с одним и тем же множеством городов (железные и шоссейные дороги). Найти минимальный по длине путь из города А в город В (путь может проходить по любому виду дорог) и места пересадок с одного вида транспорта на другой.
Задача 4.5.31. Определить станцию пересадки в московском метро, если задаются начальная и конечная станции маршрута. Итоговый путь должен отнимать минимальное время (считать, что на пересадку тратится 5 мин, а на проезд между двумя станциями 2 мин).



ЗАКЛЮЧЕНИЕ

В учебном пособии по практическим занятиям по дисциплинам «Методы программирования» и «Средства и методы программирования» рассмотрены вопросы, позволяющие студенту более углубленно изучать теоретический материал, предусмотренный учебной программой этих дисциплин и в дальнейшем самостоятельно решать практические задачи по следующей тематике:
конструирование структур данных;
сортировка и поиск данных;
конструирование динамических структур данных;
применение теории графов в программировании.








БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Кнут Д. Искусство программирования для ЭВМ. т.1,2,3, Сортировка и поиск. - М.: Мир, 2001.
Седжвик Р. Фундаментальные алгоритмы на С++.Анализ/Структуры данных/Сортировка/Поиск.: Пер. с англ. - К.: ДиаСофт, 2001.
Кормен. Т., Леверсон Ч., Ртвест Р. Алгоритмы. Построение и анализ.-М.; МЦНМО, 1999, 960 с.
Грехем Р., Кнут Д., Поиашник О. Конкретная математика.М.. Мир.,1998, 702 с.
Ахо А. , Хопкрофт ДЖ. Построение и анализ вычислительных алгоритмов. - М; Мир, 1979. - 536 с.
Мейер Б., Бодуэн К. Методы программирования. т.1, - М.; Мир, 1982г. 362с.
Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990.
Касьянов В.Н., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986.
Липский В. Комбинаторика для программистов. - М.: Мир, 1988.
Лэнгсам И. Структуры данных для персональных ЭВМ. - М.: Мир, 1976.
Рейнголд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. - М.: Мир, 1980.
Евстигнеев В.А. Применение теории графов в программировании. - М.: Наука, 1985.
Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989.
Лэнгсам И., Огснстайн М., Тснснбаум А. Структуры данных для персональных ЭВМ. - М.: Мир, 1989.
Сибуя М., Ямамото Т. Алгоритмы обработки данных.М.: Мир, 1986.


Оглавление
13 TOC \o "1-3" \h \z \u 14
13 LINK \l "_Toc325480477" 14ВВЕДЕНИЕ 13 PAGEREF _Toc325480477 \h 1431515
13 LINK \l "_Toc325480478" 141. Практическое занятие № 1. 13 PAGEREF _Toc325480478 \h 1441515
13 LINK \l "_Toc325480479" 14Конструирование структур данных 13 PAGEREF _Toc325480479 \h 1441515
13 LINK \l "_Toc325480480" 141.1. Примеры решения задач 13 PAGEREF _Toc325480480 \h 1441515
13 LINK \l "_Toc325480481" 141.2. Задания для самоконтроля 13 PAGEREF _Toc325480481 \h 1471515
13 LINK \l "_Toc325480482" 142. Практическое занятие № 2. 13 PAGEREF _Toc325480482 \h 14121515
13 LINK \l "_Toc325480483" 14Сортировка и поиск данных 13 PAGEREF _Toc325480483 \h 14121515
13 LINK \l "_Toc325480484" 142.1. Алгоритмы сортировки 13 PAGEREF _Toc325480484 \h 14121515
13 LINK \l "_Toc325480485" 142.2. Алгоритмы поиска 13 PAGEREF _Toc325480485 \h 14201515
13 LINK \l "_Toc325480486" 142.3. Примеры решения задач 13 PAGEREF _Toc325480486 \h 14211515
13 LINK \l "_Toc325480487" 142.4. Задания для самоконтроля 13 PAGEREF _Toc325480487 \h 14251515
13 LINK \l "_Toc325480488" 143. Практическое занятие № 3. 13 PAGEREF _Toc325480488 \h 14281515
13 LINK \l "_Toc325480489" 14Конструирование динамических структур данных 13 PAGEREF _Toc325480489 \h 14281515
13 LINK \l "_Toc325480490" 143.1. Общие сведения 13 PAGEREF _Toc325480490 \h 14281515
13 LINK \l "_Toc325480491" 143.2. Задания для самоконтроля 13 PAGEREF _Toc325480491 \h 14421515
13 LINK \l "_Toc325480492" 144. Практическое занятие № 4. 13 PAGEREF _Toc325480492 \h 14521515
13 LINK \l "_Toc325480493" 14Алгоритмы на графах 13 PAGEREF _Toc325480493 \h 14521515
13 LINK \l "_Toc325480494" 144.1. Некоторые основные определения 13 PAGEREF _Toc325480494 \h 14521515
13 LINK \l "_Toc325480495" 144.2. Способы машинного представления графов 13 PAGEREF _Toc325480495 \h 14551515
13 LINK \l "_Toc325480496" 144.3. Некоторые теоремы и алгоритмы из теории 13 PAGEREF _Toc325480496 \h 14581515
13 LINK \l "_Toc325480497" 14графов 13 PAGEREF _Toc325480497 \h 14581515
13 LINK \l "_Toc325480498" 144.4. Пример решения задачи 13 PAGEREF _Toc325480498 \h 14601515
13 LINK \l "_Toc325480499" 144.5. Задания для самоконтроля 13 PAGEREF _Toc325480499 \h 14691515
13 LINK \l "_Toc325480500" 14ЗАКЛЮЧЕНИЕ 13 PAGEREF _Toc325480500 \h 14731515
13 LINK \l "_Toc325480501" 14БИБЛИОГРАФИЧЕСКИЙ СПИСОК 13 PAGEREF _Toc325480501 \h 14741515
15









13PAGE 14215


13 PAGE \* MERGEFORMAT 147515



Рис. 4.1.

Рис. 4.3.

Рис. 4.2.

Рис. 4.4.

Рис. 4.5.

Рис. 4.6.

Рис. 4.8.

Рис. 4.7.

Рис. 4.9.

Рис. 4.10.

Рис. 4.11.

Рис. 4.12.



Root Entry

Приложенные файлы

  • doc 8981434
    Размер файла: 551 kB Загрузок: 0

Добавить комментарий