Тема 3. Основы реализации списковых структур

Задание 1. Реализовать программу для простейшего моделирования линейного списка с помощью массива. Должны быть реализованы все основные действия:

· проход по списку с выводом на экран информационных частей элементов

· поиск элемента с заданной информационной частью

· добавление нового элемента после заданного и перед заданным со сдвигом (при необходимости) хвостовой части вправо для освобождения ячейки массива

· удаление заданного элемента со сдвигом (при необходимости) хвостовой части влево для заполнения образовавшейся пустой ячейки.

Выполнение всех операций предусматривает необходимые проверки (наличие в списке хотя бы одного элемента, наличие свободных ячеек, наличие искомого элемента). Все основные операции оформляются как подпрограммы с параметрами. Главная программа создает пустой список, устанавливая счетчик числа элементов в списке в ноль, и организует диалог для реализации всех операций.

Проверить работу программы для небольшого массива (до 10 элементов).

 

Задание 2. Изменить предыдущую программу для создания упорядоченного списка. Для этого надо изменить логику работы подпрограммы добавления элемента. Подпрограмма должна находить соответствующее место для нового элемента, т.е. поиск должен останавливаться при обнаружении первого элемента, большего заданного. Предусмотреть обработку особых случаев:

· если в списке нет ни одного элемента, вставка производится в первую ячейку массива

· если все элементы меньше заданного, вставка производится в конец списка

Проверить работу программы для двух случаев: список целых чисел по возрастанию и список коротких текстовых строк по алфавиту.

Задание 3. Реализовать линейный список на базе массива с указателями-индексами. Список должен иметь заголовок (нулевая ячейка массива) с номером первого элемента списка. Набор операций - стандартный. Для отслеживания свободных ячеек использовать простейшую схему – отмечать свободные ячейки специальным значением индекса ( -1). Главная программа при создании пустого списка должна отметить все ячейки массива (кроме нулевой) как свободные.

Задание 4. Реализовать линейный динамический список со стандартным набором операций. Пустой список содержит только элемент-заголовок, который создается главной программой в начале работы и содержит значение nil в ссылочной части. У непустого списка в ссылочной части хранится адрес первого реального элемента. Адрес заголовка сохраняется в глобальной ссылочной переменной. Все действия оформляются как подпрограммы.

Подпрограмма для добавления элемента после заданного должна работать и для пустого списка – в этом случае новый (он же первый реальный! ) элемент должен добавляться сразу после заголовка. Для этого проверить пустоту списка, после чего для пустого списка установить глобальный указатель текущего элемента в адрес заголовка, для непустого списка вызвать процедуру поиска. Само добавление выполняется обычным образом.

Задание 5. Изменить предыдущую программу так, чтобы удаляемый из основного списка элемент добавлялся во вспомогательный список с возможностью просмотра вспомогательного списка. Работа со вспомогательным списком может выполняться по стековому принципу.

В предыдущую программу надо внести следующие изменения:

· добавить глобальную ссылочную переменную для хранения адреса вершины стека

· в начале главной программы создать пустой вспомогательный список (стек)

· в основное меню добавить возможность просмотра вспомогательного списка (стека)

· изменить процедуру удаления элемента из основного списка, заменив операцию освобождения памяти операциями добавления удаленного элемента во вспомогательный список (стек)

· добавить обычную процедуру вывода вспомогательного списка (стека)

Задание 6. Изменить предыдущую программу для поддержки упорядоченных списков (см. задание 2).

Тема 4. Усложненные списковые структуры

Задание 1. Реализовать линейный динамический двунаправленный список со следующим набором операций:

· просмотр списка в прямом и обратном направлениях

· поиск заданного элемента в прямом и обратном направлениях

· добавление элемента перед или после заданного

· удаление заданного элемента

Список должен иметь заголовок и быть кольцевым. Пустой список содержит только заголовок, оба ссылочных поля которого указывают на сам заголовок. Адрес заголовка задается глобальной ссылочной переменной. Все операции оформляются как подпрограммы. Добавление нового элемента после заданного должно работать и для пустого списка (см. задание 4 из предыдущей темы).

Задание 2. Реализовать набор подпрограмм для выполнения основных операций с массивом списков. Каждый элемент массива хранит только указатель на начало связанного списка. Сам базовый массив работает на основе сдвиговых операций. Основные операции:

· полный проход по всей структуре

· поиск заданного элемента

· добавление нового элемента в массив с пустым связанным списком

· добавление нового элемента в связанный список

· удаление элемента из связанного списка

· удаление элемента из базового массива

Задание 3. Реализовать набор подпрограмм для выполнения основных операций со списком списков. Требования аналогичны предыдущему заданию.

Тема 5. Основные понятия о древовидных структурах

Задание 1. Построение и обход идеально сбалансированных двоичных деревьев. Реализовать программу, выполняющую следующий набор операций:

· построение идеально сбалансированного двоичного дерева с заданным числом вершин

· построчный вывод дерева на основе процедуры обхода в прямом порядке

· построчный вывод дерева на основе процедуры обхода в симметричном порядке

· построчный вывод дерева на основе процедуры обхода в обратно-симметричном порядке

Рекомендации:

· для простоты построения дерева можно информационную часть формировать как случайное целое число в интервале от 0 до 99

· глобальные переменные: указатель на корень дерева и число вершин

· алгоритмы построения ИСД и его обхода оформляются как подпрограммы, вызываемые из главной программы

· все процедуры обхода должны выводить вершины с числом отступов, пропорциональным уровню вершины: корень дерева не имеет отступов, вершины первого уровня выводятся на 5 отступов правее, вершины 2-го уровня – еще на 5 отступов правее и т.д. Для этого в рекурсивные подпрограммы обхода надо ввести второй формальный параметр - уровень этой вершины

· Все процедуры обхода имеют похожую структуру. Например, процедура обхода в прямом направлении должна:

Ø проверить пустоту очередного поддерева

Ø вывести в цикле необходимое число пробелов в соответствии с уровнем вершины

Ø вывести информационную часть текущей вершины

Ø вызвать рекурсивно саму себя для обработки своего левого поддерева с увеличением уровня на 1

Ø вызвать рекурсивно саму себя для обработки своего правого поддерева с увеличением уровня на 1

Сравнение рассмотренных правил вывода двоичного дерева приводится в следующей таблице

 

Исходное дерево	Вывод в прямом порядке	Вывод в симметричном порядке	Вывод в обратно-симметричном порядке
10   15 9 13 22 5 17

 

Главная программа реализует следующий набор действий:

· запрос числа вершин в дереве

· запуск рекурсивной подпрограммы построения идеально сбалансированного дерева со следующими фактическими параметрами: указатель на корень дерева (при построении дерева этот параметр является выходным! ) и заданное число вершин

· последовательный вызов подпрограмм обхода дерева со следующими фактическими входными параметрами: указатель на корень дерева, ноль в качестве уровня корневой вершины дерева.

 

Задание 2. Добавить в программу нерекурсивный вариант процедуры обхода дерева в симметричном порядке.

Замена рекурсии циклом основана на использовании вспомогательного стека для хранения последовательности пройденных вершин от корня до текущей вершины и уровня этих вершин в дереве (напомним, что уровень используется только для задания правильного числа отступов при построчном выводе дерева). Исходя из этого, создаваемая подпрограмма должна объявить необходимые локальные типы данных для динамической реализации вспомогательного стека. Каждый элемент стека должен хранить: указатель на пройденную вершину дерева, уровень вершины, указатель на следующий элемент стека. Для реализации стека, как обычно, требуются две ссылочные переменные: указатель на вершину стека и вспомогательный указатель, используемый при добавлении или удалении элементов в стек.

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

· циклическое сохранение очередной вершины в стеке (пока не будет достигнута пустая вершина) следующим образом:

Ø увеличение уровня вершины на 1

Ø создание нового элемента стека, заполнение всех его полей и добавление его в стек

Ø переход к левому потомку текущей вершины

· проверка пустоты стека: если стек пуст, то основной цикл следует завершить, а иначе – перейти к обработке вершины

Ø извлечь из стека адрес текущей обрабатываемой вершины и ее уровень

Ø вывести вершину с необходимым числом пробелов

Ø удалить элемент из стека с освобождением памяти

Ø перейти к правому потомку текущей вершины

Для проверки правильности работы подпрограммы сравнить ее результаты с рекурсивным аналогом.

Задание 3. Обработка произвольных двоичных деревьев

