Динамічні структуры даних.

2 Динамические данные размер заранее неизвестен, определяется во время работы программы память выделяется во время работы программы нет имени? Проблема: как обращаться к данным, если нет имени? Решение: использовать адрес в памяти Следующая проблема: в каких переменных могут храниться адреса? как работать с адресами?

3 Статические данные переменная (массив) имеет имя, по которому к ней можно обращаться размер заранее известен (задается при написании программы) память выделяется при объявлении размер нельзя увеличить во время работы программы var x, y: integer; z: real; A: array[1..10] of real; str: string; var x, y: integer; z: real; A: array[1..10] of real; str: string;

4 Указатели Указатель – это переменная, в которую можно записывать адрес другой переменной (или блока памяти). Объявление: Как записать адрес: var pC: ^char; // адрес символа pI: ^integer; // адрес целой переменной pR: ^real; // адрес вещ. переменной var pC: ^char; // адрес символа pI: ^integer; // адрес целой переменной pR: ^real; // адрес вещ. переменной var m: integer; // целая переменная pI: ^integer; // указатель A: array[1..2] of integer; // массив... m; // адрес переменной m A[1]; // адрес элемента массива A[1] pI:= nil; // нулевой адрес var m: integer; // целая переменная pI: ^integer; // указатель A: array[1..2] of integer; // массив... m; // адрес переменной m A[1]; // адрес элемента массива A[1] pI:= nil; // нулевой ^ nil указатель адрес ячейки

5 Обращение к данным через указатель program qq; var m, n: integer; pI: ^integer; begin m := 4; pI 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. program qq; var m, n: integer; pI: ^integer; begin m := 4; pI 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. ^ «вытащить» значение по адресу

6 Что надо знать об указателях указатель – это переменная, в которой можно хранить адрес другой переменной; при объявлении указателя надо указать тип переменных, на которых он будет указывать, а перед типом поставить знак ^ ; перед именем переменной обозначает ее адрес; запись p^ обозначает значение ячейки, на которую указывает указатель p ; nil – это нулевой указатель, он никуда не указывает Нельзя использовать указатель, который указывает неизвестно куда (будет сбой или зависание)!

7 Динамические структуры данных Строение: набор узлов, объединенных с помощью ссылок. Как устроен узел: данные ссылки на другие узлы Типы структур: списки деревья графы nil односвязный двунаправленный (двусвязный) циклические списки (кольца) nil

8 Когда нужны списки? Задача (алфавитно-частотный словарь). В файле записан текст. Нужно записать в другой файл в столбик все слова, встречающиеся в тексте, в алфавитном порядке, и количество повторений для каждого слова. Проблемы: 1)количество слов заранее неизвестно (статический массив); 2)количество слов определяется только в конце работы (динамический массив). Решение – список. Алгоритм: 1)создать список; 2)если слова в файле закончились, то стоп. 3)прочитать слово и искать его в списке; 4)если слово найдено – увеличить счетчик повторений, иначе добавить слово в список; 5)перейти к шагу 2.

9 Что такое список: 1)пустая структура – это список; 2)список – это начальный узел (голова) и связанный с ним список. Списки: новые типы данных type PNode = ^Node; { указатель на узел } Node = record { структура узла } word: string[40]; { слово } count: integer; { счетчик повторений } next: PNode; { ссылка на следующий } end; type PNode = ^Node; { указатель на узел } Node = record { структура узла } word: string[40]; { слово } count: integer; { счетчик повторений } next: PNode; { ссылка на следующий } end; Новые типы данных: Адрес начала списка: var Head: PNode;... Head := nil; var Head: PNode;... Head := nil; Рекурсивное определение! ! ! nil Для доступа к списку достаточно знать адрес его головы! ! !

10 Задача: сделать что-нибудь хорошее с каждым элементом списка. Алгоритм: 1)установить вспомогательный указатель q на голову списка; 2)если указатель q равен nil (дошли до конца списка), то стоп; 3)выполнить действие над узлом с адресом q ; 4)перейти к следующему узлу, q^.next. Проход по списку var q: PNode;... q := Head; // начали с головы while q <> nil do begin // пока не дошли до конца... // делаем что-то хорошее с q q := q^.next; // переходим к следующему end; var q: PNode;... q := Head; // начали с головы while q <> nil do begin // пока не дошли до конца... // делаем что-то хорошее с q q := q^.next; // переходим к следующему end; Head nil q q

11 Добавление узла в начало списка NewNode Head nil 1) Установить ссылку нового узла на голову списка: NewNode^.next := Head; NewNode Head nil 2) Установить новый узел как голову списка: Head := NewNode;

Добавление узла после заданного 1) Установить ссылку нового узла на узел, следующий за p : NewNode^.next = p^.next; 2) Установить ссылку узла p на новый узел: p^.next = NewNode; NewNode p p nil NewNode p p nil Удаление узла q q Head p p nil Проблема: нужно знать адрес предыдущего узла q.

