использование нового оператора при создании связанного списка - PullRequest
Новая
       22

использование нового оператора при создании связанного списка

3 голосов
/ 29 августа 2011

В следующей программе: 

// illustration of linked list
#include <iostream>

using namespace std;

struct node {
    int data;
    struct node* next;
};

struct node* buildList();

int main() {

struct node* head = buildList();
cout << head->data;
}

struct node* buildList() {
    struct node* head = NULL;
    struct node* second = NULL;
    struct node* third = NULL;

    head = new node;      // builds up a pointer structure on heap
    second = new node;
    third = new node;

    head->data = 1;
    head->next = second;

    head->data = 2;
    second->next = third;

    head->data = 3;
    third->next = NULL;

    return head;
}

Я не знаю о работе оператора new здесь. Какую задачу они выполняют? (я читал, что он выделяет место в куче. Но я не знаю, что это значит) Если я удаляю эти операторы, выходных данных нет, и программа падает. Почему это так?

Ответы [ 4 ]

3 голосов
/ 29 августа 2011

Переменные заголовка, второй и третьей являются указателями на узлы в памяти.Но, прежде чем вы сможете их использовать, они должны указывать на действительный узел в памяти.Вот тут и вступает новый оператор. Куча - это просто область памяти, выделенная вашей программе для динамического создания объектов (в отличие от стека. См. здесь , чтобы узнать разницу).

3 голосов
/ 29 августа 2011

* РЕДАКТИРОВАТЬ *

Я просто подумал, что добавлю перед моим ответом:

Стек, проще говоря, место, где находится ваша программав настоящее время работает и несколько временно.Я имею в виду, что ваша функция main () может вызывать другую функцию.Эта функция будет иметь свою собственную область видимости (область между {}), свои собственные локальные переменные, пробел и т. Д. Она, в свою очередь, может вызывать другую функцию.Эти функции продолжают помещаться «в стек».Как только функция вернется, она будет удалена из стека, и вы вернетесь к точке в функции повышения уровня следующего уровня, в которой вы начали.Это как если бы вы положили лист бумаги поверх вашей текущей тетради, сделали несколько заметок, а затем удалили его, чтобы вернуться на исходную страницу.«Переменные стека» - это те, которые вы создаете обычным способом внутри функции, и они умирают / разрушаются при выходе из области действия.

Переменные кучи - это статические / глобальные переменные или переменные, созданные с использованием «new, malloc,так далее."Эти переменные являются постоянными и будут сохраняться / существовать до тех пор, пока вы не вызовете их явно.Они выживут за пределами области, в которой они были созданы, и если вы не отследите их, их ресурсы будут недоступны, и у вас будет утечка памяти / ресурсов.

Normal Post

Строки: 

struct node* head = NULL;
struct node* second = NULL;
struct node* third = NULL;

все создают указатели * после того, как узел заявляет, что это указатель на узел.Эти указатели инициализируются как NULL или 0. Указатель - это просто адрес / местоположение в памяти, в нем еще нет объекта узла.Таким образом, 

node* ptr = NULL;  //creates pointer to a node object, but no node itself.
node  obj;         //creates an actual node object on the stack.

Указатели могут использоваться для указания на основанный на стеке объект, взяв его адрес с помощью оператора & следующим образом: 

node obj;  //Real object.
node* ptr = &obj;  //ptr points to the "address of" obj.

В вашем случае указатель узла нене указывайте ни на что, пока вы не создадите это с "новым".После этого указатель указывает на «динамически выделенную» память, которая будет сохраняться вечно до тех пор, пока вы не вызовете «удалить» из нее.Преимущество этого в том, что память может сохраняться вне функции, в которой она создана.Итак: 

void myFunction()
{
    node obj;
}  //obj dies here.

void myOtherFunction()
{
    node* ptr = new obj;
} //the "node" created by new will survive after this.

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

0 голосов
/ 29 августа 2011

new создает новый объект этого типа.

В этом случае вы создаете новый узел. Однако в некотором коде вам не нужно этого делать, вместо этого вы можете просто использовать объекты. то есть голова узла; head.data = 1; head.next = бла.

Причина использования new заключается в простом создании «нового» объекта этого типа. Обычно используется для динамической вещи, в этом случае это выглядит как какой-то связанный список, так что да, вам потребуется новый. Но с каждым новым вам нужно удалять данные, когда вы закончите с в противном случае у вас будет утечка памяти, и в этом случае чем больше список, и вы не будете деконструировать вещи, которые больше не требуются, тем больше памяти будет потрачено впустую.

Однако вам вообще не нужно использовать этот код. Скорее уже есть контейнер в стандартной библиотеке, которая предлагает этот тип поддержки, а также дополнительные функции на стороне. 

#include <list> 
// and use
std::list<type> data;

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

0 голосов
/ 29 августа 2011

struct node* head = NULL; -> создает указатель (указывает на ноль из-за присваивания)

head = new node; -> выделяет память под размер узла и указывает на начало этой памяти

так что если ваш указатель равен NULL и вы никогда не говорите ему указывать на узел (или что-либо еще), то любые операции с этим указателем или с этим указателем завершатся неудачей

...