Советы по реализации функции put () в шаблонной очереди c ++?

Question

Я пытаюсь создать очередь, в которой мне не разрешено изменять определение файла заголовка, которое выглядит следующим образом:

class PQueue
{
  private:

    struct Node
    {
      EType Item;
      unsigned Priority;
      unsigned Identifier;
      Node * Pred;
      Node * Succ;
    };

    Node * Head;    // Pointer to head of chain (front)
    Node * Tail;    // Pointer to tail of chain (back)

  public:

    // Initialize pqueue to empty
    //
    PQueue();

    // De-initialize pqueue
    //
    ~PQueue();

    // Re-initialize pqueue to empty
    //
    void reset();

    // Initialize pqueue using existing pqueue
    //
    PQueue( const PQueue<EType>& );

    // Assign into pqueue from other pqueue
    //
    PQueue<EType>& operator=( const PQueue<EType>& );

    // Display attributes and contents of pqueue
    // (from front to back, or back to front)
    //
    void display( ostream&, Direction ) const;

    // Return number of items in pqueue
    //
    unsigned length() const;

    // Return copy of item at front of pqueue (unless pqueue is empty)
    //
    bool front( EType& ) const;

    // Return copy of item at back of pqueue (unless pqueue is empty)
    //
    bool back( EType& ) const;

    // Insert one item (with specified priority) into pqueue (if possible)
    //
    bool put( const EType&, unsigned );

    // Remove item with highest priority from pqueue (unless pqueue is empty)
    //
    bool get( EType& );

    // Discard item with specified identifier from pqueue (if possible)
    //
    bool discard( unsigned );
};

Пока у меня есть эти конструкторы и деструкторы:

template <typename EType> PQueue::PQueue() {
    Head->Pred = NULL;
    Tail->Succ = NULL;
    Tail->Pred=Head;
    Head->Succ=Tail;
} 

template <typename EType> PQueue::~PQueue() {
    reset();
    delete Head;
    Head = NULL;
    delete Tail;
    Tail = NULL;
}

Теперь я застрял на put(), понятия не имею, с чего начать, любая помощь?

Answer 1

Прежде чем перейти к put(), вам нужно правильно настроить существующий конструктор и деструктор!

Если вы собираетесь установить ->Pred или ->Succ узла, тогда узел должен сначала существовать . Голова и хвост - это указатели на узел ... не экземпляры узла, поэтому нет узлов, с которыми можно работать:

Вопросы были бы другими, если бы Голова и Хвост сами были Узлами, но тогда они были бы объявлены как:

Node Head;    // head node of chain (front)
Node Tail;    // tail node of chain (back)

... вместо:

Node * Head;    // Pointer to head of chain (front)
Node * Tail;    // Pointer to tail of chain (back)

Это технически возможно сделать, но не ясно, почему реализация очереди с пустыми и неинициализированными вообще требовала бы существования каких-либо узлов. Если вы создавали необычный класс очереди, в котором всегда было как минимум два элемента (по какой-то причине), вы могли бы рассмотреть такие странности. Но ваше задание явно не требует этого.

Правило, за которое вы хотите стрелять, состоит в том, что пустая очередь (например, только что построенная) имеет ноль Node с. Просто установите указатели Head и Tail на NULL, и все готово:

template <typename EType> PQueue::PQueue() {
    Head = NULL;
    Tail = NULL;
} 

Между прочим, существует специальный синтаксис для инициализации членов ... и, хотя в данном случае не имеет значения, инициализируете ли вы с помощью операторов присваивания в коде, в некоторых случаях, таких как инициализация базового класса, вам необходимо сделать это так:

template <typename EType> PQueue::PQueue() :
    Head (NULL),
    Tail (NULL)
{
} 

Таким образом, если правило (или "инвариант" ) состоит в том, что пустые очереди имеют нулевые головы и хвосты, то вызов reset() должен привести вас в состояние, в котором голова и хвост имеют значение NULL. Но если голова и хвост НЕДЕЙСТВИТЕЛЬНЫ, то почему вы удаляете их в деструкторе? Это технически безопасно:

Безопасно ли удалять нулевой указатель?

Но не будет иметь никакого эффекта. Вызов reset () должен быть достаточным для реализации работы деструктора по освобождению всех выделенных узлов любых непустых очередей ... и reset () должен быть достаточно умным, чтобы ничего не делать, если очередь пуста:

template <typename EType> PQueue::~PQueue() {
    reset();
}

Что касается моего совета по переходу на put() ... ну ... похоже, вам нужно немного попотеть в книгах и понять фундаментальные проблемы языка и структур данных. Работайте через простые связанные списки ... без шаблонов ... и просто получите один рабочий:

http://en.wikipedia.org/wiki/Linked_list

Answer 2

Вы должны выделить узел и подключить его к списку.

Как это:

   template <typename EType>
   bool PQueue::put( const EType& et, unsigned pri ) {
      Node *p = new Node ();
      p->Item = et;
      p->priority = pri;
// now hook it into the list
   p->pred = NULL;
   head = p;
   }

Однако этого недостаточно, потому что вы не правильно инициализируете голову и хвост в конструкторе; до такой степени, что я не могу сказать, создаете ли вы односвязный список или двусвязный список. В вашем текущем коде ваш код действует так, как будто голова и хвост указывают на фактические узлы, но я не вижу, где эти узлы (или создаются).

Кроме того, часть вашего кода спроектирована на EType, в то время как другие части - нет. Вы должны быть последовательными.