Типове завдання

У файлі записані прізвища студентів. Для вмісту файлу створити хеш-таблицю на 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="";

int pos=0;

clrscr();

First();

if((f=fopen("kesh.txt","rt"))==NULL)

{ cout<<"Error reading input filen";

getch();

exit(1);

}

while(!feof(f))

{ fgets(string,20,f);

if(string[strlen(string)-1]=='n')

string[strlen(string)-1]='';

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,'');

scanf("%s",ss); // прізвище, що вставляється в список

pos=Kesh(ss); // обчислення хэш-функции для даного прізвища

Build(pos,ss); // вставка прізвища в список

cout<<"nString inserted in "<<pos<<" positionn";

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 absentn";

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 stringn";

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<<" stringn";

return;

} else

{ cout<<str<<" is absentn";

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 filen";

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 numbern";

cout<<"1 - Searchn";

cout<<"2 - Insertn";

cout<<"3 - Deleten";

cout<<"4 - Shown";

cout<<"5 - Update filen";

cout<<"6 - Exitn";

c=getche();

switch(c)

{

case '1': Search();clrscr();Show();break;

case '2': printf("nInput string for insertn");Insert();clrscr();Show();break;

case '3': printf("nInput string for deleten");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);

}