链表，在末尾插入 C++
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20125477/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Linked List, insert at the end C++
提问by user3018297
I was writing a simple function to insert at the end of a linked list on C++, but finally it only shows the first data. I can't figure what's wrong. This is the function:
我正在编写一个简单的函数来插入 C++ 链表的末尾，但最终它只显示了第一个数据。我无法弄清楚出了什么问题。这是功能：
void InsertAtEnd (node* &firstNode, string name){
node* temp=firstNode;
while(temp!=NULL) temp=temp->next;
temp = new node;
temp->data=name;
temp->next=NULL;
if(firstNode==NULL) firstNode=temp;
}
回答by Antoine
What you wrote is:
你写的是：
if
firstNodeis null, it's replaced with the single nodetempwhich has no next node (and nobody'snextistemp)Else, if
firstNodeis not null, nothing happens, except that thetempnode is allocated and leaked.
如果
firstNode为空，则替换为temp没有下一个节点的单个节点（没有人next是temp）否则，如果
firstNode不为空，除了temp节点被分配和泄漏之外，什么也不会发生。
Below is a more correct code:
下面是一个更正确的代码：
void insertAtEnd(node* &first, string name) {
// create node
node* temp = new node;
temp->data = name;
temp->next = NULL;
if(!first) { // empty list becomes the new node
first = temp;
return;
} else { // find last and link the new node
node* last = first;
while(last->next) last=last->next;
last->next = temp;
}
}
Also, I would suggest adding a constructor to node:
另外，我建议添加一个构造函数node：
struct node {
std::string data;
node* next;
node(const std::string & val, node* n = 0) : data(val), next(n) {}
node(node* n = 0) : next(n) {}
};
Which enables you to create the tempnode like this:
这使您能够temp像这样创建节点：
node* temp = new node(name);
回答by SF.
You've made two fundamental mistakes:
你犯了两个基本错误：
As you scroll through the list, you roll off the last element and start constructing in the void behind it. Finding the first NULL past the last element is useless. You must find the last element itself (one that has its 'next' equal NULL). Iterate over
temp->next, nottemp.If you want to append the element at the end, you must overwrite the last pointer's NULL with its address. Instead, you write the new element at the beginning of the list.
当您滚动列表时，您将滚动到最后一个元素并开始在其后面的空白处进行构建。查找最后一个元素之后的第一个 NULL 是没有用的。您必须找到最后一个元素本身（“下一个”等于 NULL 的元素）。迭代
temp->next，不是temp。如果要在末尾追加元素，则必须用其地址覆盖最后一个指针的 NULL。相反，您将新元素写在列表的开头。
void InsertAtEnd (node* &firstNode, string name) { node* newnode = new node; newnode->data=name; newnode->next=NULL; if(firstNode == NULL) { firstNode=newnode; } else { node* last=firstNode; while(last->next != NULL) last=last->next; last->next = newnode; } }
void InsertAtEnd (node* &firstNode, string name) { node* newnode = new node; newnode->data=name; newnode->next=NULL; if(firstNode == NULL) { firstNode=newnode; } else { node* last=firstNode; while(last->next != NULL) last=last->next; last->next = newnode; } }
Note, this gets a bit neater if you make sure never to feed NULL but have all lists always initialized with at least one element. Also, inserting at the beginning of list is much easier than appending at the end: newnode->next=firstNode; firstNode=newnode.
请注意，如果您确保从不提供 NULL 但始终使用至少一个元素初始化所有列表，则这会变得更简洁。此外，在列表的开头插入比在结尾添加要容易得多：newnode->next=firstNode; firstNode=newnode。
回答by maxywb
The last element in your list never has it's nextpointer set to the new element in the list.
列表中的最后一个元素从未将其next指针设置为列表中的新元素。
回答by John Colanduoni
The problem is that you are replacing the head of the linked list with the new element, and in the process losing the reference to the actual list.
问题是您正在用新元素替换链表的头部，并且在此过程中丢失了对实际列表的引用。
To insert at the end, you want to change the whilecondition to:
要在最后插入，您要将while条件更改为：
while(temp->next != null)
After the loop, tempwill point to the last element in the list. Then create a new node:
循环后，temp将指向列表中的最后一个元素。然后创建一个新节点：
node* newNode = new node;
newNode->data = name;
newNode->next = NULL;
Then change temps next to this new node:
然后temp在这个新节点旁边更改s：
temp->next = newNode;
You also do not need to pass firstNodeas a reference, unless you want NULLto be treated as a linked list with length 0. In that case, you will need to significantly modify your method so it can handle the case where firstNodeis NULLseparately, as in that case you cannot evaluate firstNode->nextwithout a segmentation fault.
您也不需要firstNode作为引用传递，除非您希望NULL被视为长度为 0 的链表。在这种情况下，您将需要显着修改您的方法，以便它可以单独处理 where firstNodeis的情况NULL，如如果firstNode->next没有分段错误，您就无法进行评估。
回答by Robber
void addlast ( int a)
{
node* temp = new node;
temp->data = a;
temp->next = NULL;
temp->prev=NULL;
if(count == maxnum)
{
top = temp;
count++;
}
else
{
node* last = top;
while(last->next)
last=last->next;
last->next = temp;
}
}
回答by codesavory
If you don't want to use reference pointer, you could use pointer to pointer. My complete code goes like below:
如果您不想使用引用指针，则可以使用指向指针的指针。我的完整代码如下：
void insertAtEnd(struct node **p,int new_data)
{
struct node *new_node=(struct node *)malloc(sizeof(struct node));
new_node->data=new_data;
new_node->next=NULL;
if((*p)==NULL)//if list is empty
{
*p=new_node;
return;
}
struct node* last=*p;//initailly points to the 1st node
while((last)->next != NULL)//traverse till the last node
last=last->next;
last->next=new_node;
}
void printlist(struct node *node)
{
while(node != NULL);
{
printf("%d->",node->data);
node=node->next;
}
}
int main()
{
struct node *root=NULL;
insertAtEnd(&root,1);
insertAtEnd(&root,2);
insertAtEnd(&root,3);
insertAtEnd(&root,4);
insertAtEnd(&root,5);
printlist(root);
return 0;
}
Understanding the need of the below two variables is key to understanding the problem:
理解以下两个变量的需要是理解问题的关键：
- struct node **p: Because we need to link it from the root node created in the main.
- struct node* last: Because if not used, the original content will be changed with the contents of the next node inside the while loop. In the end only 2 elements will be printed, the last 2 nodes, which is not desired.
- struct node **p：因为我们需要从main中创建的根节点链接它。
- struct node* last：因为如果不使用，原来的内容会随着while循环内下一个节点的内容而改变。最后只打印 2 个元素，最后 2 个节点，这是不需要的。
回答by Prvn Yadav
void InsertAtEnd (node* &firstNode, string name){
node* temp=firstNode;
while(temp && temp->next!=NULL) temp=temp->next;
node * temp1 = new node;
temp1->data=name;
temp1->next=NULL;
if(temp==NULL)
firstNode=temp1;
else
temp->next= temp1;
}
while loop will return at temp==null in your code instead you need to return last node pointer from while loop like this
while 循环将在您的代码中以 temp==null 返回，而您需要像这样从 while 循环中返回最后一个节点指针
while(temp && temp->next!=NULL) temp=temp->next;
and assign a new node to next pointer of the returned temp node will add the data to the tail of linked list.
并将新节点分配给返回的临时节点的下一个指针，将数据添加到链表的尾部。
回答by adinchi
You can use this code:
您可以使用此代码：
void insertAtEnd(Node* firstNode, string name)
{
Node* newn = new Node; //create new node
while( firstNode->next != NULL ) //find the last element in yur list
firstNode = firstNode->next; //he is the one that points to NULL
firstNode->next = newn; //make it to point to the new element
newn->next = NULL; //make your new element to be the last (NULL)
newn->data = name; //assign data.
}
