Что, если я помещу все узлы LinkedList в массив? - PullRequest
Новая
       54

Что, если я помещу все узлы LinkedList в массив?

0 голосов
/ 06 мая 2020

В последнее время я изучал C ++, а сейчас изучаю Linkedlist.

Мне интересно, почему бы нам не создать узлы с массивом, скажем: 

#include <iostream>
using namespace std;

struct Node {
    int data = 0; //data
    Node* next = nullptr; //next node in the linked list;
};


void deallocateLinkedList(Node* n)
{
 if (n == nullptr) // An empty list; nothing to delete
  return;
 else{
  deallocateLinkedList(n->next);
  delete n;
  n = nullptr;
 }

}

int main()
{

 int k;
 cout<<"enter k as number of nodes"<<endl;
 cin>>k;

 Node* n = new Node [k];                //creates dynamic array;
 for(int i =0;i<k;i++)
 {
  if (i==k-1)
  {
   n[i].data=i;
   n[i].next=nullptr;
  }
  else
  {
   n[i].data=i;
   n[i].next = &n[i+1];
  }
 }
 deallocateLinkedList(n);               //pointer points to the first node;

 cout<<"programmed finished"<<endl;     //indicates successful running


 return 0;
}

В этом случае узлы связаны и также помещаются в массив;

Однако программа освобождения памяти не запускается полностью и завершается без ошибок

Есть ли какие-либо проблемы с этим стилем создание связного списка или просто проблема с освобождением?

1 Ответ

0 голосов
/ 06 мая 2020

Что, если я помещу все узлы LinkedList в массив?

Тогда вот где находятся узлы.

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

Есть ли с этим проблемы?

Да, есть проблема.

Проблема в том, что вы можете пройти только указатель на delete, если вы получили указатель из new (и он должен быть удален не более одного раза, а если вы создали массив, вы должны использовать delete[]).

Когда вы это сделаете delete n;, вы обнаружите, что никогда не назначали какой-либо из n->next (который будет n в рекурсивном вызове) иметь значение указателя, которое было возвращено из new. Как следствие, поведение программы не определено.

Если вы выделяете объекты следующим образом: 

Node* n = new Node [k];

, то вы должны освободить место следующим образом: 

delete[] n;
...