ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

Отёска стен и прирубка косяков - Когда на доме не достаёт окон и дверей, красивое высокое крыльцо ещё только в воображении, приходится подниматься с улицы в дом по трапу.

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

Результаты работы программы

Условие задачи

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

Анализ решения

Дано:

Множество вида: A = {шифр изделия, название изделия, количество}

Шифр последовательность символов;

Название последовательность латинских букв;

Количество Z⁺.

Результат:

Таблица с вычисляемым входом вида:

Шифр изделия – последовательность букв и цифр

Наименование изделия – последовательность латинских букв

Количество изделий – целое положительное число

Решение:

Если просматривая файл work, найдутся несколько элементов с одинаковым ключом, в таблицу с вычисляемым входом заносится такой элемент один раз с общим количеством штук изделия.

Если ключ code[i] ключ code[j], а f(ключ code_i) = f(ключ code_j) при i j (возникновение коллизии), то такая проблема решается методом линейного рехеширования:

Пусть ключ – сумма всех кодов символов входящих в имя переменной (шифр изделия).

Для линейного рехеширования будем использовать следующую функцию: хеш-функция = (ключ + i) mod N (N – размер таблицы), i = 1, 2, … используя это рехеширование, при поиске свободного элемента таблицы последовательно рассматриваются все элементы таблицы, начиная с первоначального индекса, полученного в результате хеширования.

Структуры данных

Внутреннее представление входных данных:

Шифр изделия – переменная строкового типа (одномерный массив char code[9])

Наименование изделия - переменная строкового типа (одномерный массив char name[255])

Количество изделий – целочисленная переменная (int numb)

Внешнее представление входных данных:

Текст в файле work.txt, включающий элементы типа F={B, C, D|B- шифр изделия, C- название изделия, D- количеств изделий.}

Внутреннее представление выходных данных:

Таблица с вычисляемым входом – динамический массив с ключом, элемент списка имеет вид:

char code[9];

char name[255];

int numb;

Внешнее представление выходных данных:

Текст в файле table.txt, включающий элементы типа F={B, C, D|B- шифр изделия, C- название изделия, D- количеств изделий.}, измененные в результате линейного рехеширования и сложения количества элементов с одинаковым ключом.

Начало (лин.рехеширование)

Алгоритм решения

Шифр изделия, наименование,количество

Вычислить значение ключа и хеш-функции = ключ mod N

Коллизия и есть свободные места в таблице?

Рехешировать по формуле хеш=(ключ+i) mod N, i=1,2,…

Место найдено?

Записать значение в таблицу

Таблица полна

конец

Текст программы

/*файл head.h */

#include <stdio.h>

#include <string.h>

const int N=10000;

extern int num;

struct table

{

char code[9];

char name[255];

int numb;

};

void table_add(table *t, char *code, char *name, int numb);

void hash_add(table *t, char *code, char *name, int numb);

/*файл p.prog.cpp*/

void table_add(table *t, char *code, char *name, int numb)

{

int flag = 0;

for(int i = 0; i < num && !flag; i++)

if(!strcmp(code, t[i].code))

{

flag++;

t[i].numb += numb;

}

if(!flag)

{

strcpy(t[num].code, code);

strcpy(t[num].name, name);

t[num].numb = numb;

num++;

}

void hash_add(table *t, char *code, char *name, int numb)

{

int sym = 0, hash;

for(int i = 0; i < 9; i++)

sym += name[i];

hash = sym % N;

for(int i = 1; i < N && strlen(t[hash].code); i++)

hash = (sym + i) % N;

if(!strlen(t[hash].code))

{

strcpy(t[hash].code, code);

strcpy(t[hash].name, name);

t[hash].numb = numb;

}}

/*файл main.cpp*/

#include <stdio.h>

#include <string.h>

#include "head.h"

int num = 0;

int main()

{

table *t = new table [N];

for(int i = 0; i < N; i++)

{

t[i].code[0] = '\0';

t[i].name[0] = '\0';

t[i].numb = 0;

}

FILE *f = fopen("work.txt","r");

int numb;

char name[255], code[9];

while(fscanf(f, "%s %s %i", code, name, &numb) != EOF && num < N)

table_add(t, code, name, numb);

fclose(f);

table *t2 = new table [N];

for(int i = 0; i < N; i++)

{

t2[i].code[0] = '\0';

t2[i].name[0] = '\0';

t2[i].numb = 0;

}

for(int i = 0; i < num; i++)

hash_add(t2, t[i].code, t[i].name, t[i].numb);

f = fopen("table.txt", "w");

for(int i = 0; i < N; i++)

if(t2[i].code[0] != '\0')

fprintf(f, "%s\t%s\t%i\n", t2[i].code, t2[i].name, t2[i].numb);

delete [] t;

delete [] t2;

return 0;

}

Набор тестов

Входные данные	Назначение теста
th00tf00 table 67 th00tf00 table 67 tg770009 chair 67 000019h0 desk 56 0010090h screw 89 190000h0 nut 98 u0088iu0 sofa 76 u00880ui drill 71 679uyvbm nail 999	Проверка правильности решения коллизии; Проверка правильности сложения количества элементов с одинаковыми ключами.

Результаты работы программы

Входные данные	Результат
th00tf00 table 67 th00tf00 table 67 tg770009 chair 67 000019h0 desk 56 190000h0 nut 98 u0088iu0 sofa 76 0010090h screw 89 u00880ui drill 71 679uyvbm nail 999	000019h0 desk 56 0010090h screw 89 190000h0 nut 98 tg770009 chair 67 u0088iu0 sofa 76 u00880ui drill 71 th00tf00 table 134 679uyvbm nail 999