为什么链表使用指针而不是在节点内存储节点

Question

我之前在Java中广泛使用链表,但我对C++很新.我正在使用在项目中给我的这个节点类就好了

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

但我有一个问题没有得到很好的回答.为什么有必要使用

Node *m_next;

指向列表中的下一个节点而不是

Node m_next;

我知道最好使用指针版本; 我不会争论事实,但我不知道为什么它会更好.关于指针如何更好地用于内存分配,我得到了一个不太清楚的答案,我想知道这里是否有人可以帮助我更好地理解它.

Answer 1

这不仅仅是更好,它是唯一可能的方式.

如果你在自己内部存储了一个Node 对象,会sizeof(Node)是什么？它将sizeof(int) + sizeof(Node)等于sizeof(int) + (sizeof(int) + sizeof(Node)),等于sizeof(int) + (sizeof(int) + (sizeof(int) + sizeof(Node)))无限等等.

像这样的对象不可能存在.这是不可能的.

Answer 2

在Java中

Node m_node

存储指向另一个节点的指针.你没有选择它.在C++中

Node *m_node

意思是一样的.不同之处在于,在C++中,您实际上可以存储对象而不是指向它的指针.这就是为什么你不得不说你想要一个指针.在C++中:

Node m_node

意味着在这里存储节点(显然不能用于列表 - 最终得到一个递归定义的结构).

Answer 3

C++不是Java.当你写作

Node m_next;

在Java中,这与写作相同

Node* m_next;

在C++中.在Java中,指针是隐式的,在C++中它是显式的.如果你写

Node m_next;

在C++中,您将一个实例Node放在您定义的对象中.它始终存在,不能省略,不能分配,new也不能删除.这种效果在Java中是不可能实现的,它与Java使用相同语法完全不同.

Answer 4

你使用指针,否则你的代码:

class Node
{
   //etc
   Node m_next; //non-pointer
};

... 不会编译,因为编译器无法计算大小Node.这是因为它依赖于自身 - 这意味着编译器无法决定它将消耗多少内存.

Answer 5

后者(Node m_next)必须包含节点.它不会指向它.然后就没有元素的联系.

Answer 6

您描述的方法不仅与C++兼容,而且与其(主要)子集语言C兼容.学习开发C风格的链表是一种向低级编程技术(如手动内存管理)介绍自己的好方法,但它通常不是现代C++开发的最佳实践.

下面,我已经实现了如何管理C++中的项列表的四种变体.

1. raw_pointer_demo使用与您相同的方法 - 使用原始指针所需的手动内存管理.这里使用C++仅用于语法糖,并且所使用的方法与C语言兼容.
2. 在shared_pointer_demo列表管理中仍然手动完成,但内存管理是自动的(不使用原始指针).这与您在Java中可能遇到的非常相似.
3. std_list_demo使用标准库list容器.这表明,如果您依赖现有的库而不是自己的库,那么事情会变得多么简单.
4. std_vector_demo使用标准库vector容器.这将在单个连续内存分配中管理列表存储.换句话说,没有指向单个元素的指针.对于某些相当极端的情况,这可能会变得非常低效.但是,对于典型情况,这是C++中列表管理的推荐最佳实践.

值得注意的是:在所有这些中,只有raw_pointer_demo实际上要求明确销毁列表以避免"泄漏"内存.当容器超出范围时(在函数结束时),其他三种方法将自动销毁列表及其内容.关键在于:C++在这方面能够非常"类似Java" - 但前提是您选择使用高级工具开发程序.

/*BINFMTCXX: -Wall -Werror -std=c++11
*/

#include <iostream>
#include <algorithm>
#include <string>
#include <list>
#include <vector>
#include <memory>
using std::cerr;

/** Brief   Create a list, show it, then destroy it */
void raw_pointer_demo()
{
    cerr << "\n" << "raw_pointer_demo()..." << "\n";

    struct Node
    {
        Node(int data, Node *next) : data(data), next(next) {}
        int data;
        Node *next;
    };

    Node * items = 0;
    items = new Node(1,items);
    items = new Node(7,items);
    items = new Node(3,items);
    items = new Node(9,items);

    for (Node *i = items; i != 0; i = i->next)
        cerr << (i==items?"":", ") << i->data;
    cerr << "\n";

    // Erase the entire list
    while (items) {
        Node *temp = items;
        items = items->next;
        delete temp;
    }
}

raw_pointer_demo()...
9, 3, 7, 1

/** Brief   Create a list, show it, then destroy it */
void shared_pointer_demo()
{
    cerr << "\n" << "shared_pointer_demo()..." << "\n";

    struct Node; // Forward declaration of 'Node' required for typedef
    typedef std::shared_ptr<Node> Node_reference;

    struct Node
    {
        Node(int data, std::shared_ptr<Node> next ) : data(data), next(next) {}
        int data;
        Node_reference next;
    };

    Node_reference items = 0;
    items.reset( new Node(1,items) );
    items.reset( new Node(7,items) );
    items.reset( new Node(3,items) );
    items.reset( new Node(9,items) );

    for (Node_reference i = items; i != 0; i = i->next)
        cerr << (i==items?"":", ") << i->data;
    cerr<<"\n";

    // Erase the entire list
    while (items)
        items = items->next;
}

shared_pointer_demo()...
9, 3, 7, 1

/** Brief   Show the contents of a standard container */
template< typename C >
void show(std::string const & msg, C const & container)
{
    cerr << msg;
    bool first = true;
    for ( int i : container )
        cerr << (first?" ":", ") << i, first = false;
    cerr<<"\n";
}

/** Brief  Create a list, manipulate it, then destroy it */
void std_list_demo()
{
    cerr << "\n" << "std_list_demo()..." << "\n";

    // Initial list of integers
    std::list<int> items = { 9, 3, 7, 1 };
    show( "A: ", items );

    // Insert '8' before '3'
    items.insert(std::find( items.begin(), items.end(), 3), 8);
    show("B: ", items);

    // Sort the list
    items.sort();
    show( "C: ", items);

    // Erase '7'
    items.erase(std::find(items.begin(), items.end(), 7));
    show("D: ", items);

    // Erase the entire list
    items.clear();
    show("E: ", items);
}

std_list_demo()...
A:  9, 3, 7, 1
B:  9, 8, 3, 7, 1
C:  1, 3, 7, 8, 9
D:  1, 3, 8, 9
E:

/** brief  Create a list, manipulate it, then destroy it */
void std_vector_demo()
{
    cerr << "\n" << "std_vector_demo()..." << "\n";

    // Initial list of integers
    std::vector<int> items = { 9, 3, 7, 1 };
    show( "A: ", items );

    // Insert '8' before '3'
    items.insert(std::find(items.begin(), items.end(), 3), 8);
    show( "B: ", items );

    // Sort the list
    sort(items.begin(), items.end());
    show("C: ", items);

    // Erase '7'
    items.erase( std::find( items.begin(), items.end(), 7 ) );
    show("D: ", items);

    // Erase the entire list
    items.clear();
    show("E: ", items);
}

std_vector_demo()...
A:  9, 3, 7, 1
B:  9, 8, 3, 7, 1
C:  1, 3, 7, 8, 9
D:  1, 3, 8, 9
E:

int main()
{
    raw_pointer_demo();
    shared_pointer_demo();
    std_list_demo();
    std_vector_demo();
}

Answer 7

概观

有两种方法可以在C++中引用和分配对象,而在Java中只有一种方法.

为了解释这一点,下图显示了对象如何存储在内存中.

1.1没有指针的C++项

class AddressClass
{
  public:
    int      Code;
    char[50] Street;
    char[10] Number;
    char[50] POBox;
    char[50] City;
    char[50] State;
    char[50] Country;
};

class CustomerClass
{
  public:
    int          Code;
    char[50]     FirstName;
    char[50]     LastName;
    // "Address" IS NOT A pointer !!!
    AddressClass Address;
};

int main(...)
{
   CustomerClass MyCustomer();
     MyCustomer.Code = 1;
     strcpy(MyCustomer.FirstName, "John");
     strcpy(MyCustomer.LastName, "Doe");
     MyCustomer.Address.Code = 2;
     strcpy(MyCustomer.Address.Street, "Blue River");
     strcpy(MyCustomer.Address.Number, "2231 A");

   return 0;
} // int main (...)

.......................................
..+---------------------------------+..
..|          AddressClass           |..
..+---------------------------------+..
..| [+] int:      Code              |..
..| [+] char[50]: Street            |..
..| [+] char[10]: Number            |..
..| [+] char[50]: POBox             |..
..| [+] char[50]: City              |..
..| [+] char[50]: State             |..
..| [+] char[50]: Country           |..
..+---------------------------------+..
.......................................
..+---------------------------------+..
..|          CustomerClass          |..
..+---------------------------------+..
..| [+] int:      Code              |..
..| [+] char[50]: FirstName         |..
..| [+] char[50]: LastName          |..
..+---------------------------------+..
..| [+] AddressClass: Address       |..
..| +-----------------------------+ |..
..| | [+] int:      Code          | |..
..| | [+] char[50]: Street        | |..
..| | [+] char[10]: Number        | |..
..| | [+] char[50]: POBox         | |..
..| | [+] char[50]: City          | |..
..| | [+] char[50]: State         | |..
..| | [+] char[50]: Country       | |..
..| +-----------------------------+ |..
..+---------------------------------+..
.......................................

警告:此示例中使用的C++语法类似于Java中的语法.但是,内存分配是不同的.

1.2使用指针的C++项

class AddressClass
{
  public:
    int      Code;
    char[50] Street;
    char[10] Number;
    char[50] POBox;
    char[50] City;
    char[50] State;
    char[50] Country;
};

class CustomerClass
{
  public:
    int           Code;
    char[50]      FirstName;
    char[50]      LastName;
    // "Address" IS A pointer !!!
    AddressClass* Address;
};

.......................................
..+-----------------------------+......
..|        AddressClass         +<--+..
..+-----------------------------+...|..
..| [+] int:      Code          |...|..
..| [+] char[50]: Street        |...|..
..| [+] char[10]: Number        |...|..
..| [+] char[50]: POBox         |...|..
..| [+] char[50]: City          |...|..
..| [+] char[50]: State         |...|..
..| [+] char[50]: Country       |...|..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|         CustomerClass       |...|..
..+-----------------------------+...|..
..| [+] int:      Code          |...|..
..| [+] char[50]: FirstName     |...|..
..| [+] char[50]: LastName      |...|..
..| [+] AddressClass*: Address  +---+..
..+-----------------------------+......
.......................................

int main(...)
{
   CustomerClass* MyCustomer = new CustomerClass();
     MyCustomer->Code = 1;
     strcpy(MyCustomer->FirstName, "John");
     strcpy(MyCustomer->LastName, "Doe");

     AddressClass* MyCustomer->Address = new AddressClass();
     MyCustomer->Address->Code = 2;
     strcpy(MyCustomer->Address->Street, "Blue River");
     strcpy(MyCustomer->Address->Number, "2231 A");

     free MyCustomer->Address();
     free MyCustomer();

   return 0;
} // int main (...)

如果你检查两种方式之间的区别,你会看到,在第一种技术中,地址项是在客户中分配的,而第二种方式,你必须明确地创建每个地址.

警告: Java像第二种技术那样在内存中分配对象,但是,语法就像第一种方式,这可能会让新手对"C++"感到困惑.

履行

因此,您的列表示例可能类似于以下示例.

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

.......................................
..+-----------------------------+......
..|            Node             |......
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|            Node             +<--+..
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................|..
..+-----------------------------+...|..
..|            Node             +<--+..
..+-----------------------------+......
..| [+] int:           m_data   |......
..| [+] Node*:         m_next   +---+..
..+-----------------------------+...|..
....................................v..
...................................[X].
.......................................

摘要

由于链接列表具有可变数量的项目,因此根据需要分配内存,并且可用.

更新:

另外值得一提,正如@haccks在他的帖子中评论道.

有时,引用或对象指针指示嵌套项(也称为"UML组合").

有时,引用或对象指针指示外部项(也称为"UML聚合").

但是,同一类的嵌套项不能应用"无指针"技术.

Answer 8

在旁注中,如果类或结构的第一个成员是下一个指针(因此没有虚函数或类的任何其他特征,这意味着下一个不是类或结构的第一个成员),那么你可以使用只有下一个指针的"基础"类或结构,并使用公共代码进行基本链接列表操作,如追加,插入之前,从前面检索,.... 这是因为C/C++保证类或结构的第一个成员的地址与类或结构的地址相同.基节点类或​​结构只有一个下一个指针供基本链表函数使用,然后根据需要使用类型转换来在基节点类型和"派生"节点类型之间进行转换.旁注 - 在C++中,如果基节点类只有下一个指针,那么我假设派生类不能有虚函数.

Answer 9

为什么在链表中使用指针更好？

原因是当您创建Node对象时,编译器必须为该对象分配内存,并为此计算对象的大小.
指向任何类型的指针的大小对于编译器是已知的,因此可以计算对象的自引用指针大小.

如果Node m_node使用if 而编译器不知道Node它的大小,它将陷入计算的无限递归sizeof(Node).永远记住:一个类不能包含自己类型的成员.

Answer 10

因为这在C++中

int main (..)
{
    MyClass myObject;

    // or

    MyClass * myObjectPointer = new MyClass();

    ..
}

在Java中等同于此

public static void main (..)
{
    MyClass myObjectReference = new MyClass();
}

其中两个都创建了一个MyClass使用默认构造函数的新对象.