Posted By

DrPepper on 10/05/11


Tagged


Versions (?)

[cisp 430]queue


 / Published in: C++
 

  1. // FILE: pqueue1.h
  2. /*
  3. You will implement and test a PriorityQueue class,
  4. where the items of the priority queue are stored on a linked list.
  5. The material from Ch1 ~ 8 of the textbook can help you tremendously.
  6. You can get a lot of good information about implementing this assignment from chapter 8.
  7. There are couple notes about this assignment.
  8.  
  9. 1. Using structure Node with a pointer point to Node structure to create a linked list,
  10. the definition of the Note structure is in the priority queue header file (pqueue1.h).
  11. 2. Using a typedef statement to define the underlying data type, we can easily change to
  12. a new data type on all the typedef data type by change one statement.
  13. 3. Abandoning the usage of linked list toolkit, all the needed function will be implemented in the class.
  14.  
  15. I want to mention it again you that you are welcome to use more advance skills than the techniques introduce
  16. in the textbook to do the assignment. But the implemented class needs to pass the examining file to get credit.
  17. Following is an introduction to some files in this program.
  18.  
  19. pqueue1.h is the headers file for this first version of the PriorityQueue class.
  20. You can start from this version and add your name and other documentation information at the top.
  21. Please look into and understand the structure Note.
  22. Without understanding this, you will have tough time to finish this project.
  23. Reading through this file carefully you need to know what functions you need to
  24. implement and the preconditions and postcondition of each function.
  25. This file should be a good guide to your implementation of the class.
  26. By the way if a member function of a class is an inline function,
  27. it is implemented in this file. You don’t need to redo it in the implementation
  28. file which is pqueue1.cpp.
  29.  
  30. pqueue1.cpp is the implementation file for the PriorityQueue class.
  31. You need to create this file and implement all the function defined in the pqueue1.cpp.
  32. I want to bring to you attention that the PriorityQueue's linked list consists of allocating memory.
  33. So we have to define a copy constructor, an assignment operator, and also a destructor to cope
  34. with the demand of dynamic memories allocation.
  35.  
  36. pqtest.cpp is the same style interactive test program that you used in the previous assignments.
  37. You can open it with your editor or import it to a compiler project to run with the pqueue1.cpp and pqueue1.h.\
  38.  
  39. pqexam1.cpp is the same style non-interactive examine program as you use in the previous assignment.
  40. You can add this file to a compiler to run with the pqueue1.cpp and pqueue1.h to grade your pqueue1.cpp implementation.
  41. CISP430V4A4Exam.exe is an executable file which you can generate this file by
  42. compiling and running the pqexam1.cpp, pqueue1.cpp (proper implemented) and pqueue1.h.
  43.  */
  44.  
  45.  
  46.  
  47. // CLASS PROVIDED: PriorityQueue (a priority queue of items)
  48. //
  49. // TYPEDEF for the PriorityQueue class:
  50. // typedef _____ Item
  51. // The type Item is the data type of the items in the Priority Queue.
  52. // It may be any of the C++ built-in types (int, char, etc.), or a class
  53. // with a default constructor, a copy constructor, and assignment operator.
  54. //
  55. // CONSTRUCTOR for the PriorityQueue class:
  56. // PriorityQueue( )
  57. // Postcondition: The PriorityQueue has been initialized with no Items.
  58. //
  59. // MODIFICATION MEMBER FUNCTIONS for the PriorityQueue class:
  60. // void insert(const Item& entry, unsigned int priority)
  61. // Postcondition: A new copy of entry has been inserted with the specified
  62. // priority.
  63. //
  64. // Item get_front( )
  65. // Precondition: size( ) > 0.
  66. // Postcondition: The highest priority item has been returned and has been
  67. // removed from the PriorityQueue. (If several items have equal priority,
  68. // then the one that entered first will come out first.)
  69. //
  70. // CONSTANT MEMBER FUNCTIONS for the PriorityQueue class:
  71. // size_t size( ) const
  72. // Postcondition: Return value is the total number of items in the
  73. // PriorityQueue.
  74. //
  75. // bool is_empty( ) const
  76. // Postcondition: Return value is true if the PriorityQueue is empty.
  77. //
  78. // VALUE SEMANTICS for the PriorityQueue class:
  79. // Assignments and the copy constructor may be used with
  80. // PriorityQueue objects
  81.  
  82. #ifndef PQUEUE_H
  83. #define PQUEUE_H
  84. #include <stdlib.h> // Provides size_t
  85.  
  86. struct Node; // This will be completely defined below.
  87.  
  88. class PriorityQueue
  89. {
  90. public:
  91. typedef int Item;
  92. PriorityQueue( );
  93. PriorityQueue(const PriorityQueue& source);
  94. ~PriorityQueue( );
  95. void operator =(const PriorityQueue& source);
  96. size_t size( ) const { return many_nodes; }
  97. void insert(const Item& entry, unsigned int priority);
  98. Item get_front( );
  99. bool is_empty( ) const { return many_nodes == 0; }
  100. private:
  101. // Note: head_ptr is the head pointer for a linked list that
  102. // contains the items along with their priorities. These nodes are
  103. // kept in order from highest priority (at the head of the list)
  104. // to lowest priority (at the tail of the list). The private member
  105. // variable, many_nodes, indicates how many nodes are on the list.
  106. // The data type Node is completely defined below.
  107. Node* head_ptr; // head pointer for a linked list
  108. size_t many_nodes; // how many nodes are on teh list.
  109. };
  110. // the node has
  111. // priorityQueue
  112. // unsigned int
  113. // Node (which is array stuff)
  114. struct Node
  115. { // Node for a linked list
  116. PriorityQueue::Item data;
  117. unsigned int priority;
  118. Node *link;
  119. };
  120.  
  121. #endif

Report this snippet  

You need to login to post a comment.