Критиковать моя реализация связанных списков


Я бы признателен за любые и все критики об этом коде. У меня не было конкретного случая использования в виду, когда я писал это, я просто хотел попробовать реализация связанных списков. Мои комментарии не очень полезно, я думаю. Я не очень опытный программист, поэтому там, наверное, много вещей, я мог бы улучшить или исправить здесь.

Вот заголовочный файл:

// llist.h
#ifndef LLIST_H_
#define LLIST_H_

struct LList;
typedef struct LList LList;

struct LLNode;
typedef struct LLNode LLNode;

struct LList {
    LLNode *front, *back;
};

struct LLNode {
    void *data;
    LLNode *next;
};

LList* llist_new(LList **self);
void llist_add(LList *self, void *v);
void llist_remove(LList *self, LLNode *node);
void llist_insert(LLNode *node, void *v);
void llist_destroy(LList *self);

#endif

Вот .файл c:

// llist.c
#include <assert.h>
#include <stdlib.h>

#include "llist.h"

// Initialize a new, empty LList, in dynamically allocated memory.
LList *llist_new(LList **self) {
    *self = malloc(sizeof (LList));
    if (self == NULL) { return NULL; }

    (*self)->front = NULL;
    (*self)->back = NULL;

    return *self;
}


// Append a value to the LList.  Creates a new node.
void llist_add(LList *self, void *v) {
    LLNode *node = malloc(sizeof (LLNode));
    assert(node != NULL);

    node->data = v;
    node->next = NULL;

    // Put this node at the back of the list.
    if (self->front != NULL) {
        self->back->next = node;
        self->back = node;
    } else {
        self->back = node;
        self->front = node;
    }
}


// Iterate over the LList to locate a node, and then remove it from the list.
void llist_remove(LList *self, LLNode *node) {
    LLNode *iter_node = self->front;
    LLNode *prev_node = NULL;

    while (iter_node != NULL) {
        if (iter_node == node) {
            if (prev_node != NULL) { prev_node->next = iter_node->next; }
            else { self->front = NULL; }
            free(iter_node);
            return;
        }
        prev_node = iter_node;
        iter_node = iter_node->next;
    }

}


// Insert a value after a particular node.
void llist_insert(LLNode *node, void *v) {
    LLNode *next = node->next;
    LLNode *new_node = malloc(sizeof (LLNode));

    new_node->data = v;
    new_node->next = next;

    node->next = new_node;
}


void llist_destroy(LList *self) {
    LLNode *iter_node = self->front;

    while (iter_node != NULL) {
        LLNode *next = iter_node->next;
        free(iter_node);
        iter_node = next;
    }

    free(self);
}


420
3
задан 20 августа 2011 в 12:08 Источник Поделиться
Комментарии
2 ответа

// Initialize a new, empty LList, in dynamically allocated memory.
LList *llist_new(LList **self) {

Его странное возвращение в новый список, как возвращение значению и по ссылке.

    *self = malloc(sizeof (LList));
if (self == NULL) { return NULL; }

Делать эту проверку после того, как вы уже разыменован себя, кажется, довольно бессмысленно. Возможно, вы имели в виду *я?

    (*self)->front = NULL;
(*self)->back = NULL;

return *self;
}

// Append a value to the LList. Creates a new node.
void llist_add(LList *self, void *v) {
LLNode *node = malloc(sizeof (LLNode));
assert(node != NULL);

node->data = v;
node->next = NULL;

// Put this node at the back of the list.
if (self->front != NULL) {

Я хотел добавить комментарий, чтобы объяснить, что имея собственн->передний null означает.

        self->back->next = node;
self->back = node;
} else {
self->back = node;
self->front = node;
}
}

// Iterate over the LList to locate a node, and then remove it from the list.
void llist_remove(LList *self, LLNode *node) {
LLNode *iter_node = self->front;
LLNode *prev_node = NULL;

while (iter_node != NULL) {
if (iter_node == node) {
if (prev_node != NULL) { prev_node->next = iter_node->next; }
else { self->front = NULL; }

Я думаю, что класть блоки на одной строке, как это делает его труднее читать. Я тоже думаю, что сбой при удалении первого узла.

            free(iter_node);
return;
}
prev_node = iter_node;
iter_node = iter_node->next;
}

}

// Insert a value after a particular node.
void llist_insert(LLNode *node, void *v) {
LLNode *next = node->next;
LLNode *new_node = malloc(sizeof (LLNode));

new_node->data = v;
new_node->next = next;

Почему у тебя локальная переменная. Это, кажется, не помогли сделать код понятнее.

    node->next = new_node;
}

void llist_destroy(LList *self) {
LLNode *iter_node = self->front;

while (iter_node != NULL) {
LLNode *next = iter_node->next;
free(iter_node);
iter_node = next;
}

free(self);
}

2
ответ дан 20 августа 2011 в 12:08 Источник Поделиться

Кажется хорошим:

В llist_new() я бы не передать параметр.
Это не делает интерфейс удобнее в использовании, но это добавляет сложности к тестам.

LList *llist_new(LList **self) {

Просто сделать это:

LList *llist_new()

Winsoton указал, что проверка самостоятельно после распределения было бессмысленно.
Это правда. Но я думаю, вы проверяли, чтобы увидеть, если значение, возвращаемое из функции malloc() значение null. Если это так, то вы забыли де-ссылка здесь:

if (self == NULL) { return NULL; }

Я думаю, что вы хотели

if ((*self) == NULL) { return NULL; }
// ^^ De-reference to check if malloc() worked.

Примечание: Если вы измените интерфейс этой проблемы отпадают, поскольку у вас нет ** параметр в первую очередь.

В llist_add() если вы собираетесь заявить (), что узел был создан, вы также должны убедиться, что входной параметр действителен. Как llist_new() может вернуть null, если функция malloc() завершается неудачей. Так что вы, вероятно, следует утверждать на Добавить если само значение null (вы должны действительно ссэч кон все интерфейсы, чтобы убедиться в собственной не null).

void llist_add(LList *self, void *v)
{
assert(self != NULL);

LLNode *node = malloc(sizeof (LLNode));
assert(node != NULL);

Я согласен с Уинстоном, что вы должны использовать более явные отступы на если сделать его читаемым:

        if (prev_node != NULL)
{ prev_node->next = iter_node->next;
}
else
{ self->front = iter_node->next;
} // ^^^^^^^^^^^^^^^^ Fix this

Также задание не должно быть null, но должен назначить нового главу списка.

Также интерфейс для удаления элементов занимает указатель LLNode. Но никакой другой интерфейс предоставляет вам указатель LLNode. Так что вы застряли в ситуации с курицей и яйцом и не в состоянии использовать интерфейс.

void llist_remove(LList *self, LLNode *node) {

1
ответ дан 20 августа 2011 в 02:08 Источник Поделиться