Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
2407 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  Problêmes sur les listes chainées

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Problêmes sur les listes chainées

n°1959676
snake77380
Posté le 22-01-2010 à 12:44:10  profilanswer
 

Bonjour à tous,  
 
 voila je suis débutant en algo et je souhaitrais vous soumettre un des mes problêmes, le voici :
 
Je travail sur une liste simplement chainée dont chaque maillon est définit ainsi :
 
 Type  Maillon = Enreg( valeur : Entier, suivant : pointeur(Maillon) )
 
Tout d'abord je dois élaborer une fonction permettant de calculer la somme des éléments de cette liste chainée ( par exemple : 1,2,3 -> 6).
 
 Voici ce que j'ai fais :  
 
Fonction Somme ( maillon : ENTIER )         */ il doit manquer des choses là */
 somme =0  
 DEBUT
       tant que (tmp!= NULL)                  */ tant que je n'est pas parcouru toute ma liste */
            somme = somme + maillon.val
            maillon = * maillon.suivant          */ je parcours tous les maillons de ma chaine */
       fin du tant que
            retourner somme;
  FIN
   
 J'espère que cest assez lisible.
 
 J'ai une deuxième question si jamais vous avez le temps, je dois créer une procédure permettant d'inverser ma liste simplement chainée ( ex: 4,1,8 -> 8,1,4)
 
 Procédure inversion ( tab,tab2 : Tableau  )       */ cest très certainnement incorrect */
  DEBUT
  milieu = taille/2
    Pour (i=0;i<milieu;i++) {
      tab2 = tab[i]
      tab[i] = tab[taille-i]       */ je tente de réaliser un swap avec tab2 et tab le tableau initial */
      tab[taille-i] = tab2;
   FIN
 
Alors là je suis un peu perdu, je me suis servis d'un code utlisé en C, mais je suis pas sur que je puisses parler de tableau ici.
 
 Merci à vous.
   

mood
Publicité
Posté le 22-01-2010 à 12:44:10  profilanswer
 

n°1959689
breizhbugs
Posté le 22-01-2010 à 13:28:17  profilanswer
 

snake77380 a écrit :


Fonction Somme ( maillon : ENTIER )         */ il doit manquer des choses là */
 somme =0  
 DEBUT
       tant que (tmp!= NULL)                  */ tant que je n'est pas parcouru toute ma liste */
            somme = somme + maillon.val
            maillon = * maillon.suivant          */ je parcours tous les maillons de ma chaine */
       fin du tant que
            retourner somme;
  FIN
   
   


Plop,
Bon je me souvient plus trop de la syntaxe du lda mais voici quelques remarques:
- Ta fonction Somme prend une liste de maillon en entrée et renvoi un entier : ENTIER Somme(m:maillon)  
- initialiser somme correct
- tu dois boucler tant que ta liste n'est pas vide: TANT QUE (m != NULL)  
- le calcul de la somme est correct : somme <- somme + m.valeur
- passage au maillon suivant : m <- m.suivant                
- TANT QUE correct et retourner somme aussi
-A noter que si on passe une liste vide, la fonction ne plante pas et renvoie somme = 0
 
Pour ce qui est d'inverser la liste, le principe est que pour chaque maillon que tu découvres de la liste 'a' tu le places au début de la liste 'b' .
Essaie de reproposer une version de ta procédure en tenant compte de ca

n°1959702
snake77380
Posté le 22-01-2010 à 14:05:21  profilanswer
 

Salut breizhbugs et merci pour tes réponses, j'ai éssayé de refaire une procédure pour inverser, en utilisant deux boucles, une 1ere qui va passer les élements du début à la fin, et une seconde qui va passer les élements de la fin au début, voila ce que ça donne :
 
 Procedure inverser (tab1,tab2 : Tableau )  {
   DEBUT  
      milieu = taille / 2
      Pour (i=0;i<milieu;i++) {
        tab1[i]=tab2[i];  */ ici je met les valeurs de ma 1ere moitié dans la seconde */
      Pour (j=milieu;j<fin;j++) {
         tab2[j]=tab1[j];     */ je fais de meme avec l'autre moitié */
                                       } }
   FIN
 
Si mes deux boucles sont imbriquées les valeurs que je fais bouger dans la seconde boucle ne sont pas affectées par la première il me semble, sinon ce que j'ai fais n'a servis a rien, j'aurais changé de place des éléments pour les remettre ensuite a leurs positions initials.
 
 Merci.
   

n°1959764
MagicBuzz
Posté le 22-01-2010 à 16:06:19  profilanswer
 

Salut, je ne suis pas famillié avec un "langage d'algo" particulier (lda), puisque par définition, y'a pas de langage d'algo, c'est du français.
 
En revanche, voici mes commentaires :

snake77380 a écrit :

 
Fonction Somme ( maillon : ENTIER )         */ il doit manquer des choses là */
 somme =0  
 DEBUT
       tant que (tmp!= NULL)                  */ tant que je n'est pas parcouru toute ma liste */
            somme = somme + maillon.val
            maillon = * maillon.suivant          */ je parcours tous les maillons de ma chaine */
       fin du tant que
            retourner somme;
  FIN
   


 
tant que (tmp!= NULL)    
=> Tu ne déclares pas ce "tmp". Pour moi, "tmp", c'est "maillon.suivant".
=> Avant de pouvoir tester "maillon.suivant", tu dois tester "maillon", afin de t'assurer qu'on t'as pas passé une liste vide. Il manque donc un test avant ta boucle.
   

snake77380 a écrit :

 
 Procédure inversion ( tab,tab2 : Tableau  )       */ cest très certainnement incorrect */
  DEBUT
  milieu = taille/2
    Pour (i=0;i<milieu;i++) {
      tab2 = tab[i]
      tab[i] = tab[taille-i]       */ je tente de réaliser un swap avec tab2 et tab le tableau initial */
      tab[taille-i] = tab2;
   FIN
   


 
Comme tu le dis, c'est très clairement incorrect : tu cherches à modifier l'ordre d'une liste... Donc à partir de là, la liste c'est pas un tableau...
 
Ensuite, niveau principe :
 
Tu boucles sur chaque ELEMENT :
Tu copies ELEMENT.suivant dans un TMP.
Tu copies TMP.suivant dans un TMP2.
Le TMP.suivant devient ELEMENT.
ELEMENT devient TMP2.
 
Ou un truc du genre, j'ai pas trop la tête à ton problème, qui sent l'exercice à plein nez en plus.


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  Problêmes sur les listes chainées

 

Sujets relatifs
Listes déroulantes et affichages[HTML/Css/Javascript] Listes liées avec la librairie prototype
Programmation VB problèmes de débutantProblemes requetes PHP/MySql
Problèmes avec un tableau à 2 dimensionslistes C
Intitulé d'un évènement sur 2 listes déroulantes [RESOLU]Quelques problèmes simples en AS 3
Problèmes de liens, headers et fonctions 
Plus de sujets relatifs à : Problêmes sur les listes chainées


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR