Методичка по Системному программированию (лабораторные работы с 3 по 6)

РАБОТА 1>1 3, СОРТИРОВКА С ИСПОЛЬЗОВАНИЕМ ДОПОЛНИТЕЛЬНЫХ МАССИВОВ Одним из путей повышения эффективности ОС является упорядочение массива в процессе его заполнения, т.е. каждый поступающий вновь ключ находит свое место среди уже поступивших. Различные методы сортировки с использоваиисм дополнительных массивов применяются в разных ситуациях, возникающих при обработке данных.

Рассмотрим наиболсс важныс из иих. 3,1, Метод вставки Пусть требуется сформировать упорядоченный массив ключей В(Дг). Предположим также, что источником является неупорядоченный массив А(дг). Суть метода состоит в том, что каждый новый элемент а, вставляется в уже упорядоченную совокупность Ь>,Ьз„...Ь; > на подходящее место по следующему алгоритму: 1) 7 ° 1; 2) сравнить элементы Ь и а;; если а; не соответствует месту/ по условию сортировки, то перейти к п.5; 3) сдвинуть вправо все элементы от Ь; 1 до Ь на одну позицию; 4) присвоить значение Ь = аа т.е. поместить а; на /-е место; 5) перейти к рассмотрению следующего занятого места: у=1'+1; 6) если 7'<1-1, то повторять с п.2; 7) поместить аг на первое незанятое место, Ь.

= а,; 8) пере>ути к вводу следующего, элемента а;, т.с. г' з+1. 3.2. Метод двухпутевого слияния Этот метод применяется в случае, когда объединяются два упорядоченных массива. Пусть требуется объединить два массива ключей А(А) и В(М), упорядоченных по возрастанию, а один массив С(К), К=А> +М, также упорядоченный по возрастанию. Суть метода состоит а сравнении очередной пары ключей а; н Ь и занесении минимального нз них в массив С. При этом возможны варианты реализации данного метода: а) замести в очередной элемент массиоа с»1 ключ а; н сравнить его с ключом Ь, если Ь;< с»1, то с»> = Ь, затем перейти к занесению Р следующего элемента с»>ь ! = Ь>ь> и сра««синю с а» и т.д.; б) срао«ить ключи а; н Ь) и минимальный из них занссти на место с»н затем перейти к следующему элементу с»>, > и текущему значение ключа а; > или Ь,, Следует отмстить, что совпадения ключей а и Ь, ках правило, нс ! допускнютсн, о противном случае в масси«С ключ вносится однократно.

3.3. Адресная сортировка Пусть задан массив ключей Х(Д>), предста«лнннпих собой цслыс положительныс числа. Адресная сортировка выполняется в доа этапа: 1) подсчет числа ключей с одинаковычи значениями о массиве Х(ву). Рсзультьты подсчета заносятся в массив 1(М), где А(1) - число к.>ючей н массиве Х(А>), имеющих значснис й а М - максимально возможное значение ключа; 2) заполнение чассива У(1т) упорядоченными значениями ключей иа ос«овс данных, >юлучснных «массиве А(М). Л>троеная сортировка упорядочивает ключи по нсубыванию„ио можст использоваться и для упорндочения чисел по нсвозрастанию. Рассмотрим подробно алгоритм адрес«ой сортировки: !) К=О, чассив А(М)=0; 2) при изменении 1 от 1 до Ю для массива Х(Д>) сформировать масси«А(М) по формуле А(Х(/))-А(Х(/))+1; 3) при изчснснии / от 1 до М для массива Л(М) сформировать массив У(Л'): если Л(>) О, перейти к п,5„ 4) при изменении У от 1 до Л(>) присвоить У(К)" 1, К=К +1; 5) перейти к п.З, если I<М.

Таким образоль массив Л содержит распределение частот понвлснин ключей « заданной последователь«ости в порядке их возрастанию Лля получении отсортированной последовательности ключей в пмходной массив У текущее значение ключа 1 записывается столько раз, сколько ключ 1 встречается и исходной послсдоаательиости (внутренний цикл по .>). Следует отмстить, что для отсортированной иос,>сдовательиости можно использо«ать исходный массив Х(А). В случас использования языков програчмиро«ания, позволяющих згла«ать мин«мальиос значение индекса массива, мож«о сохратитл затраты памяти иа массив А с соответствующей модифихацисй алгоритма.

Содержание отчета: !) структурная схема адгоритма; 2) текст программы; 3) распечатка указанных о задании розу.>ьтатов выполнен>щ программ. Тобдичи 3.1 1!онер вв рнвнтв И-15; упорадо бсз повто сннй М 1б; упорадо нню без повго М 14; упорадо с понто синан М 15; упорало нню с понто сг Ы 16; >'попало бсз понто сннй б М 14; упорадо нню без прото 1 Ы 15; >порапо ,нню с понто 4.1.

Реализация стека 1.1РО Тибдини 3 2 4.2. Реализация стека Р1РО 1О 11 Задание. Разработать и отладить три программы сортирооки, выводя на печать исходиыс состояния массивов и состояния заполннсмого массива после каждого изменения; пусть ключи - цслыс положитсльннс числа. Варианты заданий приведены в табл. 3.1 и 3.2, где для каждого метода заданы размерности массивое, критерий упорядочения и вариант реализации. Для адресной сортировки задано максимальное число повторения ключей, а также имя массива для хранения результата.

РАБОТА )ч' 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ СТЕКА Стеком называется специально организованная память, которая позволяет записывать и считывать информацию только по определенной дисциплине. При этом возможны две дисциплины обслуживания записей: (ЛРО (последним пришел - псрпнм ушел) - часто именно эта реализация называется стсколг; Р(РО (первым пришол - первым ушел) - е литсрат>рс часто называется деком. Стек должен выполнять следующие функции: 1) запись элемента е стек; 2) чтение элемента из стека, причем прочитанная информация должна стираться из стека; 3) оповещение об экстремальных ситуациях: - попытка записи о заполненный стек; - пппнтка чтения из пустого стека. Программная рсализация стека заключается в выделении одномерного массива Л(А1), где Аг - глубина стека, и указателя стека К- простой переменной целого типа, указывающей адрес последнего заполненного элемента или адрес первой свободной ячейки (н зависимости от желания авторов).

Стек типа 1.!РО находит широкое применение в ОС для организации нложснных циклов, вложенных подпрограмм и в других случаях. Стек типа ГГРО лежит о основе оргшгнзаг1ии различного типа очередей. Возможно несколько вариантов программной реализации стека: а) стек заполняется, начиная с первого индекса, это наиболее экономичный способ, тах ках здесь не происходит сдвига информации; б) заполнение стека со стороны алнав, т.с. с последнего инлскса. Д.чя дека существует много программных реализаций, которые характеризуются следующими особенностями: а) заполнение стека последовательно, начиная с первого индекса без сдоига информации, и считывание всегда 1-го элемента массива со сдвигом оставшихся элементов влево; б) заполнение стека, начиная с псроого индекса, со сдвигом инфОрмации при записи и при считывании; Таблица 4.! 5(~) = 13 12 в) заполнение стека со стороны «дна», т.е.

с последнего индекса без сдвига информации, а считывание из последнего индекса со сдвигом информации вправо; г) «кольцевой» стек отличается тем, что нет сдвига информации ни при записи, ни при считывании, но вводится более сложная система указателей: указатель первого в очереди элемента (начало очереди), указатель конца очереди; здесь возникает также проблема организации «кольцевого» перехода указателей стека. Содержание отчета: 1) структурная схема алгоритма; 2) текст программы; 3) распечатка указанных в задании результатов выполнения программ.

Задание. Разработать программу реализации стеков для двух дисциплин с использованием указателя выбора дисциплины обслуживания, значение которого вводится в режиме диалога. Программа должна продемонстрировать все возможные действия, выполняемые стеком, в диалоговом режиме. Варианты заданий приведены в табл. 4.1, где указана глубина стека и вариант реализации стека Р1РО, причем вариант реализации стека 1.1РО следует выбрать самостоятельно, исходя из соображений совместимости программ для двух видов стека.

РАБОТА Х 5. ХЭШИРОВАНИЕ КЛЮЧЕЙ Поиск данных в больших расширяющихся таблицах, размеры которых заранее не известны, приходится вести другим способом. Линейный поиск здесь неприменим из-за размеров таблицы, а двоичный потребовал бы прн добавлении каждой новой записи проводить повторное упорядочение (сортировку) таблицы по возрастанию ключа, что выливалось бы в дополнительные временные потери. Поэтому таблицы организуются по способу перемешанных (разбросанных, рэндоми- зированных, с преобразованием ключа, хэш-таблиц - аналогичные названия) таблиц.

В перемешанных таблицах, как и в таблицах с прямым доступом, используется адресная функция 1(К), которая по заданному значению ключа К позволяет определить значение адреса 1(К). Однако здесь заранее допускается, что 1(К) не обеспечивает однозначности, т.с. могут возникать ситуации (называемые коллизиями), при которых 1(К)=1(К.), К,.я К.. Вектор хранения, куда отображаются записи, имеет длину Ф > М, где М вЂ” число табличных записей. Предполагается, что М сверху ограничено.

Простейший алгоритм открытого перемешивания при занесении в таблицу: 1) по заданному К вычислить 1=11'К); 2) если запись с номером 1 в таблице пустая, то занести в нее новую запись; 3) если нет, то положить 1 П+1)тоИ А1 и вернуться к п.2. Очевидно, что поиск записи по заданному ключу аналогичен. Таким образом, последовательность процедур 2 и 3 обеспечивает линейный поиск свободной позиции в таблице для помещения в нее коллизнйной записи.

Неравномерность размещения записей, а следовательно, скопление коллизийных записей в некоторых областях таблицы увеличивает линейный поиск. Поэтому в ряде случаев улучшить общую картину можно, изменив процедуру 3 данного алгоритма. В этом случае полагают( (1+Р)тоб А1. Пусть о = М/М, где М - текущее значение для числа записей, уже включенных в таблицу. Тогда приближенное значение для длины поиска в таблице т.е. длина поиска зависит от коэффициента заполнения таблицы. Достаточно интересным фактом для перемешанных таблиц является то, что средняя длина поиска зависит не от размера таблицы, а только от ее заполнения.

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

В организации перемешанной таблицы каждая запись имеет усложнение в своей структуре. В ней вводится поле, где размещается адрес первой коллизийной записи, расположенной в «сцепленной» таблице. Точно так же усложняется структура записей «сцепленной» таблицы, поскольку в них хранят адрес размещения следующей коллизийной записи, и т.д. Средняя длина поиска в этом случае оценивается приблизительно: 5(М,М) = !+ (М вЂ” ~~.

Очень часто после того как расширение таблицы завершено и места в таблице достаточно для размещения коллизнйных записей, содержимое сцепленной таблицы переносится в основную при сохранении их сцепления по адресам размещения. При выборе хэш-функции и, отображающей множество ключей х е К в адреса а а [И, М- 1), требуется, чтобы она не только сокращала число коллизий, но и исключала скучивание ключей в отдельных частях таблицы. 5.1.

Выбор хэш-функцин Выбор хэш-функции производится, как правило, из двух основных. а) Метод деления. В качестве значения хэш-функции используется остаток от деления ключа на некоторое целое М, т.е. Ь (К ) = К шоб М . Если М является степенью основания системы счисления, то значением хэш-функции являются младшие разряды ключа. Для предотвращения окучивания ключей лучше брать М простым числом. Желательно связать М с длиной таблицы размещения. б) Метод умножения.