Batch Index du Forum
S’enregistrerRechercherFAQMembresGroupesConnexion
Répondre au sujet Page 1 sur 1
[C] Fast Linked List
Auteur Message
Répondre en citant
Message [C] Fast Linked List 
Bonjour, ceci est une "micro" librairie qui est très utile pour ceux qui font du C.

Une linked list, est une liste chaînée, dans mon cas, c'est une liste à sens unique (singly linked list en Anglais).
Elle peut servir pour résoudre divers problèmes comme l'allocation est dynamique.

Pour ce genre de chose, il y a d'innombrables implémentations existantes mais elles ne sont pas parfaites pour moi, donc je décide d'en faire une moi-même.
Exemples d'implémentations existantes :
- Implémentation de carlos (créateur de BG.exe) : http://consolesoft.com/c_structures/linked_list/slinkedlist.c
Cette implémentation supporte les listes chaînés circulaires.
- Implémentation de DarkBatcher (créateur de batbox) : https://sourceforge.net/p/dos9/code/ci/master/tree/libDos9/stack/Dos9_Stack…
Ce n'est pas le même type de liste chaîné, mais ça reste quand même une liste chaînée, c'est plus précisément une pile (stack).
- Une implémentation prise sur internet : http://www.cprogramming.com/snippets/source-code/singly-linked-list-insert-…
Cette implémentation est pas vraiment claire (je dirais une liste bidirectionnelle).

Donc voici ma version Mr. Green Okay :

Code:
[lang=c]/*
    Copyright (c) 2016 Teddy ASTIE (TSnake41)

    Permission is hereby granted, free of charge, to any person obtaining a copy
    of this software and associated documentation files (the "Software"), to deal
    in the Software without restriction, including without limitation the rights
    to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
    copies of the Software, and to permit persons to whom the Software is
    furnished to do so, subject to the following conditions:

    The above copyright notice and this permission notice shall be included in all
    copies or substantial portions of the Software.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
    SOFTWARE.
*/

/* Fast simple linked list implementation */

#include <stdlib.h>
#include "fllist.h"

llist_t ll_add_item(llist_t llist, void *value)
{
    llist_t base = llist;

    while (base && llist->next)
        llist = llist->next;

    llist_t node = malloc(sizeof(struct linked_list));

    node->next = NULL;
    node->value = value;

    if (base)
        llist->next = node;
    else
        base = node;

    return base;
}

llist_t ll_goto_next(llist_t llist)
{
    if (!llist->next)
        return NULL;

    llist_t new_node = llist->next;
    free(llist);

    return new_node;
}

int ll_get_count(llist_t llist)
{
    if (!llist)
        return 0;

    int i = 1;

    while (llist = llist->next)
        i++;

    return i;
}
Code:
[lang=c]/*
    Copyright (c) 2016 Teddy ASTIE (TSnake41)

    Permission is hereby granted, free of charge, to any person obtaining a copy
    of this software and associated documentation files (the "Software"), to deal
    in the Software without restriction, including without limitation the rights
    to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
    copies of the Software, and to permit persons to whom the Software is
    furnished to do so, subject to the following conditions:

    The above copyright notice and this permission notice shall be included in all
    copies or substantial portions of the Software.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
    SOFTWARE.
*/

#ifndef H_FLLIST
#define H_FLLIST

typedef struct linked_list {
    struct linked_list *next;
    void *value;
} *llist_t;

/* Add an item to the linked list. */
llist_t ll_add_item(llist_t llist, void *value);

/* Go to next node, return NULL if there is no node next. */
llist_t ll_goto_next(llist_t llist);

/* Get the count of items in the linked list. */
int ll_get_count(llist_t llist);

#endif /* H_LLIST */


Plutôt simple non (si on compare avec les autres) ?

Si vous voulez tester :
Code:
[lang=c]#include <stdio.h>
#include "fllist.h"

int main()
{
    int values[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    llist_t linked_list = NULL;

    for (size_t i = 0; i < 9; i++)
        linked_list = ll_add_item(linked_list, &values[i]);

    printf("Initial elements count : %d\n", ll_get_count(linked_list));

    do
        printf("%d\n", *(int*)linked_list->value);
    while (linked_list = ll_goto_next(linked_list));

    printf("Last elements count : %d\n", ll_get_count(linked_list));

    return 0;
}
Sortie :
Citation:
Initial elements count : 9
1
2
3
4
5
6
7
8
9
Last elements count : 0
Pour ceux a qui ça intéresse :
- Il n'y a pas de réelle "liste", tout ce qui est une liste est en réalité un noeud.
- Lorsque que l'on fait 'll_goto_next', l'ancien noeud est désalloué (ll_add_item en alloue un puis l'ajoute).
- L'implémentation est simple elle peut donc être efficacement intégrée puis utilisée dans une commande externe Okay.

Son utilisation :
Code:
[lang=c]llist_t ma_list = NULL;
Crée une liste.

Code:
[lang=c]ma_liste->value
Récupère la valeur du nœud actuel.

Code:
[lang=c]llist_t ll_add_item(llist_t llist, void *value)
Ajoute à la chaîne une valeur.

Code:
[lang=c]llist_t ll_goto_next(llist_t llist)
Passe au prochain noeud de la liste, désalloue l'ancien.

Code:
[lang=c]int ll_get_count(llist_t llist)
Récupère le nombre de noeud dans la liste.

Voici le lien de téléchargement avec l'exemple (compilé) et le code source : https://up.nerdby.net/#zE5jmkAn46olJf_Fm99r8Q
Si vous avez la moindre question, n'hésitez pas.




______________________________________________________
Partager permet le savoir. Le savoir permet de partager de nouveau savoirs.
Message Publicité 
PublicitéSupprimer les publicités ?


Montrer les messages depuis:
Répondre au sujet Page 1 sur 1
  



Index | créer un forum | Forum gratuit d’entraide | Annuaire des forums gratuits | Signaler une violation | Conditions générales d'utilisation
Copyright 2008 - 2016 // Batch