Library of Gustavo

libofgustavo.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "libofgustavo.h"

// LISTAS

void lista_iniciar(Lista **p_Raiz){
    *p_Raiz = NULL;
}

int lista_inserirInicio (Lista **p_Raiz, char *p_String){
    Lista *p_Novo;
         /** Alocação dinâmica da memoria */
    p_Novo = (Lista *) malloc(sizeof(Lista));  
    if( p_Novo == NULL ){
        puts( "Falta Memoria\n");
        return -1 ;
    }
     
    p_Novo->info = p_String;
 
    p_Novo->prox = *p_Raiz;
    *p_Raiz = p_Novo;
}

int lista_inserirFim(Lista **p_Raiz, char *p_String){
    Lista *p_Novo; 
    Lista *e_atual;

    p_Novo = (Lista *) malloc(sizeof(Lista));
    if(p_Novo == NULL){
        puts("Falta Memoria\n");
        return -1 ;
    }
    p_Novo->info = p_String;
    p_Novo->prox = NULL;
    
    if(*p_Raiz == NULL)  //Lista vazia
        *p_Raiz = p_Novo;
    else{
        e_atual = *p_Raiz;   /*@ Primeiro elemento*/
        
        while(e_atual->prox != NULL){
            e_atual = e_atual->prox;
        }
        e_atual->prox = p_Novo;
    }
}

void lista_removerInicio(Lista **p_Raiz){
    if(*p_Raiz == NULL) printf("\nA lista ja esta vazia\n");
    else{
        Lista *p_atual;
        p_atual = *p_Raiz;
         
        *p_Raiz = (*p_Raiz)->prox;
        free(p_atual);
    }
}

void lista_removerFim(Lista **p_Raiz){
    if(*p_Raiz == NULL) printf("\nA lista ja esta vazia");
    else{
        Lista *p_atual, *p_anterior ;
        p_atual = *p_Raiz;
        while(p_atual->prox != NULL){
            p_anterior = p_atual ;
            p_atual    = p_atual->prox;
        }
        p_anterior->prox = NULL;
        free(p_atual);
    }
}

void lista_imprimeFimRaiz(Lista *p_Raiz){
    if(p_Raiz == NULL) printf("\nLista vazia");
    else{
        Lista *p_Atual_Corredor, *p_Atual_Fim;
        p_Atual_Corredor = p_Raiz;
        p_Atual_Fim = p_Raiz;
        while(p_Atual_Fim->prox != NULL){ //ir para o ultimo elemento
            p_Atual_Fim = p_Atual_Fim->prox;
        }
        while(p_Atual_Corredor != p_Atual_Fim){
            if(p_Atual_Corredor->prox == p_Atual_Fim){
                printf(" <- %s", p_Atual_Fim->info);
                p_Atual_Fim = p_Atual_Corredor;
                p_Atual_Corredor = p_Raiz;
            }
            else p_Atual_Corredor = p_Atual_Corredor->prox;
        }
        printf(" <- %s", p_Atual_Fim->info);
    }
}

void lista_imprimeRaizFim(Lista *p_Raiz){
    if(p_Raiz == NULL) printf("\nLista vazia");
    else{
        Lista *p_atual;
        p_atual = p_Raiz;
        while(p_atual != NULL){
            if (p_atual->prox == NULL){
                printf("%s ", p_atual->info);
            } else 
                printf("%s -> ", p_atual->info);
            p_atual = p_atual->prox;
                 
        }
    }
}
/*********************************************************************************/
// PILHAS FILO

void pilha_iniciar (Pilha *monte){
	monte->inicio = NULL;
	monte->tamanho = 0;
}

int push(Pilha** monte, char *info){ //inserir
	Lista *novo_elemento;
	if ((novo_elemento = (Lista *) malloc (sizeof (Lista))) == NULL)
		return -1;
	if ((novo_elemento->info = (char *) malloc (50 * sizeof (char))) == NULL)
		return -1;
	strcpy (novo_elemento->info, info);
	novo_elemento->prox = (*monte)->inicio;
	(*monte)->inicio = novo_elemento;
	(*monte)->tamanho++;
}

int pop(Pilha **monte){ //tirar
	Lista *p_elemento;
	if ((*monte)->tamanho == 0)
		return -1;
	p_elemento = (*monte)->inicio;
	(*monte)->inicio = (*monte)->inicio->prox;
	free (p_elemento->info);
	free (p_elemento);
	(*monte)->tamanho--;
	return 0;
}

void pilha_imprime(Pilha* monte){
	Lista *atual;
	int i;
	atual = monte->inicio;

	for(i=0;i<monte->tamanho;++i){
	    printf("\t\t%s\n", atual->info);
    	atual = atual->prox;
	}
}
/*********************************************************************************/
// FILAS FIFO

void fila_iniciar(Fila **f){
    *f = (Fila *) malloc(sizeof(Fila));
	(*f)->ini = (*f)->fim = NULL;
}

