Типовое задание
В файле записаны фамилии студентов. Для содержимого файла создать хэш-таблицу на 10 элементов с распределенными цепочками переполнения (в списки записывать фамилии - синонимы). Функция хеширования определяется как:
Адрес = ? (Код) i mod 10
где: ? (Код) i - сумма кодов всех букв фамилии,
mod - остаток от целочисленного деления.
Проверить работоспособность хэш-таблиц. Результаты выдать на экран.
ВЫХОДНЫЕ МОДУЛИ.
1). Файл с фамилиями
Pihtin .
Gavruk
Kovalenko
Popa
Semenuk
Kosenko
Yankovoy
Petrov
Ponomarenko
Panteleymonov
Sidorov
Lyashenko
Konashevich
Storogenko
Storogenko
Panin
Maslov
Ivanov
Ermolenko
Kolugniy
2). Файл с описанием ФУНКЦИЙ.
#define RAZM 10 // Размер хеш-таблицы
struct Stud
{char name [20]; // Фамилия студента
Stud *next; // Указатель на следующее фамилия
Stud *prev; // Указатель на предыдущую фамилию
Stud *beg; // Указатель на начало списка
Stud *curr; // Указатель на текущее фамилия
};
Stud *st;
Stud *p [RAZM]; / / Хеш-таблица
int Build (int position, char *str); // Создание элемента списка для данного фамилии str
void Del (); // Удаление фамилии из списка
void First (); // Инициализация хеш-таблицы
void Insert (); // Вставки фамилии в хэш-таблицу
int Kesh (char *str); / / Распределение фамилий по спискам
void Show (); // Выдача списков на экран
void Search (); / Поиск фамилии в списке
void Death (); // Уничтожение списков
void Menu (); // Выдача меню
void Update_File (); // Замена входного файла в соответствии с изменениями
3). ГЛАВНЫЙ МОДУЛЬ.
/ * Открывается файл, для каждой фамилии исчисляется позиция в хешованому списке записывается в список, выдается результат на экран и переход к меню. * /
#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#include <string.h>
#include "func.h"
#include "do.cpp"
void main(void)
{ FILE *f;
char *string="\0";
int pos=0;
clrscr();
First();
if((f=fopen("kesh.txt","rt"))==NULL)
{ cout<<"Error reading input file\n";
getch();
exit(1);
}
while(!feof(f))
{ fgets(string,20,f);
if(string[strlen(string)-1]=='\n')
string[strlen(string)-1]='\0';
pos=Kesh(string);
Build(pos,string);
}
fclose(f);
Show();
Menu();
Death();
getch();
}
4). МОДУЛЬ, содержащий функции для реализации всех вышеуказанных действий.
int Kesh(char *str)
{ int i,kesh=0,size=0;
for(i=0;i<(strlen(str)-2);i++)
size+=(int)str[i]; //суммируем все коды строки
kesh=size%RAZM; //Значение хэш-функции
return kesh;
}
void First()
{ for(int i=0;i<RAZM;i++)
p[i]=NULL; // инициализация массива указателей на списки
}
int Build(int position, char *str)
{ Stud *pt,*nw,*nxt;
int kol=0;
pt=new Stud;
if(!pt)
{ cout<<"Error"<<endl;
getch();
exit(1);
}
nw=p[position]; // выделение памяти под новый элемент
if(!nw)
{ p[position]=pt;
p[position]->next=NULL;
p[position]->curr=pt;
}
else
{ pt->next=p[position]->curr;
p[position]->curr->prev=pt;
p[position]->curr=pt;
}
strcpy(p[position]->curr->name,str); //занесение в элемент
return 0;
}
void Insert()
{ Stud *pt;
char *ss;
int pos;
setmem(ss,1,'\0');
scanf("%s",ss); // фамилия, которая вставляется в список
pos=Kesh(ss); // вычисления хэш-функции для данного фамилии
Build(pos,ss); // вставка фамилии в список
cout<<"\nString inserted in "<<pos<<" position\n";
delay(1000);
}
void Del()
{ int pos;
char *s;
Stud *pt,*pt1=NULL,*pt2=NULL;
scanf("%s",s);
pos=Kesh(s);
pt=p[pos]->curr;
pt1=pt;
while((strcmp(pt->name,s))&&(pt))
pt=pt->next; // Удаление первого
if((pt1= =pt)&&(pt))
{ pt1=pt->next;
delete pt;
p[pos]->curr=pt1;
p[pos]->curr->prev=NULL;
} //Элемент не найден
if(!pt)
{ cout<<"This string is absent\n";
getch();
return;
} // Последний элемент
if(!pt->next)
{ Stud *temp;
Stud *temp1 = p[pos]->curr;
temp = p[pos];
p[pos] = temp->prev;
delete temp;
p[pos]->next = 0;
p[pos]->curr = temp1;
} // Элемент в середине
else
{ pt1=pt->prev;
pt2=pt->next;
pt1->next=pt2;
delete pt;
}
}
void Show()
{ Stud *ptr;
int len,o;
for(int i=0;i<RAZM;i++)
{ ptr=p[i];
cout<<"Segment "<<i<<" ";
if(ptr)
{ ptr=p[i]->curr;
while(ptr)
{ cout<<" "<<ptr->name<<" ";
ptr=ptr->next;
}
}
cout<<"\n";
}
}
void Search()
{ Stud *ptr;
int pos;
char *str;
cout<<"\nInput string\n";
gets(str); // строка, вводимого
pos=Kesh(str); // вычисление номера списка фамилии
ptr=p[pos]->curr;
if(ptr)
{ while((strcmp(ptr->name,str))&&(ptr))
ptr=ptr->next;
if(ptr)
{ cout<<" is present on "<<pos<<" string\n";
return;
} else
{ cout<<str<<" is absent\n";
return;
}
}
}
void Death()
{ Stud *ptr;
for(int i=0;i<RAZM;i++)
{ ptr=p[i]->curr;
while(ptr)
{ ptr=ptr->next;
delete p[i]->curr;
p[i]->curr=ptr;
}
}
}
void Update_File()
{ Stud *ptr;
int len,o,i;
char c;
FILE *f;
cout<<"Do you realy want to Update input File (y/n)\n";
c=getch();
if(c= ='n')
return;
if(c=='y')
{ if((f=fopen("kesh.txt","w+t"))==NULL)
{ cout<<"Error writing input file\n";
getch();
exit(1);
}
for(i=0;i<RAZM;i++)
{ ptr=p[i];
if(ptr)
{ ptr=p[i]->curr;
while(ptr)
{ fputs(ptr->name,f);
fputs("\n",f);
ptr=ptr->next;
}
}
}
fclose(f);
} else
return;
}
void Menu()
{ char c;
do
{ cout<<"\n"<<"Input need number\n";
cout<<"1 - Search\n";
cout<<"2 - Insert\n";
cout<<"3 - Delete\n";
cout<<"4 - Show\n";
cout<<"5 - Update file\n";
cout<<"6 - Exit\n";
c=getche();
switch(c)
{
case '1': Search();clrscr();Show();break;
case '2': printf("\nInput string for insert\n");Insert();clrscr();Show();break;
case '3': printf("\nInput string for delete\n");Del();clrscr();Show();break;
case '4': clrscr();Show();break;
case '5': clrscr();Update_File();break;
case '6': return;cout<<"\nExit";break;
default: cout<<" - Error of input";getch();clrscr();Show();
}
}while(c!=28);
}
