c++in class more

profiletheman04
in_class_assignmetz.zip
Home>Computer Science homework help>c++in class more

In Class Assignmetz/CST280W13a-1.pdf

CST 280 In-Class Practice – Week 13

Manually determine the configuration of the priority queue (stored as a heap) created by the following operations. Trace the following logic and define the output:

enqueue(7); enqueue(17); enqueue(2); enqueue(5); enqueue(22); enqueue(19); enqueue(6); enqueue(11); enqueue(13); write the queue contents

dequeue and write front item enqueue(15); enqueue(8);

dequeue and write front item dequeue and write front item

enqueue(24); enqueue(14); write the queue contents

Part 2

Then, verify the output by implementing the algorithm by rewriting the priority queue demonstration program discussed in class. Files needed: testPQueue.cpp pqType.h heap.cpp

Deliverables • This cover sheet (with your names on it) • Driver source code and output for verification program exectution.

In Class Assignmetz/CST280W13b.pdf

CST 280 In-Class Practice – Week 13 Use this page as a worksheet to sketch the progression of the elements up to the first split for the QuickSort algorithm. Use the middle array element as the split value: 15 34 99 42 11 41 66 23 55 93 48

Next, access the file quickSort.cpp from the course web page. Tailor the program by entering the array values above in place of the integer values used for an in-class demonstration. Be sure to adjust the index range to match the size of this array. Remember that the parameters to the QuickSort algorithm are starting and ending index values, not the size of the array. Next, insert code to demonstrate the state of the array after the first split. This should verify what you did by hand above. Insert the following code at various points within the partition function to “see” the array at various stages of processing: for (int i = start; i <= end; i++) // <== ADD cout << set[i] << ' '; cout << endl;

Insert the code at these positions: int partition(int set[], int start, int end) { int pivotValue, pivotIndex, mid; mid = (start + end) / 2; swap(set[start], set[mid]); pivotIndex = start; pivotValue = set[start]; ç HERE for (int scan = start + 1; scan <= end; scan++) { if (set[scan] < pivotValue) { pivotIndex++; swap(set[pivotIndex], set[scan]); } ç HERE } swap(set[start], set[pivotIndex]); ç HERE return pivotIndex; } Finally, identify the line that matches what you concluded above. Deliverables:

Deliver the following for this assignment:

• This work sheet with a sketch of the array first split • Program source code with required change • Program output demonstrating array configuration after first split

In Class Assignmetz/heap.cpp

In Class Assignmetz/heap.cpp

// This file contains the definition and implementations of struct HeapType.

// A swap function for a generic data type
template   < class   ItemType >
void   Swap   (   ItemType &  item1 ,   ItemType &  item2  )
{
   ItemType  temp  =  item1 ;
  item1  =  item2 ;
  item2  =  temp ;
}

// Assumes ItemType is either a built-in simple type or a class
// with overloaded relational operators.
template < class   ItemType >
struct   HeapType
{
   void   ReheapDown ( int  root ,   int  bottom );
   void   ReheapUp ( int  root ,   int  bottom );
   ItemType *  elements ;   // Array to be allocated dynamically
   int  numElements ;
};

// This function performs the REHEAP DOWN action to restore
// a binary tree to a heap after a removal from the root
// Postcondition: Heap property is restored.
template < class   ItemType >
void   HeapType < ItemType >:: ReheapDown ( int  root ,   int  bottom )
{
   int  maxChild ;
   int  rightChild ;
   int  leftChild ;
  leftChild  =  root  *   2   +   1 ;
  rightChild  =  root  *   2   +   2 ;
   if   ( leftChild  <=  bottom )
   {
     if   ( leftChild  ==  bottom )
      maxChild  =  leftChild ;
     else
     {
       if   ( elements [ leftChild ]   <=  elements [ rightChild ])
        maxChild  =  rightChild ;
       else
        maxChild  =  leftChild ;
     }
     if   ( elements [ root ]   <  elements [ maxChild ])
     {
       Swap ( elements [ root ],  elements [ maxChild ]);
       ReheapDown ( maxChild ,  bottom );
     }
   }
}

// This function performs the REHEAP UP action to restore
// a binary tree to a heap after addition of an item at
// the bottom open position
// Postcondition: Heap property is restored.
template < class   ItemType >
void   HeapType < ItemType >:: ReheapUp ( int  root ,   int  bottom )
{
   int  parent ;
   if   ( bottom  >  root )
   {
    parent  =   ( bottom  -   1 )   /   2 ;
     if   ( elements [ parent ]   <  elements [ bottom ])
     {
       Swap ( elements [ parent ],  elements [ bottom ]);
       ReheapUp ( root ,  parent );
     }
   }
}  

In Class Assignmetz/pqType.h

