返回顶部

收藏

[cisp 430]优先队列

更多
// FILE: pqueue1.h
/*
You will implement and test a PriorityQueue class, 
where the items of the priority queue are stored on a linked list.  
The material from Ch1 ~ 8 of the textbook can help you tremendously. 
You can get a lot of good information about implementing this assignment from chapter 8. 
There are couple notes about this assignment.  

    1.  Using structure Node with a pointer point to Node structure to create a linked list,
        the definition of the Note structure is in the priority queue header file (pqueue1.h).
    2.  Using a typedef statement to define the underlying data type, we can easily change to
        a new data type on all the typedef data type by change one statement.  
    3.  Abandoning the usage of linked list toolkit, all the needed function will be implemented in the class.

I want to mention it again you that you are welcome to use more advance skills than the techniques introduce
in the textbook to do the assignment.  But the implemented class needs to pass the examining file to get credit.
Following is an introduction to some files in this program.

pqueue1.h is the headers file for this first version of the PriorityQueue class. 
    You can start from this version and add your name and other documentation information at the top.  
    Please look into and understand the structure Note.  
    Without understanding this, you will have tough time to finish this project.  
    Reading through this file carefully you need to know what functions you need to 
    implement and the preconditions and postcondition of each function. 
    This file should be a good guide to your implementation of the class.  
    By the way if a member function of a class is an inline function, 
    it is implemented in this file.  You don’t need to redo it in the implementation 
    file which is pqueue1.cpp.

pqueue1.cpp is the implementation file for the PriorityQueue class. 
    You need to create this file and implement all the function defined in the pqueue1.cpp.  
    I want to bring to you attention that the PriorityQueue's linked list consists of allocating memory.  
    So we have to define a copy constructor, an assignment operator, and also a destructor to cope 
    with the demand of dynamic memories allocation.

pqtest.cpp is the same style interactive test program that you used in the previous assignments.  
    You can open it with your editor or import it to a compiler project to run with the pqueue1.cpp and pqueue1.h.\

pqexam1.cpp is the same style non-interactive examine program as you use in the previous assignment.  
    You can add this file to a compiler to run with the pqueue1.cpp and pqueue1.h to grade your pqueue1.cpp implementation.
    CISP430V4A4Exam.exe is an executable file which you can generate this file by
    compiling and running the pqexam1.cpp, pqueue1.cpp (proper implemented) and pqueue1.h.
 */

// CLASS PROVIDED: PriorityQueue (a priority queue of items)
//
// TYPEDEF for the PriorityQueue class:
//   typedef _____ Item 
//     The type Item is the data type of the items in the Priority Queue.
//     It may be any of the C++ built-in types (int, char, etc.), or a class 
//     with a default constructor, a copy constructor, and assignment operator.
//
// CONSTRUCTOR for the PriorityQueue class:
//   PriorityQueue( )
//     Postcondition: The PriorityQueue has been initialized with no Items.
//
// MODIFICATION MEMBER FUNCTIONS for the PriorityQueue class:
//   void insert(const Item& entry, unsigned int priority)
//     Postcondition: A new copy of entry has been inserted with the specified
//     priority.
//
//   Item get_front( )
//     Precondition: size( ) > 0.
//     Postcondition: The highest priority item has been returned and has been
//     removed from the PriorityQueue. (If several items have equal priority,
//     then the one that entered first will come out first.)
//
// CONSTANT MEMBER FUNCTIONS for the PriorityQueue class:
//   size_t size( ) const
//     Postcondition: Return value is the total number of items in the
//     PriorityQueue.
//
//   bool is_empty( ) const
//     Postcondition: Return value is true if the PriorityQueue is empty.
//
// VALUE SEMANTICS for the PriorityQueue class:
//   Assignments and the copy constructor may be used with
//   PriorityQueue objects

#ifndef PQUEUE_H
#define PQUEUE_H
#include <stdlib.h> // Provides size_t

    struct Node; // This will be completely defined below.

    class PriorityQueue
    {
    public:
        typedef int Item;
        PriorityQueue( );
        PriorityQueue(const PriorityQueue& source);
        ~PriorityQueue( );
        void operator =(const PriorityQueue& source);
        size_t size( ) const { return many_nodes; }
        void insert(const Item& entry, unsigned int priority);
        Item get_front( );
        bool is_empty( ) const { return many_nodes == 0; }
    private:
        // Note: head_ptr is the head pointer for a linked list that
        // contains the items along with their priorities. These nodes are
        // kept in order from highest priority (at the head of the list)
        // to lowest priority (at the tail of the list). The private member
        // variable, many_nodes, indicates how many nodes are on the list.
        // The data type Node is completely defined below.
        Node* head_ptr; // head pointer for a linked list 
    size_t many_nodes;  // how many nodes are on teh list.
    };
        // the node has 
        // priorityQueue
        // unsigned int 
        // Node (which is array stuff)
    struct Node
    {   // Node for a linked list
        PriorityQueue::Item data;   
        unsigned int priority;
        Node *link;     
    };

#endif

标签:队列

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. lorem 发表 2018-10-21 11:28:28 猫狗队列的再解
  2. lorem 发表 2018-10-21 11:28:28 猫狗队列的再解
  3. 博主 发表 2018-07-11 12:45:00 环形队列
  4. phpvar 发表 2012-07-22 03:45:04 jquery animate动画函数和动画队列
  5. xinlu 发表 2017-12-23 15:20:50 线程安全队列
  6. 博主 发表 2017-10-22 06:23:40 Kafka实战一
  7. 博主 发表 2017-07-14 23:41:00 一个Redis消息队列实现
  8. 博主 发表 2017-07-14 23:41:00 一个Redis消息队列实现
  9. TiuVe2 发表 2017-06-23 16:01:08 优先队列实现原理分析
  10. TiuVe2 发表 2017-06-08 01:24:24 并行化资源池队列 3 —— 紧密相关的同步化队列
  11. TiuVe2 发表 2017-06-06 17:10:27 并行化资源池队列 2 —— 无锁化的无界队列
  12. TiuVe2 发表 2017-06-06 02:46:29 并行化资源池队列 1 —— 部分有界队列

发表评论