c - 无法理解 Deitel&Deitel 书中的插入节点函数

Question

我正在研究 Deitel&Deitel 的 C 手册中的这个函数，但它的文档不多(至少，对我来说理解不够)，我很难理解它。

void insert(ListNodePtr *sPtr, char value){
  ListNodePtr newPtr = malloc(sizeof(ListNode));

  if(newPtr != NULL){
    newPtr->data = value;
    newPtr->nextPtr = NULL;

    ListNodePtr previousPtr = NULL;
    ListNodePtr currentPtr = *sPtr;

    while(currentPtr != NULL && value > currentPtr->data){ 
      previousPtr = currentPtr;                            
      currentPtr = currentPtr->nextPtr; 
    }

    if(previousPtr == NULL){
      newPtr->nextPtr = *sPtr;
      *sPtr = newPtr;
    }
    else{ 
      previousPtr->nextPtr = newPtr; //*
      newPtr->nextPtr = currentPtr; 
    }
  }
  else{
    printf("%c not inserted. No memory available.\n", value);
  }
}

1. 为什么需要存在 previousPtr 和 currentPtr？我不能只在没有这些变量的情况下移动节点吗？
2. previousPtr->nextPtr (*) 不就是 currentPtr 吗？为什么在将 newPtr 附加到 currentPtr 时此功能不起作用？
3. 我是否正确地假设 previousPtr 和 currentPtr 实际上不是连续的，而是为了简单起见而像它们一样被调用？

请注意，此函数以有序方式放置元素。

Answer 1

欢迎来到 C 语言编码世界!这里的逻辑处理围绕 NULL 指针的工作，这个概念可能有点难以理解。从某种意义上说，NULL 意味着指针地址处“没有任何内容”。在我们开始之前，这里有一个 few good tutorials在单链表上，您可能有兴趣查看。

---

Why is there a need for previousPtr and currentPtr to exist? Can't I just move through the nodes without those variables?

您看到的代码是 linked list .没有看到它的struct定义，就不好说了，但是链表的要点是数据存储在堆中，并通过指针访问。插入链表时，首先必须找到要插入的位置。

    //this code traverses the linked list. each node has a nextPtr value, which 
    //points, predictably, to the next value. if this is the end of the list,
    //the nextPtr value will be NULL.

    //first, check if the current pointer is NULL. this happens in two cases:
    // - the list is totally empty, in which case this is the first pointer.
    // - the end of the list has been reached.
    //second, if it's not NULL, check the value. 
    //if the value is greater than the current pointer, we'll insert the new data here.
    while(currentPtr != NULL && value > currentPtr->data){

      //entering this loop means we've encountered a non-null next ptr, as well as one
      //whose value is larger than this one. we'll go to the next node.

      //save the node we're at now
      previousPtr = currentPtr;   
      //go to the next node                         
      currentPtr = currentPtr->nextPtr; 
    }

我们现在在路上 - 在这个循环退出后，我们要么到达列表的末尾，要么到达我们想要插入值的位置。不过，首先要进行完整性检查 - 该列表是否还有任何节点？

    //check to see whether there's even a list yet. note that previousPtr starts at
    //NULL - if this doesn't change, the while loop didn't traverse anything, and 
    //the sPtr (start pointer) was NULL.

    if(previousPtr == NULL){
      //start pointer was NULL - make a new list head

      //assign newPtr->nextPtr to NULL
      newPtr->nextPtr = *sPtr;

      //assign sPtr to the new node we've made
      *sPtr = newPtr;
    }

这里是我们为什么需要 previousPtr 和 currentPtr 的地方。

    //we've either reached the end of the list, OR we've reached a value 
    //we want to insert to.
    //
    //if we've reached the end of the list, currentPtr is NULL, and we can't access
    //its value or its nextPtr. if we hadn't kept previousPtr, we'd know we were at
    //the end of the list, but would have no way to back up one pointer in order to 
    //add the new node.
    //
    //even if we haven't reached the end of the list, currentPtr doesn't know what 
    //the previous pointer was, so we'd have no way to insert something where currentPtr 
    //used to be.

    else{ 

      //make previousPtr point to the new pointer
      previousPtr->nextPtr = newPtr; //*
      //make the newPtr point to currentPtr. note that it's irrelevant if this
      //is the end of the list or not - currentPtr will be NULL if it is, and if it 
      //isn't, the list will still point to whatever was in currentPtr - just with
      //newPtr coming first.
      newPtr->nextPtr = currentPtr; 
    }

所以 - currentPtr 和 previousPtr 是必需的，因为为了插入到列表中，您需要一种方法来跟踪您将添加数据的新节点到。您可以在没有这些值的情况下移动节点，并且某些函数确实不使用这些变量 - 常见示例是 find(int value) 或类似的。如果你想在没有它们的情况下执行 insert，你可以，但这有点棘手，因为你必须引用 currentPtr->nextPtr->value - 如果 nextPtr 为 NULL，您的代码将崩溃。

---

isn't previousPtr->nextPtr (*) just currentPtr? Why does this function not work when attaching newPtr to currentPtr?

你是对的，previousPtr->nextPtr 确实是 currentPtr - 但是，不能保证 currentPtr 不是 NULL 。如果附加到 currentPtr，您将面临段错误的风险。此外，如果它不是 NULL，则意味着如果您尝试绑定(bind)到它，数据将无法正确附加。例如:

currentPtr has a new value:
                                newPtr(5)
ptr(9) -> ptr(7) -> previousPtr(6) -> currentPtr(4) -> ptr(3) -> ptr(1) -> NULL


attach to previousPtr (correct)
                                    newPtr(5) -v
ptr(9) -> ptr(7) -> previousPtr(6) -^          currentPtr(4) -> ptr(3) -> ptr(1) -> NULL


attach to currentPtr (out of order, and currentPtr might be NULL)
                                                     newPtr(5) -v
ptr(9) -> ptr(7) -> previousPtr(6) -> currentPtr(4) -^          ptr(3) -> ptr(1) -> NULL



currentPtr is NULL:
                      newPtr(4)
ptr(6) -> previousPtr(5) -> NULL [currentPtr]


attach to previousPtr (correct)
                          newPtr(4) -v
ptr(6) -> previousPtr(5) -^          NULL

attach to currentPtr (SEGFAULT)
                                  newPtr(4)
ptr(6) -> previousPtr(5) -> NULL -^ 

                            ^^^^^^^  can't do this - NULL doesn't have a nextPtr!

---

Am I right in assuming that previousPtr and currentPtr aren't actually contiguous but are called like they are for simplicity?

再次纠正! previousPtr 和 currentPtr 在内存中不连续 - 它们是在堆上创建的，is not contiguous.这些变量的命名是为了程序员的易用性。

祝你好运!