DaniWeb Forum Index > Software Development > C++

Circular List help

Thread Solved

•

Join Date: Nov 2006

Posts: 6

Reputation: Corum is an unknown quantity at this point

Solved Threads: 0

Corum

Offline

Newbie Poster

Circular List help

Aug 5th, 2008

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)

 Help with Code Tags 
 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 3:12 pm.

•

Join Date: Dec 2005

Posts: 6,590

Reputation: Salem has a reputation beyond repute

Solved Threads: 851

Salem

Offline

Void main'ers are DOOMed

Re: Circular List help

Aug 5th, 2008

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

If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
--
If your code lacks code tags, you will be IGNORED

•

Join Date: Oct 2007

Posts: 1,979

Reputation: Duoas has much to be proud of

Solved Threads: 220

Duoas

Offline

Posting Virtuoso

Re: Circular List help

Aug 5th, 2008

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).

 Help with Code Tags 
 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 3:28 pm.

•

Join Date: Nov 2006

Posts: 6

Reputation: Corum is an unknown quantity at this point

Solved Threads: 0

Corum

Offline

Newbie Poster

Re: Circular List help

Aug 5th, 2008

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!

•

Join Date: Nov 2006

Posts: 6

Reputation: Corum is an unknown quantity at this point

Solved Threads: 0

Corum

Offline

Newbie Poster

Re: Circular List help

Aug 6th, 2008

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!

 Help with Code Tags 
 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();
---------------------------------------------------------------------------------
}

•

Join Date: Jul 2008

Posts: 2,001

Reputation: ArkM has much to be proud of

Solved Threads: 344

ArkM

Offline

Postaholic

Re: Circular List help

Aug 6th, 2008

Use magical word virtual in

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

and try again...