// Definition of class PQType, which represents the Priority Queue ADT // An array is used to implement the heap for this data type #include "heap.cpp" template<class ItemType> class PQType { public: PQType(int); // Parameterized class constructor // to initialize max size of heap array ~PQType(); // Class destructor void MakeEmpty(); // Function: Initializes the queue to an empty state. // Post: Queue is empty. bool IsEmpty() const; // Function: Determines whether the queue is empty. // Post: Function value = (queue is empty) bool IsFull() const; // Function: Determines whether the queue is full. // Post: Function value = (queue is full) void Enqueue(ItemType newItem); // Function: Adds newItem to the rear of the queue. // Pre: Queue is not full. // Post: newItem is in the queue. ItemType Dequeue(); // Function: Removes element with highest priority from the queue // and returns it in item. // Pre: Queue is not empty. // Post: Highest priority element has been removed from the queue. // item is a copy of the removed element. void ListQueue(); // Write current queue contents back to front private: int numItems; HeapType<ItemType> items; int maxItems; }; // ------------------------------------------------------- // IMPLEMENTATION OF PRIORITY QUEUE CLASS FUNCTIONS // ------------------------------------------------------- template<class ItemType> PQType<ItemType>::PQType(int max) { maxItems = max; items.elements = new ItemType[max]; numItems = 0; } template<class ItemType> void PQType<ItemType>::MakeEmpty() { numItems = 0; } template<class ItemType> PQType<ItemType>::~PQType() { delete [] items.elements; } template<class ItemType> ItemType PQType<ItemType>::Dequeue() // Post: element with highest priority has been removed // from the queue; a copy is returned in item. { ItemType item = items.elements[0]; items.elements[0] = items.elements[numItems-1]; numItems--; items.ReheapDown(0, numItems-1); return item; } template<class ItemType> void PQType<ItemType>::Enqueue(ItemType newItem) // Post: newItem is in the queue. { numItems++; items.elements[numItems-1] = newItem; items.ReheapUp(0, numItems-1); } template<class ItemType> bool PQType<ItemType>::IsFull() const // Post: Function value = true if the queue is full; // false, otherwise { return numItems == maxItems; } template<class ItemType> bool PQType<ItemType>::IsEmpty() const // Post: Function value = true if the queue is empty; // false, otherwise { return numItems == 0; } // Write current queue contents back to front template<class ItemType> void PQType<ItemType>::ListQueue() { for (int i=0; i<numItems; i++) cout << items.elements[i] << ' '; cout << endl; }

In Class Assignmetz/quickSort.cpp

In Class Assignmetz/quickSort.cpp

// This program demonstrates the QuickSort Algorithm
#include   < iostream >
using   namespace  std ;

// Function prototypes
void  quickSort ( int   [],   int ,   int );
int  partition ( int   [],   int ,   int );
void  swap ( int   & ,   int   & );

int  main ()
{
     int   array [ 10 ]   =   { 7 ,   3 ,   9 ,   2 ,   0 ,   1 ,   8 ,   4 ,   6 ,   5 };
     int  x ;   // Counter

     for   ( x  =   0 ;  x  <   10 ;  x ++ )
       cout  <<   array [ x ]   <<   " " ;
    cout  <<  endl ;

    quickSort ( array ,   0 ,   9 );

     for   ( x  =   0 ;  x  <   10 ;  x ++ )
       cout  <<   array [ x ]   <<   " " ;
    cout  <<  endl ;

     return   0 ;
}

//************************************************
// quickSort uses the quicksort algorithm to     *
// sort set, from set[start] through set[end].   *
//************************************************
void  quickSort ( int  set [],   int  start ,   int  end )
{
     int  pivotPoint ;

     if   ( start  <  end )
     {
         // Get the pivot point
        pivotPoint  =  partition ( set ,  start ,  end );
        
         // Sort the first sub list
        quickSort ( set ,  start ,  pivotPoint  -   1 );
        
         // Sort the second sub list
        quickSort ( set ,  pivotPoint  +   1 ,  end );
     }
}

//**********************************************************
// partition selects the value in the middle of the        *
// array set as the pivot. The list is rearranged so       *
// all the values less than the pivot are on its left      *
// and all the values greater than pivot are on its right. *
//**********************************************************
int  partition ( int  set [],   int  start ,   int  end )
{
     int  pivotValue ,  pivotIndex ,  mid ;

    mid  =   ( start  +  end )   /   2 ;
    swap ( set [ start ],  set [ mid ]);
    pivotIndex  =  start ;
    pivotValue  =  set [ start ];
 
     for   ( int  scan  =  start  +   1 ;  scan  <=  end ;  scan ++ )
     {
         if   ( set [ scan ]   <  pivotValue )
         {
            pivotIndex ++ ;
            swap ( set [ pivotIndex ],  set [ scan ]);
         }
     }
    swap ( set [ start ],  set [ pivotIndex ]);

     return  pivotIndex ;
}

//**********************************************
// swap simply exchanges the contents of       *
// value1 and value2.                          *
//**********************************************
void  swap ( int   & value1 ,   int   & value2 )
{
     int  temp  =  value1 ;

    value1  =  value2 ;
    value2  =  temp ;
}  

In Class Assignmetz/testPQueue.cpp

In Class Assignmetz/testPQueue.cpp

// This program drives a testing plan for a priority queue data type.  It simulates
// inserting and deleting integers from the priority queue.

#include   < iostream >
using   namespace  std ;

#include   "pqType.h"

int  main ()
{
PQType < int >  theQueue ( 50 );
int  anItem ;

theQueue . Enqueue ( 15 );
theQueue . Enqueue ( 24 );
theQueue . Enqueue ( 65 );
theQueue . Enqueue ( 10 );
theQueue . Enqueue ( 88 );
theQueue . ListQueue ();

theQueue . Enqueue ( 11 );
theQueue . Enqueue ( 25 );
theQueue . Enqueue ( 55 );
theQueue . Enqueue ( 77 );
theQueue . ListQueue ();

anItem  =  theQueue . Dequeue ();
cout  <<  anItem  <<   " out"   <<  endl ;
theQueue . ListQueue ();

anItem  =  theQueue . Dequeue ();
cout  <<  anItem  <<   " out"    <<  endl ;
theQueue . ListQueue ();

anItem  =  theQueue . Dequeue ();
cout  <<  anItem  <<   " out"    <<  endl ;
theQueue . ListQueue ();

return   0 ;
}