Doppelte Implementierung einer verknüpften Liste

Question

Ich komme aus einem C ++ - Hintergrund und bin kürzlich zu C gekommen. Eines der ersten Dinge, die ich gemacht habe, war eine doppelt verknüpfte Liste, da ich dachte, es wäre eine gute Praxis für mich mit Zeigern und Speicherzuweisung. Es ist jedoch nicht zu komplex, es enthält nur einige Grundfunktionen.

Hier ist die Übersicht meiner 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);

Es verfügt lediglich über grundlegende Funktionen zum Einfügen und Entfernen sowie über Konstruktor-, Destruktor-, Sortier- und Umkehrfunktionen.

Hier ist die eigentliche Definition für die Funktionen:

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

Und hier ist eine kleine Auswahl, wie meine Liste verwendet werden würde:

double_list* list = create_list();

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

sort_list(list);

destroy_list(list);

Mein Hauptanliegen sind:

1. Machen der Konstruktor und der Destruktor ihre Arbeit richtig? Verliert der Destruktor Speicher und gibt es eine bessere Möglichkeit, den Konstruktor auszuführen?

2. Sind die remove()und insert()Funktionen effizient? Gibt es eine bessere Möglichkeit, dies zu tun, als eine allgemeinere remove()Funktion zu erstellen , damit ich keine speziellen Testfälle für den Index 0 und ähnliches haben muss?

3. Sind die sort()und reverse()Funktionen zumindest in Ordnung? Ich weiß, dass die Auswahlsortierung nicht der beste Algorithmus ist. Und ist die reverse()Funktion korrekt implementiert? Gibt es eine bessere Möglichkeit, die Liste umzukehren?

Tut mir leid, dass ich mit meiner Frage etwas zu weit gefasst bin. Ich kann es bearbeiten, um mich bei Bedarf auf eine spezifischere Frage zu konzentrieren.

Vielen Dank

Answer 1

Gute Frage, gut formatiert, gut ausgearbeitet und die Implementierung scheint zu funktionieren!

Beantworten Sie zuerst Ihre Fragen:

Q1:

Konstrukteur:

• Überprüfen Sie den Rückgabewert von malloc. Dies kann der Fall sein, NULLwenn ein Fehler aufgetreten ist (nicht genügend Speicher).

Zerstörer:

• Pass einfach vorbei double_list *list, das constmacht keinen Sinn (nicht sicher, warum du es dort hingelegt hast).
• Sie verlieren Speicher, weil Sie nicht freigeben list, was Sie im Konstruktor zugewiesen haben

Bearbeiten 1:

Wenn Sie übergeben double_list *const list, bedeutet dies, dass der Wert von list (der Zeiger) nicht geändert werden kann, was hier nicht sinnvoll ist, da der Benutzer dieser Schnittstelle am Zeiger festhält.

Wenn das constvor dem Typ steht, const double_list *listbedeutet dies, dass sich der Inhalt der Liste nicht ändern kann.

Wenn Sie beispielsweise eine Funktion haben, die eine Zeichenfolge akzeptiert, und dem Benutzer dieser Funktion mitteilen möchten, dass sich der Inhalt der Zeichenfolge nicht ändern wird, sollten Sie dies tun void foo(const char *bar). Wenn die Funktion nur ist, kann foo(char *bar)der Benutzer nicht sicher sein, dass der Inhalt der Zeichenfolge danach barimmer noch der gleiche ist.

Q2:

• Ich sehe keine Probleme mit den removeund insertFunktionen in Bezug auf die Leistung. In der Mitte einfügen wird immer O (n) sein. Das Entfernen / Einfügen an Kopf und Schwanz ist O (1), das Sie in Ihrem Code erreichen.
• Es wäre etwas intuitiver, wenn Sie den einfachen Fall des Entfernens von Kopf / Schwanz in der Funktion remove_front/ implementieren remove_backund diese Funktionen in der generischen remove_posFunktion verwenden würden.

Q3:

Sortierung

• sort_list: Was Sie tun können, ist ein Flag zu setzen, wenn die Liste bestellt wird, so dass es schnell ist, wenn es erneut bestellt wird (deaktivieren Sie das Flag, wenn ein Element hinzugefügt wird)
• Ansonsten sehe ich keine Probleme mit der Sortierimplementierung

umkehren

Ihre Listenumkehrimplementierung ist O (n), aber da Sie eine doppelt verknüpfte Liste haben, können Sie diese einfach verwenden. Sie können zwei Arten von Operationen in der Liste haben, eine in Vorwärtsrichtung und die andere in Rückwärtsrichtung. Wann immer das reverse_listaufgerufen wird, würden Sie den Funktionssatz tauschen. Siehe das folgende Beispiel:

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

Allgemeineres Feedback:

Private Informationen ausblenden

Sie verlieren einige der Details in der h-Datei. Sie möchten wahrscheinlich nicht, dass ein Benutzer Ihrer double_listBibliothek mit den Knoten herumspielen kann. Deshalb sollten Sie sie ausblenden und Funktionen hinzufügen, um den Wert zu erhalten. Die h-Datei würde wie folgt aussehen:

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

Entfernen Sie die const

Sie gehen vorbei double_list* const list, was genau versuchen Sie mit dem zu erreichen const?

Einschlussschutz fehlt

Sie sollten Folgendes hinzufügen:

#ifndef __DOUBLE_LIST_H__
#define __DOUBLE_LIST_H__

// snip

#endif

Entfernen Sie die Includes in der h-Datei

Die Includes sollten nur in den c-Dateien enthalten sein. Andernfalls können Sie auf zyklische Einschlüsse stoßen.

Der Zeigerstern bleibt bei der Variablen

zB nicht gut: char* b

besser: char *b

Ansonsten sieht es komisch aus, wenn Sie folgende Erklärung haben:

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

Auf NULL prüfen

Überprüfen Sie das listArgument für NULL in den Funktionen

Nach der Zuweisung auf NULL prüfen

Wenn Sie die Knoten zuweisen, sollten Sie auch prüfen, ob sie malloczurückgegeben werden NULL.

Testen

Wenn Sie zu Ihrer Liste hinzufügen, fügen Sie das Element in der Reihenfolge 1,2,3 hinzu, sodass Sie sort_listnicht viel tun.

Benennung der Funktionen

Wenn es um Namensfunktionen geht, kommt es sicherlich auf den persönlichen Geschmack an, aber ich würde mich an gebräuchliche Ausdrücke halten. Zum Beispiel backund frontsind etwas ungewöhnlich, ich denke headund tailbeschreibe besser, was die Funktionen zu tun haben.

Außerdem wird Ihre Benutzeroberfläche dadurch etwas sauberer, wenn Sie sie konsistent benennen

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

Lassen Sie mich einfach wissen, wenn etwas unklar ist. Codereview hat die Hälfte meines Textes "vergessen", also habe ich ihn ein wenig beschleunigt, um ihn erneut aufzuschreiben.

Answer 2

hinsichtlich:

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

Die meisten Debugger verwenden den Tag-Namen einer Struktur, um auf die einzelnen Felder zugreifen zu können. Schlagen Sie vor, einen Tag-Namen einzufügen

Die main()Funktion fehlt. Vielleicht würden Sie dort die Anrufe tätigen:

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

Es wird dringend empfohlen, die Liste nach 'insert ()' und nicht als separate Operation zu sortieren

Answer 3

Ich würde Nodewie Sie als Klasse behandeln double_list. Dh erstellen Funktionen node_create(), node_destroy()usw.
Lassen node_...()Funktionen ändern / geistige Gesundheit des Knotens Inhalt überprüfen.