时间戳

首页 > 解决方案 > C中的单链表：pushBack

c - C中的单链表：pushBack

问题描述

我必须创建将元素添加到列表末尾的 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 方法中的任何更正将不胜感激。

标签： c

解决方案

关于您当前的代码：

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

推荐阅读