IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

comment insere un élément dans un tab trié ? [Débutant(e)]


Sujet :

C

  1. #1
    Membre averti
    Profil pro
    Inscrit en
    Octobre 2006
    Messages
    24
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : Tunisie

    Informations forums :
    Inscription : Octobre 2006
    Messages : 24
    Par défaut comment insere un élément dans un tab trié ?
    j'ai une question : j'ai un tableau de dimension n+1
    contient n valeurs triés par ordre croissant
    la (n+1) ème valeur est indéfinie
    je doit insérer une valeur ( x ) dans ce tableau, tout en gardant l'ordre !
    c'est à dire je vais comparer ( x ) et les autres éléments du tabelau jusqu'a trouver la dernière valeur ( a ) qui précéde ( x ) dans le tableau ( cad x>a et puis x< a+1 )
    Apres je doit décaler les éléments qui suit (x) pour que je puisse l'insérer, et donc j'ai rempli la (n+1)ème valeur du tableau
    question : comment on peu décaler ce tableau ?

  2. #2
    Membre averti
    Profil pro
    Inscrit en
    Octobre 2006
    Messages
    24
    Détails du profil
    Informations personnelles :
    Âge : 38
    Localisation : Tunisie

    Informations forums :
    Inscription : Octobre 2006
    Messages : 24
    Par défaut
    voila un exemple :
    le tableau est de 6 cases ( tableau trié par ordre croissant, le dernier élément est pas définie )

    ----------------------------
    1 | 2 | 3 | 5 | 6 | indéfine |
    ----------------------------

    je doit insérer x=4 dans ce tableau
    je doit faire le parcours " tantque ( x>t[i] ) ..."
    je m'arrete à la case conteannt la valeur 5
    je doit insérer x=4 dans la case entre 3 et 5
    pour ca je doit décaler la partie " 5|6 " du tableau à droite pour libérer une case de x, et comme ca on a rempli tout le tableau
    comment peu on décaler ce tableau & insérer la valeur 4 ?
    ( merci pour votre aide )

  3. #3
    Expert éminent
    Avatar de Emmanuel Delahaye
    Profil pro
    Retraité
    Inscrit en
    Décembre 2003
    Messages
    14 512
    Détails du profil
    Informations personnelles :
    Âge : 68
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Retraité

    Informations forums :
    Inscription : Décembre 2003
    Messages : 14 512
    Par défaut
    Citation Envoyé par sablito
    j'ai une question : <...>
    Par copie des éléments. Avec un tableau, il n'y a pas d'autre solution.

    Un peu de méthodologie. Pour résoudre un problème quel qu'il soit, il faut passer au moins par 3 étapes dans l'ordre :

    1 - Définition : quoi ?
    2 - Conception : comment ?
    3 - Réalisation (ici, codage et tests)

    La définition est ici l'énoncé du problème. Il est assez clair :
    j'ai un tableau de dimension n+1
    contient n valeurs triés par ordre croissant
    la (n+1) ème valeur est indéfinie
    je doit insérer une valeur ( x ) dans ce tableau, tout en gardant l'ordre !
    Ensuite, il y a une tentative de résolution du problème que l'on peut assimiler à de la conception :
    c'est à dire je vais comparer ( x ) et les autres éléments du tabelau jusqu'a trouver la dernière valeur ( a ) qui précéde ( x ) dans le tableau ( cad x>a et puis x< a+1 )
    Apres je doit décaler les éléments qui suit (x) pour que je puisse l'insérer, et donc j'ai rempli la (n+1)ème valeur du tableau
    question : comment on peu décaler ce tableau ?
    et finalement une question dont la réponse a déjà quasiment été donnée dans l'analyse précédente. Il suffit maintenant de décrire le comportement avec de phrases simples et claires. Par exemple, ceci en 'premier jet'.
    • Faire une copie de l'élément à insérer
    • Parcourir le tableau pour trouver sa position d'insertion
    • Noter la position
    • Aller en fin de tableau
    • De la fin du tableau à la position d'insertion, copier chaque élément à la position suivante
    • Copier l'élément à insérer

    Maintenant, on peut réfléchir à une meilleure séquence qui aurait pour effet de réduire les déplacements :
    • Aller à la position de l'élément à insérer (par définition la fin de tableau)
    • Faire une copie de l'élément à insérer
    • De la fin du tableau à la position d'insertion, copier chaque élément à la position suivante
    • Copier l'élément à insérer

    et voilà, tout simplement.

    Ce travail de reflexion est essentiel. C'est ici que se fait la conception, et les choix déterminants la performance. Et c'est pour ça qu'on est payé ! Le codage, c'est secondaire. Une machine un peu douée sachant lire le texte précédant saurant en tirer du code et les jeux de tests correspondants un jour ou l'autre...

  4. #4
    Expert éminent
    Avatar de Emmanuel Delahaye
    Profil pro
    Retraité
    Inscrit en
    Décembre 2003
    Messages
    14 512
    Détails du profil
    Informations personnelles :
    Âge : 68
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Retraité

    Informations forums :
    Inscription : Décembre 2003
    Messages : 14 512
    Par défaut
    Citation Envoyé par markipoli Voir le message
    Je suis dans la même situation mais je bloque depuis plusieurs jours pour un projet que je dois rendre après demain :-/ je désespère. Si vous pouviez <...>
    Il est parfaitement impoli et déplacé de squatter la discussion d'un autre. C'est à toi de créer ta discussion si tu veux qu'elle soit suivie.

    Question supprimée.

  5. #5
    Membre régulier
    Inscrit en
    Novembre 2007
    Messages
    8
    Détails du profil
    Informations forums :
    Inscription : Novembre 2007
    Messages : 8
    Par défaut
    Salut,

    Merci, je ne m'attendais pas à un tel rappel à l'ordre alors que sur tout les forums que j'ai vu de ma vie on préfère réutiliser les topics déjà existants plutôt que d'en faire un autre à propos du même soucis...

    Je ne savais pas que c'était « parfaitement impoli et déplacé » et je n'assimilais pas cela à du squatte. Désolé, je ne referai plus la même erreur, et j'apprendrai à sauvegarder une copie des messages que je posterai de peur qu'ils soient de nouveau supprimés sans préavis, et donc de reperdre un temps fou à retaper parfaitement et clairement mon message, du fait de mon ignorance des règles exotiques et implicites telles que celle ci (et qui n'est même pas dans la charte : http://club.developpez.com/regles/).

    Encore désolé :-/

    PS : sans remettre en cause la modération, j'apporte juste un précision, après les modérateurs font ce qu'ils veulent...

    @++

  6. #6
    Membre chevronné Avatar de Pierre Maurette
    Profil pro
    Inscrit en
    Juillet 2002
    Messages
    283
    Détails du profil
    Informations personnelles :
    Âge : 69
    Localisation : France

    Informations forums :
    Inscription : Juillet 2002
    Messages : 283
    Par défaut
    Citation Envoyé par sablito Voir le message
    j'ai une question : j'ai un tableau de dimension n+1
    contient n valeurs triés par ordre croissant
    la (n+1) ème valeur est indéfinie
    je doit insérer une valeur ( x ) dans ce tableau, tout en gardant l'ordre !
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    #include <stdio.h>
    #include <stdlib.h>
     
    void printinttab(int* tab, int taille){
    	int i;
    	for(i = 0; i < taille; i++){
    		printf("%d - %d\n", i, tab[i]);
    	}
    }
     
    int compareint(const void* a, const void* b){
    	return *(int*)a - *(int*)b;
    }
     
     
    int main(void) {
    #define PETRUS_TAILLE (sizeof rats / sizeof(int))
    	int rats[] = {1, 2, 3, 5, 6, 0};
    	rats[PETRUS_TAILLE - 1] = 4;
    	puts("rats pas triés:");
    	printinttab(rats, PETRUS_TAILLE);
    	qsort(rats, PETRUS_TAILLE, sizeof(int), compareint);
    	puts("rats triés:");
    	printinttab(rats, PETRUS_TAILLE);
    #undef PETRUS_TAILLE
    	return EXIT_SUCCESS;
    }
    Mais c'est pas sûr que ce soit ce que souhaite le prof ...

  7. #7
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 801
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 801
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par Pierre Maurette Voir le message
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    ...
    	qsort(rats, PETRUS_TAILLE, sizeof(int), compareint);
    	puts("rats triés:");
    	printinttab(rats, PETRUS_TAILLE);
    #undef PETRUS_TAILLE
    	return EXIT_SUCCESS;
    }
    Mais c'est pas sûr que ce soit ce que souhaite le prof ...
    Absolument. Le topic parle de méthode d'insertion dans un tableau déjà trié et non d'insertion puis de tri à l'issue. A la limite la solution demandée doit fonctionner même si la fonction qsort() n'existe pas...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

Discussions similaires

  1. Réponses: 9
    Dernier message: 28/11/2007, 08h12
  2. Réponses: 2
    Dernier message: 16/05/2006, 11h53
  3. comment inserer un logo dans un HTML????
    Par Mickey.jet dans le forum XML/XSL et SOAP
    Réponses: 2
    Dernier message: 20/03/2006, 15h53
  4. [SVG][JSP]Comment inserer du SVG dans un JSP ?
    Par Jaxofun dans le forum XML/XSL et SOAP
    Réponses: 5
    Dernier message: 27/04/2005, 14h42
  5. Comment inserer une image dans une table sous sql qerveur
    Par zeddy23 dans le forum Bases de données
    Réponses: 4
    Dernier message: 25/02/2005, 08h51

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo