Методы программирования. Кулаков Ю.В - 5 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

важный особый случай, когда каждый из списков переменного размера является стеком. Познакомьтесь с поня-
тием перепаковки памяти при возникшей ситуации переполнения в одном из стеков и возможными способами
реализации перепаковки. Изучите алгоритм G, который выполняет полную перепаковку памяти, основываясь на
изменении размера каждого стека с момента последней перепаковки. Выполните этот алгоритм вручную для не-
которой входной информации и проанализируйте полученный результат.
Познакомьтесь со связанным распределением памяти при хранении линейных списков. Сопоставьте по-
следовательное и связанное распределение памяти и оцените их преимущества и недостатки. Познакомьтесь с
понятием списка свободного пространства и рассмотрите операции исключения и включения узлов в этот спи-
сок. Уделите внимание понятию пула памяти (списка свободного пространства) и изучите операцию исключения
узла из этого списка с проверкой на переполнение. Изучите метод, позволяющий использовать минимально воз-
можный пул памяти. Рассмотрите несколько наиболее распространенных операций со связанными стеками и оче-
редями. Познакомьтесь с задачей топологической сортировки и простым способом ее решения. Рассмотрите ма-
шинно-ориентированный алгоритм T топологической сортировки, использующий последовательную таблицу и
связанные списки. Опробуйте этот алгоритм вручную для некоторой входной информации и проанализируйте
полученные результаты.
Познакомьтесь с понятием циклически связанного списка и особенностями такого списка. Рассмотрите
операции включения и исключения узлов, очистки циклического списка, включения одного циклического спи-
ска в другой, расщепления одного циклического списка на два. Рассмотрите задачу сложения двух многочленов
и алгоритм A ее решения, в котором многочлены представлены циклическими списками. Опробуйте этот алго-
ритм вручную для сложения некоторых многочленов и проанализируйте полученные результаты.
Рассмотрите линейные списки с двумя связями. Опишите операции включения и исключения информации в
левом конце двусвязного списка и добавьте двойственные операции в правом конце, получаемые на основании
симметрии. Убедитесь в том, что полученные операции реализуют все действия для дека общего вида. Рас-
смотрите схему двусвязного списка с головным узлом и выясните главную причину предпочтительности такого
представления. Изучите операции исключения и включения узлов для двусвязного списка с головным узлом и
оцените простоту их реализации.
Обратите внимание на то, что двумерные массивы и массивы более высокой размерности по существу яв-
ляются простейшими обобщениями линейных списков. Изучите последовательное распределение памяти при
хранении массивов, имеющих полную прямоугольную структуру, а также структуру треугольной матрицы.
Рассмотрите способ линейной адресации памяти при плотном упаковывании вместе двух треугольных матриц
одинакового размера в одну прямоугольную матрицу. Познакомьтесь со связанным распределением памяти для
многомерных массивов информации и рассмотрите подробно такое представление на примере разреженных
матриц. Внимательно изучите операцию осевого шага в разреженной матрице, представленной связанными ор-
тогональными списками, и алгоритм S реализации осевого шага. Опробуйте этот алгоритм вручную для некото-
рой разреженной матрицы и проанализируйте полученные результаты.
1.2. Деревья
Познакомьтесь с понятиями: дерева, корня дерева, поддерева, степени узла дерева, концевого узла, узла
разветвления, уровня узла, упорядоченного и ориентированного деревьев, а также леса. Обратите внимание на
удобство использования в разговоре о деревьях терминологии генеалогических деревьев.
Изучите способы представления деревьев с помощью графов, вложенных множеств, вложенных скобок,
уступчатого списка и десятичной системы обозначений Дьюи. Обратите внимание на то, что, например, вся-
кий прямоугольный массив или алгебраическую формулу можно рассматривать как частный случай древовид-
ной структуры. Познакомьтесь с понятием наиболее важного типа деревьев – бинарного дерева. Рассмотрите
понятие прохождения бинарных деревьев, которое выполняется во всех алгоритмах, работающих с древовид-
ными структурами. Изучите прямой, обратный и концевой порядки прохождения бинарного дерева и рассмот-
рите алгоритм T прохождения бинарного дерева в обратном порядке, который использует стек. Опробуйте этот
алгоритм вручную для некоторого бинарного дерева и проанализируйте полученный результат.
Познакомьтесь с достаточно остроумным методом представления бинарных деревьев посредством так на-
зываемых прошитых деревьев, в соответствии с которым все конечные связи заменены связями-нитями. Ак-
центируйте свое внимание на том, как идут правые и левые связи-нити. Рассмотрите алгоритм S определения
обратного преемника в прошитом бинарном дереве и обратите внимание, что в данном случае стек не требует-
ся. Попробуйте придумать модификацию этого алгоритма для определения обратного предшественника в про-
шитом бинарном дереве. Обратите внимание на условия, которым должно удовлетворять пустое прошитое де-
рево, и рассмотрите представление в ЭВМ дерева как прошитого дерева с головным узлом в соответствии с
этими условиями. Проанализируйте преимущества прошитого бинарного дерева с точки зрения его прохожде-
ния перед непрошитым.
Убедитесь в том, что прошитые деревья растут почти так же легко, как и обычные деревья, изучив алго-
ритм I присоединения одиночного узла в качестве правого поддерева некоторого узла. Опробуйте этот алго-
ритм вручную для некоторой входной информации и проанализируйте полученный результат. Поменяв ролями
левое и правое поддеревья, получите алгоритм производящий подобным же образом включение влево. Обрати-
те внимание на важный промежуточный метод, использующий право-прошитые бинарные деревья. Рассмотри-
те алгоритм С копирования бинарного дерева, опробуйте его вручную и проанализируйте полученный резуль-
тат.

Страницы