Проблема: нужно знать адрес предыдущего узла, а идти назад нельзя! Решение: найти предыдущий узел q (проход с начала списка). Добавление узла перед заданным NewNode p p nil Задача: вставить узел перед заданным без поиска предыдущего. Алгоритм: 1)поменять местами данные нового узла и узла p ; 2)установить ссылку узла p на NewNode. NewNode p p nil NewNode p p nil

type PNode = ^Node; { указатель на узел } Node = record { структура узла } word: string[40]; { слово } count: integer; { счетчик повторений } next: PNode; { ссылка на следующий } prev: PNode; { ссылка на предыдущий } end; type PNode = ^Node; { указатель на узел } Node = record { структура узла } word: string[40]; { слово } count: integer; { счетчик повторений } next: PNode; { ссылка на следующий } prev: PNode; { ссылка на предыдущий } end; 14 Двусвязные списки Структура узла: Адреса «головы» и «хвоста»: var Head, Tail: PNode;... Head := nil; Tail := nil; var Head, Tail: PNode;... Head := nil; Tail := nil; nextprev previous можно двигаться в обе стороны нужно работать с двумя указателями вместо одного nil Head Tail

15 Стек Стек – это линейная структура данных, в которой добавление и удаление элементов возможно только с одного конца (вершины стека). Stack = кипа, куча, стопка (англ.) LIFO = Last In – First Out «Кто последним вошел, тот первым вышел». Операции со стеком: 1)добавить элемент на вершину (Push = втолкнуть); 2)снять элемент с вершины (Pop = вылететь со звуком).

