c - 难以理解Deitel＆Deitel的书中的插入节点功能

我正在从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);
  }
}

为什么需要PiviouSPTR和Currut-PTR存在？我不能在没有这些变量的节点间移动吗？
前一个ptr->下一个tptr（*）不就是currentpr吗？为什么将newPtr附加到currentPtr时此功能不起作用？
我是否正确地假设previousPtr和currentPtr实际上不是连续的，但它们被称为简单的？
请注意，此函数按顺序放置元素。

最佳答案

欢迎来到用C编写代码的世界！这里的逻辑处理围绕NULL指针的工作，这个概念可能有点难以理解。在某种意义上，NULL表示指针地址处没有“任何内容”。在我们开始之前，这里有一个单独链接列表上的few good tutorials，您可能会对它感兴趣。
为什么需要PiviouSPTR和Currut-PTR存在？我不能在没有这些变量的节点间移动吗？
你看到的代码是一个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，你的代码将崩溃。
前一个ptr->下一个tptr（*）不就是currentpr吗？为什么将newPtr附加到currentPtr时此功能不起作用？
你说得对，previousPtr->nextPtr确实是currentPtr-但是，不能保证currentPtr不是NULL。如果连接到currentPtr，则会有segfault的风险。此外，如果它不是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在内存中不连续-它们是在堆上创建的，堆中的is not contiguous.变量的命名是为了便于程序员使用。
祝你好运！

关于c - 难以理解Deitel＆Deitel的书中的插入节点功能，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57857815/

currentptr

c - 难以理解Deitel＆Deitel的书中的插入节点功能