singly linked circular list

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

Quote:

---

Part 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

---

slnode.h

Code:

---

#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"

---

sclist.h

Code:

---

#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"

---

slnode.template

Code:

---

#include "slnode.h"

slnode::slnode()
{
    data = NULL
    nextPtr = NULL
}

slnode::slnode(T data)
{
    data = T data
    nextPtr = NULL
}

---

sclist.template

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;
}

}

---