Implémenter un tas en tableau

Implémenter un tas en tableau - Java - Programmation

Marsh Posté le 02-05-2008 à 20:07:29    

Hello les gens,
je suis en train d'implémenter un tas en tableau pour un cours de Java. Le truc c'est que ma fonction ExtraireMax ne tourne pas. Les 2-3 premieres valeurs que j'extraie sont bien les maximum mais après j'obtiens des valeurs inférieures à celles restantes. Voilà mon code :
 

Code :
  1. public class Tastab implements Tas {
  3. private int tab[];
  4. private int cpt;
  6. /**----------------------------------------------------------------
  7.  * Constructeur
  8.  */
  10. public Tastab() {
  11.  super();
  12.  cpt=0;
  13.  tab = new int[10];
  14. }
  16. /**----------------------------------------------------------------
  17.  * Fonction permettant d'obtenir l'élément maximum du tas
  18.  * @return Retourne le maximum du tas
  19.  */
  20. public Integer max() {
  21.  return new Integer(tab[0]);
  22. }
  24. /**----------------------------------------------------------------
  25.  * La fonction d'insertion
  26.  * @param nb Le nombre à insérer.
  27.  */
  28. public void inserer(int nb) {
  29.  tab[cpt]=nb;
  30.  int i=cpt;
  31.  while(i!=0 && tab[i/2]<tab[i]){
  32.   echanger(i,i/2);
  33.   i=i/2;
  34.  }
  35.  cpt++;
  36. }
  38. /**----------------------------------------------------------------
  39.  * Fonction permettant d'échanger deux éléments du tas
  40.  * @param i Le premier nombre à échanger.
  41.  * @param j Le second nombre à échanger.
  42.  */
  44. public void echanger(int i, int j) {
  45.  int tmp=tab[i];
  46.  tab[i]=tab[j];
  47.  tab[j]=tmp;
  48. }
  50. /**----------------------------------------------------------------
  51.  * Méthode itérative d'affichage.
  52.  * @param i Le noeud à partir duquel on souhaire afficher.
  53.  */
  54. public void affichage()
  55. {
  56.  for(int i=0;i<cpt;i++)
  57.  {
  58.   int fd=2*(i+1)+1;
  59.   int fg=2*(i+1);
  60.   if(fd>cpt&&fg>cpt){
  61.    System.out.println(tab[i]+" est une feuille." );
  62.   }
  64.   else{
  65.    if(fd<cpt && fg<cpt) System.out.println(tab[i]+" est le pere de "+tab[fg-1]+" et de "+tab[fd-1]+"." );
  66.    else
  67.    {
  68.     if(fd<cpt) System.out.println(tab[i] +" est le pere de " +tab[fd-1]+ "." );
  69.     if(fg<cpt) System.out.println(tab[i] +" est le pere de " +tab[fg-1]+"." );
  70.    }
  71.   }
  72.  }
  73. }
  75. /**----------------------------------------------------------------
  76.  * La fonction toString()
  77.  * @return la chaine décrivant le tas
  78.  */
  79. public String toString()
  80. {
  81.  String tmp = "";
  82.  for(int i=1;i<=cpt;i++){
  83.   tmp+=tab[i-1]+" ";
  84.  }
  85.  return tmp;
  86. }
  88. /**----------------------------------------------------------------
  89.  * Méthode retournant le nombre d'éléments du tas.
  90.  * @return Le compteur d'éléments qu'on souhaite retourner.
  91.  */
  93. public int getCpt() {
  94.  return cpt;
  95. }
  98. /**----------------------------------------------------------------
  99.  * Méthode permettant d'extraire l'élément maximum du tas.
  100.  * @return L'élément maximum qui a été retiré.
  101.  */
  103. public Integer extraireMax() {
  104.  int tmp=tab[0];
  105.  int i,j;
  106.  boolean stop=false;
  108.  i=1;
  109.  while((2*i+1)<cpt && !stop)
  110.  {
  111.   j=2*i;
  112.   if((2*i+1)<=cpt && tab[2*i]>tab[2*i-1])
  113.   {
  114.    j=2*i+1;
  115.   }
  116.   if(tab[i-1]>tab[j-1]) stop=true;
  117.   else{
  118.    echanger(i-1, j-1);
  119.    i=j;
  120.   }
  121.  }
  123.  return new Integer(tmp);
  124. }
  126. public int[] getTab() {
  127.  return tab;
  128. }
  130. public void setCpt(int cpt) {
  131.  this.cpt = cpt;
  132. }
  134. public void setTab(int[] tab) {
  135.  this.tab = tab;
  136. }
  138. public boolean estFeuille(int i)
  139. {
  140.  if((2*i+1)>cpt) return true;
  141.  return false;
  142. }
  143. }

Reply

Marsh Posté le 02-05-2008 à 20:07:29   

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed