PortailAccueilFAQRechercherCalendrierS'enregistrerMembresGroupesConnexion

Partagez | 
 

 ALGORITHME MOVE TO FRONT (MTF)

Voir le sujet précédent Voir le sujet suivant Aller en bas 
AuteurMessage
Admin
Admin
avatar

Masculin
Nombre de messages : 138
Age : 30
Date d'inscription : 02/09/2006

MessageSujet: ALGORITHME MOVE TO FRONT (MTF)   Mer 13 Sep - 5:26

la mtf consite a transformer une chaine de caractere, avec des caracteres a répétitions
exemple:
la phrase suivante 'BCCCBB' a transformer.
a l'intialisation on a un tableau d'index[0..255] = [0]...[A][B][C][D]...[255]
- 1er carractere 'B', on ecrit la position de B en sortie et on fait une rotation des valeurs des index.
ainsi tableau d'index[0..255] = [b][0]...[A][C][D]...[255]
- 2nd carractere 'C', on ecrit la position de C, et rotation des index.
tableau d'index[0..255] = [C][B][0]...[A][D]...[255]
- 3em carractere 'C', ecrit la position de 'C' = 0.
- 4em carractere 'C', ecrit la position de 'C' = 0.
- 5em carractere 'B', ecrit la position de 'B' = 1, rotations des index
tableau d'index [0..255] = [B][C][0]...[A][D]...[255]
- 6em carractere 'B', ecrit la position de 'C' = 0.

Code:
le fichier definition.h
--------------------------------------------
#define BYTE unsigned char
 
 
le fichier mtf.h
--------------------------------------------
void mtf(BYTE *source, BYTE *destination, int sizesrc) {
  int i=0, index, pos;
  BYTE tab[256];
 
  for (index=0; index<256; index++) tab[index]=index; // initialisation du tableau d'index
 
  for (i=0; i<sizesrc; i++){ // parcourt du buffer source
      if (source[i]==tab[0]) { // la valeur courante est elle egale a l'index 0
          destination[i]=0; // oui ecrire 0
      } else { // sinon
          for(pos = 0; tab[pos] != source[i]; ++pos); // recherche du nouvelle l'index
          for(index=pos; index>0; index--) tab[index] = tab[index-1]; // index trouve rotation des index.
          tab[0] = source[i];
          destination[i] = pos; // ecriture de l'index trouvé.
      }
  }
}
 
le fichier imtf.h
--------------------------------------------
void imtf(BYTE *source, BYTE *destination, int sizesrc) {
  int i=0, index, pos;
  BYTE tmp, tab[256];
 
  for (index=0; index<256; index++) tab[index]=index; // initialisation du tableau d'index
 
  for (i=0; i<sizesrc; i++){ // parcourt du buffer a inverser.
      if (source[i]==0) { // si s'agit de la meme valeur originale
          destination[i]=tab[0]; // ecrire cette valeur
      } else { // sinon
          pos = tab[source[i]]; // recherche de la nouvelle valeur
          for(index=source[i]; index>0; index--) tab[index] = tab[index-1]; // rotation des index
          tab[0] = pos;
          destination[i] = pos; // ecrire cette valeur
      }
  }
}
 
le fichier main.c
--------------------------------------------
/* --------------------------- move to front ----------------------------- */
#include <stdio.h>
#include <stdlib.h>
#include "definition.h"
#include "mtf.h"
#include "imtf.h"
 
 
int main(int argc, char *argv[]){
  BYTE *phrase="AAACACCAABBBBBB";
  BYTE *dest;
  BYTE *ori;
   
  // préparation des buffers necessaire dest et ori
  dest = (BYTE *) malloc(strlen(phrase)*sizeof(BYTE)+1); dest[strlen(phrase)]=0x0;
  ori = (BYTE *) malloc(strlen(phrase)*sizeof(BYTE)+1); ori[strlen(phrase)] =0x0;
 
  // calcul de la mtf et son inverse
  mtf(phrase, dest, strlen(phrase));
  imtf(dest, ori, strlen(phrase));
   
  // affichage pour comparer
  printf("phrase '%s'\n", phrase);
  printf("imtf '%s'\n", ori);
 
  system("PAUSE");   
  return 0;
}
study study study study
Revenir en haut Aller en bas
Voir le profil de l'utilisateur http://design.jeun.fr
 
ALGORITHME MOVE TO FRONT (MTF)
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 1
 Sujets similaires
-
» Algorithme d'évolution progressive d'une variable
» algorithme de classement
» [Résolu] Pathfinding Algorithme A* - exemple exe gmk
» Highlanders
» Créé un installeur...pérféctionné !

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
DESIGN STUDIO FORUM :: programmation :: C,C++-
Sauter vers: