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 实际上并不连续，但为了简单起见它们被称为是正确的？

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

标签： clist

Answer 1

欢迎来到 C 语言编码的世界！这里的逻辑涉及围绕NULL指针工作，这个概念可能有点难以掌握。从某种意义上说，NULL意味着指针地址处“什么都没有”。在我们开始之前，这里有一些 关于单链表的好 教程，您可能有兴趣查看这些教程。

---

为什么需要 previousPtr 和 currentPtr 存在？我不能在没有这些变量的情况下通过节点吗？

您看到的代码是一个链表。没有看到它的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，你的代码会崩溃。

---

不是 previousPtr->nextPtr (*) 只是 currentPtr 吗？为什么将 newPtr 附加到 currentPtr 时此功能不起作用？

你是对的，previousPtr->nextPtr确实是currentPtr- 但是，不能保证currentPtr不是NULL。如果附加到currentPtr. 此外，如果不是NULL，则意味着如果您尝试绑定数据，则无法正确附加数据。例如：

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!

---

我是否正确假设 previousPtr 和 currentPtr 实际上并不连续，但为了简单起见它们被称为是正确的？

再次正确！previousPtr并且currentPtr在内存中不连续 - 它们是在堆上创建的，这不是连续的。这些变量如此命名是为了程序员的易用性。

祝你好运！