Размещено на http://www.allbest.ru/

Министерство транспорта РФ

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

высшего профессионального образования

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ МОРСКОГО И РЕЧНОГО ФЛОТА ИМЕНИ АДМИРАЛА С.О. МАКАРОВА

Факультет информационных технологий

Кафедра вычислительных систем и информатики

Лабораторная работа № 1

Вариант 1

Выполнила: Дегтярева Н.Е

Проверила: Крупенина Н.В.

Санкт-Петербург 2015



Оглавление

Введение

Теоретические сведения

Простейшие методы построения таблиц идентификаторов

Хэш-функции и хэш-адресация

Хэш-функция

Блок схема

Код программы

Тест программы

Список литературы



Введение

идентификатор рехеширование таблица программа

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



Теоретические сведения

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

Можно выделить следующие способы организации таблиц идентификаторов:

· Простые и упорядоченные списки

· Бинарное дерево

· Хэш-адресация с рехэшированием

· Хэш-адресация по метод цепочек

· Комбинация хэш-адресации со списком или бинарным деревом

Простейшие методы построения таблиц идентификаторов

В простейшем случае таблица идентификаторов представляет собой линейный неупорядоченный список, или массив, каждая ячейка которого содержит данные о соответствующем элементе таблицы. Размещение новых элементов в такой таблице выполняется путем записи информации в очередную ячейку массива или списка по мере обнаружения новых элементов в исходной программе. Поиск нужного элемента в таблице будет в этом случае выполняться путем последовательного перебора всех элементов и сравнения их имени с именем искомого элемента, пока не будет найден элемент с таким же именем. Тогда если за единицу времени принять время, затрачиваемое компилятором на сравнение двух строк (в современных вычислительных системах такое сравнение чаще всего выполняется одной командой), то для таблицы, содержащей N элементов, в среднем будет выполнено N/2 сравнений. Время, требуемое на добавление нового элемента в таблицу (T_д), не зависит от числа элементов в таблице (N). Но если N велико, то поиск потребует значительных затрат времени. Время поиска (Т_п) в такой таблице можно оценить как Т_п = 0(N). Поскольку именно поиск в таблице идентификаторов является наиболее часто выполняемой компилятором операцией, такой способ организации таблиц идентификаторов является неэффективным. Он применим только для самых простых компиляторов, работающих с небольшими программами. Поиск может быть выполнен более эффективно, если элементы таблицы отсортированы (упорядочены) естественным образом. Поскольку поиск осуществляется по имени, наиболее естественным решением будет расположить элементы таблицы в прямом или обратном алфавитном порядке. Эффективным методом поиска в упорядоченном списке из N элементов является бинарный, или логарифмический; поиск. Алгоритм логарифмического поиска заключается в следующем: искомый символ сравнивается с элементом (N + 1)/2 в середине таблицы; если этот элемент не является искомым, то мы должны просмотреть только блок элементов, пронумерованных от 1 до (N + 1)/2 - 1, или блок элементов от (N + 1)/2 + 1 до N в зависимости от того, меньше или больше искомый элемент того, с которым его сравнили. Затем процесс повторяется над нужным блоком в два раза меньшего размера. Так продолжается до тех пор, пока либо искомый элемент не будет найден, либо алгоритм "не дойдет до очередного блока, содержащего один или два элемента (с которыми можно выполнить прямое сравнение искомого элемента). Так как на каждом шаге число элементов, которые могут содержать искомый элемент, сокращается в два раза, максимальное число сравнений равно 1 + log₂N. Тогда время поиска элемента в таблице идентификаторов можно оценить как Т_п = О(1og₂ N). Для сравнения: при N = 128 бинарный поиск требует самое большее 8 сравнений, а поиск в неупорядоченной таблице -- в среднем 64 сравнения. Метод называют «бинарным поиском», поскольку на каждом шаге объем рассматриваемой информации сокращается в два раза, а «логарифмпческим» -- поскольку время, затрачиваемое на поиск нужного элемента в массиве, имеет логарифмическую зависимость от общего количества элементов в нем. Недостатком логарифмического поиска является требование упорядочивания таблицы идентификаторов. Так как массив информации, в котором выполняется поиск, должен быть упорядочен, время его заполнения уже будет зависеть от числа элементов в массиве. Таблица идентификаторов зачастую просматривается компилятором еще до' того, как она заполнена, поэтому требуется, чтобы условие упорядоченности выполнялось на всех этапах обращения к ней. Следовательно, для построения такой таблицы можно пользоваться только алгоритмом прямого упорядоченного включения элементов. Если пользоваться стандартными алгоритмами, применяемыми для организации упорядоченных массивов данных, то среднее время, необходимое на помещение всех элементов в таблицу, можно оценить следующим образом:

Т_д= О(N*log₂ N) + k*О(N²).

Здесь k -- некоторый коэффициент, отражающий соотношение между временами, затрачиваемыми компьютером на выполнение операции сравнения и операции переноса данных. При организации логарифмического поиска в таблице идентификаторов обеспечивается существенное сокращение времени поиска нужного элемента за счет увеличения времени на помещение нового элемента в таблицу. Поскольку добавление новых элементов в таблицу идентификаторов происходит существенно реже, чем обращение к ним, этот метод следует признать более эффективным, чем метод организации неупорядоченной таблицы. Однако в реальных компиляторах этот метод непосредственно также не используется, поскольку существуют более эффективные методы.

Хэш-функции и хэш-адресация

В реальных исходных программах количество идентификаторов столь велико, что даже логарифмическую зависимость времени поиска от их числа нельзя признать удовлетворительной. Необходимы более эффективные методы поиска информации в таблице идентификаторов. Лучших результатов можно достичь, если применить методы, связанные с использованием хэш-функций и хэш-адресации.

Хэш-функцией F называется некоторое отображение множества входных элементов R на множество целых неотрицательных чисел Z: F(r) = n, r ? R, n ? Z. Сам термин «хэш-функция» происходит от английского термина <hash function» (hash - «мешать», «смешивать», «путать»). Вместо термина «хэширование» иногда используются термины «рандомизация», «переупорядочивание». Множество допустимых входных элементов R называется областью определения хэш-функции. Множеством значений хэш-функции F называется подмножество М из множества целых неотрицательных чисел Z: М, содержащее все возможные значения, возвращаемые функцией F: ? r?R: F(r) ?М. Процесс отображения области определения хэш-функции на множество значений называется «хэшированием». При работе с таблицей идентификаторов хэш-функция должна выполнять отображение имен идентификаторов на множество целых неотрицательных чисел.

Областью определения хэш-функции будет множество всех возможных имен идентификаторов.

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

Первоначально таблица идентификаторов должна быть заполнена информацией, которая позволила бы говорить о том, что все ее ячейки являются пустыми. Этот метод весьма эффективен, поскольку как время размещения элемента в таблице, так и время его поиска определяются только временем, затрачиваемым на вычисление хэш-функции, которое в общем случае несопоставимо меньше времени, необходимого для многократных сравнений элементов таблицы. Метод имеет два очевидных недостатка. Первый из них - неэффективное использование объема памяти под таблицу идентификаторов: размер массива для ее хранения должен соответствовать всей области значений хэш-функции, в то время как реально хранимых в таблице идентификаторов может быть существенно меньше. Второй недостаток - необходимость соответствующего разумного выбора хэш-функции. Этот недостаток является настолько существенным, что не позволяет непосредственно использовать хэш-адресацию для организации таблиц идентификаторов. Проблема выбора хэш-функции не имеет универсального решения. Хэширование обычно происходит за счет выполнения над цепочкой символов некоторых простых арифметических и логических операций. Самой простой хэш-функцией для символа является код внутреннего представления в компьютере литеры символа. Эту хэш-функцию можно использовать и для цепочки символов, выбирая первый символ в цепочке. Очевидно, что такая примитивная хэш-функция будет неудовлетворительной: при ее использовании возникнет проблема - двум различным идентификаторам, начинающимся с одной и той же буквы, будет соответствовать одно и то же значение хэш-функции. Тогда при хэш-адресации в одну и ту же ячейку таблицы идентификаторов должны быть помещены два различных идентификатора, что явно невозможно. Такая ситуация, когда двум или более идентификаторам соответствует одно и то же значение хэш-функции, называется коллизией. Естественно, что хэш-функция, допускающая коллизии, не может быть использована для хэш-адресации в таблице идентификаторов. Причем достаточно получить хотя бы один случай коллизии на всем множестве идентификаторов, чтобы такой хэш-функцией нельзя было пользоваться. Но возможно ли построить хэш-функцию, которая бы полностью исключала возникновение коллизий? Для полного исключения коллизий хэш-функция должна быть взаимно однозначной: каждому элементу из области определения хэш-функции должно соответствовать одно значение из ее множества значений, и наоборот - каждому значению из множества значений этой функции должен соответствовать только один элемент из ее области определения. Тогда любым двум произвольным элементам из области определения хэш-функции будут всегда соответствовать два различных ее значения. Теоретически для идентификаторов такую хэш-функцию построить можно, так как и область определения хэш-функции (все возможные имена идентификаторов), и область ее значений (целые неотрицательные числа) являются бесконечными счетными множествами, поэтому можно организовать взаимно однозначное отображение одного множества на другое. Но на практике существует ограничение, делающее создание взаимно однозначной хэш-функции для идентификаторов невозможным. Дело в том, что в реальности область значений любой хэш-функции ограничена размером доступного адресного пространства компьютера. Множество адресов любого компьютера с традиционной архитектурой может быть велико, но всегда конечно, то есть ограничено. Организовать взаимно однозначное отображение бесконечного множества на конечное даже теоретически невозможно. Можно, конечно, учесть, что длина принимаемой во внимание части имени идентификатора в реальных компиляторах на практике также ограничена - обычно она лежит в пределах от 32 до 128 символов (то есть и область определения хэш-функции конечна). Но и тогда количество элементов в конечном множестве, составляющем область определения хэш-функции, будет превышать их количество в конечном множестве области ее значений (количество всех возможных идентификаторов больше количества допустимых адресов в современных компьютерах). Таким образом, создать взаимно однозначную хэш-функцию на практике невозможно. Следовательно, невозможно избежать возникновения коллизий. Поэтому нельзя организовать таблицу идентификаторов непосредственно на основе одной только хэш-адресации. Но существуют методы, позволяющие использовать хэш-функции для организации таблиц идентификаторов даже при наличии коллизий.

Для решения проблемы коллизии можно использовать много способов. Одним из них является метод рехэширования (или расстановки). Согласно этому методу, если для элемента А адрес n₀ = h(А), вычисленный с помощью хэш-функции h, указывает на уже занятую ячейку, то необходимо вычислить значение функции n₁ = h₁(А) и проверить занятость ячейки по адресу n₁. Если и она занята, то вычисляется значение h₂(А), и так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение h_i(А) не совпадет с h(А). В последнем случае считается, что таблица идентификаторов заполнена и места в ней больше нет -- выдается информация об ошибке размещения идентификатора в таблице. Тогда поиск элемента А в таблице идентификаторов, организованной таким образом, будет выполняться по следующему алгоритму:
1. Вычислить значение хэш-функции n = h(А) для искомого элемента А.

2. Если ячейка по адресу n пустая, то элемент не найден, алгоритм завершен, иначе необходимо сравнить имя элемента в ячейке n с именем искомого элемента А. Если они совпадают, то элемент найден и алгоритм завершен, иначе i:= 1 и перейти к шагу 3.

3. Вычислить n_i = h_i(А). Если ячейка по адресу n_i пустая или n = n_i, то элемент не найден и алгоритм завершен, иначе -- сравнить имя элемента в ячейке n_i с именем искомого элемента А. Если они совпадают, то элемент найден и алгоритм завершен, иначе i:= i + 1 и повторить шаг 3.

Алгоритмы размещения и поиска элемента схожи по выполняемым операциям. Поэтому они будут иметь одинаковые оценки времени, необходимого для их выполнения.

При такой организации таблиц идентификаторов в случае возникновения коллизии алгоритм помещает элементы в пустые ячейки таблицы, выбирая их определенным образом. При этом элементы могут попадать в ячейки с адресами, которые потом будут совпадать со значениями хэш-функции, что приведет к возникновению новых, дополнительных коллизий. Таким образом, количество операций, необходимых для поиска или размещения в таблице элемента, зависит от заполненности таблицы. Для организации таблицы идентификаторов по методу рехэширования необходимо определить все хэш-функции h_i для всех i. Чаще всего функции h_i определяют как некоторые модификации хэш-функции h. Например, самым простым методом вычисления функции h_i(А) является ее организация в виде h_i(А) = (h(А) + р_i) mod N_m, где р_i -- некоторое вычисляемое целое число, а N_m -- максимальное значение из области значений хэш-функции h. В свою очередь, самым простым подходом здесь будет положить р_i = i. Тогда получаем формулу h_i(А) = (h(А) + i) mod N_m. В этом случае при совпадении значений хэш-функции для каких-либо элементов поиск свободной ячейки в таблице начинается последовательно от текущей позиции; заданной хэш-функцией h(А). Этот способ нельзя признать особенно удачным: при совпадении хэш адресов элементы в таблице начинают группироваться вокруг них, что увеличивает число необходимых сравнений при поиске и размещении. Но даже такой примитивный метод рехэширования является достаточно эффективным средством организации таблиц идентификаторов при неполном заполнении таблицы.

Хэш-функция

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

Будем считать, что прописные и строчные буквы в идентификаторах различны. В качестве кодов символов мы возьмем коды таблицы ASCLL. Тогда, если положить, что строка из области определения хэш-функции содержит только цифры и буквы английского алфавита, то минимальным значением хэш-функции будет сумма трех кодов цифры «0», а максимальным значением - сумма трех кодов буквы «z».

Таким образом, диапазон области значений составляет 223 элемента, что удовлетворяет требованиям задания (не менее 200 элементов). Длина входных идентификаторов в данном случае ничем не ограничена.



Блок схема

Код программы

#include "Function.h"

#include <iostream>

#include <sstream>

#include <fstream>

#include <string>

using namespace std;

int count_hex1=0,count_hex2=0,count=0;

string* beg= new string[100];

int n;

