• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 261
  • Last Modified:

creating a copy constructor for a circluar linked list

I am working on a program that will simulate the Josephus problem.  My problem comes in when I need to create the copy constructor.  I cannot see how to copy all the private members in my class as well as all the nodes in the original list.

My class is:
#ifndef CIRCLINKEDLIST_H
#define CIRCLINKEDLIST_H
#include "CIRCLINKEDLIST.H"

typedef struct node* NodePtr;
typedef char NodeItemType;

struct node
{
    NodeItemType item;
    NodePtr next;
};


class CircleLL
{
public:
    CircleLL();
    ~CircleLL();
    CircleLL(const CircleLL& objtocopy);
    void operator= (const CircleLL& rightside);

    void insert(const NodeItemType& newItem, bool& success);
    //inserts a new node at last position.  newItem is the data to insert

    void remove(int index, bool& success);
    //removes node at index number.  index is the number to jump by

    NodeItemType retrieve(int index, bool& success);
    //retuns the specified item type at the index number in the list
    //if index is 3, the 3rd item in the list will be returned

    bool isEmpty();
    //returns true if the list is empty

    int getLength();
    //returns the number of nodes in the list

    void curPosition(int& index);
    //moves cur pointer to the desired index position


private:

    NodePtr head;
    //head pointer(doesn't move)

    NodePtr cur;
    //cur points to the current node you
    //want to access

    int size;
    //size of the circle linked list

};

Please help if you can, and if more information is needed please tell me.
0
ECUBlake
Asked:
ECUBlake
  • 11
  • 8
1 Solution
 
n_fortynineCommented:
>> I cannot see how to copy all the private members in my >> class as well as all the nodes in the original list.
What *part* can you not see how? Btw some code would be helpful.
0
 
ECUBlakeAuthor Commented:
Here is the code for the class. If I insert 5 nodes to my list, I need to be able to copy all five nodes and the anything else in the class.

//circlinkedlist.cpp

CircleLL::CircleLL():size(0), head(NULL)
{
    cur = head;
}

void CircleLL::insert (const itemtype& NewItem, bool& success)
{
         if(head == NULL)                      //insert to empty list
         {
             NodePtr temp = new node;
             temp->next=temp;
             temp->item=NewItem;
             head=temp;
         }
         else
         {    cur = head;
              do
              {
                  cur = cur->next;
              }while(cur->next != head);

              NodePtr temp = new node;
              cur->next = temp;
              temp->item = NewItem;
              temp->next = head;
         }

     size++;
     success = true;
}


void CircleLL::remove(int index, bool& success)
{
    NodePtr prev = head;
    NodePtr killptr = cur;

    while(prev->next != killptr)
    {
         prev = prev->next;
    }
    cerr << "Kill   : " << killptr->item << endl;
    if(killptr == head)                 //delete head node
    {
         prev->next = head;
         cur = cur->next;
         killptr->next = NULL;
         delete killptr;
    }

    else                                      //delete all other nodes
    {
         prev->next = killptr->next;
         cur = cur->next;                     //update cur pointer to point to
         killptr->next = NULL;                //next "alive" node
         delete killptr;
    }
    cerr << "current: " << cur->item << endl;
    size--;
}

NodeItemType CircleLL::retrieve(int index, bool& success)
{
    curPosition(index);              //return item of the current node

    return cur->item;
}

bool CircleLL::isEmpty ()
{
    return bool(size == 0);
}

int CircleLL::getLength()
{
    return size;
}

void CircleLL::curPosition(int& index)
{
    for(int count = 1; count < index; ++count)         //transverse list to jump
        cur = cur->next;                               //number
}


#endif
0
 
n_fortynineCommented:
I think this will work, please verify I have to go to class:
CircleLL::CircleLL(const CircleLL& obj) : head(NULL), cur(NULL), size(obj.size) {
   if(size) {
      NodePtr tmp = obj.head;
      cur = new node;
      cur->item = tmp->item;
      tmp = tmp->next;
      head = cur;

      while(size - 1) {
         cur->next = new node;
         cur = cur->next;
         cur->item = tmp->item;
         tmp = tmp->next;
      }

      tmp = NULL;
      cur->next = head;
      cur = head;
   }
}
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
n_fortynineCommented:
>> while(size - 1) changes too while(--size) then add the size = obj.size to the end of this. sorry i wrote in a hurry.
0
 
ECUBlakeAuthor Commented:
its still not copying right, my input has duplicates of some info.  big help though, at least something is printing out now.  but i know for sure my insert function is working correctly, and the program crashes most likely because of pointer errors while copying.
0
 
n_fortynineCommented:
I think this whole piece works for me, what i changed was I reset cur to head at the beginning of retrieve. You HAVE TO write the destructor. I compiled this on UNIX GCC.

#ifndef CIRCLINKEDLIST_H
#define CIRCLINKEDLIST_H

#include <stddef.h>
#include <errno.h>
#include <iostream.h>

typedef struct node* NodePtr;
typedef char NodeItemType;

struct node {
   NodeItemType item;
   NodePtr next;
};

class CircleLL {
   public:
      CircleLL();
      ~CircleLL() {}
      CircleLL(const CircleLL& objtocopy);
      void operator= (const CircleLL& rightside);
      void insert(const NodeItemType& newItem, bool& success);
      void remove(int index, bool& success);
      NodeItemType retrieve(int index, bool& success);
      bool isEmpty();
      int getLength();
      void curPosition(int& index);

   private:
      NodePtr head;
      NodePtr cur;
      int size;
};

#endif

CircleLL::CircleLL() : size(0), head(NULL), cur(head) {}

void CircleLL::insert(const NodeItemType& NewItem, bool& success) {
   if(!head) {
      NodePtr temp = new node;
      temp->next = temp;
      temp->item = NewItem;
      head = temp;
   }
   else {
      cur = head;
      do { cur = cur->next; } while(cur->next != head);
      NodePtr temp = new node;
      cur->next = temp;
      temp->item = NewItem;
      temp->next = head;
   }

   size++;
   success = true;
}

void CircleLL::remove(int index, bool& success) {
   NodePtr prev = head;
   NodePtr killptr = cur;

   while(prev->next != killptr) { prev = prev->next; }
   cerr << "Kill   : " << killptr->item << endl;
   if(killptr == head) {
      prev->next = head;
      cur = cur->next;
      killptr->next = NULL;
      delete killptr;
   }
   else {
      prev->next = killptr->next;
      cur = cur->next;                     //update cur pointer to point to
      killptr->next = NULL;                //next "alive" node
      delete killptr;
   }

   cerr << "current: " << cur->item << endl;
   size--;
}

NodeItemType CircleLL::retrieve(int index, bool& success) {
   cur = head;
   curPosition(index);
   return cur->item;
}

bool CircleLL::isEmpty () { return !size; }

int CircleLL::getLength() { return size; }

void CircleLL::curPosition(int& index) {
   for(int count = 1; count < index; ++count)
       cur = cur->next;
}

CircleLL::CircleLL(const CircleLL& obj) : head(NULL), cur(NULL), size(obj.size) {
  if(size) {
     NodePtr tmp = obj.head;
     cur = new node;
     cur->item = tmp->item;
     tmp = tmp->next;
     head = cur;

     while(--size) {
        cur->next = new node;
        cur = cur->next;
        cur->item = tmp->item;
        tmp = tmp->next;
     }

     tmp = NULL;
     cur->next = head;
     cur = head;
     size = obj.size;
  }
}

int main() {
   CircleLL L1;
   bool s;
   L1.insert('a', s);
   L1.insert('b', s);
   cout << s << "\n";
   CircleLL L2(L1);
   cout << L2.retrieve(1, s) << L2.retrieve(2, s);
}

You put this all in one .cpp file and test it, change the main() to your main() if you want, let me know how it turns out. I need to go to class again. =)
0
 
n_fortynineCommented:
you might want to test the sensitive cases (copy empty lists, copy one item lists etc. and test your delete cos I didn't test it)
0
 
ECUBlakeAuthor Commented:
haha... I'm almost completely stumped... and my professor doesn't have office hours today. after this is solved, or if it does i'll increase points to 75 (thats all i have :) ) but below is a copy of my main.  what i need to do is move around the circle and "kill" a node at index position, then move to the next "alive" node then jump index nodes and "kill" that one until there is one left.
i really appricate the help.

#include <fstream.h>
#include <iostream.h>
#include <stdlib.h>
#include "CIRCLINKEDLIST.H"

void display(CircleLL y, bool& success)
{
    NodeItemType data;

    cout << "          size=" <<y.getLength() << "  (";
    for(int count = 1; count <= y.getLength(); count++)
    {
        data = y.retrieve(count, success);
        cout << data << ", ";
    }
    cout << ")" << endl;
}


void main()
{
     NodeItemType newitem;
     bool success;

     CircleLL x;

     char filename[30];
     ifstream infile;

     int index=0;
     cout << "Enter number of jumps: ";
     cin >> index;

     cout << "Enter the file name: ";
     cin >> filename;

     infile.open(filename);          //check for vaild file name
     if(infile.fail())
     {
         cout << "Error: No such file name." << endl;
         system("PAUSE");
         exit(1);
     }

     NodeItemType data;

     while(infile >> data)                //get all data from file
     {
         x.insert(data, success);
     }
     cout << "Starting length is: " << x.getLength() << endl;

     display(x, success);
     cout << endl;

     while(x.getLength() > 1)
     {
        x.remove(index, success);
        x.curPosition(index);
        display(x, success);
     }

     system("PAUSE");
}
0
 
n_fortynineCommented:
Here's a solution for this problem from a non-OO POV you can have a look at. I still have one last class so I can't help much till I'm back.

//@Description: Solving the Joshua Death's Problem
//              Starting from 1, count circularly to M then that person kills himself.
#include <iostream.h>

struct node {
   int key;
   node *next;
};

int main() {
   int i, M, N;                 //M < N.
   node *t, *x;

   cout << "Enter them now: \n";
   cin >> N >> M;

   t = new node;
   t -> key = 1;                //Insert first item.
   x = t;                       //x is now "head."

   for(i = 2; i <= N; ++i) {
      t -> next = new node;
      t = t -> next;
      t -> key = i;
   }                            //Finish inserting items from 1 to N.

   t -> next = x;               //Circular list.

   while(t != t -> next) {      //While there ain't only 1 node
      for(i = 1; i < M; ++i)    //Traverse M positions
         t = t -> next;
      cout << t -> next -> key << " ";
      x = t -> next;
      t -> next = x -> next;
      delete x;
   }

   cout << t -> key << " ";
}
0
 
n_fortynineCommented:
N is the number of people and M is the number of jumps
0
 
n_fortynineCommented:
There's a problem with your remove(). int index is not used and really shouldn't be there. I gotta go to class.
0
 
n_fortynineCommented:
ok i won't. could you explain more to me what remove() is supposed to do?
0
 
ECUBlakeAuthor Commented:
remove() "kills" or takes a node out of the list.
0
 
n_fortynineCommented:
yeah but what does index do. So if I do remove(3,success) then the 3rd node gets removed then? Ok.
0
 
ECUBlakeAuthor Commented:
remove() "kills" or takes a node out of the list.
0
 
ECUBlakeAuthor Commented:
remove() "kills" or takes a node out of the list.
0
 
n_fortynineCommented:
your code for traversing and killing the list in main doesn't make sense. you first try to remove the item at the index-th position, ok this is done.

Then you advance cur an index number of positions, yes it might circle around to be somewhere, but THEN your code will remove the item at the index-th position again???

I think you're expecting remove() to remove the item in the index-th position and at the same time remove the item where cur is pointing to. This is impossible!!!

You need to change the order of the calls.
Inside the while loop in main:
{
 //First you advance cur to THE NODE BEFORE THE
 //TO_BE_REMOVED. curPosition has to be reimplemented.
 curPosition(index);
 //Then remove the item which cur is pointing to.
 //No index here.
 remove(success);
 //Then display, whatever you want.
}

How's that? Do you want to do it that way or do the specs for your program unchangable?
0
 
ECUBlakeAuthor Commented:
wow.... don't i feel dumb :)  you're right the order of the remove() and traverse function made a big difference, and now there are no more errors.  I can't thank you enough
0
 
ECUBlakeAuthor Commented:
big help and very fast responses
0

Featured Post

Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

  • 11
  • 8
Tackle projects and never again get stuck behind a technical roadblock.
Join Now