Cod sursa(job #1343684)

Utilizator Corina1997Todoran Ana-Corina Corina1997 Data 15 februarie 2015 19:42:15
Problema Trie Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include <fstream>
#include <cstring>
#include <iostream>
using namespace std;

ifstream is("trie.in");
ofstream os("trie.out");

int x;
char a[25];

struct Node{
    Node()
    {
        nr_cuv = nr_son = 0;
        memset( son, 0, sizeof(son));
    }
    int nr_cuv, nr_son;
    Node* son[25];
};

Node* T = new Node;
void Insert( Node* node, char *s );
bool Delete( Node* node, char *s );
int NR( Node* node, char *s );
int Prefix( Node* node, char *s, int nr );

int main()
{
    while(is.getline(a, 25))
    {
        switch ( a[0] )
        {
            case '0': Insert( T, a + 2 ); break;
            case '1' : Delete( T, a + 2 ); break;
            case '2' : os << NR( T, a + 2 ) << '\n'; break;
            case '3' : os << Prefix( T, a + 2, 0 ) << '\n'; break;
            default : os << "Eroare\n"; break;
        }
    }
    is.close();
    os.close();
    return 0;
}

void Insert( Node* node, char *s )
{
    if ( *s == '\0' )
    {
        node->nr_cuv++;
        return;
    }
    if ( node->son[*s-'a'] == 0 )
    {
        node->son[*s-'a'] = new Node;
        node->nr_son++;
    }
    Insert( node->son[*s-'a'], s + 1 );
}

bool Delete( Node* node, char *s )
{
    if ( *s == '\0' )
        node->nr_cuv--;
    else
    {
        if ( Delete( node->son[*s-'a'], s+1 ) )
        {
            node->son[*s-'a'] = 0;
            node->nr_cuv--;
        }

    }
    if ( node->nr_cuv == 0 && node->nr_son == 0 && node != T)
    {
        delete node;
        return true;
    }
    return false;
}

int NR( Node* node, char *s )
{
    if ( *s == '\0' )
        return node->nr_cuv;
    if( node->son[*s-'a'] == 0 )
        return 0;
    else
        return NR( node->son[*s-'a'], s + 1);
}
int Prefix( Node* node, char *s, int nr )
{
    if( node->son[*s-'a'] == 0 )
        return nr;
    if ( *s == '\0' )
        return nr;
    Prefix( node->son[*s-'a'], s + 1, nr + 1 );
}