В.В. Беликов

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

Оформление задания:

Задание должно быть оформлено на украинском или русском языках.

Титульный лист. Должен быть верхний колонтитул, содержащий надписи:

Дніпропетровський національний університет

Фізико-технічний інститут

Кафедра систем автоматизованого управління

и нижний колонтитул, указывающий год оформления задания. Должно быть указано название задания:

КУРСОВЕ ЗАВДАННЯ

по курсу інформатики та обчислювальної техніки

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

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

Раздел 1. Специальные случаи сортировки

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

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

Задача 1. Сортировка путем индексирования

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

Этого можно достичь индексированием с последующей сортировкой индекса.

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

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

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

Задание.

Зарезервировать массив A, подлежащий сортировке, размером 100 строк  5 столбцов и соответствующий массив индекса.

Заполнить первые 20 строк массива, подлежащего сортировке, следующим образом:

- первый столбец – ключевой – заполнить целыми случайными числами от 0 до 19, используя генератор случайных чисел.

- второй столбец заполнить числами, равными 20 минус значение ключа.

- остальные столбцы заполнить нулями.

Построить простой индекс и отсортировать его по возрастанию.

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

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

Поиск ключа можно реализовать одним из двух способов. 1) Простой перебор индексного массива сначала до нахождения нужного значения либо до того, как значение ключа в индексе превысит заданное значение ключа. 2) Дихотомический поиск. Вначале проверить значение ключа в середине индексного массива, чтобы определить, находится ли искомое значение в первой или второй половине массива, и далее искать только в этой половине. Затем проверить значение ключа в середине выбранной оставшейся части. При простом переборе, например, в массиве из 128 элементов, и при равномерном распределении запрашиваемых значений ключа, количество проверок будет от 1 до 128, в среднем около 64, тогда как при дихотомическом поиске оно не превысит 7.

Задача 2. Сортировка динамической цепочки путем индексирования

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

Задание

Динамическую цепочку следует сформировать из 20 записей, содержащих 3 поля. Первое поле заполняется случайными значениями от 0 до 19, второе поле – значениями, равными 20 минус значение первого поля. Третье поле – поле-указатель для связывания динамической цепочки. Соответственно, в индексном массиве первый столбец должен содержать значение ключа, а второй столбец – указатель на соответствующую запись в цепочке. В остальном, задание такое же, как в Задаче 1.

Задача 3. Сортировка связанного списка

Задание

Нужно сформировать динамическую цепочку из 20 записей, содержащих 3 поля. Первое поле заполняется случайными значениями от 0 до 19, второе поле – значениями, равными 20 минус значение первого поля. Третье поле – поле-указатель для связывания динамической цепочки. Такую цепочку нужно отсортировать, не используя индекс, например, используя метод пузырька, переставляя значения полей-указателей в списке. При этом записи в памяти физически не перемещаются. Отличие от обычного метода пузырька состоит в том, что для перестановки двух записей в последовательности нужно переписать 3 поля-указателя.

Пусть есть цепочка:

Для замены в ней местами 2 и 3 элементов нужно переставить указатель с 1-го элемента на 3-й, с 3-го на второй и со 2-го на 4-й.

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

Задача 4. Изменения в таблице с использованием индекса в виде связанного списка

Еще одна ситуация. В двумерный массив часто вносятся изменения – добавляются или удаляются строки, и нужно, чтобы после каждого изменения он оставался отсортированным по одному из столбцов. Если нужно добавить строку между, например, 45-й и 46-й строками или удалить 10-ю строку в массиве из 5000 строк, при прямолинейном подходе это потребует переписывания почти пяти тысяч строк на новое место. Использование простого индекса намного ускоряет решение этой задачи. Но если изменения в массив вносятся часто, индексный массив также придется часто переписывать. Если же построить индекс в виде связанного списка, добавить новый элемент в этот список можно будет без перемещения остальных элементов – просто переставив указатели в индексном списке.

Задание

Зарезервировать массив, подлежащий изменениям, размером 100 строк  3 столбца.

Заполнить первые 20 строк этого массива следующим образом:

- первый столбец – ключевой – заполнить целыми числами от 1 до 100 с шагом 5.

- остальные столбцы заполнить нулями.

Таким образом, этот массив будет изначально отсортирован по ключу.

Построить два индекса в виде связанных списков. Первый должен содержать два информационных поля – для значения ключа и для номера строки, соответствующей этому ключу. Количество записей в нем должно быть равно количеству заполненных строк в массиве. Второй индекс должен содержать информационные поля с номерами незаполненных строк в массиве.

Запрашивать команды на добавление или удаление строк или на прекращение работы программы.

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

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

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

При вводе команды прекращения работы завершать работу программы.

Задача 5. Сортировка слиянием файлов

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

В таком случае можно загружать этот файл по частям, сортировать каждую часть одним из способов, например, методом пузырька, или, если записи в файле имеют много полей, с помощью простого индекса, и записывая каждую часть в отдельный файл. Затем слить отсортированные части в один файл. Например, если получилось две части, причем 1-я часть содержит значения 1,10,12,15, а 2-я – значения 2,5,6,8,11, слияние производится таким образом: в файл слияния пишется первое значение из 1-й части, так как оно меньше, чем первое значение 2-й части, затем с первого по четвертое значения из 2-й части, так как они меньше второго значения 1-й части, и так далее. Аналогично можно сливать три или более файлов с отсортированными частями исходного файла. Если количество частей слишком велико, их можно сливать попарно в несколько этапов.

Задание

Подготовить файл, содержащий 20 случайных целых чисел в диапазоне от 1 до 20. Вывести его на дисплей и записать на диск.

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