Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

#include<stdio.h> #include<stdlib.h> #include<string.h> /**********************

#include<stdio.h> #include<stdlib.h> #include<string.h> /**********************structure de la code**************************/ typedef struct codeL { int cd; struct code *suiv; }codeL; typedef struct codeL *coding; /**********************fin de la structure***************************/ /*********************structure de la liste**************************/ typedef struct elementTree { int nbr; coding code; char value; struct elementTree *left,*right; }elementTree; typedef struct elementTree *Tree; /****************fin de la structure de la liste*********************/ /*********************structure de la liste**************************/ typedef struct elementListe { Tree arbreListe; struct elementListe *next; }elementListe; typedef struct elementListe *lliste; /****************fin de la structure de la liste*********************/ /*******************Ecrire dans un fichier.txt***********************/ int writeInFile() { char c='0'; FILE* fiche=NULL; fiche=fopen("test.txt","w"); if(fiche!=NULL) { scanf("%c",&c); printf("entrer votre text:"); while(c!='#') { scanf("%c",&c); fputc(c,fiche); } fclose(fiche); return 1; } else { printf("erreur d'ouvrrire le fichier!"); return 0; } } /**********************fin de la fonction**************************/ /*******************lecture from fichier.txt***********************/ void readFromFile() { int val=0; FILE* fiche=NULL; fiche=fopen("test.txt","r"); if(fiche!=NULL) { do { val = fgetc(fiche); printf("%c", val); }while (val!= EOF); fclose(fiche); } else printf("erreur d'ouvrrire le fichier!"); } /*******************fin de la fonction ***********************/ /*******************creer element coding***********************/ coding creerElementCode(int nbr,coding nd) { coding nouv=malloc(sizeof(codeL)); nouv->cd=nbr; nouv->suiv=nd; return nouv; } /*******************fin de la fonction ***********************/ /**********************creer element d'un arbre****************************/ Tree creerElementTree(int nbr,int cod,char ch,Tree lef,Tree rig) { Tree nouv=malloc(sizeof(elementTree)); nouv->code=creerElementCode(cod,NULL); nouv->nbr=nbr; nouv->value=ch; nouv->left=lef; nouv->right=rig; return nouv; } /***********************fin de la fonction*********************************/ /**********************creer element d'un liste****************************/ lliste creerElementListe(Tree arb) { lliste nouv=malloc(sizeof(elementListe)); nouv->arbreListe=arb; nouv->next=NULL; return nouv; } /***********************fin de la fonction*********************************/ /*****************inseret les element de text dans un liste****************/ lliste insertElementAuListe(lliste liste,char ch,int nbr,Tree lef,Tree rig) { Tree arb=creerElementTree(nbr,3,ch,lef,rig); lliste lis=creerElementListe(arb); if(liste==NULL) return lis; else { lliste temp=liste; while(temp->next!=NULL) temp=temp->next; temp->next=lis; return liste; } } /***********************fin de la fonction*********************************/ /***********************existance d'un valeur******************************/ int existe(lliste listeBD,char val) { int n=0; while(listeBD!=NULL&&n==0) { if(listeBD->arbreListe->value==val) n=1; listeBD=listeBD->next; } return n; } /***********************fin de la fonction*********************************/ /**********************insertion sans double*******************************/ lliste insertListeBienDifini(lliste liste) { lliste listeBD=NULL; int n=0; if(liste==NULL) { printf("liste vide!"); return NULL; } else { while(liste!=NULL) { if(existe(listeBD,liste->arbreListe->value)==0) listeBD=insertElementAuListe(listeBD,liste->arbreListe->value,liste->arbreListe- >nbr, liste->arbreListe->left,liste->arbreListe->right); else { lliste temp=listeBD; while(temp!=NULL) { if(temp->arbreListe->value==liste->arbreListe->value) temp->arbreListe->nbr++; temp=temp->next; } } liste=liste->next; } return listeBD; } } /***********************fin de la fonction*********************************/ ; /************************* affiche liste **********************************/ void afficheListe(lliste liste) { while(liste!=NULL) { printf("char->%c ||nbr->%d ||code->not yet.\n",liste->arbreListe->value, liste->arbreListe->nbr); liste=liste->next; } } /***********************fin de la fonction*********************************/ /******************test si un arbre est feuille****************************/ int estFeuille(Tree arb) { return(arb->left==NULL&&arb->right==NULL)? 1:0; } /***********************fin de la fonction*********************************/ /**********************affiche coding liste********************************/ void afficheCoding(coding lis) { if(lis==NULL) printf("liste vide!\n"); else while(lis!=NULL) { printf("%d",lis->cd); lis=lis->suiv; } } /***********************fin de la fonction*********************************/ /************************afficher les feuille********************************/ void afficheFeuille(Tree arb) { if(arb!=NULL) { afficheFeuille(arb->left); if(estFeuille(arb)==1) { printf("char->%c ||nbr->%d ||code->",arb->value,arb->nbr); afficheCoding(arb->code); printf(".\n"); } afficheFeuille(arb->right); } } /***********************fin de la fonction*********************************/ /*********************affiche arbre huffman********************************/ void afficheTree(Tree arb) { if(arb!=NULL) { printf("char->%c ||nbr->%d ||code-> ",arb->value,arb->nbr); while(arb->code!=NULL) { printf("%d",arb->code->cd); arb->code=arb->code->suiv; } printf("\n"); afficheTree(arb->left); afficheTree(arb->right); } } /***********************fin de la fonction*********************************/ /*******************chercher le min de la liste****************************/ Tree searcheMinListe(lliste liste,int *pos) { int n=0; int min=liste->arbreListe->nbr; Tree tr=creerElementTree(liste->arbreListe->nbr,liste->arbreListe->code, liste->arbreListe->value, liste->arbreListe->left,liste->arbreListe->right ); while(liste!=NULL) { n++; if(liste->arbreListe->nbr<min) { *pos=n; min=liste->arbreListe->nbr; tr=creerElementTree(liste->arbreListe->nbr,liste->arbreL iste->code,liste->arbreListe->value, liste->arbreListe->left,liste->arbreListe->right ); } liste=liste->next; } return tr; } /***********************fin de la fonction*********************************/ /******************supprimer le min de la liste****************************/ lliste DeleteMinListe(lliste liste,int pos) { lliste listeS=NULL; int n=0; while(liste!=NULL) { n++; if(n!=pos) listeS=insertElementAuListe(listeS,liste->arbreListe->value,list e->arbreListe->nbr, liste->arbreListe->left,liste->arbreListe->right); liste=liste->next; } return listeS; } /***********************fin de la fonction*********************************/ /******************nombre des element de la liste**************************/ int nbrElement(lliste liste) { int n=0; while(liste!=NULL) { n++; liste=liste->next; } return n; } /***********************fin de la fonction*********************************/ /***********************concatination*********************************/ Tree concate(Tree min1,Tree min2) { Tree nouv=malloc(sizeof(elementTree)); nouv->code=creerElementCode(2,NULL); nouv->value='#'; nouv->nbr=min1->nbr+min2->nbr; nouv->left=min1; nouv->right=min2; return nouv; } /***********************fin de la fonction*********************************/ /************************Arbre de Huffman**********************************/ Tree HuffmanTree(lliste liste) { Tree min1,min2; int pos=1; lliste concat; while(nbrElement(liste)>1) { min1=searcheMinListe(liste,&pos); min1->code->cd=0; liste=DeleteMinListe(liste,pos); pos=1; min2=searcheMinListe(liste,&pos); min2->code->cd=1; liste=DeleteMinListe(liste,pos); pos=1; concat=NULL; concat=malloc(sizeof(elementListe)); concat->arbreListe=concate(min1,min2); concat->next=liste; liste=concat; } return liste->arbreListe; } /***********************fin de la fonction*********************************/ /***********************concate deux liste*********************************/ coding concateListe(coding fils,coding pere) { coding temp=pere; if(pere!=NULL) { while(temp->suiv!=NULL) temp=temp->suiv; temp->suiv=fils; return pere; } } /***********************fin de la fonction*********************************/ /****************inseret un element au debut d'un liste********************/ coding insertDebut(coding liste,int val) { coding nouv=malloc(sizeof(codeL)); nouv->cd=val; nouv->suiv=liste; return nouv; } /***********************fin de la fonction*********************************/ /************************inverse un liste**********************************/ coding inverse(coding cod) { coding nouv=NULL; while(cod!=NULL) { if(cod->cd!=2) nouv=insertDebut(nouv,cod->cd); cod=cod->suiv; } return nouv; } /***********************fin de la fonction*********************************/ /***********************reglage de l'arbre*********************************/ Tree Reglage(Tree arbre) { if(arbre!=NULL) { Reglage(arbre->left); arbre->code=inverse(arbre->code); Reglage(arbre->right); } return arbre; } /***********************fin de la fonction*********************************/ /************************codage dhuffman***********************************/ Tree codageHuffman(Tree arbre) { if(arbre!=NULL) { if(estFeuille(arbre)==0) { arbre->left->code=concateListe(arbre->code,arbre->left->code); arbre->right->code=concateListe(arbre->code,arbre->right->code); } codageHuffman(arbre->left); codageHuffman(arbre->right); } return arbre; } /***********************fin de la fonction*********************************/ /*************************inseret au fin***********************************/ coding insertFin(coding lis,int val) { coding nouv=malloc(sizeof(codeL)); nouv->cd=val; nouv->suiv=NULL; if(lis==NULL) return nouv; else { coding temp=lis; while(temp->suiv!=NULL) temp=temp->suiv; temp->suiv=nouv; return lis; } } /***********************fin de la fonction*********************************/ /***********************decodage de huffman********************************/ void decodageHuffman(Tree racine,coding liste) { Tree arbre=racine; if(liste==NULL) printf("liste vide"); else { while(liste!=NULL) { if(liste->cd==1) arbre=arbre->right; else if(liste->cd==0) arbre=arbre->left; if(estFeuille(arbre)==1) { printf("%c",arbre->value); arbre=racine; } else if(liste->suiv==NULL) printf(" code n'est pas complet!\n"); liste=liste->suiv; } } printf("\n\n"); } /***********************fin de la fonction*********************************/ /***********************fin de la fonction*********************************/ void nbrFeuilles(Tree treeHuff,int *nbr) { if(treeHuff!=NULL) { nbrFeuilles(treeHuff->left,nbr); if(estFeuille(treeHuff)==1) *nbr+=1; nbrFeuilles(treeHuff->right,nbr); } } /***********************fin de la fonction*********************************/ /************nombre de bit apré le codage de huffman***********************/ void nbrBitDeArbreHuffman(Tree arb,int *nbr) { if(arb!=NULL) { nbrBitDeArbreHuffman(arb->left,nbr); if(estFeuille(arb)==1) *nbr+=(arb->nbr*nbrElement(arb->code)); nbrBitDeArbreHuffman(arb->right,nbr); } } /***********************fin de la fonction*********************************/ /*********************combien ganier de bits*******************************/ void GanierBits(Tree treeHuff) { int nbr=0,nbrArb=0; nbrFeuilles(treeHuff,&nbr); printf("en a %d element se coder au cas normal sur %d*8=%d bit.\n",nbr,nbr,nbr*8 ); nbrBitDeArbreHuffman(treeHuff,&nbrArb); printf("en a les meme element ce coder avec le code de huffman sur %d bit.\n",nb rArb); printf("donc en a ganier %d - %d=%d bit.\n\n\n",nbr*8,nbrArb,nbr*8-nbrArb); } /****************************programme principale******************************* ***/ void main() { int res,nbr=1,cod=0,dc; char c,val; FILE* fiche=NULL; coding listeDecod=NULL; lliste listeBD=NULL,liste=NULL; Tree treeHuff=NULL,arb=NULL,minListe=NULL; /******************************codage de huffman******************************** ****/ printf("******************************debut de codage*************************** ***\n\n\n"); printf("entrer 'o' pour travaillez avec un nouvelle fichier text:"); scanf("%c",&c); if(c=='o') { printf("inseret des caracteres et pour finir inseret un '#':\n"); res=writeInFile(fiche); if(res==1) readFromFile(); else printf("erreur d'ecriture dans le fichier!\n"); } else printf("donc en utulise un fichier deja exist!\n"); fiche=fopen("test.txt","r"); if(fiche!=NULL) { val=fgetc(fiche); do{ liste=insertElementAuListe(liste,val,nbr,NULL,NULL); val=fgetc(fiche); }while(val!=EOF); fclose(fiche); } listeBD=insertListeBienDifini(liste); printf("\n\nla liste des element finale est:\n"); afficheListe(listeBD); printf("fin de la liste.\n\n\n"); if(listeBD!=NULL) { treeHuff=HuffmanTree(listeBD); treeHuff=codageHuffman(treeHuff); treeHuff=Reglage(treeHuff); printf("les feuilles de l'arbre de Huffman:\n"); afficheFeuille(treeHuff); printf("fin des feuilles.\n\n\n"); } printf("etude siplumentaire:\n"); GanierBits(treeHuff); printf("*******************************fin de codage**************************** ***\n\n\n"); /**************************fin de codage de huffman***************************** ***/ /*****************************decodage de huffman******************************* *****/ printf("******************************debut de decodage************************* *****\n\n\n"); printf("entrer 1 pour decoder des valeur selon l'arbre de huffman précidente:"); scanf("%d",&dc); if(dc==1) { printf("entrer un code qui composer par 1(un) et 0(zero) si la valeur et defirent ce termine le code:"); while(cod==0 || cod==1) { scanf("%d",&cod); if(cod==1||cod==0) listeDecod=insertFin(listeDecod,cod); } printf("les lettre qui composer avec le code precedent est:"); decodageHuffman(treeHuff,listeDecod); } else printf("donc comme vous voulez merci!\n"); printf("*******************************fin de decodage************************** *****\n\n\n"); /**************************fin de decodage de huffman*************************** *****/ } /************************fin de programme principale**************************** ***/ uploads/S4/ fin-de-projet2.pdf