namespace Молчанов4 {

using namespace System;

using namespace System::ComponentModel;

using namespace System::Collections;

using namespace System::Windows::Forms;

using namespace System::Data;

using namespace System::Drawing;

/// <summary>

/// Сводка для Form1

/// </summary>

public ref class Form1: public System::Windows::Forms::Form

{

public:

Form1(void)

{

InitializeComponent();

//

//TODO: добавьте код конструктора

//

}

protected:

/// <summary>

/// Освободить все используемые ресурсы.

/// </summary>

~Form1()

{

if (components)

{

delete components;

}

}

private: System::Windows::Forms::Button^ button1;

private: System::Windows::Forms::GroupBox^ groupBox1;

private: System::Windows::Forms::ListBox^ listBox1;

private: System::Windows::Forms::TextBox^ textBox1;

private: System::Windows::Forms::Button^ button2;

private: System::Windows::Forms::Button^ button3;

private: System::Windows::Forms::OpenFileDialog^ openFileDialog1;

private: System::Windows::Forms::GroupBox^ groupBox2;

private: System::Windows::Forms::GroupBox^ groupBox3;

private: System::Windows::Forms::Button^ button5;

private: System::Windows::Forms::Button^ button4;

private: System::Windows::Forms::TextBox^ textBox2;

private: System::Windows::Forms::GroupBox^ groupBox4;

private: System::Windows::Forms::GroupBox^ groupBox5;

private: System::Windows::Forms::Label^ label5;

private: System::Windows::Forms::Label^ label4;

private: System::Windows::Forms::Label^ label3;

private: System::Windows::Forms::Label^ label2;

private: System::Windows::Forms::Label^ label1;

private: System::Windows::Forms::Label^ label6;

private: System::Windows::Forms::Label^ label9;

private: System::Windows::Forms::Label^ label8;

private: System::Windows::Forms::Label^ label7;

private: System::Windows::Forms::Button^ button6;

private: System::ComponentModel::IContainer^ components;

protected:

private:

/// <summary>

/// Требуется переменная конструктора.

/// </summary>

#pragma region Windows Form Designer generated code

/// <summary>

/// Обязательный метод для поддержки конструктора - не изменяйте

/// содержимое данного метода при помощи редактора кода.

/// </summary>

void InitializeComponent(void)

{

this->button1 = (gcnew System::Windows::Forms::Button());

this->groupBox1 = (gcnew System::Windows::Forms::GroupBox());

this->listBox1 = (gcnew System::Windows::Forms::ListBox());

this->textBox1 = (gcnew System::Windows::Forms::TextBox());

this->button2 = (gcnew System::Windows::Forms::Button());

this->button3 = (gcnew System::Windows::Forms::Button());

this->openFileDialog1 = (gcnew System::Windows::Forms::OpenFileDialog());

this->groupBox2 = (gcnew System::Windows::Forms::GroupBox());

this->groupBox3 = (gcnew System::Windows::Forms::GroupBox());

this->button6 = (gcnew System::Windows::Forms::Button());

this->groupBox5 = (gcnew System::Windows::Forms::GroupBox());

this->label9 = (gcnew System::Windows::Forms::Label());

this->label8 = (gcnew System::Windows::Forms::Label());

this->label7 = (gcnew System::Windows::Forms::Label());

this->label6 = (gcnew System::Windows::Forms::Label());

this->label5 = (gcnew System::Windows::Forms::Label());

this->button5 = (gcnew System::Windows::Forms::Button());

this->button4 = (gcnew System::Windows::Forms::Button());

this->textBox2 = (gcnew System::Windows::Forms::TextBox());

this->groupBox4 = (gcnew System::Windows::Forms::GroupBox());

this->label4 = (gcnew System::Windows::Forms::Label());

this->label3 = (gcnew System::Windows::Forms::Label());

this->label2 = (gcnew System::Windows::Forms::Label());

this->label1 = (gcnew System::Windows::Forms::Label());

this->groupBox1->SuspendLayout();

this->groupBox2->SuspendLayout();

this->groupBox3->SuspendLayout();

this->groupBox5->SuspendLayout();

this->groupBox4->SuspendLayout();

this->SuspendLayout();

//

// button1

//

this->button1->Location = System::Drawing::Point(16, -182);

this->button1->Name = L"button1";

this->button1->Size = System::Drawing::Size(99, 23);

this->button1->TabIndex = 0;

this->button1->Text = L"button1";

this->button1->UseVisualStyleBackColor = true;

//

// groupBox1

//

this->groupBox1->Controls->Add(this->listBox1);

this->groupBox1->Location = System::Drawing::Point(12, 22);

this->groupBox1->Name = L"groupBox1";

this->groupBox1->Size = System::Drawing::Size(348, 351);

this->groupBox1->TabIndex = 2;

this->groupBox1->TabStop = false;

this->groupBox1->Text = L"Исходные данные";

//

// listBox1

//

this->listBox1->FormattingEnabled = true;

this->listBox1->Location = System::Drawing::Point(6, 16);

this->listBox1->Name = L"listBox1";

this->listBox1->Size = System::Drawing::Size(336, 329);

this->listBox1->TabIndex = 0;

this->listBox1->SelectedIndexChanged += gcnew System::EventHandler(this, &Form1::listBox1_SelectedIndexChanged_1);

//

// textBox1

//

this->textBox1->Location = System::Drawing::Point(16, 28);

this->textBox1->Name = L"textBox1";

this->textBox1->Size = System::Drawing::Size(375, 20);

this->textBox1->TabIndex = 4;

//

// button2

//

this->button2->Location = System::Drawing::Point(16, 54);

this->button2->Name = L"button2";

this->button2->Size = System::Drawing::Size(98, 20);

this->button2->TabIndex = 5;

this->button2->Text = L"Выбрать файл";

this->button2->UseVisualStyleBackColor = true;

this->button2->Click += gcnew System::EventHandler(this, &Form1::button2_Click);

//

// button3

//

this->button3->Location = System::Drawing::Point(16, 80);

this->button3->Name = L"button3";

this->button3->Size = System::Drawing::Size(98, 22);

this->button3->TabIndex = 6;

this->button3->Text = L"Загрузить файл";

this->button3->UseVisualStyleBackColor = true;

this->button3->Click += gcnew System::EventHandler(this, &Form1::button3_Click);

//

// openFileDialog1

//

this->openFileDialog1->FileName = L"openFileDialog1";

//

// groupBox2

//

this->groupBox2->Controls->Add(this->textBox1);

this->groupBox2->Controls->Add(this->button3);

this->groupBox2->Controls->Add(this->button2);

this->groupBox2->Location = System::Drawing::Point(380, 22);

this->groupBox2->Name = L"groupBox2";

this->groupBox2->Size = System::Drawing::Size(413, 111);

this->groupBox2->TabIndex = 7;

this->groupBox2->TabStop = false;

this->groupBox2->Text = L"Исходный файл";

//

// groupBox3

//

this->groupBox3->Controls->Add(this->button6);

this->groupBox3->Controls->Add(this->groupBox5);

this->groupBox3->Controls->Add(this->label5);

this->groupBox3->Controls->Add(this->button5);

this->groupBox3->Controls->Add(this->button4);

this->groupBox3->Controls->Add(this->textBox2);

this->groupBox3->Location = System::Drawing::Point(380, 142);

this->groupBox3->Name = L"groupBox3";

this->groupBox3->Size = System::Drawing::Size(413, 231);

this->groupBox3->TabIndex = 8;

this->groupBox3->TabStop = false;

this->groupBox3->Text = L"Поиск идентификатора";

//

// button6

//

this->button6->Location = System::Drawing::Point(16, 49);

this->button6->Name = L"button6";

this->button6->Size = System::Drawing::Size(103, 23);

this->button6->TabIndex = 11;

this->button6->Text = L"Найти все";

this->button6->UseVisualStyleBackColor = true;

this->button6->Click += gcnew System::EventHandler(this, &Form1::button6_Click_1);

//

// groupBox5

//

this->groupBox5->Controls->Add(this->label9);

this->groupBox5->Controls->Add(this->label8);

this->groupBox5->Controls->Add(this->label7);

this->groupBox5->Controls->Add(this->label6);

this->groupBox5->Location = System::Drawing::Point(216, 79);

this->groupBox5->Name = L"groupBox5";

this->groupBox5->Size = System::Drawing::Size(175, 140);

this->groupBox5->TabIndex = 10;

this->groupBox5->TabStop = false;

this->groupBox5->Text = L"Рехэширование с псевдо сл. ч.";

//

// label9

//

this->label9->AutoSize = true;

this->label9->Location = System::Drawing::Point(7, 105);

this->label9->Name = L"label9";

this->label9->Size = System::Drawing::Size(124, 13);

this->label9->TabIndex = 3;

this->label9->Text = L"В среднем сравнений: ";

//

// label8

//

this->label8->AutoSize = true;

this->label8->Location = System::Drawing::Point(7, 77);

this->label8->Name = L"label8";

this->label8->Size = System::Drawing::Size(100, 13);

this->label8->TabIndex = 2;

this->label8->Text = L"Всего сравнений: ";

//

// label7

//

this->label7->AutoSize = true;

this->label7->Location = System::Drawing::Point(7, 52);

this->label7->Name = L"label7";

this->label7->Size = System::Drawing::Size(68, 13);

this->label7->TabIndex = 1;

this->label7->Text = L"Сравнений: ";

//

// label6

//

this->label6->AutoSize = true;

this->label6->Location = System::Drawing::Point(7, 25);

this->label6->Name = L"label6";

this->label6->Size = System::Drawing::Size(87, 13);

this->label6->TabIndex = 0;

this->label6->Text = L"Идентификатор";

//

// label5

//

this->label5->AutoSize = true;

this->label5->Location = System::Drawing::Point(125, 54);

this->label5->Name = L"label5";

this->label5->Size = System::Drawing::Size(100, 13);

this->label5->TabIndex = 3;

this->label5->Text = L"Всего сравнений: ";

//

// button5

//

this->button5->Location = System::Drawing::Point(328, 49);

this->button5->Name = L"button5";

this->button5->Size = System::Drawing::Size(63, 23);

this->button5->TabIndex = 2;

this->button5->Text = L"Сброс";

this->button5->UseVisualStyleBackColor = true;

//

// button4

//

this->button4->Location = System::Drawing::Point(328, 19);

this->button4->Name = L"button4";

this->button4->Size = System::Drawing::Size(63, 24);

this->button4->TabIndex = 1;

this->button4->Text = L"Поиск";

this->button4->UseVisualStyleBackColor = true;

this->button4->Click += gcnew System::EventHandler(this, &Form1::button4_Click);

//

// textBox2

//

this->textBox2->Location = System::Drawing::Point(16, 20);

this->textBox2->Name = L"textBox2";

this->textBox2->Size = System::Drawing::Size(289, 20);

this->textBox2->TabIndex = 0;

this->textBox2->TextChanged += gcnew System::EventHandler(this, &Form1::textBox2_TextChanged);

//

// groupBox4

//

this->groupBox4->Controls->Add(this->label4);

this->groupBox4->Controls->Add(this->label3);

this->groupBox4->Controls->Add(this->label2);

this->groupBox4->Controls->Add(this->label1);

this->groupBox4->Location = System::Drawing::Point(398, 220);

this->groupBox4->Name = L"groupBox4";

this->groupBox4->Size = System::Drawing::Size(178, 141);

this->groupBox4->TabIndex = 9;

this->groupBox4->TabStop = false;

this->groupBox4->Text = L"Рехэширование простое";

//

// label4

//

this->label4->AutoSize = true;

this->label4->Location = System::Drawing::Point(6, 105);

this->label4->Name = L"label4";

this->label4->Size = System::Drawing::Size(124, 13);

this->label4->TabIndex = 3;

this->label4->Text = L"В среднем сравнений: ";

//

// label3

//

this->label3->AutoSize = true;

this->label3->Location = System::Drawing::Point(6, 77);

this->label3->Name = L"label3";

this->label3->Size = System::Drawing::Size(100, 13);

this->label3->TabIndex = 2;

this->label3->Text = L"Всего сравнений: ";

//

// label2

//

this->label2->AutoSize = true;

this->label2->Location = System::Drawing::Point(6, 52);

this->label2->Name = L"label2";

this->label2->Size = System::Drawing::Size(68, 13);

this->label2->TabIndex = 1;

this->label2->Text = L"Сравнений: ";

//

// label1

//

this->label1->AutoSize = true;

this->label1->Location = System::Drawing::Point(6, 26);

this->label1->Name = L"label1";

this->label1->Size = System::Drawing::Size(87, 13);

this->label1->TabIndex = 0;

this->label1->Text = L"Идентификатор";

//

// Form1

//

this->AutoScaleDimensions = System::Drawing::SizeF(6, 13);

this->AutoScaleMode = System::Windows::Forms::AutoScaleMode::Font;

this->ClientSize = System::Drawing::Size(805, 381);

this->Controls->Add(this->groupBox4);

this->Controls->Add(this->groupBox3);

this->Controls->Add(this->groupBox2);

this->Controls->Add(this->groupBox1);

this->Controls->Add(this->button1);

this->Name = L"Form1";

this->Text = L"Form1";

this->Load += gcnew System::EventHandler(this, &Form1::Form1_Load);

this->groupBox1->ResumeLayout(false);

this->groupBox2->ResumeLayout(false);

this->groupBox2->PerformLayout();

this->groupBox3->ResumeLayout(false);

this->groupBox3->PerformLayout();

this->groupBox5->ResumeLayout(false);

this->groupBox5->PerformLayout();

this->groupBox4->ResumeLayout(false);

this->groupBox4->PerformLayout();

this->ResumeLayout(false);

}

#pragma endregion

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

}

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

}

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

OpenFileDialog^ openFileDialog1 = gcnew OpenFileDialog;

openFileDialog1->ShowDialog();

textBox1->Text=openFileDialog1->FileName;

}

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

this->listBox1->Items->Clear();

fstream in (SysToStd(textBox1->Text));

string s;

int i=0;

while (!in.eof())

{

getline(in,s);

if (s!="") this->listBox1->Items->Add(StdToSys(s));

if (s!="") beg[i]=s;

i++;

}

n=i;

}

static System::String^ StdToSys(std::string StdStr){

return gcnew System::String(StdStr.c_str());

}

static std::string SysToStd(System::String^ SysStr){

using namespace Runtime::InteropServices;

char *v = (char*) (Marshal::StringToHGlobalAnsi(SysStr)).ToPointer() ;

std::string result = std::string(v);

Marshal::FreeHGlobal(System::IntPtr((void*)v));

return result;

}

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

}

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

int k=0;

String^ slovo=this->textBox2->Text;

bool check;

search_hex(SysToStd(slovo),k,check);

if (check) this->label1->Text="Идентификатор найден";

else this->label1->Text="Идентификатор не найден";

this->label2->Text="Сравнений: " + k;

k=0;

search_hex1(SysToStd(slovo),k,check);

if (check) this->label6->Text="Идентификатор найден";

else this->label6->Text="Идентификатор не найден";

this->label7->Text="Сравнений: " + k;

}

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

}

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

count=0;

count_hex1=0;

count_hex2=0;

bool check=false;

count+=n;

start_hex(beg,n,count_hex1);

start_hex1(beg,n,count_hex2);

for (int i=0; i<n; i++)

{

int j=0;

while (beg[j]!=beg[i])

{

j++;

count++;

}

search_hex(beg[i],count_hex1,check);

search_hex1(beg[i],count_hex2,check);

}

this->label5->Text="Всего сравнений: " + count;

this->label3->Text="Всего сравнений: " + count_hex1;

this->label8->Text="Всего сравнений: " + count_hex2;

this->label4->Text="В среднем сравнений: " + (float)count_hex1/count;

this->label9->Text="В среднем сравнений: " + (float)count_hex2/count;

}

};

}

#include "stdafx.h"

#include "Function.h"

//////Функции Организации таблиц/////////////////

#include <iostream>

#include <string>

using namespace std;

struct chains

{

string a;

chains *next;

};

int HASH_MIN = '0'+'0'+'0';

int HASH_MAX = 'z'+'z'+'z';

chains *begin;

string begin2[366];

int k=0;

bool search(string* a,int n,string str, int &count)

{

int i=0;

while (a[i]!=str)

{

i++;

if (i==n) break;

}

count+=i;

if (i==n) return false; else return true;

}

