Advertisement
Guest User

entiertrié

a guest
Nov 18th, 2018
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.83 KB | None | 0 0
  1. public class TableauTrieDEntiers{
  2.  
  3. private int [] tableDEntiers; // table d'entiers triée par ordre croissant
  4. private int nombreDEntiers; // nombre d'entiers dans tableDEntiers
  5. private static final int TAILLE = 10;
  6.  
  7. public TableauTrieDEntiers(){
  8. this.tableDEntiers = new int[TAILLE];
  9. this.nombreDEntiers = 0;
  10. }
  11.  
  12. @Override
  13. public boolean equals(Object obj) {
  14. if (this == obj)
  15. return true;
  16. if (obj == null)
  17. return false;
  18. if (getClass() != obj.getClass())
  19. return false;
  20. TableauTrieDEntiers t = (TableauTrieDEntiers)obj;
  21. if (t.nombreDEntiers!=this.nombreDEntiers)
  22. return false;
  23. for (int i = 0; i < nombreDEntiers;i++)
  24. if (this.tableDEntiers[i]!=t.tableDEntiers[i])
  25. return false;
  26. return true;
  27. }
  28.  
  29. public boolean estEgalA(TableauTrieDEntiers t){
  30. if (t.nombreDEntiers!=this.nombreDEntiers)
  31. return false;
  32. for (int i = 0; i < nombreDEntiers;i++)
  33. if (this.tableDEntiers[i]!=t.tableDEntiers[i])
  34. return false;
  35. return true;
  36. }
  37.  
  38. public String toString(){
  39. String aRenvoyer = "\n nombreDEntiers : " + this.nombreDEntiers;
  40. aRenvoyer += " tableDEntiers : ";
  41. for (int i = 0; i < this.nombreDEntiers; i++) {
  42. aRenvoyer += this.tableDEntiers[i]+" ";
  43. }
  44. return aRenvoyer;
  45. }
  46.  
  47. /**
  48. * constructeur par recopie
  49. * ce constructeur leve une exception si la table passee en parametre contient plus de 10 entiers
  50. * utile pour les tests!!!
  51. * @param tableARecopier une table d'au plus TAILLE entiers triée par ordre croissant
  52. */
  53.  
  54. public TableauTrieDEntiers(int[] tableARecopier){
  55. if (tableARecopier.length>TAILLE) throw new IllegalArgumentException();
  56. this.nombreDEntiers = tableARecopier.length;
  57. tableDEntiers= new int[TAILLE];
  58. for (int i = 0; i<nombreDEntiers; i++){
  59. tableDEntiers[i] = tableARecopier[i];
  60. }
  61. }
  62.  
  63. public int getNombreDEntiers(){
  64. return this.nombreDEntiers;
  65. }
  66.  
  67.  
  68. /**
  69. * methode qui ajoute un entier si la table n'est pas encore pleine. La table doit rester triee!
  70. * @param unEntier l'entier a ajouter
  71. * @return boolean signale si l'entier a pu etre ajoute
  72. */
  73.  
  74. public boolean ajouterUnEntier(int unEntier){
  75. if(nombreDEntiers==10) return false;
  76. int posInsert = nombreDEntiers;
  77.  
  78. while(posInsert!=0 && tableDEntiers[posInsert-1]>unEntier) {
  79. tableDEntiers[posInsert]=tableDEntiers[posInsert-1];
  80. posInsert--;
  81. }
  82. tableDEntiers[posInsert]=unEntier;
  83. nombreDEntiers++;
  84. // UTILISER L ALGORITHME D INSERTION DANS UNE TABLE TRIEE VU AU COURS!!!
  85.  
  86. return true;
  87. }
  88.  
  89. /**
  90. * methode qui recherche l'indice correspondant a une occurrence de l'entier passe en parametre
  91. * @param unEntier l'entier dont on desire connaître l'indice
  92. * @return indice correspondant a unEntier, -1 s'il n'est pas dans la table
  93. */
  94. private int trouverIndice(int unEntier){
  95. //recherche sequentielle
  96. /*for (int i = 0; i < this.nombreDEntiers; i++) {
  97. if (this.tableDEntiers[i]==unEntier)
  98. return i;
  99. if (this.tableDEntiers[i]>unEntier)
  100. return -1;
  101. }
  102. return -1;*/
  103. //recherche dichotomique
  104. int iMin=0;
  105. int iMax = nombreDEntiers;
  106. int iMil =0;
  107. boolean trouve = false;
  108. while(!trouve &&((iMax-iMin)>1)){
  109. iMil=((iMin+iMax)/2);
  110. if(tableDEntiers[iMil]==unEntier) {
  111. trouve =true;
  112. return iMil;
  113.  
  114. }
  115. if(unEntier>tableDEntiers[iMil]) {
  116. iMin = iMil;
  117.  
  118. }else {
  119. iMax=iMil;
  120. }
  121.  
  122. }
  123. if(tableDEntiers[iMil]==unEntier)
  124. return iMin;
  125.  
  126. return -1;
  127. }
  128.  
  129. /**
  130. * methode qui verifie si la table contient l'entier passe en parametre
  131. * @param unEntier l'entier dont on desire tester la presence
  132. * @return boolean true si l'entier est present dans la table
  133. */
  134. public boolean contient(int unEntier){
  135. if(trouverIndice(unEntier)==-1)return false;
  136.  
  137. // UTILISER LA METHODE trouverIndice() donnee!
  138.  
  139. return true;
  140. }
  141.  
  142. /**
  143. * methode qui supprime une occurrence d'un entier. La table doit rester triee!
  144. * @param unEntier l'entier a supprimer
  145. * @return boolean signale si l'entier a pu etre supprime
  146. */
  147. public boolean supprimerUneOccurrence(int unEntier){
  148. if(!contient(unEntier)) return false;
  149. // UTILISER LA METHODE trouverIndice() donnee!
  150. int i = trouverIndice(unEntier);
  151.  
  152.  
  153. while(i!=nombreDEntiers-1) {
  154. tableDEntiers[i]=tableDEntiers[i+1];
  155. i++;
  156.  
  157. }
  158. nombreDEntiers--;
  159.  
  160. return true;
  161. }
  162.  
  163. /**
  164. * methode qui supprime toutes les occurrences d'un entier
  165. * @param unEntier l'entier a supprimer
  166. * @return int le nombre de suppressions effectuees
  167. */
  168. public int supprimerToutesLesOccurrences(int unEntier){
  169. if(!contient(unEntier)) return 0;
  170.  
  171. int iE = trouverIndice(unEntier);
  172. int iL = iE;
  173. int compteur =0;
  174. while(iL<nombreDEntiers-1) {
  175. if(tableDEntiers[iL]==tableDEntiers[iE]) {
  176. tableDEntiers[iL]=tableDEntiers[iL+1];
  177. compteur++;
  178. }
  179.  
  180. iL++;
  181. }
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188. return compteur;
  189.  
  190. }
  191.  
  192.  
  193. /**
  194. * methode qui verifie si la table contient des ex-aequos
  195. * @return boolean true si la table contient des ex-aequos, false sinon
  196. */
  197. public boolean contientExAequo(){
  198. for (int i = 0; i<nombreDEntiers-1; i++) {
  199. if(tableDEntiers[i]==tableDEntiers[i+1]) return true;
  200. }
  201.  
  202. return false;
  203. }
  204.  
  205. /**
  206. * methode qui supprime tous les ex-aequos
  207. * @return int le nombre de suppressions effectuees
  208. */
  209. public int supprimerTousLesExAequos(){
  210. int nombreSuppression = 0;
  211. for (int i = 1; i < nombreDEntiers; i++) {
  212. if (tableDEntiers[i]==tableDEntiers[i-1]) {
  213. nombreSuppression++;
  214. }else {
  215. tableDEntiers[i-nombreSuppression] = tableDEntiers[i];
  216. }
  217.  
  218. }
  219. nombreDEntiers = nombreDEntiers - nombreSuppression;
  220. return nombreSuppression;
  221. }
  222.  
  223.  
  224.  
  225.  
  226. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement