Реализация простого связанного списка в C ++

Question

Я студент по программированию в моем первом классе C ++, и недавно мы рассмотрели связанные списки, и нам было дано задание для реализации простого. Я закодировал все, кроме моей функции pop_back(), которая должна возвращать указатель на Node, который необходимо удалить в Main(). Нет Node удаление должно быть сделано в фактической функции. Итак, мой вопрос:

Не могли бы вы помочь мне указать верное направление для моей функции pop_back()? Кроме того, если вы заметили что-то еще, что я делаю неправильно, дайте мне знать.

Кроме того, этот связанный список предназначен только для работы со строками. В этом случае список покупок, поэтому одна строка для количества товара (1,2), и одна строка для типа товара. (Молоко, яйца и т. Д.)

Ниже я включил свои реализации классов List & Node, чтобы вы могли получить представление о том, что я сделал до сих пор.

node.cpp

Node::Node(void)
{
    descrip = " ";
    quantity = " ";
    previous = NULL;
    next = NULL;
}
Node::Node(string q, string d)
{
    descrip = d;
    quantity = q;
    previous = NULL;
    next = NULL;
}
Node* Node::GetNext()
{
    return next;
}
Node* Node::GetPrevious()
{
    return previous;
}
void Node::SetNext(Node * setter)
{
    next = setter;
}
void Node::SetPrevious(Node * setter)
{
    previous = setter;
}

---

List.cpp

List::List(void)
{
   first = NULL;
   last = NULL;
   numNodes = 0;
}
Node* List::GetFirst()
{
    return first;
}
Node* List::GetLast()
{
    return last;
}
void List::SetFirst(Node* setter)
{
    first = setter;
}
void List::SetLast(Node* setter)
{
    last = setter;
}
int List::GetNumNodes()
{
    return numNodes;
}
void List::push_front(Node* item)
{
   if (first == NULL)
   {
       first = item;
       last = item;
   }
   else 
   {
       Node* pFirst = first;
       item->SetNext(pFirst);
       first = item;
       numNodes++;
   }
}
void List::push_back(Node * item)
{
    if (last == NULL)
    {
       first = item;
       last = item;
    }
    else 
    {
        last->SetNext(item);
        last = item;
        numNodes++;
    }
}
Node* List::pop_front()
{
    Node* temp = first;
    first = first->GetNext();
    if (first == NULL)
    {
        temp = first->GetNext();
        first = p;
    }
    if (first == NULL)
    {
        last = NULL;
    }
    if (numNodes > 0)
    {
        numNodes--;
    }
    return temp;
}
Node* List::pop_back() // this whole function may be wrong, this is just my attempt at it
{
    Node* temp;
    temp = first;

    while((temp->GetNext()) != NULL)
        // im stuck here

}

Answer 1

Некоторые указатели:

0x1243bfa3
0x45afc56e
0xdeadbeef

Еще несколько указателей:

1. Вы должны предпочесть инициализировать членов вашего класса в списке инициализации, а не в теле конструктора.

2. В C ++, в отличие от C89, мы объявляем и определяем функцию без параметров как void f();, а не void f(void);.

3. В C ++ мы обычно сбрасываем указатели с 0, а не NULL.

   Смотрите ниже то, что я имею в виду в коде.

4. Хороший код C ++ попытается воспользоваться RAII . Это подразумевает избегание примитивных указателей по большей части. В этом случае простой старый std::auto_ptr<> будет вполне достаточным заменителем простых указателей Node*. Тем не менее, я считаю, что часть упражнения здесь - это арифметика указателей, и поэтому я просто оставляю это как примечание.

5. Было бы полезно для нас, если бы вы прикрепили объявления класса. Я предполагаю, что все эти аксессоры и мутаторы, GetFirst() и SetFirst() и т. Д., Присутствуют, потому что они общедоступны. Это плохая идея. Во-первых, они выставляют частные указатели, которые побеждают всю точку доступа. Во-вторых, они не делают ничего особенного, поэтому они просто дополнительный код - что означает дополнительное пространство для ошибок. Это подводит меня к следующему пункту.

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

7. Когда-нибудь пытались pop_front(), когда список пуст?

8. Наконец, 8 - круглое число, пришло время перейти к рассматриваемому вопросу. pop_back(). Мой вопрос к вам: почему вы пересекаете список до самого конца, если вы так тщательно поддерживаете указатель на последний узел вашего списка? В самом деле, если вы не будете беспокоиться о сохранении указателя на конец списка, вам придется пройти весь путь до последнего узла, чтобы открыть его. И для этого вы были в правильном направлении. Кроме того ...

9. Когда вы обращаетесь к членам через указатели, как в first->GetNext(), всегда , убедитесь, что first не является нулевым указателем - или же укажите в комментарии к документации функции, который вы принимаете указатель не является нулевым.

Это должно помочь вам начать.

Пункты 1, 2 и 3 в коде:

Node::Node()
: descrip(" "), quantity(" "), previous(0), next(0)
{
}

Answer 2

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

Node* List::pop_back() // this whole function may be wrong, this is just my attempt at it  
{  
    Node* temp;  
    temp = first;  
    while(temp->GetNext() != NULL)  
    {  
        temp = temp->GetNext();  
    }  
    return temp;  
}

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

Answer 3

Мне нравится ответ предыдущего постера, но одну вещь, которую вы могли бы иметь в виду, - это если у вас есть пустой список. Тогда ваш первый указатель будет равен NULL, и вы будете пытаться вызвать NULL-> GetNext () в основном и Seg Fault. Я думаю, что вы можете немного отредактировать приведенный выше код и все же получить его так:

Node* List::pop_back() 
{  
    Node* temp;  
    temp = first;  
    while(temp != NULL && temp->GetNext() != NULL)  
    {  
        temp = temp->GetNext();  
    }  
    return temp;  
}

Функция вернет NULL, если в списке ничего нет, и все еще будет работать правильно.

Answer 4

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

Node* List::pop_back()
{
  Node *temp = NULL;
  if(numNodes == 1) 
  {
    temp = first;
    // setting the list pointers to NULL
    first = NULL;
    // setting the list pointers to NULL 
    last = NULL; 
    //You should also probably remove the links from your node 
    //to the next and previous nodes but since you didn't specify 
    //this it is up to you
    numNodes--;
  }
  else if(numNodes > 1) //more than one element
  {
    //the pointer you want to return
    temp = last;
    //For clarity I am creating another variable here
    Node *newLast = temp->GetPrevious(); 
    //Setting the new last node to point at nothing so now temp 
    //is "disconnected from the list"
    newLast->next = NULL; 
    //the last pointer of the list is now pointing at the new last node
    last = newLast;         
//You should also probably remove the links from your node 
//to the next and previous nodes but since you didn't specify this it is up to you
        numNodes--; //decrement the counter
      }
      return temp;
    }