关于在c ++模板化队列中实现put（）函数的建议？ [英] Advice on implementing put() function in a c++ templated queue?

问题描述

我试图实现一个队列，其中我不允许更改头文件定义，它看起来像这样：

  class PQueue 
 {
 private：
 
 struct Node 
 {
 EType Item; 
 unsigned优先级; 
 unsigned标识符; 
 Node * Pred; 
节点* Succ; 
}; 
 
 Node * Head; //指向链头（前面）
 Node * Tail; //指向链的尾部（后）
 
 public：
 
 //初始化pqueue为空
 // 
 PQueue（）; 
 
 //初始化pqueue 
 // 
〜PQueue（）; 
 
 //重新初始化pqueue为空
 // 
 void reset（）; 
 
 //使用现有pqueue初始化pqueue 
 // 
 PQueue（const PQueue< EType>& 
 
 //从其他pqueue分配到pqueue中
 // 
 PQueue< EType>& operator =（const PQueue< EType>&）; 
 
 //显示pqueue的属性和内容
 //（从前到后或从前到后）
 // 
 void display（ostream& Direction ）const; 
 
 //返回pqueue中的项目数量
 // 
无符号长度（）const; 
 
 //返回pqueue前面的项目副本（除非pqueue为空）
 // 
 bool front（EType&）const; 
 
 //返回pqueue后面的项目副本（除非pqueue为空）
 // 
 bool back（EType&）const; 
 
 //将一个项目（具有指定优先级）插入pqueue（如果可能）
 // 
 bool put（const EType& unsigned）; 
 
 //从pqueue中删除具有最高优先级的项（除非pqueue为空）
 // 
 bool get（EType&）; 
 
 //从pqueue中丢弃带有指定标识符的项目（如果可能）
 // 
 bool discard（unsigned）; 
}; 
  

到目前为止，我有这些构造函数和析构函数：

 模板< typename EType> PQueue :: PQueue（）{
 Head-> Pred = NULL; 
 Tail-> Succ = NULL; 
 Tail-> Pred = Head; 
 Head-> Succ = Tail; 
} 
 
模板< typename EType> PQueue ::〜PQueue（）{
 reset（）; 
 delete头; 
 Head = NULL; 
 delete Tail; 
 Tail = NULL; 
} 
  

现在我被困在 put / code>，我不知道从哪里开始，任何帮助？

解决方案

c $ c> put（）你需要得到你现有的构造函数和析构函数。

如果你要设置<$如果一个节点必须首先存在一个节点的 c $ c> - > Pred 或 - > Succ 。 Head和Tail是 的指针，所以没有节点可以操作：

<如果Head和Tail本身是Nodes，那么它们会有所不同，但是它们将被声明为：

  //链的头节点（前面）
节点尾; //链的尾节点（后面）
  

...而不是：

 节点*头; //指向链头（前面）
 Node * Tail; //指向尾链的指针（回）
  

这在技术上可行，但不清楚为什么一个空和未初始化队列实现将需要任何节点存在。如果你创建一个不寻常的队列类，总是有至少两个元素（由于某种原因），那么你可能会考虑这样的怪异。

你想要拍摄的规则是一个空队列（例如刚刚构建的队列）具有零 节点。只需将Head和Tail指针本身设置为NULL即可。

  template< typename EType> PQueue :: PQueue（）{
 Head = NULL; 
 Tail = NULL; 
} 
  

有一个特殊的语法用于初始化成员，在这种情况下并不重要，无论是否在代码中使用赋值语句进行初始化，有一些情况下，基类初始化，你必须这样做：

  template< typename EType> PQueue :: PQueue（）：
 Head（NULL），
 Tail（NULL）
 {
} 
  

因此，如果规则（或invariant）是空队列具有空头和尾部，然后调用 reset（）应该使你处于head和tail为NULL的状态。但是如果头部和尾部为NULL，那么为什么要在析构函数中删除它们呢？它在技术上是安全的：

是否可以安全地删除NULL指针？

但是没有效果。 reset（）调用应该足以实现析构函数的工作以释放任何非空队列的所有已分配节点...并且reset（）应足够聪明，以便在队列为空时不执行任何操作：

 模板< typename EType> PQueue ::〜PQueue（）{
 reset（）;至于我的建议，继续到 put（）。<$ c $ b> 
  


$ b < ...好吧，看起来你需要打一点书，了解语言和数据结构的基本问题。通过简单的链接列表...无需模板...只需获得一个工作：

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

I'm trying to implement a queue where I'm not allowed to change the header file definition, which looks like this:

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 );
};

So far I have these constructors and destructors:

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;
}

Now I am stuck on the put(), I have no idea where to start, any help?

解决方案

Before you move on to put() you need to get your existing constructor and destructor right!

If you are going to be setting the ->Pred or ->Succ of a Node then a node has to first exist. Head and Tail are pointers to Node...not instances of Node, so there's no nodes to operate on:

Matters would be different if Head and Tail were themselves Nodes, but then they would be declared like:

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

...instead of:

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

That's technically possible to do, but it's not clear why an empty-and-uninitialized queue implementation would require any nodes to exist at all. If you were creating an unusual queue class which always had at least two elements (for some reason) then you might consider such oddities. But your assignment clearly isn't asking for that.

The rule you want to shoot for is that an empty queue (such as one that has just been constructed) has zero Nodes. Just set the Head and Tail pointers themselves to NULL and you're done:

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

There's a special syntax for initializing members, by the way...and while it doesn't really matter in this case whether you initialize using assignment statements in the code, there are some cases like base class initialization where you have to do it this way:

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

So if the rule (or the "invariant") is that empty queues have null heads and tails, then calling reset() should put you in a state where the head and tail are NULL. Yet if the head and tail are NULL, then why are you deleting them in the destructor? It's technically safe:

Is it safe to delete a NULL pointer?

But would have no effect. A reset() call should be sufficient to implement the work of the destructor to release all the allocated nodes of any non-empty queues...and reset() should be smart enough to do nothing if a queue is empty:

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

As for my advice on proceeding to put()... well... it looks like you need to hit the books a bit and understand foundational issues of the language and data structures. Work through simple linked lists...without templates...and just get one working:

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

这篇关于关于在c ++模板化队列中实现put（）函数的建议？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！