Separa o código em diferentes arquivos

Ian Varejao · 20 de junho de 2015

Tenho 1 arquivo.c

Quero separar ele em 3 codigos fontes:

1 com a main

1 com a Arvore

1 com a Fila

#include <stdio.h>#include <stdlib.h>typedef struct NoA{	int elem;	struct NoA *esq,*dir,*pai;}NoA;typedef struct Arvore{	int N,H;	NoA *raiz;}Arvore;typedef struct NoF{	NoA* elem;	struct NoF *prox,*ant;}NoF;typedef struct Fila{	int Tamanho;	NoF *primeiro,*ultimo;}Fila;void ConstroiA(Arvore *);void DestroiA(Arvore *,NoA *);NoA* Busca(Arvore *,int );NoA* BuscaMenor(NoA *);void Insere(Arvore *,int);void Remove(Arvore *,int);void Enumera(Arvore *);void ConstroiF(Fila *);void DestroiF(Fila *);void Enfileira(Fila *, NoA *);NoA* Desenfileira(Fila *);//MAINint main(){	printf("Testando a Arvore!\n");	Arvore A;	ConstroiA(&A);	int i,N=3000;	Insere(&A,22);	for(i=1;i<=N;i++)		Insere(&A,i%2?i*2:i*3);	Enumera(&A);	for(i=1;i<=N;i++)		Remove(&A,i%2?i*2:i*3);	for(i=1;i<N;i++)		Insere(&A,i%2?i*2:i*3);	DestroiA(&A,A.raiz);	return 0;}//Funcoesvoid ConstroiA(Arvore *A){	A->N=A->H=0;	A->raiz=NULL;}void DestroiA(Arvore *A,NoA *{	if(B!=NULL){		DestroiA(A,B->esq);		DestroiA(A,B->dir);		free(;}}NoA* Busca(Arvore *A,int x){	NoA *pai,*prox=A->raiz;	if(prox == NULL){		printf("A arvore estÃ¡ vazia!\n");		return NULL;}	while(prox->elem != x){		pai=prox;				if(x > prox->elem)			prox=prox->dir;		else			prox=prox->esq;		if(prox == NULL)			return pai;}	return prox;}NoA* BuscaMenor(NoA *A){	while(A->esq!=NULL)		A=A->esq;	return A;}void Insere(Arvore *A,int x){	NoA *novo,*pai;	novo=(NoA *) malloc(sizeof(NoA));	novo->elem=x;	novo->esq=NULL;	novo->dir=NULL;	if(A->raiz == NULL){		A->raiz=novo;		novo->pai=NULL;		return;}	pai=Busca(A,x);	if(x > pai->elem)		pai->dir=novo;	else if(x < pai->elem)		pai->esq=novo;	else{		printf("%d ja esta na Arvore!\n",x);		return;}	novo->pai=pai;	A->N++;}void Remove(Arvore *A,int x){	//printf("%d\n",x);	NoA *r,*pai;	int f,isroot=0;	r=Busca(A,x);	if(r==NULL || r->elem != x)		return;	if(r->pai!=NULL){		pai=r->pai;		f=x>pai->elem;}	else		isroot=1;	if(r->esq == NULL && r->dir == NULL){//r nao tem filhos		if(isroot)			A->raiz=NULL;		else if(f)			pai->dir=NULL;		else{			pai->esq=NULL;}		free(r);}	else if(r->esq == NULL){//r tem 1 filho(dir)		if(isroot){				A->raiz=r->dir;				r->dir->pai=NULL;}		else{		if(f){			pai->dir=r->dir;			r->dir->pai=pai;}		else{			pai->esq=r->dir;			r->dir->pai=pai;}		free(r);}}	else if (r->dir == NULL){//r tem 1 filho(esq)		if(isroot){				A->raiz=r->esq;				r->esq->pai=NULL;}		else if(f){			pai->dir=r->esq;			r->esq->pai=pai->dir;}		else{			pai->esq=r->esq;			r->esq->pai=r->dir;}		free(r);}	else{//r tem 2 filhos(esq e dir)		pai=BuscaMenor(r->dir);//Busca pelo menor elemento na subarvore a direita de r		f=pai->elem;//coloca o elemento encontrado em f		Remove(A,f);//Remove f		r->elem=f;//Troca f pelo elemento em r, desse jeito a arvore mantem sua logica		return;}	A->N--;}//Enumera Em Niveisvoid Enumera(Arvore *A){		printf("Imprimindo Arvore em \"ArvoreSaida.txt\"!\n");		FILE *fp=fopen("ArvoreSaida.txt","w");        NoA *prox=A->raiz;        Fila F;        int i=1;        NoA *node=(NoA *) malloc(sizeof(NoA));        node->elem=0;        node->esq=node->dir=NULL;        ConstroiF(&F);        Enfileira(&F,prox);        Enfileira(&F,NULL);        fprintf(fp,"nivel %d: ",i++);        while(F.Tamanho){            prox=Desenfileira(&F);            if(prox==NULL){                if(F.primeiro->elem==F.primeiro->ant->elem)                	if(!F.Tamanho)                    	break;                fprintf(fp,"\nnivel %d: ",i++);                Enfileira(&F,NULL);}            else{                if(!prox->elem)                    fprintf(fp,"X ");                else{                fprintf(fp,"%d ",prox->elem);                if(prox->esq!=NULL)                    Enfileira(&F,prox->esq);                else                    Enfileira(&F,node);                if(prox->dir!=NULL)                    Enfileira(&F,prox->dir);                else                    Enfileira(&F,node);}}}        free(node);        fflush(fp);        fclose(fp);}//Fila	//Constroi	void ConstroiF(Fila *F){		F->Tamanho=0;		F->primeiro=F->ultimo=NULL;}	//Destroi	void DestroiF(Fila *F){		while(F->Tamanho--)			Desenfileira(F);}	//Enfileira	void Enfileira(Fila *F,NoA* x){		NoF *novo;		novo=(NoF *) malloc(sizeof(NoF));		novo->elem=x;		novo->ant=novo;		novo->prox=F->ultimo;		if(F->Tamanho){			F->ultimo->ant=novo;			F->ultimo=novo;}		else{			F->ultimo=novo;			F->primeiro=novo;}		F->Tamanho++;}				//Desenfileira	NoA* Desenfileira(Fila *F){		NoF *p;		NoA *x;		p=F->primeiro;		F->primeiro=p->ant;		x=p->elem;				free(p);		F->Tamanho--;		return x;}

Isis Binder · 22 de junho de 2015

Está meio confuso essa sua estrutura de dados. O que exatamente você precisa representar?

Ian Varejao · 22 de junho de 2015

Uma arvore binaria de busca, que usa fila para executar o percurso em niveis.

Isis Binder · 22 de junho de 2015

Usa fila p/ exibir os dados? você não quer dizer percurso em pré-ordem?
https://en.wikipedia.org/wiki/Tree_traversal#Pre-order

Se for isso não é necessário criar uma estrutura fila, a não ser que você queira armazenar a sequência do percurso. E mesmo nesse caso, a fila não se relaciona com a árvore.

Ian Varejao · 25 de junho de 2015

Usa fila p/ exibir os dados? você não quer dizer percurso em pré-ordem?

https://en.wikipedia.org/wiki/Tree_traversal#Pre-order

Se for isso não é necessário criar uma estrutura fila, a não ser que você queira armazenar a sequência do percurso. E mesmo nesse caso, a fila não se relaciona com a árvore.

Não, eu me refro ao percurso em niveis, onde voce percorre nivel por nivel, e visita os elementos na ordem em que aparecem no nivel, da esquerda pra direita.

Exemplo:

A

B C

D E F G

H I J K L M N O P

...

onde eu uso o No NULL para indicar que devo inserir '\n'.

Isis Binder · 25 de junho de 2015

arvore.h:

struct NoArvore{   int elem;   struct NoArvore *esq,*dir;};struct Arvore {   int niveis;   struct NoArvore * raiz;};void inserir(struct NoArvore * a_inserir, struct Arvore * arvore);void remover(struct NoArvore * a_remover, struct Arvore * arvore);void pesquisar(int elemento, struct Arvore * arvore);void percurso_em_nivel(struct Arvore * arvore);

Lista.h:

#ifndef _ARVORE_#define _ARVORE_#include "arvore.h"#endifstruct NoLista {   struct NoArvore * p; // Aqui será armazenado o endereço do elemento.   struct NoLista * proximo;};void lista_inserir(struct NoLista * a_inserir, struct NoLista * pai);void lista_remover(struct NoLista * a_remover);void lista_exibir(struct NoLista * origem);

No main você pode usar o mesmo truque das macros p/ evitar inclusão duplicada.

Note que você poderia meio que se livrar de incluir a lógica do armazenamento na lista na função percurso_em_nivel se passar um ponteiro p/ função (só dê uma olhada nos efeitos de se passar NULL pra esse tipo de coisa, porque não lembro se existe algum problema):

void percurso_em_nivel(struct Arvore * arvore, void (*store_traversal_function) (void *, void *)) {   // Lógica do percurso na árvore   // A cada nó visitado é possível executar a função store_traversall_function com   // store_traversal_function(no_visitado, lista)   // No seu caso, seria a função de inserção na lista.   if (store_traversal_function) {       struct NoLista * n = malloc(sizeof(struct NoLista));       // Verificação do retorno AQUI       store_traversal_function(n, lista);   }}

No main a chamada seria percurso_em_nivel(arvore, lista_inserir);

http://www.geeksforgeeks.org/level-order-tree-traversal/

Edit: falei lista, mas é fila.

Ian Varejao · 25 de junho de 2015

arvore.h:
struct NoArvore{   int elem;   struct NoArvore *esq,*dir;};struct Arvore {   int niveis;   struct NoArvore * raiz;};void inserir(struct NoArvore * a_inserir, struct Arvore * arvore);void remover(struct NoArvore * a_remover, struct Arvore * arvore);void pesquisar(int elemento, struct Arvore * arvore);void percurso_em_nivel(struct Arvore * arvore);
Lista.h:
#ifndef _ARVORE_#define _ARVORE_#include "arvore.h"#endifstruct NoLista {   struct NoArvore * p; // Aqui será armazenado o endereço do elemento.   struct NoLista * proximo;};void lista_inserir(struct NoLista * a_inserir, struct NoLista * pai);void lista_remover(struct NoLista * a_remover);void lista_exibir(struct NoLista * origem);
No main você pode usar o mesmo truque das macros p/ evitar inclusão duplicada.

Note que você poderia meio que se livrar de incluir a lógica do armazenamento na lista na função percurso_em_nivel se passar um ponteiro p/ função (só dê uma olhada nos efeitos de se passar NULL pra esse tipo de coisa, porque não lembro se existe algum problema):
void percurso_em_nivel(struct Arvore * arvore, void (*store_traversal_function) (void *, void *)) {   // Lógica do percurso na árvore   // A cada nó visitado é possível executar a função store_traversall_function com   // store_traversal_function(no_visitado, lista)   // No seu caso, seria a função de inserção na lista.   if (store_traversal_function) {       struct NoLista * n = malloc(sizeof(struct NoLista));       // Verificação do retorno AQUI       store_traversal_function(n, lista);   }}
No main a chamada seria percurso_em_nivel(arvore, lista_inserir);

http://www.geeksforgeeks.org/level-order-tree-traversal/

Edit: falei lista, mas é fila.

Sim, o professor mostrou na aula essa versao com ponteiro para ponteiro no lugar de ficar comparando toda hora se é maior ou menor.

Eu vou tentar desse seu jeito, porque do jeito que eu fiz o codigo funciona como esperado porém na compilaçao aparece aviso: e um erro estranho que nao faz o menor sentido.

Ian Varejao · 6 de setembro de 2015

Ok, depois de tanto tempo, o código já está muito melhor, porém continuo com a dúvida de o que colocar no arvore.h e o que colocar no fila.h.

O grande problema é que no arvore.h há funcoes de arvore que usam a estrutura de fila,e por isso o arvore.h deve conhecer a estrutura de fila, e a mesma coisa acontece para o fila.h, que usa a estrutura de arvores.

o que fazer quando dois header files possuem dependencia mutua?O unico jeito é juntar tudo num unico header file?

ps.: Desculpa ressucitar um topico antigo, mas tenho coisa a acrescentar e ainda tenho duvida.

arvore.h:

/**********************************Arvore Binaria de Busca com Fila**versao Recursiva                **arvore.h HEADER FILE            **********************************///Estrutura de Dados	typedef struct arvore	{		int elem;		int N;		struct arvore *esq,*dir;	}arvore;	typedef struct fila 	{ 		arvore* node; 		struct fila *prox; 	}fila;//Prototipos//Arvore //Funcoes essenciais  arvore* Cria(int);  void Destroi(arvore**); //Funcoes de Insercao  void Insere(arvore **,int);  void Preenche(arvore **,int,int); //Funcoes de Remocao  void Remove(arvore **,int); //Funcoes de Percurso  void PreOrdem(arvore*);  void EmNiveis(arvore*,fila**);  void fEmNiveis(FILE*,arvore*,fila**); //Funcoes de Busca  int Existe(arvore*,int);  int Menor(arvore*); //Outras Funcoes  void setN(arvore*);//Fila //Essenciais  fila* CriaFila(arvore*);  void DestroiFila(fila**); //Insercao  void Enfileira(fila**,arvore*); //Remocao  arvore* Desenfileira(fila**);  void ImprimeFila(fila*);

fila.h:

/**************************FILA PARA USO EM ARVORES**HEADER FILE             **************************///Estrutura de Dados typedef struct fila { 	arvore* node; 	struct fila *prox; }fila;//Prototipos das Funcoes //Essenciais  fila* CriaFila(arvore*);  void DestroiFila(fila**); //Insercao  void Enfileira(fila**,arvore*); //Remocao  arvore* Desenfileira(fila**);

arvore.c:

/*************************Arvore Binaria de Busca**versao Recursiva       **arvore.c SOURCE FILE   *************************///Headers#include <stdio.h>#include <stdlib.h>#include "arvore.h"//Funcoes essenciaisarvore* Cria(int x){    arvore *novo=(arvore*) malloc(sizeof(arvore));    novo->elem=x;    novo->N=1;    novo->esq=novo->dir=NULL;}void Destroi(arvore **p){    if(*p != NULL)    {        Destroi(&(*p)->esq);        Destroi(&(*p)->dir);        (*p)->esq=(*p)->dir=NULL;        free(*p);    }}//Funcoes de Insercaovoid Insere(arvore **A,int x){    arvore *p=(*A);    if(p!=NULL)    {    	if(p->elem > x)            Insere(&p->esq,x);        else if(p->elem < x)            Insere(&p->dir,x);        else            printf("Elemento já existente!\n");    }    else    {        p=Cria(x);        (*A)=p;    }}void Preenche(arvore **A,int x,int y){    if(x<y)    {        int meio= (x+y)/2;        Insere(A,meio);        Preenche(&(*A)->esq,x,meio);        Preenche(&(*A)->dir,meio+1,y);    }}//Funcoes de Remoçaovoid Remove(arvore **A,int x){	arvore *p=(*A);	if(p!=NULL)	{		if(p->elem != x)		{			if(p->elem > x)				Remove(&p->esq,x);			else				Remove(&p->dir,x);		}		else		{			if(p->esq == p->dir)			{				(*A)=NULL;				free(p);			}			else if(p->esq == NULL)			{				(*A)=p->dir;				free(p);			}			else if(p->dir == NULL)			{				(*A)=p->esq;				free(p);			}			else			{				int y=Menor(p->dir);				Remove(&p->dir,y);				p->elem=y;			}		}	}}			//Funcoes de Percursovoid PreOrdem(arvore *p){    if(p!=NULL)    {        printf("Elemento: %d \tTamanho: %d\n",p->elem,p->N);        PreOrdem(p->esq);        PreOrdem(p->dir);    }}void EmNiveis(arvore *p,fila **F){	if(p!=NULL)	{		if(*F==NULL)			Enfileira(F,NULL);		Enfileira(F,p->esq);		Enfileira(F,p->dir);		printf("%d ",p->elem);		p=Desenfileira(F);		if(p==NULL && *F!=NULL)		{			printf("\n");			p=Desenfileira(F);			Enfileira(F,NULL);		}		EmNiveis(p,F);	}}void fEmNiveis(FILE *fp,arvore *p,fila **F){	if(p!=NULL)	{		if(*F==NULL)			Enfileira(F,NULL);		Enfileira(F,p->esq);		Enfileira(F,p->dir);		fprintf(fp,"%d ",p->elem);		p=Desenfileira(F);		if(p==NULL && *F!=NULL)		{			fprintf(fp,"\n");			p=Desenfileira(F);			Enfileira(F,NULL);		}		fEmNiveis(fp,p,F);	}}		//Funcoes de Buscaint Existe(arvore *p,int x){    if(p!=NULL)    {        int y=p->elem;        if(y!=x)        {            if(y > x)                Existe(p->esq,x);            else                Existe(p->dir,x);        }        else            return 1;    }    else        return 0;}int Menor(arvore *p){	if(p!=NULL)	{		if(p->esq!=NULL)			Menor(p->esq);		else			return p->elem;	}}//Outras Funcoesvoid setN(arvore *p){	if(p!=NULL)	{		if(p->esq != NULL)		{			setN(p->esq);			p->N+=p->esq->N;		}		if(p->dir != NULL)		{			setN(p->dir);			p->N+=p->dir->N;		}	}}

fila.c:

/**************************FILA PARA USO EM ARVORES**SOURCE FILE             **************************///Header Files#include <stdio.h>#include <stdlib.h>#include "arvore.h"//Funcoes Essenciaisfila* CriaFila(arvore *A){	fila *novo= (fila*) malloc(sizeof(fila));	novo->prox=NULL;	novo->node=A;}void DestroiFila(fila **F){    if(*F!=NULL)    {        DestroiFila(&(*F)->prox);        free(*F);        (*F)=NULL;    }}//Funcoes de Insercaovoid Enfileira(fila **F,arvore *A){	if(*F!=NULL)	{		fila *novo=CriaFila(A);		novo->prox=(*F);		(*F)=novo;	}	else		(*F)=CriaFila(A);}//Funcoes de Remocaoarvore* Desenfileira(fila **F){	if(*F!=NULL)	{		if((*F)->prox!=NULL)			Desenfileira(&(*F)->prox);		else		{			arvore *A=(*F)->node;			free(*F);			(*F)=NULL;			return A;		}	}}//Funcoes de Percursovoid ImprimeFila(fila *F){	if(F!=NULL)	{		if(F->node != NULL)			printf("%d ",F->node->elem);		ImprimeFila(F->prox);	}	else		printf("\n");}