СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ В ЭВМ

СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ В ЭВМ

Практические задания

Раздел 1. Основные структуры данных

Тема 2. Структуры данных “стек” и “очередь”

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

· проверку пустоты стека

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

· добавление элемента в вершину стека

· удаление элемента из вершины стека

· вывод текущего состояния стека на экран

Требования:

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

· добавлению/удалению должна предшествовать проверка возможности выполнения этих операций

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

o инициализация пустого стека

o организация диалогового цикла с пользователем

Задание 2. Реализовать тот же набор действий на основе динамического распределения памяти.

Требования аналогичны заданию 1, за исключением того, что проверку заполненности стека проводить не надо. Пустой стек задается установкой sp: = nil.

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

Задание 4 (дополнительно). Добавить в предыдущую программу следующие возможности:

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

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

· вывод содержимого вспомогательного стека удаленных элементов

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

· проверку пустоты очереди

· проверку заполненности очереди

· добавление элемента в конец очереди

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

· вывод текущего состояния очереди на экран

Требования к программе:

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

· добавлению/удалению должна предшествовать проверка возможности выполнения этих операций

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

o инициализация пустой очереди

o организация диалогового цикла с пользователем

Задание 6. Реализовать тот же набор действий на основе динамического распределения памяти.

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

Задание 7. Написать программу для моделирования работы очереди со случайным числом добавляемых и удаляемых элементов.

Пусть за единицу времени (например – 1 минуту) в очередь либо добавляется, либо удаляется случайное число элементов в количестве от 1 до 3-х. Одновременно добавление и удаление НЕ происходит. Для наглядности элементами пусть являются большие латинские буквы (коды ASCII от 65 до 90), выбираемые случайным образом. Тип операции с очередью (добавление или удаление) также задается случайно. Это приводит к тому, что очередь случайно растет и убывает. Программа должна наглядно показывать состояние очереди в каждый момент времени.

Рекомендации по разработке программы.

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

· процедура добавления вместо запроса у пользователя информационной части нового элемента должна получать ее как входной параметр

· процедура удаления должна выполнять удаление одного элемента только если очередь НЕ пустая

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

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

· организовать цикл с выходом при вводе пользователем какого-либо специального символа (например – буквы q)

· сгенерировать случайное число в диапазоне от 1 до 100 и проверить его четность с помощью операции взятия остатка от деления этого числа на 2

· если число четное – реализовать операцию добавления, если нечетное – операцию удаления

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

o генерацию случайного числа добавляемых или удаляемых символов в диапазоне от 1 до 3-х

o вывод сообщения о выполняемом действии и количестве добавляемых/удаляемых элементов

o выполнение цикла для добавления или удаления заданного числа элементов с вызовом соответствующих процедур работы с очередью, причем при добавлении новый символ должен генерироваться случайно с помощью его кода (диапазон 65 – 90) с последующим преобразованием кода в сам символ с помощью стандартной функции CHR

· вывести текущее состояние очереди

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

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

· случайное число добавляемых и удаляемых элементов одинаково (например – от 1 до 3-х)

· число добавляемых элементов чуть больше (в среднем! ) числа удаляемых (например, добавляется случайное количество элементов в диапазоне от 1 до 4-х, а удаляется – от 1 до 3-х)

· число удаляемых элементов чуть больше числа добавляемых

Для каждого случая выполнить программу при достаточно большом числе добавлений/удалений (30-40) и сделать вывод о поведении очереди.

Тема 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 и текущего указателя

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

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

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

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

Begin

x: = 1;

y: = x + 2;

write(x, y);

End.

Тогда для нее должна быть построена следующая таблица имен и дерево поиска:

	y x write var test string str program integer end begin

begin	4
end
integer	2
program	1
str
string	3
test	1
var	2
write
x	2 5 6 7
y	2 6 7

 

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

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

 

 

2. Объявить необходимые глобальные переменные, такие как номер обрабатываемой строки исходного текста и ее длина, номер обрабатываемого символа в строке (счетчик символов), сама текущая строка, текущее формируемое имя, имя исходного файла, файловая переменная, указатель на корень дерева

3. Объявить и реализовать рекурсивную подпрограмму добавления вершины в дерево поиска. За основу можно взять рассмотренную в предыдущей работе процедуру добавления, внеся в нее следующие небольшие дополнения:

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

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

4. Объявить и реализовать рекурсивную подпрограмму для вывода построенной таблицы в порядке возрастания имен. Основа – обход дерева в симметричном порядке. Дополнительно для каждой вершины выводится список номеров строк, где используется данное имя. Для этого организуется проход по вспомогательному линейному списку от его начала до конца.

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

6. Реализовать главную программу, выполняющую основную работу по выделению имен из строк обрабатываемого текста. Формируемое имя объявляется как String, но обрабатывается как массив символов. Основной механизм формирования имени – посимвольная обработка текущей строки. Как только в строке после не-буквенных символов распознается буква, начинается выделение всех последующих буквенно-цифровых символов и формирование очередного имени. Обрабатываемая строка (тип String ) рассматривается как массив символов. Удобно перед обработкой строки добавить в ее конце символ пробела. Номер текущего обрабатываемого символа задается переменной-счетчиком. Для отслеживания символов в формируемом имени также необходима переменная-счетчик.

Алгоритм работы главной программы:

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

· цикл обработки строк исходного файла:

ü чтение очередной строки и определение ее длины

ü добавление в конец строки дополнительного символа пробела

ü инициализация счетчика символов

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

a. если очередной символ есть буква, то:

Ø запомнить символ как первую букву имени

Ø организовать цикл просмотра следующих символов в строке, пока они являются буквами или цифрами, с добавлением этих символов к формируемому имени

Ø после окончания цикла установить длину сформированного имени (можно использовать нулевой элемент массива символов)

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

b. увеличить значение счетчика символов для перехода к анализу следующего символа

· вывод построенной таблицы в алфавитном порядке

· построчный вывод дерева поиска

Тема 7. Дополнительные вопросы обработки деревьев. Графы.

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

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

· удаление заданной вершины

· вывод всех вершин с указанием родительских связей

· поиск заданной вершины

Требования к подпрограммам и главной программе – стандартные.

Задание 2. Реализовать основные операции с простыми графами с использованием матричного и спискового представлений:

· формирование матрицы смежности

· преобразование матрицы смежности в список смежности

· формирование списка смежности

· преобразование списка смежности в матрицу смежности

· добавление нового ребра

· удаление заданного ребра

· добавление новой вершины

· удаление заданной вершины

· обход графа в глубину

· обход графа в ширину

Требования к подпрограммам и главной программе – стандартные.

 

 

СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ В ЭВМ

Практические задания

123Следующая ⇒

Поделиться: