2

Preciso construir uma Arvore B que leia o nome dos arquivos em uma pasta e os ordene. "Criar um repositório de imagens(100 imagens com 5 de cada categoria–ex:árvores,barco,cachorros,casas,computadores,flores,gatos,pessoas,praia,plantaoes,etc.) Implementar uma árvoreB (t=4)com as seguintes operações:

  1. Inserção(inserir uma imagem que já esteja no repositório em um nó da árvore,dada a ordem lexicográfica do rótulo)

  2. Busca(ex.‘gato’ retorna todas as imagens com esse rótulo).

  3. Impressão (imprime todos os elementos da árvore em ordem).

    4.Exclusão(excluir imagens relacionadas a um certo rótulo).

Meu código por enquanto funciona com vetores em que os números são pequenos Ex: 5,10,7,9 mas quando coloco números da tabela ASCII Ex: 4239424 ele trava ao inserir o segundo :( Não consigo descobrir o que ocorre

#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;
}

1 Resposta 1

1

O problema com esse código é que você não entendeu como strings funcionam em C, e como elas são representadas na memória.

Você não pode simplesmente fazer algo como:

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

COmo acho que é o que você tenta fazer na linha:

vetor[tamChave] = int(vetorEntrada[tamChave])

Bom, primeiro, não dá para usar int como a sintaxe de função como você faz acima, isso é um erro de sintaxe em C - mas mesmo você fazendo o cast como eu indiquei acima, o valor de "a" usado para a conversão não é seu conteúdo, e sim, seu endereço de memória - que não vai ter nenhuma relação com a palavra "teste".

Daí temos outras dicas que vem da sua pergunta, quando você comenta que "quando coloco números da tabela ASCII Ex: 4239424 " - primeiro, a tabela ASCII na verdade só tem números de 0 até 127. Duas letras consecutivas não viram um número por alguma fórmula usando "a tabela ASCII" [*]. Já vimos que tentar usar o casting de C de string para número não funciona - ainda assim, se fosse só isso, seria o caso de você criar uma função que fizesse gerasse um número que concatenasse os valores de cada caractere da string como um byte - de forma que uma palavra de 4 letras como "gato" virasse uma sequência de 4 bytes com o código ASCII de "g" no primeiro byte, e assim por diante. Essa função seria relativamente simples, mas aí temos DOIS outros problemas para o que você quer fazer: (1) Números em C estão limitados ao tamanho de números que o computador consegue usar para trabalhar. Você até poderia declarar os números como "long int" de 64 bits, mas mesmo assim estaria limitada a strings de 8 caracteres (e isso ainda sem levar em conta a codificação do texto). (2) as palavras "gato" e, por exemplo "gatinho" gerariam números radicalmente diferentes - todas as palavras mais longas seriam números maiores, e sua árvore seria ordenada na verdade pelo comprimento das strings (a grosso modo) e não por sua ordem alfabética

A forma certa de fazer: Guarde strigns como chaves da sua árvore, não números. E em todas as funções de comparação e inserção da árvore, em vez de usar operadores que funcionam apenas com números com <, >, == use as funções de comparação de string: strncmp, por exemplo.

FIcou claro? Para usar uma árvore com texto, você usa chaves de texto, e comparações compatíveis com texto - nao adianta tentar codificar o texto como um número. (ok, há forma de fazer isso, mas seriam bem mais sofisticadas, e simplesmente não vale a pena).

Agora, pelo que vi por cima seu programa vai ter outros problemas também - não sei se está correta a forma de tentar armazenar o texto numa matriz fixa de char como você declara: char vetorEntrada[100][260]; por que a maior parte de funções de texto do C espera um ponteiro para o começo do texto, e em uma matriz dessas, o conteúdo de vetorEntrada[0] é direto a primeira letra da primeira palavra (um byte) não um ponteiro para a palavra. Se for só isso é contornável com o operador & - ou seja, você pode passar o endereço de cada liha de texto para todas as funções que vão manipular strings (incluindo printf, strncmp, strncpy, strnlen ) na forma &(vetorEntrada[i]) (onde "i" é o número na tabela).

E por fim, note que a minha recomendação é sempre usar as varições com "n" das funçoes de string de C, - como strnlen em vez de strlen - por que as versões sem o "n" são inerentemente inseguras, podendo levar qualquer string mal-formada a gerar um erro no seu programa ou mesmo propiciar um vetor de invasão por estouro de buffer, se o seu código estiver rodando em um servidor, por exemplo.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .