Web Analytics Made Easy -
StatCounter linked list of points - CodingForum

Announcement

Collapse
No announcement yet.

linked list of points

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • linked list of points

    Hi guys I need a little help on solving a problem I'm having with an assignment. What we have to do is make a linked list of points. The program should ask the user to enter as many points as they want then take those points and put them in a linked list and print out the linked list ordered by the x value.

    I have a point class working that will let me plot points at different locations. I also have a linkedList class that I can create linked lists of integers from. I don't know how to get the linked list to hold each seperate point though.

    Im attaching a zip file (4.4kb) that has my point class and linked list class. If anyone could please help me get on the right track that'd be great please. I have looked all over and can't really find any specific help about using a linked list with points.

    I am new at this still, but am trying to learn it I just need some kind of example so I know what to do. Thanks.
    Attached Files

  • #2
    What you would do is make the data that your linked list holds from integers to your point class. The ideal way for the long term would be to make your linked list class templated so it could easily hold any sort of data you wanted. However if you haven't really worked with templates yet, that might not be the best idea for you. I don't have time right now to go over your code otherwise I would of given some more specific advice but that might at least get the ball rolling.
    OracleGuy

    Comment


    • #3
      Yea I figured that, but I don't know how to do it. My linked list is templated, but I'm not sure how to make it hold more than just the basic data types we've been working with like int. I try to change it to my point class, but get there is no valid conversion errors. I'll attach how I tried to do it.
      Attached Files

      Comment


      • #4
        I have the linked list class and the point class made I just need help with the main() where I ask the user to enter as many points as they want then I print the created linked list back to them ordered by the x value. I don't have any sort in yet I was saving that until I can at least get the data from the user and print it. Can anyone please tell me where I am going wrong for implementing what I'm trying to do in main() an example would be most helpful I am still learning. Thanks.

        Comment


        • #5
          Well you need to put the cin where you ask for the points inside the while loop.
          OracleGuy

          Comment


          • #6
            Hey thanks that was a small error that was messing the program up. I have another problem now though. The problem is with the list1.print() in the code. Here is the error I get:

            error C2679: binary '<<' : no operator found which takes a right-hand operand of type 'Point' (or there is no acceptable conversion)


            Here is the code for the print function:

            void print() const;
            //Function to output the data contained in each node.
            //Postcondition: none

            template<class Type>
            void linkedListType<Type>:: print() const
            {
            nodeType<Type> *current; //pointer to traverse the list

            current = first; //set current so that it points to
            //the first node
            while (current != NULL) //while more data to print
            {
            cout << current->info << " ";
            current = current->link;
            }
            }//end print


            I appreciate the help by the way. I was actually closer than I thought I was I think.

            Comment


            • #7
              Basically that means it doesn't know how to apply your class with that operator. You have two options:
              1) Do something like: cout << current->info->PrintPoint() where the PrintPoint() is a method of your point class that prints the data to the console.

              2) Overload the insertion operator so it will print the point out with the code you already have. Based on the code you posted, this would be the ideal solution since you have your linked list templated.
              OracleGuy

              Comment


              • #8
                Thanks. I have this in my linkedlist.h

                friend ostream& operator <<(ostream& , const linkedListType<Type>&);

                I don't know how to overload the insertion operator all the way though.

                My new code is zipped up if you have time to take a look and see what I'm doing wrong.

                You've been helpful so far and I'm still trying to figure out how to do this. Thanks again.
                Attached Files

                Comment


                • #9
                  If you don't have time to look at all my code here is what is in linkedList.h:

                  friend ostream& operator <<(ostream&, const linkedListType<Type>&);


                  and


                  //Overloading the stream insertion operator
                  template<class Type>
                  ostream& operator<<(ostream& osObject, const linkedListType<Type>& list)
                  {
                  nodeType<Type> *current; //pointer to traverse the list

                  current = list.first; //set current so that it points to
                  //the first node
                  while(current != NULL) //while more data to print
                  {
                  osObject<<current->info<<" ";
                  current = current->link;
                  }

                  return osObject;
                  }



                  and print() from the above post is the print method. I want to be able to print the linked list of points with list1.print();

                  Here is the main() code:

                  #include "stdafx.h"
                  #include "linkedList.h"
                  #include "Point.h"

                  int _tmain(int argc, _TCHAR* argv[])
                  {
                  int x = 0;
                  int y = 0;

                  Point p1(x, y);

                  linkedListType<Point> list1;

                  cout<<"1) Type two numbers to make a coordinate."
                  "\n2) Use the format (XX YY) only spacing the numbers not using a comma."
                  "\n3) Then press Enter to add the coordinate to the list."
                  "\n4) When finished adding to the list type -9999 and press Enter."
                  <<endl;

                  while(x != -9999)//execution number for list creation
                  {
                  cin >> x, y;
                  list1.insertLast(p1);//insert info into the list as long as -9999 isn't entered
                  }

                  list1.print();


                  return 0;
                  }

                  Comment


                  • #10
                    Well I've worked on this for a very long time and I can't really figure it all out. Can someone please tell me what I need to add to my code to make a program that will ask the user for as many points as they want, make a linked list of points (x,y), sort it by x value, then print out the list of points.

                    I have the linkedList class and Point class that I think are done right, but I don't know how to tie it all together to do what I need because of little problems I keep running into. I'll attach my latest code to this post and hopefully someone can help me get it working. Thanks again.

                    A few of the specific problems I'm having are printing the list, and I don't think I'm reading the data into my the list correctly as a point (x, y). I think I'm only getting x values. I think my main() is totally wrong.
                    Attached Files

                    Comment


                    • #11
                      Well in the while loop in main, you never assign the x and y values to p1. And you insert the point into the linked list before you ask the user for the points. Which if you think about, doesn't make much sense.

                      It should go:
                      1) Collect the x, y values from user
                      2) Assign them to p1
                      3) Insert p1 into the list

                      Does that make sense?

                      As for the overloading, I ment you need to apply the overload operator to your Point class, not the linked list class. It could look something like this:
                      Code:
                      ostream& operator<<(ostream& osObject, const Point& p)
                      {
                      osObject << "x: " << p.x << " y: " << p.y;
                      }
                      Then your print method in your linked list should work.
                      Last edited by oracleguy; Sep 30, 2006, 03:05 PM.
                      OracleGuy

                      Comment


                      • #12
                        Yea it makes sense, but I don't really know how to do it.

                        1) Am I collecting x and y right?

                        2) how do I assign them to p1?

                        3) I insert like I have been once that is done?

                        Code:
                        // LinkedPoints.cpp : Defines the entry point for the console application.
                        //
                        
                        #include "stdafx.h"
                        #include "linkedList.h"
                        #include "Point.h"
                        
                        int _tmain(int argc, _TCHAR* argv[])
                        {
                        	int x = 0;
                        	int y = 0;
                        
                        Point p1(x, y);
                        
                        linkedListType<Point> list1;
                        
                        	cout<<"1) Type two numbers to make a coordinate."
                        		"\n2) Use the format (XX YY) only spacing the numbers not using a comma."
                        		"\n3) Then press Enter to add the coordinate to the list."
                        		"\n4) When finished adding to the list type -9999 and press Enter."
                        		<<endl;
                        		cin >> x;
                        		cin >> y;
                        
                        	while(x != -9999)//execution number for list creation
                        		{
                        			cin >> x;
                        			cin >> y;
                        			p1(x, y);
                        			list1.insertLast(p1);//insert info into the list as long as -9999 isn't entered
                        		}
                        
                        	cout << p1 << endl;
                        
                        return 0;
                        }
                        Also for the ostream operator you gave me if it is in Point.h/Point.cpp how do I use it to print the entire linked list? I know how to get it to print one point(p1), but I need a way to print the entire list. I used this when I did the linked list with simple data type int.

                        Code:
                        list1.print();
                        and it printed the entire list. Can I do that with my points too once I get them in the list okay? I think something is wrong with how I'm gathering x and y or how it is finding x and y values because it isn't displaying what I put right it's giving me some large number instead.

                        Please tell me how to ask the user for x and y, put it in p1, put p1 in the linked list and print it. If you know what code would get this working please tell me. The assignment is due Sunday and I've been working on it all week with no luck. I don't usually ask like this, but it is a high point assignment and after many weeks of turning in good programs that I did myself I am for some reason having insane problems on this one that are going to cost me two letter grades. I really am desperate can you try getting it to work because nothing seems to be working, and I've tried countless things and suggestions.
                        Last edited by Zer033; Sep 30, 2006, 03:34 PM.

                        Comment


                        • #13
                          1) Yes

                          2) Your point class has methods to set the X and Y, use them to set the values in p1. You'll want to use those instead of the constructor because I'm pretty sure you can't do it again. Unless you were to create p1 inside the loop after you get the data from the user.

                          3) Yes

                          Basically ask the user for the data like you are, then set the values in p1 using the set methods in the point class. Then insert it into your list.

                          As for the overloading, if you overload the operator for the point class, then when you print it out in the linked list it can sucessfully do something like:

                          Code:
                          Point p1;
                          cout << p1 << endl;
                          Because it will now how to insert the point class into the stream by calling the overloaded operator method. So your print method in your linked list class should just work exactly like it did if you were storing ints if you overload the insertion operator on the point class.

                          If you know what code would get this working please tell me. The assignment is due Sunday and I've been working on it all week with no luck. I don't usually ask like this, but it is a high point assignment and after many weeks of turning in good programs that I did myself I am for some reason having insane problems on this one that are going to cost me two letter grades. I really am desperate can you try getting it to work because nothing seems to be working, and I've tried countless things and suggestions.
                          Well I can't just give you the code for multiple reasons, one of which being against the forum rules when it comes to homework assignments.
                          OracleGuy

                          Comment


                          • #14
                            Thanks I figured it out. I have another problem though if you can help. I get it to print the list, but it doesn't sort right. I think my problem is not singling out just x to sort. How do I single out just x to sort and forget about y. Everything I've tried hasn't worked.

                            Here is how I decided to ask for x and y and print the list. Printing the list works perfect unsorted, but I need to sort by x.

                            Code:
                            	cout << "\nEnter Coordinates (integers) - Use format X Y: ";
                            
                            	while(cin >> x >> y)//Allow user to enter points until an invalid entry occurs ex. "done"
                            	{
                            		cout << "Enter Coordinates (integers) - Use format X Y: ";
                            			list1.insertLast(Point(x, y));
                            
                            	}//end while
                            
                            system("cls");
                            
                            	cout << "Your linked list of points (sorted by x value) looks like this: \n" << endl;
                            
                            	//sort linked list
                            	list1.linkedInsertionSort();
                            
                            	//print the sorted linked list of points
                            	list1.print();
                            
                            cout << endl;

                            Here is my insertion sort function

                            Code:
                            template<class Type>
                            void linkedListType<Type>::linkedInsertionSort()
                            {
                            	nodeType<Type> *lastInOrder;
                            	nodeType<Type> *firstOutOfOrder;
                            	nodeType<Type> *current;
                            	nodeType<Type> *trailCurrent;
                            
                            	lastInOrder = first;
                            
                            	if (first == NULL)
                            		cout << "Cannot sort an empty list" << endl;
                            	else
                            		if (first->link == NULL)
                            			cout << "List is of length 1.  Already in order" << endl;
                            		else
                            			while (lastInOrder->link != NULL)
                            			{
                            				firstOutOfOrder = lastInOrder->link;
                            				if (firstOutOfOrder->info < first->info)
                            				{
                            					lastInOrder->link = firstOutOfOrder->link;
                            					firstOutOfOrder->link = first;
                            					first = firstOutOfOrder;
                            				}
                            				else
                            				{
                            					trailCurrent = first;
                            					current = first->link;
                            
                            					while (current->info < firstOutOfOrder->info)
                            					{
                            						trailCurrent = current;
                            						current = current->link;
                            					}
                            
                            					if (current != firstOutOfOrder)
                            					{
                            						lastInOrder->link = firstOutOfOrder->link;
                            						firstOutOfOrder->link = current;
                            						trailCurrent->link = firstOutOfOrder;
                            					}
                            					else
                            						lastInOrder = lastInOrder->link;
                            				}
                            			}//end while
                            }//end linkedInsertionSort
                            I'm not really sure how to sort just by x value. If I take just one value for my linked list it does sort right, but I think having both x and y is messing it up.

                            Comment

                            Working...
                            X