Hey I'm trying to create a singly linked circular list. I've made a template class for the node and list itself. My problem is that i don't know what to do with it . I'll post my project requirements and then I'll post what i've done. I have no idea what to do in my main.cpp. Also i don't even know if my other stuff is right.
Project
slnode.hPart I:
For this portion of the project do the following:
* Create a directory called project6_yourlogin.
* Create header files called slnode.h and sclist.h. These headers will declare the template classes for a singly linked node, SLNode, and a singly linked circular list, SLCList.
* Each header will include at the bottom the implementation file (.template) that implements the class.
The SLNode class is simple and satisfies the following requirements:
o Makes the SCList class a friend of the Node class so SCList can have direct access to its private data members. You do this with the following code in slnode.h:
// Makes the SLCList class a friend of SLNode
template <class> friend class SCList;
o Defines a constructor that takes as an argument a const reference to the Type stored in the data portion of the node.
o Has private data members "data" and "nextPtr".
The List class must satisfy the following requirements:
o Maintain headPtr as a private data member.
o Support at least the following functions:
+ Constructor/Destructor
+ InsertAtHead()
+ InsertAtTail()
+ RemoveFromHead(): returns a pointer to the node removed from the head of the list.
+ RemoveFromTail(): returns a pointer to the node removed from the tail of the list.
+ IsEmpty(): true if the list is empty, otherwise false.
+ Advance(): moves headPtr one node forward in the list.
+ Locate(Type data): returns a pointer to the first node in the list, starting from the head of the list, that contains the indicated data. If the data is not in the list, returns NULL.
* Make certain your code maintains a consistent circular linked list. Draw pictures so you know what the circular linked list will look like in different situations (e.g., when there are five nodes, two nodes, a single node, and no nodes). You should also read through the problem description below to make sure you're creating all the operations you need.
Part II: The Josephus Problem
Note: this same description can be found in many locations on the Internet. I do not attest to its accuracy. It's an interesting story, though.
Josephus Flavius was a famous Jewish historian of the first century at the time of the Second Temple destruction. During the Jewish-Roman war he got trapped in a cave with a group of 40 soldiers surrounded by romans. Legend has it that --- preferring suicide to capture --- the Jews decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left. Josephus, not keen to die, quickly found the safe spot in the circle and thus stayed alive.
In this part of the lab you will write a program to simulate a generalization of the Josephus problem. The program will utilize (you guessed it!) a single circular linked list. It will take input from a file called "josephus.in", which has the following format:
* Line 1: "skip" number, S
* The next N lines: The last names of the N participants (the name will be a single word)
* The last line: the word "END" (without quotes).
Your program will read the input file, creating a circular linked list of the names. The first name (on line 2) will remain at the head of the list. Starting with this node as number 1, count the nodes up to S. When you get to S, print the name on a line and remove this node from the list. The node following this node will then become the head of the list. When you have only one node left in the list, print "Survivor: ", followed by the name of the survivor and a newline.
You can test your program with the following input file:
6
Gauss
Dirichlet
Euler
Newton
Pythagoras
Riemann
Euclid
Fourier
The output for this file should be:
Riemann
Newton
Euler
Pythagoras
Fourier
Euclid
Dirichlet
Survivor: Gauss
sclist.hCode:#include <iostream> template <class T> class slnode.h { //makes slnodes private data available to sclist template <class> friend class sclist; public: //default constructor slnode(); //constructor that takes a const reference to the Type //stored in the data portion of the node slnode(cosnt T&); private: T data; int* nextPtr; }; #include "slnode.template"
slnode.templateCode:#include "slnode.h" template<class T> class sclist { public: //default constructor sclist(); //deconstructor ~sclist(); //inserts a node at the head of the list InsertAtHead(const T&); //inserts a node at the tail of the list InsertAtTail(const T&); //returns a pointer to the node removed //from the head of the list RemoveFromHead(); //returns a pointer to the node removed //from the tail of the list RemoveFromTail(); //true if the list is empty, otherwise false bool IsEmpty(); //moves headPtr one node forward in the list void Advance(); //returns a pointer to the first node in the list //starting from the head of the list, that contains //the indicated data. If the data is not in the list, //returns NULL. slnode<T>* Locate(T data); private: T* headPtr; int size; }; #include "sclist.template"
sclist.templateCode:#include "slnode.h" slnode::slnode() { data = NULL nextPtr = NULL } slnode::slnode(T data) { data = T data nextPtr = NULL }
Code:#include sclist.h sclist::sclist() { headPtr = NULL; size = 0; } sclist::~sclist() { //here need to delete all the nodes and set the headPtr back to NULL //and size equal to 0 //temp count variable int i; //loops through starting at the front and uses the RemoveFromHead //function to remove all the nodes till none are left at which point //the loop is broken and size and headPtr get set back to their //starting values of 0 and NULL respectively. for(i=1;i <= 5;i++) { RemoveFromHead(); } size = 0; headPtr = NULL; } sclist::InsertAtHead() { //this is a temp pointer that points to the current node T* currentPtr = new currentPtr; //if there is nothing in the list if(headPtr == NULL) { // makes a new list sclist = new T sclist; //makes a new node and puts data into it slnode = new T slnode(data); //sets the headPtr of the list to the newly created node headPtr = slnode; //this sets the currentPtr equal to the headPtr currentPtr = headPtr; //since its a circular list the only nodes nextPtr must point to //itself nextPtr = headPtr; //increments size size++; { //if there is something in the list else if(headPtr != NULL) { //it will fist make a new node slnode = new T slnode(data); //it will first set the headPtr to the new node headPtr = slnode; //will set the nextPtr of the slnode equal to teh currentPtr //so that it will now point to the previous node nextPtr = currentPtr; //now needs to make the first nodes nextPtr point to the head nextPtr = headPtr; //increments the size size++; } } sclist::InsertAtTail() { //first will walk through size times to get to the correct node then //will take that node that has the nextPtr pointing to the head and //set currentPtr equal to that nextPtr. Then it will have that nextPtr //point to the new node. Then have the new nodes nextPtr set //equal to the currentPtr. //temp count variable int i; //check to see if this is the first node in the list being added and if it is //the node will just be inserted at the head if(headPtr = NULL) { InsertAtHead(); } else if(headPtr != NULL) { //will set the currentPtr back to headPtr so it starts at the beginning of //the list currentPtr = headPtr; //this for loop will go through chaging what currentPtr is equal to for(i=1;i<=size;i++) { currentPtr = currentPtr->nextPtr; } //creates a new node with the data in it. slnode = new T slnode(data); //set the nextPTr of the new node equal to the currentPtr which will be //pointing to the headPtr nextPtr = currentPTr; //sets the last end nodes nextPtr equal to the new node nextPtr = slnode; } } //returns a pointer to the node removed from the head of the list sclist::RemoveFromHead() { //going to have the currentPtr set equal to the headPtr. Then set the headPtr //equal to the nextPtr of the node we are removing from the head. Then delete //the currentPtr because it will be pointing to the now unliked node currentPtr = headPtr; headPtr = headPtr->nextPtr; delete currentPtr; } //returns a pointer to the node removed from the tail of the list. sclist::RemoveFromTail() { //Walk through the list size number of times. //Set up a temp pointer named delete equal to that //node. Then walk through the list again but this time size-1 times and //set that nodes nextPtr equal to headPtr.Then delete the delete pointer //temp count variable int i; //the tempPtr named tempEnd T* delete = new delete; //set currentPtr equal to the head delete = head; //the for loop to walk to the end of the list for(i=1;i<=size;i++) { delete = delete->nextPtr; } //now will go through size-1 times for(i=1;i<=size-1;i++) { currentPtr = currentPtr->nextPtr; } //this leaves the previous tail node unlinked nextPtr = headPtr; //deletes the unlinked node delete delete; } //true if the list is empty, otherwise false. sclist::IsEmpty() { //if the headPtr is equal to null then its empty; if(headPtr == NULL) { IsEmpty = true; } else { IsEmpty = false; } } //moves headPtr one node forward in the list. sclist::Advance() { //is just advancing one spot so just set currentPtr equal to the nextPtr currentPtr = currentPtr->nextPtr; } //returns a pointer to the first node in the list, starting from the head of //the list,that contains the indicated data. If the data is not in the list, //returns NULL. sclist::Locate(T data) { //will first set currentPtr equal to head. Then it will advance one at a //time and check the data to see if it matches the data in the parameter. //If not it will continue to move on. A if statement will be used here. //a temporary counter so that when or if the data is found it will have a //number that will correspond to where in the size it is. int count; if(*currentPtr != data) { Advance(); //need an if statement to see if its at the end of the list will compare //count to the size if they are equal it will stop and print not found. if(size = count) { cout << "Data not found." << endl; break; } count++; } //if the data is found else if(*currentPtr == data) { //will print the count number the data is located at and then break. cout << "Data found at node #" << count << endl; break; } }