begin process at 2012 02 12 10:29:24
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths & Algorithmes

 > [C ANSI] TAS (PRIORITY QUEUE)

[C ANSI] TAS (PRIORITY QUEUE)


 Information sur la source

Note :
Aucune note
Catégorie :Maths & Algorithmes Classé sous :tas, priority, queue, file, priorite Niveau :Initié Date de création :06/11/2008 Date de mise à jour :07/11/2008 04:01:53 Vu :3 086
Auteur : coucou747

Ecrire un message privé
Site perso
Ce membre participe au partage de revenus publicitaires
Commentaire sur cette source (3)
Ajouter un commentaire et/ou une note

 Description

On voit souvent ici des "programmes" qui mettent en oeuvre uniquement une liste chainee, ou une liste doublement chainee. Ici, je vous propose une structure particuliere d'arbre binaire complet ordonnee de la facon suivante :

chaque pere a une valeur plus elevee que ses deux enfants.
si il manque des enfants, c'est forcement "en bas a droite".
toutes les branches ont la meme hauteur (sauf eventuellement, tout en bas a droite)

sur une telle structure, on s'appercoit que si on les numerote :

                0
        1               2
    3       4       5       6
  7   8   9  10  11  12  13  14

alors si un pere est numerote : i, ses enfants sont : 2i et 2i+1

a partir de la, on peut faire une structure de tableau, et on evite ainsi le triple chainage (et on y gagne un random acces, meme si avant l'acces etait logarithmique, c'est toujours mieux.)

Bref, sur cette structure, on peut ajouter des elements, supprimer des elements (de preference, on supprime celui du dessus) en O(log(n)).
sur une liste non triee, on aurait l'insertion en O(1) et la suppression (ainsi que la recherche) du plus grand element en O(n)
sur une liste triee, c'est l'insertion qui serait en O(n), la suppression et la recherche du plus grand element serait en O(1)

c'est donc une bonne structure pour une file de priorites (priority queue), meme si elle ne permet pas le "merge" de deux tas en O(log(n)) mais seulement en O(n).


certaines fonctions sont plutot la pour la decoration (to_2_exp, ln2, spaces servent uniquement pour pouvoir faire draw_tas)

mon exemple est avec une file d'int, mais on peut l'adapter pour n'importe quel type, voir carement en faire une classe Cpp avec des templates.

il existe une methode de tri qui se base sur l'insertion dans une liste comme ceci, ca fait un tres bon tri en O(n log(n)), a peu pres entre le merge sort et le quick sort.

Source

  • #include <stdio.h>
  • #include <stdlib.h>
  • void swap(int *v1, int *v2){
  • int v3 = *v1;
  • *v1 = *v2;
  • *v2 = v3;
  • }
  • int to_2_exp(int i){
  • if (i==0) return 0;
  • if (i==1) return 1;
  • return 2 * to_2_exp( i / 2);
  • }
  • int ln2(int i){
  • if (i==0) return 0;
  • if (i==1) return 1;
  • return 1 + to_2_exp( i / 2);
  • }
  • void spaces(int n){
  • int i;
  • for (i=0; i<n; i++) putchar(' ');
  • }
  • typedef int * tas;
  • tas new_tas(size_t s){
  • return malloc(s * sizeof(int));
  • }
  • void fixup(tas t, size_t n){
  • if (n == 0) return;
  • else{
  • int n2 = (n-1)/2;
  • if (t[n] > t[n2]){
  • swap(&t[n], &t[n2]);
  • fixup(t, n2);
  • }
  • }
  • }
  • void fixdown(tas t, size_t n, size_t max){
  • int n2 = n*2+1;
  • if (n2 >= max) return;
  • if (n2 + 1 < max && t[n2+1] > t[n2] ) n2++;
  • if (t[n] < t[n2]){
  • swap(&t[n], &t[n2]);
  • fixdown(t, n2, max);
  • }
  • }
  • void draw_tas(tas t, size_t n){
  • int i;
  • int k = 1;
  • int k_max = to_2_exp(n);
  • int v;
  • for (i=0; i<n; i++){
  • if (i == k - 1){
  • k *= 2;
  • if (i) putchar('\n');
  • v = 2* (k_max * 2 / k ) - 1;
  • spaces(v);
  • }
  • printf("%2d", t[i]);
  • spaces(2 * v);
  • }
  • putchar('\n');
  • }
  • size_t add_tas(tas t, int value, size_t n){
  • t[n] = value;
  • fixup(t, n);
  • return n+1;
  • }
  • size_t pop_tas(tas t, size_t n){
  • t[0] = t[--n];
  • fixdown(t, 0, n);
  • return n;
  • }
  • int main(){
  • /* exemple d'utilisation d'un tas */
  • int s = 0;
  • tas t = new_tas(15);
  • add_tas(t, 12, s++);
  • add_tas(t, 24, s++);
  • add_tas(t, 48, s++);
  • add_tas(t, 15, s++);
  • add_tas(t, 23, s++);
  • add_tas(t, 49, s++);
  • add_tas(t, 19, s++);
  • add_tas(t, 54, s++);
  • add_tas(t, 29, s++);
  • add_tas(t, 18, s++);
  • add_tas(t, 53, s++);
  • add_tas(t, 92, s++);
  • add_tas(t, 90, s++);
  • add_tas(t, 64, s++);
  • add_tas(t, 22, s++);
  • draw_tas(t, s);
  • s = pop_tas(t, s);
  • s = pop_tas(t, s);
  • draw_tas(t, s);
  • free(t);
  • return 0;
  • } 
