?
Solved

creating a copy constructor for a circluar linked list

Posted on 2003-03-19
19
Medium Priority
?
257 Views
Last Modified: 2010-04-01
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
Comment
Question by:ECUBlake
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 11
  • 8
19 Comments
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8168386
>> 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
 

Author Comment

by:ECUBlake
ID: 8168495
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
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8168656
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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 4

Expert Comment

by:n_fortynine
ID: 8168664
>> 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
 

Author Comment

by:ECUBlake
ID: 8168763
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
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8169337
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
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8169350
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
 

Author Comment

by:ECUBlake
ID: 8169569
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
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8170161
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
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8170176
N is the number of people and M is the number of jumps
0
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8170278
There's a problem with your remove(). int index is not used and really shouldn't be there. I gotta go to class.
0
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8170287
ok i won't. could you explain more to me what remove() is supposed to do?
0
 

Author Comment

by:ECUBlake
ID: 8170366
remove() "kills" or takes a node out of the list.
0
 
LVL 4

Expert Comment

by:n_fortynine
ID: 8170402
yeah but what does index do. So if I do remove(3,success) then the 3rd node gets removed then? Ok.
0
 

Author Comment

by:ECUBlake
ID: 8170418
remove() "kills" or takes a node out of the list.
0
 

Author Comment

by:ECUBlake
ID: 8170487
remove() "kills" or takes a node out of the list.
0
 
LVL 4

Accepted Solution

by:
n_fortynine earned 300 total points
ID: 8170507
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
 

Author Comment

by:ECUBlake
ID: 8170736
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
 

Author Comment

by:ECUBlake
ID: 8170742
big help and very fast responses
0

Featured Post

On Demand Webinar: Networking for the Cloud Era

Did you know SD-WANs can improve network connectivity? Check out this webinar to learn how an SD-WAN simplified, one-click tool can help you migrate and manage data in the cloud.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
Suggested Courses

800 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question