0

昨天我试图实现一个链接列表，虽然它有效并且我“有点”理解，但它让我的大脑有点煎熬。

这里的函数 addNode() 有什么问题？

#include <stdio.h>

struct Node
{
    int value;
    struct Node *next;
};

struct Node *createList();
void addNode(struct Node* head, int value); // Adds Node directly after head
void viewList(struct Node *head); // Outputs list starting from head

int main()
{
    struct Node *head = createList();

    addNode(head, 10);
    addNode(head, 8);
    addNode(head, 23);
    addNode(head, 5);
    addNode(head, 4);
    addNode(head, 4100);


    viewList(head); // I didn't upload here to save space

    return 0;
}

struct Node *createList()
{ 
    struct Node *head = (struct Node *) malloc(sizeof(struct Node));
    head = NULL;
    return head;
}

void addNode(struct Node* head, int value)
{
    if(head == NULL)
    {
        struct Node *tmp = (struct Node *) malloc(sizeof(struct Node));
        tmp->value = value;
        tmp->next = head;
        head = tmp;
    }

    else
    {
        struct Node *newNode = (struct Node *) malloc(sizeof(struct Node));
        newNode->value = value;
        newNode->next = head;
        head = newNode;
    }
}

我感到困惑的原因是因为那个版本的添加节点没有工作，而这个版本......

void addNode(struct Node** head, int value)
{
    if(*head == NULL)
    {
        struct Node *tmp = (struct Node *) malloc(sizeof(struct Node));
        tmp->value = value;
        tmp->next = *head;
        *head = tmp;
    }

    else
    {
        struct Node *newNode = (struct Node *) malloc(sizeof(struct Node));
        newNode->value = value;
        newNode->next = *head;
        *head = newNode;
    }
}

并在主函数中使用头节点指针前面的 & 号调用

addNode(&head, 10);

也让我感到困惑的是这一点。我编写了一些练习函数，它们在参数列表和函数内接受指针，修改指针指向的内容。我从来不用这种**指针语法。

4

4 回答 4

0

文体（不要重复自己）::

void addNode(struct Node** head, int value)
{
    if(*head == NULL)
    {
        struct Node *tmp = (struct Node *) malloc(sizeof(struct Node));
        tmp->value = value;
        tmp->next = *head;
        *head = tmp;
    }

    else
    {
        struct Node *newNode = (struct Node *) malloc(sizeof(struct Node));
        newNode->value = value;
        newNode->next = *head;
        *head = newNode;
    }
}

你不需要 if/else ::

#include <stdlib.h>

void addNode(struct Node **head, int value)
{

        struct Node *newNode = malloc(sizeof *newNode);
        if ( !newNode) { error(); return;}
        newNode->value = value;
        newNode->next = *head; // Could be NULL, but we need a NULL anyway in that case
        *head = newNode;

}
于 2013-03-16T14:45:04.047 回答
0

它与参数按值传递有关。因此，在第一个非工作版本中，指向的指针head是按值传递的，因此该变量是函数内部的局部变量。当函数返回时，对局部变量的更改在函数外部不可见。

但是，在第二个版本中，您通过引用传递指针，因此该函数知道实际指针在内存中的位置，并且可以直接存储在该内存中。

ASCII 图表时间：

假设您有以下三个变量：

int value1;
int *pointer1 = &value1;
int **pointer2 = &pointer1;

变量的内存看起来像这样：

+----------+ +----------+ +--------+
| 指针2 | --> | 指针1 | --> | 值1 |
+----------+ +----------+ +--------+

所以pointer2指向pointer1，pointer1指向value1。

使用取消引用运算符*onpointer2将获得pointer2指向的值，即pointer1.

于 2013-03-16T14:24:57.433 回答
0

这里是：

你有一个错误createList

struct Node *createList()
{
    struct Node *head = malloc(sizeof(*head));
    head->value = 0;   //< Probably you want this
    head->next = NULL; //< You definitively wanted this
    return head;
}

如果要将节点添加到列表的尾部，则addNode如下所示：

void addNodeLast(struct Node* head, int value)
{
    struct Node *tailNode;
    struct Node *newNode;

    newNode = malloc(sizeof(*newNode));
    newNode->value = value;
    newNode->next = NULL;

    // Find the last node in the list
    for (tailNode = head; tailNode->next; tailNode = tailNode->next); 

    tailNode->next = head->next;
}

如果要在头部之后插入节点：

void addNodeAfterHead(struct Node* head, int value)
{
    struct Node *newNode;

    newNode = malloc(sizeof(*newNode));
    newNode->value = value;
    newNode->next = head-next;

    head->next = newNode;
}

如果您正在更换头部（每次都制作新头部）：

Node *addNodeNewHead(struct Node* head, int value)
{
    struct Node *newNode;

    newNode = malloc(sizeof(*newNode));
    newNode->value = value;
    newNode->next = head;

    return newNode;
}

...
Node * head = createList();
head = addNodNewHead(head, 3);
head = addNodNewHead(head, 5);
于 2013-03-16T16:28:30.133 回答
0

这在这里不会很好用

struct Node *createList()
{ 
    struct Node *head = (struct Node *) malloc(sizeof(struct Node));
    head = NULL;
    return head;
}

在您分配一个节点并让 head 指向它之后，您将 head 设置为指向 NULL。

于 2013-03-16T16:07:39.070 回答