void fila_insere(Fila *f,char *v){
	Lista *n = (Lista *) malloc(sizeof(Lista));
    n->info = v;
	n->prox = NULL;
	if(f->fim != NULL) f->fim->prox = n;
	else f->ini = n;
	f->fim = n;
}

char *fila_retira(Fila *f){
	Lista *t;
	char *v;
	if(fila_vazia(f)){
		printf("Fila vazia!");
		exit(1);
    }
	t = f->ini;
	v = t->info;
	f->ini = t->prox;
	if(f->ini==NULL) f->fim = NULL;
	free(t);
	return v;
}

int fila_vazia(Fila *f){
    return (f->ini == NULL);
}

void fila_libera(Fila *f){
    Lista *q = f->ini;
    while(q!=NULL){
        Lista *t = q->prox;
        free(q);
        q = t;
    }
    free(f);
}

void fila_imprime(Fila *f){
    Lista *q;
    for(q=f->ini; q!= NULL; q=q->prox) printf("%s ",q->info);
}
/*********************************************************************************/
// ARVORES

void arvore_iniciar(No **pRaiz){
	*pRaiz = NULL;
}

int arvore_vazia(No *pRaiz){
	return (pRaiz == NULL);
}

void arvore_inserir(No **pRaiz, char info){
	if (*pRaiz == NULL){
		*pRaiz = (No *) malloc (sizeof(No));
		(*pRaiz)->esquerda = NULL;
		(*pRaiz)->direita = NULL;
		(*pRaiz)->info = info;
	} else {
		if (info <= (*pRaiz)->info)
			arvore_inserir(&(*pRaiz)->esquerda, info);
		if (info >  (*pRaiz)->info)
			arvore_inserir(&(*pRaiz)->direita, info);
	}
}

No *MaiorDireita(No **no){
    if((*no)->direita != NULL) 
       return MaiorDireita(&(*no)->direita);
    else{
       No *aux = *no;
       if((*no)->esquerda != NULL) // se nao houver essa verificacao, esse nó vai perder todos os seus filhos da esquerda!
          *no = (*no)->esquerda;
       else
          *no = NULL;
       return aux;
       }
}

No *MenorEsquerda(No **no){
    if((*no)->esquerda != NULL) 
       return MenorEsquerda(&(*no)->esquerda);
    else{
       No *aux = *no; 
       if((*no)->direita != NULL) // se nao houver essa verificacao, esse nó vai perder todos os seus filhos da direita!
          *no = (*no)->direita;
       else
          *no = NULL;
       return aux;
       }
}

void arvore_remover(No **pRaiz, char info){
	if(*pRaiz == NULL){   // esta verificacao serve para caso o info nao exista na arvore.
		printf("info nao existe na arvore!");
		return;
	}
	if(info < (*pRaiz)->info)
		arvore_remover(&(*pRaiz)->esquerda, info);
	else 
		if(info > (*pRaiz)->info)
			arvore_remover(&(*pRaiz)->direita, info);
		else {    // se nao eh menor nem maior, logo, eh o info que estou procurando! :)
			No *pAux = *pRaiz;    
			if (((*pRaiz)->esquerda == NULL) && ((*pRaiz)->direita == NULL)){         // se nao houver filhos...
				free(pAux);
				(*pRaiz) = NULL; }
			else {     // so tem o filho da direita
				if ((*pRaiz)->esquerda == NULL){
					(*pRaiz) = (*pRaiz)->direita;
					pAux->direita = NULL;
					free(pAux); pAux = NULL;
				} else {            //so tem filho da esquerda
					if ((*pRaiz)->direita == NULL){
						(*pRaiz) = (*pRaiz)->esquerda;
						pAux->esquerda = NULL;
						free(pAux); pAux = NULL;
					} else {       //Escolhi fazer o maior filho direito da subarvore esquerda.
						pAux = MaiorDireita(&(*pRaiz)->esquerda); 
						pAux->esquerda = (*pRaiz)->esquerda;      
						pAux->direita = (*pRaiz)->direita;
						(*pRaiz)->esquerda = (*pRaiz)->direita = NULL;
						free((*pRaiz));  *pRaiz = pAux;  pAux = NULL;   
					}
				}
			}
		}
}

void exibirEmOrdem(No *pRaiz){
    if(pRaiz != NULL){
        exibirEmOrdem(pRaiz->esquerda);
        printf("%c ", pRaiz->info);
        exibirEmOrdem(pRaiz->direita);
    }
}

void exibirPreOrdem(No *pRaiz){
    if(pRaiz != NULL){
        printf("%c ", pRaiz->info);
        exibirPreOrdem(pRaiz->esquerda);
        exibirPreOrdem(pRaiz->direita);
    }
}

void exibirPosOrdem(No *pRaiz){
    if(pRaiz != NULL){
        exibirPosOrdem(pRaiz->esquerda);
        exibirPosOrdem(pRaiz->direita);
        printf("%c ", pRaiz->info);
    }
}

void arvoreParaLista(No *pRaiz, Lista **lista){
    if(pRaiz != NULL){
        char string[2];
        string[0] = pRaiz->info;
        string[1] = '\0';
        arvoreParaLista(pRaiz->esquerda, lista);
        arvoreParaLista(pRaiz->direita, lista);
        inserir(lista, string);
    }
}

int contarNos(No *pRaiz){
	if (pRaiz == NULL)
		return 0;
	if (pRaiz->direita == NULL && pRaiz->esquerda == NULL)
		return 1;
	return 1 + contarNos(pRaiz->esquerda) + contarNos(pRaiz->direita);
}

int contarFolhas(No *pRaiz){
	if (pRaiz == NULL)
		return 0;
	if (pRaiz->direita == NULL && pRaiz->esquerda == NULL)
		return 1;
	return contarFolhas(pRaiz->esquerda) + contarFolhas(pRaiz->direita);
}

void contarTN(No *pRaiz, int *folhas, int *noUmFilho, int *noDoisFilhos){ //contar tipos de nos
	if (!arvore_vazia(pRaiz)){
		if (pRaiz->direita == NULL && pRaiz->esquerda == NULL) ++(*folhas);
		if (pRaiz->direita != NULL && pRaiz->esquerda != NULL) ++(*noDoisFilhos);
		if ((pRaiz->direita == NULL && pRaiz->esquerda != NULL) || (pRaiz->direita != NULL && pRaiz->esquerda == NULL)) ++(*noUmFilho);
		contarTN(pRaiz->esquerda, folhas, noUmFilho, noDoisFilhos);
		contarTN(pRaiz->direita, folhas, noUmFilho, noDoisFilhos);
	}
}
static int maior(int a, int b){
	return (a>b)?a:b;
}

int altura(No *pRaiz){
	if((pRaiz == NULL) || (pRaiz->esquerda == NULL && pRaiz->direita == NULL))
		return 0;
	else
		return 1 + maior(altura(pRaiz->esquerda), altura(pRaiz->direita));
}

libofgustavo.h

/* DOCUMENTAÇÃO libofgustavo.h
 * para iniciar qualquer estrutura de dados, só usar a função iniciar();
 * a função inserir() tbm funciona para qualquer EDs, na lista ela insere no final
 * remover(); funciona para filas e pilhas
 * imprimir(); funciona para todas
 */


// LISTAS
struct lista{
    char *info;
    struct lista *prox;
};
typedef struct lista Lista;

void lista_iniciar(Lista **p_Raiz);
int lista_inserirInicio (Lista **p_Raiz, char *p_String);
int lista_inserirFim(Lista **p_Raiz, char *p_String);
void lista_removerInicio(Lista **p_Raiz);
void lista_removerFim(Lista **p_Raiz);
void lista_imprimeFimRaiz(Lista *p_Raiz);
void lista_imprimeRaizFim(Lista *p_Raiz);

/*********************************************************************************/
// PILHAS
struct pilha{
	Lista *inicio;
	int tamanho;
};
typedef struct pilha Pilha;

void pilha_iniciar (Pilha *monte);
int push(Pilha** monte, char *info);
int pop(Pilha** monte);
void pilha_imprime(Pilha* monte);

/*********************************************************************************/
//FILAS
struct fila{
    Lista *ini;
    Lista *fim;
};
typedef struct fila Fila;

void fila_iniciar(Fila **f);
void fila_insere(Fila *f, char *v);
char *fila_retira(Fila *f);
int fila_vazia(Fila *f);
void fila_libera(Fila *f);
void fila_imprime(Fila *f);

/*********************************************************************************/
// ARVORES
struct No {
	char info;
	struct No *esquerda;
	struct No *direita;
};
typedef struct No No;

void arvore_iniciar(No **pRaiz); //**
void arvore_inserir(No **pRaiz, char info); //**
No *MaiorDireita(No **no);
No *MenorEsquerda(No **no);
void arvore_remover(No **pRaiz, char info); //**
void exibirEmOrdem(No *pRaiz);
void exibirPreOrdem(No *pRaiz);
void exibirPosOrdem(No *pRaiz);
int contarNos(No *pRaiz);  //**
int contarFolhas(No *pRaiz);
void contarTN(No *pRaiz, int *folhas, int *noUmFilho, int *noDoisFilhos); //contar tipos de nos
static int maior(int a, int b);
int altura(No *pRaiz);  //**
/*********************************************************************************/

void arvoreParaLista(No *pRaiz, Lista **lista);

#define iniciar(a) _Generic(a, Lista **: lista_iniciar, Pilha *: pilha_iniciar, Fila **: fila_iniciar, No **: arvore_iniciar)(a)
#define inserir(a, b) _Generic(a, Lista **: lista_inserirFim, Pilha **: push, Fila *: fila_insere, No **: arvore_inserir)(a, b)
#define remover(a) _Generic(a, Pilha **: pop, Fila *: fila_retira)(a)
#define imprime(a) _Generic(a, Lista *: lista_imprimeRaizFim, Pilha *: pilha_imprime, Fila *: fila_imprime)(a)