CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7
  1. #1
    Join Date
    Oct 2017
    Posts
    2

    Doubly linked list that canstore objects of different classes in polymorphic hirarchy

    hey guys! we have been given an assignment in our data structures and algorithms subject in c++ language..the question is:
    Create a doubly linked list that can store objects of different shapes such as
    Circle
    Rectangle
    Triangle
    Note: you must implement all the classes as an inheritance hierarchy with a common parent class.

    The linked list should have the following functions
    i. Traverse/draw all shape objects in the linked list.
    ii. Insert a new item at the head, tail.
    iii. Insert a new item at a given location in the linked list.
    iv. Search an object based on its class type.
    v. Delete item at head, tail and with a given key value.

    i have created Doubly linked list to store integers etc, but storing objects as in this question is new for me and i am working on it for the whole weekend but still not very good results for me..any help in this regard will be appreciated..thanks.

  2. #2
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: Doubly linked list that canstore objects of different classes in polymorphic hira

    [Thread moved]
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  3. #3
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: Doubly linked list that canstore objects of different classes in polymorphic hira

    still not very good results for me
    Could you post the code you have so far.

    Do you have something like a base class of shape with virtual function methods and circle, rectangle, triangle etc classes derived from shape? Are you storing a pointer to the base class in the list?
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  4. #4
    Join Date
    Feb 2017
    Posts
    677

    Re: Doubly linked list that canstore objects of different classes in polymorphic hira

    Quote Originally Posted by Chronic View Post
    have created Doubly linked list to store integers etc, but storing objects
    If you can store integers you're close.

    Since the objects are polymorphic you cannot copy them (due to so called object slicing). The implication is that you cannot store the objects directly in your list but must instead store pointers to the objects (because pointers aren't sliced). This would be the case also if you used some data structure from the C++ standard library for example std::list.

    Say you have this inheritance hierarchy,

    Code:
    class Shape { // parent base class 
    public:
        virtual ~Shape() = default; // destructor should be virtual in base class
    
          // declarations of pure virtual functions, like say
        virtual void hello() =0;
    };
    
    class Circle : public Shape { // derived child class
    private: // hidden implementation (access via Circle pointer is not possible, only via Shape pointer)
           // implementations of the pure virtual functions of Shape, like say
        void hello() override {
            std::cout << "I'm a Circle" << std::endl;
        }
    };
    
    class Rectangle : public Shape { // derived child class
    public: // visible implementation (access via both Rectangle pointer and Shape pointer is possible)
        void hello() override {
            std::cout << "I'm a Rectangle" << std::endl;
        }
    };
    With that hierarchy in place you now replace all declarations of the integer you currently use to store data in your list with declarations of pointer to the polymorphic parent class. That is you replace int with Shape* where applicable.

    Before storing a derived child object you need to instantiate it dynamically using new (meaning at some later point when it's no longer anywhere in use you must delete it using delete), like say

    Code:
    Circle* c = new Circle(); // dynamic instantiation of a Circle object and assignment to a Circle pointer
    //
    Shape* s = c; // implicit upcast possible since a Circle is also a Shape (downcast not typesafe so must be explicit)
    The c pointer (or alternatively the s pointer) can now be stored in your list.

    That's it basically. The code can be generalized using templates and the handling of the pointers can be made more safe by the introduction of std::shared_ptr but that's for another exercise.
    Last edited by wolle; October 23rd, 2017 at 04:20 AM.

  5. #5
    Join Date
    Oct 2017
    Posts
    2

    Re: Doubly linked list that canstore objects of different classes in polymorphic hira

    guys i have done pretty much all the things for the first part now it comes to add nodes at start ,end and at a given position then searching according to the shape type etc. i am attaching the code till now..any help to these functions will be appreciated..http://forums.codeguru.com/images/smilies/smile.gif

    Code:
    #include<iostream>
    using namespace std;
    class shape
    {
        public:
              void virtual draw()=0;
              void virtual display()=0;
              shape *next;
              shape *prev;
    };
       class circle: public shape
       {
    private:
        float radius;
        float area;
    public:
        void draw()
        {
           while(1)
    	   {
    	     cout<<endl<<"Enter the Radius"<<endl;
              cin>> radius;
              
              area=2*3.14*radius;
              
           		if(radius<0)
           		  {
                 	cout<<endl<<"radius can't be negative: ";
           		  }	
           	    else
           		  {
        	   	  return;
    		      }
          }
    }
        void display()
        {
          cout<<"\nThe area of the circle is:"<<area;
                }  
    };
     class rectangle: public circle
       {
       private:
        int length;
        int width;
        int area;
       public:
          void draw()
          {
              cout<<" Enter the length of the rectangle: ";
              cin>>length;
              cout<<endl<<"Enter the width of the rectangle: ";
              cin>>width;
              area=length*width;
              if(length <0 || width <0)
              {
    
                  cout<<"Length and width ca't be zero";
              }
          }
          void display()
          {
          	cout<<"The area of the rectangle is:"<<area;
          }
       };
       class triangle : public shape
       {
       private:
        int s1;
        int s2;
        int area;
       public:
       	triangle(){
       		s1=0;s2=0;area=0;
    	   }
         void draw()
         {
             cout<<"\nEnter one side of the tringle: ";
             cin>>s1;
             cout<<"\nEnter the second one side of the triangle:  ";
             cin>>s2;
             area=0.5*(s1*s2);
             if(s1<0||s2<0)
             cout<<"\nSide can't be less than zero: ";
         }
         void display()
         {
         	cout<<"The area of the Triangle is"<<area;
         }
    
        };
    class list
    {
    	private:
    		shape *head;
    		shape *current;
    	public:
    	 void insertshape()
    	     {  
    	        int ch;
    	        shape *ptr;
    	        cout<<"Enter your choice: \n1. circle \n2.tringle 3.\n rectangle";
                 cin>>ch;
                 switch(ch)
                 {
                 	case 1:
                 			{
    						 circle *c1 = new circle();
    	                     ptr = c1;
    	                    break;
    						}
    	            case 2:       {
    				       triangle *t1 = new triangle();
    				       ptr = t1;
    			           break;
    					   }
    			    case 3:{
    			    	rectangle *rec1 = new rectangle();
    			    	ptr = rec1;
    			    	break;
    					}
    			    default:{
    				   cout<<"\nInput is not correct please try again later !!!!!";
    				   return;
    				   }		 
    			 }
    		 	ptr->draw();
    	     	ptr->next = NULL;
    	     	ptr->prev = NULL ;
    	     	if(head == NULL)
    	     	 {
    	     	 	head = current = ptr;
    			 }
    			 else
    			 {
    			 	current->next = ptr;
    			 	ptr->prev = current;
    			 	current = ptr;
    			 }
    		 }	
    		 
    		 void insert_at_start(){
    		 	
    		 	
    		 	
    		 	int ch;
    	        shape *ptr;
    	        cout<<"Enter your choice: \n1. circle \n2.tringle 3.\n rectangle";
                 cin>>ch;
                 switch(ch)
                 {
                 	case 1:
                 			{
    						 circle *c1 = new circle();
    	                     ptr = c1;
    	                    break;
    						}
    	            case 2:       {
    				       triangle *t1 = new triangle();
    				       ptr = t1;
    			           break;
    					   }
    			    case 3:{
    			    	rectangle *rec1 = new rectangle();
    			    	ptr = rec1;
    			    	break;
    					}
    			    default:{
    				   cout<<"\nInput is not correct please try again later !!!!!";
    				   return;
    				   }		 
    			 }
    		 	ptr->draw();
    	     	ptr->next = NULL;
    	     	ptr->prev = NULL ;
    	     	if(head == NULL)
    	     	 {
    	     	 	head = current = ptr;
    			 }
    			 else
    			 {
    			 	current->next = ptr;
    			 	ptr->prev = NULL;
    			 	current = head;
    			 }
    		 }	
    		 	
    		 
    		 
    		 
    		 
    		 void insert_at_last(){
    		 	
    		 	
    		 }
    		 
    		 
    		 void insert_at_point(){
    		 	
    		 	
    		 }
    		 
    		 void search(){
    		 	
    		 	
    		 }
    		 
    		 void deletenode_at_head(){
    		 	
    		 	
    		 }
    		 
    		 
    		 void deletenode_at_tail(){
    		 	
    		 	
    		 }
    		 
    		 
    		 void deletenode_at_point(){
    		 	
    		 	
    		 }
    		 
    		 
    		void display()
    		{
    		   shape *newshape;
    		   newshape = head;
    		   while( newshape != NULL)
    		   {
    		   	newshape->display();
    		   	newshape = newshape->next;
    		   }
    		} 
    };
    	int main()
    {
    		list *li = new list();
    	//	li->insertshape();
    		li->insert_at_start();
    		li->insert_at_start();
        	li->display();
        	return 0;
    }
    Attached Files Attached Files
    Last edited by 2kaud; October 23rd, 2017 at 04:08 PM.

  6. #6
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: Doubly linked list that canstore objects of different classes in polymorphic hira

    Displaying and obtaining input would usually not be part of the class, but as part of the code that uses the class - in this case main. The same with insertshape. Most of that would be outside of the class with insertatstart, insertatlast etc taking a pointer to shape. Why do you have next and prev in shape? The nodes of the list have next, prev and a pointer to shape. Where is the definition of a node? Why are you deriving rectangle from circle?

    Consider

    Code:
    #include <iostream>
    #include <vector>
    using namespace std;
    
    class shape
    {
    public:
    	void virtual display() = 0;
    };
    
    class circle : public shape
    {
    private:
    	float radius;
    	float area;
    public:
    	circle(float rad) : radius(rad), area(2 * 3.14 * rad) {}
    
    	void display() override
    	{
    		cout << "The area of a circle of radius " << radius << " is " << area << endl;
    	}
    };
    
    class rectangle : public shape
    {
    private:
    	int length;
    	int width;
    	int area;
    public:
    	rectangle(int len, int wid) : length(len), width(wid), area(len * wid) {}
    
    	void display() override
    	{
    		cout << "The area of a rectangle of sides " << length << " and " << width << " is " << area << endl;
    	}
    };
    
    class triangle : public shape
    {
    private:
    	int base;
    	int height;
    	float area;
    public:
    	triangle(int bas, int hgt) : base(bas), height(hgt), area(bas * hgt * .5) {}
    
    	void display() override
    	{
    		cout << "The area of a triangle of side " << base << " and height " << height << " is " << area << endl;
    	}
    };
    
    int main()
    {
    	vector<shape*> vs;
    	shape* c1 = new circle(2.0);
    	shape* r1 = new rectangle(3, 4);
    	shape* t1 = new triangle(4, 5);
    
    	vs.emplace_back(c1);
    	vs.emplace_back(r1);
    	vs.emplace_back(t1);
    
    	for (const auto& v : vs)
    		v->display();
    }
    This uses a vector instead of a list, but it shows the use of the polymorphic classes. This displays

    Code:
    The area of a circle of radius 2 is 12.56
    The area of a rectangle of sides 3 and 4 is 12
    The area of a triangle of side 4 and height 5 is 10
    Now you need a node that has its data as shape* with next and prev links and a list class that creates and manipulates a list of nodes.

    i have created Doubly linked list to store integers etc,
    Did this list use a node structure? If it did then to change it from storing int to storing shape* is easy.
    Last edited by 2kaud; October 23rd, 2017 at 04:46 PM.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  7. #7
    Join Date
    Feb 2017
    Posts
    677

    Re: Doubly linked list that canstore objects of different classes in polymorphic hira

    In my previous reply (post #4) I was under the impression that you had already developed a linked list to store ints. In a classic implementation the list would consist of linked nodes that would look something like this,

    Code:
    class Node {
    public:
        int data; // modify to store other kinds of data in the list
        Node *next; 
        Node *prev;
    };
    With that in place you would only need to replace the int with Shape* like this,

    Code:
    class Node {
    public:
        Shape* data;
        Node *next; 
        Node *prev;
    };
    and of course also modify the rest of the linked list code to be consistent with that change.

    But note that technically there's nothing wrong with your approach (to tie the Shape base class to the implementation of the list by letting it hold the next and prev pointers). It will work but this kind of design is called intrusive and generally avoided.
    Last edited by wolle; October 24th, 2017 at 02:05 AM.

Posting Permissions

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





Click Here to Expand Forum to Full Width

Featured