Cod sursa(job #1222179)

Utilizator somuBanil Ardej somu Data 22 august 2014 14:26:41
Problema Trie Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

#define nmax 101
ifstream in("dictree.in");
ofstream out("dictree.out");

typedef struct varf {
    struct varf *desc[52];
}VARF, *TRIE;

int N,Nod;
char C[nmax];
TRIE T;

void init(TRIE &T) {
    T = new VARF;
    for (int i=0; i<52; i++)
        T->desc[i] = NULL;
}

void adauga(TRIE &T, char C[], int p) {
    
    int ind;
    
    if (T == NULL)
        Nod++, init(T);
    
    if (C[p] == '\0')
        return;
    
    if (C[p] >= 'A' && C[p] <= 'Z')
        ind = int(C[p]-'A');
    else
        ind = int(C[p]-'A') - 6;
    
    if (T->desc[ind] != NULL)
        adauga(T->desc[ind], C, p+1);
    else {
        Nod++;
        init(T->desc[ind]);
        adauga(T->desc[ind], C, p+1);
    }
    
}

void sterge(TRIE &T) {
    
    int cnt;
    
    if (T == NULL)
        return;
    
    for (int i=0; i<52; i++)
        if (T->desc[i] != NULL){
            cnt++;
            break;
        }
    
    if (!cnt) {
        delete(T);
        T = NULL;
    } else {
        
        for (int i=0; i<52; i++)
            if (T->desc[i] != NULL)
                sterge(T->desc[i]);
        
        delete(T);
        T = NULL;
        
    }
}

int main() {
    
    in >> N;
    
    init(T);
    
    for (int i=1; i<=N; i++) {
        in >> C;
        adauga(T,C,0);
    }
    
    sterge(T);
    
    out << Nod + 1 << "\n";
    
    in.close();
    out.close();
    
    return 0;
}