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

В качестве хэш-функции используют .(. (к) = [М(ха)1, где [х 1- наибольшее целое, не превосходящее х. Константе а, как правило, присваивают значение, называемое золотым сечением: а= (45 — 1)/2 О.б48. Здесь М может быть кратно 2, т.е. М = би, т.е. М может быть длиной таблицы размещения. 5.2. Разрешение коллизии а) Метод открытой адресации Алгоритм можно представить в форме: 1) 1=0; 2) а = й(а)+11 3) если а свободно, конец алгоритма (если это процедура вставки, то занесение по адресу а;если процедура поиска, то ключа нет).

4) если ключ, связанный с адресом а, равен к, то при поиске алгоритм заканчивается; 5) 1=1+! и переход к шагу 2, б) Пинейное апробирование. В этом случае в схеме открытой адресации используется а л(к)+с1, где с - константа; с и М выбираются взаимно простыми, с - не очень малым. в) Квадратичное апробирование. Это схема открытой адресации, где а = А (к)+ с[+ а1, где с,й - константы. з г) Двойное хэширование, Это схема открытой адресации, а=А(й)+й)17с), где й[к/ - хэш-функция, почти такая, как й (х ), но не эквивалентная ей.

Так, например, используют следующие представления: а = (к шобМ) + 1(1+ к шоб(М- 2)) или а = л (к)+ 1(М вЂ” л(х)), Теоретическая оценка числа коллизий при случайном равномерном распределении по М адресам дается следующими соотношениями: математическое ожидание: М1 — (М- А1); -нм дисперсия: М1 (1 — (М- Ф) 1 /М .

Распределение при 1 с с А! с с М приближается к распределению Пуассона, прн 1 с с А1= М - к нормальному распределению. Содержание отчета: 1) структурная схема алгоритма; 2) текст программы; 3) распечатка указанных в задании результатов выполнения программ. Задание. Взять множество целых двузначных ключей А(Л1).

Разработать две программы, демонстрирующие заполнение хэш-таблицы и поиск хотя бы одного ключа в таблице для заданной хэш-функции (одна - без «сцепленной» таблицы, М >Ф, другая - с использованием «сцепленной» таблицы М =Ф). В табл. 5.1 приведены варианты заданий. таблица зл РАБОТА Х 6. ОДНОСВЯЗНЫЕ И ДВУСВЯЗНЫЕ СПИСКИ Одно- и двусвязные списки относятся к линейным динамическим структурам данных, которые характеризуются переменным размером структуры н отсутствием последовательного расположения элементов структуры в памяти. Число элементов динамической структуры может изменяться от нуля до некоторой величины, определяемой доступным объемом машинной памяти. Логическая последовательность элементов задается в явном виде с помощью одного или двух указателей, хранящихся в самих элементах.

Таким образом, элементы динамической структуры могут быть разбросаны в памяти хаотическим образом, в результате чего усложняется процедура доступа к элементам. Для доступа к требуемому элементу необходимо просматривать список с его начала. Связный список - это структура, элементами которой служат записи с одним и тем же форматом. 6.1. Односвязные списки В односвязном списке каждый элемент состоит из двух различных по назначению полей: информационного поля и поля указателя.

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

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

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

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

Найти свободный элемент списка. 2. Записать его адрес в дескриптор. 3. Заполнить информационное поле найденного элемента требуемыми данными, 4. Если данные исчерпаны, записать в поле указателя признак конца списка и закончить работу. 5.

Запомнить адрес текущего элемента. 6. Найти свободный элемент. 7. Записать его адрес в поле указателя предыдущего элемента. 8. Перейти к п.3. б) Удаление существующего списка Входные данные: дескриптор удаляемого списка. 1. Считать из дескриптора адрес начала списка.

2. Запомнить содержимое поля указателя текущего элемента. 3. Записать в поле указателя признак свободного элемента. 17 4. Если в поле указателя был не признак конца списка, перейти к и. 2. в) Добавление элемента в список Входные данные: дескриптор списка, порядковый номер эле- мента списка, после которого надо вставить элемент в список, до- бавляемые данные. 1. Найти свободный элемент. 2. Если добавляется первый элемент в список, то запомнить адрес списка, записать в дескриптор адрес найденного свободного элемента, перейти к и, 6.

3. Найти'элемент списка, после которого необходимо вставить но- вый элемент, 4, Запомнить содержимое поля указателя (адрес элемента, следу- ющего за новым). 5. Записать в поле указателя адрес свободного элемента, , б, Заполнить данными информационное поле свободного элемента. 7. Записать в поле указателя сохраненный адрес следующего элемента. г) Исключение эламени!а из списка Входные данные: порядковый номер удаляемого элемента списка, дескриптор списка, 1. Вели исключается первый элемент списка, то изменить содер- жимое дескриптора, перейти к п. 4. 2. Найти элемент, после которого находится исключаемый эле- мент списка, и запомнить его адрес. 3.

Переписать информацию из поля указателя удаляемого элемен- та в поле указателя предыдущего элемента. 4, Пометить удаляемый элемент как свободный. Содержание отчета: 1) структурная схема алгоритма; 2) текст программы; 3) распечатка указанных в задании результатов выполнения программ. Задание 1. Составить программы работы с односвязными списка- ми, пользуясь следующими соглашениями. В качестве области памяти односвязных списков использовать массив размерности (2,50), началь- ное содержимое которого считать из файла ЗР1З1.ОАТ. Поле указа- теля элемента списка содержит номер столбца массива со следующим элементом списка. Последний элемент содержит в поле указателя значение О, а свободный элемент - значение -!.

Вывод информацион- ных полей осуществляется в виде строки символов форматным опе- ратором вывода через спецификацию 'А! ' (РОКТЕАК-1Ч). Восьмерич- ные и десятичные коды символов АЗСП и содержимое файла ЗР1З1.ОАТ даны в приложениях ! и 2. Варианты задания 1: 1. Создать новый односвязный список, информационные поля которого содержат символы слова «ДРАЙВЕР». Вывести содержимое сформированного массива и содержимое сформированного списка (информационных полей и полей указателей). 2.

Удалить односвязный список, дескриптор которого указывает на адрес 25. Вывести содержимое сформированного массива. 3. Дополнить односвязный список, дескриптор которого указывает на адрес 2, элементом с символом «- » между 3-м и 4-м элементами списка. Вывести содержимое информационных полей полученного списка в виде строки символов. 4. Удалить нз односвязного списка, дескриптор которого указывает на адрес 30, пятый элемент списка. Вывести содержимое списка в виде строки символов. 5. Определить все элементы, не относящиеся ни к одному списку (дескрипторы списков содержат адреса 1, 2, 25, 30) и не помеченные как свободные.

Перевести эти элементы в разряд свободных и вывести их адреса, 6. Дополнить односвязный список, дескриптор которого указывает на адрес 25, элементом с символом «, », стоящим после последнего элемента списка. Вывести содержимое информационных полей полученного списка в виде строки символов. 7.

Скопировать односвязный список, дескриптор которого указывает на адрес 30, сформировав в свободных элементах новый список. Вывести содержимое сформированного массива и адрес начала сформированного списка. Задание 2. Составить программы работы с двусвязными списками, пользуясь следующими соглашениями. В качестве области памяти двусвязных списков использовать массив размерности (3,50), начальное содержимое которого читать из файла ЗР1З2.ОАТ.

Поля указателей элемента списка содержат номера столбцов массива со следующим и предыдущим элементами списка соответственно. Последний элемент содержит в поле указателя значение О, а свободный элемент - значение -1. Вывод информационных полей осуществляется в виде строки символов форматным оператором вывода через спецификацию 'А1' (РОКТКАХ-1Ч).