A task involving linked lists and a headache
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 3 123 LastLast
Results 1 to 15 of 33

Thread: A task involving linked lists and a headache

Hybrid View

  1. #1
    Join Date
    Sep 2012
    Posts
    11

    Question A task involving linked lists and a headache

    Hi everyone around here, im new and im hopint to give and get help
    The task is to create a linked list consisting of bunny's, the bunny is a class.
    Im having problems in managing the list itself. I have doubts about the Delete() function in the list, is it correct?
    When the bunnies reach 10 years, they should die, that means, that the first 5 bunnies should die all tohether, but they dont, 3 of them do, the other 2 die each the following 2 years. The 2 survivors dont age when the 3 die, but they should. [Bolded]
    Objects are added in the back of the list, so that Head points to the very first element. The OutOfFood() function is doing nothing but harm, although it should work. Kills half of them, and then just keeps killing... If they are a lot of them, then it even prints, that nameless or completely all-less bunnies are killed.
    Ive noticed, that sometimes, so bunnies are created without something (Color, Name etc.).
    Sorry for the long post, the code seems a mess and i dont know where even to start cheking.
    Thanks in advance!

    Code:
    #include <iostream>
    #include <time.h>
    #include <string>
    
    using namespace std;
    
    char *Names[15]={"Phill","Colin","Bucket","Fluffy","Mister","Lilly","Rose","Shamandale","Yoshie","Jane","PeanutButter","Plank","Sucubus","Broken","Horse ****"};
    
    class Bunny
    {
    public:
    	string Sex;
    	string Color;
    	int Age;
    	string Name;
    	bool Mutant;
    
    	Bunny *Next;
    
    	int Random(int x)
    	{
    		return x=rand()%(x+1);
    	}
    	
    	bool MutantBunny()
    	{
    		int X=Random(100);
    		if(X<2)
    		{
    			return true;
    		}
    		return false;
    	}
    
    	string SexIsNotAChoise()
    	{
    		int R=Random(10);
    		if(R<5)
    		{
    			Sex="Male";
    		}
    		else
    		{
    			Sex="Female";
    		}
    		return Sex;
    	}
    
    	string HopeImNotBlack()
    	{
    		int R=Random(100);
    		if(R<24)
    		{
    			Color="White";
    		}
    		else if(R>24 && R<=49)
    		{
    			Color="Brown";
    		}
    		else if(R>50 && R<=75)
    		{
    			Color="Black";
    		}
    		else if(R>76)
    		{
    			Color="Spotted";
    		}
    		return Color;
    	}
    
    	int ImNotOld()
    	{
    		Age=0;
    		return Age;
    	}
    
    	string HelloMyNameIs()
    	{
    		if(Mutant==true)
    		{
    			Name=Names[rand()%(14-10)+10];
    		}
    		else if(Sex=="Male")
    		{
    			Name=Names[rand()%5];
    		}
    		else if(Sex=="Female")
    		{
    			Name=Names[rand()%(9-5)+5];
    		}
    		return Name;
    	}
    
    	Bunny()
    	{
    		Mutant=MutantBunny();
    		if(Mutant==true)
    		{
    			Sex=SexIsNotAChoise();
    			Color="Green";
    			Age=ImNotOld();
    			Name=HelloMyNameIs();
    		}
    		else if(Mutant==false)
    		{
    			Sex=SexIsNotAChoise();
    			Color=HopeImNotBlack();
    			Age=ImNotOld();
    			Name=HelloMyNameIs();
    		}
    		
    	}
    
    	void print()
    	{
    		cout<<"Bunny "<<Name<<" was born!";
    		if(Mutant==true)
    		{
    			cout<<" He's a mutant..!"<<endl;
    		}
    		else
    		{
    			cout<<endl;
    		}
    	}
    
    	~Bunny()
    	{
    		cout<<"A bunny with the name "<<Name<<" has died!"<<endl;
    	}
    
    };
    
    class BunnyList
    {
    private:
    	int size;
    public:
    	Bunny *Head;
    
    	BunnyList()
    	{
    		size=0;
    		Head=NULL;
    	}
    
    	int Count()
    	{
    		return size;
    	}
    
    	int AddBunny(Bunny* NewBunny)
    	{
    		if(Head==NULL)
    		{
    			Bunny *Temp=new Bunny;
    			Temp=NewBunny;
    			Temp->Next=Head;
    			Head=Temp;
    			return ++size;
    		}
    		else
    		{
    			Bunny *Current=new Bunny;
    			Current=Head;
    			while(Current->Next!=NULL) 
    			{
    				Current=Current->Next;
    			}
    			Current->Next=NewBunny; 
    			NewBunny->Next=NULL;
    			return ++size;
    		}
    	}
    
    	Bunny *GetBunny(int Pos)
    	{
    		Bunny *Current=Head;
    		for(int i=1;i<Pos && Current!=NULL;i++)
    		{
    			Current=Current->Next;
    		}
    		return Current;
    	}
    
    	bool Delete(int Pos)
    	{
    		if(GetBunny(Pos)==NULL)
    		{
    			return false;
    		}
    		else
    		{
    			if(Pos==1)
    			{
    				Bunny *Temp=Head->Next;
    				Head=Temp;
    				size--;
    				return true;
    			}
    			else
    			{
    				GetBunny(Pos-1)->Next=GetBunny(Pos+1);
    				size--;
    			}
    			return true;
    		}
    	}
    
    	int MutantCheck()
    	{
    		int MutantCount=0;
    		for(int i=1;i<Count() && GetBunny(i)!=NULL;i++)
    		{
    			if(GetBunny(i)->Mutant==true)
    			{
    				MutantCount++;
    			}
    		}
    		return MutantCount;
    	}
    
    	int Male()
    	{
    		int M=0;
    		for(int i=1;i<Count()+1 && GetBunny(i)!=NULL;i++)
    		{
    			if(GetBunny(i)->Sex=="Male" && GetBunny(i)->Age>2)
    			{
    				M++;
    			}
    		}
    		return M;
    	}
    
    	int Female()
    	{
    		int F=0;
    		for(int i=1;i<Count()+1 && GetBunny(i)!=NULL;i++)
    		{
    			if(GetBunny(i)->Sex=="Female" && GetBunny(i)->Age>2)
    			{
    				F++;
    			}
    		}
    		return F;
    	}
    
    	bool WeWillMate()
    	{
    		int M=Male(),F=Female();
    		if(M>=1 && F>=1)
    		{
    			return true;
    		}
    		else
    		{
    			return false;
    		}
    	}
    
    	void OutOfFood()
    	{
    		if(Count()>100)
    		{
    			int k=Count()/2;
    			for(int i=0;i<k;i++)
    			{
    				int z=rand()%k;
    				if(GetBunny(z)!=NULL)
    				{
    					GetBunny(z)->~Bunny();
    					Delete(z);
    				}
    				else
    				{
    					do{
    						z=rand()%k;
    					}
    					while(GetBunny(z)!=NULL);
    					GetBunny(z)->~Bunny();
    					Delete(z);
    				}
    				 
    			}
    		}
    	}
    
    };
    
    void PrintTheHorde(BunnyList* List)
    {
    		cout<<"The Horde consists of "<<List->Count()<<" bunnies, here they are: "<<endl;
    		cout<<endl;
    		for(int i=1;i<List->Count()+1 && List->GetBunny(i)!=NULL;i++)
    		{
    				Bunny *Temp=List->GetBunny(i);
    				cout<<"Name: "<<Temp->Name<<" Sex: "<<Temp->Sex<<" Age: "<<Temp->Age<<" Color: "<<Temp->Color;
    				if((Temp->Mutant)==true)
    				{
    					cout<<" Im a Mutant.."<<endl;
    				}
    				else if((Temp->Mutant)==false)
    				{
    					cout<<endl;
    				}
    
    		}
    }
    
    int main()
    {
    	srand(time(NULL));
    	BunnyList *List=new BunnyList;
    
    	for(int i=0;i<5;i++)
    	{
    		Bunny *NewBunny=new Bunny();
    		List->AddBunny(NewBunny);
    		NewBunny->print();
    	}
    
    	while(List->Count()>0)
    	{
    		for(int i=1;i<List->Count()+1 && List->GetBunny(i)!=NULL;i++)
    			{
    				Bunny *Temp=new Bunny;
    				Temp=List->GetBunny(i);
    				Temp->Age++;
    				if(Temp->Age>10)
    				{
    					Temp->~Bunny();
    					List->Delete(i);
    				}
    			}
    
    		bool C=List->WeWillMate();
    		if(C==true)
    		{
    			int k=List->Female();
    			for(int i=0;i<k;i++)
    			{
    				Bunny *NewBunny=new Bunny();
    				List->AddBunny(NewBunny);
    				NewBunny->print();
    			}
    		}
    		List->OutOfFood();
    		PrintTheHorde(List);
    		int m=List->Male(),f=List->Female();
    		cout<<"Adult males: "<<m<<endl;
    		cout<<"Adult females: "<<f<<endl;
    		cout<<"The Horde consists of "<<List->Count()<<" bunnies! "<<endl;
    		system("pause");
    		system("cls");
    	}
    	return getchar();
    }

  2. #2
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,055

    Re: A task involving linked lists and a headache

    So, I did what you should be doing, stepping through your code using the debugger and ran into problems right away. The first big issue is AddBunny.
    Code:
    	int AddBunny(Bunny* NewBunny)
    	{
    		if(Head==NULL)
    		{
    			Bunny *Temp=new Bunny;
    			Temp=NewBunny;
    			Temp->Next=Head;
    			Head=Temp;
    			return ++size;
    		}
    You're passing in a Bunny*, but ignoring it and creating a new Bunny. You should just use the pointer you passed in. Also, you're setting next to head. That's a mistake too. Next in the last node should point to NULL.

    From a design point of view, your list class should have a node class or struct that has the Bunny* as a member, and handles the next pointer. It's bad design to have the Bunny class contain the next pointer.

    I would imagine there are lots more problems, but when writing code, you need to write small chunks, debug them and make sure they're working, then move on to the next piece. When you try to write it all at once, you end up with a huge mess. Get the list class properly designed, get the AddBunny function working properly, then move on and debug it piece by piece.

  3. #3
    Join Date
    Sep 2012
    Posts
    11

    Re: A task involving linked lists and a headache

    Thank you for your reply and advice Will tear this mess down peace by peace and learn to debug. I got the idea how to write the add function from a tutorial, guess it was wrong or i miss understood something and that propably means i might have some other mistakes..

  4. #4
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,055

    Re: A task involving linked lists and a headache

    Another thing, never under any circumstances call a destructor directly. Use delete and the destructor is called for you.

  5. #5
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,699

    Re: A task involving linked lists and a headache

    Im having problems in managing the list itself.
    Trying to figure out the steps needed to manage the head/tail/next/previous pointers for all the operations for a linked list can get a little mind boggling after a while.
    My choice for solving problems like this is the draw the sequence of steps that are needed for each operation (Add, Delete, Insert), with lines showing where each pointer points to at each step. Otherwise it's easy to get yourself in a muddle.
    "It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
    Richard P. Feynman

  6. #6
    Join Date
    Apr 1999
    Posts
    27,423

    Re: A task involving linked lists and a headache

    Quote Originally Posted by MustSeeMelons View Post
    I got the idea how to write the add function from a tutorial,
    That is the wrong approach. No tutorial, unless it is geared towards a definite aspect of an application, is going to write the program for you.

    If you are to look at source code, then it should only be used to see how "programmer x" implemented a linked list. What "programmer x" did may not even look like or fit the requirements that you're looking for. What if that programmer implemented a template-based, STL-like linked list, complete with iterators, etc? Are you going to blindly copy the code or copy major portions of it? Of course not.

    Googling or web searching for the exact code that fits what you're doing is a waste of time and energy, when that time could have been spent writing the program. It's better you learn what a linked list is, and based on that learning, create the program yourself.

    You should have had a data structures textbook describing what a linked list is -- it's your job to then take the description of the linked list and create a program that manages a linked list.

    Regards,

    Paul McKenzie

  7. #7
    Join Date
    Sep 2012
    Posts
    11

    Re: A task involving linked lists and a headache

    @JohnW@Wessex
    Thats what I am going to do, cant put everything together in my head.

    @Paul McKenzie
    Thanks for the post. I learned what a linked list is from tutorials, I went through 3 if i remmember corectly, but I didnt just plain copy the code, i tried to undesrstand and by what i learnt i made this mess. I know that copying gets you nowhere, i try to understand what and why i am writing something.
    Reading just the description in not always enough, especially[did google check this word] if you dont have much experiance.

    @GCDEF
    Could you please explain this? I cant wrap my head around the idea..
    "From a design point of view, your list class should have a node class or struct that has the Bunny* as a member, and handles the next pointer. It's bad design to have the Bunny class contain the next pointer."

  8. #8
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,055

    Re: A task involving linked lists and a headache

    Quote Originally Posted by MustSeeMelons View Post
    @GCDEF
    Could you please explain this? I cant wrap my head around the idea..
    "From a design point of view, your list class should have a node class or struct that has the Bunny* as a member, and handles the next pointer. It's bad design to have the Bunny class contain the next pointer."
    You need another class or struct to make up the elements of your list. For example
    Code:
    struct BunnyListNode
    {
        BunnyListNode* pNext;
        BunnyListNode* pPrev;// if you want doubly linked
        Bunny* pBunny;
    };
    That way you've decoupled the concepts of your Bunny class and the container that holds them. When you call AddBunny, you'd create a new BunnyListNode and set pBunny to point to the Bunny that node is containing, and set the BunnyListNode pointers instead of having your Bunny class responsible for its position in the list.

  9. #9
    Join Date
    Aug 2009
    Posts
    439

    Re: A task involving linked lists and a headache

    What GCDEF is referring to is to have a struct:
    Code:
    struct Node
    {
        MyClass data;
        Node *next;   //points to next node in the list
    };
    You then will use these nodes in your linked list class.

  10. #10
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,055

    Re: A task involving linked lists and a headache

    Quote Originally Posted by Alterah View Post
    What GCDEF is referring to is to have a struct:
    Code:
    struct Node
    {
        MyClass data;
        Node *next;   //points to next node in the list
    };
    You then will use these nodes in your linked list class.
    data would typically be a pointer to MyClass though.

  11. #11
    Join Date
    Aug 2009
    Posts
    439

    Re: A task involving linked lists and a headache

    Quote Originally Posted by GCDEF View Post
    data would typically be a pointer to MyClass though.
    Is the reason to decrease the size of the nodes? Most examples don't have data as a pointer, but then again, most examples use primitives for the data.

  12. #12
    Join Date
    Sep 2012
    Posts
    11

    Re: A task involving linked lists and a headache

    Well ok, thanks, understood the idea. When i create a new bunny, i create a struct inside, that has the information about the bunnies location and its neighbours. The bunny itself now is just data and has nothing to do with the list itself.
    Could you try explaining why my method was inferior? Unless my previous sentence is the reason.

  13. #13
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,055

    Re: A task involving linked lists and a headache

    I don't really understand your previous sentence. You create a struct inside what?

    Whenever possible you should decouple classes as much as possible. There's no reason Bunny should know anything about the list, or any other container that may hold them. When you're working with Bunny objects, you shouldn't have to be concerned with whether they're members of a list, and if you change the implementation of your list, you shouldn't have to change your Bunny class to accommodate it. While it's not always possible, good design dictates that you reduce inter-dependencies among classes as much as possible.

  14. #14
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,055

    Re: A task involving linked lists and a headache

    It's so that the list can store the actual object, not a copy of it, and again, it decouples the class from its container. If the list contains an actual object, that that object only exists as long as the list node exists, and that's not necessarily desirable behavior.

  15. #15
    Join Date
    Sep 2012
    Posts
    11

    Re: A task involving linked lists and a headache

    Dont have much time, but i have done some changes, created another class that handles the bunnies in the list. The sad parts is that nothing has changed :| If i create 5 bunnies and then delete with a simple cycle (Bold), all is whel, they are deleted, but if i make a cycle with aging (Bold), 2 of them are still not deleted.. Whats wrong with the cycle?

    Another, possibly dumb, question:
    Code:
    for(int i=1;i<List->Count()+1 && List->GetBunnyInList(i)!=NULL;i++)
    When the cycle goes through, does it recalculate List->Count()?

    Thanks!


    Code:
    class BunnyInList
    	{
    	public:
    		BunnyInList *Next;
    		Bunny *Cur;
    	};
    
    class BunnyList
    {
    public:
    	
    	BunnyInList *Head;
    	int size;
    
    	BunnyList()
    	{
    		Head=NULL;
    		size=0;
    	}
    
    	int Count()
    	{
    		return size;
    	}
    
    	int Add(Bunny* NewBunny)
    	{
    		BunnyInList *InList= new BunnyInList;
    		if(Head==NULL)
    		{
    			InList->Cur=NewBunny;
    			InList->Next=Head;
    			Head=InList;
    			return size++;
    		}
    		else
    		{
    			BunnyInList *Current=new BunnyInList;
    			Current=Head;
    			while(Current->Next!=NULL)
    			{
    				Current=Current->Next;
    			}
    			Current->Next=InList;
    			InList->Cur=NewBunny;
    			InList->Next=NULL;
    			return size++;
    
    		}
    	}
    
    	BunnyInList *GetBunnyInList(int Pos)
    	{
    		BunnyInList *Current=Head;
    		for(int i=1;i<Pos && Current!=NULL;i++)
    		{
    			Current=Current->Next;
    		}
    		return Current;
    	}
    
    	bool Delete(int Pos)
    	{
    		if(GetBunnyInList(Pos-1)==NULL)
    		{
    			Head=GetBunnyInList(Pos+1);
    			size--;
    			return true;
    		}
    		else if(GetBunnyInList(Pos+1)==NULL)
    		{
    			GetBunnyInList(Pos-1)->Next=NULL;
    			size--;
    			return true;
    		}
    		else
    		{
    			GetBunnyInList(Pos-1)->Next=GetBunnyInList(Pos+1)->Next;
    			size--;
    			return true;
    		}
    		return false;
    	}
    
    	int MutantCheck()
    	{
    		int MutantCount=0;
    		for(int i=1;i<Count() && GetBunnyInList(i)!=NULL;i++)
    		{
    			if(GetBunnyInList(i)->Cur->Mutant==true)
    			{
    				MutantCount++;
    			}
    		}
    		return MutantCount;
    	}
    
    	int Male()
    	{
    		int M=0;
    		for(int i=1;i<Count()+1 && GetBunnyInList(i)!=NULL;i++)
    		{
    			if(GetBunnyInList(i)->Cur->Sex=="Male" && GetBunnyInList(i)->Cur->Age>2)
    			{
    				M++;
    			}
    		}
    		return M;
    	}
    
    	int Female()
    	{
    		int F=0;
    		for(int i=1;i<Count()+1 && GetBunnyInList(i)!=NULL;i++)
    		{
    			if(GetBunnyInList(i)->Cur->Sex=="Female" && GetBunnyInList(i)->Cur->Age>2)
    			{
    				F++;
    			}
    		}
    		return F;
    	}
    
    	bool WeWillMate()
    	{
    		int M=Male(),F=Female();
    		if(M>=1 && F>=1)
    		{
    			return true;
    		}
    		else
    		{
    			return false;
    		}
    	}
    };
    Code:
    srand(time(NULL));
    	BunnyList *List=new BunnyList;
    	for(int i=0;i<5;i++)
    	{
    		Bunny *NewBunny=new Bunny();
    		List->Add(NewBunny);
    		NewBunny->print();
    	}
    	PrintTheHorde(List);
    
    	for(int i=1;i<6;i++)
    	{
    		List->Delete(i);
    	}
    
    	while(List->Count()>0)
    	{
    		for(int i=1;i<List->Count()+1 && List->GetBunnyInList(i)!=NULL;i++)
    			{
    				BunnyInList *Temp=new BunnyInList;
    				Temp=List->GetBunnyInList(i);
    				if(Temp->Cur->Age>=10)
    				{
    					List->Delete(i);
    				}
    				Temp->Cur->Age++;
    				cout<<List->Count()<<endl;
    			}

Page 1 of 3 123 LastLast

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center