Отчет по производственно-технологической практики в ИП «Лосева М.М.»

         void init(void) 

         {

         register int i; 
 

         for (i=0; i<MAX; i++) { primary[i]. index = -1;

         primary[i].next = NULL;  /*пустая цепочка */ primary[i].val = 0;

         } 
 
 
 
 
 

         } 

         Процедура store() преобразует имя ячейки в хэш-адрес в первичном массиве primary. Если позиция, на которую указывает значение хэш-адрес, занята процедура автоматически добавляет запись в список коллизий с помощью модифицированной версии функции slstore() из предыдущей главы. Логический индекс также сохраняется, поскольку он понадобится при извлечении элемента. Данные функции показаны ниже: 

         I* Вычисление хэш-адреса и сохранение значения. /* 

         void store(char *cell_name, int v) 

         {

         int h, loc;

         struct htype *p; 
 
 

         /* Получение хэш-адреса /* 

         loc = *cell_name - 'А'; /* столбец /*

         loc += (atoi(&cell_name[1])-1) * 26; /* строка * ширина + столбец */

           h = loc/10;/*hash*/ 
 

         /* Сохранить в полученной позиции, если она не занята либо если логические индексы совпадают - то есть, при обновлении.

         */

         if(primary[h].index==-1 || primary[h].index==loc) { primary[h].index = loc;

         primary[h].val = v;

         return;

         } 
 

         /* в противном случае, создать список коллизий

         либо добавить в его элемент */

         р = (struct htype *) malloc(sizeof(struct htype)); 
 
 
 
 
 

         If (!p)}

         Printf(“Не хватает памяти\n"); return;

         }

         p->index = loc; p->val = v;

         slstore(p, &primary[h]);

         } 
 

         /* Добавление элементов в список коллизий. */ void slstore(struct htype *i, struct htype *start)

         {

         struct htype *old, *p; old = start;

         /* найти конец списка */ while(start) {

         old = start;

         start = start->next;

         }

         I* связать с новой записью */ old->next = i;

         i->next = NULL;

         _}

         Для того чтобы получить значение элемента, программа должна сначала вычислить хэш-адрес и проверить, совпадает ли с искомым логический индекс, хранящийся в полученной позиции физического массива. Если совпадает, возвращается значение ячейки; в противном случае — производится поиске списке коллизий. Функция find(), выполняющая эти задачи, показана ниже: 

         /*Вычисление хэш-адреса и получение значения. */

         int find(char *cell_name) {

         int h, loc;

         struct htype *p; 
 

         /*получение значения хэш-адреса */

         loc = *cell_name - 'А'; /* столбец */

         loc += (atoi(&cell_name[1])-1) * 26; l* строка * ширина + столбец */

         h = loc/10; 
 

         /* вернуть значение, если ячейка найдена */

         if(primary[h].index == loc) return(primary[h],val);

         else { /* в противном случае просмотреть список коллизий */

          р = primary[h].next;

         while(p) {

         if(p->index == loc) return p->val;

         p = p->next;

         }

         Рrintf(“Ячейки нет в массиве \n"); return -1;

         }

         }

         Создание функции удаления оставлено читателю в качестве упражнения. (Подсказка: Просто обратите процесс вставки.)

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

         Анализ метода хеширования.

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

           Иными словами, хэш-функция является биекцией.

         ^[2]Т.е. ситуации, когда разным ключам k1#k₂ соответствует один и тот же хэш-адрес: h(k1)=h(k₂) (здесь h — хэш-функция).

         ^[31Цепочка хеширования (hash chain) — цепочка, соединяющая элементы хэш-таблицы с одним и тем же хэш-кодом. Ранее автор назвал ее списком коллизий (collision list). Иногда она называется также пакетом переполнения. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

         Заключение 
 
 
 

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

         Во время производственной практике все полученные навыки теоретического обучения были закреплены на реальном производстве. В данном отчете предоставлен программный комплекс, который в дальнейшем будет разработан для дипломного проектирования.

         Подводя итоги производственной практике, мы сталкивались со многими трудностями, но успешно их преодолевали. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

         Список литературы

1. Ван Тассел Д. « Стиль, разработка, эффективность, отладка испытание программ»,М. «Мир», 1981 г.
2. Фаронов В. В. Программирование на персональных ЭВМ в среде Турбо Паскаль. -М.: Изд-во МГТУ,1990.

3. "Единая система программной документации (ЕСПД)". Справочник.

4. "Программное обеспечение персональных компьютеров" под ред. Брусенцова Н.П. и Шаумана A.M. Изд. Московского Университета. 1990 г.