Требования

Лабораторная работа 3

Тема: Динамические структуры данных

Постановка задачи

Написать программу на языке Object Pascal, которая для заданной динамической структуры данных (ДСД):

1) реализует базовые действия в отдельном модуле:

a. создание пустой ДСД

b. добавление нового элемента

c. удаление элемента

d. проверка ДСД на пустоту

e. поиск элемента по ключу

f. уничтожение ДСД

2) реализует дополнительные действия, указанные в индивидуальном варианте

3) в главной программе обеспечивает доступ к действиям при помощи меню и демонстрирует их выполнение на тестовых примерах.

Требования

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

Построение индивидуальных вариантов заданий

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

Динамические структуры данных:

1) Линейный однонаправленный список без заглавного звена.

2) Линейный однонаправленный список с заглавным звеном.

3) Циклический однонаправленный список с заглавным звеном.

4) Линейный двунаправленный список без заглавного звена.

5) Линейный двунаправленный список с заглавным звеном.

6) Циклический двунаправленный список с заглавным звеном.

7) Стек.

8) Очередь.

Действия над динамическими структурами данных:

1) Создать список L1.

2) Создать два списка L1 и L2.

3) Создать три списка L1, L2 и L.

4) Проверить на равенство списки L1 и L2.

5) Проверить, есть ли в списке L1 хотя бы два одинаковых элемента.

6) В списке L1 из каждой группы подряд идущих равных элементов оставить только один.

7) Оставить в списке L1 только первые вхождения одинаковых элементов.

8) Определить входит ли список L1 в список L2.

9) Вставить в список L1 за первым вхождением заданного элемента все элементы списка L2, если заданный элемент входит в L1.

10) Сформировать новый список L3, включив в него по одному разу те элементы, которые входят хотя бы в один из списков L1 и L2.

11) Сформировать новый список L3, включив в него по одному разу те элементы, которые входят одновременно в оба списка L1 и L2.

12) Сформировать новый список L3, включив в него по одному разу те элементы, которые входят в список L1 и не входят в L2.

13) Добавить в список L1, элементы которого упорядочены по неубыванию, новый элемент так, чтобы сохранилась упорядоченность.

14) Объединить два упорядоченных по неубыванию списка L1 и L2, построив новый список L3.

15) Объединить два упорядоченных по неубыванию списка L1 и L2, меняя соответствующим образом ссылки в L1 и L2 и, присвоив полученный список параметру L1.

16) Удалить из списка L1 все вхождения элемента с заданным информационным полем.

17) Перевернуть список L1, т.е. изменить ссылки в этом списке так, чтобы его элементы оказались расположены в обратном порядке.

18) Подсчитать количество элементов списка L1, у которых равные соседи.

19) Определить, есть ли в списке L1 хотя бы один элемент, который равен следующему за ним (по кругу) элементу.

20) В списке L1 переставить в обратном порядке все элементы между первым и последним вхождением заданного элемента, если заданный элемент входит в список не менее двух раз.

21) Удаляет из списка L1, содержащего не менее двух элементов, все элементы у которых равные "соседи" (первый и последний элементы считать соседями).

22) Удвоить в списке L1 каждое вхождение заданного элемента.

23) Заменить в списке L первое вхождение списка L1(если такое есть) на список L2.

24) Проверить, является ли содержимое текстового файла правильной записью формулы следующего вида:

<формула>::=<терм>|<терм>+<формула>| <терм>-<формула>

<терм>::=<имя> | (<формула>) | [<формула>]|{<формула>}

<имя>::=x | y | z

(решение описать в виде функции или процедуры)

25) В текстовом файле f записана без ошибок формула следующего вида:

<формула>::=<цифра> | М(<формула>,<формула>) | m(<формула>,<формула>)

<цифра>::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

где M обозначает функцию max, а m – min.

Вычислить (как целое число) значение данной формулы.

26) В текстовом файле записано без ошибок логическое выражение(ЛВ) в следующей форме:

<ЛВ>::=true | false | (ù<ЛВ>) | (<ЛВ> Ù <ЛВ>) | (<ЛВ> Ú <ЛВ>)

где знаки ù, Ù, Ú обозначают соответственно отрицание, конъюнкцию и дизъюнкцию.

Вычислить (как boolean) значение этого выражения.

27) В текстовом файле записан текст, сбалансированный по круглым скобкам <текст>::=<пусто> | <элемент> <текст>

<элемент>::=<буква> (<текст>)

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

28) За один просмотр файла f типа TF, где TF= file of real, без использования дополнительных файлов напечатать элементы файла в следующем порядке: сначала – все числа, меньшие a, затем – все числа из отрезка [a,b], и наконец – все остальные числа, сохраняя исходный взаимный порядок в каждой из этих трех групп чисел (a, b –заданные числа, a<b).

Индивидуальные варианты заданий

30) Представить масив натуральных чисел в виде линейного однонаправленного списка

Описать процедуру, упорядочивающую по неубыванию числа непустого списка L с помощью алгоритма поразрядной сортировки (рис. 1, где-n предполагается равным 2).

Создать 10 пустых подсписков (по количеству цифр), а затем, просматривая числа исходного списка, занести k-й подсписок все числа, оканчивающиеся цифрой k, после чего эти подсписки объединить в один список L записав в последнее звено k-го подсписка ссылку на начало (k+1)-го подсписка. Далее аналогичный метод применяется по отношению к предпоследней цифре чисел (не нарушая при этом упорядоченность по последней цифре), затем—по отношению к третьей от конца цифре и т. д.

Рис. 1

31). Многочлен

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

Описать тип данных, соответствующий такому представлению многочленов и определить следующие функции и процедуры для работы с этими списками-многочленами.

1. Определить логическую функцию равно (p,q), проверяющую на равенство многочлены p и q.
2. Определить функцию знач (p,x), вычисляющую значение многочлена p в точке x.
3. Определить процедуру диф (p,q), которая строит многочлен p-производную многочлена q.
4. Определить процедуру слож (p,q,r), которая строит многочлен p-сумму многочленов q и r.
5. Определить процедуру вывод (p,v), которая печатает многочлен p как многочлен от переменной, однобуквенное имя которой является значением литерного параметра v.
6. Определить процедуру ввод (p), которая считывает из входного файла безошибочную запись многочлена (за ней-пробел) и формирует соответствующий список-многочлен p.

Рекомендованная литература

1. Axo А., Хопкрофт В., Ульман Джеффри Д. Структуры данных и алгоритмы.: М.: Издательский

дом "Вильямc", 2003. — 384 с.

2. Бакнел Джулиан М. Фундаментальные алгоритмы и структуры данных в Delphi. – СПб: ООО "ДиаСофтЮП", 2003. – 560 с.

3. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. - М.: МЦНМО, 1999. - 960 с.

Поиск по сайту: