Lista duplamente encadeada utilizando técnica de Hashing.

This message was edited 1 time. Last update was at 13/05/2008 15:01:20

Mais um codigo interresante que pode auxiliar os futuros programadores e futuros loucos de informatica:

Lista duplamente encadeada utilizando técnica de Hashing:

#include <iostream>

using namespace std;

class node {
    private : int info;
    public  : node *previous, *next;
              node ();
              node (int);
              int getValue ();
};

node :: node () {
    this->previous = this->next = NULL;
}

node :: node (int info) {
    this->info = info;
    this->previous = this->next = NULL;
}

int node :: getValue () {
    return info;
}

class list {
    private : node *start;
    public  : list ();
              void insert (int);
              int  search (int, int);
              void remove (int);
              void show ();
              ~list ();
              
};

list :: list () {
    start = NULL;
}

void list :: insert (int info) {
    node *temp_start = this->start;
    node *temp_node;
    
    if (!temp_start) {
        temp_node = new node (info);
        this->start = temp_node;
    }
    else {
        while (temp_start->next)
            temp_start = temp_start->next;
        
        temp_node = new node (info);
        temp_start->next = temp_node;
        temp_node->previous = temp_start;
    }    
}

int list :: search (int info, int ign) {
    node *temp_start = this->start;
    int position = 0;
    int oc = 0;
    
    while (temp_start) {
        if (temp_start->getValue() == info) {
            ++oc;
            
            if (oc >= ign)
                break;
        }
        
        temp_start = temp_start->next;
        ++position;
    }
    
    if (temp_start) 
        return position;
    
    return -1;
}

void list :: remove (int info) {
    node *temp_start = this->start;
    
    if (temp_start) {
        if (temp_start->getValue() == info) {
            this->start = this->start->next;
            this->start->previous = NULL;
        }
        else {
            while (temp_start) {
                if (temp_start->getValue() == info)
                    break;
        
                 temp_start = temp_start->next;
            }
    
            if (temp_start) { 
                if (temp_start->next) {
                    temp_start->previous->next = temp_start->next;
                    temp_start->next->previous = temp_start->previous;
                }
                else
                    temp_start->previous->next = NULL;
            }
            else 
                cout << endl << "this value doesn't exist !" << endl;
        }
        delete temp_start;
    }
    else
        cout << "the list is empty !";
}

void list :: show () {
    node *temp_start = this->start;
    
    while (temp_start) {
        cout << temp_start->getValue() << " ";
        temp_start = temp_start->next;
    }
}

list :: ~list () {
    node *temp_start;
    
    while (this->start) {
        temp_start = this->start;
        this->start = this->start->next;
        delete temp_start;
    }
    
    delete this->start;
}

class hash {
    private : char **info;
              int length, quantify;
              list *index;
              int key (char *);
    public  : hash (int);
              void hashing (char *);
              void search (char *);
              ~hash ();
};

hash :: hash (int length) {
    this->length = length;
    this->quantify = 0;
    info = new char* [this->length];
    index = new list ();
}

void hash :: hashing (char *info) {
    this->info[this->quantify] = new char [strlen (info)];
    strcpy (this->info[this->quantify], info);
    this->index->insert(key(this->info[this->quantify++]));
}

int hash :: key (char *info) {
    char *tmp_info = info;
    int value = 0;
    
    for (int i = 0; i < strlen(info); ++i) {
        value += info[i];
    }    
    value = value % 17;
    
    return value;
}

void hash :: search(char *info) {
    int vkey = this->key(info);
    int oc = 1, position;
    
    while ((position = this->index->search(vkey, oc)) != -1) {
        if (strcmp(info, this->info[position]) == 0) {
            cout << "found it !" << endl;
            break;
        }
        else
            ++oc;
    }
    
    if (position == -1)
        cout << "not found" << endl;    
}

hash :: ~hash () {
    for (int i = 0; i < this->length; ++i)
        delete [] this->info[i];
    
    this->length = 0;
    delete index;
}

int main () {
    hash *h = new hash (10);
    h->hashing("teste12");
    h->hashing("abc");
    h->hashing("sfsdfsdf");
    
    h->search("456");
    h->search("abc");
   
    delete h;
    
    return 0;
}

Lembrando que este código não foi desenvolvido por mim!

Espero ter ajudado!

Falowsss

Moderador Membro desde: 29/07/2004 16:10:13 Mensagens: 17543 Offline

Na próxima versão do C++ (também conhecida por C++0X), estarão disponíveis um template para hash maps e hash tables chamado unordered_set<> e unordered_map<>.
Por enquanto, você pode usar o "TR1" ou o Boost.

Blz valeu pelas dicas!

Notícias, artigos e o maior fórum brasileiro sobre Java