Лабораторные работы (ФИРТ 4 курс)
скачать (5485.4 kb.)
Доступные файлы (87):
MyLab1.exe | |||
MyLab1.ilk | |||
MyLab1.obj | |||
MyLab1.pch | |||
MyLab1.pdb | |||
vc60.idb | |||
vc60.pdb | |||
MyFile.txt | 1kb. | 29.10.2006 14:45 | ![]() |
myfil.txt | 0kb. | 01.11.2006 23:20 | ![]() |
MyLab1.cpp | |||
MyLab1.dsp | |||
MyLab1.dsw | |||
MyLab1.ncb | |||
MyLab1.opt | |||
MyLab1.plg | |||
Лаба1.doc | 179kb. | 23.12.2006 20:39 | ![]() |
MyLab2.exe | |||
MyLab2.ilk | |||
MyLab2.obj | |||
MyLab2.pch | |||
MyLab2.pdb | |||
vc60.idb | |||
vc60.pdb | |||
myfile.txt | 1kb. | 11.11.2006 00:53 | ![]() |
MyLab2.cpp | |||
MyLab2.dsp | |||
MyLab2.dsw | |||
MyLab2_func.h | |||
MyLab2.ncb | |||
MyLab2.opt | |||
MyLab2.plg | |||
Лаба2.doc | 1052kb. | 23.12.2006 20:39 | ![]() |
ex.txt | 1kb. | 30.11.2006 02:08 | ![]() |
LabSPODlg.obj | |||
LabSPO.exe | |||
LabSPO.ilk | |||
LabSPO.obj | |||
LabSPO.pch | |||
LabSPO.pdb | |||
LabSPO.res | |||
StdAfx.obj | |||
vc60.idb | |||
vc60.pdb | |||
ex.txt | 1kb. | 30.11.2006 02:08 | ![]() |
LabSPO.aps | |||
LabSPO.clw | |||
LabSPO.cpp | |||
LabSPODlg.cpp | |||
LabSPODlg.h | |||
LabSPO.dsp | |||
LabSPO.dsw | |||
LabSPO.h | |||
LabSPO.ncb | |||
LabSPO.opt | |||
LabSPO.plg | |||
LabSPO.rc | |||
MyLab2_func.h | |||
ReadMe.txt | 4kb. | 24.11.2006 22:52 | ![]() |
LabSPO.ico | |||
LabSPO.rc2 | |||
Thumbs.db | |||
Resource.h | |||
StdAfx.cpp | |||
StdAfx.h | |||
ex2.txt | 1kb. | 23.11.2006 18:47 | ![]() |
ex.txt | 1kb. | 22.11.2006 01:44 | ![]() |
mmm.txt | 0kb. | 30.11.2006 14:24 | ![]() |
myfile.txt | 0kb. | 30.11.2006 14:24 | ![]() |
MyLab3.exe | |||
MyLab3.ilk | |||
MyLab3.obj | |||
MyLab3.pch | |||
MyLab3.pdb | |||
vc60.idb | |||
vc60.pdb | |||
ex2.txt | 1kb. | 23.11.2006 18:47 | ![]() |
ex.txt | 1kb. | 22.11.2006 01:44 | ![]() |
myfile.txt | 1kb. | 11.11.2006 00:53 | ![]() |
MyLab2_func.h | |||
MyLab3.cpp | |||
MyLab3.dsp | |||
MyLab3.dsw | |||
MyLab3.ncb | |||
MyLab3.opt | |||
MyLab3.plg | |||
гзоҐзҐ | |||
Лаба3.doc | 222kb. | 23.12.2006 20:40 | ![]() |
содержание
- Смотрите также:
- Лабораторные работы (ФИРТ 4 курс) [ лабораторная работа ]
- Каретников Г.С. и др. Лабораторные работы по физической химии [ документ ]
- Лабораторные работы по метрологии [ документ ]
- Лабораторные работы [ документ ]
- Лабораторные работы по VB и компасу (+курсовые) [ документ ]
- Лабораторные работы по КОУ №5,6 [ документ ]
- Готовые лабораторные работы по вакуумной электронике [ документ ]
- Лабораторные работы [ документ ]
- Лабораторные работы по информационному маркетингу 1 [ лабораторная работа ]
- Лабораторные работы [ документ ]
- Лабораторные работы [ документ ]
- Лабораторные работы по МПС [ лабораторная работа ]
Лаба1.doc
Уфимский Государственный АвиационныйТехнический Университет
кафедра АПРиС
Лабораторная работа №1
Работа с таблицей символов
Выполнил: студент гр. Т28-421
Проверила: Пузырникова Е.А.
Уфа 2006
Задание
Разработать программу, реализующую комбинированный способ организации таблицы идентификаторов. Для организации таблицы используется простейшая хэш-функция, указанная в варианте задания, а при возникновении коллизий используется дополнительный метод размещения идентификаторов в памяти. Если в качестве этого метода используется дерево или список, то они должны быть связаны с элементом главной хэш-таблицы.
В каждом варианте требуется, чтобы программа сообщала среднее число коллизий и среднее количество сравнений, выполненных для поиска идентификатора.
№ | Тип хэш-функции (таблицы) | Способ разрешения коллизий |
9. | Сумма кодов первой и последней букв | Упорядоченный список с логарифмическим поиском |
^
#include <iostream.h>
#include <fstream.h>
#include <math.h>
const int maxAddr=367;
class Table
{
public:
Table(int initTable);
~Table();
void removeRec(int addr);
void createRec(int addr, char ident[40], char prop[20]);
char* GetRecId(int addr);
char* GetRecProp(int addr);
bool GetRecEF(int addr);
void PrintRec(int addr);
int GetRecLink(int addr);
void FillRecLink(int addr, int link);
int HashTab[maxAddr];
private:
bool EmptyFlag[maxAddr];
char Ident[maxAddr][40];
char Property[maxAddr][20];
int Links[maxAddr];
};
Table::Table(int initTable)
{
for (int i=0; i<initTable; i++)
{
EmptyFlag[i]=true;
for(int j=0; j<40; j++) Ident[i][j]=NULL;
for( j=0; j<40; j++) Property[i][j]=NULL;
for(int e=0; e<367; e++) Links[e]=400;
for( e=0; e<367; e++) HashTab[e]=500;
}
}
Table::~Table()
{
}
bool Table::GetRecEF(int addr)
{
return EmptyFlag[addr];
}
char* Table::GetRecId(int addr)
{
return Ident[addr];
}
char* Table::GetRecProp(int addr)
{
return Property[addr];
}
int Table::GetRecLink(int addr)
{
return Links[addr];
}
void Table::FillRecLink(int addr, int link)
{
Links[addr]=link;
}
void Table::createRec(int addr, char ident[40], char prop[20])
{
for (int k=0; k<40; k++) Ident[addr][k]=ident[k];
for (int j=0; j<20; j++) Property[addr][j]=prop[j];
EmptyFlag[addr]=false;
};
void Table::removeRec(int addr)
{
EmptyFlag[addr]=true;
for (int k=0; k<40; k++) Ident[addr][k]=NULL;
for (int j=0; j<20; j++) Property[addr][j]=NULL;
}
void Table::PrintRec(int addr)
{
cout<<"| "<<addr<<"| ";
for(int i=0; i<40; i++) cout<<Ident[addr][i]; cout<<"|";
for(i=0; i<20; i++) cout<<Property[addr][i]; cout<<"|";
}
bool ElExist(char id_fromFile[40], Table T1);
bool ElExist(char id_fromFile[40], Table T1)
{
int fHashF, fa, t=0,fAddr, fnAddr, Nm=367, f_last=0, fCountAttempt=0, Compar=0;
for (int e=0; e<40; e++)
{ //подсчет количества символов в идентивикаторе
if (int(id_fromFile[e])!=NULL) f_last++;
};
fHashF=int(id_fromFile[0])+int(id_fromFile[f_last-2])+int(id_fromFile[f_last-1]);
if(T1.HashTab[fHashF]==500) cout<<" There is no such dentifier! "<<endl;
else
{
fa=T1.HashTab[fHashF];
while( int(id_fromFile[t]) >= int(T1.GetRecId(fa)[t]))
{
m1: if(int(id_fromFile[t]) == int(T1.GetRecId(fa)[t]))
{
t++;
if(t==f_last)
{
cout<<" This ID successfully found! Its addr: "<<fa
<<"\n There were(was) "<<Compar<<" comparision(s)."<<endl;
return true; break;
};
continue;
}
else
{
fa=T1.GetRecLink(fa); Compar++;
if(fa==400) {cout<<" There is no such dentifier! "<<endl; return false;}
else goto m1;
}
t=0;
}
while( int(id_fromFile[t]) <= int(T1.GetRecId(fa)[t]))
{
m2: if(int(id_fromFile[t]) == int(T1.GetRecId(fa)[t]))
{
t++;
if(t==f_last)
{
cout<<" This ID successfully found! Its addr: "<<fa<<endl;
return true; break;
};
continue;
}
else
{
fa=T1.GetRecLink(fa); Compar++;
if(fa==400) {cout<<" There is no such dentifier! "<<endl; return false;}
else goto m2;
};
t=0;
}
}
}
void main()
{
while(true){
const int arraySize1=40, arraySize2=41, mA=367;
Table TableID(mA);
char FileName[40];
cout<<"Enter file name, which must be written: ";
cin>>FileName;
char ID[arraySize1][arraySize2]={NULL};
int d=0, e=0;
ifstream ReadFromFile(FileName);
cout<<" Content of file "<<FileName<<endl;
char ch; int QuantOfID=0;
while (ReadFromFile.get(ch))
{
if (ch!=' ')
{
ID[d][e]=ch;
e++;
}
else {d++; e=0; QuantOfID++;};
};
ReadFromFile.close();
for (d=0; d<=QuantOfID; d++)
{
cout<<"ID["<<d<<"]";
for (e=0; e<arraySize2; e++)
{
cout<<ID[d][e];
}
cout<<"\n";
}
cout<<" Table of IDs, which was built by rehash:"<<endl;
d=0; int last=0, sch=0, oldHashF=0, a=0, b=0, pointer=0; const Nm=367;
int HashF, CountColl=0, el=0, y=0, AverColl;
char NullStr[20][20]={NULL}; //инициализация пустой строки для подстановки вмеcто Property
char Reh[1][12]={NULL,NULL,'r','e','h','a','s','h','!'};
bool Coll[200]; for (e=0;e<200;e++) Coll[e]=false;
while (sch<=QuantOfID)
{
//if (ElExist(ID[d], TableID, Verific)==false)
// {
for ( e=0; e<40; e++)
{ //подсчет количества символов в идентивикаторе
if (int(ID[d][e])!=0) last++;
};
HashF=int(ID[d][0])+int(ID[d][last-2])+int(ID[d][last-1]);
if(TableID.HashTab[HashF]==500 ) {a=pointer; TableID.HashTab[HashF]=a;}
else a=TableID.HashTab[HashF];
TableID.HashTab[HashF]=a;
int i=a; b=0;
if (TableID.GetRecEF(a) == true)
{
TableID.createRec(a, ID[d], NullStr[1]);
while (TableID.GetRecEF(pointer)==false)
{
pointer++; //ищем след. свободную ячейку
};
}
else
{
while (TableID.GetRecEF(pointer)==false)
{
pointer++; //ищем след. свободную ячейку
};
while(TableID.GetRecLink(i)!=400)
{
i=TableID.GetRecLink(i); //если ссылка есть, то переходим по ней,т.е.определяем последн.
};
CountColl++;
Coll[a]=true;
do{
TableID.createRec(pointer, TableID.GetRecId(i), NullStr[1]);
TableID.removeRec(i);
TableID.FillRecLink(i,pointer);
while(TableID.GetRecLink(b)!=i)
{
b++;
if(b==367) break;
};
if(b==367) break;
pointer=i;
i=b; b=0;
}
while(b!=500);
TableID.createRec(i, ID[d], NullStr[1]);
/*TableID.PrintRec(i);*/ pointer=0;
while (TableID.GetRecEF(pointer)==false)
{
pointer++;
};
}
sch++; d++; last=0; //a++;
}
for (e=0; e<=QuantOfID; e++)
{
TableID.PrintRec(e);
if(TableID.GetRecLink(e)==400) cout<<" "<<endl;
else cout<<TableID.GetRecLink(e)<<endl;
}
for (e=0; e<200; e++) { if (Coll[e]==true) el++;}
AverColl=CountColl/el;
cout<<" Average quantity of collisions is "<<AverColl<<endl;
cout<<"\nEnter ID, which you can find: ";
char FindElem[40]={' '};
cin>>FindElem;
ElExist(FindElem, TableID);
cout<<"If you want to restart program press 1\n else press another key"<<endl;
cin>>e; if(e==1) continue; else break;
}
}
^

Блок-схема алгоритма поиска

Результаты выполнения программы

Вывод
В результате работы программы на экран выводится содержимое файла, из которого осуществляется чтение, затем содержимое таблицы идентификаторов, заполнение которой осуществлялось по методу, заданному в варианте задания. Также на экран выводится среднее число коллизий, возникших в результате заполнения таблицы. После поиска выводится число сравнений, произошедших при выполнении данной функции.
Скачать файл (5485.4 kb.)