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 :

Comprendre les "Linked lists"


Sujet :

C

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Invité1
    Invité(e)
    Par défaut Comprendre les "Linked lists"
    Je suis rendu à apprendre comment fonctionnent les "linked lists" (je sais pas comment le dire en français) . . .

    J'ai un petit bout de code, mais je n'arrive pas à comprendre à quoi sert le
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    struct account *previousa;
    Il est utilisé dans le code, mais je ne voit pas son utilité . . .

    Voici le code:
    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
     
    void deleteAccount(void){
    	int record;
    	struct account *previousa;
     
    	if(firsta==NULL)
    	{
    		puts("There are no records to delete!");
    		return;
    	}
     
    	listAll();		/* show all records first */
    	printf("Enter account number to delete: ");
    	scanf("%d",&record);
     
    	currenta = firsta;
    	while(currenta != NULL)
    	{
    		if(currenta->number == record)
    	{
    		if(currenta == firsta)	/* special condition */
    		firsta=currenta->next;
    		else
    		previousa->next = currenta->next;
    			free(currenta);
    		printf("Acount %d deleted!\n",record);
    		return;
    	}
    	else
    	{
    			previousa = currenta;
    		currenta = currenta->next;
    	}
    	}
    	printf("Account %d was not found!\n",record);
    	puts("Nothing deleted.");
    }
    Merci beaucoup!
    Alex

    Edit: Voici le code qui sert à ajouter un compte (ça pourrait peut-être aider à comprendre) . . .
    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
     
    void addNewAccount(void)
    {
        newa = (struct account *)malloc(sizeof(struct account));
     
    /*
     * Check to see if this is the first record
     * If so, then initialize all the pointers to this,
     * first structure in the database
     */
     
        if(firsta==NULL)
            firsta = currenta = newa;
     
    /* 
     * Otherwise, you must find the end of the structure list
     * (Easily spotted by the NULL pointer) and add on the
     * new structure you just allocated memory for
     */
     
        else
        {
            currenta = firsta;      /* make the first record the current one */
                                    /* and loop through all records: */
     
            while(currenta->next != NULL)
                currenta = currenta->next;
    				/* the last record is found */
            currenta->next = newa;  /* save the address of new */
            currenta = newa;        /* make current record the new one */
        }
     
    /* Now, you just fill in the new structure */
     
        anum++;
        printf("%27s: %5i\n","Account number",anum);
        currenta->number = anum;
     
        printf("%27s: ","Enter customer's last name");
        gets(currenta->lastname);
     
        printf("%27s: ","Enter customer's first name");
        gets(currenta->firstname);
     
        printf("%27s: $","Enter account balance");
        scanf("%f",&currenta->balance);
     
    /* 
     * Finally, cap the new record with a NULL pointer
     * so that you know it's the last record:
     */
     
        currenta->next = NULL;
    }

  2. #2
    Scorpi0
    Invité(e)
    Par défaut
    Bonjour,

    Citation Envoyé par Alexandreg12 Voir le message
    Je suis rendu à apprendre comment fonctionnent les "linked lists" (je sais pas comment le dire en français) . . .
    Listes chainees en français.

    La variable previousa (appelons le X) sert a 'sauvegarder' l'élément précedent de la liste (d'ou le previous = précédent).
    Il est nécessaire de la sauvegarder, car une fois l'élément à supprimer (appelons le Y) trouver, il faut reconnecter l'élément suivant, appelons le Z.

    On a donc X->Y->Z.
    On veut détruire Y.

    On part de X, pas le bon, on le garde en tête quand même.
    On arrive à Y, a, c'est lui qu'on veut plu. On regarde le suivant, Z, on le garde en tête.
    On détruit Y.

    On connecte les 2 éléments garder en tête, X et Z, on final il nous reste X->Z.

    Voilà pour l'utilité de previousa.

    Pour t'aider à mieux comprendre, je te commente le code fournit :

    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    /* Fonction qui detruit un element de la liste dont le premier element est une ignoble 
     * variable globale diaboliquement appele firsta et qui ferait mieux d'etre passe en argument, 
     * enfin moi j'dit ca j'dit rien... 
    */
    void deleteAccount(void){
     
    	/* Numero de l'element a supprimer qui sera demande a l'utilisateur */
    	int record;
     
    	/* Variable sauvegardant l'element precedent celui en cours */
    	struct account *previousa;
     
    	/* Si liste vide, on sort */
    	if(firsta==NULL)
    	{
    		puts("There are no records to delete!");
    		return;
    	}
     
    	listAll();		/* show all records first */
     
    	/* Demande du numero de l'element a supprimer */
    	printf("Enter account number to delete: ");
    	scanf("%d",&record);
     
    	/* L'element courant est initialise au premier element de la liste */
    	/* Au passage, currenta est une variable globale aussi, ce qui n'a absolument aucun interet */
    	currenta = firsta;
     
    	/* Tant qu'il reste des elements, dans la liste, on boucle */
    	while(currenta != NULL)
    	{
    		if(currenta->number == record)
    		/* Youhou, on a trouve l'element a supprimer !!*/
    		{
    			if(currenta == firsta)
    			/* Au cas ou l'element a supprimer est le premier, 
    			 * on reinitalise le premier element de la liste avec son suivant
    			 */
    			{
    				firsta=currenta->next;
    			}
    			else
    			/* Cas normal, connection entre le precedent et le suivant de l'element a supprimer */
    			{
    				previousa->next = currenta->next;
    			}
     
    			/* Destruction de l'element courant */
    			free(currenta);
    			printf("Acount %d deleted!\n",record);
    			return;
    		}
    		else
    		/* L'element courant n'est pas celui a supprimer, on continu a boucler */
    		/* Le courant devient le precedent, et le suivant devient le courant */
    		{
    			previousa = currenta;
    			currenta = currenta->next;
    		}
    	}
     
    	/* Toute la liste a ete analyse, aucun element n'a ete trouve */
    	printf("Account %d was not found!\n",record);
    	puts("Nothing deleted.");
    }
    Dernière modification par Scorpi0 ; 28/08/2008 à 16h53.

  3. #3
    Invité1
    Invité(e)
    Par défaut
    Je vais paraitre un peu stupide, mais j'ai toujours du mal à comprendre . . .

    Je vais commenter le code, ce sera peut-être plus facile . . .

    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
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
     
    void deleteAccount(void){
    	int record;
    	struct account *previousa;
     
    	if(firsta==NULL)
    	{
    		puts("There are no records to delete!");
    		return;
    	}
     
    	listAll();		/* show all records first */
    	printf("Enter account number to delete: ");
    	scanf("%d",&record);
     
     	//L'élément courrant prend la valeur du premier.
    	currenta = firsta;
     
    	//Tant qu'on arrive pas à la fin de la liste
    	while(currenta != NULL)
    	{
    		//Si le currenta est le compte à détruire.
    		if(currenta->number == record)
    		{
    			//Si c'est le premier
    			if(currenta == firsta)	/* special condition */
    			//Le firsta devient le 2e (le 2e devient le premier . . .) . . . Bon, on comprend ...
    			firsta=currenta->next;
    			//Si c'est pas le premier
    			else
    			//Le previous.next . . . C'est l'adresse du current dans le fond? ... prend la valeur du currenta->next? ... 
    			//donc le previous.next . . . qui montre en fait ... ah, je comprend pas ...!! Je voit pas à quoi cette ligne va servir! ...
    			//Elle me semble inutile ...
    			previousa->next = currenta->next;
    				//On efface le currenta
    				free(currenta);
    			printf("Acount %d deleted!\n",record);
    			return;
    		}
    	else
    	{
    			previousa = currenta;
    		currenta = currenta->next;
    	}
    	}
    	printf("Account %d was not found!\n",record);
    	puts("Nothing deleted.");
    }

  4. #4
    Invité1
    Invité(e)
    Par défaut
    je viens de voir les commentaires! . . .

    Je crois que j'ai besoin d'un dessin On dirait que je suis pas super intelligent ce matin

  5. #5
    Invité1
    Invité(e)
    Par défaut
    Je ne comprend pas à quoi sert le previousa->next = currenta->next; . . .

    La valeur que prend le previousa->next n'est jamais utilisée plus tard . . .

  6. #6
    Scorpi0
    Invité(e)
    Par défaut
    Disons qu'il faut bien comprendre les pointeurs ici.

    Dans une zone mémoire, qui est l'élément 'next' de l'instance previousa de la structure account, tu va mettre un pointeur vers un autre account.

    previousa est un pointeur sur un account, en fait, c'est plutôt une sorte d'itérateur en quelque sorte. Une sorte de pointeur qui balaye ta liste à chaque itération.

    Même si previousa n'est plu jamais utilisé dans la fonction ensuite, ce n'est pas grave, son office aura été faite, à savoir renseigner la zone 'next' de l'instance de la structure account sur lequel il pointait.

    Hors de la fonction, la structure sur lequel il pointait existera toujours, et donc l'affectation n'aura pas été vaine.

  7. #7
    Scorpi0
    Invité(e)
    Par défaut
    Si tu ne fait pas

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    previousa->next = currenta->next;
    Tu va avoir ton X->Y->Z->null , qui une fois Y supprimer va devenir

    X->null1
    et
    Z->null

    previousa->next = null1
    currenta->next = Z

    donc previousa->next = currenta->next <=> X->Z
    Je sais pas si j'explique bien là

  8. #8
    Membre chevronné

    Inscrit en
    Juillet 2008
    Messages
    232
    Détails du profil
    Informations forums :
    Inscription : Juillet 2008
    Messages : 232
    Par défaut
    Une liste chainee a un lien vers l'element suivant de la liste

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
     -------      -------      -------
    |  1er |---->| 2eme |---->| 3eme |
    |______|     |______|     |______|
    La boucle conserve un lien vers l'element precedent de la liste, et l'attache a l'element suivant. Dans cette illustration previousa = 1er element et currenta = 2eme element. Le 3eme element est currenta->next.
    On veut le resultat final

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
     -------      -------
    |  1er |---->| 3eme |
    |______|     |______|
    Donc on veut que le lien "next" du 1er element soit le 3eme element. D'ou:

    previousa->next = currenta->next

  9. #9
    Invité1
    Invité(e)
    Par défaut
    Un dessin

    Merci!!!

  10. #10
    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 Alexandreg12 Voir le message
    Un dessin

    Merci!!!
    http://emmanuel-delahaye.developpez....s_chainees.htm

Discussions similaires

  1. Réponses: 2
    Dernier message: 28/05/2015, 17h28
  2. question sur les linked list
    Par yacin87 dans le forum Débuter avec Java
    Réponses: 3
    Dernier message: 11/04/2010, 22h04

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