Учебник_Информатика. Стандарт третьего поколениян. В. Макарова, В. Б. Волков
 Скачать 14.49 Mb.
|
|
деления, в общем, любых величин, имеющих дробную часть. Два значения типа BOOLEAN обозначаются идентификаторами со значениями истина (TRUE) и ложь (FALSE). Операции над данными этого типа подчиняются правилам булевой алгебры. Пример. Тип BOOLEAN играет важную роль при составлении алгоритмов: именно на основе значений, которые принимают переменные или выражения этого типа, осуществляется управление ходом выполнения программы (алгоритма). В базовый тип CHAR входит множество печатаемых символов и символов- разделителей в соответствии с кодом ASCII. Пример. Тип CHAR является основой всех простых и сложных типов, содержащих текст (строк, массивов и коллекций строк, записей). К переменным типа REAL и INTEGER применимы арифметические операции, такие как сложение (+), вычитание ( - ) , умножение (* ) и деление ( / ) , к переменным типа BOOLEAN — логические операции, к символьным переменным — операция конка 412 Глава 14. Основы теории алгоритмов тенации («склеивания») последовательностей символов. Операции отношения или сравнения применяются к данным любого типа, но правила их применения различны. 14.4.3. Представление и обработка данных в виде структур (массив, запись) Наиболее известная структура данных — массив. Массив представляет собой упорядоченную структуру однотипных данных, которые называются элементами массива. Массив подходит для решения задач, в которых накапливаются и под лежат обработке данные одного и того же типа. Доступ к каждому элементу массива осуществляется с помощью индекса. В общем случае индекс — это порядковый номер элемента в массиве. Массивы могут быть как одномерными (адрес каждого элемента определяется значением одного индекса), так и многомерными (адрес каждого элемента опреде ляется значением нескольких индексов). Другим известным структурным типом данных является запись. Элемен ты записи называются полями. Примером данных такого типа может быть за пись «Информация о студенте». Для представления такого типа в каждом язы ке программирования существуют встроенные средства языка, но, кроме того, такой тип (или переменная такого типа) может быть представлен графически (рис. 14.15). Иванов Петр Николаевич 1 4 1990 2004 2239/22 Рис. 1 4 .15. Графическое изображение записи данных в массиве Из записей могут формироваться массивы. Такое сочетание двух этих струк турных типов часто встречается при обработке данных, извлеченных из баз данных. В качестве примера рассмотрим алгоритм обработки двухмерного массива. Ана логом двухмерного массива в математике является матрица. Общий вид матрицы Л размерности М х N следующий: а \ \ а 12 • а 21 а 22 ■ а М 1 а М 2 a lN а 2 N *MN Для матрицы размерностью N * JV (квадратной матрицы) определены понятия главной и побочной диагоналей. Элементы главной диагонали - г - {щ ,1 — 1 ...N } , а элементы побочной — {ai(N-i+i>,i = 1..JV}. 14.4. Представление и обработка данных разного типа 413 Пример. Пусть необходимо построить матрицу, элемент которой < 2 t> вычисляется как (i + j )2, а элементам главной диагонали присвоить значение 0. Для решения поставленной задачи воспользуемся двухмерным массивом целых чисел. На первом этапе происходит построение вложенного цикла для расчета элементов и заполнения массива. На втором этапе элементам главной диагонали присваиваются нулевые значения. Блок-схема такого алгоритма приведена на рис. 14.16 (ЛГ— размерность массива, / и / — индексы массива). Рис. 14.16. Блок-схема алгоритма обработки двухмерного массива 14.4.4. Представление и обработка данных в виде символьных цепочек Символьные цепочки с точки зрения физической организации представляют собой обыкновенные массивы типа CHAR. Особенность этого типа данных состоит в том, что символьный массив в подавляющем большинстве случаев является осмысленным текстом, а значит, имеет логическую структуру: разделен на слова, предложения, строки и абзацы. Поэтому алгоритмы обработки символьных цепочек почти всегда включают в себя поиск специальных символов-разделителей, разде ление текста на логические единицы (слова, предложения, строки) и выполнение операций (подсчет, сортировка, поиск и замена) над этими единицами. 414 Глава 14. Основы теории алгоритмов В качестве примера рассмотрим задание на определение количества слов в по следовательности символов. Определим слово как часть последовательности (ненулевой длины), ограниченную с двух сторон (либо только справа или слева) символом пробела. Рис. 14.17. Блок-схема алгоритма определения количества слов в последовательности символов Для решения задачи разместим обрабатываемую последовательность в массиве размерностью N (где N — длина последовательности). При построении алгоритма необходимо учесть, что последовательность может начинаться или заканчиваться пробелами, причем в потоке символов может встретиться несколько смежных пробелов. 14.4. Представление и обработка данных разного типа 415 Блок-схема алгоритма приведена на рис. 14.17. Здесь L — длина очередного слова, N W — количество слов в последовательности, знак пробела обозначен сим волом подчеркивания (_). 14.4.5. Представление и обработка данных в виде одно- и двусвязных списков Структура данных, в которой объекты расположены в линейном порядке, на зывается связным списком. Однако в отличие от массива, в котором этот порядок определяется индексами, порядок в связном списке определяется указателями на объекты. Элемент (узел) связного списка, помимо полей с данными, имеет поле next, в ко тором содержится указатель на следующий элемент списка. Если это последний элемент списка, поле next принимает нулевое значение. Помимо своих элементов, каждый список содержит указатель head на первый элемент списка. Если этот ука затель равен 0, значит, список пуст. Поскольку этот указатель относится к списку в целом и не содержит в себе данных, на рис. 14.18, на котором схематически по казан односвязный список, указатель не заключен в прямоугольник. Рис. 14.18. Односвязный список Односвязный список отличается тем, что пройти по нему можно только в одном направлении — от начала в конец списка. Это оказывается достаточно неудобно, по этому гораздо большее распространение получили двусвязные списки (рис. 14.19), отличающиеся тем, что их узлы содержат по два указателя — на следующий (next) и на предыдущий (prev) элементы списка. Помимо указателя head на первый элемент списка, может существовать также указатель ta il на последний элемент списка. Рис. 14.19. Двусвязный список , Частный случай двусвязного списка — замкнутый (кольцевой) список, указа тель next последнего элемента которого указывает на первый элемент, а указатель prev первого элемента — на последний элемент списка. 416 Глава 14. Основы теории алгоритмов Главная особенность списка — быстрое выполнение операций вставки и уда ления в произвольном месте списка. Эти операции требуют модификации ука зателей максимум у трех узлов: узла, над которым выполняется операция, и двух окружающих узлов. Схематично эти операции и изменения значений указателей показаны на рис. 14.20. 1 : v r Удаление Рис. 14.20. Вставка и удаление в двусвязных списках Алгоритм этих операций, приведенный на рис. 14.21 и 14.22, показывает, на сколько простыми являются алгоритмические операции со списками. Входные данные: L — список х — вставляемый элемент (узел) Поле next элемента х теперь указывает на первый элемент списка, поскольку мы присвоили ему значение указателя head Список не пустой, и указатель head указывает на следующий узел? Указатель prev бывшего первого элемента списка теперь указывает на вставляемый элемент х Указатель head списка теперь указывает на вставленный элемент х Поскольку х в списке первый, его указатель prev не указывает ни на какой элемент Выходные данные: L — список со вставленным элементом х Рис. 14.21. Вставка элемента в начало списка 14.4. Представление и обработка данных разного типа 417 ( Начало ) Входные данные: L — список х — удалямый элемент (узел) Удаляемый элемент не первый в списке? Если да (true), то полю next предыдущего элемен та присваивается значение поля next удаляемого элемента. Если удаляемый элемент в списке первый (false), то поле head списка направляется на следующий за удаляемым элемент Удаляемый элемент не последний в списке? Если да (true), то полю prev следующего за х элемен та присваивается значение поля prev удаляемого элемента Выходные данные: L — список с удаленным элементом х Рис. 14.22. Удаление элемента списка 14.4.6. Представление и обработка данных в виде деревьев Элементы данных могут образовывать и более сложные структуры, чем линей ный список. Часто данные, подлежащие обработке, образуют иерархическую струк туру, которую необходимо отобразить в памяти компьютера и, соответственно, описать в структурах данных. Такая структура получила название дерева. Каждый элемент такой структуры, называемый узлом, может содержать ссылки на элементы более низкого уровня иерархии, а может быть, и на объект, находящийся на более высоком уровне иерархии. Узел, находящийся на самом верхнем уроне иерархии, называется корневым. Корень дерева — это единственный узел, не имеющий непосредственного предка. Имеется множество типов деревьев. Важнейшим с точки зрения информатики подмножеством структуры типа дерева является подмножество бинарных деревьев поиска. У бинарного дерева каждый узел имеет не более двух дочерних узлов, при чем левый и правый узлы различаются. Каждый узел содержит несколько полей: поля значения, хранящегося в узле, и полей, указывающих на левый и правый по томки данного узла, а также на родительский узел. Бинарным деревом поиска его 418 Глава 14. Основы теории алгоритмов делает следующее свойство: значения в узлах дерева располагаются таким образом, что в любой момент для любого узла х значения всех узлов в его левом поддереве не превышают значения узлах, а значения всех узлов в его правом поддереве не мень ше значения узла х. На рис. 14.23 показано несколько деревьев. Числа в кружках отражают значения данных, хранящихся в узлах дерева. Дерево на рис. 14.23, а не является бинарным, так как у узла 5 есть три дочерних узла. Дерево на рис. 14.23, б является бинарным, но не является деревом поиска, так как узел 2 является правым дочерним узлом по отношению к узлу 3, нарушая свойство дерева поиска. Дерево на рис. 14.23, в представляет собой корректное бинарное дерево поиска. Рис. 14.23. Виды деревьев На рис. 14.24 изображено возможное представление бинарного дерева поис ка с использованием полей указателей. На этом рисунке, как и на предыдущем, цифры представляют собой значения, хранящиеся в каждом из элементов дерева, а стрелки показывают, как при помощи указателей каждый узел дерева связан со своими правым и левым поддеревьями, а также с родительским узлом. Так, для узла со значением 2 буквой а помечен указатель, связывающий его с родительским узлом, а буквами Ь и с — указатели, связывающие этот узел, соответственно, с его левым и правым поддеревьями. Рис. 14.24. Бинарное дерево поиска Посетить все узлы дерева очень легко с помощью рекурсивной процедуры об хода. Основной вариант обхода бинарного дерева — симметричный обход дерева, когда для каждого узла сначала рекурсивно выполняется посещение его левого поддерева, затем — самого узла, а после этого — узлов его правого поддерева. Для дерева на рис. 14.24 симметричный обход дает следующую последовательность 14.4. Представление и обработка данных разного типа 419 узлов: 1,2, 3 ,4 ,5 ,7 . Как видите, таким образом можно получить отсортированную последовательность значений узлов. Два других распространенных метода обхода дерева — обход в прямом порядке, при котором сначала выводится корень, а потом значение левого и правого поддере вьев (для уже рассматривавшегося дерева это дает последовательность значений 4, 2 ,1 ,3 ,7 ,5 ), и обход в обратном порядке, при котором сначала выводятся значения узлов левого и правого поддеревьев, а затем — корня (для нашего дерева это дает последовательность 1, 3, 2, 5, 7,4). Псевдокоды описанных обходов дерева очень просты. Алгоритм процедуры симметричного обхода представлен на рис. 14.25. Входные данные: х — указатель на корневой узел дерева f — функция, вызываемая для обработки данных в текущем узле Если ссылка на след, элемент отсутствует, выполнение процедуры прекращается Процедура вызывает сама себя в качестве ссылки на обрабатываемый узел принимая ссылку на корень левого поддерева ( x.le ft) Функция f обрабатывает значение, хранящееся в текущем узле Процедура вызывает сама себя в качестве ссылки на обрабатываемый узел, принимая ссылку на корень правого поддерева ( х.right) Рис. 14.25. Процедура симметричного обхода бинарного дерева В этой процедуре для обхода всех узлов дерева и выполнения над ними опре деленных операций используется рекурсия. Рекурсия часто применяется в алгоритмах обработки разного рода сложно структурированных объектов, в частности документов в формате XML, когда ко личество дочерних узлов и уровень их вложенности заранее не известны. Основные операции при работе с бинарным деревом поиска — поиск в нем опре деленного значения, а также поиск наименьшего и наибольшего элементов дерева и поиск предшествующего и последующего элементов для данного. Выполнение операции поиска основано на том, что находясь на определенной вершине, всегда можно однозначно указать, в каком из поддеревьев находится искомое значение (если таковое имеется в данном дереве), так как согласно свой ству бинарного дерева поиска все значения узлов в левом поддереве не больше, а в правом — не меньше значения в корне. 420 Глава 14. Основы теории алгоритмов Что касается поиска наименьшего и наибольшего элементов в бинарном дереве поиска, то из свойства бинарного дерева поиска очевидно: чтобы достичь наи меньшего (наибольшего) элемента, надо двигаться по левым (или, соответственно, правым) ветвям дерева до тех пор, пока это возможно. 14.4.7. Представление и обработка данных в виде графов Графы формально описывают множество близких ситуаций. Самым привычным примером служит карта автодорог, на которой изображены перекрестки и связыва ющие их дороги. Перекрестки являются вершинами графа, а дороги — его ребрами. Графы могут быть ориентированы (подобно улицам с односторонним движением) или взвешены, когда каждой дороге приписана стоимость путешествия по ней (если, например, дороги платные). С формальной точки зрения граф представляет собой упорядоченную пару мно жеств G = ( V, Е), первое из которых состоит из вершин (узлов) графа, а второе — из его ребер. Ребро связывает между собой две вершины. При работе с графами часто решается вопрос, как проложить путь из ребер от одной вершины графа к другой. В этом случае говорят о движении по ребру, что означает переход из вершины А гра фа в другую вершину В, связанную с ней ребром АВ (ребро графа, связывающее две вершины, для краткости обозначается этой парой вершин). В этом случае говорят, что ребро А примыкает к ребру В или что эти две вершины соседние. Граф может быть ориентированным или нет. Ребра неориентированного гра фа, чаще всего называемого просто графом, можно проходить в обоих направле ниях (рис. 14.26). В этом случае ребро — это неупорядоченная пара вершин, его концов. Рис. 14.26. Неориентированный граф В ориентированном графе, или орграфе, ребра представляют собой упорядочен ные пары вершин: первая вершина — это начало ребра, вторая — его конец (рис. 14.27). Полный граф — это граф, в котором каждая вершина соединена со всеми осталь ными. Количество ребер в полном графе без петель с N вершинами равно (N2 - N ) / 2. В полном ориентированном графе разрешается переход из любой вершины в любую другую. Поскольку в графе переход по ребру разрешается в обоих направ- 14.4. Представление и обработка данных разного типа 421 лениях, а переход по ребру в орграфе — только в одном, в полном орграфе в два раза больше ребер, то есть их количество равно N 2 - N. Ориентированный граф G = ( { 1 , 2, 3, 4 ,5 }, { ( 1 , 2 ), (1, 3 ), ( 2, 4 ), ( 3, 2 ), (4, 3 ), ( 5, 2 ), ( 5, 4 ) } ) Рис. 14.27. Ориентированный граф Подграф ( VSfEs) графа или орграфа (V,E) состоит из некоторого подмножества вершин, Vs C V , n некоторого подмножества ребер, их соединяющих, Es С Е. Путь в графе или орграфе — это последовательность ребер, по которым можно поочередно проходить. Другими словами, путь из вершины А в вершину В начина ется в Л и проходит по набору ребер до тех пор, пока не будет достигнута вершина В. С формальной точки зрения путь из вершины Vx в вершину Vy — это последова тельность ребер графа: ^х^хл-Ь ®х+1®х+2> ••• vy -\vy Необходимо, чтобы любая вершина встречалась на таком пути не более, чем однажды. У всякого пути есть длина — количество ребер в нем. Длина пути А В , ВС, CD, DE равна 4. Граф или орграф называется связным, если всякую пару узлов можно соединить по крайней мере одним путем. Цикл — это путь, который начинается и кончается в одной и той же вершине. В ациклическом графе или орграфе циклы отсутствуют. Связный ациклический граф называется неукорененным деревом. Структура неуко- рененного дерева такая же, как и у дерева, только в нем не выделен корень. Однако каждая вершина неукорененного дерева может служить его корнем. Информацию о графах или орграфах в пригодном для обработки компьютер ными алгоритмами виде можно хранить двумя способами: в виде матрицы при мыканий и в виде списка примыканий\ Матрица примыканий обеспечивает быстрый доступ к информации о ребрах графа, однако, если в графе мало ребер, эта матрица будет содержать гораздо боль ше пустых клеток, чем заполненных. Длина списка примыканий пропорциональна числу ребер в графе, однако при пользовании списком время получения информа ции о ребре увеличивается. |