#include <iostream> #include <string> using namespace std; /* ============= FOR YOUR ANALYSIS ================= You need to analyze the following functionalities: 1. Copy constructor or assignment operator 2. Insert method 3. All 3 remove methods ====================================================*/ /** Item 1 of hw#3 goes here  you should add any data and functionality as needed but do not change the interface of the given methods and attributes */ //utility class to represent a node of the list template <class Obj> class Node { public: //constructor Node(): next(NULL), prev(NULL){} //default constructor Node(Obj data):next(NULL), prev(NULL){ this>data = data; } //public for efficient access Obj data; //the stored Node<Obj> * next; //point to next node Node<Obj> * prev; //point to previous node }; /* THE SORTED DOUBLY LINKED LIST */ template<class T> class SortedList { public: //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here Jason: I didn't do this in my assignment 3, bu'st this would make a head node and tail node, // head's next pointing to the tail initially, and /////////////////////////////////////////////////////////////////// //default constructor //set next pointer on head to point to tail, and set prev on tail to point to head. SortedList():head(NULL), tail(NULL), current(NULL), count(0) { head = new Node<Obj>; tail = new Node<Obj>; tail = head>next; head = tail>prev; } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// //copy constructor // copy the content of the given list rhs into a new list // + O(n)t. //clone list SortedList(const SortedList<T> & rhs): head(NULL), tail(NULL) { //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// //assignment operator // + O(n) //call copy constructor once. SortedList & operator=(const SortedList<T> & rhs) ; //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here //Insertion procedure to make sure node is inserted in a way that keeps list sorted: It iterates two variables simutanously, the pointer starting at the first node and the pointer starting at last node, comparing nodes using => =< operators. /*Start at beginning, check to make sure beginning node is less than node to be inserted. If it is greater, insert new node at beginning. If it is less than node to be inserted, check the last node, make sure last node is greater than node to be inserted. If not, than make node to be inserted last node. If last node was greater than node to be inserted, go back to beginning and compare next node (2nd in this case) Make sure next node is less than node to be inserted. If it isn't, make node to be inserted the 2nd Node(in between the first node and former 2nd node) If it is less, go to other side again and check the 2nd to last node. Do similar comparisons until node is inserted, or the two ends of the comparing function meets in middle In which case node to be inserted is at the median of the linked list. This algorithm uses a single while statement, with each iteration looking at both ends of the list. Is inefficient if the insertion point makes the node to be inserted the second node, but if it is at a later position, it is actually as efficient as O(n)=n, and can be more efficient than the regular sorted insert because it does not need to look at every node in sequence. Only works with doubly linked list, not single linked list. Uses 3 if statements, one if statement starts for loop (which itself contains an if statement), but if one of the other if statements are followed, loop isn't used saving time. Best case scenario is if the node will be inserted at beginning or very end, worst case is if it is smack dab in the middle. Decided that since I such limited amount of time, I would forgo using my above procedure and go with a regular sorted insertion(start at beginning, end at end. Still tests fist and last nodes though. Worst case scenario is if is inserted at second to last node position. If I had more time, I would have used the idea I came up with. When insert point found, use below function(may need to add it to a function):*/ /*insertDLinkNode(Node *current) //public, used to insert a new node. {//Code to insert a node within Linked list newNode = new Node(x); newNode>prev = current; newNode>next = current>next; newNode>prev>next = newNode; newNode>next>prev = newNode; current = newNode; return current; }*/ /////////////////////////////////////////////////////////////////// // + insert a value into the list in assending order // duplicated entry will be ordered by arrival order // + current pointer points at the new node // + list size must be updated // + return the pointer to the new node in the list // + O(n) //Jason: Can use a variation of my sorted insertion, need to add something to make sure duplicates ordered by arrival. Node<T> * insert(const T & value); { Node *firstNode, *lastNode, *nextNode, *prevNode; // nextNode and prevNode are for if the nodes are not at the beginning or end. firstNode=head>next; lastNode=tail>prev; if (value < (firstNode>data)) { newNode = new Node(x); newNode > prev = head; newNode > next = firstNode; head>next = newNode; firstNode = newNode; current = firstNode; return current; } else if (value > (lastNode>data)) { newNode = new Node(x); newNode > next = head; newNode > prev = lastNode; tail > prev = newNode; lastNode = newNode; current = lastNode; return current; } else { for (current = firstNode > next; (current == lastNode > prev)  ((current > data == value) && (current>next>data > value); current = current > next;) { if (((current> data) <= value) && ((current > next > data) > value)) { newNode = new Node(x); newNode>prev = current; newNode>next = current>next; newNode>prev>next = newNode; newNode>next>prev = newNode; current = newNode; return current; } } } } /*insertDLinkNode(Node *current) //public, used to insert a new node. insert function followed this general form. {//Code to insert a node within Linked list newNode = new Node(x); newNode>prev = current; newNode>next = current>next; newNode>prev>next = newNode; newNode>next>prev = newNode; current = newNode; return current; }*/ //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// //+ check the node at all three internal pointers: head, tail, current // to find the range in which the node is in; then scan the range to // find the node with given value // + if found the node in the list, the current pointer points at the first // found node // + return NULL if not found or the pointer to the first matching // + O(n) //Jason: Search function. Return pointer. Node<T> * find(const T & value) const { if(((head>next>data) > search_term)  ((tail>prev>data) < (search_term))) { return null; } else //if (current>data != value) { Node<Obj> * p = head> next; while (p != NULL && p != value) { p = p>next; if (p > data) return NULL; } current = p; return Node<T>(p); } } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// // + remove all nodes with the given value // + current pointer points at the node immediately after the removing nodes // + list size must be updated (use size function) // + return number of removed nodes Jason: (perhaps create variable of size before removalsize after removal) // + O(n) //Jason: will have to go through whole list to remove nodes with a specific value. //Jason: can use a variant on the removal algorithm that I came up with for assignment 3. //algorithm needs to be altered so that instead of simply removing the first node it comes across that has the specified value, //(c)it will remove all nodes in the list with the specified value. Will need to reassign 2 pointers, delete all others. int remove(const T & value); //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// //+ remove node pointed by the pointer //+ current pointer point at the node immediately after the removed node // + list size must be updated //+ return the current pointer //+ O(1) //Jason: This can use an almost exact duplicate of the algorithm from assignment 3 that I came up with. Unless this isn't the file I'm supposed to insert that code in. //Jason: Will have to create and attach code that makes current pointer point at node that comes after removed node (if mine does not already). //Jason: move current pointer to next node. Node<T> * remove(Node<T> * node); //public function, returns current. Needed to delete nodes without compromising the whole list. Frees up memory when node removed. { node>prev>next = node>next; node>next>prev = node>prev; current = node>next; delete node; count; return current; } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// // + remove all nodes, inclusively, between the two given pointers // + current pointer point at the node immediately after the removing nodes // + return number of nodes removed // + list size must be updated // + O(n) //Jason: will be similar to other multiple delete, but instead of looking at duplicates, it simply deletes everything between plus given pointers. int remove(Node<T> * from, Node<T> * to) { int originalSize = size(); while (current = from; current == to;) { remove(Node<T> current); } remove(Node<T> current); return (originalSizesize()); } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here //uses a loop that calls my single node remove function, until the list is empty. Use the count variable to track to see if size equals zero. Afterward, may need to put in a delete head and tail outside of loop. /////////////////////////////////////////////////////////////////// // destructor: remove all the nodes //O(n) ~SortedList() { current = head > next; while(current > next != null) { remove(Node<T> current); } delete head; delete tail; } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// // + return the number of node in the list //O(1) int size() const { return this>count; } private: //data members Node<T>*current; //point at the last access node. Create a constructor for current. In linked list class. Node<T>*head; //points at the head of the list. Create a constructor for head. Node<T> *tail; //points at the tail of the list. Create a constructor for tail. int count; // the total number of nodes in the list }; //end of SortedList class
48 Replies  2745 Views  Last Post: 28 March 2013  11:19 PM
#1
Problem with linked list class
Posted 24 March 2013  11:52 PM
Replies To: Problem with linked list class
#2
Re: Problem with linked list class
Posted 25 March 2013  03:30 AM
Quote
Usually error messages are a good indication of problems. You should be compiling often and fixing the errors as you go, not compiling after writing everything.
The first thing I notice is this:
SortedList(const SortedList<T> & rhs): head(NULL), tail(NULL) { //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// //assignment operator // + O(n) //call copy constructor once. SortedList & operator=(const SortedList<T> & rhs) ;
You seem to be missing a closing brace for the constructor.
Next this:
Node<T> * insert(const T & value); {
Here you seem to have an errant semicolon. You do this several places.
So before you even worry about adding anything else fix these and any other errors you find before moving on.
Once you have the errors fixed you will need to create your main and actually try to use this class, because you are using templates, then recompile. Templates are not actually created until they are used so create a function that actually tries to declare and use the class.
I also edited your title to be more accurate.
Jim
This post has been edited by jimblumberg: 25 March 2013  03:31 AM
#3
Re: Problem with linked list class
Posted 25 March 2013  06:10 AM
This post has been edited by jayburn00: 25 March 2013  06:12 AM
#4
Re: Problem with linked list class
Posted 25 March 2013  06:53 AM
Quote
The problem is that when you went to implement the functions you tried to implement them inside the class definition, instead of placing them outside the class definition, therefore you need to remove the semicolons. This is not a mistake by your instructor, it is your mistake. Normally the definition of the class is separated from the implementation:
class Test { public: void someFunction(); private: int someVariable; }; void Test::someFunction() { someVariable = 10; }
Quote
No, you should be able to test most of the class without the copy constructor and assignment operator. There are "extra" semicolons several places in your code not just the assignment and assignment operator. Like I said before you go any further get the program to compile without warnings or errors.
Jim
This post has been edited by jimblumberg: 25 March 2013  06:54 AM
#5
Re: Problem with linked list class
Posted 25 March 2013  07:28 AM
#6
Re: Problem with linked list class
Posted 25 March 2013  07:40 AM
Jim
#7
Re: Problem with linked list class
Posted 25 March 2013  07:49 AM
#8
Re: Problem with linked list class
Posted 25 March 2013  08:29 AM
Anyway, the file the teacher gave out without any changes from me:
SortedList.h:
#include <iostream> #include <string> using namespace std; /* ============= FOR YOUR ANALYSIS ================= You need to analyze the following functionalities: 1. Copy constructor or assignment operator 2. Insert method 3. All 3 remove methods ====================================================*/ /** Item 1 of hw#3 goes here  you should add any data and functionality as needed but do not change the interface of the given methods and attributes */ //utility class to represent a node of the list template <class Obj> class Node { public: //constructor Node(): next(NULL), prev(NULL){} //default constructor Node(Obj data):next(NULL), prev(NULL){ this>data = data; } //public for efficient access Obj data; //the stored Node<Obj> * next; //point to next node Node<Obj> * prev; //point to previous node }; /* THE SORTED DOUBLY LINKED LIST */ template<class T> class SortedList{ public: //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// //default constructor SortedList():head(NULL), tail(NULL), current(NULL), count(0){} //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// //copy constructor // copy the content of the given list rhs into a new list // + O(n) SortedList(const SortedList<T> & rhs); //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// //assignment operator // + O(n) SortedList & operator=(const SortedList<T> & rhs) ; //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// // + insert a value into the list in assending order // duplicated entry will be ordered by arrival order // + current pointer points at the new node // + list size must be updated // + return the pointer to the new node in the list // + O(n) Node<T> * insert(const T & value); //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// //+ check the node at all three internal pointers: head, tail, current // to find the range in which the node is in; then scan the range to // find the node with given value // + if found the node in the list, the current pointer points at the first // found node // + return NULL if not found or the pointer to the first matching // + O(n) Node<T> * find(const T & value) const; //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// // + remove all nodes with the given value // + current pointer points at the node immediately after the removing nodes // + list size must be updated // + return number of removed nodes // + O(n) int remove(const T & value); //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// //+ remove node pointed by the pointer //+ current pointer point at the node immediately after the removed node // + list size must be updated //+ return the current pointer //+ O(1) Node<T> * remove(Node<T> * node); //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// // + remove all nodes, inclusively, between the two given pointers // + current pointer point at the node immediately after the removing nodes // + return number of nodes removed // + list size must be updated // + O(n) int remove(Node<T> * from, Node<T> * to); //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// // destructor: remove all the nodes //O(n) ~SortedList(){} //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// // + return the number of node in the list //O(1) int size() const { return this>count;} private: //data members Node<T>*current; //point at the last access node Node<T>*head; //points at the head of the list Node<T> *tail; //points at the tail of the list int count; // the total number of nodes in the list }; //end of SortedList class
The class functions, constructors, etc. etc. that I have coded, copy constructor and assignment operator still missing:
#include <iostream> #include <string>//Jason: why is string needed in include statements? using namespace std; /* ============= FOR YOUR ANALYSIS ================= You need to analyze the following functionalities: 1. Copy constructor or assignment operator 2. Insert method 3. All 3 remove methods ====================================================*/ /** Item 1 of hw#3 goes here  you should add any data and functionality as needed but do not change the interface of the given methods and attributes */ //utility class to represent a node of the list template <class Obj> class Node { public: //constructor Node(): next(NULL), prev(NULL){} //default constructor Node(Obj data):next(NULL), prev(NULL){ this>data = data; } //public for efficient access Obj data; //the stored Node<Obj> * next; //point to next node Node<Obj> * prev; //point to previous node }; /* THE SORTED DOUBLY LINKED LIST */ template<class T> class SortedList { public: //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here Jason: I didn't do this in my assignment 3, but this would make a head node and tail node, // head's next pointing to the tail initially, and tail prev pointer initially pointing to head. /////////////////////////////////////////////////////////////////// //default constructor //set next pointer on head to point to tail, and set prev on tail to point to head. SortedList():head(NULL), tail(NULL), current(NULL), count(0) { head = new Node<Obj>; tail = new Node<Obj>; tail = head>next; head = tail>prev; } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// //copy constructor // copy the content of the given list rhs into a new list // + O(n)t. //clone list SortedList(const SortedList<T> & rhs): head(NULL), tail(NULL) { //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// //assignment operator // + O(n) //call copy constructor once. SortedList & operator=(const SortedList<T> & rhs) ; //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here //Insertion procedure to make sure node is inserted in a way that keeps list sorted: It iterates two variables simutanously, the pointer starting at the first node and the pointer starting at last node, comparing nodes using => =< operators. /*Start at beginning, check to make sure beginning node is less than node to be inserted. If it is greater, insert new node at beginning. If it is less than node to be inserted, check the last node, make sure last node is greater than node to be inserted. If not, than make node to be inserted last node. If last node was greater than node to be inserted, go back to beginning and compare next node (2nd in this case) Make sure next node is less than node to be inserted. If it isn't, make node to be inserted the 2nd Node(in between the first node and former 2nd node) If it is less, go to other side again and check the 2nd to last node. Do similar comparisons until node is inserted, or the two ends of the comparing function meets in middle In which case node to be inserted is at the median of the linked list. This algorithm uses a single while statement, with each iteration looking at both ends of the list. Is inefficient if the insertion point makes the node to be inserted the second node, but if it is at a later position, it is actually as efficient as O(n)=n, and can be more efficient than the regular sorted insert because it does not need to look at every node in sequence. Only works with doubly linked list, not single linked list. Uses 3 if statements, one if statement starts for loop (which itself contains an if statement), but if one of the other if statements are followed, loop isn't used saving time. Best case scenario is if the node will be inserted at beginning or very end, worst case is if it is smack dab in the middle. Decided that since I such limited amount of time, I would forgo using my above procedure and go with a regular sorted insertion(start at beginning, end at end. Still tests fist and last nodes though. Worst case scenario is if is inserted at second to last node position. If I had more time, I would have used the idea I came up with. When insert point found, use below function(may need to add it to a function):*/ /*insertDLinkNode(Node *current) //public, used to insert a new node. {//Code to insert a node within Linked list newNode = new Node(x); newNode>prev = current; newNode>next = current>next; newNode>prev>next = newNode; newNode>next>prev = newNode; current = newNode; return current; }*/ /////////////////////////////////////////////////////////////////// // + insert a value into the list in assending order // duplicated entry will be ordered by arrival order // + current pointer points at the new node // + list size must be updated // + return the pointer to the new node in the list // + O(n) //Jason: Can use a variation of my sorted insertion, need to add something to make sure duplicates ordered by arrival. Node<T> * insert(const T & value) { Node *firstNode, *lastNode, *nextNode, *prevNode; // nextNode and prevNode are for if the nodes are not at the beginning or end. firstNode=head>next; lastNode=tail>prev; if (value < (firstNode>data)) { newNode = new Node(x); newNode > prev = head; newNode > next = firstNode; head>next = newNode; firstNode = newNode; current = firstNode; return current; } else if (value > (lastNode>data)) { newNode = new Node(x); newNode > next = head; newNode > prev = lastNode; tail > prev = newNode; lastNode = newNode; current = lastNode; return current; } else { for (current = firstNode > next; (current == lastNode > prev)  ((current > data == value) && (current>next>data > value); current = current > next;) { if (((current> data) <= value) && ((current > next > data) > value)) { newNode = new Node(x); newNode>prev = current; newNode>next = current>next; newNode>prev>next = newNode; newNode>next>prev = newNode; current = newNode; return current; } } } } /*insertDLinkNode(Node *current) //public, used to insert a new node. insert function followed this general form. {//Code to insert a node within Linked list newNode = new Node(x); newNode>prev = current; newNode>next = current>next; newNode>prev>next = newNode; newNode>next>prev = newNode; current = newNode; return current; }*/ //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here //this will be a sort of search function that returns a pointer to the first node found with the desired value. //If the value is not found in list, it returns NULL. /////////////////////////////////////////////////////////////////// //+ check the node at all three internal pointers: head, tail, current // to find the range in which the node is in; then scan the range to // find the node with given value // + if found the node in the list, the current pointer points at the first // found node // + return NULL if not found or the pointer to the first matching // + O(n) //Jason: Search function. Return pointer. Node<T> * find(const T & value) const { if(((head>next>data) > search_term)  ((tail>prev>data) < (search_term))) { return null; } else //if (current>data != value) { Node<Obj> * p = head> next; while (p != NULL && p != value) { p = p>next; if (p > data) return NULL; } current = p; return Node<T>(p); } } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// // + remove all nodes with the given value // + current pointer points at the node immediately after the removing nodes // + list size must be updated (use size function) // + return number of removed nodes Jason: (perhaps create variable of size before removalsize after removal) // + O(n) //Jason: will have to go through whole list to remove nodes with a specific value. //Jason: can use a variant on the removal algorithm that I came up with for assignment 3. //algorithm needs to be altered so that instead of simply removing the first node it comes across that has the specified value, //(c)it will remove all nodes in the list with the specified value. Will need to reassign 2 pointers, delete all others. int remove(const T & value) { originalSize = size(); for (find(const T & value) const; ((current>data) != value); remove(current))//since the find function returns current as being equal to the current pointer to the value sought, I put that as the start condition. This will be an empty for loop, since the single remove function removes a single node and then moves current to next. {//leave empty; } return (originalSize  size()); } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// //+ remove node pointed by the pointer //+ current pointer point at the node immediately after the removed node // + list size must be updated //+ return the current pointer //+ O(1) //Jason: This can use an almost exact duplicate of the algorithm from assignment 3 that I came up with. Unless this isn't the file I'm supposed to insert that code in. //Jason: Will have to create and attach code that makes current pointer point at node that comes after removed node (if mine does not already). //Jason: move current pointer to next node. Node<T> * remove(Node<T> * node); //public function, returns current. Needed to delete nodes without compromising the whole list. Frees up memory when node removed. { node>prev>next = node>next; node>next>prev = node>prev; current = node>next; delete node; count; return current; } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// // + remove all nodes, inclusively, between the two given pointers // + current pointer point at the node immediately after the removing nodes // + return number of nodes removed // + list size must be updated // + O(n) //Jason: will be similar to other multiple delete, but instead of looking at duplicates, it simply deletes everything between plus given pointers. int remove(Node<T> * from, Node<T> * to) { int originalSize = size(); while (current = from; current == to;) { remove(Node<T> current); } remove(Node<T> current); return (originalSizesize()); } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here //uses a loop that calls my single node remove function, until the list is empty. Use the count variable to track to see if size equals zero. Afterward, may need to put in a delete head and tail outside of loop. /////////////////////////////////////////////////////////////////// // destructor: remove all the nodes //O(n) ~SortedList() { current = head > next; while(current > next != null) { remove(Node current); } delete head; delete tail; } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// // + return the number of node in the list //O(1) int size() const { return this>count; } private: //data members Node<T>*current; //point at the last access node. Create a constructor for current. In linked list class. Node<T>*head; //points at the head of the list. Create a constructor for head. Node<T> *tail; //points at the tail of the list. Create a constructor for tail. int count; // the total number of nodes in the list }; //end of SortedList class
One reason I haven't gone and created a main yet is because the way the teacher set this up, is that the teacher doesn't give us much time on the assignment and the main he wants is complicated to set up (it has to test 15 different list creations, each one 100 times, find average run time completion, and then we graph it. Since it is difficult to run a test 1500 times manually, he says to make main do it. I will have enough debugging as is with that monstrosity(not that familiar with creating a program like that), prefer not to add more to it. All I want is tips on how to create the copy constructor for this this and the assignment operator, unless you see other errors I am currently unable to detect, again I fixed the semicolon issue I think.)
Edit: just realized, I think I may be missing an awful lot of include statements, as to which ones, not sure.
This post has been edited by jayburn00: 25 March 2013  08:31 AM
#9
Re: Problem with linked list class
Posted 25 March 2013  08:47 AM
#10
Re: Problem with linked list class
Posted 25 March 2013  10:47 AM
#include <iostream> #include <string>//Jason: why is string needed in include statements? using namespace std; /* ============= FOR YOUR ANALYSIS ================= You need to analyze the following functionalities: 1. Copy constructor or assignment operator 2. Insert method 3. All 3 remove methods ====================================================*/ /** Item 1 of hw#3 goes here  you should add any data and functionality as needed but do not change the interface of the given methods and attributes */ //utility class to represent a node of the list template <class Obj> class Node { public: //constructor Node(): next(NULL), prev(NULL){}; //default constructor Node(Obj data):next(NULL), prev(NULL){ this>data = data; } //public for efficient access Obj data; //the stored Node<Obj> * next; //point to next node Node<Obj> * prev; //point to previous node }; /* THE SORTED DOUBLY LINKED LIST */ template<class T> class SortedList { public: //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here Jason: I didn't do this in my assignment 3, but this would make a head node and tail node, // head's next pointing to the tail initially, and tail prev pointer initially pointing to head. /////////////////////////////////////////////////////////////////// //default constructor //set next pointer on head to point to tail, and set prev on tail to point to head. SortedList():head(NULL), tail(NULL), current(NULL), count(0) { head = new Node<Obj>; tail = new Node<Obj>; tail = head>next; head = tail>prev; } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// //copy constructor // copy the content of the given list rhs into a new list // + O(n)t. //clone list SortedList(const SortedList<T> & rhs): head(NULL), tail(NULL) { } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// //assignment operator // + O(n) //call copy constructor once. SortedList & operator=(const SortedList<T> & rhs) ; //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here //Insertion procedure to make sure node is inserted in a way that keeps list sorted: It iterates two variables simutanously, the pointer starting at the first node and the pointer starting at last node, comparing nodes using => =< operators. /*Start at beginning, check to make sure beginning node is less than node to be inserted. If it is greater, insert new node at beginning. If it is less than node to be inserted, check the last node, make sure last node is greater than node to be inserted. If not, than make node to be inserted last node. If last node was greater than node to be inserted, go back to beginning and compare next node (2nd in this case) Make sure next node is less than node to be inserted. If it isn't, make node to be inserted the 2nd Node(in between the first node and former 2nd node) If it is less, go to other side again and check the 2nd to last node. Do similar comparisons until node is inserted, or the two ends of the comparing function meets in middle In which case node to be inserted is at the median of the linked list. This algorithm uses a single while statement, with each iteration looking at both ends of the list. Is inefficient if the insertion point makes the node to be inserted the second node, but if it is at a later position, it is actually as efficient as O(n)=n, and can be more efficient than the regular sorted insert because it does not need to look at every node in sequence. Only works with doubly linked list, not single linked list. Uses 3 if statements, one if statement starts for loop (which itself contains an if statement), but if one of the other if statements are followed, loop isn't used saving time. Best case scenario is if the node will be inserted at beginning or very end, worst case is if it is smack dab in the middle. Decided that since I such limited amount of time, I would forgo using my above procedure and go with a regular sorted insertion(start at beginning, end at end. Still tests fist and last nodes though. Worst case scenario is if is inserted at second to last node position. If I had more time, I would have used the idea I came up with. When insert point found, use below function(may need to add it to a function):*/ /*insertDLinkNode(Node *current) //public, used to insert a new node. {//Code to insert a node within Linked list newNode = new Node(x); newNode>prev = current; newNode>next = current>next; newNode>prev>next = newNode; newNode>next>prev = newNode; current = newNode; return current; }*/ /////////////////////////////////////////////////////////////////// // + insert a value into the list in assending order // duplicated entry will be ordered by arrival order // + current pointer points at the new node // + list size must be updated // + return the pointer to the new node in the list // + O(n) //Jason: Can use a variation of my sorted insertion, need to add something to make sure duplicates ordered by arrival. Node<T> * insert(const T & value) { Node *firstNode, *lastNode, *nextNode, *prevNode; // nextNode and prevNode are for if the nodes are not at the beginning or end. firstNode=head>next; lastNode=tail>prev; if (value < (firstNode>data)) { newNode = new Node(x); newNode > prev = head; newNode > next = firstNode; head>next = newNode; firstNode = newNode; current = firstNode; return current; } else if (value > (lastNode>data)) { newNode = new Node(x); newNode > next = head; newNode > prev = lastNode; tail > prev = newNode; lastNode = newNode; current = lastNode; return current; } else { for ((current = firstNode > next); (current == lastNode > prev)  ((current > data == value) && (current>next>data > value); current = current > next;)) { if (((current> data) <= value) && ((current > next > data) > value)) { newNode = new Node(x); newNode>prev = current; newNode>next = current>next; newNode>prev>next = newNode; newNode>next>prev = newNode; current = newNode; return current; } } } } /*insertDLinkNode(Node *current) //public, used to insert a new node. insert function followed this general form. {//Code to insert a node within Linked list newNode = new Node(x); newNode>prev = current; newNode>next = current>next; newNode>prev>next = newNode; newNode>next>prev = newNode; current = newNode; return current; }*/ //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here //this will be a sort of search function that returns a pointer to the first node found with the desired value. //If the value is not found in list, it returns NULL. /////////////////////////////////////////////////////////////////// //+ check the node at all three internal pointers: head, tail, current // to find the range in which the node is in; then scan the range to // find the node with given value // + if found the node in the list, the current pointer points at the first // found node // + return NULL if not found or the pointer to the first matching // + O(n) //Jason: Search function. Return pointer. Node<T> * find(const T & value) const { if(((head>next>data) > search_term)  ((tail>prev>data) < (search_term))) { return null; } else //if (current>data != value) { Node<Obj> * p = head> next; while (p != NULL && p != value) { p = p>next; if (p > data) return NULL; } current = p; return Node<T>(p); } } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// // + remove all nodes with the given value // + current pointer points at the node immediately after the removing nodes // + list size must be updated (use size function) // + return number of removed nodes Jason: (perhaps create variable of size before removalsize after removal) // + O(n) //Jason: will have to go through whole list to remove nodes with a specific value. //Jason: can use a variant on the removal algorithm that I came up with for assignment 3. //algorithm needs to be altered so that instead of simply removing the first node it comes across that has the specified value, //(c)it will remove all nodes in the list with the specified value. Will need to reassign 2 pointers, delete all others. int remove(const T & value) { originalSize = size(); for (find(const T & value) const; ((current>data) != value); remove(current))//since the find function returns current as being equal to the current pointer to the value sought, I put that as the start condition. This will be an empty for loop, since the single remove function removes a single node and then moves current to next. {//leave empty; } return (originalSize  size()); } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// //+ remove node pointed by the pointer //+ current pointer point at the node immediately after the removed node // + list size must be updated //+ return the current pointer //+ O(1) //Jason: This can use an almost exact duplicate of the algorithm from assignment 3 that I came up with. Unless this isn't the file I'm supposed to insert that code in. //Jason: Will have to create and attach code that makes current pointer point at node that comes after removed node (if mine does not already). //Jason: move current pointer to next node. Node<T> * remove(Node<T> * node)//public function, returns current. Needed to delete nodes without compromising the whole list. Frees up memory when node removed. { node>prev>next = node>next; node>next>prev = node>prev; current = node>next; delete node; count; return current; } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// // + remove all nodes, inclusively, between the two given pointers // + current pointer point at the node immediately after the removing nodes // + return number of nodes removed // + list size must be updated // + O(n) //Jason: will be similar to other multiple delete, but instead of looking at duplicates, it simply deletes everything between plus given pointers. int remove(Node<T> * from, Node<T> * to) { int originalSize = size(); while (current = from; current == to;) { remove(Node<T> current); } remove(Node<T> current); return (originalSizesize()); } //for testing I have made a cycle through function, simply cycles through the list, printing data. void printList() { current = head > next; while(current != tail) { cout << (current > data); current = current > next; } } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here //uses a loop that calls my single node remove function, until the list is empty. Use the count variable to track to see if size equals zero. Afterward, may need to put in a delete head and tail outside of loop. /////////////////////////////////////////////////////////////////// // destructor: remove all the nodes //O(n) ~SortedList() { current = head > next; while(current > next != null) { remove(Node current); } delete head; delete tail; } //////////////////////////////////////////////////////////////////// // Put your hw#3 coresponding item here /////////////////////////////////////////////////////////////////// // + return the number of node in the list //O(1) int size() const { return this>count; } private: //data members Node<T>*current; //point at the last access node. Create a constructor for current. In linked list class. Node<T>*head; //points at the head of the list. Create a constructor for head. Node<T> *tail; //points at the tail of the list. Create a constructor for tail. int count; // the total number of nodes in the list }; //end of SortedList class int main() { SortedList<int>(testList1); for(int i = 0; i == 5; i++) { testList1.insert(i); } testList1.printList(); return 0; }
errors:
Error 1 error C2065: 'Obj' : undeclared identifier c:\users\jason burn\desktop\compsci class\hw3and4\sortedlist.cpp 50
Error 2 error C2923: 'Node' : 'Obj' is not a valid template type argument for parameter 'Obj' c:\users\jason burn\desktop\compsci class\hw3and4\sortedlist.cpp 50
Error 3 error C2512: 'Node' : no appropriate default constructor available c:\users\jason burn\desktop\compsci class\hw3and4\sortedlist.cpp 50
And for the next 3 errors, its a repeat of above, but on line 51 instead of line 50.
#11
Re: Problem with linked list class
Posted 25 March 2013  12:45 PM
#12
Re: Problem with linked list class
Posted 25 March 2013  01:00 PM
Quote
So what is an obj? Shouldn't it be the same Type as your template class Type?
Jim
#13
Re: Problem with linked list class
Posted 25 March 2013  01:06 PM
Edit: Obj is supposed to be a generic type, to be replaced by int in the case of my main. That is what I am trying anyway.
This post has been edited by jayburn00: 25 March 2013  01:08 PM
#14
Re: Problem with linked list class
Posted 25 March 2013  01:25 PM
template<class T> class SortedList { public: SortedList():head(NULL), tail(NULL), current(NULL), count(0) { head = new Node<Obj>; tail = new Node<Obj>;
Look closely at your class definition, what "generic type" is this class using? Hint: It's not "Obj".
Jim
#15
Re: Problem with linked list class
Posted 25 March 2013  01:28 PM
This post has been edited by jayburn00: 25 March 2013  01:30 PM
