Указатели Динамические массивы Структуры Списки Стеки, очереди, деки Деревья Графы
Тема 1. Указатели Динамические структуры данных (язык Паскаль)
3 Статические данные переменная (массив) имеет имя, по которому к ней можно обращаться размер заранее известен (задается при написании программы) память выделяется при объявлении размер нельзя увеличить во время работы программы var x, y: integer; z: float; A: array[1..10] of float; str : string;
4 Динамические данные размер заранее неизвестен, определяется во время работы программы память выделяется во время работы программы нет имени? Проблема: как обращаться к данным, если нет имени? Решение: использовать адрес в памяти Следующая проблема: в каких переменных могут храниться адреса? как работать с адресами?
5 Указатели Указатель – это переменная, в которую можно записывать адрес другой переменной (или блока памяти). Объявление: Как записать адрес: var pC : ^char; // адрес символа pI : ^integer; // адрес целой переменной pR : ^real; // адрес вещ. переменной var m: integer; // целая переменная pI : ^integer; // указатель A: array[1..2] of integer; // массив ... pI = @ m; // адрес переменной m pI = @ A[1]; // адрес элемента массива A[1] pI = nil; // нулевой адрес @ ^ nil указатель адрес ячейки
6 Обращение к данным через указатель program qq ; var m, n: integer; pI : ^integer; begin m := 4; pI := @m; writeln (' Адрес m = ', pI ); // вывод адреса writeln ('m = ', pI ^); // вывод значения n := 4*(7 - pI ^); // n = 4*(7 - 4) = 12 pI ^ := 4*(n - m); // m = 4*(12 – 4) = 32 end. ^ «вытащить» значение по адресу
7 Обращение к данным (массивы) program qq ; var i : integer; A: array[1..4] of integer; pI : ^integer; begin for i :=1 to 4 do A[ i ] := i ; pI := @A[1]; // адрес A[ 1 ] while ( pI ^ <= 4 ) // while( A[ i ] <= 4 ) do begin pI ^ := pI ^ * 2; // A[ i ] := A[ i ] *2 ; pI := pI + 1; // к следующему элементу end; end. переместиться к следующему элементу = изменить адрес на sizeof (integer) Не работает в PascalABC.NET ! !
8 Что надо знать об указателях указатель – это переменная, в которой можно хранить адрес другой переменной; при объявлении указателя надо указать тип переменных, на которых он будет указывать, а перед типом поставить знак ^ ; знак @ перед именем переменной обозначает ее адрес; запись p^ обозначает значение ячейки, на которую указывает указатель p ; nil – это нулевой указатель, он никуда не указывает при изменении значения указателя на n он в самом деле сдвигается к n - ому следующему числу данного типа (для указателей на целые числа – на n * sizeof ( integer ) байт). Нельзя использовать указатель, который указывает неизвестно куда ( будет сбой или зависание ) !
Тема 2. Динамические массивы Динамические структуры данных (язык Паскаль)
10 Где нужны динамические массивы? Задача. Ввести размер массива, затем – элементы массива. Отсортировать массив и вывести на экран. Проблема: размер массива заранее неизвестен. Пути решения: выделить память «с запасом»; выделять память тогда, когда размер стал известен. Алгоритм: ввести размер массива; выделить память ; ввести элементы массива ; отсортировать и вывести на экран; удалить массив. выделить память удалить массив
11 Использование указателей (Delphi) program qq; type intArray = array[ 1.. 1 ] of integer; var A: ^intArray; i, N: integer; begin writeln(' Размер массива >'); readln(N); GetMem(pointer(A), N*sizeof(integer)); for i := 1 to N do readln(A[i]); ... { сортировка } for i := 1 to N do writeln(A[i]); FreeMem(pointer(A)); end. выделить память освободить память работаем так же, как с обычным массивом! какой-то массив целых чисел
12 Использование указателей для выделения памяти используют процедуру GetMem GetMem( указатель, размер в байтах ); указатель должен быть приведен к типу pointer –указатель без типа, просто адрес какого-то байта в памяти; с динамическим массивом можно работать так же, как и с обычным (статическим); для освобождения блока памяти нужно применить процедуру FreeMem : FreeMem ( указатель );
13 Ошибки при работе с памятью Запись в «чужую» область памяти: память не была выделена, а массив используется. Что делать : так не делать. Выход за границы массива: обращение к элементу массива с неправильным номером, при записи портятся данные в «чужой» памяти. Что делать : если позволяет транслятор, включать проверку выхода за границы массива. Указатель удаляется второй раз: структура памяти нарушена, может быть все, что угодно. Что делать : в удаленный указатель лучше записывать nil, ошибка выявится быстрее. Утечка памяти: ненужная память не освобождается. Что делать : убирайте «мусор» (в среде.NET есть сборщик мусора!)
14 Динамические массивы (Delphi) program qq; var A: array of integer; i, N: integer; begin writeln(' Размер массива >'); readln(N); SetLength ( A, N ); for i := 0 to N-1 do readln(A[i]); ... { сортировка } for i := 0 to N -1 do writeln(A[i]); SetLength( A, 0 ); end. выделить память освободить память какой-то массив целых чисел нумерация с НУЛЯ !
15 Динамические массивы ( Delphi ) при объявлении массива указывают только его тип, память не выделяется: var A: array of integer ; для выделения памяти используют процедуру SetLength ( установить длину ) SetLength ( массив, размер ); номера элементов начинаются с НУЛЯ ! для освобождения блока памяти нужно установить нулевую длину через процедуру SetLength : SetLength ( массив, 0 );
16 Динамические матрицы ( Delphi ) Задача. Ввести размеры матрицы и выделить для нее место в памяти во время работы программы. Проблема: размеры матрицы заранее неизвестны Решение: var A: array of array of integer; N, M: integer; begin writeln (' Число строк и столбцов >'); readln (N, M); SetLength ( A, N, M ); ... // работаем, как с обычной матрицей SetLength ( A, 0, 0 ); end.
Тема 3. Структуры ( записи) Динамические структуры данных (язык Паскаль)
18 Структуры (в Паскале – записи ) Структура (запись) – это тип данных, который может включать в себя несколько полей – элементов разных типов (в том числе и другие структуры). Свойства : автор ( строка ) название ( строка ) год издания ( целое число ) количество страниц ( целое число ) Задача : объединить эти данные в единое целое Размещение в памяти автор название год издания количество страниц 40 символов 80 символов целое целое
19 Одна запись readln ( Book.author ); // ввод readln ( Book.title ); Book.year := 1998; // присваивание if Book.pages > 200 then // сравнение writeln ( Book.author, '.', Book.title ); // вывод Объявление (выделение памяти): var Book: record author: string [40]; // автор, строка title: string [80]; // название, строка year: integer ; // год издания, целое pages: integer ; // кол-во страниц, целое end ; название запись поля Обращение к полям: Для обращения к полю записи используется точка! !
20 Массив записей Объявление (выделение памяти): const N = 10; var aBooks : array[1..N] of record author: string [40]; title: string [80]; year: integer ; pages: integer ; end; Books[ 1 ]... Books[ 10 ] author title year pages
21 Массив записей for i :=1 to N do begin readln ( aBooks [ i ].author); readln ( aBooks [ i ].title); ... end; for i :=1 to N do if aBooks [ i ].pages > 200 then writeln ( aBooks [ i ].author, '.', aBooks [ i ].title); Обращение к полям: aBooks [ i ].author – обращение к полю author записи aBooks [ i ] !
22 Новый тип данных – запись const N = 10; var Book: TBook ; // одна запись aBooks : array[1..N] of TBook ; // массив Объявление типа: type TBook = record author: string [40]; // автор, строка title: string [80]; // название, строка year: integer ; // год издания, целое pages : integer ; // кол-во страниц, целое end ; Память не выделяется! ! Объявление переменных и массивов: TBook – Type Book ( «тип книга» ) – удобно!
23 Записи в процедурах и функциях Book.author := ' А.С. Пушкин '; ShowAuthor ( Book ); Book.year := 1800; writeln ( IsOld (Book) ); Процедура: procedure ShowAuthor ( b: TBook ); begin writeln ( b.author ); end; Память не выделяется! ! Основная программа: function IsOld ( b: TBook ): boolean ; begin IsOld := b.year < 1900; end; Функция:
24 Файлы записей Объявление указателя на файл: var F: file of TBook ; Assign(F, 'books.dat'); { связать с указателем } Rewrite(F); { открыть файл для запись } writeln (F, Book); { запись } for i :=1 to 5 do writeln ( aBook [ i ]); { запись } Close(F); { закрыть файл } Запись в файл:
25 Чтение из файла Известное число записей: Assign(F, 'books.dat'); { связать с указателем } Reset(F); { открыть для чтения } Read(F, Book); { чтение } for i :=1 to 5 do Read(F, aBook [ i ]); { чтение } Close(F); { закрыть файл } «Пока не кончатся»: count := 0; while not eof (F) do begin count := count + 1; { счетчик } Read(F, aBook [count]); { чтение } end; В чем может быть проблема! ? пока не дошли до конца файла F EOF = end of file
26 Пример программы Задача : в файле books.dat записаны данные о книгах в виде массива структур типа TBook ( не более 100 ). Установить для всех 200 8 год издания и записать обратно в тот же файл. type Tb ook … ; const MAX = 100; var aBooks : array[1..MAX] of TBook ; i, N: integer; F: file of TBook ; begin { прочитать записи из файла, N - количество } for i :=1 to N do aBooks [ i ].year := 2008; { сохранить в файле } end. type TB ook … ; полное описание структуры
27 Пример программы Чтение «пока не кончатся»: Assign(f, 'books.dat'); Reset(f); N := 0; while not eof (F) and (N < MAX) do begin N := N + 1; read(F, aBooks [N]); end; С lose(f); Assign(f, 'books.dat'); { можно без этого } Rewrite(f); for i :=1 to N do write(F, aBooks [ i ]); Close(f); Сохранение: чтобы не выйти за пределы массива
28 Выделение памяти под запись var pB : ^ TBook ; begin New( pB ); pB^.author := ' А.С. Пушкин '; pB^.title := ' Полтава '; pB^.year := 1990; pB^.pages := 129; Dispose( pB ); end. Для обращения к полю записи по адресу используется знак ^ ! N ew (pB ); выделить память под запись, записать адрес в pB p B^ Dispose( p B) ; освободить память p B: ^TBook; переменная-указатель на TBook
29 Сортировка массива записей Ключ (ключевое поле) – это поле записи (или комбинация полей), по которому выполняется сортировка. const N = 100; var aBooks : array[1..N] of TBook ; i, j, N: integer; temp: TBook ; { для обмена } begin { заполнить массив aBooks } { отсортировать = переставить } for i :=1 to N do writeln ( aBooks [ i ].title, aBooks [ i ].year:5); end.
30 Сортировка массива записей for i :=1 to N-1 do for j:=N-1 downto i do if aBooks [j].year > aBooks [j+1].year then begin temp := aBooks [j]; aBooks [j] := aBooks [j+1]; aBooks [j+1] := temp; end; Какой ключ сортировки? ? Какой метод сортировки? ? Что плохо? ?
31 Сортировка массива записей Проблема: как избежать копирования записи при сортировке? Решение: использовать вспомогательный массив указателей, при сортировке переставлять указатели. 5 1 3 2 4 p[ 1 ] p[ 2 ] p[ 3 ] p[ 4 ] p[ 5 ] p[ 5 ] p[ 1 ] p[ 3 ] p[ 2 ] p[ 4 ] До сортировки: После сортировки: Вывод результата: for i :=1 to N do writeln (p[ i ]^.title, p[ i ]^.year:5); p[i]^ p[i]^ 5 1 3 2 4
32 Реализация в программе type PBook = ^ TBook ; { новый тип данных } var p: array[1..N] of PBook ; begin { заполнение массива записей } for i :=1 to N do p[ i ] := @ aBooks [ i ]; for i :=1 to N do writeln (p[ i ]^.title, p[ i ]^.year:5); end. for i:=1 to N-1 do for j:=N-1 downto i do if p[j]^.year > p[j+1]^.year then begin temp := p[j]; p[j] := p[j+1]; p[j+1] := temp; end; вспомогательные указатели меняем только указатели, записи остаются на местах начальная расстановка
Тема 4. Списки Динамические структуры данных (язык Паскаль)
34 Динамические структуры данных Строение: набор узлов, объединенных с помощью ссылок. Как устроен узел : данные ссылки на другие узлы Типы структур : списки деревья графы nil nil nil односвязный двунаправленный (двусвязный) циклические списки (кольца) nil nil nil nil nil nil
35 Когда нужны списки? Задача (алфавитно-частотный словарь). В файле записан текст. Нужно записать в другой файл в столбик все слова, встречающиеся в тексте, в алфавитном порядке, и количество повторений для каждого слова. Проблемы : количество слов заранее неизвестно (статический массив); количество слов определяется только в конце работы (динамический массив). Решение – список. Алгоритм : создать список; если слова в файле закончились, то стоп. прочитать слово и искать его в списке; если слово найдено – увеличить счетчик повторений, иначе добавить слово в список; перейти к шагу 2.
36 Что такое список: пустая структура – это список; список – это начальный узел ( голова ) и связанный с ним список. Списки: новые типы данных type PNode = ^Node; { указатель на узел } Node = record { структура узла } word: string[40]; { слово } count: integer; { счетчик повторений } next: PNode ; { ссылка на следующий } end; Новые типы данных : Адрес начала списка : var Head: PNode ; ... Head := nil; Рекурсивное определение! ! nil Для доступа к списку достаточно знать адрес его головы! !
37 Что нужно уметь делать со списком? Создать новый узел. Добавить узел: а) в начало списка; б) в конец списка; в) после заданного узла; г) до заданного узла. Искать нужный узел в списке. Удалить узел.
38 Создание узла function CreateNode ( NewWord : string): PNode ; var NewNode : PNode ; begin New( NewNode ); NewNode^.word := NewWord ; NewNode^.count := 1; NewNode^.next := nil; Result := NewNode ; end; Функция CreateNode ( создать узел ): вход: новое слово, прочитанное из файла; выход: адрес нового узла, созданного в памяти. возвращает адрес созданного узла новое слово Если память выделить не удалось? ?
39 Добавление узла в начало списка NewNode Head nil 1) Установить ссылку нового узла на голову списка: NewNode ^. next : = Head ; NewNode Head nil nil 2 ) Установить новый узел как голову списка: Head : = NewNode ; procedure AddFirst ( var Head: PNode ; NewNode : PNode ); begin NewNode^.next := Head; Head := NewNode ; end; var адрес головы меняется
40 Добавление узла после заданного 1) Установить ссылку нового узла на узел, следующий за p : NewNode ^. next = p^.next ; 2 ) Установить ссылку узла p на новый узел: p^.next = NewNode ; NewNode p nil nil NewNode p nil procedure AddAfter ( p, NewNode : PNode ); begin NewNode^.next := p^.next ; p^.next := NewNode ; end;
41 Задача: сделать что-нибудь хорошее с каждым элементом списка. Алгоритм: установить вспомогательный указатель q на голову списка; если указатель q равен nil (дошли до конца списка), то стоп; выполнить действие над узлом с адресом q ; перейти к следующему узлу, q^.next. Проход по списку var q: PNode ; ... q := Head; // начали с головы while q <> nil do begin // пока не дошли до конца ... // делаем что-то хорошее с q q := q^.next ; // переходим к следующему end; Head nil q
42 Добавление узла в конец списка Задача: добавить новый узел в конец списка. Алгоритм: найти последний узел q, такой что q^.next равен nil ; добавить узел после узла с адресом q ( процедура AddAfter ). Особый случай: добавление в пустой список. procedure AddLast ( var Head: PNode ; NewNode : PNode ); var q: PNode ; begin if Head = nil then AddFirst ( Head, NewNode ) else begin q := Head; while q^.next <> nil do q := q^.next ; AddAfter ( q, NewNode ); end; end; особый случай – добавление в пустой список ищем последний узел добавить узел после узла q
43 Проблема: нужно знать адрес предыдущего узла, а идти назад нельзя! Решение: найти предыдущий узел q (проход с начала списка). Добавление узла перед заданным NewNode p nil nil procedure AddBefore ( var Head: PNode ; p, NewNode : PNode ); var q: PNode ; begin q := Head; if p = Head then AddFirst ( Head, NewNode ) else begin while (q <> nil) and ( q^.next <> p) do q := q^.next ; if q <> nil then AddAfter ( q, NewNode ); end; end; в начало списка ищем узел, следующий за которым – узел p добавить узел после узла q Что плохо? ?
44 Добавление узла перед заданным ( II ) Задача: вставить узел перед заданным без поиска предыдущего. Алгоритм: поменять местами данные нового узла и узла p ; установить ссылку узла p на NewNode. procedure AddBefore 2 ( p, NewNode : PNode ); var temp: Node; begin temp := p^; p^ := NewNode ^; NewNode ^ := temp; p^.next := NewNode ; end; NewNode p nil Так нельзя, если p = nil или адреса узлов где-то еще запоминаются! ! NewNode p nil nil
45 Поиск слова в списке Задача: найти в списке заданное слово или определить, что его нет. Функция Find : вход : слово (символьная строка); выход : адрес узла, содержащего это слово или nil. Алгоритм: проход по списку. function Find(Head: PNode ; NewWord : string): PNode ; var q: PNode ; begin q := Head; while (q <> nil) and ( NewWord <> q^.word ) do q := q^.next ; Result := q; end; ищем это слово результат – адрес узла или nil ( нет такого ) while (q <> nil) and (NewWord <> q^.word) do q := q^.next; пока не дошли до конца списка и слово не равно заданному
46 Куда вставить новое слово? Задача: найти узел, перед которым нужно вставить, заданное слово, так чтобы в списке сохранился алфавитный порядок слов. Функция FindPlace : вход : слово (символьная строка); выход : адрес узла, перед которым нужно вставить это слово или nil, если слово нужно вставить в конец списка. function FindPlace (Head: PNode ; NewWord : string): PNode ; var q: PNode ; begin q := Head; while (q <> nil) and ( NewWord > q^.word ) do q := q^.next ; Result := q; end; > слово NewWord стоит по алфавиту перед q^.word
47 Удаление узла procedure DeleteNode ( var Head: PNode ; p: PNode ); var q: PNode ; begin if Head = p then Head := p^.next else begin q := Head; while (q <> nil) and ( q^.next <> p) do q := q^.next ; if q <> nil then q^.next := p^.next ; end; Dispose(p); end; while (q <> nil) and (q^.next <> p) do q := q^.next; if Head = p then Head := p^.next q Head p nil Проблема: нужно знать адрес предыдущего узла q. особый случай: удаляем первый узел ищем узел, такой что q^.next = p Dispose( p ) ; освобождение памяти
48 Алфавитно-частотный словарь Алгоритм: открыть файл на чтение; прочитать очередное слово ( как? ) если файл закончился, то перейти к шагу 7; если слово найдено, увеличить счетчик (поле count ); если слова нет в списке, то создать новый узел, заполнить поля ( CreateNode ); найти узел, перед которым нужно вставить слово ( FindPlace ); добавить узел ( AddBefore ); перейти к шагу 2; закрыть файл вывести список слов, используя проход по списку. var F: Text; ... Assign(F, 'input.dat'); Reset ( F ); Close ( F );
49 Как прочитать одно слово из файла? function GetWord ( F: Text ) : string; var c: char; begin Result := ''; { пустая строка } c := ' '; { пробел – чтобы войти в цикл } { пропускаем спецсимволы и пробелы } while not eof (f) and (c <= ' ') do read(F, c); { читаем слово } while not eof (f) and (c > ' ') do begin Result := Result + c; read(F, c); end; end; Алгоритм: пропускаем все спецсимволы и пробелы (с кодами <= 32 ) читаем все символы до первого пробела или спецсимвола М ожно поменять местами строчки в цикле? ?
type PNode = ^Node; { указатель на узел } Node = record { структура узла } word: string[40]; { слово } count: integer; { счетчик повторений } next: PNode ; { ссылка на следующий } prev : PNode ; { ссылка на предыдущий } end; 50 Двусвязные списки Структура узла : Адреса «головы» и «хвоста» : var Head, Tail: PNode ; ... Head := nil; Tail := nil; next prev previous можно двигаться в обе стороны нужно работать с двумя указателями вместо одного nil nil Head Tail
51 Задания «4»: «Собрать» из этих функций программу для построения алфавитно-частотного словаря. В конце файла вывести общее количество разных слов (количество элементов списка). «5»: То же самое, но использовать двусвязные списки. «6»: То же самое, что и на «5», но вывести список слов в порядке убывания частоты, то есть, сначала те слова, которые встречаются чаще всего.
Тема 5. Стеки, очереди, деки Динамические структуры данных (язык Паскаль)
53 Стек Стек – это линейная структура данных, в которой добавление и удаление элементов возможно только с одного конца ( вершины стека ). Stack = кипа, куча, стопка (англ.) LIFO = Last In – First Out «Кто последним вошел, тот первым вышел». Операции со стеком: добавить элемент на вершину ( Push = втолкнуть) ; снять элемент с вершины ( Pop = вылететь со звуком ).
54 Пример задачи Задача: вводится символьная строка, в которой записано выражение со скобками трех типов: [], {} и (). Определить, верно ли расставлены скобки (не обращая внимания на остальные символы). Примеры: [()]{} ][ [({)]} Упрощенная задача: то же самое, но с одним видом скобок. Решение : счетчик вложенности скобок. Последовательность правильная, если в конце счетчик равен нулю и при проходе не разу не становился отрицательным. Можно ли решить исходную задачу так же, но с тремя счетчиками? ? [ ( { ) ] } ( : 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 ( ( ) ) (
55 Решение задачи со скобками Алгоритм: в начале стек пуст; в цикле просматриваем все символы строки по порядку; если очередной символ – открывающая скобка, заносим ее на вершину стека; если символ – закрывающая скобка, проверяем вершину стека: там должна быть соответствующая открывающая скобка (если это не так, то ошибка); если в конце стек не пуст, выражение неправильное. [ ( ( ) ) ] { } [ [ ( [ ( ( [ ( ( [ ( [ { {
56 Реализация стека (массив) Структура-стек: const MAXSIZE = 100; type Stack = record { стек на 100 символов } data: array[1..MAXSIZE] of char; size: integer; { число элементов } end; Добавление элемента: procedure Push( var S: Stack; x: char); begin if S.size = MAXSIZE then Exit; S.size := S.size + 1; S.data [ S.size ] := x; end; ошибка : переполнение стека добавить элемент Что плохо? ?
57 Реализация стека (массив) function Pop ( var S:Stack ): char; begin if S.size = 0 then begin Result := char(255); Exit; end; Result := S.data [ S.size ]; S.size := S.size - 1; end; Снятие элемента с вершины: Пустой или нет? function isEmpty ( S: Stack ): Boolean; begin Result := ( S.size = 0); end; ошибка : стек пуст
58 Программа var br1, br2, expr: string; i, k: integer; upper: char; { то, что сняли со стека } error: Boolean; { признак ошибки } S: Stack; begin br1 := '([{'; br2 := ')]}'; S.size := 0; error := False; writeln (' Введите выражение со скобками '); readln ( expr ); ... { здесь будет основной цикл обработки } if not error and isEmpty (S) then writeln (' Выражение правильное.') else writeln (' Выражение неправильное.') end. открывающие скобки закрывающие скобки
59 Обработка строки (основной цикл) for i :=1 to length( expr ) do begin for k:=1 to 3 do begin if expr [ i ] = br1[k] then begin { откр. скобка } Push(S, expr [ i ]); { втолкнуть в стек } break; end; if expr [ i ] = br2[k] then begin { закр. скобка } upper := Pop(S); { снять символ со стека } error := upper <> br1[k]; break; end; end; if error then break; end; цикл по всем символам строки expr цикл по всем видам скобок ошибка: стек пуст или не та скобка была ошибка: дальше нет смысла проверять
60 Реализация стека (список) Добавление элемента: Структура узла: type PNode = ^Node; { указатель на узел } Node = record data: char; { данные } next: PNode ; { указатель на след. элемент } end; procedure Push( var Head: PNode ; x: char); var NewNode : PNode ; begin New( NewNode ); { выделить память } NewNode^.data := x; { записать символ } NewNode^.next := Head; { сделать первым узлом } Head := NewNode ; end;
61 Реализация стека (список) Снятие элемента с вершины: function Pop ( var Head: PNode ): char; var q: PNode ; begin if Head = nil then begin { стек пуст } Result := char(255); { неиспользуемый символ } Exit; end; Result := Head^.data ; { взять верхний символ } q := Head; { запомнить вершину } Head := Head^.next ; { удалить вершину из стека } Dispose(q); { удалить из памяти } end; Можно ли переставлять операторы? ? q := Head; Head := Head^.next ; Dispose(q);
62 Реализация стека (список) Изменения в основной программе: var S: Stack; ... S.size := 0; var S: PNode ; S : = nil; Больше ничего не меняется! ! Пустой или нет? function isEmpty ( S: Stack ): Boolean; begin Result := (S = nil); end;
63 Вычисление арифметических выражений 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
64 Запишите в постфиксной форме (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)
65 Вычисление выражений Постфиксная форма: 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 =
66 Системный стек ( Windows – 1 Мб ) Используется для размещения локальных переменных ; хранения адресов возврата (по которым переходит программа после выполнения функции или процедуры); передачи параметров в функции и процедуры; временного хранения данных (в программах на языке Ассмеблер ). Переполнение стека ( stack overflow ): слишком много локальных переменных ( выход – использовать динамические массивы) ; очень много рекурсивных вызовов функций и процедур ( выход – переделать алгоритм так, чтобы уменьшить глубину рекурсии или отказаться от нее вообще).
67 Очередь 1 2 3 4 5 6 Очередь – это линейная структура данных, в которой добавление элементов возможно только с одного конца ( конца очереди ), а удаление элементов – только с другого конца ( начала очереди ). FIFO = First In – First Out «Кто первым вошел, тот первым вышел». Операции с очередью: добавить элемент в конец очереди ( PushTail = втолкнуть в конец) ; удалить элемент с начала очереди ( Pop ).
68 Реализация очереди (массив) 1 1 2 1 2 3 1 2 3 самый простой способ нужно заранее выделить массив; при выборке из очереди нужно сдвигать все элементы.
69 Реализация очереди (кольцевой массив) 1 2 Head Tail 1 2 3 2 3 2 3 4 3 4 Сколько элементов можно хранить в такой очереди? ? Как различить состояния «очередь пуста» и «очередь полна»? ? 3 4 5
70 Реализация очереди (кольцевой массив) 1 Head Tail В очереди 1 элемент: Очередь пуста: Очередь полна: Head = Tail + 1 Head = ( Tail mod N) + 1 1 N размер массива 1 2 3 Head = Tail + 2 Head = ( Tail+1) mod N + 1 1 N 1 2 3 Head = Tail
71 Реализация очереди (кольцевой массив) type Queue = record data: array[1..MAXSIZE] of integer; head, tail: integer; end; Структура данных: Добавление в очередь: procedure PushTail ( var Q: Queue; x: integer); begin if Q.head = (Q.tail+1) mod MAXSIZE + 1 then Exit; { очередь полна, не добавить } Q.tail := Q.tail mod MAXSIZE + 1; Q.data [ Q.tail ] := x; end; замкнуть в кольцо mod MAXSIZE
72 Реализация очереди (кольцевой массив) Выборка из очереди: function Pop ( var S: Queue ): integer; begin if Q.head = Q.tail mod MAXSIZE + 1 then begin Result := MaxInt ; Exit; end; Result := Q.data [ Q.head ]; Q.head := Q.head mod MAXSIZE + 1; end; очередь пуста взять первый элемент удалить его из очереди максимальное целое число
73 Реализация очереди (списки) type PNode = ^Node; Node = record data: integer; next: PNode ; end; type Queue = record head, tail: PNode ; end; Структура узла: Тип данных «очередь»:
74 Реализация очереди (списки) procedure PushTail ( var Q: Queue; x: integer ); var NewNode : PNode ; begin New( NewNode ); NewNode^.data := x; NewNode^.next := nil; if Q.tail <> nil then Q.tail^.next := NewNode ; Q.tail := NewNode ; { новый узел – в конец } if Q.head = nil then Q.head := Q.tail ; end; Добавление элемента: создаем новый узел если в списке уже что-то было, добавляем в конец если в списке ничего не было, …
75 Реализация очереди (списки) function Pop ( var S: Queue ): integer; var top: PNode ; begin if Q.head = nil then begin Result := MaxInt ; Exit; end; top := Q.head ; Result := top^.data ; Q.head := top^.next ; if Q.head = nil then Q.tail := nil; Dispose(top); end; Выборка элемента: если список пуст, … запомнили первый элемент если в списке ничего не осталось, … освободить память
76 Дек Дек ( deque = d ouble e nded que ue, очередь с двумя концами) – это линейная структура данных, в которой добавление и удаление элементов возможно с обоих концов. 1 2 3 4 5 6 Операции с деком: добавление элемента в начало ( Push ); удаление элемента с начала ( Pop ) ; добавление элемента в конец (PushTail) ; удаление элемента с конца (PopTail). Реализация: кольцевой массив ; двусвязный список.
77 Задания «4»: В файле input.dat находится список чисел (или слов). Переписать его в файл output.dat в обратном порядке. «5»: Составить программу, которая вычисляет значение арифметического выражения, записанного в постфиксной форме, с помощью стека. Выражение правильное, допускаются только однозначные числа и знаки +, -, *, /. «6»: То же самое, что и на «5», но допускаются многозначные числа.
Тема 6. Деревья Динамические структуры данных (язык Паскаль)
79 Деревья директор гл. инженер гл. бухгалтер инженер инженер инженер бухгалтер бухгалтер бухгалтер Что общего во всех примерах? ?
80 Деревья Дерево – это структура данных, состоящая из узлов и соединяющих их направленных ребер (дуг), причем в каждый узел (кроме корневого) ведет ровно одна дуга. Корень – это начальный узел дерева. Лист – это узел, из которого не выходит ни одной дуги. корень 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
81 Деревья Предок узла x – это узел, из которого существует путь по стрелкам в узел x. Потомок узла x – это узел, в который существует путь по стрелкам из узла x. Родитель узла x – это узел, из которого существует дуга непосредственно в узел x. С помощью деревьев изображаются отношения подчиненности (иерархия, «старший – младший», «родитель – ребенок»). ! 2 4 6 1 3 5 Сын узла x – это узел, в который существует дуга непосредственно из узла x. Брат узла x ( sibling ) – это узел, у которого тот же родитель, что и у узла x. Высота дерева – это наибольшее расстояние от корня до листа (количество дуг).
82 Дерево – рекурсивная структура данных Рекурсивное определение: Пустая структура – это дерево. Дерево – это корень и несколько связанных с ним деревьев. 2 4 6 1 3 5 Двоичное (бинарное) дерево – это дерево, в котором каждый узел имеет не более двух сыновей. Пустая структура – это двоичное дерево. Двоичное дерево – это корень и два связанных с ним двоичных дерева (левое и правое поддеревья).
83 Двоичные деревья Структура узла: type PNode = ^Node; { указатель на узел } Node = record data: integer; { полезные данные } left, right: PNode ; { ссылки на левого и правого сыновей } end; Применение: поиск данных в специально построенных деревьях (базы данных); сортировка данных; вычисление арифметических выражений; кодирование (метод Хаффмана).
84 Двоичные деревья поиска 16 45 30 76 12 5 98 59 Какая закономерность? ? Слева от каждого узла находятся узлы с меньшими ключами, а справа – с б ó льшими. Ключ – это характеристика узла, по которой выполняется поиск (чаще всего – одно из полей структуры). Как искать ключ, равный x : если дерево пустое, ключ не найден; если ключ узла равен x, то стоп. если ключ узла меньше x, то искать x в левом поддереве; если ключ узла больше x, то искать x в правом поддереве. Сведение задачи к такой же задаче меньшей размерности – это …? ?
85 Двоичные деревья поиска 16 45 30 76 12 5 98 59 Поиск в массиве ( N элементов): 16 45 30 76 12 5 98 59 При каждом сравнении отбрасывается 1 элемент. Число сравнений – N. Поиск по дереву ( N элементов): При каждом сравнении отбрасывается половина оставшихся элементов. Число сравнений ~ log 2 N. быстрый поиск нужно заранее построить дерево; желательно, чтобы дерево было минимальной высоты.
86 Реализация алгоритма поиска { Функция Search – поиск по дереву Вход: Tree - адрес корня, x - что ищем Выход: адрес узла или nil ( не нашли ) } function Search(Tree: PNode ; x: integer): PNode ; begin if Tree = nil then begin Result := nil; Exit; end; if x = Tree^.data then Result := Tree else if x < Tree^.data then Result := Search( Tree^.left, x) else Result := Search( Tree^.right, x); end; дерево пустое: ключ не нашли… нашли, возвращаем адрес корня искать в левом поддереве искать в правом поддереве
87 Как построить дерево поиска? { Процедура AddToTree – добавить элемент Вход: Tree - адрес корня, x - что добавляем } procedure AddToTree ( var Tree: PNode ; x: integer ); begin if Tree = nil then begin New(Tree); Tree^.data := x; Tree^.left := nil; Tree^.right := nil; Exit; end; if x < Tree^.data then AddToTree ( Tree^.left, x) else AddToTree ( Tree^.right, x); end; дерево пустое: создаем новый узел (корень) адрес корня может измениться добавляем к левому или правому поддереву Минимальная высота не гарантируется! !
88 Обход дерева 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
89 Обход дерева – реализация { Процедура LKP – обход дерева в порядке ЛКП ( левый – корень – правый ) Вход: Tree - адрес корня } procedure LKP(Tree: PNode ); begin if Tree = nil then Exit; LKP( Tree^.left ); write(' ', Tree^.data ); LKP( Tree^.right ); end; обход этой ветки закончен обход левого поддерева вывод данных корня обход правого поддерева Для рекурсивной структуры удобно применять рекурсивную обработку! !
90 Разбор арифметических выражений 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
91 Вычисление выражений Постфиксная форма: 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 =
92 Вычисление выражений Задача: в символьной строке записано правильное арифметическое выражение, которое может содержать только однозначные числа и знаки операций +-*\. Вычислить это выражение. Алгоритм: ввести строку; построить дерево; вычислить выражение по дереву. Ограничения: ошибки не обрабатываем; многозначные числа не разрешены; дробные числа не разрешены; скобки не разрешены.
93 Построение дерева Алгоритм: если first=last (остался один символ – число), то создать новый узел и записать в него этот элемент; иначе... среди элементов от first до last включительно найти последнюю операцию (элемент с номером k ); создать новый узел (корень) и записать в него знак операции ; рекурсивно применить этот алгоритм два раза: построить левое поддерево, разобрав выражение из элементов массива с номерами от first до k-1 ; построить правое поддерево, разобрав выражение из элементов массива с номерами от k+1 до last. 5 + 7 * 6 - 3 * 2 first last k k +1 k -1
94 Как найти последнюю операцию? Порядок выполнения операций умножение и деление; сложение и вычитание. 5 + 7 * 6 - 3 * 2 Нужно искать последнюю операцию с наименьшим приоритетом! ! Приоритет (старшинство) – число, определяющее последовательность выполнения операций: раньше выполняются операции с большим приоритетом: умножение и деление (приоритет 2 ); сложение и вычитание (приоритет 1 ).
95 Приоритет операции { Функция Priority – приоритет операции Вход: символ операции Выход: приоритет или 100, если не операция } function Priority ( c: char ): integer; begin case ( c ) of '+', '-': Result := 1; '*', '/': Result := 2; else Result := 100; end; end; сложение и вычитание: приоритет 1 умножение и деление: приоритет 2 это вообще не операция
96 Номер последней операции { Функция LastOperation – номер последней операции Вход: строка, номера первого и последнего символов рассматриваемой части Выход: номер символа - последней операции } function LastOperation ( Expr : string; first, last: integer): integer; var MinPrt, i, k, prt : integer; begin MinPrt := 100; for i :=first to last do begin prt := Priority ( Expr [ i ] ); if prt <= MinPrt then begin MinPrt := prt ; k := i ; end; end; Result := k; end; проверяем все символы вернуть номер символа нашли операцию с минимальным приоритетом
97 Построение дерева Структура узла type PNode = ^Node; Node = record data: char; left, right: PNode ; end; Создание узла для числа (без потомков) function NumberNode (c: char): PNode ; begin New(Result); Result^.data := c; Result^.left := nil; Result^.right := nil; end; возвращает адрес созданного узла один символ, число
98 Построение дерева { Функция MakeTree – построение дерева Вход: строка, номера первого и последнего символов рассматриваемой части Выход: адрес построенного дерева } function MakeTree ( Expr : string; first, last: integer): PNode ; var k: integer; begin if first = last then begin Result := NumberNode ( Expr [first] ); Exit; end; k := LastOperation ( Expr, first, last ); New(Result); Result^.data := Expr [k]; Result^.left := MakeTree ( Expr, first, k-1 ); Result^.right := MakeTree ( Expr, k+1, last ); end; осталось только число новый узел: операция
99 Вычисление выражения по дереву { Функция CalcTree – вычисление по дереву Вход: адрес дерева Выход: значение выражения } function CalcTree (Tree: PNode ): integer; var num1, num2: integer; begin if Tree^.left = nil then begin Result := Ord ( Tree^.data ) - Ord ('0'); Exit; end; num1 := CalcTree ( Tree^.left ); num2 := CalcTree ( Tree^.right ); case Tree^.data of '+': Result := num1+num2; '-': Result := num1-num2; '*': Result := num1*num2; '/': Result := num1 div num2; else Result := MaxInt ; end; end; вернуть число, если это лист вычисляем операнды (поддеревья) выполняем операцию некорректная операция
100 Основная программа { Ввод и вычисление выражения с помощью дерева } program qq ; var Tree: PNode ; Expr : string; { процедуры и функции } begin write(' Введите выражение > '); readln ( Expr ); Tree := MakeTree ( Expr, 1, Length( Expr ) ); writeln (' = ', CalcTree (Tree) ); end.
101 Дерево игры Задача. Перед двумя игроками лежат две кучки камней, в первой из которых 3, а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок?
102 Дерево игры 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
103 Задания «4»: «Собрать» программу для вычисления правильного арифметического выражения, включающего только однозначные числа и знаки операций +, -, *, /. «5»: То же самое, но допускаются также многозначные числа и скобки. «6»: То же самое, что и на «5», но с обработкой ошибок (должно выводиться сообщение).
Тема 7. Графы Динамические структуры данных (язык Паскаль)
105 Определения Граф – это набор вершин (узлов) и соединяющих их ребер (дуг). Направленный граф (ориентированный, орграф) – это граф, в котором все дуги имеют направления. Цепь – это последовательность ребер, соединяющих две вершины (в орграфе – путь ). Цикл – это цепь из какой-то вершины в нее саму. Взвешенный граф (сеть) – это граф, в котором каждому ребру приписывается вес (длина). 5 3 2 4 1 3 2 4 1 Дерево – это граф? ? Да, без циклов!
106 Определения Связный граф – это граф, в котором существует цепь между каждой парой вершин. k -c вязный граф – это граф, который можно разбить на k связных частей. Полный граф – это граф, в котором проведены все возможные ребра ( n вершин → n(n-1)/2 ребер ). 5 3 2 4 1 8 6 7 2 1 3 2 1 3 4
107 Описание графа Матрица смежности – это матрица, элемент M[i][j] которой равен 1, если существует ребро из вершины i в вершину j, и равен 0, если такого ребра нет. 5 3 2 4 1 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 1 2 3 4 5 1 2 3 4 5 5 3 2 4 1 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 1 2 3 4 5 1 2 3 4 5 Симметрия! ! Список смежности 2 3 4 1 4 5 1 1 2 5 2 4 1 2 3 4 5 2 3 4 4 5 5 1 2 3 4 5
108 Матрица и список смежности 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 2 1 5 3 4 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 5 3 4 2
109 Построения графа по матрице смежности 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 1 2 3 4 5 1 2 3 4 5 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 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 3 5 2 4 1 3 5 2 4
110 Как обнаружить цепи и циклы? Задача: определить, существует ли цепь длины k из вершины i в вершину j (или цикл длиной k из вершины i в нее саму ). M 2 [i][j] =1, если M[i][1]=1 и M[1][j]=1 или M[i][2]=1 и M[2][j]=1 или M[i][3]=1 и M[3][j]=1 строка i логическое умножение столбец j логическое сложение 1 3 4 2 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 1 2 3 4 1 2 3 4 M = или M[i][4]=1 и M[4][j]=1
111 Как обнаружить цепи и циклы? 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 1 3 4 2 1 2 3 4 1 2 3 4 M 2 [3][1] = 0 · 0 + 1 · 1 + 0 · 0 + 1 · 1 = 1 маршрут 3 - 2 - 1 маршрут 3 - 4 - 1
112 Как обнаружить цепи и циклы? 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 1 3 4 2 1 2 3 4 1 2 3 4 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 1 2 3 4 1 2 3 4 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1
113 Весовая матрица 5 3 2 4 1 3 5 7 4 6 8 5 3 2 4 1 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 1 2 3 4 5 1 2 3 4 5 0 7 3 5 ∞ ∞ 0 ∞ 4 8 3 ∞ 0 ∞ ∞ 5 ∞ ∞ 0 6 ∞ 8 ∞ ∞ 0 1 2 3 4 5 1 2 3 4 5
114 Задача Прима-Краскала Задача: соединить N городов телефонной сетью так, чтобы длина телефонных линий была минимальная. Та же задача: дан связный граф с N вершинами, веса ребер заданы весовой матрицей W. Нужно найти набор ребер, соединяющий все вершины графа ( остовное дерево ) и имеющий наименьший вес. 5 3 2 4 1 3 5 7 4 6 8 0 7 3 5 ∞ 7 0 ∞ 4 8 3 ∞ 0 ∞ ∞ 5 4 ∞ 0 6 ∞ 8 ∞ 6 0 1 2 3 4 5 1 2 3 4 5
115 Жадный алгоритм Жадный алгоритм – это многошаговый алгоритм, в котором на каждом шаге принимается решение, лучшее в данный момент. В целом может получиться не оптимальное решение (последовательность шагов)! ! Шаг в задаче Прима-Краскала – это выбор еще невыбранного ребра и добавление его к решению. 5 3 2 4 1 3 5 7 4 6 8 В задаче Прима-Краскала жадный алгоритм дает оптимальное решение! !
116 Реализация алгоритма Прима-Краскала Проблема: как проверить, что 1) ребро не выбрано, и 2) ребро не образует цикла с выбранными ребрами. Решение: присвоить каждой вершине свой цвет и перекрашивать вершины при добавлении ребра. 5 3 2 4 1 3 5 7 4 6 8 3 2 4 5 Алгоритм: покрасить все вершины в разные цвета; сделать N-1 раз в цикле: выбрать ребро ( i,j ) минимальной длины из всех ребер, соединяющих вершины разного цвета; перекрасить все вершины, имеющие цвет j, в цвет i. вывести найденные ребра. 4
117 Реализация алгоритма Прима-Краскала Структура «ребро»: type rebro = record i, j: integer; { номера вершин } end; const N = 5; var W: array[1..N,1..N] of integer; Color: array[1..N] of integer; i, j, k, min, col_i, col_j : integer; Reb : array[1..N-1] of rebro ; begin ... { здесь надо ввести матрицу W } for i:=1 to N do { раскрасить в разные цвета } Color[i] := i; ... { основной алгоритм – заполнение массива Reb } ... { вывести найденные ребра (массив Reb )} end. Основная программа: весовая матрица цвета вершин
118 Реализация алгоритма Прима-Краскала for k:=1 to N-1 do begin min := MaxInt ; for i :=1 to N do for j:=i+1 to N do if (Color[ i ] <> Color[j]) and (W[ i,j ] < min) then begin min := W[ i,j ]; Reb [k]. i := i ; Reb [k].j := j; col_i := Color[ i ]; col_j := Color[j]; end; for i :=1 to N do if Color[ i ] = col_j then Color[ i ] := col_i ; end; Основной алгоритм: нужно выбрать всего N-1 ребер цикл по всем парам вершин учитываем только пары с разным цветом вершин запоминаем ребро и цвета вершин перекрашиваем вершины цвета col_j
119 Сложность алгоритма Основной цикл: O(N 3 ) for k:=1 to N-1 do begin ... for i :=1 to N do for j:=i+1 to N do ... end; три вложенных цикла, в каждом число шагов <=N растет не быстрее, чем N 3 Требуемая память: var W: array[1..N,1..N] of integer; Color: array[1..N] of integer; Reb : array[1..N-1] of rebro ; O(N 2 ) Количество операций:
120 Кратчайшие пути (алгоритм Дейкстры) Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти кратчайшие расстояния от заданного города до всех остальных городов. Та же задача: дан связный граф с N вершинами, веса ребер заданы матрицей W. Найти кратчайшие расстояния от заданной вершины до всех остальных. присвоить всем вершинам метку ∞ ; среди нерассмотренных вершин найти вершину j с наименьшей меткой; для каждой необработанной вершины i : если путь к вершине i через вершину j меньше существующей метки, заменить метку на новое расстояние; если остались необработанны вершины, перейти к шагу 2; метка = минимальное расстояние. 7 5 3 2 4 1 6 10 15 11 6 9 2 9 14 Алгоритм Дейкстры ( E. W. Dijkstra, 1959)
121 Алгоритм Дейкстры 7 5 3 2 4 1 6 10 15 11 6 9 2 9 14 ∞ ∞ ∞ ∞ ∞ 0 7 5 3 2 4 1 6 10 15 11 6 9 2 9 14 ∞ ∞ 14 7 9 0 7 5 3 2 4 1 6 10 15 11 6 9 2 9 14 22 ∞ 14 7 9 0 7 5 3 2 4 1 6 10 15 11 6 9 2 9 14 20 ∞ 11 7 9 0 7 5 3 2 4 1 6 10 15 11 6 9 2 9 14 20 20 11 7 9 0 7 5 3 2 4 1 6 10 15 11 6 9 2 9 14 20 20 11 7 9 0
122 Реализация алгоритма Дейкстры Массивы: массив 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 5 3 2 4 1 6 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 1 2 3 4 5 6
123 Реализация алгоритма Дейкстры Основной цикл : если все вершины рассмотрены, то стоп. среди всех нерассмотренных вершин ( 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 1 2 3 4 5 6 Шаг 1: 7 5 3 2 4 1 6 10 15 11 6 9 2 9 14 22 ∞ 14 7 9 0
124 Реализация алгоритма Дейкстры 1 1 1 0 0 0 0 7 9 2 0 ∞ 1 1 0 0 0 2 0 2 a b c 1 2 3 4 5 6 Шаг 2: 7 5 3 2 4 1 6 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 1 4 3 4 5 6 Шаг 3 : 7 5 3 2 4 1 6 10 15 11 6 9 2 9 14 2 0 20 11 7 9 0 Дальше массивы не изменяются ! !
125 Как вывести маршрут? 1 1 1 1 1 1 0 7 9 2 0 20 1 1 0 0 0 2 5 2 a b c 1 2 3 4 5 6 Результат работа алгоритма Дейкстры: длины путей Маршрут из вершины 0 в вершину 4: 4 0 5 2 5 2 0 Сложность алгоритма Дейкстры: O(N 2 ) два вложенных цикла по N шагов Вывод маршрута в вершину i (использование массива c ) : установить z:=i ; пока c[i]<>x присвоить z:=c[z] и вывести z.
126 Алгоритм Флойда-Уоршелла Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти все кратчайшие расстояния, от каждого города до всех остальных городов. for k : = 1 to N for i : = 1 to N for j: = 1 to N if W[ i, j ] > W[ i, k ] + W[ k, j ] then 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 ! Нет информации о маршруте, только кратчайшие расстояния! !
127 Алгоритм Флойда-Уоршелла Версия с запоминанием маршрута: for i := 1 to N for j := 1 to N c[ i,j ] := i ; ... for k : = 1 to N for i : = 1 to N for j: = 1 to N if W[ i, j ] > W[ i, k ] + W[ k, j ] then begin W[ i, j ] : = W[ i, k ] + W[ k, j ] ; c [ i, j ] := c[ k,j ] ; end; i – ая строка строится так же, как массив c в алгоритме Дейкстры в конце цикла c[ i,j ] – предпоследняя вершина в кратчайшем маршруте из вершины i в вершину j c [i, j] := c[k,j] ; Какова сложность алгоритма? ? O(N 3 )
128 Задача коммивояжера Задача коммивояжера. Коммивояжер (бродячий торговец) должен выйти из первого города и, посетив по разу в неизвестном порядке города 2,3,... N, вернуться обратно в первый город. В каком порядке надо обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим? Это NP- полная задача, которая строго решается только перебором вариантов (пока) ! ! Точные методы: простой перебор; метод ветвей и границ; метод Литтла; … Приближенные методы: метод случайных перестановок ( Matlab ) ; генетические алгоритмы; метод муравьиных колоний; … большое время счета для больших N O(N!) не гарантируется оптимальное решение
129 Другие классические задачи Задача на минимум суммы. Имеется N населенных пунктов, в каждом из которых живет p i школьников ( i=1,..., N ). Надо разместить школу в одном из них так, чтобы общее расстояние, проходимое всеми учениками по дороге в школу, было минимальным. Задача о наибольшем потоке. Есть система труб, которые имеют соединения в N узлах. Один узел S является источником, еще один – стоком T. Известны пропускные способности каждой трубы. Надо найти наибольший поток от источника к стоку. Задача о наибольшем паросочетании. Есть M мужчин и N женщин. Каждый мужчина указывает несколько (от 0 до N ) женщин, на которых он согласен жениться. Каждая женщина указывает несколько мужчин (от 0 до M ), за которых она согласна выйти замуж. Требуется заключить наибольшее количество моногамных браков.
130 Конец фильма
