© К.Ю. Поляков, 2008 Указатели Динамические массивы Структуры Списки Стеки, очереди, деки Деревья Графы
Тема 1. Указатели © К.Ю. Поляков, 2008 Динамические структуры данных (язык Си)
3 Статические данные переменная (массив) имеет имя, по которому к ней можно обращаться размер заранее известен (задается при написании программы) память выделяется при объявлении размер нельзя увеличить во время работы программы int x, y = 20; float z, A[10]; char str[80];
4 Динамические данные размер заранее неизвестен, определяется во время работы программы память выделяется во время работы программы нет имени? Проблема: как обращаться к данным, если нет имени? Решение: использовать адрес в памяти Следующая проблема: в каких переменных могут храниться адреса? как работать с адресами?
5 Указатели Указатель – это переменная, в которую можно записывать адрес другой переменной (или блока памяти). Объявление: Как записать адрес: char *pC; // адрес символа // ( или элемента массива ) int *pI; // адрес целой переменной float *pF; // адрес вещественной переменной int m = 5, *pI; int A[2] = { 3, 4 }; pI = & m; // адрес переменной m pI = & A[1]; // адрес элемента массива A[1] pI = NULL; // нулевой адрес & scanf("%d", &m);
6 Обращение к данным Как работать с данными через указатель? Как работать с массивами? int m = 4, n, *pI; pI = &m; printf ("m = % d", * pI); // вывод значения n = 4*(7 - *pI); // n = 4*(7 - 4) = 12 *pI = 4*(n – m); // m = 4*(12 – 4) = 32 printf("&m = %p", pI); // вывод адреса int *pI, i, A[] = { 1, 2, 3, 4, 5, 999}; pI = A; // адрес A[0] записывается как A while ( *pI != 999 ) { // while( A[i] != 999 ) *pI += 2; // A[i] += 2; pI++; // i++ ( переход к следующему ) } * % p Оператор pI++ увеличивает адрес на sizeof(int) ! ! «вытащить» значение по адресу
7 Что надо знать об указателях указатель – это переменная, в которой можно хранить адрес другой переменной; при объявлении указателя надо указать тип переменных, на которых он будет указывать, а перед именем поставить знак * ; знак & перед именем переменной обозначает ее адрес; знак * перед указателем в рабочей части программы (не в объявлении) обозначает значение ячейки, на которую указывает указатель; для обозначения недействительного указателя используется константа NULL (нулевой указатель) ; при изменении значения указателя на n он в самом деле сдвигается к n - ому следующему числу данного типа, то есть для указателей на целые числа на n * sizeof ( integer ) байт ; указатели печатаются по формату % p. Нельзя использовать указатель, который указывает неизвестно куда ( будет сбой или зависание ) !
Тема 2. Динамические массивы © К.Ю. Поляков, 2008 Динамические структуры данных (язык Си)
9 Где нужны динамические массивы? Задача. Ввести размер массива, затем – элементы массива. Отсортировать массив и вывести на экран. Проблема: размер массива заранее неизвестен. Пути решения: выделить память «с запасом»; выделять память тогда, когда размер стал известен. Алгоритм: ввести размер массива; выделить память ; ввести элементы массива ; отсортировать и вывести на экран; удалить массив. выделить память удалить массив
10 Программа #include <stdio.h> void main() { int *A, N; printf ("Введите размер массива > "); scanf ("%d", &N); A = new int [N]; if ( A == NULL ) { printf ("Не удалось выделить память"); return; } for (i = 0; i < N; i ++ ) { printf ("\nA[%d] = ", i+1); scanf ("%d", &A[i]); } ... delete pI ; } delete A ; A = new int [N]; выделить память (С++) освободить память for (i = 0; i < N; i ++ ) { printf ("\nA[%d] = ", i+1); scanf ("%d", &A[i]); } работаем так же, как с обычным массивом! if ( A == NULL ) { printf ("Не удалось выделить память"); return; } проверка
11 Динамические массивы для выделения памяти в языке Си используются функции malloc и calloc ; в языке C++ удобнее использовать оператор new ; указатель = new тип [ размер ]; результат работы оператора new – адрес выделенного блока памяти, который нужно сохранить в указателе; если оператор new вернул нулевой указатель ( NULL ), память выделить не удалось; с динамическим массивом можно работать так же, как и с обычным (статическим); для освобождения блока памяти нужно применить оператор delete : delete указатель ;
12 Ошибки при работе с памятью Запись в «чужую» область памяти: память не была выделена, а массив используется. Что делать : проверять указатель на NULL. Выход за границы массива: обращение к элементу массива с неправильным номером, при записи портятся данные в «чужой» памяти. Что делать : если позволяет транслятор, включать проверку выхода за границы массива. Указатель удален второй раз: структура памяти нарушена, может быть все, что угодно. Что делать : в удаленный указатель лучше записывать NULL, ошибка выявится быстрее. Утечка памяти: ненужная память не освобождается. Что делать : убирайте «мусор».
13 Динамические матрицы Задача. Ввести размеры матрицы и выделить для нее место в памяти во время работы программы. Проблема: размеры матрицы заранее неизвестны. Пути решения: выделять отдельный блок памяти для каждой строки; выделить память сразу на всю матрицу.
14 Вариант 1. Свой блок – каждой строке Адрес матрицы: матрица = массив строк адрес матрицы = адрес массива, где хранятся адреса строк адрес строки = указатель адрес матрицы = адрес массива указателей A int **A; typedef int *pInt; pInt *A; или через объявление нового типа данных pInt = указатель на int Объявление динамической матрицы: A[M][0]... A[M][N] A[ 0 ][0]... A[ 0 ][N] A[0] A[1] A[M] . . .
15 Вариант 1. Свой блок – каждой строке typedef int *pInt; void main() { int M, N, i; pInt *A; ... A = new pInt[M]; for ( i = 0; i < M; i ++ ) A[i] = new int[N]; ... for ( i = 0; i < M; i ++ ) delete A[i]; delete A; } A = new pInt[M]; for ( i = 0; i < M; i ++ ) A[i] = new int[N]; for ( i = 0; i < M; i ++ ) delete A[i]; delete A; // ввод M и N // работаем с матрицей A, как обычно выделяем массив указателей выделяем массив под каждую строку освобождаем память для строк освобождаем массив адресов строк
16 Вариант 2. Один блок на матрицу A Выделение памяти: A[0]... A[M] A[ 0 ][0] … A[1][0] … A[2][0]... A[M][N] Освобождение памяти: A = new pInt[M]; A[0] = new int [M*N]; delete A[0]; delete A; Можно ли поменять строки местами? ? Расстановка указателей: for ( i = 1; i < N; i ++ ) A[i] = A[i-1] + N;
Тема 3. Структуры © К.Ю. Поляков, 2008 Динамические структуры данных (язык Си)
18 Структуры Структура – это тип данных, который может включать в себя несколько полей – элементов разных типов (в том числе и другие структуры). Свойства : автор ( строка ) название ( строка ) год издания ( целое число ) количество страниц ( целое число ) Задача : объединить эти данные в единое целое struct Book { char author [40]; // автор, символьная строка char title [80]; // название, символьная строка int year ; // год издания, целое число int pages ; // количество страниц, целое число }; Как ввести новый тип данных-структур? Память не выделяется! ! структура название поля
19 Как работать со структурами? Объявление: Book b; // здесь выделяется память! Book b1 = { "А.С. Пушкин", "Полтава", 1998, 2 23 }; Заполнение полей: strcpy ( b.author, "А.С. Пушкин " ); strcpy ( b.title, "Полтава " ); b.year = 1998 ; b.pages = 2 23 ; Для обращения к полю структуры используется точка! ! Ввод полей с клавиатуры: printf ( "Автор " ); gets ( b.author ); printf ( "Название книги " ); gets ( b.title ); printf ( "Год издания, кол-во страниц " ); scanf ( "%d%d", &b.year, &b.pages );
20 Копирование структур По элементам: Book b 1, b2; ... // здесь вводим b1 strcpy ( b2.author, b1.author ); strcpy ( b2.title, b1.title ); b2.year = b1.year; b2.pages = b1.pages; Задача : скопировать структуру b1 в b2. Копирование «бит в бит»: #include <mem.h> ... memcpy ( &b2, &b1, sizeof(Book) ); или просто так: b2 = b1; куда откуда сколько байт Первые два параметра – адреса структур! !
21 Массивы структур Объявление: Book B[10]; Обращение к полям: for ( i = 0; i < 10; i ++ ) B[i].year = 2008; B[0]... B[9] author title year pages Запись в двоичный файл: Чтение из двоичного файла: FILE *f; f = fopen("input.dat", "wb" ); fwrite ( B, sizeof(Book), 10, f ); f = fopen("input.dat", "rb" ); n = fread ( B, sizeof(Book), 10, f ); printf ( " Прочитано %d структур ", n ); адрес массива размер блока сколько блоков указатель на файл fread возвращает число удачно прочитанных блоков! ! Book write binary
22 Пример программы Задача : в файле books.dat записаны данные о книгах в виде массива структур типа Book ( не более 100 ). Установить для всех 200 8 год издания и записать обратно в тот же файл. #include <stdio.h> struct Book { … }; void main() { Book B [100]; int i, n; FILE *f; f = fopen ( "books.dat ", "rb" ); n = fread ( B, sizeof(Book), 100, f ); fclose(f); for ( i = 0; i < n; i ++ ) B [i].year = 200 8 ; fp = fopen("books.dat ", "wb" ); fwrite ( B, sizeof(Book), n, f ); fclose ( f ); } struct Book { … }; f = fopen ( "books.dat ", "rb" ); n = fread ( B, sizeof(Book), 100, f ); fclose ( f ); fp = fopen("books.dat ", "wb" ); fwrite ( B, sizeof(Book), n, f ); fclose ( f ); полное описание структуры чтение массива ( ≤ 100 структур), размер записывается в переменную n запись массива ( n структур)
23 Выделение памяти под структуру Book *p; p = new Book; printf ( "Автор " ); gets ( p->author ); printf ( "Название книги " ); gets ( p->title ); printf ( " Количество страниц " ); scanf ( "%d", &p->pages ); p->year = 2008; ... delete p; Для обращения к полю структуры по адресу используется стрелка -> ! ! p = new Book; выделить память под структуру, записать ее адрес в переменную p p->author delete p; освободить память
24 Динамические массивы структур Book *B; int n; printf ( "Сколько у вас книг? " ); scanf ( "%d", &n ); B = new Book[n]; ... // здесь заполняем массив B for ( i = 0; i < n; i++ ) printf ( "%s. %s. %d.\n", B[i].author, B[i].title, B[i].year); delete B; Задача : выделить память под массив структур во время выполнения программы. B = new Book[n]; Book *B; delete B; в этот указатель будет записан адрес массива выделяем память освобождаем память
25 Сортировка массива структур Ключ (ключевое поле) – это поле, по которому сортируются структуры. Проблема: как избежать копирования структур при сортировке? Решение: использовать вспомогательный массив указателей, при сортировке переставлять указатели. 5 1 3 2 4 5 1 3 2 4 p[0] p[1] p[2] p[3] p[4] p[ 4 ] p[ 0 ] p[ 2 ] p[ 1 ] p[ 3 ] До сортировки: После сортировки: Вывод результата: for ( i = 0; i < 5 ; i ++ ) printf("%d %s", p[i]->year, p[i]->title); p[i] p[i]
26 Реализация в программе const N = 10; Book B[N]; Book *p[N], * temp; int i, j; ... // здесь заполняем структуры for ( i = 0; i < N; i++ ) p[i] = &B[i]; for ( i = 0; i < n-1; i++ ) for ( j = n-2; j >= i; j-- ) if ( p[j+1]->year < p[j]->year ) { temp = p[j]; p[j] = p[j+1]; p [ j +1] = temp ; } for ( i = 0; i < 5 ; i ++ ) printf("%d %s", p[i]->year, p[i]->title); Book *p[N], * temp; for ( i = 0; i < N; i++ ) p[i] = &B[i]; for ( i = 0; i < n-1; i++ ) for ( j = n-2; j >= i; j-- ) if ( p[j+1]->year < p[j]->year ) { temp = p[j]; p[j] = p[j+1]; p [ j +1] = temp ; } вспомогательные указатели начальная расстановка указателей сортировка методом пузырька, меняем только указатели, сами структуры остаются на местах
Тема 4. Списки © К.Ю. Поляков, 2008 Динамические структуры данных (язык Си)
28 Динамические структуры данных Строение: набор узлов, объединенных с помощью ссылок. Как устроен узел : данные ссылки на другие узлы Типы структур : списки деревья графы NULL NULL NULL односвязный двунаправленный (двусвязный) циклические списки (кольца) NULL NULL NULL NULL NULL NULL
29 Когда нужны списки? Задача (алфавитно-частотный словарь). В файле записан текст. Нужно записать в другой файл в столбик все слова, встречающиеся в тексте, в алфавитном порядке, и количество повторений для каждого слова. Проблемы : количество слов заранее неизвестно (статический массив); количество слов определяется только в конце работы (динамический массив). Решение – список. Алгоритм : создать список; если слова в файле закончились, то стоп. прочитать слово и искать его в списке; если слово найдено – увеличить счетчик повторений, иначе добавить слово в список; перейти к шагу 2.
30 Что такое список: пустая структура – это список; список – это начальный узел ( голова ) и связанный с ним список. Списки: новые типы данных Структура узла : struct Node { char word[40]; // слово int count; // счетчик повторений Node *next; // ссылка на следующий элемент }; typedef Node *PNode; Указатель на эту структуру : Адрес начала списка : PNode Head = NULL; Рекурсивное определение! ! NULL Для доступа к списку достаточно знать адрес его головы! !
31 Что нужно уметь делать со списком? Создать новый узел. Добавить узел: в начало списка; в конец списка; после заданного узла; до заданного узла. Искать нужный узел в списке. Удалить узел.
32 Создание узла PNode CreateNode ( char NewWord[] ) { PNode NewNode = new Node; strcpy(NewNode->word, NewWord); NewNode->count = 1; NewNode->next = NULL; return NewNode; } Функция CreateNode ( создать узел ): вход: новое слово, прочитанное из файла; выход: адрес нового узла, созданного в памяти. возвращает адрес созданного узла новое слово Если память выделить не удалось? ?
33 Добавление узла в начало списка NewNode Head NULL 1) Установить ссылку нового узла на голову списка: NewNode->next = Head; NewNode Head NULL NULL 2 ) Установить новый узел как голову списка: Head = NewNode ; void AddFirst (PNode & Head, PNode NewNode) { NewNode->next = Head; Head = NewNode; } & адрес головы меняется
34 Добавление узла после заданного 1) Установить ссылку нового узла на узел, следующий за p : NewNode->next = p->next ; 2 ) Установить ссылку узла p на новый узел: p->next = NewNode ; NewNode p NULL NULL NewNode p NULL void AddAfter (PNode p, PNode NewNode) { NewNode->next = p->next; p->next = NewNode; }
35 Задача: сделать что-нибудь хорошее с каждым элементом списка. Алгоритм: установить вспомогательный указатель q на голову списка; если указатель q равен NULL (дошли до конца списка), то стоп; выполнить действие над узлом с адресом q ; перейти к следующему узлу, q->next. Проход по списку ... PNode q = Head; // начали с головы while ( q != NULL ) { // пока не дошли до конца ... // делаем что-то хорошее с q q = q->next; // переходим к следующему узлу } ... Head NULL q
36 Добавление узла в конец списка Задача: добавить новый узел в конец списка. Алгоритм: найти последний узел q, такой что q->next равен NULL ; добавить узел после узла с адресом q ( процедура AddAfter ). Особый случай: добавление в пустой список. void AddLast ( PNode &Head, PNode NewNode ) { PNode q = Head; if ( Head == NULL ) { AddFirst( Head, NewNode ); return; } while ( q->next ) q = q->next; AddAfter ( q, NewNode ); } особый случай – добавление в пустой список ищем последний узел добавить узел после узла q
37 Проблема: нужно знать адрес предыдущего узла, а идти назад нельзя! Решение: найти предыдущий узел q (проход с начала списка). Добавление узла перед заданным NewNode p NULL NULL void AddBefore ( PNode & Head, PNode p, PNode NewNode ) { PNode q = Head; if ( Head == p ) { AddFirst ( Head, NewNode ); return; } while ( q && q->next != p ) q = q->next; if ( q ) AddAfter(q, NewNode); } особый случай – добавление в начало списка ищем узел, следующий за которым – узел p добавить узел после узла q Что плохо? ?
38 Добавление узла перед заданным ( II ) Задача: вставить узел перед заданным без поиска предыдущего. Алгоритм: поменять местами данные нового узла и узла p ; установить ссылку узла p на NewNode. void AddBefore2 ( PNode p, PNode NewNode ) { Node temp; temp = *p; *p = * NewNode ; * NewNode = temp; p->next = NewNode ; } NewNode p NULL Так нельзя, если p = NULL или адреса узлов где-то еще запоминаются! ! NewNode p NULL NULL
39 Поиск слова в списке Задача: найти в списке заданное слово или определить, что его нет. Функция Find : вход : слово (символьная строка); выход : адрес узла, содержащего это слово или NULL. Алгоритм: проход по списку. PNode Find ( PNode Head, char NewWord[] ) { PNode q = Head; while (q && strcmp(q->word, NewWord)) q = q->next; return q ; } ищем это слово результат – адрес узла while ( q && strcmp ( q->word, NewWord) ) q = q->next; пока не дошли до конца списка и слово не равно заданному
40 Куда вставить новое слово? Задача: найти узел, перед которым нужно вставить, заданное слово, так чтобы в списке сохранился алфавитный порядок слов. Функция FindPlace : вход : слово (символьная строка); выход : адрес узла, перед которым нужно вставить это слово или NULL, если слово нужно вставить в конец списка. PNode FindPlace ( PNode Head, char NewWord[] ) { PNode q = Head; while ( q && strcmp(NewWord, q->word) > 0 ) q = q->next; return q ; } > 0 слово NewWord стоит по алфавиту до q->word
41 Удаление узла void DeleteNode ( PNode &Head, PNode p ) { PNode q = Head; if ( Head == p ) Head = p->next; else { while ( q && q->next != p ) q = q->next; if ( q == NULL ) return; q->next = p->next; } delete p; } while ( q && q->next != p ) q = q->next; if ( Head == p ) Head = p->next; q Head p NULL Проблема: нужно знать адрес предыдущего узла q. особый случай: удаляем первый узел ищем предыдущий узел, такой что q->next == p delete p; освобождение памяти
42 Алфавитно-частотный словарь Алгоритм: открыть файл на чтение; прочитать слово: если файл закончился ( n !=1 ), то перейти к шагу 7; если слово найдено, увеличить счетчик (поле count ); если слова нет в списке, то создать новый узел, заполнить поля ( CreateNode ) ; найти узел, перед которым нужно вставить слово ( FindPlace ); добавить узел ( AddBefore ); перейти к шагу 2; вывести список слов, используя проход по списку. char word[80]; ... n = fscanf ( in, "%s", word ); FILE *in; in = fopen ( "input.dat", "r" ); read, чтение вводится только одно слово ( до пробела)!
43 Двусвязные списки Структура узла : struct Node { char word[40]; // слово int count; // счетчик повторений Node *next; // ссылка на следующий элемент Node *prev; // ссылка на предыдущий элемент }; typedef Node *PNode; Указатель на эту структуру : Адреса «головы» и «хвоста» : PNode Head = NULL; PNode Tail = NULL; next prev previous можно двигаться в обе стороны нужно правильно работать с двумя указателями вместо одного NULL NULL Head Tail
44 Задания «4»: «Собрать» из этих функций программу для построения алфавитно-частотного словаря. В конце файла вывести общее количество разных слов (количество элементов списка). «5»: То же самое, но использовать двусвязные списки. «6»: То же самое, что и на «5», но вывести список слов в порядке убывания частоты, то есть, сначала те слова, которые встречаются чаще всего.
Тема 5. Стеки, очереди, деки © К.Ю. Поляков, 2008 Динамические структуры данных (язык Си)
46 Стек Стек – это линейная структура данных, в которой добавление и удаление элементов возможно только с одного конца ( вершины стека ). Stack = кипа, куча, стопка (англ.) LIFO = Last In – First Out «Кто последним вошел, тот первым вышел». Операции со стеком: добавить элемент на вершину ( Push = втолкнуть) ; снять элемент с вершины ( Pop = вылететь со звуком ).
47 Пример задачи Задача: вводится символьная строка, в которой записано выражение со скобками трех типов: [], {} и (). Определить, верно ли расставлены скобки (не обращая внимания на остальные символы). Примеры: [()]{} ][ [({)]} Упрощенная задача: то же самое, но с одним видом скобок. Решение : счетчик вложенности скобок. Последовательность правильная, если в конце счетчик равен нулю и при проходе не разу не становился отрицательным. Можно ли решить исходную задачу так же, но с тремя счетчиками? ? [ ( { ) ] } ( : 0 1 0 [: 0 1 0 {: 0 1 0 [ ( { ) ] } ( ( ) ) ( ) 1 2 1 0 1 0 ( ( ) ) ( ) ( ( ) ) ) ( 1 2 1 0 -1 0 ( ( ) ) ) ( ( ( ) ) ( 1 2 1 0 1 ( ( ) ) (
48 Решение задачи со скобками Алгоритм: в начале стек пуст; в цикле просматриваем все символы строки по порядку; если очередной символ – открывающая скобка, заносим ее на вершину стека; если символ – закрывающая скобка, проверяем вершину стека: там должна быть соответствующая открывающая скобка (если это не так, то ошибка); если в конце стек не пуст, выражение неправильное. [ ( ( ) ) ] { } [ [ ( [ ( ( [ ( ( [ ( [ { {
49 Реализация стека (массив) Структура-стек: const MAXSIZE = 100; struct Stack { char data[MAXSIZE]; // стек на 100 символов int size; // число элементов }; Добавление элемента: int Push ( Stack &S, char x ) { if ( S.size == MAXSIZE ) return 0 ; S.data[S.size] = x; S.size ++; return 1; } ошибка: переполнение стека добавить элемент нет ошибки
50 Реализация стека (массив) char Pop ( Stack &S ) { if ( S.size == 0 ) return char(255); S.size --; return S.data[S.size]; } Снятие элемента с вершины: Пусто й или нет? int isEmpty ( Stack &S ) { if ( S.size == 0 ) return 1; else return 0; } ошибка: стек пуст int isEmpty ( Stack &S ) { return (S.size == 0); }
51 Программа void main() { char br1[3] = { '(', '[', '{' }; char br2[3] = { ')', ']', '}' }; char s[80], upper; int i, k, error = 0; Stack S; S.size = 0; printf("Введите выражение со скобками > "); gets ( s ); ... // здесь будет основной цикл обработки if ( ! error && (S.size == 0) ) printf("\nВыpажение пpавильное\n"); else printf("\nВыpажение непpавильное\n"); } открывающие скобки закрывающие скобки то, что сняли со стека признак ошибки
52 Обработка строки (основной цикл) for ( i = 0; i < strlen(s); i++ ) { for ( k = 0; k < 3; k++ ) { if ( s[i] == br1[k] ) // если открывающая скобка { Push ( S, s[i] ); // втолкнуть в стек break; } if ( s[i] == br2[k] ) // если закрывающая скобка { upper = Pop ( S ); // снять верхний элемент if ( upper != br1[k] ) error = 1; break; } } if ( error ) break; } цикл по всем символам строки s цикл по всем видам скобок ошибка: стек пуст или не та скобка была ошибка: дальше нет смысла проверять
53 Реализация стека (список) Добавление элемента: Структура узла: struct Node { char data; Node *next; }; typedef Node *PNode; void Push (PNode &Head, char x) { PNode NewNode = new Node; NewNode->data = x; NewNode->next = Head; Head = NewNode; }
54 Реализация стека (список) Снятие элемента с вершины: char Pop (PNode &Head) { char x; PNode q = Head; if ( Head == NULL ) return char(255); x = Head->data; Head = Head->next; delete q; return x; } Изменения в основной программе: Stack S; S.size = 0; ... if ( ! error && (S.size == 0) ) printf("\nВыpажение пpавильное\n"); else printf("\nВыpажение непpавильное \n"); PNode S = NULL; ( S = = NULL ) стек пуст
55 Вычисление арифметических выражений a b + c d + 1 - / Как вычислять автоматически: Инфиксная запись (знак операции между операндами) (a + b) / ( c + d – 1) необходимы скобки! Постфиксная запись (знак операции после операндов) польская нотация, Jan Łukasiewicz (1920) скобки не нужны, можно однозначно вычислить! Префиксная запись (знак операции до операндов) / + a b - + c d 1 обратная польская нотация, F. L. Bauer and E. W. Dijkstra a + b a + b c + d c + d c + d - 1 c + d - 1
56 Запишите в постфиксной форме (32*6-5)*(2*3+4) /(3+7*2) (2* 4+3* 5)*(2*3+ 18/3*2 ) *(12-3) (4-2 * 3)*(3- 1 2 /3/4 ) *(24-3*12)
57 Вычисление выражений Постфиксная форма: a b + c d + 1 - / Алгоритм: взять очередной элемент; если это не знак операции, добавить его в стек; если это знак операции, то взять из стека два операнда; выполнить операцию и записать результат в стек; перейти к шагу 1. a b a a+b c a+b d c a+b c+d a+b 1 c+d a+b c+d-1 a+b X X =
58 Системный стек ( Windows – 1 Мб ) Используется для размещения локальных переменных ; хранения адресов возврата (по которым переходит программа после выполнения функции или процедуры); передачи параметров в функции и процедуры; временного хранения данных (в программах на языке Ассмеблер ). Переполнение стека ( stack overflow ): слишком много локальных переменных ( выход – использовать динамические массивы) ; очень много рекурсивных вызовов функций и процедур ( выход – переделать алгоритм так, чтобы уменьшить глубину рекурсии или отказаться от нее вообще).
59 Очередь 1 2 3 4 5 6 Очередь – это линейная структура данных, в которой добавление элементов возможно только с одного конца ( конца очереди ), а удаление элементов – только с другого конца ( начала очереди ). FIFO = First In – First Out «Кто первым вошел, тот первым вышел». Операции с очередью: добавить элемент в конец очереди ( PushTail = втолкнуть в конец) ; удалить элемент с начала очереди ( Pop ).
60 Реализация очереди (массив) 1 1 2 1 2 3 1 2 3 самый простой способ нужно заранее выделить массив; при выборке из очереди нужно сдвигать все элементы.
61 Реализация очереди (кольцевой массив) 1 2 Head Tail 1 2 3 2 3 2 3 4 3 4 Сколько элементов можно хранить в такой очереди? ? Как различить состояния «очередь пуста» и «очередь полна»? ? 3 4 5
62 Реализация очереди (кольцевой массив) 1 Head Tail В очереди 1 элемент: Очередь пуста: Очередь полна: Head = = Tail + 1 Head = = ( Tail + 1) % N 0 N-1 размер массива 1 2 3 Head = = Tail + 2 Head = = ( Tail + 2) % N 0 N-1 1 2 3 Head = = Tail
63 Реализация очереди (кольцевой массив) const MAXSIZE = 100; struct Queue { int data[MAXSIZE]; int head, tail; }; Структура данных: Добавление в очередь: int PushTail ( Queue &Q, int x ) { if ( Q.head == (Q.tail+2) % MAXSIZE ) return 0; Q.tail = (Q.tail + 1) % MAXSIZE; Q.data[Q.tail] = x; return 1; } замкнуть в кольцо % MAXSIZE очередь полна, не добавить удачно добавили
64 Реализация очереди (кольцевой массив) Выборка из очереди: int Pop ( Queue &Q ) { int temp; if ( Q.head == (Q.tail + 1) % MAXSIZE ) return 32767; temp = Q.data[Q.head]; Q.head = (Q.head + 1) % MAXSIZE; return temp; } очередь пуста взять первый элемент удалить его из очереди
65 Реализация очереди (списки) struct Node { int data; Node *next; }; typedef Node *PNode; struct Queue { PNode Head, Tail; }; Структура узла: Тип данных «очередь»:
66 Реализация очереди (списки) void PushTail ( Queue &Q, int x ) { PNode NewNode; NewNode = new Node; NewNode->data = x; NewNode->next = NULL; if ( Q.Tail ) Q.Tail->next = NewNode; Q.Tail = NewNode; if ( Q.Head == NULL ) Q.Head = Q.Tail; } Добавление элемента: создаем новый узел если в списке уже что-то было, добавляем в конец если в списке ничего не было, …
67 Реализация очереди (списки) int Pop ( Queue &Q ) { PNode top = Q.Head; int x; if ( top == NULL ) return 32767; x = top->data; Q.Head = top->next; if ( Q.Head == NULL ) Q.Tail = NULL; delete top; return x; } Выборка элемента: если список пуст, … запомнили первый элемент если в списке ничего не осталось, … освободить память
68 Дек Дек ( deque = d ouble e nded que ue, очередь с двумя концами) – это линейная структура данных, в которой добавление и удаление элементов возможно с обоих концов. 1 2 3 4 5 6 Операции с деком: добавление элемента в начало ( Push ); удаление элемента с начала ( Pop ) ; добавление элемента в конец (PushTail) ; удаление элемента с конца (PopTail). Реализация: кольцевой массив ; двусвязный список.
69 Задания «4»: В файле input.dat находится список чисел (или слов). Переписать его в файл output.dat в обратном порядке. «5»: Составить программу, которая вычисляет значение арифметического выражения, записанного в постфиксной форме, с помощью стека. Выражение правильное, допускаются только однозначные числа и знаки +, -, *, /. «6»: То же самое, что и на «5», но допускаются многозначные числа.
Тема 6. Деревья © К.Ю. Поляков, 2008 Динамические структуры данных (язык Си)
71 Деревья директор гл. инженер гл. бухгалтер инженер инженер инженер бухгалтер бухгалтер бухгалтер Что общего во всех примерах? ?
72 Деревья Дерево – это структура данных, состоящая из узлов и соединяющих их направленных ребер (дуг), причем в каждый узел (кроме корневого) ведет ровно одна дуга. Корень – это начальный узел дерева. Лист – это узел, из которого не выходит ни одной дуги. корень 2 8 5 6 9 1 3 4 10 7 Какие структуры – не деревья? 4 1 3 2 5 2 4 6 1 3 5 3 2 1 3 2 1 4
73 Деревья Предок узла x – это узел, из которого существует путь по стрелкам в узел x. Потомок узла x – это узел, в который существует путь по стрелкам из узла x. Родитель узла x – это узел, из которого существует дуга непосредственно в узел x. С помощью деревьев изображаются отношения подчиненности (иерархия, «старший – младший», «родитель – ребенок»). ! 2 4 6 1 3 5 Сын узла x – это узел, в который существует дуга непосредственно из узла x. Брат узла x ( sibling ) – это узел, у которого тот же родитель, что и у узла x. Высота дерева – это наибольшее расстояние от корня до листа (количество дуг).
74 Дерево – рекурсивная структура данных Рекурсивное определение: Пустая структура – это дерево. Дерево – это корень и несколько связанных с ним деревьев. 2 4 6 1 3 5 Двоичное (бинарное) дерево – это дерево, в котором каждый узел имеет не более двух сыновей. Пустая структура – это двоичное дерево. Двоичное дерево – это корень и два связанных с ним двоичных дерева (левое и правое поддеревья).
75 Двоичные деревья Структура узла: struct Node { int data ; // полезные данные Node *left, *right; // ссылки на левого // и правого сыновей }; typedef Node *PNode; Применение: поиск данных в специально построенных деревьях (базы данных); сортировка данных; вычисление арифметических выражений; кодирование (метод Хаффмана).
76 Двоичные деревья поиска 16 45 30 76 12 5 98 59 Какая закономерность? ? Слева от каждого узла находятся узлы с меньшими ключами, а справа – с б ó льшими. Ключ – это характеристика узла, по которой выполняется поиск (чаще всего – одно из полей структуры). Как искать ключ, равный x : если дерево пустое, ключ не найден; если ключ узла равен x, то стоп. если ключ узла меньше x, то искать x в левом поддереве; если ключ узла больше x, то искать x в правом поддереве. Сведение задачи к такой же задаче меньшей размерности – это …? ?
77 Двоичные деревья поиска 16 45 30 76 12 5 98 59 Поиск в массиве ( N элементов): 16 45 30 76 12 5 98 59 При каждом сравнении отбрасывается 1 элемент. Число сравнений – N. Поиск по дереву ( N элементов): При каждом сравнении отбрасывается половина оставшихся элементов. Число сравнений ~ log 2 N. быстрый поиск нужно заранее построить дерево; желательно, чтобы дерево было минимальной высоты.
78 Реализация алгоритма поиска // --------------------------------------- // Функция Search – поиск по дереву // Вход: Tree - адрес корня, // x - что ищем // Выход: адрес узла или NULL ( не нашли ) // --------------------------------------- PNode Search (PNode Tree, int x) { if ( ! Tree ) return NULL; if ( x == Tree->data ) return Tree; if ( x < Tree->data ) return Search(Tree->left, x); else return Search ( Tree->right, x); } дерево пустое: ключ не нашли… нашли, возвращаем адрес корня искать в левом поддереве искать в правом поддереве
79 Как построить дерево поиска? // --------------------------------------------- // Функция AddToTree – добавить элемент к дереву // Вход: Tree - адрес корня, // x - что добавляем // ---------------------------------------------- void AddToTree (PNode &Tree, int x) { if ( ! Tree ) { Tree = new Node; Tree->data = x; Tree->left = NULL; Tree->right = NULL; return; } if ( x < Tree->data ) AddToTree ( Tree->left, x ); else AddToTree ( Tree->right, x ); } дерево пустое: создаем новый узел (корень) адрес корня может измениться добавляем к левому или правому поддереву Минимальная высота не гарантируется! !
80 Обход дерева 16 45 30 76 12 5 98 59 Обход дерева – это перечисление всех узлов в определенном порядке. Обход ЛКП («левый – корень – правый»): 125 98 76 45 59 30 16 Обход ПКЛ («правый – корень – левый»): 16 30 45 76 59 98 125 Обход КЛП («корень – левый – правый»): 125 76 98 16 45 30 59 Обход ЛПК («левый – правый – корень»): 59 98 125 30 76 45 16
81 Обход дерева – реализация // --------------------------------------------- // Функция LKP – обход дерева в порядке ЛКП // ( левый – корень – правый ) // Вход: Tree - адрес корня // ---------------------------------------------- void LKP( PNode Tree ) { if ( ! Tree ) return; LKP ( Tree->left ); printf ( "%d ", Tree->data ); LKP ( Tree->right ); } обход этой ветки закончен обход левого поддерева вывод данных корня обход правого поддерева Для рекурсивной структуры удобно применять рекурсивную обработку! !
82 Разбор арифметических выражений a b + + 1 - / c d a b + c d + 1 - / Как вычислять автоматически: Инфиксная запись, обход ЛКП (знак операции между операндами) (a + b) / ( c + d – 1) необходимы скобки! Постфиксная запись, ЛПК (знак операции после операндов) a + b / c + d – 1 польская нотация, Jan Łukasiewicz (1920) скобки не нужны, можно однозначно вычислить! Префиксная запись, КЛП (знак операции до операндов) / + a b - + c d 1 обратная польская нотация, F. L. Bauer and E. W. Dijkstra
83 Вычисление выражений Постфиксная форма: a b + c d + 1 - / Алгоритм: взять очередной элемент; если это не знак операции, добавить его в стек; если это знак операции, то взять из стека два операнда; выполнить операцию и записать результат в стек; перейти к шагу 1. a b a a+b c a+b d c a+b c+d a+b 1 c+d a+b c+d-1 a+b X X =
84 Вычисление выражений Задача: в символьной строке записано правильное арифметическое выражение, которое может содержать только однозначные числа и знаки операций +-*\. Вычислить это выражение. Алгоритм: ввести строку; построить дерево; вычислить выражение по дереву. Ограничения: ошибки не обрабатываем; многозначные числа не разрешены; дробные числа не разрешены; скобки не разрешены.
85 Построение дерева Алгоритм: если first=last (остался один символ – число), то создать новый узел и записать в него этот элемент; иначе... среди элементов от first до last включительно найти последнюю операцию (элемент с номером k ); создать новый узел (корень) и записать в него знак операции ; рекурсивно применить этот алгоритм два раза: построить левое поддерево, разобрав выражение из элементов массива с номерами от first до k-1 ; построить правое поддерево, разобрав выражение из элементов массива с номерами от k+1 до last. 5 + 7 * 6 - 3 * 2 first last k k +1 k -1
86 Как найти последнюю операцию? Порядок выполнения операций умножение и деление; сложение и вычитание. 5 + 7 * 6 - 3 * 2 Нужно искать последнюю операцию с наименьшим приоритетом! ! Приоритет (старшинство) – число, определяющее последовательность выполнения операций: раньше выполняются операции с большим приоритетом: умножение и деление (приоритет 2 ); сложение и вычитание (приоритет 1 ).
87 Приоритет операции //------------------------------------ -------- // Функция Priority – приоритет операции // Вход: символ операции // Выход: приоритет или 100, если не операция //------------------------------------ -------- int Priority ( char c ) { switch ( c ) { case '+': case '-': return 1; case '*': case '/': return 2; } return 100; } сложение и вычитание: приоритет 1 умножение и деление: приоритет 2 это вообще не операция
88 Номер последней операции //------------------------------------ -------- // Функция LastOperation – номер последней операции // Вход: строка, номера первого и последнего // символов рассматриваемой части // Выход: номер символа - последней операции //------------------------------------ -------- int LastOperation ( char Expr[], int first, int last ) { int MinPrt, i, k, prt; MinPrt = 100; for( i = first; i <= last; i++ ) { prt = Priority ( Expr[i] ); if ( prt <= MinPrt ) { MinPrt = prt; k = i; } } return k; } проверяем все символы вернуть номер символа нашли операцию с минимальным приоритетом
89 Построение дерева Структура узла struct Node { char data; Node *left, *right; }; typedef Node *PNode; Создание узла для числа (без потомков) PNode NumberNode ( char c ) { PNode Tree = new Node; Tree->data = c; Tree->left = NULL; Tree->right = NULL; return Tree; } возвращает адрес созданного узла один символ, число
90 Построение дерева //------------------------------------ -------- // Функция MakeTree – построение дерева // Вход: строка, номера первого и последнего // символов рассматриваемой части // Выход: адрес построенного дерева //------------------------------------ -------- PNode MakeTree ( char Expr [], int first, int last ) { PNode Tree; int k; if ( first == last ) return NumberNode ( Expr [first] ) ; k = LastOperation ( Expr, first, last ); Tree = new Node; Tree->data = Expr[k]; Tree->left = MakeTree ( Expr, first, k-1 ); Tree->right = MakeTree ( Expr, k+1, last ); return Tree; } осталось только число новый узел: операция
91 Вычисление выражения по дереву //------------------------------------ -------- // Функция CalcTree – вычисление по дереву // Вход: адрес дерева // Выход: значение выражения //------------------------------------ -------- int CalcTree (PNode Tree) { int num1, num2; if ( ! Tree->left ) return Tree->data - '0'; num1 = CalcTree( Tree->left); num2 = CalcTree(Tree->right); switch ( Tree->data ) { case '+': return num1+num2; case '-': return num1-num2; case '*': return num1*num2; case '/': return num1/num2; } return 32767; } вернуть число, если это лист вычисляем операнды (поддеревья) выполняем операцию некорректная операция
92 Основная программа //------------------------------------ -------- // Основная программа: ввод и вычисление // выражения с помощью дерева //------------------------------------ -------- void main() { char s[80]; PNode Tree; printf ( " Введите выражение > " ); gets(s); Tree = MakeTree ( s, 0, strlen(s)-1 ); printf ( "= %d \n", CalcTree ( Tree ) ); getch(); }
93 Дерево игры Задача. Перед двумя игроками лежат две кучки камней, в первой из которых 3, а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок?
94 Дерево игры 3, 2 игрок 1 3, 6 27, 2 3, 18 3, 3 4, 2 12, 2 4, 6 5, 2 4, 3 9, 3 4, 3 36, 2 4, 18 15, 2 12, 2 4, 6 5, 3 4, 4 36, 2 12, 6 15, 3 12, 4 27, 3 При правильной игре выиграет игрок 2 ! ! игрок 1 игрок 2 игрок 2 9, 2 4, 3 4, 3 ключевой ход выиграл игрок 1
95 Задания «4»: «Собрать» программу для вычисления правильного арифметического выражения, включающего только однозначные числа и знаки операций +, -, *, /. «5»: То же самое, но допускаются также многозначные числа и скобки. «6»: То же самое, что и на «5», но с обработкой ошибок (должно выводиться сообщение).
Тема 7. Графы © К.Ю. Поляков, 2008 Динамические структуры данных (язык Си)
97 Определения Граф – это набор вершин (узлов) и соединяющих их ребер (дуг). Направленный граф (ориентированный, орграф) – это граф, в котором все дуги имеют направления. Цепь – это последовательность ребер, соединяющих две вершины (в орграфе – путь ). Цикл – это цепь из какой-то вершины в нее саму. Взвешенный граф (сеть) – это граф, в котором каждому ребру приписывается вес (длина). 5 3 2 4 1 3 2 4 1 Дерево – это граф? ? Да, без циклов!
98 Определения Связный граф – это граф, в котором существует цепь между каждой парой вершин. k -c вязный граф – это граф, который можно разбить на k связных частей. Полный граф – это граф, в котором проведены все возможные ребра ( n вершин → n(n-1)/2 ребер ). 5 3 2 4 1 8 6 7 2 1 3 2 1 3 4
99 Описание графа Матрица смежности – это матрица, элемент M[i][j] которой равен 1, если существует ребро из вершины i в вершину j, и равен 0, если такого ребра нет. 4 2 1 3 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 2 3 4 0 1 2 3 4 4 2 1 3 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 2 3 4 0 1 2 3 4 Симметрия! ! Список смежности 1 2 3 0 3 4 0 0 1 4 1 3 0 1 2 3 4 1 2 3 3 4 4 0 1 2 3 4
100 Матрица и список смежности 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 1 0 4 2 3 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 4 2 3 1
101 Построения графа по матрице смежности 0 0 1 0 0 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 1 2 3 4 0 1 2 3 4 0 0 1 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 1 0 0 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 2 4 1 3 0 2 4 1 3
102 Как обнаружить цепи и циклы? Задача: определить, существует ли цепь длины k из вершины i в вершину j (или цикл длиной k из вершины i в нее саму ). M 2 [i][j] =1, если M[i][0]=1 и M[0][j]=1 или M[i][ 1 ]=1 и M[ 1 ][j]=1 или M[i][2]=1 и M[2][j]=1 строка i логическое умножение столбец j логическое сложение 0 2 3 1 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 0 1 2 3 0 1 2 3 M = или M[i][3]=1 и M[3][j]=1
103 Как обнаружить цепи и циклы? M 2 = M M Логическое умножение матрицы на себя: матрица путей длины 2 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 M 2 = 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 = 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 2 3 1 0 1 2 3 0 1 2 3 M 2 [2][0] = 0 · 0 + 1 · 1 + 0 · 0 + 1 · 1 = 1 маршрут 2-1-0 маршрут 2-3-0
104 Как обнаружить цепи и циклы? M 3 = M 2 M Матрица путей длины 3: 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 M 3 = = 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 2 3 1 0 1 2 3 0 1 2 3 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 на главной диагонали – циклы! 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 M 4 = = 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 0 1 2 3 0 1 2 3 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1
105 Весовая матрица 4 2 1 3 0 3 5 7 4 6 8 4 2 1 3 0 3 5 7 4 6 8 Весовая матрица – это матрица, элемент W[i][j] которой равен весу ребра из вершины i в вершину j (если оно есть), или равен ∞, если такого ребра нет. 0 7 3 5 ∞ 7 0 ∞ 4 8 3 ∞ 0 ∞ ∞ 5 4 ∞ 0 6 ∞ 8 ∞ 6 0 0 1 2 3 4 0 1 2 3 4 0 7 3 5 ∞ ∞ 0 ∞ 4 8 3 ∞ 0 ∞ ∞ 5 ∞ ∞ 0 6 ∞ 8 ∞ ∞ 0 0 1 2 3 4 0 1 2 3 4
106 Задача Прима-Краскала Задача: соединить N городов телефонной сетью так, чтобы длина телефонных линий была минимальная. Та же задача: дан связный граф с N вершинами, веса ребер заданы весовой матрицей W. Нужно найти набор ребер, соединяющий все вершины графа ( остовное дерево ) и имеющий наименьший вес. 4 2 1 3 0 3 5 7 4 6 8 0 7 3 5 ∞ 7 0 ∞ 4 8 3 ∞ 0 ∞ ∞ 5 4 ∞ 0 6 ∞ 8 ∞ 6 0 0 1 2 3 4 0 1 2 3 4
107 Жадный алгоритм Жадный алгоритм – это многошаговый алгоритм, в котором на каждом шаге принимается решение, лучшее в данный момент. В целом может получиться не оптимальное решение (последовательность шагов)! ! Шаг в задаче Прима-Краскала – это выбор еще невыбранного ребра и добавление его к решению. 4 2 1 3 0 3 5 7 4 6 8 В задаче Прима-Краскала жадный алгоритм дает оптимальное решение! !
108 Реализация алгоритма Прима-Краскала Проблема: как проверить, что 1) ребро не выбрано, и 2) ребро не образует цикла с выбранными ребрами. Решение: присвоить каждой вершине свой цвет и перекрашивать вершины при добавлении ребра. 4 2 1 3 0 3 5 7 4 6 8 2 1 3 4 Алгоритм: покрасить все вершины в разные цвета; сделать N-1 раз в цикле: выбрать ребро ( i,j ) минимальной длины из всех ребер, соединяющих вершины разного цвета; перекрасить все вершины, имеющие цвет j, в цвет i. вывести найденные ребра. 3
109 Реализация алгоритма Прима-Краскала Структура «ребро»: struct rebro { int i, j; // номера вершин }; const N = 5; void main () { int W [N][N], Col or [N], i, j, k, min, col_i, col_j ; rebro Reb [N-1]; ... / / здесь надо ввести матрицу W for ( i = 0; i < N; i ++ ) // раскрасить вершины Col or [ i ] = i ; ... / / основной алгоритм – заполнение массива Reb ... // вывести найденные ребра (массив Reb ) } Основная программа: весовая матрица цвета вершин
110 Реализация алгоритма Прима-Краскала for ( k = 0; k < N-1; k ++ ) { min = 30000; // большое число for ( i = 0; i < N-1; i ++ ) for ( j = i+1; j < N; j ++ ) if ( Col or [i] != Col or [j] && W [i][j] < min ) { min = W [i][j]; Reb[k].i = i; Reb[k].j = j; col_ i = Col or [ i ]; col_j = Col or [j]; } for ( i = 0; i < N; i ++ ) if ( Col or [i] == col_j ) Col or [i] = col_i ; } Основной алгоритм: нужно выбрать N-1 ребро цикл по всем парам вершин учитываем только пары с разным цветом вершин запоминаем ребро и цвета вершин перекрашиваем вершины цвета col_j
111 Сложность алгоритма Основной цикл: O(N 3 ) for ( k = 0; k < N-1; k ++ ) { ... for ( i = 0; i < N-1; i ++ ) for ( j = i+1; j < N; j ++ ) ... } три вложенных цикла, в каждом число шагов <=N растет не быстрее, чем N 3 Требуемая память: int W [N][N], Col or [N]; rebro Reb[N-1]; O(N 2 ) Количество операций:
112 Кратчайшие пути (алгоритм Дейкстры) Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти кратчайшие расстояния от заданного города до всех остальных городов. Та же задача: дан связный граф с N вершинами, веса ребер заданы матрицей W. Найти кратчайшие расстояния от заданной вершины до всех остальных. присвоить всем вершинам метку ∞ ; среди нерассмотренных вершин найти вершину j с наименьшей меткой; для каждой необработанной вершины i : если путь к вершине i через вершину j меньше существующей метки, заменить метку на новое расстояние; если остались необработанны вершины, перейти к шагу 2; метка = минимальное расстояние. 7 4 2 1 3 0 5 10 15 11 6 9 2 9 14 Алгоритм Дейкстры ( E. W. Dijkstra, 1959)
113 Алгоритм Дейкстры 7 4 2 1 3 0 5 10 15 11 6 9 2 9 14 ∞ ∞ ∞ ∞ ∞ 0 7 4 2 1 3 0 5 10 15 11 6 9 2 9 14 ∞ ∞ 14 7 9 0 7 4 2 1 3 0 5 10 15 11 6 9 2 9 14 22 ∞ 14 7 9 0 7 4 2 1 3 0 5 10 15 11 6 9 2 9 14 20 ∞ 11 7 9 0 7 4 2 1 3 0 5 10 15 11 6 9 2 9 14 20 20 11 7 9 0 7 4 2 1 3 0 5 10 15 11 6 9 2 9 14 20 20 11 7 9 0
114 Реализация алгоритма Дейкстры Массивы: массив a, такой что a[i]=1, если вершина уже рассмотрена, и a[i]=0, если нет. массив b, такой что b[i] – длина текущего кратчайшего пути из заданной вершины x в вершину i ; массив c, такой что c[i] – номер вершины, из которой нужно идти в вершину i в текущем кратчайшем пути. Инициализация : заполнить массив a нулями (вершины не обработаны); записать в b[i] значение W[x][i] ; заполнить массив c значением x ; записать a[x]=1. 7 4 2 1 3 0 5 10 15 11 6 9 2 9 14 ∞ ∞ 14 7 9 0 1 0 0 0 0 0 0 7 9 ∞ ∞ 14 0 0 0 0 0 0 a b c 0 1 2 3 4 5
115 Реализация алгоритма Дейкстры Основной цикл : если все вершины рассмотрены, то стоп. среди всех нерассмотренных вершин ( a[i]=0 ) найти вершину j, для которой b[i] – минимальное; записать a[j]=1 ; для всех вершин k : если путь в вершину k через вершину j короче, чем найденный ранее кратчайший путь, запомнить его: записать b[k]=b[j]+W[j][k] и c[k]=j. 1 1 0 0 0 0 0 7 9 22 ∞ 14 0 0 0 1 0 0 a b c 0 1 2 3 4 5 Шаг 1: 7 4 2 1 3 0 5 10 15 11 6 9 2 9 14 22 ∞ 14 7 9 0
116 Реализация алгоритма Дейкстры 1 1 1 0 0 0 0 7 9 2 0 ∞ 1 1 0 0 0 2 0 2 a b c 0 1 2 3 4 5 Шаг 2: 7 4 2 1 3 0 5 10 15 11 6 9 2 9 14 2 0 ∞ 11 7 9 0 1 1 1 0 0 1 0 7 9 2 0 20 1 1 0 0 0 2 5 2 a b c 0 1 2 3 4 5 Шаг 3 : 7 4 2 1 3 0 5 10 15 11 6 9 2 9 14 2 0 20 11 7 9 0 Дальше массивы не изменяются ! !
117 Как вывести маршрут? 1 1 1 1 1 1 0 7 9 2 0 20 1 1 0 0 0 2 5 2 a b c 0 1 2 3 4 5 Результат работа алгоритма Дейкстры: длины путей Маршрут из вершины 0 в вершину 4: 4 0 5 2 5 2 0 Сложность алгоритма Дейкстры: O(N 2 ) два вложенных цикла по N шагов Вывод маршрута в вершину i (использование массива c ) : установить z=i ; пока c[i]!=x присвоить z=c[z] и вывести z.
118 Алгоритм Флойда-Уоршелла Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти все кратчайшие расстояния, от каждого города до всех остальных городов. for ( k = 0; k < N; k ++ ) for ( i = 0; i < N; i ++ ) for ( j = 0; j < N; j ++ ) if ( W[i][j] > W[i][k] + W[k][j] ) W[i][j] = W[i][k] + W[k][j] ; i j k W[i][j] W[i][ k ] W[ k ][ j ] Если из вершины i в вершину j короче ехать через вершину k, мы едем через вершину k ! Нет информации о маршруте, только кратчайшие расстояния! !
119 Алгоритм Флойда-Уоршелла Версия с запоминанием маршрута: for ( i = 0; i < N; i ++ ) for ( j = 0; j < N; j ++ ) c[i][j] = i; ... for ( k = 0; k < N; k ++ ) for ( i = 0; i < N; i ++ ) for ( j = 0; j < N; j ++ ) if ( W[i][j] > W[i][k] + W[k][j] ) { W[i][j] = W[i][k] + W[k][j] ; c [i][j] = c[k][j] ; } i – ая строка строится так же, как массив c в алгоритме Дейкстры в конце цикла c[i][j] – предпоследняя вершина в кратчайшем маршруте из вершины i в вершину j c [i][j] = c[k][j] ; Какова сложность алгоритма? ? O(N 3 )
120 Задача коммивояжера Задача коммивояжера. Коммивояжер (бродячий торговец) должен выйти из первого города и, посетив по разу в неизвестном порядке города 2,3,... N, вернуться обратно в первый город. В каком порядке надо обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим? Это NP- полная задача, которая строго решается только перебором вариантов (пока) ! ! Точные методы: простой перебор; метод ветвей и границ; метод Литтла; … Приближенные методы: метод случайных перестановок ( Matlab ) ; генетические алгоритмы; метод муравьиных колоний; … большое время счета для больших N O(N!) не гарантируется оптимальное решение
121 Другие классические задачи Задача на минимум суммы. Имеется N населенных пунктов, в каждом из которых живет p i школьников ( i=1,..., N ). Надо разместить школу в одном из них так, чтобы общее расстояние, проходимое всеми учениками по дороге в школу, было минимальным. Задача о наибольшем потоке. Есть система труб, которые имеют соединения в N узлах. Один узел S является источником, еще один – стоком T. Известны пропускные способности каждой трубы. Надо найти наибольший поток от источника к стоку. Задача о наибольшем паросочетании. Есть M мужчин и N женщин. Каждый мужчина указывает несколько (от 0 до N ) женщин, на которых он согласен жениться. Каждая женщина указывает несколько мужчин (от 0 до M ), за которых она согласна выйти замуж. Требуется заключить наибольшее количество моногамных браков.
122 Конец фильма
