C++-Vorlagen - LinkedList

Question

EDIT -- Unten geantwortet, die abgewinkelten Klammern übersehen. Vielen Dank an alle.

Ich habe versucht, eine rudimentäre, einfach verknüpfte Liste zu schreiben, die ich in anderen Programmen verwenden kann. Ich möchte, dass sie mit eingebauten und benutzerdefinierten Typen arbeiten kann, was bedeutet, dass sie eine Vorlage sein muss.

Aus diesem Grund muss mein Knoten auch eine Vorlage sein, da ich die Informationen, die er speichern soll, nicht kenne. Ich habe eine Knotenklasse wie folgt geschrieben -

template <class T> class Node
{
    T data; //the object information
    Node* next; //pointer to the next node element

public:
    //Methods omitted for brevity
};

Meine verknüpfte Liste Klasse ist in einer separaten Klasse implementiert, und muss einen Knoten instanziieren, wenn neue Knoten am Ende der Liste hinzufügen. Ich habe dies wie folgt implementiert -

#include <iostream>
#include "Node.h"
using namespace std;

template <class T> class CustomLinkedList
{
    Node<T> *head, *tail;

public:

    CustomLinkedList()
    {
        head = NULL;
        tail = NULL;
    }

    ~CustomLinkedList()
    {

    }

    //Method adds info to the end of the list
    void add(T info)
    {
        if(head == NULL) //if our list is currently empty
        {
            head = new Node<T>; //Create new node of type T
            head->setData(info);
            tail = head;
        }
        else //if not empty add to the end and move the tail
        {
            Node* temp = new Node<T>;
            temp->setData(info);
            temp->setNextNull();
            tail->setNext(temp);
            tail = tail->getNext();
        }
    }

    //print method omitted
};

Ich habe eine Treiber-/Testklasse wie folgt eingerichtet -

#include "CustomLinkedList.h"
using namespace std;

int main()
{
    CustomLinkedList<int> firstList;

    firstList.add(32);
    firstList.printlist();
    //Pause the program until input is received
    int i;
    cin >> i;

    return 0;
}

Ich erhalte jedoch einen Fehler beim Kompilieren - Fehler C2955: 'Node': Verwendung einer Klassenvorlage erfordert Vorlagenargumentliste - die mich auf die folgende Codezeile in meiner add-Methode verweist -

Node* temp = new Node<T>;

Ich verstehe nicht, warum dies keine Informationen über den Typ hat, da es an die verknüpfte Liste übergeben wurde, wenn in meiner Treiberklasse erstellt. Was sollte ich tun, um die Typinformationen an Node zu übergeben?

Sollte ich eine private Knotenstruktur anstelle einer separaten Klasse erstellen und die Methoden beider Klassen in einer Datei kombinieren? Ich bin nicht sicher, ob dies das Problem lösen würde, aber ich denke, es könnte. Ich würde aber lieber getrennte Klassen haben, wenn möglich.

Danke, Andrew.

Answer 1

Obwohl die Antworten bereits gegeben wurden, möchte ich meinen Senf dazugeben.

Beim Entwurf von Klassenvorlagen ist es eine gute Idee, die Argumente der Vorlage nicht überall zu wiederholen, nur für den Fall, dass Sie (eines Tages) ein bestimmtes Detail ändern möchten. Im Allgemeinen wird dies durch die Verwendung von Typdefs erreicht.

template <class T>
class Node
{
public:
  // bunch of types
  typedef T value_type;
  typedef T& reference_type;
  typedef T const& const_reference_type;
  typedef T* pointer_type;
  typedef T const* const_pointer_type;

  // From now on, T should never appear
private:
  value_type m_value;
  Node* m_next;
};

template <class T>
class List
{
  // private, no need to expose implementation
  typedef Node<T> node_type;

  // From now on, T should never appear
  typedef node_type* node_pointer;

public:
  typedef typename node_type::value_type value_type;
  typedef typename node_type::reference_type reference_type;
  typedef typename node_type::const_reference_type const_reference_type;
  // ...

  void add(value_type info);

private:
  node_pointer m_head, m_tail;
};

Es ist auch besser, die Methoden außerhalb der Klassendeklaration zu definieren, damit die Schnittstelle leichter zu lesen ist.

template <class T>
void List<T>::add(value_type info)
{
  if(head == NULL) //if our list is currently empty
  {
    head = new node_type;
    head->setData(info);
    tail = head;
  }
  else //if not empty add to the end and move the tail
  {
    Node* temp = new node_type;
    temp->setData(info);
    temp->setNextNull();
    tail->setNext(temp);
    tail = tail->getNext();
  }
}

Nun noch ein paar Bemerkungen:

• Es wäre benutzerfreundlicher, wenn List<T>::add einen Iterator zu den neu hinzugefügten Objekten zurück, wie insert Methoden in der STL tun (und man könnte sie auch in Insert umbenennen)
• bei der Durchführung von List<T>::add Sie weisen Speicher zu temp dann eine Reihe von Operationen durchführen, wenn eine davon fehlschlägt, ist Speicherplatz verloren gegangen
• el setNextNull Aufruf sollte nicht notwendig sein: Der Konstruktor von Node sollten alle Datenelemente auf sinnvolle Werte initialisiert werden, einschließlich m_next

Hier ist also eine überarbeitete Version:

template <class T>
Node<T>::Node(value_type info): m_value(info), m_next(NULL) {}

template <class T>
typename List<T>::iterator insert(value_type info)
{
  if (m_head == NULL)
  {
    m_head = new node_type(info);
    m_tail = m_head;
    return iterator(m_tail);
  }
  else
  {
    m_tail.setNext(new node_type(info));
    node_pointer temp = m_tail;
    m_tail = temp.getNext();
    return iterator(temp);
  }
}

Beachten Sie, wie die einfache Tatsache der Verwendung eines ordnungsgemäßen Konstruktors unsere Ausnahmesicherheit verbessert: wenn jemals etwas während des Konstruktors geworfen wird, new muss keinen Speicher zuweisen, daher ist nichts ausgelaufen und wir haben noch keine Operation durchgeführt. Unser List<T>::insert Methode ist jetzt belastbar.

Letzte Frage:

Üblich insert Methoden der einzelnen verknüpften Listen fügen am Anfang ein, weil es einfacher ist:

template <class T>
typename List<T>::iterator insert(value_type info)
{
  m_head = new node_type(info, m_head); // if this throws, m_head is left unmodified
  return iterator(m_head);
}

Sind Sie sicher, dass Sie am Ende eine Einfügung vornehmen wollen, oder haben Sie es so gemacht, weil die push_back Methode für traditionelle Vektoren und Listen ?

Answer 2

Vielleicht sollten Sie versuchen

Node<T>* temp = new Node<T>;

Um Hinweise zur Gestaltung der Liste zu erhalten, können Sie sich natürlich auch std::list ansehen, auch wenn es manchmal etwas entmutigend sein kann.

Answer 3

Sie benötigen:

Node<T> *temp = new Node<T>;

Könnte einen Versuch wert sein typedef NodeType = Node<T> dans le CustomLinkedList Klasse, um zu verhindern, dass dieses Problem erneut auftaucht.

Answer 4

Diese Zeile sollte lauten

Node<T>* temp = new Node<T>;

Dasselbe gilt für die next Zeiger in der Klasse Node.

Answer 5

Wie gesagt, die Lösung lautet

Node<T>* temp = new Node<T>;

... denn Node selbst ist kein Typ, Node<T> ist.