Linked list

Pages: 12
Hi, I am working through the graduation problem on this page - http://www.cplusplus.com/forum/articles/12974/. However I am having two issues at the moment. Firstly I cannot compare two bunny objects. I think that I need to override the '=' operator in order to do this? Secondly I also want to display the colour of the rabbit in its enumerated form rather than its integer value. Is there a quick way of doing this?

enum and Bunny class
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
enum colour{
    white = 0,
    brown,
    black,
    spotted
};

class Bunny{
private:
    bool isMale;
    colour appearance;
    unsigned int age;
    std::string name;
    bool radioactive_mutant_vampire_bunny;
public:
    Bunny();
    std::string GetIsMale();
    colour GetColour();
    int GetAge();
    std::string GetName();
    std::string GetVampire();
};


Linked list class
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class List{
private:
    typedef struct node{
        Bunny data;
        node *next;
    }* nodePtr;
    
    nodePtr head;
    nodePtr curr;
    nodePtr temp;
public:
    List();
    void AddNode(Bunny addData);
    void DeleteNode(Bunny delData);
    void PrintList();
};


Delete node function that causes the error when comparing the data in the linked list when compared to the data passed to the function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void List::DeleteNode(Bunny delData){
    nodePtr delPtr = NULL;
    temp = head;
    curr = head;
    while(curr != NULL && curr->data != delData){
        temp = curr;
        curr = curr->next;
    }
    if (curr == NULL){
        std::cout<<"Could not delete Bunny check DeleteNode.\n";
        delete delPtr;
    }
    else{
        delPtr = curr;
        curr->next;
        temp->next = curr;
        if (delPtr == head){
            head = head->next;
            temp = NULL;
        }
        delete delPtr;
        std::cout<<"Bunny "<< delData.GetName()<<" died :(\n";
    }
}


Thanks.
You have to overload the '!=' operator, because that is what you are doing @line 5 of your List's code. There are plenty of places to find info about how to do this.

You could also change line 5 to something like:
1
2
while (curr != NULL && curr->data.GetName() != delData.GetName() &&
       curr->data.GetAge() != delData.GetAge() /* ... */)


But you should overload the operator instead.
Last edited on
Thanks. I seems to work correctly now. Any idea on how to convert an integer back into an enumerator? for my get colour function I just return appearance. However this returns its integer value rather than its enumerator value such as white, brown etc. I did a Google search but I was not able to find anything useful.
Are you looking to print the name as a string?
http://www.cplusplus.com/forum/general/2949/

Otherwise, you can still do:
1
2
3
4
5
6
colour bColour = myBunny.getColour();
switch(bColour)
{
case white:  // ...
case brown: ///
}


Enumerator names should be all capital letters because when people read capitals they know they are dealing with a constant.
Last edited on
Thanks. I will give this a shot when I am next on comp
I have encountered a problem with my delete node function. It causes a crash at runtime when deleting a bunny object.

here is the list class:
1
2
3
4
5
6
7
8
9
10
class List{
private:
    typedef struct node{
        Bunny data;
        node *next;
    }* nodePtr;
    
    nodePtr head;
    nodePtr curr;
    nodePtr temp;


here is the delete node function for this class:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void List::DeleteNode(Bunny delData){
    nodePtr delPtr = NULL;
    temp = head;
    curr = head;
    while(curr != NULL && curr->data != delData){
        temp = curr;
        curr = curr->next;
    }
    if (curr == NULL){
        std::cout<<"Could not delete Bunny check DeleteNode.\n";
        delete delPtr;
    }
    else{
        delPtr = curr;
        curr->next;
        temp->next = curr;
        if (delPtr == head){
            head = head->next;
            temp = NULL;
        }
        delete delPtr;
        std::cout<<"Bunny "<< delData.GetName()<<" died :(\n";
    }
}


I presume it has something to do with memory?
Line 11 is a problem. Doesn't line 10 say it can't be deleted?
Line 11 is there just in case for some reason it cannot find the bunny to delete. The problem occurs once the bunny has been removed as I observe line 22 in the console however, I get a run time error. Probably should have made that clear to start with sorry.
Oh yeah. Didn't see it. Try reversing lines 21 and 22.
Surely changing the order won't do anything? as delData and delPtr are unrelated? delData is just used as reference to know which node in the list needs removing.

EDIT:
I have improved the situation on line 16 I have changed it to
temp->next = curr->next;
and removed lie 15. This now displays the correct number of bunny deaths but the runtime error still occurs after the last one.
e.g. before:
Bunny Quin died 
Runtime error

now:
Bunny Quin died
Bunny Ryan died
Bunny Riliey died
Bunny Jeff died
Bunny Tom died
Runtime error.


the correct number die now but I still end up with the runtime error.
Last edited on
I was going to just hide after being caught responding without brain twice. In a row.

But, I've decided to risk a hat trick here.
Honestly, I am getting a bit lost in the currs and temps in your code.
I think the function could be simplified (and perhaps corrected) by treating the head case first explicitly. I have started doing this and it gives some good benifits.
I am adapting from a function which I have tested in a singly linked list of my own. Here it is before adaptation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// returns true if item is found and removed
bool intList::remove_first_of(int Data)
{
    if(head)
    {
        // examine head->data
        if(head->data == Data)
        {
            pop();
            return true;
        }

        // examine list past head
        node* iter = head;
        while(iter->next)// not at list tail yet
        {
            if( iter->next->data == Data )
            {
                node* temp = iter->next;
                iter->next = temp->next;
                delete temp;
                return true;
            }
            iter = iter->next;
        }
    }

    return false;
}// end remove_first_of() 

Here is my untested adaptation for your case, and my potential hat trick.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// returns true if item is found and removed (left this in case you like the idea)
bool List::DeleteNode(Bunny delData)
{
    if(head)
    {
        // examine head->data
        if(head->data == delData)
        {
            node* temp = head;
            head = head->next;
            delete temp;
            std::cout<<"Bunny "<< delData.GetName()<<" died :(\n";
            return true;
        }

        // examine list past head
        node* iter = head;
        while(iter->next)// not at list tail yet
        {
            if( iter->next->data == delData )
            {
                node* temp = iter->next;
                iter->next = iter->next->next;// linking across node to be deleted
                delete temp;
                std::cout<<"Bunny "<< delData.GetName()<<" died :(\n";
                return true;
            }
            iter = iter->next;
        }
    }
    std::cout<<"Could not delete Bunny check DeleteNode.\n";
    return false;
}
I prefer your code as its much much easier on the eye but after adapting it it performs the runtime error before killing all the rabbits. After further debugging the issue seems to occur outside the delete node function but is caused by it.

In the main loop I have a vector<bunny> which I then store all the nodes in through another function to perform any tasks on. I use this vector to identify which bunny node to destroy and pass that object to the delete node function. I then clear the vector and reload the bunny nodes into it to make sure I don't use the deleted bunny. At this reload a runtime error occurs. This error also occurs when I add 1 more year onto the rabbits age at the end of the loop. I know that the increase age function works and so commented out the delete node part of the code and sure it runs ok. Therefore my conclusion is that the delete node function unlinks the list causing errors for every other function.
Last edited on
I don't know. It sounds like there may be some screwy stuff going on there, or I am misinterpreting what you wrote.
In the main loop I have a vector<bunny> which I then store all the nodes in...

Storing nodes in a vector<bunny> ?
The list contains the nodes, and the nodes contain the bunnies. Neither should have separate storage in any vector.

Have you tried testing this way?
1
2
3
4
5
6
7
bunnyList.PrintList();// verify good before 1st deletion
bunnyList.DeleteNode(delData);
PrintList();// still good?
// assign delData to another bunny
bunnyList.DeleteNode(delData);
PrintList();// still good?
// and so on... 
Sorry I temporally store the data at each node in a vector which I then cycle through to compare the data with any conditions I have for example if the rabbit is over 10 years old delete it. I then pass the bunny object from that vector which is 10 years or older to the delete node function in order for it to be removed. Is there a more efficient way of achieving this?

I am away from my computer now until tomorrow so I will take another look then and see if a good nights sleep will help me think more clearly.
Having a data structure in addition to the List is redundant.

Everything that has to do with a List of Bunnies should be done inside the List class.

You have problems when you only have one Node in the list (IE, head->next == null). Line 3 & 4 set temp and curr to head. If there is a head, we reach line 16 (temp->next = curr), in this situation head->next = head. After deleting head, you set it to itself, not to NULL. The Bunny is gone, and will crash the program when you de-refernce it.

You should be able to perform the needed actions directly on the list. Since you are wrapping this in your own list class you are free to write custom functions, such as one to remove all bunnies above a given age from the list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// returns the number of deceased bunnies
int List::Reaper(int maxAge)
{
    if( !head ) return 0;// list is empty

    int deadCount = 0;// return value
    
    // start at head
    while(head->data.GetAge() >= maxAge)
    {
        node* temp = head;
        head = head->next;
        delete temp;
        ++deadCount;
        if( !head ) return deadCount;// all bunnies dead
    }

    // continue to end
    node* iter = head;
    while(iter->next)
    {
        if( iter->next->data.GetAge() >= maxAge )
        {
            node* temp = iter->next;// iter->next will be deleted
            iter->next = iter->next->next;// linking across node to be deleted
            delete temp;
            ++deadCount;
        }
        iter = iter->next;
    }    

    return deadCount;
}


Untested, but I think it may work.
Last edited on
LowestOne: I have decided to restructure the program as it was becoming too dependent on a single function and have decided to go for an approach in which I have a list object in main and call a while loop in which I call all the various functions in list. such as:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
    List population;
    for (int i = 0; i< 5; i++)
        population.AddNode(Bunny());
    
	while(true){
		population.Reaper(1);
		population.AddAge(1);
		population.PrintList();
		cout<<"Press any key to start next turn\n";
		char x = 0;
		cin>>x;
		if (x == '1')
			break;
	}


Before I had:

1
2
3
4
5
6
7
8
	while(true){
		population.loop()
		cout<<"Press any key to start next turn\n";
		char x = 0;
		cin>>x;
		if (x == '1')
			break;
	}


with list::loop containing all my logic. It was becoming too large and messy.

I figured out what is causing the runtime error. It happens when I try to draw the rabbit information to the console once all the rabbits are dead. When I loop over the code however I have a check in place to make sure that if the head is NULLED to output nothing.

fun2code:
Your function works. I suspect now that the one in your previous post did as well, but appeared not to due to printlist(). Here is the print list function. I cannot see what is wrong with it though:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void List::PrintList(){
    curr = head;
	std::cout<<"Bunny List:\n";
	while(curr != NULL){
		std::cout<<"------------------------------\n"; 
		std::cout<<"Name: "<<curr->data.GetName()<<"\n";
		std::cout<<"Age: "<<curr->data.GetAge()<<"\n";
		std::cout<<"Colour: "<<curr->data.GetColour()<<"\n";
		std::cout<<"Gender: "<<curr->data.GetIsMale()<<"\n";
		std::cout<<"Abnormalities: "<<curr->data.GetVampire()<<"\n";
		std::cout<<"------------------------------\n";
		curr = curr->next;
	}
}


It must be this that is causing it because as soon as this function is not called any more it all functions correctly. except for exiting the program.
Last edited on
You have a pointer that is not NULL, but still points to nothing (a Dangling Pointer).

I would hav something like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Bunny
{
  int age;  // initiated to zero
  bool grow() { return ++age < 10; }
};

class BunnyList
{
  void update()
  {
    Node* ptr = head;
    while (ptr)
    {
      if !(ptr->grow()) 
      {
        ptr = deleteNode(ptr); // deletes ptr and returns a valid (or NULL) node 
        continue;
      }
      ptr->move();
      ptr->checkRaditation();
      ptr->///
   
      ptr = ptr->next();
    }
  }
};


I'm afraid the Reaper function is at fault.
Although the original remove_first_of() function I posted appears to be good, the adaptations made from it were not.
Reaper() will crash your program when the last (tail) node is deleted from a list with > 1 node in it.
When the tail node is deleted line 25 results in iter->next = NULL;
line 29 sets up the crash by making iter = NULL;
The crash then occurs at line 20.
Also, a bunny can get skipped over that should be removed from the list.
The fix I have found (working so far) is to change line 29 from:
iter = iter->next;
to
else iter = iter->next;
Sorry about that!

@LowestOne. Interesting approach, compact treatment.
Last edited on
@fun2code
I still receive an error even with adding the else statement. I have decided to link to what I have written on Pastebin (too long to display here) this way any ambiguity is gotten rid of. Thanks for the examples though I have learnt lots on different ways of accomplishing tasks :).

http://pastebin.com/38Qxeue8

@LowestOne

I understand what you are saying conceptually, but I don't think I am quite at that stage in terms of implementing. I really like the compactness of your example though. However I would like to complete it doing it the way I have here - http://pastebin.com/38Qxeue8, as I am more comfortable with this approach. Once I have finished it, I would like to try and re-make it more compact. Thanks for the advice I will definitely look out for things such as dangling pointers in the future.

P.S. You might see some really bad syntax or general practice. If you could alert me to this I would be most grateful as I am a physics undergrad and learning c++ in my spare time, and don't really have access to the computer science department's lecturers to ask them for advice.
Last edited on
Pages: 12