БФИ1801, СПО, Паршикова А.П., лр№1. Цель работы Изучить основные методы организации таблиц идентификаторов, получить представление о преимуществах и недостатках, присущих различным методам организации таблиц идентификаторов. Задание

• Название: Цель работы Изучить основные методы организации таблиц идентификаторов, получить представление о преимуществах и недостатках, присущих различным методам организации таблиц идентификаторов. Задание
• Дата: 14.02.2022
• Размер: 208.52 Kb.
• Имя файла: БФИ1801, СПО, Паршикова А.П., лр№1.docx
• Тип: Отчет; #361673

МИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ, СВЯЗИ И МАССОВЫХ КОММУНИКАЦИЙ РОССИЙСКОЙ ФЕДЕРАЦИИ

Ордена Трудового Красного Знамени

Федеральное государственное бюджетное образовательное учреждение высшего образования

Московский технический университет связи и информатики

(МТУСИ)

Кафедра «Системное программирование»

Отчёт по лабораторной работе №1

по дисциплине «Системное программное обеспечение»

Подготовила студентка

группы БФИ1801

Паршикова А.П.

Проверила

Алексанян Д.А.


Москва 2021

1. 
   Цель работы
   

Изучить основные методы организации таблиц идентификаторов, получить представление о преимуществах и недостатках, присущих различным методам организации таблиц идентификаторов.

2. 
   Задание
   

Для выполнения лабораторной работы требуется написать программу, которая получает на входе набор идентификаторов, организует таблицы идентификаторов с помощью заданных методов, позволяет осуществить многократный поиск произвольного идентификатора в таблицах и сравнить эффективность методов организации таблиц.

Список идентификаторов считать заданным в виде текстового файла. Длина идентификаторов ограничена 32 символами.
Таблица 1 – Вариант задания

№ вар	Первый метод организации таблицы	Второй метод организации таблицы
22	Простое рехэширование	Упорядоченный список

В качестве хэш-функции будет использована сумма кодов всех букв слова.

3. 
   Выполнение
   

Тестирование методов было выполнено с помощью списка идентификаторов вида “имя значения”, который содержит имя идентификатора и дополнительную информацию о нём, представленную в виде целочисленного значения. Список показан на рисунке 1.



Рисунок 1 – Список идентификаторов

Были реализованы методы хранения идентификаторов с применением метода простого рехеширования и упорядоченного списка. Для тестирования идентификаторы загружались в структуры данных, а затем в них происходил поиск идентификатора. Поиск происходил быстрее для метода простого рехэширования.

На рисунке 2 представлен результат выполнения программы.



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

4. 
   Текст программного кода
   

MyForm.h

#include

#include

#include

#include

#include

#include "stdafx.h"

#include

#include

#include "Hash.h"

#include "OrderdList.h"

void fillTableHash(RehashTable* table, string file, int identNum) { //Заполнение таблицы идентификаторов

ifstream in(file, ios::in);
for (int i = 0; i < identNum; i++) {

int val;

string name;

in >> name >> val;

table->Add(make_pair(name, val));

}

in.close();

}
void fillTableList(ListTable* table, string file, int identNum) { //Заполнение таблицы идентификаторов

ifstream in(file, ios::in);
for (int i = 0; i < identNum; i++) {

int val;

string name;

in >> name >> val;

table->Add(make_pair(name, val));

}

in.close();

}
void RehashFind(int identNum, string filePath, string id) {
RehashTable* simpleRehashTable = new RehashTable(500);
//считывание из файла

fillTableHash(simpleRehashTable, filePath, identNum);
double t1, t2;
t1 = clock();

int gotVal = simpleRehashTable->Get(id);

t2 = clock();
if (gotVal == 99999) {

label7->Text = "Не найден";

label3->Text = "";

}

else

{

label7->Text = Convert::ToString(gotVal);

label3->Text = Convert::ToString(RehashTable::hash(id));

}

label5->Text = Convert::ToString((t2 - t1) / 1000.0);
}

void ListFind(int identNum, string filePath, string id) {

ListTable* listTable = new ListTable(identNum * 2);
//считывание из файла

fillTableList(listTable, filePath, identNum);
double t1, t2;

t1 = clock();

auto gotVal = listTable->Get(id);

t2 = clock();

if (gotVal == 0) {

label10->Text = "Не найден";

}

else {

label10->Text = Convert::ToString(gotVal);

}


label9->Text = Convert::ToString((t2 - t1) / 1000.0);


}
void RunRehashAdd(int identNum, string filePath, string id){

double t1, t2;

RehashTable* simpleRehashTable = new RehashTable(500);
t1 = clock();

simpleRehashTable->Add(make_pair(id, 0));

t2 = clock();
label3->Text = Convert::ToString(RehashTable::hash(id));

label5->Text = Convert::ToString((t2 - t1) / 1000.0);

//label7->Text = Convert::ToString(gotVal);

}
private: System::Void button2_Click(System::Object^ sender, System::EventArgs^ e) {

int MaxHash = char('z') + char('z') + char('z');

String^ filePath = "C://4курс 1сем//Системное ПО//СПО1.txt";

IO::StreamReader^ R = gcnew IO::StreamReader(filePath);

textBox1->Text = R->ReadToEnd();

int MaxHash2 = Convert::ToInt16(MaxHash);

}

private: System::Void button3_Click(System::Object^ sender, System::EventArgs^ e) {

int identNum = 2048;

string filePath = "C://4курс 1сем//Системное ПО//СПО1.txt";

String ^id = Convert::ToString(textBox3->Text); //Для поиска

string id2 = marshal_as(id);

RehashFind(identNum, filePath, id2);

ListFind(identNum, filePath, id2);

}

private: System::Void button4_Click(System::Object^ sender, System::EventArgs^ e) {

textBox3->Clear();

label3->Text = "";

label5->Text = "";

label7->Text = "";

label9->Text = "";

label10->Text = "";

}
private: System::Void button6_Click(System::Object^ sender, System::EventArgs^ e) {

Application::Exit();

}

Hash.h

#include "stdafx.h"

#include

#include

#include

#include
using namespace System;

using namespace Windows::Forms;

using namespace System::Windows::Forms;

using namespace std;
template class RehashTable {

public:
vector*> vars;
RehashTable(int size) {

vars = vector*>(size);

}
RehashTable() {

for (auto p : vars) {

if (p != NULL) {

delete p;

}

}

}
void Add(pair var)

{
if (var.first.length() > 32)

throw exception("Слишком длинное имя идентификатора!");
int startN = hash(var.first); //Первый хэш

vector v(0);
if (vars[startN] != NULL) { //Если место в хэш-таблице занято
for (int i = 1, n = hashI(i, var.first); //Вычисляем новый хэш

n != startN; i++, n = hashI(i, var.first)) {
v.push_back(n); //Добавляем этот хэш
if (vars[n] == NULL) { //Если место (с новым хэшем) пустое

vars[n] = new pair(var.first, var.second); //Добавляем туда идентификатор

return;

}

}
throw exception("Таблица переполнена!");

}
vars[startN] = new pair(var.first, var.second);

}
TValue Get(string id)

{

int Count2 = 0;

int startN = hash(id); //Первый хэш
if (vars[startN] == NULL) {

throw exception("Идентификатор не найден!");

}
if (vars[start]->first != id) { //Если элемент с 1ым хэшем не равен идентификатору

//Count2++;

for (int i = 1, n = rehash(i, id); //Вычисляем новый хэш

n != start; i++, n = rehash(i, id)) {

Count2++;

if (vars[n]->first == id) {

//return vars[n]->second;

return i;

}

}

return 99999;

}

return i;

}

//Основная хэш-функция

int static hash(string id) {

int sum = 0;

int HASH_MIN = (char)('0') + (char)('0') + (char)('0');

int HASH_MAX = (char)('z') + (char)('z') + (char)('z');

for (char ch : id)

sum += (int)ch;
return sum % (HASH_MAX - HASH_MIN + 1) + HASH_MIN;
}
//Функция рехеширования

int static hashI(int i, string id) {

int HASH_MIN = (char)('0') + (char)('0') + (char)('0');

int HASH_MAX = (char)('z') + (char)('z') + (char)('z');

return (hash(id) + i) % (HASH_MAX - HASH_MIN + 1) + HASH_MIN;

}

OrderdList.h

#include "stdafx.h"

#include

#include

#include

#include

#include
using namespace System;

using namespace Windows::Forms;

using namespace System::Windows::Forms;
template class ListTable {

public:
vector vars;
ListTable(int size) {

vars = vector(size);

}
ListTable() {

for (auto p : vars) {

if (p != NULL) {

delete p;

}

}

}
auto Get(string id)

{

auto pos = 0;

vector::iterator it = find(vars.begin(), vars.end(), id);

if (it != vars.end()) {

// string found!

pos = distance(vars.begin(), it) - 5909;

return pos;

}

}

void Add(pair var)

{

vars.push_back(var.first);

sort(vars.begin(), vars.end());

}

};

5. 
   Вывод
   

В результате выполнения лабораторной работы были изучены основные методы организации таблиц идентификаторов, получены представление о преимуществах и недостатках, присущих различным методам организации таблиц идентификаторов.