16 Пример задачи Задача: вводится символьная строка, в которой записано выражение со скобками трех типов: [], {} и (). Определить, верно ли расставлены скобки (не обращая внимания на остальные символы). Примеры: [()]{} ][ [({)]} Упрощенная задача: то же самое, но с одним видом скобок. Решение: счетчик вложенности скобок. Последовательность правильная, если в конце счетчик равен нулю и при проходе не разу не становился отрицательным. Можно ли решить исходную задачу так же, но с тремя счетчиками? ? ? [ ( { ) ] } (: [: {: [ ( { ) ] }[ ( { ) ] } [ ( { ) ] }[ ( { ) ] } ( ( ) ) ( ) ( ( ) ) ( ) ( ( ) ) ) ( ( ( ) ) ) ( ( ( ) ) ( ( ( ) ) (

17 Решение задачи со скобками Алгоритм: 1)в начале стек пуст; 2)в цикле просматриваем все символы строки по порядку; 3)если очередной символ – открывающая скобка, заносим ее на вершину стека; 4)если символ – закрывающая скобка, проверяем вершину стека: там должна быть соответствующая открывающая скобка (если это не так, то ошибка); 5)если в конце стек не пуст, выражение неправильное. [ ( ( ) ) ] { } [[ ( [ ( ( [ ( ( [ ( [{{

18 Системный стек (Windows – 1 Мб) Используется для 1)размещения локальных переменных; 2)хранения адресов возврата (по которым переходит программа после выполнения функции или процедуры); 3)передачи параметров в функции и процедуры; 4)временного хранения данных (в программах на языке Ассмеблер). Переполнение стека (stack overflow): 1)слишком много локальных переменных (выход – использовать динамические массивы); 2)очень много рекурсивных вызовов функций и процедур (выход – переделать алгоритм так, чтобы уменьшить глубину рекурсии или отказаться от нее вообще).

19 Очередь Очередь – это линейная структура данных, в которой добавление элементов возможно только с одного конца (конца очереди), а удаление элементов – только с другого конца (начала очереди). FIFO = First In – First Out «Кто первым вошел, тот первым вышел». Операции с очередью: 1)добавить элемент в конец очереди (PushTail = втолкнуть в конец); 2)удалить элемент с начала очереди (Pop).

20 Реализация очереди (массив) самый простой способ 1)нужно заранее выделить массив; 2)при выборке из очереди нужно сдвигать все элементы.

21 Реализация очереди (кольцевой массив) 1 2 Head Tail Сколько элементов можно хранить в такой очереди? ? ? Как различить состояния «очередь пуста» и «очередь полна»? ? ? 345

22 Реализация очереди (кольцевой массив) 1 Head Tail В очереди 1 элемент: Очередь пуста: Очередь полна: Head = Tail + 1 Head = ( Tail mod N) N размер массива 123 Head = Tail + 2 Head = ( Tail+1) mod N N 123 Head = Tail

23 Деревья директор гл. инженер гл. бухгалтер инженер бухгалтер Что общего во всех примерах? ? ?

24 Деревья Дерево – это структура данных, состоящая из узлов и соединяющих их направленных ребер (дуг), причем в каждый узел (кроме корневого) ведет ровно одна дуга. Корень – это начальный узел дерева. Лист – это узел, из которого не выходит ни одной дуги. корень Какие структуры – не деревья?

25 Деревья Предок узла x – это узел, из которого существует путь по стрелкам в узел x. Потомок узла x – это узел, в который существует путь по стрелкам из узла x. Родитель узла x – это узел, из которого существует дуга непосредственно в узел x. С помощью деревьев изображаются отношения подчиненности (иерархия, «старший – младший», «родитель – ребенок»). ! ! Сын узла x – это узел, в который существует дуга непосредственно из узла x. Брат узла x (sibling) – это узел, у которого тот же родитель, что и у узла x. Высота дерева – это наибольшее расстояние от корня до листа (количество дуг).

26 Обход дерева Обход дерева – это перечисление всех узлов в определенном порядке. Обход ЛКП («левый – корень – правый»): Обход ПКЛ («правый – корень – левый»): Обход КЛП («корень – левый – правый»): Обход ЛПК («левый – правый – корень»):

27 Дерево игры Задача. Перед двумя игроками лежат две кучки камней, в первой из которых 3, а во второй – 2 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или увеличивает в 3 раза число камней в какой-то куче, или добавляет 1 камень в какую-то кучу. Выигрывает игрок, после хода которого общее число камней в двух кучах становится не менее 16. Кто выигрывает при безошибочной игре – игрок, делающий первый ход, или игрок, делающий второй ход? Как должен ходить выигрывающий игрок?

28 Дерево игры 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 При правильной игре выиграет игрок 2! ! ! игрок 1 игрок 2 9, 2 4, 3 ключевой ход игрок 1 выиграл игрок 1

29 Определения Граф – это набор вершин (узлов) и соединяющих их ребер (дуг). Направленный граф (ориентированный, орграф) – это граф, в котором все дуги имеют направления. Цепь – это последовательность ребер, соединяющих две вершины (в орграфе – путь). Цикл – это цепь из какой-то вершины в нее саму. Взвешенный граф (сеть) – это граф, в котором каждому ребру приписывается вес (длина) Дерево – это граф? ? ? Да, без циклов!

30 Определения Связный граф – это граф, в котором существует цепь между каждой парой вершин. k -cвязный граф – это граф, который можно разбить на k связных частей. Полный граф – это граф, в котором проведены все возможные ребра ( n вершин n(n-1)/2 ребер)

31 Описание графа Матрица смежности – это матрица, элемент M[i][j] которой равен 1, если существует ребро из вершины i в вершину j, и равен 0, если такого ребра нет Симметрия! ! ! Список смежности

32 Матрица и список смежности

33 Построения графа по матрице смежности

34 Как обнаружить цепи и циклы? Задача: определить, существует ли цепь длины 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 логическое сложение M = или M[i][4]=1 и M[4][j]=1

35 Как обнаружить цепи и циклы? M 2 = M M Логическое умножение матрицы на себя: матрица путей длины M2 =M2 = = M 2 [3][1] = 0·0 + 1·1 + 0·0 + 1·1 = 1 маршрут маршрут 3-4-1

36 Как обнаружить цепи и циклы? M 3 = M 2 M Матрица путей длины 3: M3 =M3 = = на главной диагонали – циклы! M4 =M4 = =

37 Весовая матрица Весовая матрица – это матрица, элемент W[i,j] которой равен весу ребра из вершины i в вершину j (если оно есть), или равен, если такого ребра нет

38 Задача Прима-Краскала Задача: соединить N городов телефонной сетью так, чтобы длина телефонных линий была минимальная. Та же задача: дан связный граф с N вершинами, веса ребер заданы весовой матрицей W. Нужно найти набор ребер, соединяющий все вершины графа (остовное дерево) и имеющий наименьший вес

39 Жадный алгоритм Жадный алгоритм – это многошаговый алгоритм, в котором на каждом шаге принимается решение, лучшее в данный момент. В целом может получиться не оптимальное решение (последовательность шагов)! ! ! Шаг в задаче Прима-Краскала – это выбор еще невыбранного ребра и добавление его к решению В задаче Прима-Краскала жадный алгоритм дает оптимальное решение! ! !

40 Реализация алгоритма Прима-Краскала Проблема: как проверить, что 1) ребро не выбрано, и 2) ребро не образует цикла с выбранными ребрами. Решение: присвоить каждой вершине свой цвет и перекрашивать вершины при добавлении ребра Алгоритм: 1)покрасить все вершины в разные цвета; 2)сделать N-1 раз в цикле: выбрать ребро (i,j) минимальной длины из всех ребер, соединяющих вершины разного цвета; перекрасить все вершины, имеющие цвет j, в цвет i. 3)вывести найденные ребра. 44

41 Кратчайшие пути (алгоритм Дейкстры) Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти кратчайшие расстояния от заданного города до всех остальных городов. Та же задача: дан связный граф с N вершинами, веса ребер заданы матрицей W. Найти кратчайшие расстояния от заданной вершины до всех остальных. 1)присвоить всем вершинам метку ; 2)среди нерассмотренных вершин найти вершину j с наименьшей меткой; 3)для каждой необработанной вершины i : если путь к вершине i через вершину j меньше существующей метки, заменить метку на новое расстояние; 4)если остались необработанны вершины, перейти к шагу 2; 5)метка = минимальное расстояние Алгоритм Дейкстры (E.W. Dijkstra, 1959)

42 Алгоритм Дейкстры