0

要求是一个input函数，它将 a 返回到从用户输入创建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;
}

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

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

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

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

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

4

3 回答 3

2

您可以执行以下操作：

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;

没有特殊情况分配，但特殊情况分配。

于 2012-09-23T13:48:15.170 回答
1

没有一个解决方案看起来很复杂，但是使用一个虚拟节点，您将拥有一个非常干净的代码：

Node root; //stored on the stack
root->next = NULL;

//...

return root->next;
于 2012-09-23T13:46:39.543 回答
1

这是一个避免特殊情况的版本，它使用指针到指针：

struct list {
        struct list *next;
        int val;
        };

struct list *input(void)
{
struct list *ret=NULL, **tail;
char buff[100];

for (tail= &ret; fgets(buff, sizeof buff, stdin);       ) {
        int val;
        if ( sscanf(buff,"%d", &val) < 1) continue;
        *tail = malloc (sizeof **tail);
        (*tail)->next = NULL;
        (*tail)->val = val;
        tail = &(*tail)->next;
        }
return ret;
}
于 2012-09-23T15:38:52.360 回答