circular link list in c++

[saraSS]

I'm trying to built and array of circular link list but when I read the input file Ijust get a long link list instead of different list and after trying to use Linked_list_Stack *obj[arraysize]; I'm getting this errors
newcir.cpp:107: request for member `push' in `obj[i]', which is of
non-aggregate type `Linked_list_Stack*'
newcir.cpp:110: request for member `print_list' in `obj[i]', which is of
non-aggregate type `Linked_list_Stack*'

[saraSS]

yes I did thanks I'm gonna work on the evaluation now let you know what else is wrong lol ;)

[saraSS]

ok I'm back to the circular lists how can I name my circular lists (from a to z) for easy manipulation of the lists like when I'm doing the postfix evaluation I refer to "a" and "b" instead of the whole list ?

[arne]

ok I'm back to the circular lists how can I name my circular lists (from a to z) for easy manipulation of the lists like when I'm doing the postfix evaluation I refer to "a" and "b" instead of the whole list ?

You could define a header struct which holds this info (i.e. an identifier) and the reference to the list. Your vector would then be no more a vector of lists, but a vector of these headers structs.

[saraSS]

how do I do that? example please

[saraSS]

struct headernode{
char x;
listNodeType *next;
};

then in main
char listname = 'a';
ListClass ListA[arraysize];
headernode header[arraysize];

then in m while loop
header[i].x=listname++;
header[i].next=ListA[i];

but error lol
mycirlist.cpp:329: cannot convert `ListClass' to `listNodeType*' in assignment

[saraSS]

should I use the same node I have for the list ?

[arne]

should I use the same node I have for the list ?

Yes the member of the header struct shoud have type 'struct node' (or how you called the type of a list element). It is the entry point to the list.

[saraSS]

I have a class node for the list like this
class ListNodeClass
{
private:
ItemType Info;
ListNodeClass * Next;
public:
// First, the constructor:
ListNodeClass(const ItemType & Item, ListNodeClass * NextPtr = NULL):
Info(Item), Next(NextPtr)
{
};
void GetInfo(ItemType & TheInfo) const;
friend class ListClass; // very convenient to allow this
};

[arne]

I have a class node for the list like this
class ListNodeClass
{
private:
ItemType Info;
ListNodeClass * Next;
public:
// First, the constructor:
ListNodeClass(const ItemType & Item, ListNodeClass * NextPtr = NULL):
Info(Item), Next(NextPtr)
{
};
void GetInfo(ItemType & TheInfo) const;
friend class ListClass; // very convenient to allow this
};

Ok, if that's the type of the nodes, use a pointer to such a class as the entry to the list in your header struct. Since the list is circular (is it?), you can let it point to an arbitrary element.

[saraSS]

how do I do this? pointers are not my good subjets lol

[arne]

how do I do this? pointers are not my good subjets lol

But you had it already (almost):

struct headernode{
        char x;
        listNodeType *next;
}; 
 

Replace listNodeType by ListNodeClass. Note that you have to change all access to a list, since you have an array of header structs now...

[saraSS]

going in circles here cant make it work with those pointers another way to do that?

[arne]

going in circles here cant make it work with those pointers another way to do that?

Since the vector has a constant number of elements, you could establish some mapping:

a is 0
b is 1
c is 2 and so on.

If you need set b, you know its the second (index 1) in your vector. But do not change the vector then or you will run in trouble ;-)

Alternatively, you could extend your nodes by another member. Instead of storing the identifier in a header you can store it in every node of the list. This is somewhat ugly, but you can go on with your current design ...

[saraSS]

I dont know nothing is working

[saraSS]

class ListNodeClass
{
private:
ItemType Info;
ListNodeClass * Next;
public:
// First, the constructor:
ListNodeClass(const ItemType & Item, ListNodeClass * NextPtr = NULL):
Info(Item), Next(NextPtr)
{
};
void GetInfo(ItemType & TheInfo) const;
friend class ListClass; // very convenient to allow this
};

struct headernode
{
char x;
ListClass *next;
};

