在 C 中实现没有输入大小的链接列表

Question

首先，我定义一个结构来实现链表：

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

然后，我必须在链表中插入一个元素。我无法完成这一部分。

我的讲义中的一个例子告诉我，当我们插入一个元素时，我们应该做这样的事情：

Node a, c; // originally
Node b; // insert-element
b->next = &c;
a->next = &b;

但是，我必须声明一个节点来实现它。但是，这是我的情况：我不知道输入大小，也许我必须插入 60 个元素，或者我只需要插入 2 个元素。解决方案是什么？

还有一个小而愚蠢的问题，a->next和a.next之间有什么不同吗？

Answer 1

这是实现空链表的方法：

typedef struct node
{
  int data;
  struct node *next;
} Node;
int main(){
  Node *a, *b;
  a=malloc(sizeof(Node));
  //here check if allocation has been done, if not error
  a->data=1;
  a->next=NULL;

  b=malloc(sizeof(Node));
  b->data=2;
  b->next=a;
  //and so on


  return 0;
} 

这样，您的链接列表将如下所示：b ----> a -----> NULL现在假设您想在链表的末尾添加 3;您可以使用此功能：

void insertToEnd(Node *head, int newNumber)
{
   Node *newNode, *tmp;
   newNode=malloc(sizeof(Node));
   newNode->data=newNumber;
   newNode->next=NULL;
   tmp=head;
   if(head->next == NULL){
     head->next = newNode;
   }
   else
   {
   while(tmp->next != NULL)
    {
        if(tmp->next == NULL)
        {
            tmp->next = newNode;
        }
        tmp = tmp->next;
    }
}

head=tmp;
}

我希望它工作正常，因为我现在没有 c 编译器。 检查一下，让我知道函数是否工作正常

Answer 2

明智的做法是创建一个函数，将新列表节点附加到现有列表。我们使用NULL来表示"空列表"。我们预先添加，因为这样可以避免每次都遍历整个列表。

Node * list_prepend(Node *head, int data)
{
  Node *n = malloc(sizeof *n);
  if(n != NULL)
  {
    n->next = head;
    n->data = data;
    return n;  /* The new head. */
  }
  return head;
}

然后像这样使用它：

int main(void)
{
  Node *list;
  list = list_prepend(NULL, 47);
  list = list_prepend(list, 11);
}

Answer 3

如果您不知道将获得多少节点，则必须在运行时分配内存。 malloc()和free()将完成这项工作。

实际上，a->next和a.next之间的区别是a。在第一种构造中，"a"是指向结构的指针，在第二种情况下，"a"是结构本身。