Logo GenDocs.ru

Поиск по сайту:  
  Лекции
  Лабораторные
  Справочники
  Эссе
  Вопросы
  Стандарты
  Программы
  Дипломные
  Курсовые
  Помогалки
  Графические

Загрузка...

Лабораторные работы (ФИРТ 4 курс) - файл Лаба1.doc


Лабораторные работы (ФИРТ 4 курс)
скачать (5485.4 kb.)

Доступные файлы (87):

MyLab1.exe
MyLab1.ilk
MyLab1.obj
MyLab1.pch
MyLab1.pdb
vc60.idb
vc60.pdb
MyFile.txt1kb.29.10.2006 14:45скачать
myfil.txt0kb.01.11.2006 23:20скачать
MyLab1.cpp
MyLab1.dsp
MyLab1.dsw
MyLab1.ncb
MyLab1.opt
MyLab1.plg
Лаба1.doc179kb.23.12.2006 20:39скачать
MyLab2.exe
MyLab2.ilk
MyLab2.obj
MyLab2.pch
MyLab2.pdb
vc60.idb
vc60.pdb
myfile.txt1kb.11.11.2006 00:53скачать
MyLab2.cpp
MyLab2.dsp
MyLab2.dsw
MyLab2_func.h
MyLab2.ncb
MyLab2.opt
MyLab2.plg
Лаба2.doc1052kb.23.12.2006 20:39скачать
ex.txt1kb.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.txt1kb.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.txt4kb.24.11.2006 22:52скачать
LabSPO.ico
LabSPO.rc2
Thumbs.db
Resource.h
StdAfx.cpp
StdAfx.h
ex2.txt1kb.23.11.2006 18:47скачать
ex.txt1kb.22.11.2006 01:44скачать
mmm.txt0kb.30.11.2006 14:24скачать
myfile.txt0kb.30.11.2006 14:24скачать
MyLab3.exe
MyLab3.ilk
MyLab3.obj
MyLab3.pch
MyLab3.pdb
vc60.idb
vc60.pdb
ex2.txt1kb.23.11.2006 18:47скачать
ex.txt1kb.22.11.2006 01:44скачать
myfile.txt1kb.11.11.2006 00:53скачать
MyLab2_func.h
MyLab3.cpp
MyLab3.dsp
MyLab3.dsw
MyLab3.ncb
MyLab3.opt
MyLab3.plg
гзоҐзҐ
Лаба3.doc222kb.23.12.2006 20:40скачать

содержание

Лаба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.)

Поиск по сайту:  
© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации