cs161@sdcsvax.UUCP (Grader for 161) (12/10/85)
Earlier I posted a article asking for help with C++. Thanks for all the replies. I am sorry about some of the bugs I introduced when copying the sample program. I am posting my solution to the problem which keeps internal details hidden (binomial queues could be used without the user knowing it!). I can do this now that the assignment is finished and students can't copy it from the net. Class object is used since this was for an assignment. It contains virtual functions for keys, ranks, etc. It could have just as easily used ``void *'', which is easier to use, but gets rid of useful typechecking. Of course, a subclass can also be written solving this, but... Thanks to all and to all a good night. Darin Johnson sdcsvax!beowulf!wbreader -------------------------------------------------------------------------- /*---------------------------------------------------------------------- * PRQ.H:This is the header file that the user of the abstract * data type, priority queues, has access to, when he is writing his * program. A user may refer to the manual page for detailed information. *----------------------------------------------------------------------*/ extern class object; /* to be defined by user */ extern class p_node; /* defined only be implementation */ class Pqueue { p_node *head; public: Pqueue(); void insert(object*, double); object *fetch(); }; -------------------------------------------------------------------- /*--------------------------------------------------------------------- * PRQ.C:Contains the library files for the abstract data type, priority * queues.This is the implementor module. *---------------------------------------------------------------------*/ #include <stdio.h> #include "prq.h" /** definition of p_node declared in prq.h **/ struct p_node { double rank; struct p_node *left; struct p_node *right; object* data; p_node(object *, double); }; /* structure for external node */ /* is there an elegant way to do this making sentinel a pointer? */ static p_node sentinel = { -1e+100, (&sentinel), (&sentinel), NULL }; p_node.p_node() {...} /*The constructor "Pqueue()" initializes the queue to be empty * and the head to point to it. */ Pqueue.Pqueue() { head = (& sentinel); } /* The function "swap()" takes as parameters two nodes representing * subtrees, and swaps them (what they are pointing to). * Could be made as a macro or inline function! */ void swap (p_node **p1, p_node **p2) { p_node *temp; temp = *p1; *p1 = *p2; *p2 = temp; } /* The function "merge()" takes as parameters two nodes representing * subtrees and merges them, returning a single tree where heap ordering * of the tree is still preserved. */ p_node *merge (p_node *p1, p_node *p2, double sign) { /*swap if heap is not preserved*/ if ( p1 -> rank < p2 -> rank) swap (&p1, &p2); if (p2 != &sentinel) { p1 -> right = merge (p1 -> right, p2, sign); swap (&p1 -> left, &p1 -> right); } return (p1); } /* The function "Pqueue.insert()" takes as an object associated with the * key to be inserted, and it's rank. * It inserts the key into the queue (self adjusting heap) preserving the * heap condition. */ void Pqueue.insert (object *prq_o, double rank) { p_node *temp; temp = new p_node(prq_o, rank); head = merge (head, temp, sign); } object* Pqueue.fetch () { object* data; p_node *temp; data = head -> data; if (head == (& sentinel)) return (data); temp = head; head = merge (temp -> left, temp -> right, sign); delete temp; return (data); }