Структуры и алгоритмы компьютерной обработки данных

Лекция №1 Введение Рассмотрим способы представления базовых структур данных, которые имеют широкое практическое применение. Массивы Массивы данных широко используются в языках программирования для представления объектов, состоящих из определенного числа компонент (элементов массива) одного и того же типа (класса). Очень часто базовой операции над массивом – индексации – бывает достаточно для решения задачи. Например, задача кодирования текста, в которой необходимо каждую букву текста представить некоторым целочисленным кодом. Строгая постановка задачи: Необходимо по заданному тексту (строке) получить массив целых чисел той же длины, в котором каждому символу исходной строки соответствует его код. Очевидно наиболее удобный способ решения такой задачи: составление кодирующей таблицы – массива, в котором каждому символу сопоставлен некоторый целочисленный код. Если считать, что коды исходных символов лежат в диапазоне от 1до 255, то кодирующая таблица записывается так: final static int codeTable={…}; //элементы массива не показаны Функция кодирования текста с помощью этой таблицы использует только операцию индексации массива: static void doCode(String source,int dest[]) { for(int i=0;i hBound) throw new IndexOutOfBoundsException("Индекс"+i+"выходит за границы массива "); return array[i-lBound]; } /** * */ static final int tab[]={5,4,7,8,4,3,6,8,2}; static final Table codeTable=new Table(32,255,tab); /** * */ static void doCode(String source,int dest[]) throws IndexOutOfBoundsException { for(int i=0;i=size) throw new IndexOutOfBoundsException("Индекс "+i+" выходит за границу массива"); return array[i]; } public void enlarge(int delta) { if( (size+=delta)>maxSize ) { maxSize=size; Object newArray[]=new Object[maxSize]; for(int i=0; isize?0:size-delta); } public void resize(int delta) { if(delta>0) enlarge(delta); else if(delta<0) shrink(-delta); } public void add(Object e) { resize(1); array[size-1]=e; } /** * */ static final Object tab[]={ new Integer(5),new Integer(4),new Integer(6),new Integer(8), new Integer(9), new Integer(5),new Integer(4),new Integer(6),new Integer(8), new Integer(9), new Integer(5),new Integer(4),new Integer(6),new Integer(8),new Integer(9) }; static final DynArray codeDynArray=new DynArray(tab.length,255,tab); /** * */ static void doCode(String source,int dest[]) throws IndexOutOfBoundsException { for(int i=0;i;<есть еще элементы>;<перейти к следующему элементу>) { <взять очередной элемент>; <обработать очередной элемент>; } Один из способов организации внешней итерации – присвоение каждому элементу списка определенного номера и использование функции, которая выдает элементы списка по номеру (getElementAt(int index)). for (int i=0;i; } Такой способ предлагается в стандартных классах Vector, LinkedList и т.п. в пакете java.util. Однако, если в списке не предусмотрена нумерация (например, односвязный список, в котором элементы связаны лишь ссылками от одного к другому), то требуется более эффективный способ организации внешней итерации. Для этого используется специальный класс, отдельный от класса IntList, в котором сосредоточены все операции по организации итерации. В пакете java.util имеются стандартные интерфейсы для классов, реализующих итераторы, – java.util.Iterator, java.util.Enumeration. public interface Iterator { boolean hasNext(); Object next(); void remove(); } public interface Enumeration { boolean hasMoreElements(); Object nextElement(); } Если в классе IntList определить метод iterator(), то суммирование элементов списка будет выглядеть так: IntList lst;… Int sum=0; for ( Iterator i=lst.itertor(); lst.hasMode(); ) { sum+=((Integer)lst.next()).intValue(); } Для определения метода iterator() в классе IntList необходимо определить внутренний новый класс, реализующий итератор. public static class IntListIterator implements java.util.Iterator { private ListItem current; public IntListIterator(IntList lst) { current=first;} public boolean hasNext() { return current!=null; } public Object next() { if(!hasNext()) return null; Integer item = new Integer(current.getItem()); current = current.getNext(); return item; } public void remove() {} }; public java.util.Iterator iterator() { return new IntListIterator(this); } Лекция №3 Деревья Элементы могут образовывать и более сложную структуру, чем линейный список. Часто данные, подлежащие обработке, образуют иерархическую структуру, подобную изображенной на рис. 1.3, которую необходимо отобразить в памяти компьютера и, соответственно, описать в структурах даннных. Каждый элемент такой структуры может содержать ссылки на элементы более низкого уровня иерархии, а может быть, и на объект, находящийся на более высоком уровне иерархии. Рис. 1.3. Структура Если абстрагироваться от конкретного содержания объектов, то получиться математический объект, называемый деревом (точнее, корневым деревом). Определение. Корневым деревом называется множество элементов, в котором выделен элемент, называемый корнем дерева, а все остальные элементы разбиты на несколько непересекающихся подмножеств, называемых поддеревьями ис­ходного дерева, каждое из которых, в свою очередь, есть дерево. При представлении в памяти компьютера элементы дерева (узлы) связывают между собой таким образом, чтобы каждый узел (который согласно определению обязательно является корнем некоторого дерева или поддерева) был связан с корнями своих поддеревьев. Наиболее распространенными спосо­бами представления дерева являются следующие три (или их комбинации). При первом способе каждый узел (кроме корня) содержит указатель на породивший его узел, т. е. на элемент, находящийся на более высоком уровне иерархии. Для корня дерева соответствующий указатель будет пустым. При таком способе представления, имея информацию о местоположении неко­торого узла, можно, прослеживая указатели, подниматься на более высокие уровни иерархии. К сожалению, этот способ представления непригоден, ес­ли требуется не только "подниматься вверх" по дереву, но и "спускаться вниз", и нет возможности независимо получать информацию о местополо­жении узлов дерева. Тем не менее, такое представление дерева иногда ис­пользуется в алгоритмах, где прохождение узлов всегда осуществляется в вос­ходящем порядке. Преимуществом такого способа представления дерева является то, что в нем используется минимальное количество памяти, причем практически вся она эффективно используется для представления связей. Второй способ представления применяют, если каждый узел дерева имеет не более двух (в более общем случае — не более к) поддеревьев. Тогда можно включить в представление узла указатели на корни поддеревьев. В этом слу­чае дерево называют двоичным (бинарным), а два поддерева каждого узла называют соответственно левым и правым поддеревьями этого узла. Разуме­ется, узел может иметь только одно — левое или правое — поддерево (эти две ситуации в бинарных деревьях обычно считаются различными) или мо­жет вообще не иметь поддеревьев (и в этом случае узел называется конце­вым узлом или листом дерева). При этом способе представления достаточно иметь ссылку на корень дерева, чтобы получить доступ к любому узлу дере­ва, спускаясь по указателям, однако память при таком способе представле­ния используется не столь эффективно. Описание класса бинарного дерева, содержащего произвольные объекты класса Оbject в узлах, может выглядеть, как представлено в листинге 1.5 (методы не показаны). Листинг 1.5. Определение класса Tree public class Tree { // Определение класса узла дерева public static class Node { public Object item; // содержимое узла public Node left = null; // указатель на левое поддерево public Node right = null; // указатель на правое поддерево // Конструкторы узла дерева: // конструктор листа public Node(Object item) { this.item = item;} // Конструктор промежуточного узла public Mode (Object item. Node left, Node right) { this.item = item; this.left = left; this.right = right; } } Node root = null; // корень дерева } Здесь корень дерева представлен ссылкой root на элемент класса Node (узел), а каждый узел, в свою очередь содержит две ссылки на корни левого и правого поддерева (left и right соответственно). Если бинарное дерево имеет N узлов, то при таком способе представления всегда остаются пустыми более половины указателей (точнее, из 2N указате­лей пустыми будут N+1 указатель, докажите это!). Тем не менее, такое пред­ставление является настолько удобным, что потерями памяти обычно пре­небрегают. Третий способ представления состоит в том, что в каждом элементе содер­жатся два указателя, причем один из них служит для представления списка поддеревьев, а второй для связывания элементов в этот список. Формально описание класса для этого представления может быть тем же самым, что и для случая бинарного дерева, но смысл содержащихся в этом описании ука­зателей меняется. При третьем способе представления деревьев часто ис­пользуется генеалогическая терминология: узлы, содержащиеся в поддеревь­ях каждого узла, называются его потомками, а корни этих поддеревьев, расположенные на одном уровне иерархии, называют братьями. Эту терми­нологию можно отразить в описании класса, и тогда поля left и right бу­дут называться son и brother соответственно. Рекурсивную природу дерева, отраженную в его определении, можно выра­зить более явно и в описании класса, если в описании ссылок на поддере­вья вместо класса Node использовать описатель Tree. Тогда и многие опера­ции над деревом могут быть просто выражены в виде рекурсивных функций. Определим, например, метод для вычисления высоты бинарного дерева. Вы­сотой бинарного дерева назовем максимальное число узлов, которое может встретиться на пути из корня дерева в некоторый другой узел, при условии, что этот путь проходит только по связанным между собой узлам и никогда не проходит дважды через один и тот же узел. Будем для удобства считать, что пустой указатель представляет вырожденное "пустое" дерево, высота которого равна нулю. В этом случае высота бинарного дерева может быть выражена следующей формулой: где t — исходное дерево, — левое и правое поддеревья исходного дерева; null — пустое дерево. Тогда определение класса с методом height, реализующим вычисление высоты дерева, может выглядеть, как представле­но в листинге 1.6. Листинг 1.6. Рекурсивное определение дерева public class Tree { private Object item; private Tree left = null; private Tree right = null; public int height ( ) { int hl = (left = = null ? 0 : left .height ()); int hr = (right = = null ? 0 : right . height ()); return Math.max (hl, hr) + 1; } } Тем не менее, в общем случае удобнее пользоваться ранее приведенным представлением дерева с явным выделением структуры узла. Тогда метод для вычисления высоты дерева в контексте представленного в листинге 1.5 опи­сания класса запишется несколько иначе: public int height () { return height (root) ; } private int height (Node n) { if (n == null) return 0; else return Math. max (height (n.left) , height (n. right) ) + 1; } Здесь описание метода выполнено с помощью вспомогательной рекурсив­ной функции, аргументом которой является указатель узла того поддерева, высоту которого требуется вычислить. Иногда структура обрабатывающей дерево рекурсивной функции не так проста. Рассмотрим, например, следующую задачу. Пусть надо определить функцию, вычисляющую число узлов бинарного дерева, расположенных на i - м уровне при заданном значении i > 0. Заметим, что в пустом дереве таких вершин нет вовсе, а в непустом дереве требуемое количество узлов можно определить рекурсивно: при i = 1 существует лишь одна вершина — корень дерева, а при i > 1 число узлов, расположенных на i-м уровне дерева, равно сумме количества узлов, расположенных в его поддеревьях (левом и правом) на ( i — 1)-м уровне. Отсюда сразу же следует определение функции (считаем его также выпол­ненным в контексте описания класса Tree, приведенного в листинге 1.5). public int nodesOnLevel (int level} { return nodesOnLevel (root, level); } private int nodesOnLevel (Node n, int level) { if (n == null) return 0; if (level == 1) return 1; return nodesOnLevel (n. left, level-1) + nodesOnLevel (n. right, level-1 } ; } Так же, как и в случае списков, важной проблемой является итерация (обход) дерева. Если в случае списков обычно обход выполняется в естест­венном порядке (от начала списка к концу), в крайнем случае, можно рас­смотреть еще обход элементов списка в противоположном направлении - от конца к началу, то в случае дерева существует много порядков обхода его узлов, большинство из которых имеет свое самостоятельное значение и применяется в различных алгоритмах. Здесь для примера приведем лишь один способ обхода дерева — левосторонний. Для реализации обхода опре­делим внутренний итератор. При левостороннем обходе сначала полностью обходится левое поддерево исходного дерева (также в левостороннем поряд­ке, разумеется, если это дерево не пусто), затем проходится корень дерева, а затем правое поддерево также обходится в левостороннем порядке. Как и в случае списков сначала напишем интерфейс для определения посе­щения узла дерева. public interface Visitor { void visit (Object item) ; } Заметим, что фактически это тот же самый интерфейс, который использо­вался нами для «посещения» элементов списка. Теперь собствен­но операция обхода может быть определена с помощью рекурсивной функ­ции, например, следующим образом. public void left2right (Visitor visitor) { left2right (root, visitor); } private void left2right (Node n, Visitor visitor) { if (n != null) { left2right (n. left, visitor); visitor. visit (n.item); left2right (n. right, visitor); } } Применим, например, функцию обхода дерева с помощью внутреннего итератора для подсчета числа его узлов. В этом случае аргумент visitor должен лишь добавлять единицу к общему количеству уже сосчитанных узлов. Для этого определим дополнительно класс counter, реализующий интерфейс Visitor. public class Counter implements Visitor { int counter = 0; public void visit (Object o) { counter++; } public int getCounter() { return counter; } } Вот как теперь будет выглядеть программа для заданного дерева tree. public static void main (String args[]) { Tree tree = new Tree ( ) ; /* Где-то здесь формируется дерево tree... */ Counter counter = new Counter (); tree.left2right (counter) ; // обход дерева с посещением всех его узлов System.out.println ( "Всего узлов в дереве: " + counter.getCounter ()); } Иногда используются и более экзотические способы представления деревь­ев. Например, в некоторых случаях связи между узлами дерева можно вооб­ще не представлять с помощью указателей, а "вычислять", если узлы дерева образуют регулярную структуру, не меняющуюся или меняющуюся очень мало в процессе работы с деревом. Рассмотрим пример. Пусть узлы бинарного дерева пронумерованы, начиная с корня и далее вниз по иерархическим уровням, как показано на рис. 1.4. Рис. 1.4. Дерево с узлами, пронумерованными по уровням сверху вниз При этом узлы расположены настолько плотно, что предком узла с номером i всегда является узел с номером i/2. В этом случае узлы дерева можно рас­положить в массиве, причем местоположение каждого узла будет задано его индексом в массиве, а максимальное число узлов указывается сразу же при создании дерева. Представление такого дерева описано в листинге 1.7. Дере­во, определенное в этом листинге, обладает следующим свойством: каждый узел дерева содержит целое число, меньшее, чем значения, хранящиеся в поддеревьях этого узла. Таким образом, минимальное число всегда находит­ся в корне дерева. Такое дерево иногда называют «пирамидой». Класс Heap определяет такое дерево вместе с операцией insert добавления нового значения в дерево. Сначала новое значение добавляется в качестве последнего узла дерева, но если оно оказывается меньше, чем значения, расположенные выше по дереву, то оно «всплывает» наверх до тех пор, пока не окажется минимальным среди всех узлов поддерева, в корне которого это значение находится. В процессе работы операция insert для каждого узла определяет индекс его «родителя» и затем выясняет, надо ли продвигать новое значение дальше по направлению к вершине «пирамиды». Для сравнения двух элементов класса Integer используется операция compareTo, определенная для любых объек­тов, которые можно сравнивать по величине друг с другом (точнее, для объектов, класс которых реализует интерфейс Comparable). Выражение objl .compareTo(obj2) будет: • меньше нуля, если объект objl «меньше» объекта obj2; • равно нулю, если объекты равны; • больше нуля, если объект objl «больше» объекта obj2. Разумеется, для объектов класса Integer результат такого сравнения совпа­дает с результатом обычного сравнения значений. Листинг 1.7. Представление «пирамиды» в виде массива public class Heap { int count =0; // число узлов дерева Object items[]; // массив, представляющий узлы дерева // Конструктор пирамиды заданного максимального размера public Heap(int size) { items = new Object[size]; } // Операция вставки нового элемента в пирамиду public void insert(int n) throws NoMoreSpace { // Проверим, есть ли еще место в массиве if (count >= items.length) { throw new NoMoreSpace(); } // Создаем новый элемент Integer newltem = new Integer(n); int curIndex = count++; // индекс текущей позиции в пирамиде int parentIndex; // индекс «родителя» // Цикл «всплытия» элемента while (curIndex>0 && newItem.corapareTo(items[parent = curIndex / 2] ) < 0) { // Сдвигаем элемент вниз... items[curIndex] = items[parent]; // и переходим к элементу, лежащему выше в пирамиде curIndex = parent; } // Помещаем новый элемент на свое место items[curIndex] = newItem; } } Лекция №4 Множества Множество – это составной объект, который содержит компоненты одного и того же класса. В отличие от массива, над множеством определены совсем другие операции. Во множестве порядок элементов несущественен. Основная операция – проверка принадлежности элемента множеству. Другие операции – теоретико-множественные операции объединения и пересечения множеств, добавление элементов в множество, определение мощности множества. Для массива тоже можно определить такие операции, но они будут недопустимо долго. Эффективная реализация множества подразумевает , что элементы множества не храняться, а храниться только информация о принадлежности элементов множеству. Это возможно, когда элементы множества достаточно просты, а максимально возможное число элементов не слишком велико. Каждый из возможных элементов множества кодируют одним битом. Для представления множества формируют битовую шкалу, то есть последовательность двоичных элементов, каждый из которых определяет, присутствует ли в множетсве некоторый элемент. Например. Пусть используются множество русских строчных букв. Экономный способ кодирования – диапазон (0,32). В расширенной кодировке Windows-1251 коды русских строчных букв расположены в диапазоне (1072,1105) кроме 1104. Новый код символа – код символа – 1072 (если получиться 33 – дополнительно вычитается 1). При таком способе кодирования гласные буквы а,е,ё,и,о,у,ы,э,ю,я будут иметь коды 0,5,32,8,14,19,27,29,30,31. Тогда битовая шкала: 1 00001001 00000100 00100000 00101111 Байты 00100001 01000001 00001000 11101000 00000001 Байт 0 Байт 1 Байт 2 Байт 3 Байт 4 Побитовое сложение | - объединение множеств Побитовое умножение & - пересечение множеств С помощью операций побитового сдвига получают байт с единицей, расположенной в нужном разряде. Добавление в байт bt единичного бита, записанного а разряде n: bt | = (1<max) { minElem=max; maxElem=min; } else { minElem=min; maxElem=max; } int num=maxElem-minElem+1; int numBytes=(num+7)/8; elems=new byte[numbytes]; } // проверка принадлежности элемента множеству public boolean has(int n) throws IndexOutOfBoundsException { if(n>maxElem || n=minElem) { int bit=n-minElem; elems[bit/8]|=(1<<(bit%8)); } else { throw new IndexOutOfBoundsException(“ошибка”); } return this; } // добавление множества к множеству public Set disjunct(Set other) throws IndexOutOfBoundsException { if(other.minElem!=minElem || other.maxElem!=maxElem) throw new IndexOutOfBoundsException(“ошибка”); for(int i=0;i=minElem) { int bit=n-minElem; elems[bit/8]&=~(1<<(bit%8)); } else throw new IndexOutOfBoundsException(“ошибка”); return this; } // Обращение (нахождение дополнения) public Set inverse() { for(int i=0;i неориентированного графа. При программировании задач обработки сетевых структур требуется решить вопрос о представлении графа структурами данных языка программирова­ния. Выбор представления графа определяется прежде всего тем, какие ал­горитмы обработки графов используются, а также соображениями экономии памяти при обработке очень больших графов или в условиях жесткого ли­мита памяти. Ниже приводится несколько способов представления графов, причем для ка­ждого способа указано, для каких алгоритмов он подходит, а также дана при­близительная оценка занимаемой памяти. Везде далее считается, что число вершин графа N= card(V) и число дуг (или ребер) графа М= card(E) — вели­чины постоянные. Структуру графа можно описать, сопоставив каждой вершине множество дуг, выходящих из нее, причем каждая дуга, выходящая из вершины А, идентифицируется своим концом — номером вершины, в которую эта дуга входит. Описанное представление графа будем называть S-графом (от англ. set— множество). Будем считать, что множество целых чисел в диапа­зоне от 0 до N представлено объектом класса Set. Тогда S-граф может быть описан следующим классом (листинг 1.9). Листинг 1.9. Определение S-графа public class SGraph { Set[] graph; public SGraph(int n) { graph = new Set [n] ; for (int i = 0; i < n; i++) { graph[i] = new Set(0, n-I); } } } Принадлежность дуги (А, В) графу может быть легко проверена с помощью следующего метода. public boolean has(int a, int b) throws IndexOutOfBcundsException { return graph[a].has(b); } При задании неправильных номеров вершин исключительная ситуация indexOutofBoundsException возникнет либо из-за неправильного индекса в массиве, либо из-за возбуждения ее методом has класса set. Легко описать методы для добавления иди удаления дуги при таком пред­ставлении графа, достаточно лишь добавить или удалить определенный эле­мент в соответствующем множестве: public void add(int u, int v) { graph[u].disjunct(v); } public void remove(int u, int v) {graph[u].remove(v); } Несколько сложнее решается задача подсчета числа дуг, инцидентных дан­ной вершине. Если считать, что класс Set содержит метод card для подсчета числа элементов множества (мощность множества), то число выходящих из данной вершины дуг легко получить с помощью выражения graph[a].card(), однако число входящих в вершину дуг может быть полу­чено только путем перебора всех вершин графа: public int cardIn(int v) { int s = 0; for (int w = 0; w < graph.length; w++) { if (has(w, v)) s++; } return s; } } Еще один распространенный способ представления графа — это представ­ление в виде матрицы смежности размером NxN. В этой матрице в элементе с индексами (/, j) записывается информация о дугах, ведущих из вершины с номером i в вершину с номером j. В важном частном случае простого графа, т. е. в котором каждая упорядоченная пара вершин соединена не более, чем одной дугой, и отсутствуют дуги вида (А, А), элементы матрицы могут при­нимать значения 0 или 1 в зависимости от того, существует ли соответст­вующая дуга. Ясно, что такое представление самым тесным образом связано с представлением, описанным выше в определении класса SGraph. Представление в виде матрицы смежности будем называть M-графом. Удоб­но связывать с матрицей смежности информацию о нагрузке на дуги. В этом случае элементом матрицы будет либо значение нагрузки на соответ­ствующую дугу, либо некоторое стандартное значение, говорящее об отсут­ствии дуги. Если, например, граф моделирует транспортную сеть, в которой нагрузка на дугу представляет расстояние между пунктами, соединенными этой дугой, то признаком отсутствия дуги удобно сделать значение 0 или, напротив, максимально возможное целое (Integer.max_value), смотря по тому, что окажется более удобным в используемом алгоритме. В общем виде, если тип нагрузки представлен значениями класса W, то класс, пред­ставляющий M-граф, может быть описан следующим образом. Листинг 1.10. Определение M-графа public class MGraph { W graph[][]; public MGraph(int n) { graph = new W[n][n];} public void add(int u, int v) { graph[u][v] = 1;} public void remove(int u, int v) { graph[u][v] = 0;} } Поскольку представление M-графа очень близко к представлению S-графа, то и операции над M-графом выполняются практически с той же степенью эффективности, что и для S-графа. Удобными и эффективно реализуемыми операциями над M-графом являются операции проверки наличия дуги и значения ее нагрузки, добавления и удаления дуг, изменение нагрузки. Менее эффективными операциями будут операции подсчета или перебора дуг, инцидентных заданной вершине. Между тем, во многих алгоритмах именно это является самой часто используемой операцией. Структура графа может меняться крайне редко, а вот исследоваться эта структура будет достаточно часто. В этом случае представление графа в виде матрицы смежности будет неудобным. Еще одно соображение. Если число вершин графа велико, то матрица смежности будет занимать достаточно много места. В то же время в графе количество дуг чаще всего существенно меньше NxN, так что большинство элементов матрицы смежности будут пустыми. В этом случае более удобным будет представление, в котором с каждой вершиной графа связывается спи­сок исходящих из нее дуг. Каждая дуга может быть представлена номером вершины, в которую эта дуга входит, а в случае нагруженного графа может также содержать значение нагрузки на дугу. Соответствующее представление будем называть L-графом (от англ. list — список). В листинге 1.11 приведено возможное описание класса для ненагруженного L-графа. Листинг 1.11. Определение L-графа public class LGraph { // Класс Arc представляет дугу, ведущую в узел end static class Arc { int end; // номер узла, в который входит эта дуга public Arc(int e) { end = е; } }; ObjectList[] graph; // массив списков дуг public LGraph(int n) { graph = new ObjectList[n]; for (int i = 0; i < graph.length; i++) { graph[i] = new ObjectList();} } } В этом определении используется класс ObjectList. Будем считать, что элементами этого спи­ска будут объекты класса Arc, определенного выше внутри класса LGraph. Например, чтобы добавить дугу (u, v) в граф, надо добавить в список дуг, выходящих из вершины и, дугу, входящую в вершину v. public void add(int u, int v) { graph[u].addLast(new Arc(v)); } Удаление дуги при таком представлении не удается реализовать столь же просто. Для этого надо просмотреть соответствующий список, найти в нем нужную дугу и удалить ее из списка. Впрочем, если определить операцию сравнения дуг на равенство (equals), то можно воспользоваться ею и для удаления нужной дуги: static class Arc { int end; // номер узла, в который входит эта дуга public Arc(int e) { end = е; } public boolean equals(Arc arc) { return arc.end == this.end;} public void remove(int u, int v) { graph[u].remove(new Arc(v));} } Представление графа в виде совокупности списков дуг становится неудоб­ным в тех случаях, когда наиболее часто используются операции проверки наличия или модификации конкретной дуги, т. е. как раз те операции, ко­торые наиболее эффективно реализуются для S-графов и M-графов. Иногда используются и другие представления графов, например, для случая очень разреженных графов, когда при большом количестве N вершин графа число дуг не только существенно меньше NxN, но и меньше N. Одним из таких представлений является представление в виде списка дуг, когда все дуги графа собраны в единый список, в каждом элементе которого записана информация об обоих концах дуги, а также, возможно, о нагрузке на дугу. Другим возможным представлением графа является матрица инцидентности, содержащая N строк и М столбцов, в которой элемент с индексами (i, j) ра­вен единице, если i-я вершина инцидентна j-му ребру, и нулю — в против­ном случае. В последнем примере речь идет о неориентированном графе, поскольку в описанном представлении матрицы инцидентности не содер­жится информации о направленности дуги, однако это представление легко модифицировать и для случая ориентированного графа. В заключение этой главы приведем функции преобразования, которые мог­ли бы использоваться для изменения представления графа. Каждая из этих функций требует времени, пропорционального NxN или М. Это означает, что если время работы некоторого алгоритма на графе имеет порядок слож­ности не меньше NxN, то скорость его работы практически не зависит от способа представления графа, поскольку всегда можно перед началом рабо­ты выполнить нужное преобразование без существенной потери эффектив­ности основного алгоритма. Каждая из функций считается определенной внутри того класса, который представляет исходный граф, а для построения графа в целевом представле­нии используются методы добавления дуг, определенные в классе результи­рующего графа. Листинг 1.12. Функции преобразования представлений графов public class LGraph { /* Функция строит S-граф по заданному значению L-графа */ public SGraph toSGraphO { SGraph g = new SGraph{graph.leng-h); for (int n = 0; n < graph.length; n++) { for (iterator i = graph [p.] . iterator (); i.hasNext () ; ) { Arc nextArc = (Arc) i.next () ; g.add(n, nextArc.end); } } return O; } } public class SGraph { /*Функция строит М-граф по заданному значению S-графа */ public MGraph toMGraphO { MGraph g = new MGraph(graph.length); for (int n = 0; n < graph.length; n++) { for (Iterator i = graph[n].iterator(); i.hasNextО; ) { g.add(n, ((Integer)i.next()).intValue()); } } return g; } } public class MGraph { /*Функция строит L-граф по заданному значению М-графа */ public LGraph tcLGraph() { LGraph g = new LGraph(graph. length); for (int i = 0; i < graph.length; i++) for (int j = 0; j < graph.length; j++) { if (graph[i][j] == 1) g.add(i, j ) ; } return g; } } Задача сортировки Постановка задачи Итак, Алгоритм – это формально описанная вычислительная процедура, получающая исходные данные, называемые входом алгоритма или его аргументом, и выдающая результат вычислений на выход. Алгоритмы строятся для решения тех или иных вычислительных задач. Формулировка задачи описывает, каким требованиям должно удовлетворять решение задачи, а алгоритм, решающий эту задачу, находит объект, этим требованиям удовлетворяющий. Рассмотрим задачу сортировки: Вход: Последовательность n чисел . Выход: Перестановка исходной последовательности, для которой . Например, получив на вход <31,41,59,26,41,58> алгоритм сортировки должен выдать на выход <26,31,41,41,58,59>. Существует много разных алгоритмов сортировки; выбор в конкретной ситуации зависит: • от длины сортируемой последовательности; • от того, в какой степени она уже отсортирована; • от типа памяти, используемой вычислительным устройством (оперативная память, диски, магнитные ленты). Определение. Алгоритм называется корректным, если на любом допустимом (для данной задачи) входе он заканчивает работу и выдает результат, удовлетворяющий требованиям задачи. Для записи алгоритмов будем пользоваться псевдокодом. Псевдокод Перечислим основные соглашения, которые будем использовать для записи псевдокода: 1. Отступ от левого края указывает на уровень вложенности команд Например при записи условия: 1 if i < 30 2 then 3 команда 1 4 команда 2 5 else 6 команда 3 7 команда 4 8 команда 5 2. Символ  начинает комментарий до конца строки 3. Операция присваивания записывается как ij, ijk. 4. Индекс массива пишется в квадратных скобках: A[i] – есть i-тый элемент в массиве A. Знак «..» выделяет часть массива: A[3..j] обозначает участок массива A, включающий A[3], A[4],…, A[j]. Сортировка вставками Данный алгоритм применяется для коротких последовательностей. Пример такого способа – сортировка карт: держа в левой руке отсортированные карты правой берут очередную карту и устанавливают ее на место, упорядочивая слева направо. Аргументом данного алгоритма является A[1..n] – последовательность длины n, подлежащая сортировке. Число элементов в последовательности A через length[A]. Технически данная последовательность A[1..n] занимает некоторый объем памяти (грубо говоря n ячеек). В результате выполнения алгоритма в данном участке памяти содержимое изменится и, таким образом, новая последовательность A[1..n] будет являться результатом работы алгоритма. Insertion-Sort(A) 1 for j2 to length[A] 2 do keyA[j] 3  добавить A[j] к отсортированной части A[1..j-1] 4 i  j –1 5 while i>0 and A[i]>key 6 do A[i+1]  A[i] 7 i  i-1 8 A[i+1] key Пример работы алгоритма: Вход: A=<5,2,4,6,1,3> x 5 2 4 6 1 3 2 x 5 4 6 1 3 2 4 5 x 6 1 3 x 2 4 5 6 1 3 1 2 x 4 5 6 3 1 2 3 4 5 6 Задание 1. Следуя образцу, показать, как работает Insertion-Sort(A) для A=<31,41,59,26,41,58>. Задание 2. Задача поиска: Вход: Последовательность n чисел A= и число v. Выход: Индекс i, для которого v = A[i], или специальное значение NIL, если v не встречается в А. Написать алгоритм линейного поиска, который последовательно просматривает А в поисках v. 11.4 Анализ алгоритмов Рассматривая различные алгоритмы одной и той же задачи, полезно проанализировать, сколько вычислительных ресурсов они требуют. Определение. Вычислительными ресурсами будем называть время работы алгоритма и память, занимаемую промежуточными и конечными данными алгоритма. Будем анализировать алгоритм сортировки вставками. Время сортировки вставками зависит от двух величин: • количество элементов во входной последовательности; • степень первоначальной упорядоченности входной последовательности. Определение. Временем работы алгоритма называется число элементарных шагов, которые он выполняет. Будем полагать, что одна строка псевдокода требует не более чем фиксированного числа операций. Каждая строка псевдокода выполняет ту или иную процедуру (например, присвоение переменной, проверка условия и т.п.). Будем различать: • вызов процедуры, на который уходит фиксированное число операций - стоимость; • исполнение процедуры, которое зависит от конкретных входных данных (может быть долгим) – число раз, которое эта процедура исполняется. Тогда для алгоритма сортировки вставками можно построить таблицу: Строка алгоритма Стоимость Число раз 1 c1 n 2 c2 n – 1 3 n – 1 4 c4 n – 1 5 C5 6 c6 7 c7 8 c8 n – 1 Где tj – сколько раз будет исполнена строка 5 для каждого j (j=2..n) Строка стоимостью с, повторенная m раз, дает вклад cm в общее число операций. Сложив вклады всех строк, получим T(n) – выражение времени работы алгоритма в общем виде. Но время работы зависит не только от n – количества элементов, поданных на вход, но и от степени упорядоченности поданной на вход последовательности. Благоприятный случай Самый простейший случай, когда на вход подана уже отсортированная последовательность. Тогда цикл в строке 5 завершается после первой же проверки (поскольку A[i]key при i = j - 1), так что все tj=1. Следовательно, Таким образом, в наиболее благоприятном случае время T(n) является линейной функцией: T(n)=an+b. Худший случай Наиболее неудачным случаем, когда время работы алгоритма будет максимальным, является входная последовательность отсортированная в обратном порядке (убывающем ) . В данном случае каждый элемент A[j] придется сравнить со всеми элементами A[1],…,A[j-1]. Поскольку , , то Теперь функция T(n) – квадратичная : T(n)=an2+bn+c. Вывод. Время работы в лучшем случае и в худшем могут сильно различаться. Наиболее часто в качестве характеристики работы алгоритма берется худшее время работы алгоритма. • Зная время работы в худшем случае можно гарантировать, что выполнение алгоритма закончится за некоторое время. • На практике наиболее вероятны именно плохие входы. • Время работы в среднем может быть довольно близко к времени работы в худшем случае. Задание 3. Найти время работы в худшем случае для задания 2. 11.5 Порядок роста Для оценки времени работы алгоритма используют время работы в самом худшем случае, причем в формуле отбрасываются члены меньших порядков и коэффициент при старшем порядке. Например, если T(n)=a n2 + b n + c, то порядок роста записывается так . Алгоритм с меньшим порядком роста предпочтительнее. Например, если один алгоритм имеет порядок роста , а другой , то первый более эфективен. Графы. Представление графа в виде списка смежных вершин использует массив Adj из списков – по одному на вершину. Для каждой вершины список смежных вершин содержит в произвольном порядке все сменные с ней вершины . Поиск в глубину Пусть задан граф . Идея алгоритма. Стратегия поиска в глубину такова: идти вглубь, пока это возможно (есть непройденные исходящие рёбра), и возвращаться и искать другой путь, когда таких рёбер нет. Так делается, пока не обнаружены все вершины, достижимые из исходной. (Если после этого остаются необнаруженные вершины, можно выбрать одну из них и повторять процесс, и делать так, пока не обнаружатся все вершины графа). Как и при поиске в ширину, обнаруженная впервые вершина , смежную с вершиной , помещается в поле . В результате получается дерево или несколько деревьев, если поиск повторяется из нескольких вершин. Будем считать, что поиск повторяется. В результате получается подграф предшествования, определенный так: Подграф предшествования представляет собой лес поиска в глубину, состоящий из деревьев поиска в глубину. Пусть вершины графа могут принимать цвета: белый, серый, чёрный. В начале они все белые, будучи обнаруженной, вершина становится серой, и черной, когда список смежных с ней вершин полностью просмотрен. Каждая вершина попадает ровно в одно дерево поиска в глубину, так что эти деревья не пересекаются. Помимо этого, поиск в глубину ставит на вершинах метки времени. Каждая вершина имеет две метки: в записано, когда эта вершина была обнаружена (и сделана серой), а в - когда была закончена обработка списка смежных с вершин ( стала черной). Пусть метки времени и являются целыми числами от 1 до и . Вершина будет белой до момента , серой между и , черной после . Исходный граф может быть ориентированным или неориентированным. Переменная - глобальная переменная текущего времени, используемого для пометок. DFS(G) // 1 for для каждой вершины 2 do color[u]=белый 3 4 time=0 5 for для каждой вершины 6 do if (color[u]==белый) 7 then DFS-Visit(u) DFS-Visit(u) // Так как , то 1 color[u]=серый //была белой 2 d[u]=time=time+1 3 for для всех //обработать ребро (u,v) 4 do if (color[v]==белый) 5 then 6 DFS-Visit(v) 7 color[u]=черный 8 f[u]=time=time+1 Таким образом, так как процедура DFS-Visit вызывается ровно один раз для каждой вершины, то время работы алгоритма поиска в глубину . Свойства поиска в глубину • Подграф предшествования в точности соответствует структуре рекурсивных вызовов процедуры DFS-Visit. • Времена обнаружения и окончания обработки образуют правильную скобочную структуру. Будем обозначать обнаруженные вершины u открывающейся скобкой с пометкой u. Окончание обработки этой вершины - закрывающейся скобкой с той же пометкой. Тогда перечень событий будет правильно построенным выражением из скобок. Классификация рёбер Рёбра графа делятся на несколько категорий в зависимости от их роли при поиске в глубину. 1. рёбра деревьев – это ребра графа . Ребро (u,v) будет ребром дерева, если вершина v была обнаружена при обработке этого ребра. 2. Обратные ребра – это ребра (u,v), соединяющие вершину u с ее предком v в дереве поиска в глубину (ребра циклы считаются обратными ребрами). 3. Прямы ребра – это ребра (u,v), соединяющие вершину с ее потомком, но не входят в дерево поиска в глубину. 4. Перекрестные ребра – все остальные ребра графа. Они могут соединять две вершины одного дерева в глубину, если ни одна из этих вершин не является предком другой, или же вершины разных деревьев. Например, ориентированный граф не имеет циклов, если поиск в глубину не находит в нем обратных ребер. Очереди head[Q] – индекс головы очереди. tail[Q] – индекс свободной ячейки, в которую будет помещён следующий добавляемый к очереди элемент. Операция добавления элемента к очереди Enqueue. Enqueue(Q,x) 1 Q[tail[Q]]=x 2 if tail[Q]=length[Q] 3 then tail[Q]=1 4 else tail[Q]=tail[Q]+1 Операция удаления Dequeue. Dequeue(Q) 1 x=Q[head[Q]] 2 if head[Q]=length[Q] 3 then head[Q]=1 4 else head[Q]=head[Q]+1 5 return x Представление графа в виде списка смежных вершин использует массив Adj из списков – по одному на вершину. Для каждой вершины список смежных вершин содержит в произвольном порядке все сменные с ней вершины . Графы. Поиск в ширину Поиск в ширину – это один из базисных алгоритмов, составляющий основу многих других. Например, алгоритм Дейкстры поиска кратчайших путей из одной вершины и алгоритм Прима поиска минимального покрывающего дерева – это обобщения поиска в ширину. Пусть задан граф и фиксирована начальная вершина s. Идея алгоритма. Алгоритм поиска в ширину перечисляет все достижимые из s вершины в порядке возрастания расстояния от s. Расстоянием считается длина кратчайшего пути. В процессе поиска из графа выделяется часть, называемая «деревом поиска в ширину» с корнем s. Она содержит все достижимые из s вершины (и только их). Для каждой из них путь из корня в дереве поиска будет одним из кратчайших путей (из начальной вершины) в графе. Название объясняется тем, что в процессе поиска сначала просматриваются все соседние вершины, затем соседей соседей и т.д. Пусть вершины графа могут принимать цвета: белый, серый, чёрный. В начале они все белые, в ходе работы вершина может стать серой, а затем черной (но не наоборот). Повстречав новую вершину, алгоритм поиска красит её в серый или черный цвет. Если и чёрная, то - серая или чёрная вершина. Таким образом, только серые вершины имеют смежные необнаруженные вершины. Вначале дерево поиска состоит только из корня – начальной вершины s. Как только алгоритм обнаруживает новую белую , смежную с ранее найденной вершиной , вершина добавляется к дереву поиска, становясь ребенком вершины , а становится родителем . Каждая вершина обнаруживается только однажды, так что двух родителей у нее быть не может. Двигаясь от вершины к корню, мы проходим всех ее предков. Пусть граф задан списками смежных вершин. Для каждой вершины графа дополнительно хранятся ее цвет и ее предшественник . Если предшественника нет (например или еще не обнаружена), . Кроме того, расстояние от до записывается в поле . Процедура использует очередь (FIFO) для хранения множества серых вершин. BFS(G,s) 1 for для каждой вершины 2 do color[u]=белый 3 4 5 color[s]=серый 6 7 8 9 while 10 do u=head[Q] 11 for для всех 12 do if color[v]==белый 13 then color[v]=серый 14 d[v]=d[u]+1 15 16 Enqueue(Q,v) 17 Dequeue(Q) 18 color[u]=черный 14.1 Поиск подстрок Большинство текстовых редакторов умеет искать заданное слово в редактируемом тексте. Критической является скорость поиска. Рассмотрим формальную постановку задачи: Пусть даны «текст» - массив T[1..n] длины n и «образец» - массив P[1..m] длины . Считается, что элементы массивов Т и Р – символы некоторого конечного алфавита ={a,b,…,z}. Такие массивы символов называют строками символов или словами в данном алфавите. Определение. Будем говорить, что образец Р входит со сдвигом s (или входит с позиции s+1) в текст Т, если и (или при ). Определение. Если Р входит со сдвигом s в текст Т , то говорят, что s – допустимый сдвиг, иначе – недопустимый. Задача поиска подстрок состоит в нахождении всех допустимых сдвигов для данных Т и Р. 14.2 Обозначения - множество всех конечных строк в алфавите  (в том числе пустая строка). Длина строки х обозначается |х|. Соединение строк x и y обозначается xy. Строка w – префикс (начало) строки x, если x=wy, где . () Строка w – суффикс (конец) строки x, если x=yw, где . () Например, ab [ abcca cca ] abcca 14.3 Простейший алгоритм Первый приходящий в голову алгоритм последовательно проверяет равенство для каждого из n-m+1 возможных значений s: String(T,P) 1 nlength[T] 2 m length[P] 3 for s0 to n-m 4 do if P[1..m]=T[s+1..s+m] 5 then print “Подстрока входит со сдвигом” s Время работы такого алгоритма в худшем случае: . 14.4 Конечные автоматы Определение. Конечный автомат представляет собой пятерку , где • Q – конечное множество состояний; • - начальное состояние. • - конечное множество допускающих состояний; •  - конечный входной алфавит; • - функция переходов автомата. 1. Первоначально конечный автомат находится в состоянии , затем он по очереди читает символы из входной строки (Т). 2. Находясь в состоянии q и читая символ a, автомат переходит в состояние . 3. Если автомат находится в состоянии , говорят, что он допускает прочитанную часть входной строки, иначе эта часть – отвергнута. Определение. Функция называется функцией конечного состояния, если есть состояние, в которое придет автомат из начального состояния , прочитав строку w. Теорема. Автомат допускает строку w тогда и только тогда, когда . Рекуррентное определение функции : Automate(T,,m) 1 nlength[T] 2 q0 3 for i1 to n 4 do q(q,T[i]) 5 if q=m 6 then si-m 7 print “образец входит со сдвигом” s Пример, Т= abababacaba, P=ababaca. Состояние a b c P 1 a 1 1 2 b i – 1 2 3 4 5 6 7 8 9 10 11 2 3 a T[i] - a b a b a b a c a b a 3 1 4 b 0 1 2 3 4 5 4 5 6 7 2 3 4 5 a 5 1 4 6 c 6 7 a 7 1 2 Время работы такого алгоритма в худшем случае: , при условии, что функция переходов уже вычислена. Иначе сложность алгоритма зависит от размерности алфавита. Вычисление функции переходов: Transition(P, ) 1 mlength[P] 2 for q0 to m 3 do for (Для) всех символов 4 do kmin(m+1,q+2) 5 repeat kk-1 6 until Pk ] Pqa 7 (q,a) k 8 return  Время работы такого алгоритма в худшем случае: .