Лабы заочникам Яковлев / SiAOD(с++) / lab2 / Unit1

//---------------------------------------------------------------------------
 
#include <vcl.h>
#pragma hdrstop
#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
 
//---------------------------------------------------------------------------
 
#pragma argsused
 
struct link//Список значений
{
        char* value;
        link* next;
};
 
class dict // класс, представл¤ющий собой словарь
{
private:
    link** spisok;//Массив списков класса dict
    int Hash(char* value);//Функция вычисления хэша
 
public:
    dict();//Конструктор
    link* Find(char* value);
    void Insert(char* value);
    bool Delete(char* value);
    ~dict();//Деструктор
};
 
void SearchV(dict* sp);
void InsertV(dict* sp);
void DeleteV(dict* sp);
 
const int maxstrlen = 100;
 
dict::dict() // конструктор
{
    this->spisok = new link*[256];
    for (int i = 0; i < 256; i++)
    {
        this->spisok[i] = NULL;
    }
}
 
int dict::Hash(char* value) // хеш-функци¤
{
    //Хэш - код первого символа в значении
    //Основные коды символов в ASCII таблице 0-255 включительно, поэтому скорее всего не выйдем за пределы массива
    return value[0];
}
 
link* dict::Find(char* value) // метод поиска строки в словаре
{
    //Получаем i-ый список в массиве списков(лучше Hash(value)%256), т.к. есть символы которые выходят из этого диапазона
    link* rez = spisok[Hash(value)];
    if (rez)//если ссылка на rez не равна 0((т.е. не NULL)т.к. 0 в приведении к bool это false)
    {
        while (strcmp(rez->value, value) != 0)//значение в списке не равно переданному значению(сравнение по строкам)
        {
            if (rez->next)//Если существует следующий элемент, то переходим на него
            {
                rez = rez->next;
            }
            else//Иначе выходим из цикла(т.е. дошли до последнего элемента в списке)
            {
                break;
            }
        }
        if (strcmp(rez->value, value) == 0)//Если значение текущего элемента в списке равно переданному, то возвращаем этот элемент
        {
            return rez;
        }
       
    }
    //Во всех остальных случаях возвращаем NULL
   
    return NULL;
}
 
void dict::Insert(char* value) // метод вставки строки в словарь
{
    int hash = Hash(value);//Вычисляем хэш
    link* current = spisok[hash];//Получаем список из массива списков
    if (current)//Если он не пустой
    {
        while (current->next)//Идём в конец массива
        {
            current = current->next;
        }
        //Создаем новый элемент списка и задаём ему значение
        current->next = new link();
        current->next->value = value;
    }
    else
    {
        //Иначе просто создаём новый элемент списка(задаём ему значение), и делаем его первым в массиве списков с текущем хэшом
        current = new link();
        current->value = value;
        spisok[hash] = current;
    }
}
bool dict::Delete(char* value) // удаление элемента
{
    int hash = Hash(value);
    link* current = spisok[hash];
    //Возвращаем true если элемент удалён, иначе false
    if (current)
    {
        link* prev = current;
        //Получение предыдущего элемента перед, элементом с переданным значением
        while (current->next && strcmp(current->next->value, value) != 0)
        {
            prev = current;
            current = current->next;
        }
        //Если у текущего элемента существуют значения
        if (current->value)
        {
            //Если у текущего элемента есть следующий элемент
            if (current->next)
            {
               
                //Если значение следующего элемента равно переданному, то выкидываем его из списка
                if (strcmp(current->next->value, value) == 0)
                {
                    link* next = current->next->next;
                    current->next = next;
                    return true;
                }
            }
            //Если нету следующего элемента
            else
            {
                //Если мы вначале списка
                if (current == spisok[hash])
                {
                    //Выкидываем список
                    spisok[hash] = NULL;
                }
                //Иначе если существует предыдущий
                else if (prev)
                {
                    //То удаляем текущий
                    prev->next = NULL;
                    current = NULL;
                }
                return true;
            }
        }
    }
    return false;
}

dict::~dict()//Деструктор
{
    //Освобождаем память от массива списков
    delete[] spisok;
}
int main(int argc, char* argv[])
{
        dict spisok = dict();
        while (1)
        {
	        cout << endl << "Dejstvie: " << endl;
	        cout << "1) Search" << endl;
	        cout << "2) Insert" << endl;
	        cout << "3) Delete" << endl;
	        cout << "4) Exit" << endl;
	        int value = 0;
	        cin >> value;
	        cout << endl;
	        switch (value)
	        {
		        case 1: SearchV(&spisok); break;
		        case 2: InsertV(&spisok); break;
		        case 3: DeleteV(&spisok); break;
		        case 4: return 0;
	        }
        }
}

void SearchV(dict* sp)
{
        char* input = new char[maxstrlen];
	cout << "Vvedite znachenie" << endl;
	cin >> input;
	link* value = sp->Find(input);
	if (value)
	{
		cout << "Element najden" << endl;
	}
	else
	{
		cout << "Element ne najden" << endl;
	}

}
void InsertV(dict* sp)
{
	char* input = new char[maxstrlen];
	cout << "Vvedite znachenie" << endl;
	cin >> input;
	sp->Insert(input);
	cout << "Element dobavlen" << endl;
}
void DeleteV(dict* sp)
{
	char* input = new char[maxstrlen];
	cout << "Vvedite znachenie" << endl;
	cin >> input;
	if (sp->Delete(input))
	{
		cout << "Element udalen" << endl;
	}
	else
	{
		cout << "Element ne najden" << endl;
	}
}
//---------------------------------------------------------------------------