Haszowanie - Metoda Łańcuchowa

#include <iostream>
#include <cmath>
#include <fstream>

using namespace std;

class Elem {
private:
    string s;
    Elem* next;
    Elem* prev;
public:
    Elem();
    Elem(string s, Elem* next, Elem* prev);
    string GetString();
    Elem* GetNext();
    void SetNext(Elem* next);
    Elem* GetPrev();
    void SetPrev(Elem* prev);
};

Elem::Elem() {
    this->s = "";
    this->next = NULL;
    this->prev = NULL;
}

Elem::Elem(string s, Elem* next, Elem* prev) {
    this->s = s;
    this->next = next;
    this->prev = prev;
}

string Elem::GetString() {
    return this->s;
}

Elem* Elem::GetNext() {
    return this->next;
}

void Elem::SetNext(Elem* next) {
    this->next = next;
}

Elem* Elem::GetPrev() {
    return this->prev;
}

void Elem::SetPrev(Elem* prev) {
    this->prev = prev;
}

class DLList {
private:
    Elem* head;
public:
    DLList() { this->head = NULL; }
    void insertFirst(string s);
    void del(string s);
    string locate(string s); //zwraca pusty ciąg jeśli nie istnieje
    friend ostream& operator<<(ostream& out, DLList& l); //wypisuje całą listę
};

void DLList::insertFirst(string s) {
    if (head == NULL) {
        head = new Elem(s, NULL, NULL);
    }
    else {
        Elem* newElem = new Elem(s, head, NULL);
        head->SetPrev(newElem);
        head = newElem;
    }
}

void DLList::del(string s) {
    Elem* temp = head;

    if (temp == NULL) {
        return;
    }

    while (temp->GetString() != s) {
        temp = temp->GetNext();
        if (temp == NULL) {
            return;
        }
    }

    if (head == temp)
        head = head->GetNext();

    Elem* prev = temp->GetPrev();
    Elem* next = temp->GetNext();

    if(prev != NULL)
        prev->SetNext(next);
    if(next != NULL)
        next->SetPrev(prev);

    delete temp;
}

string DLList::locate(string s) {
    Elem* temp = head;

    if (temp == NULL) {
        return "";
    }

    while (temp->GetString() != s) {
        temp = temp->GetNext();
        if (temp == NULL) {
            return "";
        }
    }

    return temp->GetString();
}

ostream& operator<<(ostream& out, DLList& l) {
    Elem* temp = l.head;

    if (temp == NULL) {
        out << endl;
        return out;
    }

    while (temp != NULL) {
        out << temp->GetString() << " ";
        temp = temp->GetNext();
    }
    out << endl;
    return out;
}

class HashTable2 {
private:
    DLList* t;
    int capacity;
    int ht_size;
public:
    HashTable2(int c);      //konstruktor tworzący pustą tablicę o pojemności c
    int hashF(string s);        //funkcja haszująca dla ciągu s
    void insert(string s);      //wstawienie ciągu s
    void del(string s);
    string search(string s);    //wyszukuje i zwraca s
    friend ostream& operator<<(ostream& out, HashTable2& ht); //wypisuje tablicę (z numerami pól), pozostawia puste dla wolnych pól
};

HashTable2::HashTable2(int c) {
    t = new DLList[c];
    capacity = c;
    ht_size = 0;
}

int HashTable2::hashF(string s) {
    unsigned long int wynik = 0;

    for (size_t n = 0; n < s.size(); n++) {
        wynik += (unsigned)(s[n] * (int)pow(11, s.size() - n));
        wynik %= capacity;
    }

    return (int)wynik;
}

void HashTable2::insert(string s) {
    int h = hashF(s);

    t[h].insertFirst(s);
    ht_size++;
}

void HashTable2::del(string s) {
    int h = hashF(s);

    t[h].del(s);
    ht_size--;
}

string HashTable2::search(string s) {
    int h = hashF(s);

    return t[h].locate(s);
}

ostream& operator<<(ostream& out, HashTable2& ht) {
    if (ht.ht_size == 0) {
        return out;
    }
    else {
        for (int i = 0; i < ht.capacity; i++) {
            out << i << ": " << ht.t[i];
        }
    }
    out << endl;
    return out;
}

int main() {
    HashTable2 haszowanko(50);

    ifstream wejscie("dane.txt");
    string dane;

    if (wejscie.good()) {
        cout << "Plik dane.txt otwarty" << endl;
    }

    for (int i = 0; i < 40; i++) {
        wejscie >> dane;
        haszowanko.insert(dane);
    }

    cout << haszowanko << endl;

    haszowanko.del("Liliana");
    haszowanko.del("Igor");

    cout << haszowanko << endl;

    cout << "Search1: " << haszowanko.search("Jan") << endl;
    cout << "Search2: " << haszowanko.search("KEKW") << endl;


    return 0;
}