c - 如何克服输入函数中链表第一个元素的奇数内存分配？

Question

要求是一个input 函数，它返回一个Node* 到input 根据用户输入创建的链表的根。喜欢:

Node *input()
{
     Node *root; //not yet allocated
     while(1)
     {    
           //take in numbers from the user and correspondingly add them 
           //to the linked list and quit when anything else is entered

           if(input character is a number)
           {
                //allocate memory to a fresh pointer and push the number to it
                //and add this new Node to the LL
           }
     }
     return root;
}

-> 有预分配内存给 root 并在 while 循环主体之前将第一个数字推送给它的解决方案。但在这里，如果用户不输入任何内容，则必须立即删除。

-> 此外，还有一种可能的方法来检查 root 在 while 循环中是否为 NULL，如果是，则分配内存，以便它只发生一次。

但我想知道是否有解决方案可以消除由 LL 的根引起的奇怪情况。

->也许我可以在第一个位置保留一个不包含任何值的虚拟节点。

但除此之外呢？如果有更好的方法来完成整个事情，请提出建议。

Answer 1

你可以这样做:

struct Node* root = 0; // don't forget to initialize

while (...) {
  if (...) {
    struct Node * item = ... ;  // allocate
    item->data = ...;
    item->next = root;
    root = item;
  }
}

return root;

大功告成，第一个元素不需要特殊情况。列表的末尾由空的 next 指针指示。

如果您希望列表按插入顺序排列，而不是每次都遍历整个列表，您可以:

struct Node* root = 0; // don't forget to initialize
struct Node* tail = 0;

while (...) {
  if (...) {
    struct Node * item = ... ;  // allocate
    item->data = ...;
    item->next = 0;

    if (tail)
      tail->next = item;
    tail = item;

    if (!root)
      root = item;
  }
}

return root;

没有特例分配，而是特例赋值。