Projeto3ED (proposta)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define max 100

//Estrutura para armazenar o alfabeto para algoritmo e montar a arvore binaria
typedef struct arv{
    char c;
    int freq;
    int isleft;
    int codigo[10];
    struct arv *prox;
    struct arv *esq;
    struct arv *dir;
}Arv;
//Estrutura da tabela contendo as inforacoes dos cohdigos
typedef struct tabela{
    int codigo[20];
    char a;
}Tabela;
//cria uma lista de arvores com cabeça
Arv* cria_lst(){
    Arv* q = (Arv*)malloc(sizeof(Arv));
    q->c='\n';
    q->freq=max+1;
    q->esq = q->dir = NULL;
    q->prox = NULL;
    return q;
}
//insere as folhas na lista
Arv* lst_insereF(char a, int f, Arv* lis){
    Arv* t = (Arv*)malloc(sizeof(Arv));
    t->c = a;
    t->freq = f;
    t->prox = lis->prox;
    lis->prox = t;
    t->esq = t->dir = NULL;
    return lis;
}
//insere subarvores na lista
Arv* lst_insereA(Arv* a, Arv* lis){
    a->prox = lis->prox;
    lis->prox = a;
    return lis;
}
//imprime a arvore
void arv_imprime(Arv* a){
    if(!arv_vazia(a)){
        printf("(");
        printf("%c(%d)", a->c, a->isleft);

        if(a->esq==NULL)
            printf("()");
        if(a->dir==NULL)
            printf("()");
        arv_imprime(a->esq);


        arv_imprime(a->dir);
        printf(")");
    }
}
//cria uma subarvore correpondente a 'nao-folha'
Arv* cria_arv(Arv *sae,Arv *sad){
    Arv* q = (Arv*)malloc(sizeof(Arv));
    q->c = '*';
    q->freq = sae->freq + sad->freq;

    q->esq = sae;
    q->dir = sad;

    return q;
}
//verifica se a lista com cabeca esta vazia
int vazia(Arv *lis){
    return (lis->prox==NULL);
}
//retira o menor elemento da lista criada com cada celula sendo uma arvore
Arv* retira_menor(Arv* lis){
    Arv *q=lis->prox, *menor = lis->prox, *ant=NULL;

    while(q->prox!=NULL){//ponteiro 'menor' pecorre a lista das arvores primarias
        if(menor->freq>q->prox->freq){
            menor = q->prox;
            ant = q;
        }
        q=q->prox;
    }

    if(menor==lis->prox){

        lis->prox=lis->prox->prox;

        return menor;

    }

    ant->prox = menor->prox;
    menor->prox=NULL;
    return menor;

}
//conta a frequencia do caracter digitado pelo usuario
Arv* contafreq(char *m,char a,Arv *lis){
    int i, freq=0;
    if(a=='\n')
        return lis;
    for(i=0;i<=strlen(m);i++){
        if(m[i]==a){
            freq++;
            m[i]='\n';
        }
    }
    lis = lst_insereF(a,freq,lis);
    return lis;
}
//imprime a lista dos caracteres e suas respecitivas frequencias
void lst_imprime(Arv* lis){
    Arv *p;
    for(p = lis;p!=NULL; p=p->prox)
        printf("info = %c(%d)\n", p->c,p->freq) ;
}
//quantidade de sub arvores na lista de sub arvores
int Nos(Arv* lis){
    int i=0;
    while(lis!=NULL){
        i++;
        lis=lis->prox;
    }
    return i;
}
//insere no campo isleft caso a arvore sej colocada a direita ou a esqueda da subfolha
void Arv_left(Arv* A,Arv* sae, Arv *sad){
    if(A!=NULL&&A->esq!=NULL&&A->dir!=NULL){
        sae->isleft = 1;
        sad->isleft = 0;
        Arv_left(sae,sae->esq,sae->dir);
        Arv_left(sad,sad->esq,sad->dir);
    }
}
//estrutursa de uma lista
typedef struct lista{
    int cd;
    char a;
    struct lista *prox;
}Lista;

//imprime lista
void imprime(Lista* lis){
    while(lis!=NULL){
        printf("%c(%d) ", lis->a, lis->cd);
        lis = lis->prox;
    }
}
//herda o codigo da subarvore 'pai' para a subarvore 'filha'
void guardacodigo(Arv* v,Arv* sa,int n){
    int i;
    if(sa!=NULL){
        for(i=0;i<n;i++)
            sa->codigo[i] = v->codigo[i];
        sa->codigo[n] = sa->isleft;
        guardacodigo(sa,sa->esq,n+1);
        guardacodigo(sa,sa->dir,n+1);
    }
}

void criatabd(Tabela *tabd, Arv *v, int n){
    int i=0;
    if(v!=NULL){
        if(v->esq==NULL){
            while(v->codigo[i]==0||v->codigo[i]==1){
                tabd[n].codigo[i]=v->codigo[i];
                i++;
            }
            tabd[n].a = v->c;
            n++;

        }
        criatabd(tabd,v->dir,n);
    }
}

void criatabe(Tabela *tabe, Arv *v, int n){
    int i=0;
    if(v!=NULL){
        if(v->esq==NULL){
            while(v->codigo[i]==0||v->codigo[i]==1){
                tabe[n].codigo[i]=v->codigo[i];
                i++;
            }
            tabe[n].a = v->c;
            n++;

        }
        //system("pause");
        criatabe(tabe,v->esq,n);
    }
}
int main(){
    char mensagem[50];
    int i;
    Arv *lis =cria_lst(), *a;
    Tabela tabd[50], tabe[50];
    printf("Digite a mensagem: ");
    gets(mensagem);
    //conta a qte de caracter e usa a funcao para contar a frequencia dos caracteres
    for(i=0;i<strlen(mensagem);i++)
        lis = contafreq(mensagem,mensagem[i],lis);
    lst_imprime(lis);

    int j;
    for(i=0;i<50;i++){
        for(j=0;j<10;j++){
            tabe[i].codigo[j] = -5;
            tabd[i].codigo[j] = -5;
        }
    }
    while(Nos(lis->prox)>1){

        a = cria_arv(retira_menor(lis),retira_menor(lis));
        lis = lst_insereA(a,lis);
    }

    a = lis->prox;

    printf("\n\n\n");
    Arv_left(a,a->esq,a->dir);
    arv_imprime(a);
    guardacodigo(a->esq,a->esq,0);
    guardacodigo(a->esq,a->dir,0);
    criatabe(tabe,a->esq,0);
    criatabe(tabd,a->dir,0);
    i=0;

    while(tabd[0].codigo[i]==0||tabd[0].codigo[i]==1){
        printf("%d",tabd[0].codigo[i]);
        i++;
    }
    printf("\nCaracter: %c", tabd[0].a);

    //system("pause");
    return 0;
}