LAB15_01 (Задания)
Описание файла
Файл "LAB15_01" внутри архива находится в следующих папках: Задания на лабы 2 семестр, ЯВУ, Лаб 11 (Динам. структуры). Документ из архива "Задания", который расположен в категории "". Всё это находится в предмете "информационные технологии" из 2 семестр, которые можно найти в файловом архиве РТУ МИРЭА. Не смотря на прямую связь этого архива с РТУ МИРЭА, его также можно найти и в других разделах. Архив можно найти в разделе "лабораторные работы", в предмете "информационные технологии" в общих файлах.
Онлайн просмотр документа "LAB15_01"
Текст из документа "LAB15_01"
ЛАБОРАТОРНАЯ №14
Тема: Динамические структуры данных.
Цель: Получение навыков по обработке линейных динамических структур и динамических массивов.
Темы теоретической подготовки.
Ссылочный тип в языке Паскаль. Сегментная организация памяти. Карта памяти при выполнении программ. Указатель. Ссылочная переменная. Подпрограммы доступа к динамической памяти. Аппарат создания и разрушения динамического объекта. Подпрограммы обслуживания динамической памяти.
Линейные и нелинейные динамические структуры. Операции над линейными структурами. Способы хранения их в памяти.
Контрольные вопросы
-
Система адресации в MS DOS.
-
Ссылочный тип. Виды указателей .
-
Объявление указателей.
-
Что является значением ссылочной переменной?
-
Если ссылочная переменная содержит значение nil, что это значит?
-
Какие операции можно выполнять над указателями? (приведите примеры)
-
Укажите подпрограммы для работы с адресами.
-
Когда используется динамическая память?
-
Укажите разницу в объявлении ссылочных переменных:
Var A:^integer;
Ptr: pointer;
-
Найдите ошибки, объясните каждый оператор, исправьте ошибки:
Var A:^integer;
Ptr: pointer; b:integer;
Begin b:=5; Ptr:=@b; a:=ptr; ptr:=a; end.
-
Как создать динамическую переменную? Чем динамическая переменная отличается от ссылочной? Результат работы программы изобразите в виде схемы?
Var a:poiter; b:^ real; begin New(b); a:=b;b^:=5; write(b^) end.
-
Как удалить динамическую переменную?
-
Что значит разыменовать ссылку?
-
Как создать динамический массив в пределах одного сегмента? А большого размера?
-
Какие операции выполняет монитор динамической памяти ? Процедуры управления кучей.
-
Как изменить размер кучи и стека?
-
Какое назначение у подпрограмм: MARK, RELEASE.
-
Как осуществить из программы анализ состояния кучи?(Проверить тостаточно ли памяти в куче для размещения структуры данных).
-
Рекурсивные типы данных.
-
Динамические структуры данных: линейные списки.
-
Дайте определение для линейных списков: Стек, Очередь, Дек.
-
Способы хранения списковых структур в памяти.
-
Определите структуру элемента односвязного списка для обоих способов хранения.
-
Изобразите все линейные списки в виде схемы для связанного хранения.
-
Напишите программу для построения в динамической памяти следующей структуры:
false
nil
r
2.7
-
Определите 9 базовых операций над списком.
-
Нелинейные структуры данных: графы, деревья.
-
Определение графа. Разновидности графов. Понятие пути в графе.
-
Динамическая структура данных – дерево.(основные понятия)
-
Бинарное дерево – его особенности.
-
Три алгоритма обхода дерева.
-
Алгоритм создания бинарного дерева.
-
Раскажите о использование бинарного дерева и линейных структур данных для организации поиска в таблицах данных. Преимущество одной структуры перед другой.
-
Классы Delphi для работы с динамическими структурами данных: список и дерево. Их назначение, свойства и методы.
Задание
-
Разработать программу, согласно варианту, оформив в виде рекурсивных подпрограмм операции по работе со списковой структурой:
-
создание списковой структуры
-
просмотр списковой структуры
-
поиск в списковой структуре элемента с заданным значением
-
Подпрограммы должны содержать параметры, одним из которых должен быть указатель на вершину списка.
-
Все дополнительные операции со списком, согласно варианта, оформить в виде подпрограмм.
-
Исследуйте возможность создания списковых структур с помощью класса TList Delphi
-
Опишите в тетради вашу структуру в виде объекта ООП.
ВАРИАНТЫ
-
Разработать программу сложения двух больших целых чисел ( не попадающих в диапазон стандартных типов), вводимых с клавиатуры как последовательность символов. Используя циклический однонаправленный список.
-
Используя циклический список с головным элементом, вычислить значение многочлена заданной степени по схеме Горнера, при заданном значении Х. Элемент списка должен содержать коэффициент и степень переменной Х при этом коэффициенте. Если коэффициент равен нулю, то элемент для него не строится.
-
В текстовом файле храниться неупорядоченный набор слов ( слова могут повторяться). Организуйте частотный словарь, используя для этой цели однонаправленный список. Частотный словарь содержит упорядоченные в лексикографическом порядке слова из файла. Элемент списка содержит слово и количество его вхождений в файл.
-
В текстовом файле хранятся числа из диапазона 0..100. Создать однонаправленный линейный список, элементы которого содержат числа из файла. Найти элементы списка, содержащие максимальный и минимальный элементы соответственно, и поменять их местами. Получившийся массив дописать в конец файла и перед ним вставить текст: Измененный массив.
-
Воспользуйтесь типизированным файлом лабораторной №11 и постройте индексный файл, для ускорения поиска данных в файле, в виде двунаправленного списка. Элемент списка должен содержать : ключ (одно из полей записи файла по которому организуется поиск) и значение указателя на запись с этим ключом. Затем разработайте подпрограмму поиска, использующую ваш список.
-
Представить многочлен N – ой степени в виде линейного однонаправленного списка, элемент которого содержит значение коэффициента и показатель степени Х при этом коэффициенте. Написать подпрограмму, проверяющую на равенство два многочлена Р(х) и Q(x). Если коэффициент при степени равен 0, то для него элемент в списке не образуется.
-
Представить многочлен N – ой степени в виде линейного однонаправленного списка, элемент которого содержит значение коэффициента и показатель степени Х при этом коэффициенте. Написать подпрограмму,которая строит многочлен R(x) как сумму многочленов Р(х) и Q(x). Если коэффициент при степени равен 0, то для него элемент в списке не образуется.
-
Даны два линейных однонаправленных списка L1 и L2. Разработать процедуру, которая формирует список L, включив в него по одному разу элементы, значения которых входят хотя бы в один из списков L1 и L2.
-
Даны два линейных однонаправленных списка L1 и L2. Разработать процедуру, которая формирует список L, включив в него по одному разу элементы, значения которых входят одновременно в оба списка L1 и L2
-
Даны два линейных однонаправленных списка L1 и L2. Разработать процедуру, которая формирует список L, включив в него по одному разу элементы, значения которых входят в список L1 и не входят в список L2.
-
Даны два линейных однонаправленных списка L1 и L2. Разработать процедуру, которая формирует список L, включив в него по одному разу элементы, значения которых входят ы в один из списков L1 и L2 и в то же вркмя не входят в другой.
-
Представить многочлен N – ой степени в виде линейного однонаправленного списка, элемент которого содержит значение коэффициента и показатель степени Х при этом коэффициенте. Причем одночлены многочлена могут быть не упорядочены по степени Х, а одночлены одной степени могут повторяться. Требуется привести подобные члены в этом многочлене. Вывести этот многочлен в порядке возрастания степеней Х.
-
Дана непустая последовательность слов в каждом из которых от 1 до 8 строчных латинских букв, между словами пробел, за последним словом точка. Напечатать эти слова в следующем порядке: сначала по алфавиту все слова из одной буквы, затем из двух букв и т.д.(одинаковые слова печатать один раз). Слова читаются из текстового файла и при обработке хранятся в двунаправленном упорядоченном списке.
-
L – циклический двунаправленный линейный список. Разработать рекурсивную подпрограмму, которая удаляет из списка L все элементы, у которых одинаковые соседи(первый и последний считать соседяями). Тип информационного поля элемента списка произвольный.
-
L – циклический двунаправленный линейный список. Разработать рекурсивную подпрограмму, которая определяет является ли список пустым и подпрограмму, которая переставляет в обратном порядке все элементы списка между первым и последним вхождением элемента Е, если таких элементов не более двух. Тип информационного поля элемента списка произвольный.
-
Используя структуру данных стек вычислить значение выражения с учетом приоритетности операций. 2+3+7*5+12/3. Выражение читается из текстового файла. Результат представить в форме выражения и его значения и вывести его на принтер.
-
Используя структуру данных стек вычислить значение выражения с учетом приоритетности операций. (32*7+2)/2 –(44-11). Выражение читается из текстового файла. Результат представить в форме выражения и его значения и вывести его на принтер.
-
Используя структуру данных стек вычислить значение выражения, предварительно преобразовав его в постфиксную форму. Выражение читается из текстового файла. Результат представить в форме выражения и его значения и вывести его на принтер.
-
В текстовом файле содержаться английские слова, являющиеся словарными. Используя структуру линейный список(упорядоченный) информационная часть которого содержит Английское слово и его перевод на русский язык. Удалить из файла одинаковые слова и выполнить грубый перевод английского текста. Результат из списка записать в типизированный файл а результат перевода вывести на принтер.
-
В тектовом файле записано без ошибок логическое выражение по следующей форме:
<ЛВ> ::= true| false | (not <ЛВ>)|(<ЛВ> or <ЛВ>)|(<ЛВ> and <ЛВ>)
Используя структуру данных Стек вычислить значение этого выражения. Результат вывести на принтер вместе с выражением.
-
Используя структуру данных стек сформировать и записать в файл постфиксную запись арифметического выражения, включающего скобки. Считывая созданное выражение из файла, вычислить его значение Результат: выражения в инфиксной форме, в постфиксной форме и его значение вывести на принтер.