class ListClass
{
private:
ListNodePtr GetNode(const ItemType & Item,
ListNodePtr NextPtr = NULL);
void FreeNode(ListNodePtr NodePtr);
void ClearList();
// Next 3 are sometimes made into protected fields:
ListNodePtr Front, Rear;
int Count;
public:
// constructor:
ListClass();
// destructor:
~ListClass();
int NumItems() const;
bool Empty() const;
void InsertRear(const ItemType & Item);
void printing();
ItemType RemoveFront();
ListNodePtr Find(const ItemType & Item) const;

};
int main()
{
int i,m;
char postfix[80];
char listname = 'a';

cin>>arraysize;
ListClass ListA[arraysize],*L;
L=ListA;
for( i = 0; i <arraysize; i++ )
{
while(cin>>number && number!=-1)
{
ListA[i].InsertRear(number);
}
cout<<ListA[i].NumItems()<<" ";
ListA[i].printing();
cout<<endl;
}
return 0;
}

this is almost what I have now and but cant make it work dont know why?and I have tried everyway you told me what I'm doing wrong

[arne]

this is almost what I have now and but cant make it work dont know why?and I have tried everyway you told me what I'm doing wrong

I have now used your code for a slim version. It's implementing a singly-linked, non-circular(!) list. All you can currently do is adding elements and print the content of the Info member.

Use this as a starting point. Extend the list with all features you need (circularity, removing nodes, ...).

Hope this is helpful :)

#include <iostream>
#include <string>
 
using namespace std;
 
#define ItemType int
 
// the definition of a list node
class ListNodeClass
{
public:
    // the data of a node
    ItemType Info;
 
    // the pointer to the next node
    ListNodeClass *Next;
};
 
 
// the definition of a list (header!)
class ListClass
{
private:
        // entry to the list
    ListNodeClass *Front;
 
    // number of elements
    int Count;           
 
    // the ID to identify the set
        char ID;  
 
    void FreeNode( ListNodeClass* );
 
public:
    ListClass( char id ) : Front(0), Count(0), ID(id) {}
 
    void InsertFront( ListNodeClass& );
    void InsertRear( ListNodeClass& );
 
    void RemoveFront();
 
    void ClearList();
    int NumItems() const { return Count; }
    bool Empty() const;
    void Printing();
 
    ListNodeClass* Find(const ItemType & Item) const;
 
};
 
void ListClass::InsertFront( ListNodeClass& node ) {
 
    node.Next = Front;
    Front = &node;    
    Count++;
}
 
void ListClass::Printing() {
 
    ListNodeClass *ptr = Front;
 
    cout << "This is set " << ID << " (" << Count << " elements): ";
 
    while( ptr!=NULL ) {
 
        cout << ptr->Info << " ";
        ptr = ptr->Next;
    }
 
    cout << endl;
}
 
int main( void )
{
    ListNodeClass *node;
 
    // list a
    ListClass list_a( 'a' );
 
    node = new ListNodeClass;
    node->Info = 21;
    list_a.InsertFront( *node );
 
    node = new ListNodeClass;
    node->Info = 33;
    list_a.InsertFront( *node );
 
    list_a.Printing();
 
    // list b
    ListClass list_b( 'b' );
 
    node = new ListNodeClass;
    node->Info = 3;
    list_b.InsertFront( *node );
 
    node = new ListNodeClass;
    node->Info = 2;
    list_b.InsertFront( *node );
 
    node = new ListNodeClass;
    node->Info = 1;
    list_b.InsertFront( *node );
 
    list_b.Printing();
 
    return 0;
}
 

[saraSS]

thanks gonna try that

[saraSS]

looks like we were trying the same thing
I add 1 to the arraysize and try to put the letter in the first node but getting like 9 10 11 12 13 14 instead of a b c d e f how can I fix that? this is what I did

char listname = 97;

ListClass ListA[arraysize+1];

for( i = 1; i <arraysize+1; i++ )
{
while(cin>>number && number!=-1)
{
ListA[0].InsertRear((int)listname++);
ListA[i].InsertRear(number);
}
cout<<ListA[i].NumItems()<<" ";
ListA[i].printing();
cout<<endl;
}
but getting
1st column the number of elemets of every cirlist
2nd is supose to be the a b c d e f
after that is every list
10 9 1 3 5 7 9 11 13 15 17 19
10 10 2 4 6 8 10 12 14 16 18 20
20 11 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 12 0 3 6 9 12 15 18
7 13 1 4 7 10 13 16 19
7 14 2 5 8 11 14 17 20

[saraSS]

I try 'a' instead of 97 and got the same also

[arne]

I try 'a' instead of 97 and got the same also

You try to store the list's identifier in a list element? Why? That's what the header struct (ListClass) is for. It stores the number of elements and the ID. The list nodes should only store the 'data' (Info member) and the 'Next' node pointer. When printing the list, you get the ID and the number of elements from the ListClass and the data from the ListNodeClass. Please have a look on the code I posted.

Or did I get you wrong?

[saraSS]

It looks like I get that wrong also I need an x where x is a lower-case symbol in the range ‘a’ . . . ‘z’ to indicate that a copy should be made of an input set. This copy will be an ordered singly-linked circular list with a header. A pointer to the header of the cloned list is to be pushed to the stack. ‘a’ indicates that the first
input set should be copied, ‘b’ indicates that the second input set should be copied, and so on.

[arne]

It looks like I get that wrong also I need an x where x is a lower-case symbol in the range ‘a’ . . . ‘z’ to indicate that a copy should be made of an input set. This copy will be an ordered singly-linked circular list with a header. A pointer to the header of the cloned list is to be pushed to the stack. ‘a’ indicates that the first
input set should be copied, ‘b’ indicates that the second input set should be copied, and so on.

You mean you don't understand this or your implementation doesn't work?

[saraSS]

I did not understand this part before and was trying something harder that what is suppose to be but the pointer thing still messing me up

[saraSS]

what I'm trying to do now is a stackclass where i'm gonna have all the fuction to use with the stacklike this
class stackClass
{
public:
stackClass();// constructor:
~stackClass();// destructor:
void Initialize();
void SetExpression(char *str);
void Push(char c);
char Pop();
void Evaluate();
};

and when I'm evalueting the expression I check for the letter and make a copy
'maybe'
l=strlen(eval);
ListNodePtr tmp;
for(i=0;i<l;i++)
{
if(eval[i]>=97 && eval[i]<=122)
{
//tmp=CopyList(eval[i]);
Push(eval[i]);
cout<<eval[i];
}
else
{
A=Pop( );
B=Pop( );
switch(eval[i])
{
case 'U': break;
case 'I': break;
case '-': break;
}
what do you thing?

[arne]

what I'm trying to do now is a stackclass where i'm gonna have all the fuction to use with the stacklike this

I think you're trying to write too much code on your own. As far as I can see the assignment does not prevent you from using the std::stack from STL, does it? So, you don't have to implement a stack class on your own, it's already there!

[saraSS]

how can I do that ? the easy way then?

[arne]

how can I do that ? the easy way then?

Here comes an example on how to use a stack. You can insert it at the end of the program I posted some posting ago ... you know, the one with list_a and list_b ...

    ListClass *tmp_list_ptr;
 
    // define a std::stack
    stack<ListClass *> op_stack;
 
    // get the number of elems on the stack
    cout << "Stack elements:" << op_stack.size() << endl;
 
    // push elems onto the stack
    op_stack.push( &list_b );
    op_stack.push( &list_a );
 
    cout << "Stack elements after 2x push:" << op_stack.size() << endl;
 
    // get the top element
    tmp_list_ptr = op_stack.top();
    cout << "No. of elems in top list: " << tmp_list_ptr->NumItems() 
         << endl;
    cout << "Stack elements after top():" << op_stack.size() << endl;
 
    // remove the top element
    op_stack.pop();
    cout << "Stack elements after pop():" << op_stack.size() << endl;
 

[saraSS]

good gonna try that thanks

[saraSS]

Your example looks look but does not work with my array of circular list or at least I dont know how to make it work so stuck again but i guess everybody in my class is having problem because we got more time I'm gonna try to leave the array in main just to create the set of circular list and in my funtion evaluation want to do the expresion evaluarion as a stack based postfix
like this
int main()
{
ListNodeClass *node;
ListClass *tmp_list_ptr;
int i;

cin>>arraysize;
ListClass list[arraysize];

for(i=0;i<arraysize;i++)
{
while(cin>>number && number!=-1)
{
node = new ListNodeClass;
node->Info = number;
list[i].InsertFront(*node);
}
cout<<list[i].NumItems()<<" ";
list[i].Printing();
cout<<endl;
}
Evaluate();

return 0;
} and for the evaluation

void Evaluate()
{
int i,l,A,B,Q,Z;
char postfix[80];
stack<ListClass *> op_stack;
ListNodeClass *tmp,*e[arraysize];

cin.getline (postfix,80);
SetExpression (postfix);
cout<<"ok";
puts(postfix);
cout<<"ok";
strcpy(eval,postfix);
cout<<"ok";
puts(eval);
cout<<"ok";
l=strlen(eval);
for(i=0;i<l;i++)
{
if(eval[i]>=97 && eval[i]<=122)
{
e=eval[i];
tmp=CopyList(e[i]);
op_stack.push(eval[i]);
cout<<eval[i];
}
else
{
switch(eval[i])
{
case 'U': break;
case 'I': break;
case '-': break;
//case '\'' : break;
case '<' : break;
case '&' : break;
case '|' : break;
case '!' : break;
}
//op_stack.push(Q);
}
}
op_stack.pop();
} but getting some errors
dont know what to do
?

[arne]

So, as far as I understand. If you got all things running (i.e. the creation of the array with the singly-linked circular list), you start to evaluate the expression by scanning it and performing the required action.

So for the sample expression abcdefUUUUIabIacIadIaeIafIUUUU= from your assignment, you push pointers to the lists (IMHO it would be sufficient to use the list identifier, but anyway) onto your stack, so if you reach the first 'U', your stack should look like

f e d c b a

with the top element on the left.

U means set union, so you got to unite the top 2 elements (i.e. lists on your stack). The result is the new top element, so after the U the stack looks like

f+e d c b a

I would say (correct me if I get things wrong here).

So, what you need to do technically is to invoke a routine to unite two lists :-) You may also need to allocate some result list, where you store the temporary result of the last operation (for the f+e list in the example above). The pointer to this temp result is pushed onto your stack.

The lists in your array should not be changed as they're needed for reference in later operations ...

[saraSS]

yes every set needs to be a circular list

[saraSS]

the circular lists are working, to have a pointer for every one of them so I can make a copy of the list and evaluate some expression with the list in a postfix stack based way

[saraSS]

the pointer to the list are the ones not working I need some help with that

[arne]

the pointer to the list are the ones not working I need some help with that

Sure, if I can do it. Anything particular you have problems with?

[saraSS]

yes, I need to read the last line in my input file, and with that line if I have an "a" I need to make a copy of the first circular list and after that push it into the stack I have this fuction but not working think because i need a pointer or something

int main()
{
int i,m;
char postfix[80];
char listname = 97;

cin>>arraysize;
ListClass ListA[arraysize],L[arraysize];


for(i=0;i<arraysize;i++)
{
while(cin>>number && number!=-1)
{
ListA[i].InsertRear(number);
}
cout<<ListA[i].NumItems()<<" ";
ListA[i].printing();
cout<<endl;
}
Initialize ( );
cin.getline(postfix,80,'\n');
SetExpression (postfix);
cout <<postfix<< endl;
puts(postfix);
cout<<"ok";
strcpy(eval,postfix);
m=Evaluate( );
printf("answer: %d", m );
return 0;
}in main and function is

int Evaluate()
{
int i,l,A,B,Q,Z;
l=strlen(eval);

for(i=0;i<l;i++)
{
if(eval[i])
{
Push(eval[i]);
}
else
{
A=Pop( );
B=Pop( );
switch(eval[i])
{
case 'U': break;
case 'I': break;
case '-': break;
case '\'' : break;
case '<' : break;
case '&' : break;
case '|' : break;
case '!' : break;
}
Push(Q);
}
}
Z=Pop( );

return Z;
}

[arne]

yes, I need to read the last line in my input file, and with that line if I have an "a" I need to make a copy of the first circular list and after that push it into the stack I have this fuction but not working think because i need a pointer or something

Hmm. As far as I understand, you don't need to make a copy of the list and push it on the stack. Just push pointers (or even symbols!) on the stack. Suppose the last line, i.e. the postfix expression, looks like

a b U

This means

push a on the stack
push b on the stack
unite, i.e. pop the top element from the stack, pop the top element from the stack (2 times!) and unite it.
push the result on the stack.

It is sufficient to push the symbol/pointer on the stack and to get the list content if you really need it, i.e. for the unite operation. Hence, for every operation you need a function which receives one or two symbols/pointers (the two symbols a and b in our example), fetches the list(s) contents from the array and performs the oeration. Afterwards the result has to be pushed on the stack. For this temporary result you need an additional list (and symbol/pointer!).

So, you don't have to push copies of the list on the stack, just pointers or symbols. This is much more efficient. Consider the example:

a a a a a a a ...

you would make several copies of the list a, but if you only use the pointer/symbol you save a lot of space and lose no information. You know what I mean?

[saraSS]

yes I know what you mean but I dont know how to do the pointer part I have tried some thing like
ListClass ListA[arraysize],*L; and this ListClass ListA[arraysize],*L[arraysize];

but nothing works pointing to every set is my problem

[arne]

yes I know what you mean but I dont know how to do the pointer part I have tried some thing like
ListClass ListA[arraysize],*L; and this ListClass ListA[arraysize],*L[arraysize];

but nothing works pointing to every set is my problem

I am not sure what you're trying to do here. The ListA is the array for the circular lists? What about the stack? Do you try to use the STL stack?

Can you explain that in more detail?

[saraSS]

I think I got the pointer part working but now looks like I'm not reading the last line of my input file (last line is the one with the expression)to do the evaluation

int main()
{
int i,m;
char postfix[80];
cin>>arraysize;
ListClass ListA[arraysize];


for(i=0;i<arraysize;i++)
{
while(cin>>number && number!=-1)
{
ListA[i].InsertRear(number);
}
cout<<ListA[i].NumItems()<<" ";
ListA[i].printing();
cout<<endl;
}
Initialize ( );
cin.getline(postfix,80);
cout<<postfix<<endl;
Evaluate(ListA,postfix);

return 0;
}

what I'm doing wrong think my while loop is using all the lines ?
idont know

[arne]

I think I got the pointer part working but now looks like I'm not reading the last line of my input file (last line is the one with the expression)to do the evaluation

int main()
{
int i,m;
char postfix[80];
cin>>arraysize;
ListClass ListA[arraysize];


for(i=0;i<arraysize;i++)
{
while(cin>>number && number!=-1)
{
ListA[i].InsertRear(number);
}
cout<<ListA[i].NumItems()<<" ";
ListA[i].printing();
cout<<endl;
}
Initialize ( );
cin.getline(postfix,80);
cout<<postfix<<endl;
Evaluate(ListA,postfix);

return 0;
}

what I'm doing wrong think my while loop is using all the lines ?
idont know

Looks ok to me .. what does the line

cout<<postfix<<endl;
 

write to standard out?

[saraSS]

it just give me a blank line and yes I have the standar out
using namespace std;

[saraSS]

and when I do l=strlen(postfix); I got a zero

[saraSS]

should I read letter by letter maybe?

[saraSS]

got it thanks

[arne]

got it thanks

What was the problem in the end?

[saraSS]

I replace this line
cin.getline(postfix,80,'\n');
for
cin>>postfix;
cout<<postfix<<endl;
actually easier but I dont know why I was getting confuse and trying to do something different but did not work so I stick with the easy way ;)

[saraSS]

how can I compare the two list ? if I'm only passing the pointers ?

[arne]

how can I compare the two list ? if I'm only passing the pointers ?

Do you mean how to access the list elements?

Or do you mean how to compare two data sets (lists) in general?

[saraSS]

I mean in general because I'm passing the pointers of the two list and I want to compare and make a union but dont know how I have something like this

ListNodePtr list_union(ListNodePtr a,ListNodePtr b)
{
ListClass *c;
int k=0;
bool e;
int i,j;
while(a[i]!=0)
{
e=true;
while(b[j]!=0)
{
if(a[i]==b[j])
e=false;
}
if(e)
{
c->Info=a->Info;
}
}
for(i=0;i<a.counter;i++)
{
c.arr[k]=a.arr[i];
k++;
}
c->NumItems()=k;
return c;
}

[arne]

I mean in general because I'm passing the pointers of the two list and I want to compare and make a union but dont know how I have something like this

ListNodePtr list_union(ListNodePtr a,ListNodePtr b)
{
ListClass *c;
int k=0;
bool e;
int i,j;
while(a[i]!=0)
{
e=true;
while(b[j]!=0)
{
if(a[i]==b[j])
e=false;
}
if(e)
{
c->Info=a->Info;
}
}
for(i=0;i<a.counter;i++)
{
c.arr[k]=a.arr[i];
k++;
}
c->NumItems()=k;
return c;
}

Hmm. It's not so easy to comment as I do not see the whole code, but I think your code will not work, since you don't allocate memory for your result list, you just define a pointer. And what is a[i]? 'a' is a pointer to a list node, but what does a[i] point to?

Generally, there are several ways to join two lists:
- copy one list, go through the other element by element and insert it into the copy if the element is not there (use that the lists are ordered!), or
- concatenate the two lists, sort the result (do you have a sort function for your list?), and remove double elements

And I am sure there are even more efficient ways, but you may start with the copy and insert approach. It's the most straightforward.

Once you have one of the list operations working, the others will be easy for you :)