c++指针，链表混淆

Question

我正试图在c++中建立一个链表。我的理解是，我所创建的代码应该创建一个节点，然后逐步链接4到最后。不幸的是，虽然我希望看到计数结果为"12 123 1234 12345"，但我看到的是"12 12 12 12 12"，并且在我的主程序中，我无法遍历列表-它只是崩溃了。

我有以下代码:

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

int nodeCount = 0;
listNode* addToEnd(listNode* node) {
    listNode* newNode = new listNode;
    newNode->val = ++nodeCount;
    newNode->next = NULL;
    if (node == NULL) {
        return newNode;
    }
    listNode* current = node;
    cout<<"nn";
    do {
        if (current->next == NULL) {
            current->next = newNode;
        }
        cout<<current->val<<"n";
        current = current->next;
    } while (current->next != NULL);
    cout<<current->val<<endl;
}

int main()
{
    listNode* first = addToEnd(NULL);
    addToEnd(first);
    addToEnd(first);
    addToEnd(first);
    addToEnd(first);
    cout<<"Third: "<<first->next->next->val;
}

任何帮助都是感激的，因为我已经无计可施了。

Answer 1

显然，函数addToEnd是错误的

listNode* addToEnd(listNode* node) {
    listNode* newNode = new listNode;
    newNode->val = ++nodeCount;
    newNode->next = NULL;
    if (node == NULL) {
        return newNode;
    }
    listNode* current = node;
    cout<<"nn";
    do {
        if (current->next == NULL) {
            current->next = newNode;
        }
        cout<<current->val<<"n";
        current = current->next;
    } while (current->next != NULL);
    cout<<current->val<<endl;
}

假设列表已经包含两个节点，并考虑函数内部的do-while循环。首先，current_next != null，因此执行以下语句

        current = current->next;

现在current指向第二个节点。它的数据成员next等于NULL。所以循环的条件是

    } while (current->next != NULL);

将为假，并且不会重复迭代。所以我们什么也没加。

如果node不等于NULL，函数也不返回任何值。

按如下方式重写函数

listNode* addToEnd( listNode* node ) 
{
    listNode* newNode = new listNode { ++nodeCount, NULL };
    if ( node == NULL) return newNode;
    listNode* current = node;
    while ( current->next != NULL ) current = current->next;
    current->next = newNode;
    return newNode;
    // or
    //return node;    
}

考虑到这个语句

cout<<"Third: "<<first->next->next->val;

只输出第三个节点的值。如果你想输出所有的列表，你应该写

for ( listNode *current = first; current; current = current->next ) 
{
    std::cout << current->val << ' ';
}
std::cout << std::endl;

顺便说一下，使用我的函数，你可以在main中这样写:)

listNode* first;
addToEnd( addToEnd( addToEnd( addToEnd( first  = addToEnd( NULL ) ) ) ) );

Answer 2

使用for循环让您到达最后一个节点，而不是等待，然后在循环之外分配新节点。试图在内部执行此操作将导致无限循环(并使代码更难阅读):

listNode* current;
for(current = node; current->next != NULL; current = current->next) ;
current->next = newNode;

您还忘记在函数结束时返回newNode。

Answer 3

您正在脱离非void返回类型的函数的末尾。如果你没有使用返回值，那就不可以了。

标准中

6.6.3规定:

从函数末尾流出相当于没有值的return;这将导致值返回函数中的未定义行为。

Answer 4

如果检查if(node==null)的if条件失败，则没有返回语句。

Answer 5

在你的问题中使用递归函数违反规则吗?

为什么不……

void addToEnd(listNode* node){
    if(node == NULL){
        *node = new listNode;
        node->next = NULL;
        node->val = ++nodeCount;
    }else{
        addToEnd(node->next);
    }
    return;
}
int main(){
    listNode* first = NULL;
    addToEnd(first); // 1
    addToEnd(first); // 2
    addToEnd(first); // 3
    addToEnd(first); // 4
    addToEnd(first); // Linked list is now 5 long
}

Answer 6

这就是我将五个节点添加到保存节点计数的链表中的编码方式。欢迎大家提建议。

#include <iostream>
#include <cstdlib>
using namespace std;
struct listNode{
 int val;
 listNode* next;
};
listNode* addToEnd(listNode*, int);
int main()
{
  listNode* first = NULL;
  listNode* temp;
  int nodeCount = 1;
  for(int i = 0; i < 5; i++){
     first = addToEnd(first, nodeCount);
     nodeCount++;
  }
  temp = first;
  while(temp){
     cout << temp->val << ' ';
     temp = temp->next;
  }
  temp = first;
                               //Deallocate memory
  while(temp){                 //could do memory deallocation while displaying 
     nodeToDelete = temp;      //the value of nodeCount but wanted to illustrate  
                               //both methods individually
     temp = temp->next;
     delete nodeToDelete;   
  }  
  first = NULL;                //eliminate hanging pointer
  return 0;
}
listNode* addToEnd(listNode* node, int nodeCount) 
{
  listNode* newNode = new (nothrow) listNode;
  listNode* current = node;
  if(newNode){
     newNode->val = nodeCount;
     newNode->next = NULL;
     if (node == NULL)        
        node = newNode;       
     else{          
        while (current->next != NULL) 
           current = current->next;
           current->next = newNode;          
     }
  }
  else
     cout << "error allocationg memory" << endl;
  return node;
}