Лабораторная работа по "Программированию"
Автор: 1641001290604 • Ноябрь 5, 2018 • Лабораторная работа • 2,245 Слов (9 Страниц) • 595 Просмотры
Цель работы: изучить основные методы организации таблиц идентификаторов, получить представление о преимуществах и недостатках, присущих различным методам организации таблиц символов (идентификаторов).
Вариант:4
Сумма кодов первой и второй букв | Простое рехеширование |
Код программы:
#include "stdafx.h"
#include
#include
#include
#include
#include
#define SIZE 13
using namespace std;
void Search(string str);
void AddIdentif(string str);
int GetHashcode(string str);
int GetHashcode(string str,int r);
string table[SIZE];
int collision=0;
int main()
{
fstream file;
file.open("In.txt", ios::in );
if(!file.is_open())
cout<<"ERROR!"<
else
{
while(!file.eof())
{
string name;
file>>name;
AddIdentif(name);
}
file.close();
while(true)
{
int t;
cout<<"\n##############################################\n";
cout<<"Average collision = "<
cout<
cout<<"2 - Search "<
cout<
cin>>t;
if(t==1)
{
for(int i=0;i
cout<
}
else if(t==2)
{
string str;
cout<<"Str :";cin>>str;
Search(str);
}
else return 0;
}
}
return 0;
}
int GetHashcode(string str)
{
int first = str[0];
int second = str[1];
return (first+second)%SIZE;
}
int GetHashcode(string str,int r)
{
return (GetHashcode(str)+r)%SIZE;
}
void AddIdentif(string str)
{
//Добавление строки в таблицу
int start = GetHashcode(str);
if(table[start]=="")table[start]=str;
else
{
bool flag=false;
for(int k=1;k
{
collision++;
//Рехешируем и получаем новую позиции
int next = GetHashcode(str,k);
if(next==start)
...