Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23
Download 1.85 Mb. Pdf ko'rish
|
C# Алгоритмы и структуры данных 2018 Тюкачев, Хлебостроев
|
У
ПРАЖНЕНИЯ 1. Создать приложение, в котором генерируется последовательность из 1000 целых чисел в диапазоне [0, 99], сохраняемых в двоичном дере- ве поиска. Выполнить обход дерева и сформировать массив, каждый 16 / 23 132 элемент которого содержит кратность вхождения в последователь- ность числа, равного индексу этого элемента. 2. В качестве варианта задания 1 рассмотреть возможность сохранения в узлах дерева отдельных слов из заданного текстового файла. 3. Добавить в число методов класса BinarySearchTree функцию, подсчитывающую количество дуг в дереве. 4. Измените класс BinarySearchTree так, чтобы его можно было использовать для вычисления значений бесскобочных арифметиче- ских выражений (например, 2 + 3 * 4 / 5). 5. Используйте двоичное дерево для представления файловой системы: каждый каталог содержит не более двух наследников – файлов и/или папок. Для файла, кроме имени, в виде целого числа указано время его содания. Выполнить последующий обход дерева с удалением всех файлов, созданных ранее указанной даты. 17 / 23 133 Г ЛАВА 5. Г РАФЫ Структуры данных можно классифицировать, исходя из характера от- ношений между их элементами. Так, элементы списков находятся в отноше- нии следования: «предыдущий» – «последующий». Для деревьев это отноше- ние иерархии: «родитель» – «потомок». В графах таким отношением является отношение связности. Как и элементы дерева, элементы графа называются узлами, а связь между двумя узлами называется ребром графа. Ниже в этой главе будут приведены строгие определения понятий теории графов и рас- смотрен ряд важных теорем. В настоящее время теория графов является важным разделом дискрет- ной математики, но зародилась она в связи с решением развлекательных ма- тематических задач и головоломок. Общепринято считать, что начало этому положил Леонард Эйлер, сформулировавший в 1736 году знаменитую задачу о семи кенигсбергских мостах. Другими известными примерами подобных задач являются задача о четырех красках (Ф. Гутри, 1852 г.) и задача комми- вояжера (К. Менгер, 1830 г.). Бурное развиттие теории графов в середине XIX века было связано с использований ее практических приложений в различных областях естество- знания. Многие результаты, относящиеся к теории графов, были получены при решении практических проблем. Немецкий физик Густав Кирхгоф ис- пользовал графы для представления электрических схем и анализа полной системы уравнений для токов и напряжений. В основе такого анализа лежал поиск в графе подструктур, представляющих собой линейно независимые контуры. Английский математик XIX века Артур Кэли, решавший задачу подсчета числа изомеров предельных углеводородов, свел ее к подсчету чис- ла деревьев, обладающих заданными свойствами, которые могут быть выде- лены в графе. Позже методы теории графов стали использоваться также и в других раделах математики, с чем было связано получение важных результа- тов в алгебре, теории вероятностей, топологии, теории чисел. Среди задач теории графов можно выделить задачи, носящие преиму- щественно комбинаторный или преимущественно геометрический характер. К первому классу относятся, например, задачи о подсчете и перечислении графов с заданными свойствами. Ко второму – задачи, связанные с обходами графа, а также задачи об укладке графа на различных поверхностях. Важной проблемой, специфической для теории графов, является изучение различных свойств связности графов и их изоморфизма. Результаты таких исследований находят свое применение при анализе надежности электронных схем и ком- муникационных сетей. Еще одним направлением исследований в теории гра- 18 / 23 134 фов является цикл проблем, связанных с разбиением множества вершин (ре- бер) на подмножества по какому-либо признаку. При этом смежные вершины (ребра) должны принадлежать различным подмножествам. Данная задача известна как задача о раскраске графа. Download 1.85 Mb. Do'stlaringiz bilan baham: 
|