Arvore binária sem balanceamento [RESOLVIDO]

vstachetti
(usa Ubuntu)

Enviado em 14/12/2014 - 00:34h

Pessoal, tudo bem?

Preciso fazer um exercicio, mas não sei como termina-lo. Segue a descrição do problema:

Descrição:
Faça um programa que leia um texto qualquer (arquivo no formato texto) e imprima, em ordem
alfabética, todas palavras
com 3
ou mais caracteres
e a linha na qual elas aparecem no texto. Por
exemplo, para o texto:

Um exemplo de entrada:

Entrada:
Um, dois, tres, testando.
Testando tres vezes.
Um teste final.
FIM

A saida deve ser algo parecido com ...

dois 1
final 3
testando 1, 2
teste 3
tres 1, 2
vezes 2

A leitura do arquivo deverá desprezar espaços em branco e sinais de pontuação, que serão
considerados separadores de palavras. O fim da leitura acaba quando for encontrado a palavra FIM,
que não deve ser contabilizada. Além disso, a leitura deverá converter todas as letras maiúsculas em
minúsculas. Você pode considerar que cada palavra contém no máximo 30 letras e que não haverá
caracteres acentuados.

Isso foi o que eu fiz até agora:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 5000

typedef struct arv {
char info[MAX];
int linha;
struct arv *esq;
struct arv *dir;
} T_Arv;

//--------cria árvore vazia ----------//
void criaArvVazia(T_Arv **arv){
*arv =NULL;
}

//-------- insere elementos na árvore ----------/
/* Arvore binaria onde os nodos sao inseridos de maneira ordenada: */
/* - Os nodos a esquerda de um nodo pai sao sempre menores que ele */
/* - Os nodos a direita de um nodo pai sao sempre maiores que ele */
int insereArv(T_Arv **arv, char v[]){

if (*arv == NULL){
*arv = (T_Arv*)malloc (sizeof(T_Arv));
strcpy((*arv)->info,v);
(*arv)->esq = (*arv)->dir = NULL;
}else{
if (strcmp (v, (*arv)->info) <0){
insereArv (&((*arv)->esq), v);
}else{
insereArv (&((*arv)->dir), v);
}

}
return 0;
}


//ordem assimétrica
void imprimeAssimetrico(T_Arv *arv){
if (arv != NULL && strlen(arv->info)>3){
imprimeAssimetrico(arv->esq);
puts(arv->info);
//printf("%s \n", arv->info);
imprimeAssimetrico(arv->dir);
}
}

//----------Busca Nó ----------------//
T_Arv* buscaNoArvore(T_Arv *arv, char v[]){

if (arv == NULL){
return NULL;
}else{
if (strcmp (v, arv->info) < 0){
return buscaNoArvore(arv->esq, v);
}else{
if (strcmp (v, arv->info) > 0){
return buscaNoArvore(arv->dir, v);
}
}
return arv;
}

}


int main (){
T_Arv *arvore;
char cond[MAX];
criaArvVazia(&arvore);

return 0;

}


Alguem pode me dar uma luz? hahahah não sei continuar

paulo1205
(usa Ubuntu)

Enviado em 16/12/2014 - 14:00h

O código que você mostrou só tem estruturas e algoritmos básicos (que eu não conferi para ver se têm algum erro) referentes a uma árvore binária. Você ainda não implementou nenhuma das funções pedidas no enunciado.

Ninguém aqui vai implementar o programa por você. No entanto, vou lhe dar uma dica. Você especificou o nó da árvore do seguinte modo.

typedef struct arv {

  char info[MAX];

  int linha;

  struct arv *esq;

  struct arv *dir;

} T_Arv; 

Entendo que você vai colocar uma palavra lida em cada nó. Os índices de sua árvore será um dicionário das palavras lidas do arquivo.

Note porém o seguinte: o enunciado prescreve que cada palavra do dicionário tem de indicar todas as linhas em que ocorre no texto lido. Sua estrutura de nó, no entanto, só tem espaço para uma ocorrência. Com tal estrutura, você teria de indicar repetições da mesma palavra inserindo-a várias vezes no dicionário, uma vez para cada ocorrência. Acredite em mim quando eu digo que isso pode complicar um bocado sua vida.

Minha sugestão é que você substitua o valor único do campo linha por uma fila de valores inteiros (fila é um tipo de lista encadeada na qual novos valores são inseridos sempre no fim da lista e retirados da lista apenas a partir do seu início).

vstachetti
(usa Ubuntu)

Enviado em 16/12/2014 - 14:34h

Valeu a dica Paulo eu terminei esse problema já, mas mantive o int linha, ai ai eu pego a frase até o "." com o fgets, percorro, quando encontro o "\n" eu incremento essa linha, ai fico mais tranquilo fazer, sem contar os tratamentos de string em C pra não pegar caracteres especiais (que não lembro se coloquei aqui haha) mas achei um tutorial facinho na internet. Mesmo assim, muito obrigado pela ajuda.