Doppia implementazione di liste concatenate

Question

Vengo da un background C ++ e recentemente sono entrato in C, e una delle prime cose che ho fatto è stata una doppia lista concatenata poiché pensavo che sarebbe stata una buona pratica per me con i puntatori e l'allocazione della memoria. Tuttavia, non è troppo complesso, è solo con alcune funzioni di base.

Ecco la panoramica della mia lista:

#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);

Ha solo l'inserimento e la rimozione di base, oltre a funzioni di costruzione, distruttore, ordinamento e inversione.

Ecco la definizione effettiva delle funzioni:

#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;
    }
}

Ed ecco un piccolo esempio di come verrebbe utilizzato il mio elenco:

double_list* list = create_list();

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

sort_list(list);

destroy_list(list);

Le mie principali aree di preoccupazione sono:

1. Il costruttore e il distruttore stanno facendo il loro lavoro correttamente? Il distruttore perde la memoria e c'è un modo migliore per fare il costruttore?

2. Le funzioni remove()e insert()sono efficienti? C'è un modo migliore per farlo, come creare una remove()funzione più generica in modo da non dover avere casi di test speciali per l'indice 0 e cose del genere?

3. Sono il sort()e reverse()funzioni bene, almeno? So che l'ordinamento della selezione non è il miglior algoritmo da usare. E la reverse()funzione è implementata correttamente? C'è un modo migliore per invertire l'elenco?

Scusa se sono un po 'troppo generico con la mia domanda. Posso modificarlo per concentrarmi su una domanda più specifica, se necessario.

Grazie

Answer 1

Bella domanda, ben formattata, ben elaborata e l'implementazione sembra funzionare!

Il primo a rispondere alle tue domande:

Q1:

Costruttore:

• Controlla il valore di ritorno di malloc, potrebbe essere NULLse fallisse (memoria esaurita)

Distruttore:

• basta passare double_list *list, il constlà non ha senso (non sono sicuro del perché lo metti lì).
• perdi memoria, perché non liberi list, che hai allocato nel costruttore

Modifica 1:

Se si passa, double_list *const listsignifica che il valore di list (il puntatore) non può essere modificato, il che non ha senso qui perché l'utente di questa interfaccia mantiene il puntatore.

Se constè prima del tipo, const double_list *listsignifica che il contenuto di dove sta puntando l'elenco non può cambiare.

Ad esempio, se hai una funzione che accetta una stringa e desideri comunicare all'utente di questa funzione che il contenuto della stringa non cambierà, dovresti farlo void foo(const char *bar). Se la funzione è solo foo(char *bar)l'utente non può essere sicuro che il contenuto della stringa barsia lo stesso in seguito.

Q2:

• Non vedo alcun problema con le funzioni removee per insertquanto riguarda le prestazioni. L'inserto al centro sarà sempre O (n). Rimuovere / inserire in testa e coda è O (1) che ottieni nel tuo codice.
• Sarebbe un po 'più intuitivo se implementassi il semplice caso di rimuovere testa / coda nella funzione remove_front/ remove_backe usassi queste funzioni nella remove_posfunzione generica .

Q3:

ordinamento

• sort_list: quello che potresti fare è impostare un flag quando l'elenco è ordinato in modo che se viene ordinato di nuovo, è veloce (deseleziona il flag quando viene aggiunto un elemento)
• altrimenti non vedo alcun problema con l'implementazione dell'ordinamento

inversione

L'implementazione inversa della tua lista è O (n) ma poiché hai una lista doppiamente collegata puoi semplicemente usarla. Potresti avere due gruppi di operazioni nell'elenco, uno opera in avanti, l'altro al contrario. Ogni volta che reverse_listviene chiamato, cambierete il set di funzioni. Guarda l'esempio di seguito:

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;
}

Feedback più generale:

Nascondi le informazioni private

Hai perso alcuni dettagli nel file h. Probabilmente non vuoi che un utente della tua double_listlibreria possa fare confusione con i nodi, quindi dovresti nasconderlo e aggiungere funzioni per ottenere il valore. Il file h sarebbe simile al seguente:

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);

Rimuovere il const

Stai passando double_list* const list, cosa stai cercando di ottenere esattamente con il const?

Protezione di inclusione mancante

Dovresti aggiungere quanto segue:

#ifndef __DOUBLE_LIST_H__
#define __DOUBLE_LIST_H__

// snip

#endif

Rimuovere gli include nel file h

Gli include dovrebbero andare solo nei file c. Altrimenti puoi incorrere in inclusioni cicliche.

la stella del puntatore si attacca alla variabile

ad esempio non va bene: char* b

meglio: char *b

altrimenti sembra strano se hai la seguente dichiarazione:

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

Verificare la presenza di NULL

Controlla l' listargomento per NULL nelle funzioni

Verificare la presenza di NULL dopo l'allocazione

Quando assegni i nodi, dovresti anche controllare se vengono mallocrestituiti NULL.

Test

Quando aggiungi alla tua lista, aggiungi l'elemento in ordine 1,2,3, quindi sort_listnon sta facendo molto.

Denominazione delle funzioni

Quando si tratta di denominare le funzioni, sicuramente dipende dai gusti personali, ma mi atterrei a espressioni comuni. Ad esempio, backe frontsono un po 'rari, penso heade taildescrivo meglio a cosa servono le funzioni.

Inoltre rende la tua interfaccia un po 'più pulita se li chiami in modo coerente

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()

Fammi solo sapere se qualcosa non è chiaro, codereview ha "dimenticato" metà del mio testo così mi sono affrettato un po 'a scriverlo di nuovo.

Answer 2

riguardo a:

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

La maggior parte dei debugger utilizza il nome "tag" di una struttura per poter accedere ai singoli campi. Suggerisci di inserire un nome "tag"

la main()funzione è mancante. Forse è lì che effettueresti le chiamate:

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

suggerisco vivamente di mantenere la lista ordinata in "insert ()" piuttosto che come un'operazione separata

Answer 3

Tratterei Nodecome una classe, come hai fatto tu con double_list. Cioè creare funzioni node_create(), node_destroy()ecc.
Lascia che le node_...()funzioni modifichino / controllino il contenuto del nodo.