КУРСОВАЯ РАБОТА

ЗАДАНИЕ

Разработать программу для решения задачи, указанной в вашем варианте задания.

Каждая используемая при решении задачи структура данных должна быть оформлена как самостоятельный тип — класс с набором операций, необходимых для работы с этой структурой. Класс (или иерархия родственных классов) размещается в отдельном модуле.

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

Необходимо создать два варианта программы — отладочную и рабочую версии.

Рабочая версия предназначается для решения задачи задания.

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

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

ВАРИАНТЫ ЗАДАНИЙ К КУРСОВОЙ РАБОТЕ

1. Программа преобразования выражения из инфиксной формы в постфиксную

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

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

Исходное выражение содержит идентификаторы с числом буквенно-цифровых символов <=6, целые десятичные константы (<=32767) и операции +, —, *, /, ^Л; операнды и операции отделяются друг от друга любым количеством пробелов.

При синтаксическом контроле проверяются: длина идентификатора (<=6), правильность его записи (первый символ — буква), значение константы (<=32767), наличие более одного подряд записанного знака операции, парность и правильность вложения скобок. Замечания:

• 1) программа использует стек на динамических переменных;
• 2) в программе предусмотреть булевские функции:

ТИеМат(81г:8Шд):Воо1еап; //строка идентификатор? ТИеОес(8^:8^пд):Воо1еап;// строка десятичная константа?

ТИеОрб(8^:81ппд):Воо1еап; //строка операнд?

ТИеОрс(81г:81ппд):Воо1еап; //строка операция?

2. Программа, имитирующая работу условной вычислительной машины

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

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

Исходное выражение содержит идентификаторы с числом буквенно-цифровых символов не больше шести, целые десятичные константы в диапазоне —32768 ... 32767 и операции +, —, *, /; операнды и операции отделяются друг от друга любым количеством пробелов.

Условная вычислительная машина имеет один регистр и следующую систему команд:

ЬЭ А — помещает операнд А в регистр;

ЭТ А — помещает содержимое регистра в переменную А;

АО А — прибавляет содержимое переменной А к регистру;

БВА — вычитает содержимое переменной А из регистра;

МЬ А — умножает содержимое регистра на переменную А;

ЭУ А — делит содержимое регистра на переменную А.

Замечания:

• 1) программа использует стек на динамических переменных;
• 2) в качестве промежуточных переменных использовать имена Т1, Т2 и т.д.
• 3. Программа моделирования работы магазина самообслуживания

Составить программу моделирования работы магазина самообслуживания с заданным числом касс К. Каждый покупатель подходит в момент времени /, к свободной кассе или кассе с наиболее короткой очередью и требует для своего обслуживания времени 1₂ (определяемого числом покупок).

Время прибытия покупателей и время обслуживания задаются в минутах задается с момента открытия магазина) и распределяются по нормальному закону с заданным средним значением М и отклонением 5.

Программа должна определить среднее, минимальное и максимальное время обслуживания (время нахождения в очереди плюс время расчета) одного покупателя (для К= 3 и К= 5).

Исходные данные: К, М, Р (число покупателей). Параметры

и /₂ для каждого покупателя определяются в программе с помощью генератора случайных чисел.

В отладочном варианте ^ и /₂ для каждого покупателя считывать из внешнего файла, сформированного вручную.

4. Программа выполнения арифметических операций

с длинными числами

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

Наборы исходных длинных целых чисел и операции, которые необходимо выполнять над ними, построчно вводятся из внешнего текстового файла в формате

число 1_операция_число2 (_ — символ пробела) числоЗ_операция_число4 • • •

например:

• -1592678 + 278291 15 178591 *-1756 2997518 --324277
• 5. Программа пирамидальной сортировки

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

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

Сравнить по быстродействию реализацию алгоритма пирамидальной сортировки для списка с полем значения — целым числом. С использованием такого списка построить демонстрационный вариант программы.

Размер рабочего исходного текстового файла — 100 записей.

6. Программа внутренней сортировки методом Неймана

Сравнить по быстродействию реализации метода Неймана (естественное слияние) для сортировки элементов односвязного списка и одномерного массива одинаковой длины.

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

Типы данных и их значения выбрать произвольно. Длины массивов и списков принять равными 100, 200, 500 (для их формирования использовать генератор случайных чисел).

7. Программа быстрой сортировки

Оценить характеристики быстрой сортировки (число сравнений ключей и число перестановок элементов) для сортировки:

• 1) упорядоченного массива;
• 2) случайного массива;
• 3) упорядоченного в обратном порядке массива.

Размер сортируемого массива: 10, 50, 100, 500 (для формирования использовать генератор случайных чисел).

8. Программа поразрядной сортировки

Оценить характеристики метода поразрядной сортировки числового массива с использованием связанных списков. Сортировка выполняется сначала для младших значащих цифр, затем полученные списки сливаются в файл и сортируются по следующей значащей цифре, и т.д. до старшей цифры. В характеристики быстродействия включить: число операций сравнения, число переключений связей для элементов списков (аналог числа перестановок). Исходный массив состоит из 500 случайных чисел, равномерно распределенных в диапазоне от 0 до 9999.

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

9. Программа индексно-последовательного поиска

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

Сравнить по среднему времени поиска (аналог — среднее число просмотренных при поиске элементов) реализации индексно-последовательного поиска:

• 1) число индексов: 1 и 2;
• 2) размер индекса: 3 и 10.

Файл с исходным списком символических имен сформировать с помощью подпрограммы подготовки данных следующим образом: проанализировать текст любой программы, содержащей не менее 200—300 строк, и включить в таблицу все ключевые слова и идентификаторы программы.

10. Программа поиска по дереву

Составить программу формирования таблицы имен в виде дерева поиска и последующего поиска имени в таблице.

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

В качестве аналога скорости поиска принять среднее число просмотренных при поиске элементов.

Оценить проигрыш в скорости построения дерева.

Файл с исходным списком символических имен сформировать с помощью подпрограммы подготовки данных следующим образом: проанализировать текст любой программы, содержащей не менее 200—300 строк, и включить в таблицу все ключевые слова и идентификаторы программы.

11. Программа поиска методом расстановки

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

Сравнить по скорости поиска в таблице (в качестве аналога скорости поиска принять среднее число просмотренных при поиске элементов) различные варианты выбора функции расстановки, проанализировать 3—4 варианта.

Оценить коэффициент заполнения таблицы и среднюю длину поиска при занесении 25%, 50%, 75% и 100% имен из файла. Оптимизировать параметры функции расстановки по результатам этих исследований.

Файл с исходным списком символических имен сформировать с помощью подпрограммы подготовки данных следующим образом: проанализировать текст любой программы, содержащей не менее 200—300 строк, и включить в таблицу все ключевые слова и идентификаторы программы.

12. Программа нахождения максимального пути

в ориентированном графе

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

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

• — формирование пустого графа;
• — проверка наличия узлов в графе;
• — проверка наличия заданного узла в графе;
• — проверка наличия дуги между заданными узлами графа;
• — включение нового узла в граф;
• — исключение узла из графа;
• — включение дуги с заданным весом между двумя заданными узлами (если дуга существует, то устанавливается нужный вес);
• — исключение дуги между заданными узлами с выдачей веса дуги.

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

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

13. Программа нахождения минимальных расстояний

между узлами графа

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

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

• — формирование пустого графа;
• — проверка наличия узлов в графе;
• — проверка наличия заданного узла в графе;
• — проверка наличия дуги между заданными узлами графа;
• — включение нового узла в граф;
• — исключение узла из графа;
• — включение дуги с заданным весом между двумя заданными узлами (если дуга существует, то устанавливается нужный вес);
• — исключение дуги между заданными узлами с выдачей веса дуги.

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

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

14. Программа планирования действий

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

Результаты решения выдавать в виде перечня работ, которые необходимо выполнить в каждый очередной момент времени,

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

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

• — формирование пустого графа;
• — проверка наличия узлов в графе;
• — проверка наличия заданного узла в графе;
• — проверка наличия дуги между заданными узлами графа;
• — включение нового узла в граф;
• — исключение узла из графа;
• — включение дуги с заданным весом между двумя узлами;
• — исключение дуги между заданными узлами.

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

15. Программа построения сетевого графика и определения характеристик его работ при неограниченном числе

исполнителей

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

Характеристики сетевого графика:

• — самые ранние моменты времени завершения работ, оканчивающихся в каждом узле;
• — самые поздние моменты времени завершения работ, оканчивающихся в каждом узле;
• — перечень узлов, у которых эти характеристики равны (критический путь).

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

• — формирование пустого графа;
• — проверка наличия узлов в графе;
• — проверка наличия заданного узла в графе;
• — проверка наличия дуги между заданными узлами графа;
• — включение нового узла в граф;
• — исключение узла из графа;
• — включение дуги с заданным весом между двумя заданными узлами (если дуга существует, то устанавливается нужный вес);
• — исключение дуги между заданными узлами с выдачей веса дуги.

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

16. Программа построения сетевого графика и определения характеристик его работ при ограниченном числе

исполнителей

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

Характеристики сетевого графика:

• — самые ранние моменты времени завершения работ, оканчивающихся в каждом узле;
• — самые поздние моменты времени завершения работ, оканчивающихся в каждом узле;
• — перечень узлов, у которых эти характеристики равны (критический путь).

Составить программу планирования действий и решения перечисленных выше задач при условии, что параллельно может выполняться не более т работ (т>= 1).

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

• — формирование пустого графа;
• — проверка наличия узлов в графе;
• — проверка наличия заданного узла в графе;
• — проверка наличия дуги между заданными узлами графа;
• — включение нового узла в граф;
• — исключение узла из графа;
• — включение дуги с заданным весом между двумя заданными узлами (если дуга существует, то устанавливается нужный вес);
• — исключение дуги между заданными узлами с выдачей веса дуги. Дополнительно включаются все операции, необходимые для работы с графом при решении задачи.
• 17. Библиотечный модуль для реализации одномерных динамических массивов

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

Набор операций со списком:

• — создание пустого списка;
• — удаление списка из памяти;
• — добавление элемента в начало списка.

Основной набор операций с одномерным динамическим массивом:

• — создание пустого массива заданной длины;
• — удаление массива из памяти;
• — получение указателя на элемент с заданным индексом;
• — запись значения в массив;
• — чтение элемента массива;
• — определение размера массива.

Реализовать матричные операции (копирование, сложение, скалярное произведение массивов, вывод и др.)

Продемонстрировать работу с динамическими массивами.

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

Реализовать библиотечный модуль для работы с двумерными массивами, память под которые выделяется динамически во время вы-пол нения программы. В качестве базовой (родительской) структуры для динамического массива использовать односвязный список.

Набор операций со списком:

• — создание пустого списка;
• — удаление списка из памяти;
• — добавление элемента в начало списка.

Основной набор операций с двумерным динамическим массивом:

• — создание пустого массива заданной длины;
• — удаление массива из памяти;
• — получение указателя на элемент с заданным индексом;
• — запись значения в массив;
• — чтение элемента массива;
• — определение размера массива.

Реализовать матричные операции (копирование, сложение, умножение, транспонирование, вывод и др.)

Продемонстрировать работу с динамическими массивами.

19. Программа построения дерева оптимального поиска

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

Файл с исходным списком символических имен сформировать с помощью подпрограммы подготовки данных следующим образом: проанализировать текст любой программы, содержащей не менее 200—300 строк, и включить в таблицу все ключевые слова и идентификаторы программы.

20. Реализация разреженного вектора

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

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

Продемонстрировать операции с созданным типом данных.

21. Реализация разреженной матрицы на базе списка ненулевых элементов

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

Дополнительно предусмотреть и реализовать операции вывода сообщений о возможных ошибках при работе с разреженными матрицами, а также матричные операции (копирование, сложение, умножение, транспонирование и др.)

22. Реализация разреженной матрицы

на базе списка указателей

Реализовать объект — разреженную матрицу на базе списка указателей на списки ненулевых элементов строк. Каждый элемент списка указателей содержит номер строки и указатель на список ненулевых элементов этой строки. Каждый элемент списка ненулевых элементов содержит значение ненулевого элемента строки матрицы и его номер в строке (номер столбца). Элементы матрицы — целые числа.

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

Предусмотреть и реализовать операции вывода сообщений о возможных ошибках при работе с разреженными матрицами, а также матричные операции (копирование, сложение, умножение, транспонирование и др.)

23. Реализация множества строк на базе линейного списка строк

Реализовать объект — множество с базовым типом String на основе односвязного списка строк стандартного типа ShortString. Строки располагаются в множестве в порядке возрастания их значений. Реализовать все операции, определенные для стандартного типа множества в Delphi.

Продемонстрировать операции с созданным типом данных.

Проанализировать текст любой программы, содержащей 20— 30 строк, и вывести зарезервированные слова программы.

24. Реализация множества строк на базе динамического массива строк

Реализовать объект — множество с базовым типом String на основе массива указателей на строки стандартного типа String, размещаемого в динамической памяти. Строки в множестве располагаются в порядке возрастания их значений. Реализовать все операции, определенные для стандартного типа множества в Delphi.

Продемонстрировать все операции с созданным типом данных.

Проанализировать текст любой программы, содержащей 20— 30 строк, и вывести зарезервированные слова, не использованные в программе.

25. Реализация множества целых чисел

на базе линейного списка

Реализовать объект — множество с базовым типом Integer на основе односвязного списка целых чисел. Числа располагаются в множестве в порядке возрастания их значений. Реализовать все операции, определенные для стандартного типа множества в Delphi.

Продемонстрировать все операции с созданным типом данных. Вывести все целые числа в заданном текстовом файле.

26. Реализация множества целых чисел

на базе динамического массива

Реализовать объект — множество с базовым типом Integer на основе массива величин типа Integer, размещаемого в динамической памяти. Числа располагаются в множестве в порядке возрастания их значений.

Реализовать все операции, определенные для стандартного типа множества в Delphi.

Продемонстрировать все операции с созданным типом данных. Вывести все отрицательные целые числа в заданном текстовом файле.

27. Реализация множества вещественных чисел

на базе линейного списка

Реализовать объект — множество с базовым типом Real на основе односвязного списка вещественных чисел. Числа располагаются в множестве в порядке возрастания их значений. Реализовать все операции, определенные для стандартного типа множества в Delphi.

Продемонстрировать операции с созданным типом данных.

Вывести все числа в заданном текстовом файле.

28. Реализация множества вещественных чисел на базе динамического массива

Реализовать объект — множество с базовым типом Real на основе массива величин типа Real, размещаемого в динамической памяти. Числа располагаются в множестве в порядке возрастания их значений. Реализовать все операции, определенные для стандартного типа множества в Delphi.

Продемонстрировать все операции с созданным типом данных. Вывести все не целые числа в заданном текстовом файле.

29. Реализация длинных строк на базе циклического списка

Реализовать объект — длинная строка (>256 символов) на базе циклического списка стандартных строк. Реализовать все операции, определенные для стандартного типа строка в Delphi.

Продемонстрировать все операции с созданным типом данных. Проанализировать текст любой программы, содержащей 20 — 30 строк, сцепить в одну строку (отделяя пробелом) все идентификаторы программы (без повторений) и вывести полученную строку в файл результатов.

30. Программа сортировки данных во внешнем файле

Составить программу сортировки данных, содержащихся в текстовом файле последовательного доступа, методом п лент (п — четное число).

Тип и числовые характеристики данных в исходном файле выбрать произвольно.