#include <stdio.h>
#include <stdlib.h>

void swap(int *v1, int *v2){
  int v3 = *v1;
  *v1 = *v2;
  *v2 = v3;
}

int to_2_exp(int i){
  if (i==0) return 0;
  if (i==1) return 1;
  return 2 * to_2_exp( i / 2);
}

int ln2(int i){
  if (i==0) return 0;
  if (i==1) return 1;
  return 1 + to_2_exp( i / 2);
}

void spaces(int n){
  int i;
  for (i=0; i<n; i++) putchar(' ');
}

typedef int * tas;

tas new_tas(size_t s){
  return malloc(s * sizeof(int));
}

void fixup(tas t, size_t n){
  if (n == 0) return;
  else{
    int n2 = (n-1)/2;
    if (t[n] > t[n2]){
      swap(&t[n], &t[n2]);
      fixup(t, n2);
    }
  }
}

void fixdown(tas t, size_t n, size_t max){
  int n2 = n*2+1;
  if (n2 >= max) return;
  if (n2 + 1 < max && t[n2+1] > t[n2] ) n2++;
  if (t[n] < t[n2]){
    swap(&t[n], &t[n2]);
    fixdown(t, n2, max);
  }
}

void draw_tas(tas t, size_t n){
  int i;
  int k = 1;
  int k_max = to_2_exp(n);
  int v;
  for (i=0; i<n; i++){
    if (i == k - 1){
      k *= 2;
      if (i) putchar('\n');
      v = 2* (k_max * 2 / k ) - 1;
      spaces(v);
    }
    printf("%2d", t[i]);
    spaces(2 * v);

  }
  putchar('\n');
}

size_t add_tas(tas t, int value, size_t n){
  t[n] = value;
  fixup(t, n);
  return n+1;
}

size_t pop_tas(tas t, size_t n){
  t[0] = t[--n];
  fixdown(t, 0, n);
  return n;
}


int main(){
  /* exemple d'utilisation d'un tas */
  int s = 0;
  tas t = new_tas(15);

  add_tas(t, 12, s++);
  add_tas(t, 24, s++);
  add_tas(t, 48, s++);

  add_tas(t, 15, s++);
  add_tas(t, 23, s++);
  add_tas(t, 49, s++);

  add_tas(t, 19, s++);
  add_tas(t, 54, s++);
  add_tas(t, 29, s++);

  add_tas(t, 18, s++);
  add_tas(t, 53, s++);
  add_tas(t, 92, s++);

  add_tas(t, 90, s++);
  add_tas(t, 64, s++);
  add_tas(t, 22, s++);


  draw_tas(t, s);
  s = pop_tas(t, s);
  s = pop_tas(t, s);
  draw_tas(t, s);
  free(t);
  return 0;
}

 Conclusion

voici le rendu de mon programme :
apres les insertions :
               92                              
       90              53              
   64      24      49      54      
22  12  18  23  29  15  48  19  

apres les suppressions :
               64                              
       54              53              
   48      24      49      19      
22  12  18  23  29  15  

ca compile sous linux, avec juste les options suivantes :
gcc tas.c -g -Wall -ansi --pedantic


 Historique

07 novembre 2008 04:01:53 :
correction

 Sources du même auteur

Source avec Zip INTERPRETEUR BRAINFUCK
Source avec Zip Source avec une capture COMMENTAIRES DOXYGEN VERS VISUAL
Source avec Zip INTERPRETEUR D'UN LANGAGE PROCHE DU RPN
Source avec Zip FONCTIONS USUELLES (TRIGO) EN METAPROGRAMMATION
Source avec Zip SOLVEUR DE KAKORUS EN C++
Toutes les sources de coucou747

 Sources de la même categorie

Source avec Zip UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras
Source avec Zip Source avec une capture CHIFFREMENT DE VIGENERE par lajouad
Source avec Zip Source avec une capture ANALYSE SYNTAXIQUE par lajouad
Source avec Zip Source avec une capture STRUCTURE D'UNE MATRICE PAR LES LISTE LINÉAIRE (NON CONTUGUS... par benzarabel
Source avec Zip Source avec une capture DESSINER UNE ARBRE BINAIRE( MODE CONSOLE): par benzarabel
Toutes les sources de la catégorie Maths & Algorithmes

 Sources en rapport avec celle ci

Source avec Zip Source avec une capture GENERE BMP par lajouad
Source avec Zip FILE D'ATTENTE EN C++ par bibo90
Source avec Zip HEAPCOLLECTOR par troctsch
Source avec Zip PROTEGER LE EXE PAR CRC par f_l_a_s_h_b_a_c_k
Source avec Zip BIBLIOTHÈQUE DE GESTION DE FILES DYNAMIQUES par Sunglasses

Commentaires et avis

Commentaire de petifa le 08/11/2008 18:01:41

slt,
quelques remarques :
- dans ton explication :
#alors si un pere est numerote : i, ses enfants sont : 2i et 2i+1

c'est faux, c'est 2i+1 et 2i+2

- tu définis une fonction pop_tas, alors pourquoi tu mettrais pas push_tas à la place de add_tas

- de plus tu utilise un paramètre s++ dans ta fonction add, pourquoi ne pas faire en sorte de supprimer ce paramètre??

- quelques commentaires sur la source peuvent aider ...

Commentaire de coucou747 le 08/11/2008 18:16:00 administrateur CS

en fait, le 2i+1 ou 2i+2, ca depend si tu comptes a partir de 0 ou a partir de 1 :) dans mon explication, je commence a partir de 1, alors que dans mon code, a partir de 0 (normal)

pop correspond tres bien a ce qu'on fait : on supprime l'element du sommet (qui etait le plus grand), on reordonne le tas, et on le renvoie.

par contre pour le push, on imaginerait qu'on place qqch au dessus (or c'est pas une stack )

mais euh... le nomage, c'est du detail...

s, c'est la taille du tas, j'aurais pu faire un tas sous forme de :
struct tas {
  int * tas;
  size_t n;
}

pour inclure le "tas" dedans, sauf que ca m'aurait pose quelques problemes pour pouvoir faire un heapsort (qui se fait sur un foo*).

sinon, pour les commentaires... je n'ai que 5 fonctions...


fixup permet de faire remonter un element si il est superieur a son pere
fixdown fait l'inverse : il fait descendre un element quand il est inferieur a un de ses enfants

push et add, c'est pas trop dur de deviner ce que ca fait

draw_tas affiche un tas de nombres a un ou deux chiffres

to_exp2(n) renvoie l'exposant de deux directement superieur a n ( exemple to_exp2(12) = 16 )
ln2(n) renvoie le nombre de bits utilises pour coder n.

Commentaire de petifa le 08/11/2008 21:01:14

oki mais les commentaires c pour expliquer, meme si le nom des fonctions sont assez explicites

 Ajouter un commentaire


Discussions en rapport avec ce code source dans le forum

Problème avec traitement de fichier (cplusplus !) [ par Sianrin ] Voila, j'explique mon problème. Pour voir un peu comment les accès au fichiers se géraient en cplusplus, je me suis mis en tête de faire un programme prob de compilation [ par jacky66 ] salutje debute dans la prog c++pour mon 1 er prog quand je compile il me sort un message fatal error C1083: Cannot open include file: 'idoctidm.h': No Pb avec une fonction windows... [ par Steak ] j'ai un petit probleme avec la fonction NT UpdateResource... voila ce que dit le sdk win32 : BOOL UpdateResource( HANDLE hUpdate, // update-file handl Enregistrer en HEXA un texte avec gcc !! [ par UncleShu ] /* * Ce programme affiche le fichier en HEXADECIMAL et se copie lui-même avec * une autre exetenstion (.txt). Moi je voudrais qui affiche le fichier * Petit probleme de code en C sur Linux !! [ par UncleShu ] Je voudrais créer un fichier dans le réperoire personnel d'un utilisateur mais mon code ne marche pas !!#include &lt;stdio.h&gt; #include &lt;stdlib.h conversion [ par coyotedef ] salut!!lors de la compilation de mon code une erreur apparait. impossible de trouver un remede. "cannot convert parameter 1 from 'char [10]' to 'char' devc++ et glut [ par aluco ] j'ai bo ajouter les fichiers: Options -&gt; Compiler Options -&gt; Add the following commands when calling compiler -&gt; -lglut32 -lopengl32 -lglu32 Traitement de tableau de caracteres. [ par coyotedef ] Je lit des données a partir d un fichier texte et je classe les caracteres dans un tableau de caracteres. jusque la rien de bien special.mais voila, j pb avec un labyrinthe [ par skinia ] je suis sur un projet de labyrinthe et j'ai bloqué pour l' algorithme du plus court chemin (entre un pt qq du labyrinthe et la cible au milieu).le lab ouverture de fichier avec les MFC [ par steph76 ] Bonjourvoila je programme une application qui ha beusoin d'ouvrir 1 fichier via httpJ'ai donc fait le code suivantCStdioFile *file;CInternetSession IS


Nos sponsors


Sondage...

CalendriCode

Février 2012
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
272829    

Consulter la suite du CalendriCode
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 1,061 sec (4)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)