close

Вход

Забыли?

вход по аккаунту

?

OTCHET11313

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Марийский Государственный Технический Университет
Факультет информатики и вычислительной техники
Кафедра ИВС
ОТЧЕТ
ПО ЛАБОРАТОРНОЙ РАБОТЕ №1 "Работа с таблицей символов"
Выполнили: студенты группы ИВТ-31
Сафиуллин Д, Сибагатуллин Г. Проверил: Морохин Д. В.
Йошкар-Ола,
2012 г.
1. ЗАДАНИЕ
Вариант №7
Таблица строится с использованием хеш-функции на основе суммы трех первых букв идентификатора. При этом все буквы переводятся в заглавные (большие). Одинаковые элементы помещаются в одну ячейку, внутри которой организуется упорядоченный список.
2. СХЕМА ОРГАНИЗАЦИИ ХЕШ-ТАБЛИЦЫ
Схема организации хеш-таблицы имеет вид:
где ID - идентификатор,
hach - хеш-функция (сумма кодов первых 3-х букв),
next - указатель на следующий элемент списка в ячейке с этой же хеш-функцией.
Процесс добавления нового элемента происходит следующим образом:
1) вычисляем значение хеш-функции нового элемента (hash элемента tmp);
2) каждый элемент записывается по адресу своей ячейки, равному (значение хеш-функции - 195);
3) если в таблице имеется элемент с таким же значением хеш-функции, то сравниваем значения идентификаторов ID нового элемента с данным с помощью функции strcmp() (осуществляется посимвольное сравнение кодов символов);
4) если значения ID этих элементов равны, то добавления нового элемента не происходит, т.к. такой уже имеется;
5) если значение ID нового элемента tmp больше ID данного элемента, то происходит переход на следующий элемент в списке данной ячейки;
6) если указатель на следующий элемент списка - next оказывается равен нулю (конец списка), то происходит запись нового элемента;
7) если в процессе сравнения значение ID нового элемента оказывается меньше значения ID какого-либо элемента в списке, то происходит переадресация элементов, как показано на Рис.1 и вставка нового элемента между соседними в списке (таким образом осуществляется сортировка списка).
3. ОПИСАНИЕ АЛГОРИТМА ПОИСКА В ХЕШ-ТАБЛИЦЕ
Для проверки эффективности данной хеш-функции необходимо собрать статистику времени (количество шагов), затраченного на поиск каждого элемента в построенной таблице. 1) Для этого идентификаторы берутся из того же файла и сравниваются с элементами в построенной таблицы. 2) Сначала, за один шаг, находится адрес ячейки с таким же значением, что и hash взятого идентификатора.
3) Данный hash сравнивается с hash элементов, пока не конец таблицы.
4) Далее, пока не конец списка, сравниваем ID взятого элемента с ID элементов в списке. Каждый переход в списке оценивается как один шаг.
5) Шаги суммируются и образуют время поиска каждого идентификатора.
6) Результаты поиска выводятся в виде времени (количества шагов), затраченного на поиск каждого идентификатора.
7) Потом вычисляется сумма времен поиска всех идентификаторов в файле и делится на количество идентификаторов. 8) В итоге получается среднее время поиска идентификатора в файле.
3.1. График зависимости числа сравнений от искомого идентификатора
(количество идентификаторов)
(среднее число сравнений)
5. ИСХОДНЫЙ ТЕКСТ ПРОГРАММЫ
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <conio.h>
# include <iostream.h>
typedef struct TABLECELL
{ char IDStr [33];
// int hashValue;
struct TABLECELL *next;
// struct TABLECELL *onemore;
} tcell;
class CTableID :protected tcell
{protected:
tcell *first, *last;
int elements; //
public:
CTableID();
~CTableID();
void AddID(char*);
void Vivod();
int Find(char*,int &);
int NumElements();
int IsEmpty();
};
//==========================================================
CTableID::CTableID(){ first=last=NULL; elements=0; }
//-----------------------------------------------------------
int CTableID::NumElements(){ return elements; }
int CTableID::IsEmpty()
{ if(first==NULL) return 1;
return 0;
}
//-----------------------------------------------------------
CTableID::~CTableID()
{ if(first!=NULL)
{ tcell *tmp=first;
while(tmp!=NULL)
{first=tmp->next;
delete (tmp);
tmp=first;
}
}
}
//-----------------------------------------------------------
void CTableID::AddID(char *str)
{ tcell *tmp=new(tcell);
tcell *cur;
strncpy(tmp->IDStr,str,33);
if(first==NULL)
{ tmp->next=NULL;
first=tmp;
}
else
{ cur=first;
int res;
while(cur!=NULL)
{ char S1[33];
// int hash;
res=strcmp(cur->IDStr,tmp->IDStr);
if(res>0)
{ strcpy(S1,cur->IDStr);
// hash=cur->hashValue;
strcpy(cur->IDStr,tmp->IDStr);
// cur->hashValue=tmp->hashValue;
strcpy(tmp->IDStr,S1);
// tmp->hashValue=hash;
tmp->next=cur->next;
cur->next=tmp;
break;
}
if(res==0) { delete (tmp); return; }
if(cur->next==NULL)
{cur->next=tmp;
tmp->next=NULL;
break;
}
else cur=cur->next;
}
}
elements++;
}
//-----------------------------------------------------------
void CTableID::Vivod()
{ tcell *cur;
cur=first;
while(cur!=NULL)
{ cout<<cur->IDStr<<" ";//endl;
cur=cur->next;
}
}
//-----------------------------------------------------------
int CTableID::Find(char *str,int &count)
{ tcell *cur=first;
count=0;
while( cur!=NULL )
{ count++;
if(strcmp(cur->IDStr,str)) cur=cur->next;
else return 1;
}
return 0;
}
//===============================================================
int main(int argc, char* argv[])
{
system("cls");
int hash;
FILE *f1, *result;
fpos_t filepos;
if ((f1=fopen(argv[1],"rt"))==NULL)
{ cout<<"ЌҐ ¬(r)Јг (r)вЄалвм д Ё" "<<argv[1]<<endl;
exit(1);
}
if ((result=fopen("result.txt","w"))==NULL) abort();
fgetpos(f1, &filepos);
int i=0;
float middle,sum=0,count=0;
char str[33];
char *str1;
CTableID table[75];
while (!feof(f1))
{
fscanf(f1,"%s",str);
str1=strupr(str);
strncpy(str,str1,33);
hash=str[0]+str[1]+str[2];
table[hash-195].AddID(str);
}
// fclose(f1);
// clrscr();
cout<<"\n•Ґи - в Ў"Ёж ўбҐе Ё¤Ґ­вЁдЁЄ в(r)а(r)ўвЁдЁЄ в(r)а(r)ў:\n";
cout<<"______________________________________________\n";
for(i=0;i<75;i++) {
if(!table[i].IsEmpty()) {
cout<<"\n";
cout<<"•Ґи (б㬬 3 ЇҐаўле ЎгЄў Ё¤Ґ­вЁдЁЄ в(r)а )="<<i+195<<":\n";
table[i].Vivod();
cout<<"\n";
}
}
cout<<"\n";
cout<<"‚ᥠЁ¤Ґ­вЁдЁЄ в(r)ал Ўл"Ё ­ (c)¤Ґ­л. ЏаЁў(r)¦г Є(r)"ЁзҐбвў(r) ба ў­Ґ­Ё(c):";
fsetpos(f1, &filepos);
cout<<"\n";
while (!feof(f1))
{
fscanf(f1,"%s",str);
str1=strupr(str);
strncpy(str,str1,33);
hash=str[0]+str[1]+str[2];
if (table[hash-195].Find(str,i))
{ sum+=i;
// cout<<"Ќ иҐ"!\t"<<i<<" ";//"\n";
cout<<count+1<<") "<<i<<" ";//"\n";
fprintf(result,"%d ",i);
count++;
}
}
cout<<"\n";
cout<<"€в(r)Ј(r): \n";
cout<<"'㬬 = "<<sum<<endl;
cout<<"Љ(r)"ЁзҐбвў(r) Ё¤Ґ­вЁдЁЄ в(r)а(r)ў="<<count<<endl;
cout<<"'।­ҐҐ §­ 祭ЁҐ = "<<sum/count;
getch();
fclose(f1);
fclose(result);
}
6. ВЫВОДЫ О ПРОДЕЛАННОЙ РАБОТЕ
Выполнив данную работу мы изучили основные методы организации таблиц идентификаторов, а также получили представление о преимуществах и недостатках, присущих различным методам организации таблиц символов (идентификаторов).
2
7
Документ
Категория
Рефераты
Просмотров
55
Размер файла
86 Кб
Теги
otchet11313
1/--страниц
Пожаловаться на содержимое документа