int hex (string str,int c)

{

int result=(int)str[0]+(int)str[(str.length()-1)/2]+(int)str[str.length()-1];

result+=c;

result%=366;

return result;

};

void start_line(string* a,int n,int &count)

{

::begin=NULL;

for (int i=0; i<n; i++)

{

chains *b=new chains;

b->a=a[i];

b->next=NULL;

if (::begin == NULL)

{

::begin=b;

count++;

}

else

{

chains *c=::begin;

while (c->next!=NULL)

{

c=c->next;

count++;

}

c->next=b;

}

}

};

void search_line (string str, int &count,bool &check)

{

check=true;

if (::begin == NULL) {check=false;}

if (::begin->a == str)

{

count++;

}

else {

chains *c=::begin;

while (c->next!=NULL)

{

count++;

c=c->next;

if (c->a == str) break;

}

if (c->a!= str) {check=false;}

}

}

///////////простой рехэш////////////

void start_hex(string* a,int n,int &count)

{

k=-2;

int d;

for (int i=0; i<366; i++)::begin2[i]="";

int rehash=0;

for (int i=0; i<n; i++)

{

int res=hex(a[i],rehash);

if (::begin2[res] == "")

{

::begin2[res]= a[i];

count+=k+rehash;

k++;

rehash=0;

}

else

{

if (::begin2[res] == a[i])

{

rehash=0;

}

else

{

++rehash;

i--;

}

}

}

};

void search_hex (string str, int &count,bool &check)

{

k=0;

check=true;

for (int i=0; i<200; i++)

{

int hash=hex(str,i);

if (::begin2[hash] == "") {check=false; break;}

if (::begin2[hash] == str)

{

count++;

break;

} else count++;

}

}



Тест программы



Список литературы

1. А.Ю. Молчанов Системное програмное обеспечение [Книга]. Санкт-Петербург: Питер, 2005.

2. Гордеев А.В. Молчанов А.Ю. Системное програмное обеспечение [Книга]. Санкт-Петербург: Питер, 2001.

Размещено на Allbest.ru