 |
1.2.6. Сортировка таблицы адресов
|
|
|
|
1. 2. 6. Сортировка таблицы адресов
Объем данных, помещенных в каждую из записей файла, может быть столь большим, что перемещение самих записей является нецелесообразным из-за больших накладных расходов. В этом случае может быть использована вспомогательная таблица указателей на записи, так что вместо перемещения данных перемещаются эти указатели.
Такой метод называется сортировкой таблицы адресов. Таким образом, сортировке подвергается не сам файл, а подфайл, каждая запись которого состоит из поля указателя на запись исходного файла и поля ключа этой записи.
Первоначально элемент в позиции j таблицы указателей указывает на j-ю запись. После окончания сортировки первый указатель указывает на запись файла с наименьшим ключом, второй указатель - на запись файла со следующим по порядку сортировки ключом и т. д.
Сортировку таблицы указателей можно выполнять одним из методов внутренней сортировки.
2. Лабораторное задание
1. В ходе предварительной подготовки разработать программу сортировки информации в файлах по значению ключевого поля, указанного в варианте задания к лабораторной работе № 3.
В программе предусмотреть:
· сортировку элементов набора данных заданным методом с выводом на экран монитора промежуточных результатов после каждого просмотра;
· вывод отсортированного набора данных;
· подсчет числа сравнений и перестановок, производимых при сортировке.
2. Отладить и выполнить разработанную программу. Исходными данными являются файлы, созданные в ходе выполнения лабораторной работы № 2. Метод сортировки и тип сортируемой информации определяются номером варианта.
|
|
|
3. Порядок выполнения работы
1. Открыть программный проект, созданный в лабораторной работе №2, включить в него и отладить разработанную программу сортировки.
2. Исследовать быстродействие и устойчивость заданного алгоритма сортировки. Продемонстрировать работу программы преподавателю.
3. Оформить и защитить индивидуальный отчет по лабораторной работе.
4. Содержание отчета
1. Краткое описание алгоритмов сортировки информации.
2. Задание на лабораторную работу.
3. Алгоритм разработанной программы. Описание всех переменных, массивов и сложных структур данных, используемых в программе.
4. Текст отлаженной программы.
5. Результаты работы программы в виде распечаток вводимой информации и упорядоченной информации.
6. Выводы по быстродействию и устойчивости используемого метода сортировки.
Лабораторная работа № 4
ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ ПОИСКА ИНФОРМАЦИИ
Цель работы: изучение основных методов поиска информации в ИС и получение практических навыков их алгоритмизации и программирования.
1. Теоретическая часть
1. 1. Общие положения
В информационных системах под задачей поиска понимают быстрое нахождение записи, содержащей необходимую информацию. Как и в случае сортировки, каждая запись имеет специальное поле, содержащее значение ключа, однозначно определяющего свою запись.
Алгоритмом поиска является определенный алгоритм, который воспринимает некоторый аргумент А и исследует последовательность записей X 
, X 
,..., X 
с тем, чтобы найти некоторую запись, ключ которой равен А. Целью поиска является информация, содержащаяся в записи, ассоциированной с данным ключом.
При реализации алгоритма поиска существуют две возможности его окончания: либо поиск оказался удачным, т. е. позволил определить положение соответствующей записи, содержащей ключ А, либо неудачным, т. е. показал, что аргумент А не может быть найден ни в одной из записей.
|
|
|
В настоящей лабораторной работе изучаются внутренние, статические методы поиска, основанные на последовательном просмотре всех записей и сравнении их ключей.
|
|
|
