(Eliot) # 7 page 309 Cap 4. Modify the LinkedQueue structure Linked QueueCircular. A circular queue must contain two head pointers at the beginning of the list and a tail indicating the end of the list.
The Josephus problem is named after the historian Flavius Josephus, who lived between the years 37 and 100 CE. Josephus was a reluctant leader of the Jewish revolt against the Roman Empire. When it appeared that Josephus and his band were to be captured, they resolved to kill themselves. Josephus persuaded the group by saying, "Let us commit our mutual deaths to determination by lot. He to whom the first lot falls, let him be killed by him that hath the second lot, and thus fortune shall make its progress through us all; nor shall any of us perish by his own right hand, for it would be unfair if, when the rest are gone, somebody should repent and save himself (Flavius Josephus, The Wars of the Jews, Book III, Chapter 8, Verse 7, tr. William Whiston, 1737). Yet that is exactly what happened, Josephus was left for last, and he and the person he was to kill surrendered to the Romans. Although Josephus does not describe how the lots were assigned, the following approach is generally believed to be the way it was done. People form a circle and count around the circle some predetermined number. When this number is reached that person receives a lot and leaves the circle. The count starts over with the next person. Using the circular linked list developed in Exercise 6, simulate this problem. Your program should take two parameters:n, the number of people that start, and m, the number of counts. For example, try n = 20 and m = 12. Where does Josephus need to be in the original list so that he is the last one chosen?
(Carrano) Question # 8 Implement the main program for each tree. P. 438 Chap. fifteen.
Question 8 What are the preorder, inorder, and postorder traversals of the binary trees in parts a , b , and c of Figure 15-5 ?
Figure 15-5 Binary trees with the same nodes but different heights: see image.
(Gaddis) Implement Binary Search Trees using StudentTestScores (Version 3) p. 812 Cap 14. Its implementation must contain a menu of options with: Add a student, remove a student, find a student and modify a student's information. Use the code of (Carrano) Cap. 16 Sec. 6.4 p. 482
Gaddis
Contents of StudentTestScores (Version 3)
1 #ifndef STUDENTTESTSCORES_H
2 #define STUDENTTESTSCORES_H
3 #include < string>
4 using namespace std;
5
6 const double DEFAULT_SCORE = 0.0;
7
8 class StudentTestScores
9 {
10 private:
11 string studentName; // The student's name
12 double *testScores; // Points to array of test scores
13 int numTestScores; // Number of test scores
14
15 // Private member function to create an
16 // array of test scores.
17 void createTestScoresArray(int size)
18 { numTestScores = size;
19 testScores = new double[size];
20 for (int i = 0; i < size; i++)
21 testScores[i] = DEFAULT_SCORE; }
22
23 public:
24 // Constructor
25 StudentTestScores(string name, int numScores)
26 { studentName = name;
27 createTestScoresArray(numScores); }
28
29 // Copy constructor
30 StudentTestScores(const StudentTestScores &obj)
31 { studentName = obj.studentName;
32 numTestScores = obj.numTestScores;
33 testScores = new double[numTestScores];
34 for (int i = 0; i < numTestScores; i++)
35 testScores[i] = obj.testScores[i]; }
36
37 // Destructor
38 ~StudentTestScores()
39 { delete [] testScores; }
40
41 // The setTestScore function sets a specific
42 // test score's value.
43 void setTestScore(double score, int index)
44 { testScores[index] = score; }
45
46 // Set the student's name.
47 void setStudentName(string name)
48 { studentName = name; }
49
50 // Get the student's name.
51 string getStudentName() const
52 { return studentName; }
54 // Get the number of test scores.
55 int getNumTestScores()
56 { return numTestScores; }
57
58 // Get a specific test score.
59 double getTestScore(int index) const
60 { return testScores[index]; }
61
62 // Overloaded = operator
63 void operator=(const StudentTestScores &right)
64 { delete [] testScores;
65 studentName = right.studentName;
66 numTestScores = right.numTestScores;
67 testScores = new double[numTestScores];
68 for (int i = 0; i < numTestScores; i++)
69 testScores[i] = right.testScores[i]; }
70 };
71 #endif
54 // Get the number of test scores.
55 int getNumTestScores()
56 { return numTestScores; }
57
58 // Get a specific test score.
59 double getTestScore(int index) const
60 { return testScores[index]; }
61
62 // Overloaded = operator
63 void operator=(const StudentTestScores &right)
64 { delete [] testScores;
65 studentName = right.studentName;
66 numTestScores = right.numTestScores;
67 testScores = new double[numTestScores];
68 for (int i = 0; i < numTestScores; i++)
69 testScores[i] = right.testScores[i]; }
70 };
71 #endif
Main
// This program demonstrates the overloaded = operator
2 #include < iostream>
3 #include "StudentTestScores.h"
4 using namespace std;
5
6 // Function prototype
7 void displayStudent(StudentTestScores);
8
9 int main()
10 {
11 // Create a StudentTestScores object and
12 // assign test scores.
13 StudentTestScores student1("Kelly Thorton", 3);
14 student1.setTestScore(100.0, 0);
15 student1.setTestScore(95.0, 1);
16 student1.setTestScore(80, 2);
17
18 // Create another StudentTestScore object
19 // with default test scores.
20 StudentTestScores student2("Jimmy Griffin", 5);
21
22 // Assign the student1 object to student2
23 student2 = student1;
24
25 // Display both objects. They should
26 // contain the same data.
27 displayStudent(student1);
28 displayStudent(student2);
29 return 0;
30 }
Carrano
LISTING 16-4 A header fi le for the link-based implementation of the class BinarySearchTree
/** Link-based implementation of the ADT binary search tree.
@file BinarySearchTree.h */
#ifndef _BINARY_SEARCH_TREE
#define _BINARY_SEARCH_TREE
#include "BinaryTreeInterface.h"
#include "BinaryNode.h"
#include "BinaryNodeTree.h"
#include "NotFoundException.h"
#include "PrecondViolatedExcep.h"
template < class ItemType>
class BinarySearchTree : public BinaryNodeTree
{
private :
BinaryNode< ItemType>* rootPtr;
protected :
//------------------------------------------------------------
// Protected Utility Methods Section:
// Recursive helper methods for the public methods.
//------------------------------------------------------------
// Recursively finds where the given node should be placed and
// inserts it in a leaf at that point.
BinaryNode< ItemType>* insertInorder(BinaryNode< ItemType>* subTreePtr,
BinaryNode< ItemType>* newNode);
// Removes the given target value from the tree while maintaining a
// binary search tree.
BinaryNode< ItemType>* removeValue(BinaryNode< ItemType>* subTreePtr,
const ItemType target,
bool& success);
// Removes a given node from a tree while maintaining a
// binary search tree.
BinaryNode< ItemType>* removeNode(BinaryNode< ItemType>* nodePtr);
// Removes the leftmost node in the left subtree of the node
// pointed to by nodePtr.
// Sets inorderSuccessor to the value in this node.
// Returns a pointer to the revised subtree.
BinaryNode< ItemType>* removeLeftmostNode(
BinaryNode< ItemType>* subTreePtr, ItemType& inorderSuccessor);
// Returns a pointer to the node containing the given value,
// or nullptr if not found.
BinaryNode< ItemType>* findNode(BinaryNode< ItemType>* treePtr,
const ItemType& target) const ;
public :
//------------------------------------------------------------
// Constructor and Destructor Section.
//------------------------------------------------------------
BinarySearchTree();
BinarySearchTree( const ItemType& rootItem);
BinarySearchTree( const BinarySearchTree< ItemType>& tree);
virtual ~BinarySearchTree();
//------------------------------------------------------------
// Public Methods Section.
//------------------------------------------------------------
bool isEmpty() const ;
int getHeight() const ;
int getNumberOfNodes() const ;
ItemType getRootData() const throw (PrecondViolatedExcep);
void setRootData( const ItemType& newData) const
throw (PrecondViolatedExcep);
bool add( const ItemType& newEntry);
bool remove( const ItemType& anEntry);
void clear();
ItemType getEntry( const ItemType& anEntry) const
throw (NotFoundException);
bool contains( const ItemType& anEntry) const ;
//------------------------------------------------------------
// Public Traversals Section.
//------------------------------------------------------------
void preorderTraverse(void visit(ItemType&)) const ;
void inorderTraverse(void visit(ItemType&)) const ;
void postorderTraverse(void visit(ItemType&)) const ;
//------------------------------------------------------------
// Overloaded Operator Section.
//------------------------------------------------------------
BinarySearchTree< ItemType>&
operator=(const BinarySearchTree< ItemType>& rightHandSide);
}; // end BinarySearchTree
#include "BinarySearchTree.cpp"
#endif