Insert in Tree B with a large number C/C++

Question

I need to build a B Tree that reads the name of the files in a folder and sorts them. "Create a repository of images(100 images with 5 of each category-ex: trees, boat, dogs, houses, computers, flowers, cats, people, beach, plantaoes, etc.) Implement an arevoreB (t=4) with the following operations:

1. Insertion(insert an image that is already in the repository in a tree node, given the lexicographic order of the label)

2. Search(e.g. cat' returns all images with this label).

3. Print (prints all tree elements in order).

   4.Exclusion(exclude images related to a certain label).

My code for now works with vectors in which the numbers are small Ex: 5,10,7,9 but when I put numbers in the table ASCII Ex: 4239424 it hangs when entering the second :( I can’t figure out what happens

#include stdio.h
#include stdlib.h
#include dirent.h
#include string.h

#define M 2
#define MM (2 * M)

typedef int TChave;

int vetor[100];
char vetorEntrada[100][260];

typedef struct {
    TChave Chave;
    /* outros compomentes */
} TItem;

typedef int TIndice;

typedef struct SNo *TArvoreB;

typedef struct SNo {
    TItem Item[MM];
    TArvoreB Pagina[MM + 1];
    TIndice n;
} TNo;

/* Estrutura para passar pra cima */
typedef struct{
    TItem item;
    TArvoreB pagina;
} TInfo;

typedef TInfo* PInfo;

int EhInterno(TArvoreB No)
{
    return (No != NULL) && (No->Pagina[0] != NULL);
}

int EhExterno(TArvoreB No)
{
    return (No != NULL) && (No->Pagina[0] == NULL);
}

TArvoreB Inicializa()
{
    return NULL;
}

/* Inicializa um novo no com o elemento dado */
TArvoreB Empacotador(TItem x){
    TArvoreB pacote;

    pacote= (TArvoreB) malloc(sizeof(TNo));
    pacote->Item[0] = x;
    pacote->n = 1;

    return pacote;
}

void InsereNo(TArvoreB raiz, PInfo info, TIndice i);
void InsereNo2(TArvoreB raiz, PInfo info);

/* Divide uma pagina em duas */
void Divide(TArvoreB raiz, TItem x, TIndice indice, PInfo* info){
    TArvoreB novo;
    int i, j;

    novo = (TArvoreB) malloc(sizeof(TNo));
    (*info)->pagina = novo;
    novo->n = 0;

    /* Transfere metade das paginas/itens para o no novo */
    for(i=M, j=0; i<MM && j<M; i++, j++){

        /* Elementos para a nova pagina */
        novo->Item[j] = raiz->Item[i];
        novo->Pagina[j+1] = raiz->Pagina[i+1];

        /* Ajusta os contadores */
        novo->n++;
        raiz->n--;


    }

    /* Vamos inserir o novo item para decidir qual par promover */
    if(indice < M){
        InsereNo2(raiz, *info);

        /* Seleciona o item e coloca no lugar de promocao */
        (*info)->item = raiz->Item[raiz->n-1];
        raiz->n--;
    }
    else{
        InsereNo2(novo, *info);

        /* Seleciona o item para promocao */
        (*info)->item = novo->Item[0];

        /* Puxa todo mundo pra tras */
        novo->n--;
        for(i=0; i<=novo->n; i++){
            novo->Item[i] = novo->Item[i+1];
            novo->Pagina[i] = novo->Pagina[i+1];
        }

    }

    /* Ajusta o primeiro filho do novo no para o ultimo
     * do velho no */
    novo->Pagina[0] = raiz->Pagina[raiz->n];
}

/* Retorna o ponteiro para onde o no foi encontrado
 * ou NULL caso nao seja encontrado */
TArvoreB Pesquisa(TArvoreB Raiz, TChave x){
    int i;

    /* Se a arvore for nula */
    if(Raiz == NULL)
        return NULL;

    for(i=0; i<Raiz->n; i++){

        if(Raiz->Item[i].Chave == x)
            return Raiz;

        /* Se o elemento for menor do que o analisado */
        if(Raiz->Item[i].Chave > x)
            return Pesquisa(Raiz->Pagina[i], x);
    }

    /* Verificamos se o elemento pode estar na ultima pagina
     * Se chegar aqui, i = (*pRaiz)->n-1 */
    if(x > Raiz->Item[i].Chave && Raiz->Pagina[i+1] != NULL){
        return Pesquisa(Raiz->Pagina[Raiz->n], x);
    }

    /* Pesquisa sem sucesso */
    return NULL;
}

/* Insere quando nao sabemos o indice onde devemos inserir */
void InsereNo2(TArvoreB raiz, PInfo info){
    int j;

    for(j=0; j<raiz->n && raiz->Item[j].Chave < info->item.Chave; j++);

    /* Se o item ja estiver inserido */
    if(raiz->Item[j].Chave == info->item.Chave)
        return;

    /* Se tivermos achado o indice onde colocar */
    InsereNo(raiz, info, j);
}

/* Insere dentro de um no que tem espaco */
void InsereNo(TArvoreB raiz, PInfo info, TIndice i){
    int j;

    /* Desloca os necessarios elementos para frente */
    for(j=raiz->n; j>i; j--){
        raiz->Item[j] = raiz->Item[j-1];
        raiz->Pagina[j] = raiz->Pagina[j-1];
    }

    /* Aumenta o numero de itens neste no */
    raiz->n++;

    /* Insere o elemento na posicao liberada */
    raiz->Item[i] = info->item;
    raiz->Pagina[i] = info->pagina;
}

/* Insere com promocao */
int InsereRec(TArvoreB raiz, TItem x, PInfo* info){
    int i, j, k;

    /* Se atingiu a base da arvore */
    if(raiz == NULL){
        (*info) = (PInfo) malloc(sizeof(TInfo));
        (*info)->item = x;
        (*info)->pagina = NULL;
        return 1;
    }

    /* Acha a posicao onde deve inserir o elemento novo */
    for(i=0; i<raiz->n && raiz->Item[i].Chave < x.Chave; i++);

    /* Chegamos no ponto de pesquisa com sucesso */
    if(raiz->Item[i].Chave == x.Chave)
        return 0;


    /* Insere e ve se o nivel de baixo aumentou */
    if(InsereRec(raiz->Pagina[i], x, info)){

        /* Se houver espaco na pagina */
        if(raiz->n < MM){
            /* Insere neste no */
            InsereNo(raiz, *info, i);
            return 0;
        }
        else{
            /* Se a pagina estiver lotada, divida */
            Divide(raiz, x, i, info);
            return 1;
        }
    }
}

/* Insere na arvore */
void Insere(TArvoreB *pRaiz, TItem x){
    int i;
    TArvoreB aux;
    PInfo info = (PInfo) malloc(sizeof(TInfo));

    /* Se a arvore for nula */
    if(*pRaiz == NULL){
        *pRaiz = Empacotador(x);
    }
    else{
        /* Encontro o indice onde deveria inserir o item neste no */
        for(i=0; i<(*pRaiz)->n && (*pRaiz)->Item[i].Chave < x.Chave; i++);

        /* Se achamos um item igual */
        if((*pRaiz)->Item[i].Chave == x.Chave){
            return;
        }

        /* Seleciona a pagina onde deve ser feita a insercao */
        aux = (*pRaiz)->Pagina[i];

        /* Faz a insercao propriamente dita */
        if(InsereRec(aux, x, &info)){

            /* Se houver espaco na raiz */
            if((*pRaiz)->n < MM){
                InsereNo((*pRaiz), info, i);
            }

            /* Divide a raiz */
            else{
                aux = *pRaiz;

                /* Divide a raiz e acerta a galera que deve ser promovida */
                Divide((*pRaiz), x, i, &info);

                /* Recriamos a raiz */
                *pRaiz = Empacotador(info->item);
                (*pRaiz)->Pagina[0] = aux;
                (*pRaiz)->Pagina[1] = info->pagina;
            }
        }
    }
}

void Imprime(TArvoreB No)
{
    TIndice i;

    if (No != NULL) {
        printf("(");
        for (i = 0; i < No->n; i++) {
            Imprime(No->Pagina[i]);
            printf("C%s", No->Item[i].Chave);
        }
        Imprime(No->Pagina[No->n]);
        printf(")");
    }
    else
        printf("()");
}


void Carrega(TArvoreB *pNo,int n)
{
    int i;
    TItem x;

    for (i = 0; i < n ; i++)
    {
        printf("Leu dentro: ");
        x.Chave = (vetor[i]+1);
        printf("%s",vetor[i]+1);
        printf("--- %i\n",x.Chave);

        Insere(pNo, x);
        /*Imprime(*pNo);*/
    }
}

void Libera(TArvoreB *pNo)
{
    TArvoreB No;
    TIndice i;

    No = *pNo;
    if (No != NULL)
    {
        for (i = 0; i <= No->n; i++)
            Libera(&No->Pagina[i]);
        free(No);
        (*pNo) = NULL;
    }
}

int main()
{
    int tamChave = 0;
DIR *dir;
    struct dirent *ent;
    if ((dir = opendir("C:\\Users\\Laura\\Desktop\\Trabalho2-AED\\Repositorio")) != NULL)
    {
        /* print all the files and directories within directory */
        while ((ent = readdir (dir)) != NULL)
        {
            if(strcmp(ent->d_name,".") != 0 && strcmp(ent->d_name,"..") != 0)
            {
                strcpy(vetorEntrada[tamChave], ent->d_name);
                vetor[tamChave] = int(vetorEntrada[tamChave]);
                /*printf ("%s\n", ent->d_name);*/
                tamChave = tamChave + 1;
            }
        }
        closedir (dir);
    }
    else
    {
        /* could not open directory */
        perror ("");
        return EXIT_FAILURE;
    }

printf("Tamanho %i \n",tamChave);

    TArvoreB Raiz;
     TItem x;

     Raiz = Inicializa();
     Carrega(&Raiz,tamChave);
     Libera(&Raiz);

    return 0;
}

Answer 1

The problem with this code is that you don’t understand how strings work in C, and how they are represented in memory.

You can’t just do something like:

char *a = "teste"; 
int b = (int) a;

As I think is what you try to do in line:

vector[tamChave] = int(vector[tamChave])

Well, first of all, you can’t use int like the function syntax as you do above, this is a syntax error in C - but even if you cast as I indicated above, the value of "a" used for the conversion is not your content, but your memory address - which will have no relation to the word "test".

So we have other tips that come from your question, when you comment that "when I put ASCII table numbers Ex: 4239424 " - first, the ASCII table actually only has numbers from 0 up to 127. Two consecutive letters did not see a number for some formula using "the ASCII table" [*]. We’ve seen that trying to use C casting from string to number doesn’t work - still, if that’s all, it would be the case if you created a function that would generate a number that concatenates the values of each character of the string as a byte - so that a 4-letter word like "cat" would become a 4-byte sequence with the ASCII code of "g" in the first byte, and so on. This function would be relatively simple, but then we have TWO other problems for what you want to do: (1) Numbers in C are limited to the size of numbers the computer can use to work. You could even declare the numbers to be 64-bit "long int", but still be limited to 8-character strings (and this still does not take into account the text encoding). (2) the words "cat" and for example "kitten" would generate radically different numbers - all longer words would be larger numbers, and your tree would actually be ordered by the length of the strings (roughly) and not by their alphabetical order

The right way to do it: Store strigns as keys to your tree, not numbers. And in all tree comparison and insertion functions, instead of using operators that only work with numbers with <, >, == use string comparison functions: strncmp, for example.

Was it clear? To use a text tree, you use text keys, and text-compatible comparisons - no use trying to encode text as a number. (OK, there’s a way to do that, but they’d be a lot more sophisticated, and it’s just not worth it).

Now, from what I’ve seen above your program will have other problems as well - I don’t know if it is correct how to try to store the text in a fixed char matrix as you declare: char vetorEntrada[100][260]; why most C text functions expect a pointer to the beginning of the text, and in such an array, the content of vetorEntrada[0] is direct to the first letter of the first word (a byte) not a pointer to the word. If it is only this is achievable with the operator & - ie, you can pass the address of each text line to all functions that will handle strings (including printf, strncmp, strncpy, strnlen ) in form &(vetorEntrada[i]) (where "i" is the number in the table).

And finally, note that my recommendation is to always use the "n" variances of the C string functions - like strnlen instead of strlen - because versions without the "n" are inherently insecure, and can lead to any string being wrong-formed to generate an error in your program or even provide a buffer overflow invasion vector, if your code is running on a server, for example.