C++中的简单链表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/22141477/
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
Simple linked list in C++
提问by Kalle
I am about to create a linked that can insert and display until now:
我即将创建一个可以插入和显示的链接，直到现在：
struct Node {
int x;
Node *next;
};
This is my initialisation function which only will be called for the first Node:
这是我的初始化函数，只会在第一个调用Node：
void initNode(struct Node *head, int n){
head->x = n;
head->next = NULL;
}
To add the Node, and I think the reason why my linked list isn't working correct is in this function:
要添加Node, 我认为我的链表无法正常工作的原因在于这个函数：
void addNode(struct Node *head, int n){
struct Node *NewNode = new Node;
NewNode-> x = n;
NewNode -> next = head;
head = NewNode;
}
My mainfunction:
我的main功能：
int _tmain(int argc, _TCHAR* argv[])
{
struct Node *head = new Node;
initNode(head, 5);
addNode(head, 10);
addNode(head, 20);
return 0;
}
Let me run the program as I think it works. First I initialise the head Nodeas a Nodelike this:
让我按照我认为可行的方式运行该程序。首先，我将头部初始化Node为Node这样：
head = [ 5 | NULL ]
Then I add a new node with n = 10 and pass head as my argument.
然后我添加一个 n = 10 的新节点并将 head 作为我的参数传递。
NewNode = [ x | next ] where next points at head. And then I change the place where head is pointing to NewNode, since NewNode is the first Node in LinkedList now.
新节点 = [ x | next ] next 指向头部。然后我更改 head 指向 NewNode 的位置，因为 NewNode 现在是 LinkedList 中的第一个节点。
Why isn't this working? I would appreciate any hints that could make me move in the right direction. I think LinkedList is a bit hard to understand.
为什么这不起作用？我将不胜感激任何可以使我朝着正确方向前进的提示。我认为 LinkedList 有点难以理解。
When I'm printing this, it only returns 5:
当我打印这个时，它只返回 5：
回答by exilit
This is the most simple example I can think of in this case and is not tested. Please consider that this uses some bad practices and does not go the way you normally would go with C++ (initialize lists, separation of declaration and definition, and so on). But that are topics I can't cover here.
这是我能想到的最简单的例子，没有经过测试。请注意，这使用了一些不好的做法，并且与您通常使用 C++ 的方式不同（初始化列表、声明和定义的分离等）。但这是我无法在此涵盖的主题。
#include <iostream>
using namespace std;
class LinkedList{
// Struct inside the class LinkedList
// This is one node which is not needed by the caller. It is just
// for internal work.
struct Node {
int x;
Node *next;
};
// public member
public:
// constructor
LinkedList(){
head = NULL; // set head to NULL
}
// destructor
~LinkedList(){
Node *next = head;
while(next) { // iterate over all elements
Node *deleteMe = next;
next = next->next; // save pointer to the next element
delete deleteMe; // delete the current entry
}
}
// This prepends a new value at the beginning of the list
void addValue(int val){
Node *n = new Node(); // create new Node
n->x = val; // set value
n->next = head; // make the node point to the next node.
// If the list is empty, this is NULL, so the end of the list --> OK
head = n; // last but not least, make the head point at the new node.
}
// returns the first element in the list and deletes the Node.
// caution, no error-checking here!
int popValue(){
Node *n = head;
int ret = n->x;
head = head->next;
delete n;
return ret;
}
// private member
private:
Node *head; // this is the private member variable. It is just a pointer to the first Node
};
int main() {
LinkedList list;
list.addValue(5);
list.addValue(10);
list.addValue(20);
cout << list.popValue() << endl;
cout << list.popValue() << endl;
cout << list.popValue() << endl;
// because there is no error checking in popValue(), the following
// is undefined behavior. Probably the program will crash, because
// there are no more values in the list.
// cout << list.popValue() << endl;
return 0;
}
I would strongly suggest you to read a little bit about C++ and Object oriented programming. A good starting point could be this: http://www.galileocomputing.de/1278?GPP=opoo
我强烈建议您阅读一些有关 C++ 和面向对象编程的内容。一个好的起点可能是这样的：http: //www.galileocomputing.de/1278?GPP=opoo
EDIT: added a pop function and some output. As you can see the program pushes 3 values 5, 10, 20 and afterwards pops them. The order is reversed afterwards because this list works in stack mode (LIFO, Last in First out)
编辑：添加了一个弹出功能和一些输出。如您所见，程序推送 3 个值 5、10、20，然后弹出它们。之后顺序颠倒，因为此列表在堆栈模式下工作（LIFO，后进先出）
回答by Blaz Bratanic
You should take reference of a head pointer. Otherwise the pointer modification is not visible outside of the function.
你应该参考一个头指针。否则指针修改在函数外部不可见。
void addNode(struct Node *&head, int n){
struct Node *NewNode = new Node;
NewNode-> x = n;
NewNode -> next = head;
head = NewNode;
}
回答by Saurabh Raoot
Below is a sample linkedlist
下面是一个示例链表
#include <string>
#include <iostream>
using namespace std;
template<class T>
class Node
{
public:
Node();
Node(const T& item, Node<T>* ptrnext = NULL);
T value;
Node<T> * next;
};
template<class T>
Node<T>::Node()
{
value = NULL;
next = NULL;
}
template<class T>
Node<T>::Node(const T& item, Node<T>* ptrnext = NULL)
{
this->value = item;
this->next = ptrnext;
}
template<class T>
class LinkedListClass
{
private:
Node<T> * Front;
Node<T> * Rear;
int Count;
public:
LinkedListClass();
~LinkedListClass();
void InsertFront(const T Item);
void InsertRear(const T Item);
void PrintList();
};
template<class T>
LinkedListClass<T>::LinkedListClass()
{
Front = NULL;
Rear = NULL;
}
template<class T>
void LinkedListClass<T>::InsertFront(const T Item)
{
if (Front == NULL)
{
Front = new Node<T>();
Front->value = Item;
Front->next = NULL;
Rear = new Node<T>();
Rear = Front;
}
else
{
Node<T> * newNode = new Node<T>();
newNode->value = Item;
newNode->next = Front;
Front = newNode;
}
}
template<class T>
void LinkedListClass<T>::InsertRear(const T Item)
{
if (Rear == NULL)
{
Rear = new Node<T>();
Rear->value = Item;
Rear->next = NULL;
Front = new Node<T>();
Front = Rear;
}
else
{
Node<T> * newNode = new Node<T>();
newNode->value = Item;
Rear->next = newNode;
Rear = newNode;
}
}
template<class T>
void LinkedListClass<T>::PrintList()
{
Node<T> * temp = Front;
while (temp->next != NULL)
{
cout << " " << temp->value << "";
if (temp != NULL)
{
temp = (temp->next);
}
else
{
break;
}
}
}
int main()
{
LinkedListClass<int> * LList = new LinkedListClass<int>();
LList->InsertFront(40);
LList->InsertFront(30);
LList->InsertFront(20);
LList->InsertFront(10);
LList->InsertRear(50);
LList->InsertRear(60);
LList->InsertRear(70);
LList->PrintList();
}
回答by Vlad from Moscow
Both functions are wrong. First of all function initNodehas a confusing name. It should be named as for example initListand should not do the task of addNode. That is, it should not add a value to the list.
这两个函数都是错误的。首先，函数initNode有一个令人困惑的名称。它应该命名为 exampleinitList并且不应该执行 addNode 的任务。也就是说，它不应向列表中添加值。
In fact, there is not any sense in function initNode, because the initialization of the list can be done when the head is defined:
其实函数initNode没有任何意义，因为在定义head时就可以完成列表的初始化：
Node *head = nullptr;
or
或者
Node *head = NULL;
So you can exclude function initNodefrom your design of the list.
因此，您可以initNode从列表设计中排除功能。
Also in your code there is no need to specify the elaborated type name for the structure Nodethat is to specify keyword struct before name Node.
此外，在您的代码中，无需Node为要在 name 之前指定关键字 struct的结构指定详细的类型名称Node。
Function addNodeshall change the original value of head. In your function realization you change only the copy of head passed as argument to the function.
函数addNode将改变 head 的原始值。在您的函数实现中，您只更改作为参数传递给函数的 head 副本。
The function could look as:
该函数可能如下所示：
void addNode(Node **head, int n)
{
Node *NewNode = new Node {n, *head};
*head = NewNode;
}
Or if your compiler does not support the new syntax of initialization then you could write
或者，如果您的编译器不支持初始化的新语法，那么您可以编写
void addNode(Node **head, int n)
{
Node *NewNode = new Node;
NewNode->x = n;
NewNode->next = *head;
*head = NewNode;
}
Or instead of using a pointer to pointer you could use a reference to pointer to Node. For example,
或者，您可以使用对指向 Node 的指针的引用，而不是使用指向指针的指针。例如，
void addNode(Node * &head, int n)
{
Node *NewNode = new Node {n, head};
head = NewNode;
}
Or you could return an updated head from the function:
或者你可以从函数返回一个更新的头部：
Node * addNode(Node *head, int n)
{
Node *NewNode = new Node {n, head};
head = NewNode;
return head;
}
And in mainwrite:
并在main写：
head = addNode(head, 5);
回答by Daniel Farrell
I'll join the fray. It's been too long since I've written C. Besides, there's no complete examples here anyway. The OP's code is basically C, so I went ahead and made it work with GCC.
我会加入战斗。好久没写C了，再说了，这里也没有完整的例子。OP 的代码基本上是 C 语言，所以我继续使用 GCC 使其工作。
The problems were covered before; the nextpointer wasn't being advanced. That was the crux of the issue.
问题在前面已经介绍过了；该next指针没有被提出。这是问题的关键。
I also took the opportunity to make a suggested edit; instead of having two funcitons to malloc, I put it in initNode()and then used initNode()to mallocboth (mallocis "the C new" if you will). I changed initNode()to return a pointer.
我也借此机会进行了建议的编辑；而不是有两个funcitons来malloc，我把它initNode()，然后使用initNode()到malloc两者（malloc是“C新型”如果你愿意）。我改为initNode()返回一个指针。
#include <stdlib.h>
#include <stdio.h>
// required to be declared before self-referential definition
struct Node;
struct Node {
int x;
struct Node *next;
};
struct Node* initNode( int n){
struct Node *head = malloc(sizeof(struct Node));
head->x = n;
head->next = NULL;
return head;
}
void addNode(struct Node **head, int n){
struct Node *NewNode = initNode( n );
NewNode -> next = *head;
*head = NewNode;
}
int main(int argc, char* argv[])
{
struct Node* head = initNode(5);
addNode(&head,10);
addNode(&head,20);
struct Node* cur = head;
do {
printf("Node @ %p : %i\n",(void*)cur, cur->x );
} while ( ( cur = cur->next ) != NULL );
}
compilation: gcc -o ll ll.c
汇编： gcc -o ll ll.c
output:
输出：
Node @ 0x9e0050 : 20
Node @ 0x9e0030 : 10
Node @ 0x9e0010 : 5
回答by 6502
The addNodefunction needs to be able to change head. As it's written now simply changes the local variable head(a parameter).
该addNode功能需要能够改变head。正如现在所写的那样，只需更改局部变量head（一个参数）。
Changing the code to
将代码更改为
void addNode(struct Node *& head, int n){
...
}
would solve this problem because now the headparameter is passed by reference and the called function can mutate it.
将解决这个问题，因为现在head参数是通过引用传递的，被调用的函数可以改变它。
回答by Deepu
headis defined inside the main as follows.
head在 main 中定义如下。
struct Node *head = new Node;
But you are changing the head in addNode()and initNode()functions only. The changes are not reflected back on the main.
但是您只是在改变头部addNode()和initNode()功能。更改不会反映回主要内容。
Make the declaration of the head as global and do not pass it to functions.
将 head 声明为全局并且不要将其传递给函数。
The functions should be as follows.
功能应该如下。
void initNode(int n){
head->x = n;
head->next = NULL;
}
void addNode(int n){
struct Node *NewNode = new Node;
NewNode-> x = n;
NewNode->next = head;
head = NewNode;
}
回答by Abdulhakim Zeinu
Use:
用：
#include<iostream>
using namespace std;
struct Node
{
int num;
Node *next;
};
Node *head = NULL;
Node *tail = NULL;
void AddnodeAtbeggining(){
Node *temp = new Node;
cout << "Enter the item";
cin >> temp->num;
temp->next = NULL;
if (head == NULL)
{
head = temp;
tail = temp;
}
else
{
temp->next = head;
head = temp;
}
}
void addnodeAtend()
{
Node *temp = new Node;
cout << "Enter the item";
cin >> temp->num;
temp->next = NULL;
if (head == NULL){
head = temp;
tail = temp;
}
else{
tail->next = temp;
tail = temp;
}
}
void displayNode()
{
cout << "\nDisplay Function\n";
Node *temp = head;
for(Node *temp = head; temp != NULL; temp = temp->next)
cout << temp->num << ",";
}
void deleteNode ()
{
for (Node *temp = head; temp != NULL; temp = temp->next)
delete head;
}
int main ()
{
AddnodeAtbeggining();
addnodeAtend();
displayNode();
deleteNode();
displayNode();
}
回答by JOSMAR BARBOSA - M4NOV3Y
I think that, to make sure the indeep linkage of each node in the list, the addNodemethod must be like this:
我认为，要确保列表中每个节点的深度链接，addNode方法必须是这样的：
void addNode(struct node *head, int n) {
if (head->Next == NULL) {
struct node *NewNode = new node;
NewNode->value = n;
NewNode->Next = NULL;
head->Next = NewNode;
}
else
addNode(head->Next, n);
}
回答by Vladimir Popov
In a code there is a mistake:
在一段代码中有一个错误：
void deleteNode ()
{
for (Node * temp = head; temp! = NULL; temp = temp-> next)
delete head;
}
It is necessary so:
有必要这样：
for (; head != NULL; )
{
Node *temp = head;
head = temp->next;
delete temp;
}
