0

我试图理解这个函数以将元素插入到按升序排序的整数的链表中，但是，有些代码让我感到困惑......

Node* insert (int x, Node *p) {

 if (p==nullptr)
   return cons(x,nullptr); //inserts the new node at front of list,before node with nullptr?
 if (x < = p-> val)
    return cons(x,p); //this also inserts node at front of the list?
 //now the rest of the function is where I get confused...
 Node *prev=p; //so this is not allocating new memory, so what exactly does it mean?
 Node * after=prev->next; 
 //prev->next is pointing at whatever after is pointing to but after has no address?

 while (after!=nullptr && x > after->val) { //whats going on here?
   prev=after;
   after=after-> next;
 }

 prev->next=cons(x,after);
 return p;
}
4

1 回答 1

0 
Node* insert (int x, Node *p) {

 if (p==nullptr)
 return cons(x,nullptr); 
//inserts the new node at front of list,before node with nullptr?
if (x < = p-> val)
return cons(x,p); //this also inserts node at front of the list?

上面的代码负责在链表的开头插入新元素。发生这种情况有两种情况：

  1. 如果头部（在这种情况下为 p）为 NULL。
  2. 如果 p 指向的元素的值大于要插入的当前元素。

现在前进...

//now the rest of the function is where I get confused...
Node *prev=p; 
//so this is not allocating new memory, so what exactly does it mean?

这就像一个临时指针，可以用来遍历链表。因此，您将头部“p”存储在 prev 指针中。

Node * after=prev->next; 
//prev->next is pointing at whatever 
//after is pointing to but after has no address?

这是一个指针，它将存储 head 的下一个元素。

 while (after!=nullptr && x > after->val) { //whats going on here?
   prev=after;
   after=after-> next;
 }
 prev->next=cons(x,after);
 return p;
}

在这里，这看起来有点错误。你可能想做这样的事情，而不是：

While(prev->data >= inputdata && (after->data < inputdata || after == NULL)
{
  //insert your inputdata here because it is greater than the previous but less than after
 // or after is NULL.
}

我希望这能澄清你的困惑。如果您有任何问题，请告诉我。

于 2013-11-23T22:11:08.653 回答