односвязный список в C: pushBack

Question

Мне нужно создать метод pushBack, который добавит элемент в конец моего списка, но реализуемый им метод pushBack не работает. Ниже я оставляю код:

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

typedef struct
{
    int *data;
    struct Node *next;
}Node;

typedef struct
{
    // Puntero al primer nodo
    Node *head;
    // Cantidad de datos
    unsigned short size;
    // Puntero al ultimo dato accedido.
    Node *current;
}List;

List *createList();
Node *createNode(int *);
void pushBack(List *, int *);

int main(void)
{
    List *lista = createList();
    pushBack(&lista, 4);
    return 0;
}


List *createList()
{
    List *list = (List *) malloc(sizeof(List));
    list -> head = NULL;
    list -> size = 0;
    list -> current = NULL;
    return list;
}

Node *createNode(int *data)
{
    Node *node = (Node *) malloc(sizeof(Node));
    node -> data = data;
    node -> next = NULL;
    return node;
}
// Función para insertar un nuevo nodo al final de la lista
void pushBack(List *list, int *data)
{
    Node *node = createNode(data);
    while ( list -> head )
        list -> head = list -> head -> next;
    list -> head = node;
    list -> size ++;
}

любая поправка в методе pushBack будет принята с благодарностью.

Answer 1

Относительно вашего текущего кода:

void pushBack(List *list, int *data)
{
    Node *node = createNode(data);
    while ( list -> head )
        list -> head = list -> head -> next;
    list -> head = node;
    list -> size ++;
}

Нажатие чего-либо в конец списка должно только изменить заголовок , если список ранее был пустым. То, что вы делаете, на самом деле портит список, перемещая его туда, где не должно быть.

Вы возможно имели в виду использовать current вместо head (после первой установки, конечно, на head), но для этого необычно выделять поле для этого в самом списке - вы обычно просто используют временную переменную.

Вам было бы гораздо лучше хранить хвост, чтобы вам не приходилось искать его каждый раз ^(a) . Но, предполагая, что это не вариант, следующий псевдокод должен помочь вам:

def push_back(list, item):
    # Force tail constraints, new tail must be end of list.

    item.next = null

    # If list empty, simply set head.

    if list.head == null:
        list.head = item
        return

    # Find last element in list:

    curr = list.head
    while curr.next != null:
        curr = curr.next

    # Now have last, just attach new item to it.

    curr.next = item

Превратив это в C, я оставлю это упражнение для читателя. Вы должны делать по крайней мере некоторые вашей домашней работы: -)

---

^(a) Если вам интересно, как это сделать, см. Ниже:

def push_back(list, item):
    # Force tail constraints, new tail must be end of list.

    item.next = null

    # If list empty, simply set head/tail.

    if list.head == null:
        list.head = item
        list.tail = item
        return

    # In non-empty list, tail will always be last element.

    curr.tail.next = item   # Point current tail to new tail.
    curr.tail = item        # Update tail