C中的LinkedList实现

Question

所以我开始学习数据结构，并在 Java 和 Python 中轻松地成功实现了 LinkedList。但是我的 C 代码有些不对，我没有得到输出。这个指针概念真的让我很烦恼，如果有人能告诉我我在这个实现中的错误，我将不胜感激。

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

struct node
{
  int data;
  struct node *next;
};

void append(int data, struct node *head, struct node *tail){
  struct node *newNode = ((struct node*)malloc(sizeof(struct node)));   
  (*newNode).data = data;
  (*newNode).next = NULL;
  if (head == NULL)
  {
    head = newNode;
    tail = newNode;
  }else{
    tail -> next = newNode;
    tail = newNode;
  }

}

void traverse(struct node *head){
  struct node *temp = head;
  while(temp != NULL){
    printf("%d",(*temp).data);
    temp = temp->next;
  }
}


int main()
{
  printf("Hey linked list \n");
  struct node *head = NULL;
  struct node *tail = NULL;
  /* code */
  append(3,head,tail);
  append(4,head,tail);
  append(5,head,tail);
  traverse(head);
  return 0;
}

顺便说一句，就像 head 总是指向链表中的第一个节点一样，我有一个指针 tail 总是指向链表中的最后一个节点。这种方式将数据附加到列表很容易，而且是常数时间。

谢谢你们，我希望能有一个简单易懂的答案..

Answer 1

您的 head 和 tail 指针未按您预期的方式设置。 c 中的所有内容都是按值传递的，因此基本上所有传递给函数的参数都是仅在该函数内具有作用域的局部变量。当您将 head 和 tail 传递给 append 时，会创建每个的本地副本。您对 head 和 tail 进行赋值，但是一旦函数退出并且变量超出范围，这些赋值就会丢失。如果您希望在函数外部对 "stick" 进行赋值，则必须将这些指针的地址传递给 append 并在那里取消引用它们。

void append(int data, struct node **head, struct node **tail)
{
  struct node *newNode = ((struct node*)malloc(sizeof(struct node)));   
  (*newNode).data = data;
  (*newNode).next = NULL;
  if (head == NULL)
  {
    *head = newNode;  // dereference head here so this assignment will persist outside of this function
    *tail = newNode;
  }else{
    (*tail) -> next = newNode;
    *tail = newNode;
  }
}

.....

int main(void)
{
  printf("Hey linked list \n");
  struct node *head = NULL;
  struct node *tail = NULL;
  /* code */
  append(3,&head,&tail);
  append(4,&head,&tail);
  append(5,&head,&tail);
  traverse(head);
  return 0;
}

Answer 2

您的代码仅传递 head 和 tail 指针的副本，因此调用者的值不会更新。您需要 append 中的双星参数并传递它们的地址以便它们可以更新，如下所示：

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

struct node
{
    int data;
    struct node *next;
};

void append(int data, struct node **head, struct node **tail){
    struct node *newNode = malloc(sizeof(struct node)); 
    newNode->data = data;
    newNode->next = NULL;
    if (*head == NULL)
    {
        *head = newNode;
        *tail = newNode;
    }else{
        (*tail)->next = newNode;
        *tail = newNode;
    }
}

void traverse(struct node *head){
    struct node *temp = head;
    while(temp != NULL){
        printf("%d",(*temp).data);
        temp = temp->next;
    }
}

int main(void)
{
    printf("Hey linked list \n");
    struct node *head = NULL;
    struct node *tail = NULL;
    append(3, &head, &tail);
    append(4, &head, &tail);
    append(5, &head, &tail);
    traverse(head);
    return 0;
}

程序输出：

Hey linked list
345

C中的LinkedList实现

LinkedList implementation in C

c

linked-list

data-structures

singly-linked-list