Методические указания к выполнению курсовой работы по дисциплине «Технология программирования» для студентов специальности 230401 - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Методические указания к выполнению курсовой работы для студентов... 4 631.09kb.
Методические указания разработаны на основании гос впо 653500 «Строительство» 2 404.4kb.
Методические указания к курсовой работе по дисциплине «Экономика... 1 315.51kb.
Инструкция по выполнению лабораторной работы по дисциплине "Химическое... 1 212.95kb.
Методические указания к выполнению курсовой работы Для студентов... 1 160.32kb.
Методические указания по выполнению контрольных работ по дисциплине... 2 704.74kb.
Методические указания по дисциплине «Элементы высшей математики»... 1 119.1kb.
Методические указания по выполнению контрольной работы 3 Варианты... 1 238.26kb.
Методические указания по написанию курсовой работы по дисциплине... 1 191.46kb.
Методические указания к выполнению лабораторных работ по дисциплине... 2 464.35kb.
Учебно-методическое пособие по дисциплине «Математика» предназначено... 1 194.6kb.
ОрганизАция таблиц фильтрации «без хранения адресов» в межсетевых... 1 82.91kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Методические указания к выполнению курсовой работы по дисциплине «Технология программирования» - страница №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();
          return 0;

}

5. Тестирование



Тестирование содержит результаты решения задачи на разных исходных данных.


1

2

3

4

5

Do you like to put information?

Do you like to put information?

Do you like to put information?

Do you like to put information?

Do you like to put information?

y

y

y

n

y

Enter key

Enter key

Enter key

Enter key

Enter key

12345

734

45334




7896

kk=45

kk=34

kk=34

kk=

kk=96

Enter information

Enter information

Enter information

Enter information

Enter information

tree

door

open




class

Do you like to search information?

Do you like to search information?

Do you like to search information?

Do you like to search information?

Do you like to search information?

n

n

y

y

y







Enter key

Enter key

Enter key







734

45334

12345







Information exist!

Information exist!

Information exist!

Do you like to delete the found information?

Do you like to delete the found information?

Do you like to delete the found information?

Do you like to delete the found information?

Do you like to delete the found information?

n

n

n

y

y

Do you like to finish work?

Do you like to finish work?

Do you like to finish work?

Do you like to finish work?

Do you like to finish work?

n

n

n

n

y


Литература

1. Дональд Кнут Искусство программирования, том 3. Сортировка и поиск — 2-е изд. — М.: «Вильямс», 2007.-480с.

2. Прохорова О.В. Методы программирования и прикладные алгоритмы.

Методические указания к курсовому проектированию. Йошкар –Ола:

МОСИ, 2007. -18с.

3. Прохорова О.В. Методы программирования. Учебное пособие. Йошкар –



Ола: МОСУ, 2007. -178c.