Реализовать программу, выполняющую следующий набор операций с двоичными деревьями:

· поиск вершины с заданным значением информационной части

· добавление левого или правого потомка для заданной вершины

· построчный вывод дерева с помощью основных правил обхода

· уничтожение всего дерева

Рекомендации:

· объявить необходимые глобальные переменные: указатель на корень дерева, указатель на родительскую вершину, признак успешности поиска

· объявить и реализовать рекурсивную подпрограмму поиска. В качестве основы можно взять любой из известных вариантов обхода дерева. Основное отличие рекурсивного поиска от рекурсивного обхода состоит в необходимости прекращения обхода дерева в случае совпадения информационной части текущей вершины с заданным значением. Один из способов прекращения обхода основан на использовании булевского признака, который перед запуском обхода устанавливается в false и переключается в true при обнаружении искомой вершины. Для каждой текущей вершины подпрограмма поиска должна выполнять следующие основные действия:

Ø проверить необходимость продолжения поиска

Ø проверить текущую ссылочную переменную на nil

Ø сравнить информационную часть текущей вершины с заданным значением

Ø если эти величины совпадают, то установить признак окончания поиска и установить адрес родительской переменной в адрес текущей вершины

Ø в противном случае продолжить поиск сначала в левом поддереве текущей вершины, вызвав рекурсивно саму себя с адресом левого потомка, а потом – в правом поддереве, вызвав саму себя с адресом правого потомка

Результат поиска можно проверить с помощью глобального признака. В случае успешного поиска становится известен адрес найденной вершины, который можно использовать в дальнейшем для добавления к этой вершине одного из потомков.

· Объявить и реализовать подпрограмму добавления новой вершины в дерево как потомка заданной вершины.

Подпрограмма должна:

Ø проверить пустоту дерева: если указатель корня имеет значение nil, то надо создать корень дерева

o выделить память

o запросить значение информационной части корня

o сформировать пустые ссылочные поля на потомков

Ø если дерево не пустое, то организовать поиск родительской вершины:

o запросить искомое значение информационной части родительской вершины

o установить признак поиска и вызвать подпрограмму поиска

o если поиск удачен, то проверить число потомков у найденной родительской вершины

o если вершина-родитель имеет двух потомков, то добавление невозможно

o если родительская вершина имеет только одного потомка, то сообщить о возможности добавления одного из потомков, выделить память для новой вершины и заполнить все три ее поля, настроить соответствующее ссылочное поле у родительской вершины

o если родительская вершина не имеет ни одного потомка. то запросить тип добавляемой вершины (левый или правый потомок) и выполнить само добавление

 

· Объявить и реализовать рекурсивную подпрограмму для построчного вывода дерева в обратно-симметричном порядке. Эту подпрограмму без каких-либо изменений можно взять из предыдущей работы.

· Объявить и реализовать подпрограмму для уничтожения всего дерева с освобождением памяти. Основой подпрограммы является рекурсивный обход дерева, причем – по правилу обратного обхода: сначала посещается и удаляется левый потомок текущей вершины, потом посещается и удаляется правый потомок, и лишь затем удаляется сама текущая вершина. Такой обход позволяет не разрывать связи между родительской вершиной и потомками до тех пор, пока не будут удалены оба потомка. Подпрограмма удаления имеет один формальный параметр – адрес текущей вершины. Подпрограмма должна проверить указатель на текущую вершину, и если он не равен nil, то:

Ø вызвать рекурсивно саму себя с адресом левого поддерева

Ø вызвать рекурсивно саму себя с адресом правого поддерева

Ø вывести для контроля сообщение об удаляемой вершине

Ø освободить память с помощью процедуры Dispose и текущего указателя

Главная программа должна:

· создать пустое дерево

· организовать цикл для добавления вершины с вызовом соответствующей подпрограммы и последующим построчным выводом дерева

· предоставить возможность в любой момент вызвать подпрограмму удаления дерева с фактическим параметром, равным адресу корня дерева, что запускает механизм рекурсивного удаления всех вершин, включая и корневую; поскольку после удаления корневой вершины соответствующий указатель становится неопределенным, можно инициировать его пустым значением, что позволит повторно создать дерево с новой корневой вершиной

⇐ Предыдущая123Следующая ⇒

Поделиться: