Implémentation de liste double chaînée

Question

Je viens d'un arrière-plan C ++, et je suis récemment entré dans C, et l'une des premières choses que j'ai faites était une double liste chaînée car je pensais que ce serait une bonne pratique pour moi avec les pointeurs et l'allocation de mémoire. Ce n'est pas trop complexe cependant, c'est juste avec quelques fonctions de base.

Voici l'aperçu de ma liste:

#include <stdlib.h>
#include <stdio.h>

typedef struct Node
{
    int val;
    struct Node* prev;
    struct Node* next;
} Node;

typedef struct
{
    int length;
    Node* head;
    Node* tail;
} double_list;

double_list* create_list(); // constructor
void destroy_list(double_list* const list); // destructor

void insert_pos(double_list* const list, int index, int val);
void insert_front(double_list* const list, int val);
void insert_back(double_list* const list, int val);

void remove_pos(double_list* const list, int index);
void remove_front(double_list* const list);
void remove_back(double_list* const list);

void sort_list(double_list* const list); // selection sort
void reverse_list(double_list* const list);

Il a juste une insertion et une suppression de base, ainsi qu'un constructeur, un destructeur, un tri et des fonctions inverses.

Voici la définition réelle des fonctions:

#include <stdlib.h>
#include <stdio.h>

typedef struct Node
{
    int val;
    struct Node* prev;
    struct Node* next;
} Node;

typedef struct
{
    int length;
    Node* head;
    Node* tail;
} double_list;

double_list* create_list()
{
    double_list* list = malloc(sizeof(*list));

    list->length = 0;
    list->head = NULL;
    list->tail = NULL;

    return list;
}

void destroy_list(double_list* const list)
{
    list->length = 0;

    Node* node_ptr = list->head;
    while (node_ptr != NULL)
    {
        node_ptr = node_ptr->next;
        free(list->head);
        list->head = node_ptr;
    }
}

void insert_pos(double_list* const list, int index, int val)
{
    if (index < 0 || index > list->length)
        return;

    list->length += 1;

    if (list->head == NULL)
    {
        list->head = malloc(sizeof(*(list->head)));

        list->head->val = val;
        list->head->prev = NULL;
        list->head->next = NULL;

        list->tail = list->head;

        return;
    }

    if (index == 0)
    {
        Node* new_node = malloc(sizeof(*new_node));

        new_node->val = val;
        new_node->prev = NULL;
        new_node->next = list->head;

        list->head->prev = new_node;
        list->head = new_node;

        return;
    }

    if (index == list->length - 1)
    {
        Node* new_node = malloc(sizeof(*new_node));

        new_node->val = val;
        new_node->prev = list->tail;
        new_node->next = NULL;

        list->tail->next = new_node;
        list->tail = new_node;

        return;
    }
    
    Node* node_ptr = list->head;
    for (int a = 0; a < index; ++a)
        node_ptr = node_ptr->next;

    Node* new_node = malloc(sizeof(*new_node));

    new_node->val = val;
    new_node->next = node_ptr;
    new_node->prev = node_ptr->prev;

    node_ptr->prev->next = new_node;
    node_ptr->prev = new_node;
}

void insert_front(double_list* const list, int val)
{
    insert_pos(list, 0, val);
}

void insert_back(double_list* const list, int val)
{
    insert_pos(list, list->length, val);
}

void remove_pos(double_list* const list, int index)
{
    if (index < 0 || index >= list->length)
        return;

    list->length -= 1;

    if (index == 0)
    {
        Node* node_ptr = list->head;
        list->head = list->head->next;
        list->head->prev = NULL;

        free(node_ptr);
        return;
    }

    if (index == list->length)
    {
        Node* node_ptr = list->tail;
        list->tail = list->tail->prev;
        list->tail->next = NULL;

        free(node_ptr);
        return;
    }
    
    Node* node_ptr = list->head;
    for (int a = 0; a < index; ++a)
        node_ptr = node_ptr->next;

    node_ptr->prev->next = node_ptr->next;
    node_ptr->next->prev = node_ptr->prev;

    free(node_ptr);
}

void remove_front(double_list* const list)
{
    remove_pos(list, 0);
}

void remove_back(double_list* const list)
{
    remove_pos(list, list->length - 1);
}

void sort_list(double_list* const list)
{
    Node* index_ptr = list->head;
    Node* small_ptr = list->head;
    Node* node_ptr = list->head;
    while (index_ptr->next != NULL)
    {
        while (node_ptr != NULL)
        {
            if (node_ptr->val < small_ptr->val)
                small_ptr = node_ptr;

            node_ptr = node_ptr->next;
        }

        int hold = index_ptr->val;
        index_ptr->val = small_ptr->val;
        small_ptr->val = hold;

        index_ptr = index_ptr->next;
        node_ptr = index_ptr;
        small_ptr = index_ptr;
    }
}

void reverse_list(double_list* const list)
{
    Node* node_ptr = list->head;

    list->head = list->tail;
    list->tail = node_ptr;

    while (node_ptr != NULL)
    {
        Node* temp = node_ptr->prev;
        node_ptr->prev = node_ptr->next;
        node_ptr->next = temp;

        node_ptr = node_ptr->prev;
    }
}

Et voici un petit échantillon de la façon dont ma liste serait utilisée:

double_list* list = create_list();

insert_back(list, 1);
insert_back(list, 2);
insert_back(list, 3);

sort_list(list);

destroy_list(list);

Mes principaux sujets de préoccupation sont:

1. Le constructeur et le destructeur font-ils correctement leur travail? Le destructeur perd-il de la mémoire et existe-t-il une meilleure façon de faire le constructeur?

2. Les fonctions remove()et insert()sont-elles efficaces? Y a-t-il une meilleure façon de faire cela, comme créer une remove()fonction plus générique pour ne pas avoir à avoir de cas de test spéciaux pour un index de 0 et des trucs comme ça?

3. Les fonctions sort()et reverse()sont-elles au moins correctes? Je sais que le tri par sélection n'est pas le meilleur algorithme à utiliser. Et la reverse()fonction est-elle correctement implémentée? Existe-t-il une meilleure façon d'inverser la liste?

Désolé, je suis un peu trop large avec ma question. Je peux le modifier pour me concentrer sur une question plus spécifique si nécessaire.

Merci

Answer 1

Bonne question, bien formatée, bien élaborée et la mise en œuvre semble fonctionner!

Tout d'abord pour répondre à vos questions:

Q1:

Constructeur:

• Vérifiez la valeur de retour de malloc, cela pourrait être en NULLcas d'échec (mémoire insuffisante)

Destructeur:

• il suffit de passer double_list *list, constil n'a pas de sens (je ne sais pas pourquoi vous le mettez là).
• vous perdez de la mémoire, car vous ne la libérez pas list, que vous avez allouée dans le constructeur

Modifier 1:

Si vous passez double_list *const listcela signifie que la valeur de list (le pointeur) ne peut pas être modifiée, ce qui n'a pas de sens ici car l'utilisateur de cette interface tient le pointeur.

Si le constest avant le type, const double_list *listcela signifie que le contenu de l'endroit où la liste pointe ne peut pas changer.

Par exemple, si vous avez une fonction qui prend une chaîne et que vous souhaitez communiquer à l'utilisateur de cette fonction que le contenu de la chaîne ne va pas changer, vous devez le faire void foo(const char *bar). Si la fonction est uniquement, foo(char *bar)l'utilisateur ne peut pas être sûr que le contenu de la chaîne barest toujours le même par la suite.

Q2:

• Je ne vois aucun problème avec les fonctions removeet insertconcernant les performances. L'insertion au milieu sera toujours O (n). Retirer / insérer en tête et en queue est O (1) que vous obtenez dans votre code.
• Ce serait un peu plus intuitif si vous implémentiez le cas simple de la suppression de la tête / queue dans la fonction remove_front/ remove_backet utilisiez ces fonctions dans la remove_posfonction générique .

Q3:

tri

• sort_list: ce que vous pouvez faire est de définir un drapeau lorsque la liste est ordonnée afin que si elle est à nouveau commandée, ce soit rapide (désélectionner le drapeau lorsqu'un élément est ajouté)
• sinon je ne vois aucun problème avec l'implémentation du tri

inverser

L'implémentation inverse de votre liste est O (n) mais puisque vous avez une liste doublement liée, vous pouvez simplement l'utiliser. Vous pourriez avoir deux ensembles d'opérations sur la liste, l'un fonctionne dans le sens avant, l'autre dans le sens inverse. Chaque fois que le reverse_listest appelé, vous permutez l'ensemble de fonctions. Voir l'exemple ci-dessous:

struct list_operations
{
    void (*insert_front)(double_list* const list, int val);
    // more functions
};

static const struct list_operations list_operations_forward = 
{
    .insert_front = insert_front_forward,
    // more functions
};

static const struct list_operations list_operations_reverse = 
{
    .insert_front = insert_front_reverse,
    // more functions
};

void reverse_list(double_list* list)
{
    if (NULL == list)
    {
        return
    }

    list->operations = (list->operations == &list_operations_forward)?&list_operations_reverse:&list_operations_forward;
}

Commentaires plus généraux:

Masquer les informations privées

Vous perdez certains des détails dans le fichier h. Vous ne voulez probablement pas qu'un utilisateur de votre double_listbibliothèque puisse jouer avec les nœuds, vous devriez donc le cacher et ajouter des fonctions pour obtenir la valeur. Le fichier h ressemblerait à ceci:

typedef struct double_list_s double_list_t;

double_list* create_list();
void destroy_list(double_list* list);

void insert_pos(double_list *list, int index, int val);
void insert_front(double_list *list, int val);
void insert_back(double_list *list, int val);

void remove_pos(double_list *list, int index);
void remove_front(double_list *list);
void remove_back(double_list *list);

int get_pos(double_list *list, pos);
int get_front(double_list *list);
int get_back(double_list *list);

void sort_list(double_list *list); // selection sort
void reverse_list(double_list *list);

Supprimer le const

Vous double_list* const listpassez, qu'essayez-vous exactement de réaliser avec le const?

Protection d'inclusion manquante

Vous devez ajouter ce qui suit:

#ifndef __DOUBLE_LIST_H__
#define __DOUBLE_LIST_H__

// snip

#endif

Supprimer les inclus dans le fichier h

Les inclusions ne doivent figurer que dans les fichiers c. Sinon, vous pouvez rencontrer des inclusions cycliques.

l'étoile du pointeur colle à la variable

par exemple pas bon: char* b

meilleur: char *b

sinon, cela semble bizarre si vous avez la déclaration suivante:

char* b, *avs ( char *b, *a)

Vérifier NULL

Vérifiez l' listargument NULL dans les fonctions

Vérifiez NULL après l'allocation

Lorsque vous allouez les nœuds, vous devez également vérifier s'ils sont mallocretournés NULL.

Essai

Lorsque vous ajoutez à votre liste, vous ajoutez l'élément dans l'ordre 1, 2, 3, donc sort_listne fait pas grand-chose.

Nommer les fonctions

Quand il s'agit de nommer des fonctions, cela dépend certainement de vos goûts personnels, mais je m'en tiendrai à des expressions courantes. Par exemple backet frontsont un peu rares, je pense headet taildécris mieux ce que les fonctions à.

De plus, cela rend votre interface un peu plus propre si vous les nommez de manière cohérente

list_create()
list_destroy()

list_pos_insert()
list_head_insert()
list_tail_insert()

list_pos_remove()
list_head_remove()
list_tail_remove()

list_sort()
list_reverse()

Faites-moi savoir si quelque chose n'est pas clair, codereview a "oublié" la moitié de mon texte, alors je me suis précipité un peu pour l'écrire à nouveau.

Answer 2

En ce qui concerne:

typedef struct
{
    int length;
    Node* head;
    Node* tail;
} double_list;

La plupart des débogueurs utilisent le nom 'tag' d'une structure pour pouvoir accéder aux champs individuels. Suggérer d'insérer un nom de «tag»

la main()fonction est manquante. C'est peut-être là que vous passeriez les appels:

double_list* list = create_list();
insert_back(list, 1);
insert_back(list, 2);
insert_back(list, 3);
sort_list(list);
destroy_list(list);

suggère fortement de garder la liste triée à 'insert ()' plutôt que comme une opération séparée

Answer 3

Je traiterais Nodecomme une classe, comme vous l'avez fait avec double_list. Ie créer des fonctions node_create(), node_destroy()etc.
Laissez les node_...()fonctions modifier / sanity vérifier le contenu du nœud.