страница 1
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Похожие работы
|
Методические указания к выполнению курсовой работы по дисциплине «Технология программирования» - страница №1/1
ФАКУЛЬТЕТ «ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ» Кафедра прикладной математики и ВТ О.В. Прохорова Методические указания к выполнению курсовой работы по дисциплине «Технология программирования» для студентов специальности 230401 Самара 2012 УДК 62-50 (076.5) Методические указания к выполнению курсовой работы для студентов специальности 230400. /Сост. О.В. Прохорова. – Самара, СГАСУ, 2012. - 12c. Изложены основные требования к выполнению курсовой работы по дисциплине «Технология программирования».Что включает выполнение: постановки задачи на проектирование; аналитическую часть с раскрытием теории и метода решения задачи; алгоритмическую часть, связанную с построением алгоритма решения поставленной задачи; написание кода программы на языке С++; тестирование кода с разными исходными данными; список использованной литературы. ОглавлениеОглавление 3 1. Постановка задачи проектирования 3 2. Аналитическая часть 4 3. Алгоритмическая часть 5 4. Конструкторская часть 6 5. Тестирование 11 Литература 11 1. Постановка задачи проектированияПусть задачей курсового проектирования ставится реализация алгоритма хеширования при работе с данными. Для понимания выполнения задания необходимо сделать краткий обзор проблемы. С хешированием сталкиваются при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь), компилятором (таблица символов). Заглядывая в адресную книгу, энциклопедию, алфавитный указатель, никто, как правило, не задумывается, что упорядочение по алфавиту является не чем иным, как хешированием. Использование хеширования является эффективным при поиске данных, так как этот алгоритм минимизирует число сравнений ключей друг с другом. Хеширование - метод преобразования ключа записи в абсолютный или относительный адрес расположения записи в памяти. При хешировании используется функция преобразования ключа (функция хеширования). 2. Аналитическая частьАналитическая часть раскрывает теорию и методику, лежащих в основе решения задачи. Хеш-функция – это некоторая функция h(K), которая берет ключ K и возвращает адрес, по которому производится поиск в хеш-таблице, чтобы получить информацию, связанную с K. Коллизия – это ситуация, когда h(K1) = h(K2), в то время как K1 не равен K2. В этом случае необходимо найти новое место для хранения данных. Часто используемые хеш-функции: Метод деления требующий двух шагов. Сначала ключ должен быть преобразован в целое число, а затем полученное значение вписывается в диапазон 0...n-1 с помощью оператора получения остатка. На практике метод деления используется в большинстве приложений, работающих с хешированием. Другой пример – ключ-символьная строка С++. Хеш-функция отображает эту строку в целое число посредством суммирования первого и последнего символов и последующего вычисления остатка от деления на 101 (размер таблицы). Метод середины квадрата предусматривает преобразование ключа в целое число, возведение его в квадрат и возвращение в качестве значения функции последовательности битов, извлеченных из середины полученного числа. Предположим, что ключ есть целое 32-битное число. Тогда следующая хеш-функция извлекает средние 10 бит возведенного в квадрат ключа. Известные способы разрешения коллизий: Метод цепочек. В случае, когда элемент таблицы с индексом, который вернула хеш-функция, уже занят, к нему присоединяется связный список. Поиск в этом списке осуществляется простым перебором. Открытая адресация - другой путь решения проблемы, связанной с коллизиями, состоит в том, чтобы полностью отказаться от ссылок, просто просматривая различные записи таблицы по порядку до тех пор, пока не будет найден ключ K или пустая позиция. Линейная адресация - простейшая схема открытой адресации, использует циклическую последовательность проверок. 3. Алгоритмическая частьАлгоритмическая часть дает представление о шагах решения задачи. Н1. [Инициализация]. Ввод key и ch. Н2. [запись хеш-таблицы]. Индекс ячейки после хеширования будет kk=key%100. Если ячейка TAB[kk] пуста, то TAB[kk].f2=key TAB[kk].f3[i]=ch[i]. В этом случае алгоритм завершен успешно, переход к шагу Н5. В противном случае, переход к Н3. Н3.[Разрешение коллизии]. Свободное место сначала ищется по мере убывания индекса. Если (TAB[kk-i]=='*') свободное место найдено. В ячейку TAB[kk-i] заносится признак коллизии и переход к Н2. Если место не найдено, переход к Н4. Н4. [Разрешение коллизии] .Поиск свободного места теперь происходит в обратном направлении. Если в ячейке TAB[kk+i] найдено свободное место, в нее заносится признак коллизии, переход к шагу Н2. Если (i+kk>=SIZE-1), то коллизия не может быть разрешена. Н5. Конец алгоритма. 4. Конструкторская частьКонструкторская часть содержит листинг кода программы //ХЕШИРОВАНИЕ
#include "stdafx.h" #include using namespace std; #include #define SIZE 100 #define LL 4 // длина символьной инормации struct table { char f1; /* признак свободной ячейки f1='*'; занятой без коллизии f1='0'; занятой путем разрешения коллизии f1='&' */ int f2; // ключ - key; char f3[LL]; // информация, хранимая по ключу - ch ; }; int main() { table TAB[SIZE]; int key, i,j,kk; char ch[LL], pch; int flag=0; // признак окончания работы for(i=1;i while (flag==0) { cout cin>>pch; if((pch=='Y')||(pch=='y')) { cout cin>>key; cout for(i=0;i> ch[i]; int kk=key%100; // индекс ячейки после хеширования if(TAB[kk].f1=='*') // пустая ячейка { TAB[kk].f1='0'; TAB[kk].f2=key; for( i=0;i cout for(i=0;i cout cout } else { cout int flag_1=0; // свободное место ищется сначала по мере убывания индекса bool gg = false; // gg = false признак того, что место для информации не найдено TAB[kk].f1='&'; i=1; cout while (gg==false) { while( flag_1==0) { if (TAB[kk-i].f1=='*') // свбодное место найдено { TAB[kk-i].f1='&'; // вставка признака коллизии TAB[kk-i].f2=key; for(j=0;j gg=true; break; } else { kk=kk-i; i++; if(kk-i } } // поиск свободного места в обратном направлении i=1; while(flag_1==1) { if(TAB[kk+i].f1=='*') // свободное место найдено { TAB[kk+i].f1='&'; TAB[kk+i].f2=key; for(j=0;j gg=true; break; } else { kk=kk+i; i++; if(i+kk>=SIZE-1) cout _getch(); return 0; } } } } } cout cin>>pch; if((pch=='Y')||(pch=='y')) { cout cin>>key; kk=key%100; cout if(TAB[kk].f2==key) { cout for(j=0;j } else { for(j=1;j { if ((TAB[j].f1=='&')&&(TAB[j].f2==key)) { kk=j; cout for(i=0;i } } } } cout cin>>pch; if((pch=='Y')||(pch=='y')) TAB[kk].f1='*'; cout cin>>pch; if((pch=='Y')||(pch=='y')) flag=1; } cout _getch(); } 5. ТестированиеТестирование содержит результаты решения задачи на разных исходных данных.
Литература1. Дональд Кнут Искусство программирования, том 3. Сортировка и поиск — 2-е изд. — М.: «Вильямс», 2007.-480с. 2. Прохорова О.В. Методы программирования и прикладные алгоритмы. Методические указания к курсовому проектированию. Йошкар –Ола: МОСИ, 2007. -18с. 3. Прохорова О.В. Методы программирования. Учебное пособие. Йошкар – Ола: МОСУ, 2007. -178c. |
|