Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class TableauTrieDEntiers{
- private int [] tableDEntiers; // table d'entiers triée par ordre croissant
- private int nombreDEntiers; // nombre d'entiers dans tableDEntiers
- private static final int TAILLE = 10;
- public TableauTrieDEntiers(){
- this.tableDEntiers = new int[TAILLE];
- this.nombreDEntiers = 0;
- }
- @Override
- public boolean equals(Object obj) {
- if (this == obj)
- return true;
- if (obj == null)
- return false;
- if (getClass() != obj.getClass())
- return false;
- TableauTrieDEntiers t = (TableauTrieDEntiers)obj;
- if (t.nombreDEntiers!=this.nombreDEntiers)
- return false;
- for (int i = 0; i < nombreDEntiers;i++)
- if (this.tableDEntiers[i]!=t.tableDEntiers[i])
- return false;
- return true;
- }
- public boolean estEgalA(TableauTrieDEntiers t){
- if (t.nombreDEntiers!=this.nombreDEntiers)
- return false;
- for (int i = 0; i < nombreDEntiers;i++)
- if (this.tableDEntiers[i]!=t.tableDEntiers[i])
- return false;
- return true;
- }
- public String toString(){
- String aRenvoyer = "\n nombreDEntiers : " + this.nombreDEntiers;
- aRenvoyer += " tableDEntiers : ";
- for (int i = 0; i < this.nombreDEntiers; i++) {
- aRenvoyer += this.tableDEntiers[i]+" ";
- }
- return aRenvoyer;
- }
- /**
- * constructeur par recopie
- * ce constructeur leve une exception si la table passee en parametre contient plus de 10 entiers
- * utile pour les tests!!!
- * @param tableARecopier une table d'au plus TAILLE entiers triée par ordre croissant
- */
- public TableauTrieDEntiers(int[] tableARecopier){
- if (tableARecopier.length>TAILLE) throw new IllegalArgumentException();
- this.nombreDEntiers = tableARecopier.length;
- tableDEntiers= new int[TAILLE];
- for (int i = 0; i<nombreDEntiers; i++){
- tableDEntiers[i] = tableARecopier[i];
- }
- }
- public int getNombreDEntiers(){
- return this.nombreDEntiers;
- }
- /**
- * methode qui ajoute un entier si la table n'est pas encore pleine. La table doit rester triee!
- * @param unEntier l'entier a ajouter
- * @return boolean signale si l'entier a pu etre ajoute
- */
- public boolean ajouterUnEntier(int unEntier){
- if(nombreDEntiers==10) return false;
- int posInsert = nombreDEntiers;
- while(posInsert!=0 && tableDEntiers[posInsert-1]>unEntier) {
- tableDEntiers[posInsert]=tableDEntiers[posInsert-1];
- posInsert--;
- }
- tableDEntiers[posInsert]=unEntier;
- nombreDEntiers++;
- // UTILISER L ALGORITHME D INSERTION DANS UNE TABLE TRIEE VU AU COURS!!!
- return true;
- }
- /**
- * methode qui recherche l'indice correspondant a une occurrence de l'entier passe en parametre
- * @param unEntier l'entier dont on desire connaître l'indice
- * @return indice correspondant a unEntier, -1 s'il n'est pas dans la table
- */
- private int trouverIndice(int unEntier){
- //recherche sequentielle
- /*for (int i = 0; i < this.nombreDEntiers; i++) {
- if (this.tableDEntiers[i]==unEntier)
- return i;
- if (this.tableDEntiers[i]>unEntier)
- return -1;
- }
- return -1;*/
- //recherche dichotomique
- int iMin=0;
- int iMax = nombreDEntiers;
- int iMil =0;
- boolean trouve = false;
- while(!trouve &&((iMax-iMin)>1)){
- iMil=((iMin+iMax)/2);
- if(tableDEntiers[iMil]==unEntier) {
- trouve =true;
- return iMil;
- }
- if(unEntier>tableDEntiers[iMil]) {
- iMin = iMil;
- }else {
- iMax=iMil;
- }
- }
- if(tableDEntiers[iMil]==unEntier)
- return iMin;
- return -1;
- }
- /**
- * methode qui verifie si la table contient l'entier passe en parametre
- * @param unEntier l'entier dont on desire tester la presence
- * @return boolean true si l'entier est present dans la table
- */
- public boolean contient(int unEntier){
- if(trouverIndice(unEntier)==-1)return false;
- // UTILISER LA METHODE trouverIndice() donnee!
- return true;
- }
- /**
- * methode qui supprime une occurrence d'un entier. La table doit rester triee!
- * @param unEntier l'entier a supprimer
- * @return boolean signale si l'entier a pu etre supprime
- */
- public boolean supprimerUneOccurrence(int unEntier){
- if(!contient(unEntier)) return false;
- // UTILISER LA METHODE trouverIndice() donnee!
- int i = trouverIndice(unEntier);
- while(i!=nombreDEntiers-1) {
- tableDEntiers[i]=tableDEntiers[i+1];
- i++;
- }
- nombreDEntiers--;
- return true;
- }
- /**
- * methode qui supprime toutes les occurrences d'un entier
- * @param unEntier l'entier a supprimer
- * @return int le nombre de suppressions effectuees
- */
- public int supprimerToutesLesOccurrences(int unEntier){
- if(!contient(unEntier)) return 0;
- int iE = trouverIndice(unEntier);
- int iL = iE;
- int compteur =0;
- while(iL<nombreDEntiers-1) {
- if(tableDEntiers[iL]==tableDEntiers[iE]) {
- tableDEntiers[iL]=tableDEntiers[iL+1];
- compteur++;
- }
- iL++;
- }
- return compteur;
- }
- /**
- * methode qui verifie si la table contient des ex-aequos
- * @return boolean true si la table contient des ex-aequos, false sinon
- */
- public boolean contientExAequo(){
- for (int i = 0; i<nombreDEntiers-1; i++) {
- if(tableDEntiers[i]==tableDEntiers[i+1]) return true;
- }
- return false;
- }
- /**
- * methode qui supprime tous les ex-aequos
- * @return int le nombre de suppressions effectuees
- */
- public int supprimerTousLesExAequos(){
- int nombreSuppression = 0;
- for (int i = 1; i < nombreDEntiers; i++) {
- if (tableDEntiers[i]==tableDEntiers[i-1]) {
- nombreSuppression++;
- }else {
- tableDEntiers[i-nombreSuppression] = tableDEntiers[i];
- }
- }
- nombreDEntiers = nombreDEntiers - nombreSuppression;
- return nombreSuppression;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement