Ad:

C++ Discussion Thread
Marked Solved
Views: 697

Aug 5th, 2008

Circular List help

Expand Post »

The circular list code is incomplete program with lots of feature missing, it's only one specific section that I require help with but I thought it would better to show the entirety of it to help you understand better.

The section surrounded by -------------------------- is where I'm stuck, basically the print() method should start at the first element and go through the circular list printing each element until it returns to the first element. The program then rotates the list and prints each element again.

I feel that it maybe the "do...while" loop is causing the program since when I changed the "while" expression to "(c = while)", obviously wrong as it never ended, it successfully ran through the program and printed each element but when it's "(c != while)" it fails.

If anyone can offer any assistance as to what I've done wrong then it would be greatly appreciated, I've racked my brains for long time now! (I suck)

c++ Syntax (Toggle Plain Text)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
struct listitem {
  int contents;
  struct listitem* next;
  struct listitem* prev;
};
 
class rotatableList {
protected:
  listitem *first;
  int size;
public:
  rotatableList() {
    first=NULL;
    size=0;
  }
};
 
class singleRotateList : public rotatableList {
public:
  void addFirst(int i) {
// Adds a new list element with contents i
// at the start of the list
 
    struct listitem* newItem=new listitem();
 
    newItem->contents=i;
 
    if (!first) {
      newItem->next=newItem;
      newItem->prev=newItem;
      first=newItem;
    }
    else {
       newItem->next=first;
       newItem->prev=first->prev;
       first->prev->next=newItem;
       first->prev=newItem;
       first=newItem;
 
   }
 
// Omitted: code to increment "size"
    size++;
  }
//---------------------------------------------------------------------
 void print() {
      listitem *c=first;
 
    if (c) {
        printf("%d\n", *c);
        listitem *c=first=first->next;
 
        do{
            printf("%d\n", *c);
            listitem *c=first=first->next;
        }while (c != first);
    }
  }
// Omitted: code to
// - print out contents of list element referred to by c
//   (followed by a new line);
// - make c point to the next element in the list;
// - Do the following while c doesn't refer to the same list
//   element referred to by first:
//   - print out contents of list element referred to by c
//     (followed by a new line);
//   - make c point to the next element in the list;
//----------------------------------------------------------------------
 
  void rotate() {
// Make first refer to the next item in the list
    if (first) first=first->next;
  }
};
 
class randomRotateList : public rotatableList {
public:
  void rotate() {
    if (first) {
    }
  }
};
 
main() {
  srand(time(NULL)); // This initialises the random number generator
 
  printf("Creating a singleRotateList and rotating it:\n");
  singleRotateList* l=new singleRotateList();
  l->addFirst(3);
  l->addFirst(4);
  l->addFirst(5);
  l->addFirst(6);
  l->print();
 
  l->rotate();
  printf("\nAfter rotation:\n");
  l->print();
 
  delete l;
 
  printf("\nNow using a randomRotateList:\n");
}
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct listitem {
  int contents;
  struct listitem* next;
  struct listitem* prev;
};

class rotatableList {
protected:
  listitem *first;
  int size;
public:
  rotatableList() {
    first=NULL;
    size=0;
  }
};

class singleRotateList : public rotatableList {
public:
  void addFirst(int i) {
// Adds a new list element with contents i
// at the start of the list

    struct listitem* newItem=new listitem();

    newItem->contents=i;

    if (!first) {
      newItem->next=newItem;
      newItem->prev=newItem;
      first=newItem;
    }
    else {
       newItem->next=first;
       newItem->prev=first->prev;
       first->prev->next=newItem;
       first->prev=newItem;
       first=newItem;

   }

// Omitted: code to increment "size"
    size++;
  }
//---------------------------------------------------------------------
 void print() {
      listitem *c=first;

    if (c) {
        printf("%d\n", *c);
        listitem *c=first=first->next;

        do{
            printf("%d\n", *c);
            listitem *c=first=first->next;
        }while (c != first);
    }
  }
// Omitted: code to
// - print out contents of list element referred to by c
//   (followed by a new line);
// - make c point to the next element in the list;
// - Do the following while c doesn't refer to the same list
//   element referred to by first:
//   - print out contents of list element referred to by c
//     (followed by a new line);
//   - make c point to the next element in the list;
//----------------------------------------------------------------------

  void rotate() {
// Make first refer to the next item in the list
    if (first) first=first->next;
  }
};

class randomRotateList : public rotatableList {
public:
  void rotate() {
    if (first) {
    }
  }
};

main() {
  srand(time(NULL)); // This initialises the random number generator

  printf("Creating a singleRotateList and rotating it:\n");
  singleRotateList* l=new singleRotateList();
  l->addFirst(3);
  l->addFirst(4);
  l->addFirst(5);
  l->addFirst(6);
  l->print();

  l->rotate();
  printf("\nAfter rotation:\n");
  l->print();

  delete l;

  printf("\nNow using a randomRotateList:\n");
}

Last edited by Corum; Aug 5th, 2008 at 4:12 pm.

Similar Threads

Circular linked list in C
Doubly linked circular list in C
circular linked lists in C++
Removing an item from head of linked list in C
linked list question in C

Corum

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

6 posts
since Nov 2006

Permalink

Aug 5th, 2008

Re: Circular List help

Well you probably shouldn't be modifying first, just to print it.

Salem

Team Colleague

Reputation Points: 5862

Solved Threads: 950

Posting Sage

Offline

7,164 posts
since Dec 2005

Permalink

Aug 5th, 2008

Re: Circular List help

You have three cs there:
line 51
line 55
line 59
Your loop will never terminate because every c is always == first (so no matter which of the three the compiler chooses to use you've got an infinite loop).

Make sure to use just one c.

Also, watch how many times you change first. You want to bump it just once (if I understand you right).

C++ Syntax (Toggle Plain Text)
void print() {
    listitem *c=first;
 
    if (c) {
        printf("%d\n", *c);
        c=first=first->next;
 
        do{
            printf("%d\n", *c);
            c=c->next;
        }while (c != first);
    }
  }
void print() {
    listitem *c=first;

    if (c) {
        printf("%d\n", *c);
        c=first=first->next;

        do{
            printf("%d\n", *c);
            c=c->next;
        }while (c != first);
    }
  }

Hope this helps.

[edit] BTW. What if your circular list has just one item? (It will get printed twice.)

Last edited by Duoas; Aug 5th, 2008 at 4:28 pm.

Duoas

Featured Poster

Reputation Points: 1140

Solved Threads: 229

Postaholic

Offline

2,039 posts
since Oct 2007

Permalink

Aug 5th, 2008

Re: Circular List help

Thanks a lot for helping me understand where I was going wrong and explaining it so well you've been a huge help.

The circular list always have 4 items (in main() you see them added to addFirst()) so it shouldn't be a problem.

Thank you again!

Corum

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

6 posts
since Nov 2006

Permalink

Aug 6th, 2008

Re: Circular List help

Last problem I promise! I've succesfully got the singleRotateList() to work and output but after that's executed I want it execute the randomRotateList() and output accordingly.

The problem is the main() method I have calling it two different rotate() methods but it keeps referring to the first rotate(), ideally I want it to call to the first for the singleRotateList() and the second rotate() for randomRotateList().

I'm not to hot on abstract and overridable methods so if anyone can give me tips as to how I can achieve this it would be much appreciated, again!

c++ Syntax (Toggle Plain Text)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
struct listitem {
  int contents;
  struct listitem* next;
  struct listitem* prev;
};
 
class rotatableList {
 
protected:
  listitem *first;
  int size;
public:
  rotatableList() {
    first=NULL;
    size=0;
  }
 
void addFirst(int i) {
 
    struct listitem* newItem=new listitem();
 
    newItem->contents=i;
 
    if (!first) {
        newItem->next=newItem;
        newItem->prev=newItem;
        first=newItem;
    }
    else {
        newItem->next=first;
        newItem->prev=first->prev;
        first->prev->next=newItem;
        first->prev=newItem;
        first=newItem;
    }
 
  size++;
 
  }
 
  void print() {
      listitem *c=first;
 
    if (c) {
        printf("%d\n", *c);
        c=first->next;
        do{
            printf("%d\n", *c);
            c=c->next;
        }while (c != first);
    }
  }
 
    void rotate() {
 
    if (first) first=first->next;
 
    }
 
};
 
class singleRotateList : public rotatableList {
    public:
 
 
};
 
class randomRotateList : public rotatableList {
public:
  void rotate() {
    if (first) {
 
        int numberOfTimes = rand() % 4;
        printf("The list will be rotated %d times.\n", numberOfTimes);
        for (int i = 0; i<numberOfTimes; i++){
            first=first->next;
        }
    }
  }
};
---------------------------------------------------------------------------------
main() {
  srand(time(NULL)); // This initialises the random number generator
 
  printf("Creating a singleRotateList and rotating it:\n");
  rotatableList* l=new singleRotateList();
  l->addFirst(3);
  l->addFirst(4);
  l->addFirst(5);
  l->addFirst(6);
  l->print();
 
  l->rotate();
  printf("\nAfter rotation:\n");
  l->print();
 
  delete l;
 
  printf("\nNow using a randomRotateList:\n");
 
  l=new randomRotateList();
  l->addFirst(3);
  l->addFirst(4);
  l->addFirst(5);
  l->addFirst(6);
  l->print();
 
  l->rotate();
  printf("\nAfter rotation:\n");
  l->print();
---------------------------------------------------------------------------------
}
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct listitem {
  int contents;
  struct listitem* next;
  struct listitem* prev;
};

class rotatableList {

protected:
  listitem *first;
  int size;
public:
  rotatableList() {
    first=NULL;
    size=0;
  }

void addFirst(int i) {

    struct listitem* newItem=new listitem();

    newItem->contents=i;

    if (!first) {
        newItem->next=newItem;
        newItem->prev=newItem;
        first=newItem;
    }
    else {
        newItem->next=first;
        newItem->prev=first->prev;
        first->prev->next=newItem;
        first->prev=newItem;
        first=newItem;
    }

  size++;

  }

  void print() {
      listitem *c=first;

    if (c) {
        printf("%d\n", *c);
        c=first->next;
        do{
            printf("%d\n", *c);
            c=c->next;
        }while (c != first);
    }
  }

    void rotate() {

    if (first) first=first->next;

    }

};

class singleRotateList : public rotatableList {
    public:


};

class randomRotateList : public rotatableList {
public:
  void rotate() {
    if (first) {

        int numberOfTimes = rand() % 4;
        printf("The list will be rotated %d times.\n", numberOfTimes);
        for (int i = 0; i<numberOfTimes; i++){
            first=first->next;
        }
    }
  }
};
---------------------------------------------------------------------------------
main() {
  srand(time(NULL)); // This initialises the random number generator

  printf("Creating a singleRotateList and rotating it:\n");
  rotatableList* l=new singleRotateList();
  l->addFirst(3);
  l->addFirst(4);
  l->addFirst(5);
  l->addFirst(6);
  l->print();

  l->rotate();
  printf("\nAfter rotation:\n");
  l->print();

  delete l;

  printf("\nNow using a randomRotateList:\n");

  l=new randomRotateList();
  l->addFirst(3);
  l->addFirst(4);
  l->addFirst(5);
  l->addFirst(6);
  l->print();

  l->rotate();
  printf("\nAfter rotation:\n");
  l->print();
---------------------------------------------------------------------------------
}

Corum

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

6 posts
since Nov 2006

Permalink

Aug 6th, 2008

Re: Circular List help

Use magical word virtual in

C++ Syntax (Toggle Plain Text)
class rotatableList {
...
virtual void rotate () ...
...
};
class rotatableList {
...
virtual void rotate () ...
...
};

and try again...

Last edited by ArkM; Aug 6th, 2008 at 12:32 pm.

ArkM

Reputation Points: 1234

Solved Threads: 347

Postaholic

Offline

2,001 posts
since Jul 2008

Permalink

Aug 6th, 2008

Re: Circular List help

That indeed is a magical word, thanks for the help! Hugely appreciated.

Corum

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

6 posts
since Nov 2006

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: trouble with multi text char

Next Thread in C++ Forum Timeline: Linking error in the compiler given by topcoder. Plz help me out guys.

DaniWeb Message

Cancel Changes

User Name
Password