Подтвердить что ты не робот

Почему в связанных списках используются указатели вместо хранения узлов внутри узлов

Я работал со связанными списками раньше, чем на Java, но я очень новичок в С++. Я использовал этот класс node, который был предоставлен мне в проекте просто отлично

class Node
{
  public:
   Node(int data);

   int m_data;
   Node *m_next;
};

но у меня был один вопрос, на который не ответил очень хорошо. Почему необходимо использовать

Node *m_next;

чтобы указать на следующий node в списке вместо

Node m_next;

Я понимаю, что лучше использовать версию указателя; Я не собираюсь спорить с фактами, но я не знаю, почему это лучше. Я получил не столь ясный ответ о том, как лучше указатель для распределения памяти, и мне было интересно, может ли кто-нибудь здесь помочь мне понять, что лучше.

4b9b3361

ОТВЕТЫ

Ответ 1

Это не просто лучше, это единственный возможный способ.

Если вы сохранили объект Node внутри себя, что бы было sizeof(Node)? Это будет sizeof(int) + sizeof(Node), который будет равен sizeof(int) + (sizeof(int) + sizeof(Node)), который будет равен sizeof(int) + (sizeof(int) + (sizeof(int) + sizeof(Node))) и т.д. До бесконечности.

Подобный объект не может существовать. Это невозможно.

Ответ 2

В Java

Node m_node

хранит указатель на другой node. У вас нет выбора. В С++

Node *m_node

означает одно и то же. Разница в том, что в С++ вы можете фактически сохранить объект, а не указатель на него. Вот почему вы должны сказать, что хотите указатель. В С++:

Node m_node

означает, что здесь хранится node (и это явно не может работать для списка - вы получаете рекурсивно определенную структуру).

Ответ 3

С++ не является Java. Когда вы пишете

Node m_next;

в Java, это то же самое, что и запись

Node* m_next;

в С++. В Java указатель неявный, в С++ он явный. Если вы пишете

Node m_next;

в С++, вы помещаете экземпляр Node прямо внутри объекта, который вы определяете. Он всегда присутствует и не может быть опущен, его нельзя выделить с помощью new, и его нельзя удалить. Этот эффект невозможно достичь в Java, и он полностью отличается от того, что делает Java с тем же синтаксисом.

Ответ 4

Вы используете указатель, иначе ваш код:

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

... будет компилироваться не, поскольку компилятор не может вычислить размер Node. Это потому, что оно зависит от самого себя; что означает, что компилятор не может решить, сколько памяти он будет потреблять.

Ответ 5

Последний (Node m_next) должен содержать node. Это не указывало бы на это. И тогда не было бы связывания элементов.

Ответ 6

Подход, который вы описываете, совместим не только с С++, но и с (главным образом) языком подмножества C. Изучение связанного списка C-style - это хороший способ представить себя низкоуровневым методам программирования (например, ручное управление памятью), но, как правило, это не лучшая практика для современной разработки на С++.

Ниже я реализовал четыре варианта управления списком элементов на С++.

  • raw_pointer_demo использует тот же подход, что и ваш, - ручное управление памятью, требуемое с использованием необработанных указателей. Использование С++ здесь только для синтаксического сахара, и используемый подход в противном случае совместим с языком C.
  • В shared_pointer_demo управление списками все еще выполняется вручную, но управление памятью автоматическое (не использует необработанные указатели). Это очень похоже на то, что вы, вероятно, испытали с Java.
  • std_list_demo использует контейнер стандартной библиотеки list. Это показывает, насколько проще получить все, если вы полагаетесь на существующие библиотеки, а не на свой собственный.
  • std_vector_demo использует контейнер стандартной vector. Это управляет хранением списка в одном смежном распределении памяти. Другими словами, нет указателей на отдельные элементы. В некоторых довольно экстремальных случаях это может стать значительно неэффективным. Однако для типичных случаев это рекомендуемая передовая практика для управления списками на С++.

Примечание. Из всего этого только raw_pointer_demo фактически требует, чтобы список был явно уничтожен, чтобы избежать "утечки" памяти. Остальные три метода автоматически уничтожают список и его содержимое, когда контейнер выходит за рамки (по завершении функции). Дело в том, что С++ способен быть очень "подобным 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();
}

Ответ 7

Обзор

Есть два способа ссылки и выделения объектов на С++, в то время как в Java есть только один способ.

Чтобы объяснить это, следующие диаграммы показывают, как объекты хранятся в памяти.

1.1 С++ Элементы без указателей

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       | |..
..| +-----------------------------+ |..
..+---------------------------------+..
.......................................

Предупреждение. Синтаксис С++, используемый в этом примере, похож на синтаксис Java. Но распределение памяти отличается.

1.2 С++ Элементы с помощью указателей

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 выделяет объекты в памяти, подобные этой второй технике, но синтаксис похож на первый способ, который может смущать новичков на "С++".

Реализация

Таким образом, ваш пример списка может быть чем-то похожим на следующий пример.

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].
.......................................

Резюме

Поскольку связанный список имеет переменное количество элементов, память выделяется как требуется и, как доступно.

UPDATE:

Также стоит упомянуть, как @haccks прокомментировал в своем посте.

В некоторых случаях ссылки или указатели объектов указывают на вложенные элементы (a.k.a. "U.M.L. Composition" ).

И иногда ссылки или указатели объектов указывают внешние элементы (a.k.a. "Агрегация U.M.L." ).

Но вложенные элементы одного и того же класса не могут применяться с помощью метода "без указателей".

Ответ 8

На стороне примечания, если самый первый член класса или структуры является следующим указателем (поэтому никакие виртуальные функции или любая другая функция класса, которая будет означать следующее, не является первым членом класса или структуры), то вы можете использовать "базовый" класс или структуру с помощью всего лишь следующего указателя и использовать общий код для основных операций с связанным списком, таких как append, insert before, retrieve from front,.... Это связано с тем, что C/С++ гарантирует, что адрес первого члена класса или структуры совпадает с адресом класса или структуры. Базовый класс или структура node будет иметь только следующий указатель, который будет использоваться основными функциями связанного списка, тогда при необходимости будет использоваться приведение типов при преобразовании между базовым типом node и типами "производных" node. Side note - на С++, если базовый класс node имеет только следующий указатель, то я предполагаю, что производные классы не могут иметь виртуальные функции.

Ответ 9

Почему лучше использовать указатели в связанном списке?

Причина в том, что при создании объекта Node компилятор должен выделять память для этого объекта и для этого рассчитывается размер объекта.
Размер указателя на какой-либо тип известен компилятору, и поэтому может быть рассчитан размер референтного указателя объекта.

Если вместо этого используется Node m_node, тогда компилятор понятия не имеет о размере Node, и он застрял бы в бесконечной рекурсии вычисления sizeof(Node). Всегда помните: класс не может содержать член своего типа.

Ответ 10

Потому что это в С++

int main (..)
{
    MyClass myObject;

    // or

    MyClass * myObjectPointer = new MyClass();

    ..
}

эквивалентно этому в Java

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

где оба они создают новый объект MyClass с использованием конструктора по умолчанию.